Tronso
commented
3 years ago On the branch random_slicing we developed a prototype of an integration of Random Slicing into RCL. With the prototype we tried to replace Consistent Hashing with Random Slicing without affecting the system structure too much. From this prototype the following learnings resulted:
- The choice of using Consistent Hashing is indeed an architectural one and affects many modules that make assumptions on the inner workings and guarantees of CH.
- While the integration of Random Slicing has lead to many edge cases not working and many optimizations being lost (especially during handoffs), first benchmarks have shown a similar performance. This implies that with a proper integration Random Slicing could improve the system performance-wise.
- Because Random Slicing does not come with a replication placement strategy, one has to be developed. Of the ones included with the prototype one (Ring Rotation) has proven as completely unusable while the others could be improved upon.
- Random Slicing not only replaces Consistent Hashing but also the claim algorithm.
- Adding weights to nodes can easily be achieved by using the metadata entries in RCL's ring and the native support for weights in Random Slicing.
Overall we assess a restructuring of RCL to replace Consistent Hashing with Random Slicing as beneficial for the system. However, the amount of necessary work and sources for potential errors to achieve this is significant.
Now that the code base is much smaller, possible changes in the architecture could be discussed. Possible starting points mentioned by Scott Lystig Fritchie:
[ ] The only string-to-integer hash algorithm is SHA-1.
[ ] The hash “rings” integer interval is the range 0 to 2^160-1.
[ ] The number of partitions is fixed.
[ ] The number of partitions must be a power of 2.
[ ] The size of each partition is fixed.
[ ] Historically, the “claim assignment” algorithm used to assign servers to intervals on the ring were buggy and naive and frequently created imbalanced workload across nodes.
[ ] Server capacity adjustment by “weighting” did not exist: all servers were assumed equal.
[ ] No support for segregating extremely “hot” keys, for example, Twitter’s “Justin Bieber” account.
[ ] No effective support for “rack-aware” or “fault domain aware” replica placement policy
Any of these changes will only concern the next major release most probably.