notexOPENOverview
Notex/Systems/Two issues in the basic approach
05.10LESSON 10 OF 13 · 1 MIN READ

Two issues in the basic approach

Always free to read
SECTION VIDEOTwo issues in the basic approach

Video coming soon. Start with the reading below.

COMING SOON

The consistent hashing algorithm was introduced by Karger et al. at MIT [1]. The basic steps are:

  • Map servers and keys on to the ring using a uniformly distributed hash function.
  • To find out which server a key is mapped to, go clockwise from the key position until the first server on the ring is found.

Two problems are identified with this approach. First, it is impossible to keep the same size of partitions on the ring for all servers considering a server can be added or removed. A partition is the hash space between adjacent servers. It is possible that the size of the partitions on the ring assigned to each server is very small or fairly large. In Figure 5-10, if s1 is removed, s2’s partition (highlighted with the bidirectional arrows) is twice as large as s0 and s3’s partition.

Design consistent hashing — original diagram 62

Second, it is possible to have a non-uniform key distribution on the ring. For instance, if servers are mapped to positions listed in Figure 5-11, most of the keys are stored on server 2. However, server 1 and server 3 have no data.

Design consistent hashing — original diagram 63

A technique called virtual nodes or replicas is used to solve these problems.

Progress is saved on this device.
KEEP EXPLORING

One note leads to another.

Back to the library →
⌕
Search across the entire library ⌘ K