seyyed / scalaris

Automatically exported from code.google.com/p/scalaris
Apache License 2.0
0 stars 0 forks source link

A replicas num and a majority num are hardcoded in several places of the code #57

Open GoogleCodeExporter opened 8 years ago

GoogleCodeExporter commented 8 years ago
When I saw the scalaris source code, I found several places where the values of 
number of replicas and the size of majority are hardcoded. At the same time, 
these parameters are described in the configuration file. For obvious reasons, 
this situation is bad and needs correction. As I understood from the comments - 
is to avoid the execution of "expensive" division operation.
So I proposes to use the p-value - the power of 2. Therefore R= 2 pow p.

Besides these parameters mask the most important parameter for the user - a 
factor of fault tolerance - allowable number of simultaneous failures. Also the 
factor of majority should not be specified directly, because it is a value 
calculated from the number of replicas, so it should be removed from the 
config-file.

F = R - M, 
M = R div 2 +1,
so F = R - R div 2 -1 = R div 2 + R rem 2 -1
If the R is even (so it is, because R = 2 pow p) then 
F = R/2 -1 and 
M = R/2 +1

where 
F - factor of fault tolerance,
R - number of relicas/nodes,
M - majority factor

So if the p-value will be defined if config-file the table make the factor of 
fault tolerance obvious:

p          1      2      3      4     5
R          2      4      8     16    32
M          2      3      5      9    17
F          0      1      3      7    15

This table should be added to the scalaris user manual.

The ?RT:get_replica_keys(Key) will be changed in this case to something like 
this (a preliminary calculation may be needed):

get_replica_keys(Key) ->
  P = config:read(replication_power),
  R = 2 bshl P,
  S = 128, %% The key size in bits for case of the md5 hash
  Shift = S - P,
  [Key bxor (N bshl Shift) || N <- lists:seq(0, R-1)].

What do you think about this?

Original issue reported on code.google.com by serge.po...@gmail.com on 9 Aug 2010 at 1:08

GoogleCodeExporter commented 8 years ago
Yes, we could implement something similar in the meantime. In the long term, we 
plan to also distinguish read and write majorities. 
Most important is, that read and write sets are overlapping by at least one 
replica for strong consistency.

If you want faster reads than writes you can decrease the read majority and 
increase the required write majority accordingly and vice versa. So the 
spectrum of possibilities that Scalaris can offer, is not simply put into some 
static formulas.

Nevertheless, your proposed configuration probably will be the most common and 
a section on it in the documentation would help to understand the technology 
more easily. 

Original comment by schin...@gmail.com on 26 Aug 2010 at 10:17

GoogleCodeExporter commented 8 years ago
>If you want faster reads than writes you can decrease the read majority and 
increase 
>the required write majority accordingly and vice versa. So the spectrum of 
>possibilities that Scalaris can offer, is not simply put into some static 
formulas.

But in this case the base will lose consistency and partition tolerance 
properties...

Original comment by serge.po...@gmail.com on 26 Aug 2010 at 12:37

GoogleCodeExporter commented 8 years ago
No, still for each operation there would be at least one replica in each read 
set
that is also in a write set.

replicas = 4, write majority = 3, read majority = 2
replicas = 5, write majority = 4, read majority = 2

write majority + read majority > replicas

Original comment by schin...@gmail.com on 26 Aug 2010 at 4:06

GoogleCodeExporter commented 8 years ago
Ok, I see your point. But when we increase the write majority we simultaneously 
reduce the fault tolerance property. So some table with such dependenes should 
be in the documentation.

Original comment by serge.po...@gmail.com on 27 Aug 2010 at 10:00