scalaris-team/scalaris

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

GoogleCodeExporter opened this issue · 5 comments

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

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

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

>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

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

Since quite some time the replication degree is no longer hard coded. The configured replication_factor is used. It can be any integer >= 3, so that we can decide based on majorities.