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