Skip to content

Instantly share code, notes, and snippets.

@schnell18

schnell18/consistent_harshing.md

Last active December 26, 2023 04:23
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save schnell18/7eb6cccca8432da7d28f69ff5d15c92c to your computer and use it in GitHub Desktop.
Save schnell18/7eb6cccca8432da7d28f69ff5d15c92c to your computer and use it in GitHub Desktop.
Download ZIP
consistent hashing
Raw
consistent_harshing.md

gist of consistent hashing

Resolve rebalance problem of dynamic cluster. Key techniques:

  • determine hash space, eg 2 * PI or 16K like redis
  • map keys and nodes to the same hash space using hash function(s)
  • keys are placed on the first node with hash value greater than the key, or on the first node
  • use binary search tree to speed up locating the node for a paticular key
  • when new node joins, move keys with hash value smaller than the new node from its successor to the node
  • when existing node leaves, move keys on this node to its successor
  • to distribute keys evenly, create interpersed virtual nodes for each real node

References:

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment