XING Engineering Blog

Ideas you will meet

Distributed Systems

Consensus, time, failure and the fundamentals of scale-out.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• Classic System Designs · 10 minDesign consistent hashingHow to spread keys over servers so that adding or removing a server moves only a small share of them.Read hereClose

  The problem

  You have a cluster of cache or storage servers and need a rule that says which server holds which key. The first idea is server = hash(key) mod N. It works until N changes, which it always does: a server fails, or you add capacity.

  100%

  Figure SDA-CSD-02-1 · Why mod-N hashing breaks when N changes · © forcsguy.com

  When N changes, almost every key maps somewhere new. A cache suddenly misses on nearly everything and the database behind it is flooded. A storage cluster would have to shuffle most of its data.

  Goal: when a server joins or leaves, only about 1/N of the keys should move.

  The idea: a hash ring

  1. Imagine hash values arranged in a circle (the ring), from 0 up to a maximum and wrapping around.
  2. Hash each server onto the ring.
  3. Hash each key onto the same ring.
  4. A key belongs to the first server clockwise from its position.

  100%

  Figure SDA-CSD-02-2 · Hash ring ownership · © forcsguy.com

  Adding a server D between A and B takes over only the keys that fall between A and D. Everything else stays where it is. Removing a server hands its keys to its clockwise neighbour. Either way, only the neighbouring arc moves.

  Before: hash mod N

  100%

  After: consistent hashing ring

  100%

  What changed

  • Adding a server moves only a small slice of keys
  • Cache hit rate does not collapse after a change
  • Virtual nodes even out the load

  Finding the owner efficiently

  Keep the server positions in a sorted list. To place a key, hash it and use a binary search for the first position greater than or equal to it, wrapping to the first server if you pass the end. That is O(log N) per lookup.

  Two problems with the basic ring

  100%

  Figure SDA-CSD-02-3 · Why a plain ring can be unfair · © forcsguy.com

  Fixing uneven load: virtual nodes

  With only a handful of servers, the arcs between them are uneven, so some servers hold far more keys. And when a server dies, all its load lands on a single neighbour.

  The fix is virtual nodes: each physical server is hashed at many points (say 100 to 200) on the ring.

  100%

  Figure SDA-CSD-02-4 · Virtual nodes per server · © forcsguy.com

  • Keys spread much more evenly.
  • When a server leaves, its load is shared among many others.
  • A bigger server can be given more virtual nodes than a smaller one.

  The cost is a larger ring to store and update.

  Which keys move, exactly

  When a server joins, find the previous server going anticlockwise from it; only the keys between that neighbour and the new server move, and they all move to the new server. When a server leaves, the keys it held (the span back to its anticlockwise neighbour) move to the next server clockwise. Nothing else is touched, which is why the data transfer stays small and predictable.

  Spreading keys evenly also reduces hotspots: without it, several very popular keys can land on the same server and overload it. With many virtual nodes per server, the spread gets tighter (published experiments show the imbalance shrinking from around 10 percent to about 5 percent as virtual nodes per server go from roughly 100 to 200), at the price of more ring metadata to store, so the count is a tuning knob.

  100%

  Figure SDA-CSD-02-5 · Adding a server to the ring · © forcsguy.com

  100%

  Figure SDA-CSD-02-6 · Removing a server from the ring · © forcsguy.com

  Where it is used

  • Distributed caches (so adding a node does not wipe the cache).
  • Partitioned databases such as Dynamo-style stores, where each key is also copied to the next few servers clockwise for replication (next lesson).
  • Load balancing with stickiness, where the same client keeps hitting the same backend.
  • Content delivery to decide which edge server holds an object.

  Things to watch

  • Hot keys: one very popular key still loads its owner. Replicate it or add a local cache.
  • Choose a good hash function: uniform distribution matters more than cryptographic strength.
  • Membership changes must be learned by all clients consistently, through a config service or gossip, otherwise two clients disagree about the owner.

  More on this site

  Related reading

  • Consistent Hashing and Random Trees (paper)Karger et al. · MITPapers
  • NGINX HTTP Load BalancingNGINX · F5 / NGINXDocumentation
  • Time, Clocks, and the Ordering of Events in a Distributed System (paper)Leslie Lamport · Microsoft ResearchPapers
  • Clock Skew when Syncing Password Payloads at DrobboxDrobbox engineers · DrobboxCase Studies

  Show 6 moreShow fewer

  • The System Design PrimerDonne Martin · donnemartinGitHub
  • Solving Remote Build Cache Misses (2 parts) at SoundCloudSoundCloud engineers · SoundCloudCase Studies
  • Load Balancing infrastructure to support more than 1.3 billion users at FacebookFacebook engineers · FacebookCase Studies
  • Meta Engineering BlogMeta Engineering · MetaBlogs
  • XING Engineering BlogXING engineers · XINGBlogs
  • Gusto Engineering BlogGusto engineers · GustoBlogs

  Open this lesson with its quiz and exercise