notexOPENOverview
Notex/Systems/Design consistent hashing

Design consistent hashing

Always free to read

To achieve horizontal scaling, it is important to distribute requests/data efficiently and evenly across servers. Consistent hashing is a commonly used technique to achieve…

05

DESIGN CASE STUDIES

Design consistent hashing

13 LESSONS · 15 MIN
  1. 05.01Design consistent hashingTo achieve horizontal scaling, it is important to distribute requests/data efficiently and evenly across servers. Consistent hashing is a commonly used technique to achieve…READING1 MIN
  2. 05.02The rehashing problemIf you have n cache servers, a common way to balance the load is to use the following hash method: serverIndex = hash(key) % N, where N is the size of the server pool. Let us…READING2 MIN
  3. 05.03Consistent hashingQuoted from Wikipedia: "Consistent hashing is a special kind of hashing such that when a hash table is re-sized and consistent hashing is used, only k/n keys need to be…READING1 MIN
  4. 05.04Hash space and hash ringNow we understand the definition of consistent hashing, let us find out how it works. Assume SHA-1 is used as the hash function f, and the output range of the hash function is:…READING1 MIN
  5. 05.05Hash serversUsing the same hash function f, we map servers based on server IP or name onto the ring. Figure 5-5 shows that 4 servers are mapped on the hash ring.READING1 MIN
  6. 05.06Hash keysOne thing worth mentioning is that hash function used here is different from the one in “the rehashing problem,” and there is no modular operation. As shown in Figure 5-6, 4…READING1 MIN
  7. 05.07Server lookupTo determine which server a key is stored on, we go clockwise from the key position on the ring until a server is found. Figure 5-7 explains this process. Going clockwise, key0…READING1 MIN
  8. 05.08Add a serverUsing the logic described above, adding a new server will only require redistribution of a fraction of keys. In Figure 5-8, after a new server 4 is added, only key0 needs to be…READING1 MIN
  9. 05.09Remove a serverWhen a server is removed, only a small fraction of keys require redistribution with consistent hashing. In Figure 5-9, when server 1 is removed, only key1 must be remapped to…READING1 MIN
  10. 05.10Two issues in the basic approachThe 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…READING1 MIN
  11. 05.11Virtual nodesA virtual node refers to the real node, and each server is represented by multiple virtual nodes on the ring. In Figure 5-12, both server 0 and server 1 have 3 virtual nodes.…READING2 MIN
  12. 05.12Find affected keysWhen a server is added or removed, a fraction of data needs to be redistributed. How can we find the affected range to redistribute the keys? In Figure 5-14, server 4 is added…READING1 MIN
  13. 05.13Wrap upIn this chapter, we had an in-depth discussion about consistent hashing, including why it is needed and how it works. The benefits of consistent hashing include: Minimized keys…READING1 MIN

References

Wrap up
  1. Consistent hashing: https://en.wikipedia.org/wiki/Consistent_hashing
  2. Consistent Hashing: https://tom-e-white.com/2007/11/consistent-hashing.html
  3. Dynamo: Amazon’s Highly Available Key-value Store: https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
  4. Cassandra - A Decentralized Structured Storage System: http://www.cs.cornell.edu/Projects/ladis2009/papers/Lakshman-ladis2009.PDF
  5. How Discord Scaled Elixir to 5,000,000 Concurrent Users: https://blog.discord.com/scaling-elixir-f9b8e1e7c29b
  6. CS168: The Modern Algorithmic Toolbox Lecture #1: Introduction and Consistent Hashing: http://theory.stanford.edu/~tim/s16/l/l1.pdf
  7. Maglev: A Fast and Reliable Software Network Load Balancer: https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf
KEEP EXPLORING

One note leads to another.

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