Nextdoor 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.

• Core Concepts: How Things Actually Work · 9 minDistributed locks and leader electionMaking sure only one worker does a job at a time, and why a lock needs a lease and a fencing token to be safe.Read hereClose

  The need

  Sometimes only one worker may do something at a time: run a nightly job, update a shared resource, be the primary of a group. On one machine you use a mutex. Across machines you need a distributed lock or leader election, and failure makes it tricky.

  A naive lock and why it breaks

  SET lock:job 1 NX   (set only if not exists)
  ... do the work ...
  DEL lock:job
  

  Problems:

  • The holder crashes before deleting: the lock is stuck forever.
  • Add an expiry (a lease) to fix that, and a new problem appears: the holder is merely slow (a long pause, a network stall), the lease expires, a second worker takes the lock, then the first wakes up and keeps working. Now two hold it.

  Leases and fencing tokens

  A lease is a lock that expires unless renewed. It lets the system recover from failures, but it cannot, by itself, stop a stalled holder from acting after it has lost the lock.

  The fix is a fencing token: every time the lock is granted, the lock service hands out a number that always increases. The holder sends the token with every write to the protected resource, and the resource rejects any request with a token older than one it has already seen.

  100%

  Figure SDA-CORE-18-1 · Leases and fencing tokens · © forcsguy.com

  This makes safety depend on the resource, not on timing.

  Where to keep locks

  Use a service built for coordination, with consensus underneath: etcd, ZooKeeper, Consul. A single Redis instance gives a convenient but weaker lock (it can lose the lock on failover). If correctness matters, prefer a consensus-based service or a database transaction.

  Often you can avoid a lock: make the operation idempotent, use a conditional write (compare-and-set on a version), or let a queue hand each job to just one consumer.

  Image: Senior Airman John Wright · Public domain · Source · Wikimedia Commons: Lajes Field Air Traffic Control

  Leader election

  The same tools elect a leader: nodes compete to create an ephemeral key or hold a lease; the winner leads and renews it. If it fails, the lease expires and another is chosen. Followers watch for changes.

  • Expect brief periods with no leader during failover.
  • Guard against a former leader acting too late (fencing tokens again, or stepping down when it cannot renew).
  • Avoid split brain (two leaders) by requiring a majority (a quorum) to agree.

  Rules of thumb

  • Keep critical sections short, and renew the lease while working.
  • Prefer designs that need no lock: idempotency, conditional writes, partitioned ownership.
  • Always handle "I lost the lock" by stopping work.
  • Test with pauses and network partitions, not only crashes.

  More on this site

  Related reading

  • ZooKeeper: Wait-free Coordination for Internet-scale Systems (paper)Hunt et al. · Yahoo! ResearchPapers
  • How Ringpop from Uber Engineering Helps Distribute Your ApplicationUber Engineering · UberCase Studies
  • The Chubby Lock Service (paper)Mike Burrows · GooglePapers
  • Google SRE Book: Managing Critical State (Distributed Consensus)Google SRE team · GoogleBlogs

  Show 6 moreShow fewer

  • The Byzantine Generals Problem (paper)Lamport, Shostak and Pease · Microsoft ResearchPapers
  • Paxos Made Simple (paper)Leslie Lamport · Microsoft ResearchPapers
  • Apache ZooKeeperApache Software Foundation · GitHubGitHub
  • Google SRE Book: Distributed Periodic Scheduling with CronGoogle SRE team · GoogleBlogs
  • Nextdoor Engineering BlogNextdoor engineers · NextdoorBlogs
  • Localytics Engineering BlogLocalytics engineers · LocalyticsBlogs

  Open this lesson with its quiz and exercise