Skip to content

Consistent Hashing

Hashing allows us to map a key to a number that represents a node

In large scale systems, one cluster (cache cluster, server cluster, db cluster) is not enough

Hashing can be used to determine which node should be used for the given request

Simple Hashing

  • HashFunction(key) % N
  • N is number of nodes
  • HashFunction looks to distribute evenly
  • Issue: what if N changes, all keys are now corrupt as the same node won't be used

Consistent Hashing

  • Aimed to have consistent node assignment even has N changes
  • Hash the key and server name
  • Range of x0 to xN (Hash Space)
  • Implementation
    • Make 0->N in a ring
    • HashFunction(server name/ip)
    • HashFunction(key)
    • Retrieve
      • Find Hash of key and go clockwise until a server found
    • If N changes, only one range of keys gets lost
    • Issue: distribution of objects may be uneven
      • Solution: Virtual Nodes, spread apart a single node on the ring as virtual nodes
      • Now nodes won't be starved of traffic
      • Takes metadata for maintaining virtual nodes
  • Real life usages
    • DynamoDB and Cassandra - Data Partitioning
      • Minimizes data movement during rebalances
    • Content Delivery Networks - Distribute web content
    • Load Balancer - Distribute persistent connections evenly