# NK on System Design - Consistent Hashing Algorithm (Highlights)  ## Metadata **Review**:: [readwise.io](https://readwise.io/bookreview/24670088) **Source**:: #from/readwise **Zettel**:: #zettel/fleeting **Status**:: #x **Authors**:: [[NK on System Design]] **Full Title**:: Consistent Hashing Algorithm **Category**:: #articles #readwise/articles **Category Icon**:: 📰 **URL**:: [highscalability.com](http://highscalability.com/blog/2023/2/22/consistent-hashing-algorithm.html) **Host**:: [[highscalability.com]] **Highlighted**:: [[2023-02-23]] **Created**:: [[2023-02-24]] ## Highlights - The static hash partitioning is not horizontally scalable. The removal of a node (due to a server crash) breaks the existing mappings between the keys and nodes. The keys must be rehashed to restore mapping between keys and nodes [3]. ([View Highlight](https://read.readwise.io/read/01gsy0878wbmcek0g6frx0vqgn)) ^480747121 - Consistent hashing minimizes the number of keys to be remapped when the total number of nodes changes [4]. ([View Highlight](https://read.readwise.io/read/01gsy09f1d3qj2rck7qwc639wp)) ^480747442 - The basic gist behind the consistent hashing algorithm is to hash both node identifiers and data keys using the same hash function. ([View Highlight](https://read.readwise.io/read/01gsy0a5jx43z4pwz8y8b59nkh)) ^480747477 - The key of the data object is hashed using the same hash function to locate the position of the key on the hash ring. The hash ring is traversed in the clockwise direction starting from the position of the key until a node is found. ([View Highlight](https://read.readwise.io/read/01gsy0d0x1zjns11v4rzgfvrmj)) ^480747642 - The failure (crash) of a node results in the movement of data objects from the failed node to the immediate neighboring node in the clockwise direction. ([View Highlight](https://read.readwise.io/read/01gsy0f9r52zxx4axpynr2afqe)) ^480747970 - When a new node is provisioned and added to the hash ring, the keys (data objects) that fall within the range of the new node are moved out from the immediate neighboring node in the clockwise direction. ([View Highlight](https://read.readwise.io/read/01gsy0frt54h9knxf3da0052zp)) ^480748030 - There is a chance that nodes are not uniformly distributed on the consistent hash ring. The nodes that receive a huge amount of traffic become hotspots resulting in [cascading failure](https://en.wikipedia.org/wiki/Cascading_failure) of the nodes. ([View Highlight](https://read.readwise.io/read/01gsy0gpt41sgrpkp0rqfk7mfh)) ^480748088 - The nodes are assigned to multiple positions on the hash ring by hashing the node IDs through distinct hash functions to ensure uniform distribution of keys among the nodes. The technique of assigning multiple positions to a node is known as a **virtual node**. The virtual nodes improve the load balancing of the system and prevent hotspots. ([View Highlight](https://read.readwise.io/read/01gsy0hfsnkk56b47k0kjc5x0t)) ^480748188 - The self-balancing binary search tree (**BST**) data structure is used to store the positions of the nodes on the hash ring. ([View Highlight](https://read.readwise.io/read/01gsy0mbmvfsm3ce5xpbmr537b)) ^480748313 - The BST data structure is stored on a centralized highly available service. As an alternative, the BST data structure is stored on each node, and the state information between the nodes is synchronized through the gossip protocol [7]. ([View Highlight](https://read.readwise.io/read/01gsy0mgs0r5gs5sjmyhvye820)) ^480748318 - [MurmurHash](https://en.wikipedia.org/wiki/MurmurHash) is a relatively cheaper hash function. The non-cryptographic hash functions like [xxHash](https://github.com/cespare/xxhash), [MetroHash](https://github.com/dgryski/go-metro), or [SipHash1–3](https://github.com/dgryski/go-sip13) are other potential candidates [6]. ([View Highlight](https://read.readwise.io/read/01gsy0p40meaqgsbkh6hw2j57x)) ^480748446 - The basic gist of multi-probe consistent hashing is to hash the key (data object) multiple times using distinct hash functions on lookup and the closest node in the clockwise direction returns the data object [12]. ([View Highlight](https://read.readwise.io/read/01gsy0t7sf73y8g9qef2ct1ybx)) ^480750224 - The consistent hashing with bounded load puts an upper limit on the load received by a node on the hash ring, relative to the average load of the whole hash ring. The distribution of requests is the same as consistent hashing as long as the nodes are not overloaded [13]. ([View Highlight](https://read.readwise.io/read/01gsy0x89wxkf45gk7y9cm0hdh)) ^480751221