Lesson 30 · Consensus · Module 3

Consensus as a Product

Lessons 27 to 29 built a consensus algorithm. Nobody wants a consensus algorithm. What people want is for exactly one worker to run the nightly job, and for the other workers to find out promptly when it dies. This lesson is about the service that sits between those two sentences.

The win in this lesson: you will be able to build leader election out of ephemeral sequential znodes, and explain why the herd-avoiding version has each contender watch only its immediate predecessor rather than the whole set.

1. Everyone rebuilds the same four things, badly

Before the mechanism, the observation that motivates it. Coordination is not one problem; it is a small, stubbornly recurring family of them:

"Large-scale distributed applications require different forms of coordination. Configuration is one of the most basic forms of coordination. […] Group membership and leader election are also common in distributed systems: often processes need to know which other processes are alive and what those processes are in charge of. Locks constitute a powerful coordination primitive that implement mutually exclusive access to critical resources."

ZooKeeper: Wait-free coordination for Internet-scale systems, Hunt, Konar, Junqueira & Reed, USENIX ATC 2010, §1 — de-hyphenated across the PDF's line breaks

Four needs, and every team meets them the same way: a row in the database with a locked_until column, a heartbeat table, a config file shipped by the deploy pipeline. Each of those is a small, private, untested consensus implementation, and lesson 26 has already told you how those end.

The obvious response is to ship a service per primitive — a lock service, an election service, a membership service. ZooKeeper's authors refused:

"When designing our coordination service, we moved away from implementing specific primitives on the server side, and instead we opted for exposing an API that enables application developers to implement their own primitives. Such a choice led to the implementation of a coordination kernel that enables new primitives without requiring changes to the service core."

Hunt et al., §1 — de-hyphenated

That is the product decision this whole lesson hangs on. The server ships a tiny, boring data model. The interesting primitives — locks, elections, barriers — are library code on the client. The server never learns the word "lock".

2. The data model: a tiny file system that forgets

"ZooKeeper provides to its clients the abstraction of a set of data nodes (znodes), organized according to a hierarchical name space."

Hunt et al., §2.1 — de-hyphenated

It looks like a file system and it is deliberately not one. Znodes hold at most a megabyte by default — "Each znode in the tree stores a maximum of 1MB of data by default" (§4) — reads and writes are whole-value, and there is no open() or close(): every request carries the full path. What you store here is metadata about your system, not your system's data.

Three flags on create() do nearly all the work.

The ephemeral flag is the one that removes work from you:

"Ephemeral: Clients create such znodes, and they either delete them explicitly, or let the system remove them automatically when the session that creates them terminates (deliberately or due to a failure)."

Hunt et al., §2.1 — de-hyphenated

Note "or due to a failure". This is failure detection you do not have to write. The sequential flag is the other half:

"Nodes created with the sequential flag set have the value of a monotonically increasing counter appended to its name. If n is the new znode and p is the parent znode, then the sequence value of n is never smaller than the value in the name of any other sequential znode ever created under p."

Hunt et al., §2.1 — de-hyphenated

Set both flags at once and a single call buys you two things that are painful to build separately: a position in a global queue, and an entry that disappears the moment you do.

3. Watches: one shot, and that is the point

Polling a coordination service is how you turn it into your bottleneck. Watches replace the poll:

"When a client issues a read operation with a watch flag set, the operation completes as normal except that the server promises to notify the client when the information returned has changed."

Hunt et al., §2.1 — de-hyphenated

Then two sentences that every bug report about ZooKeeper eventually traces back to:

"Watches are one-time triggers associated with a session; they are unregistered once triggered or the session closes. Watches indicate that a change has happened, but do not provide the change."

Hunt et al., §2.1

A watch is not a subscription and not a message queue. It is a cache invalidation: what you hold is stale. It carries no payload and it fires at most once. Read the value again — with a new watch — or stop caring.

One ordering guarantee makes watches safe to build on, and it is easy to miss. The notification overtakes the data: "if a client is watching for a change, the client will see the notification event before it sees the new state of the system after the change is made" (§2.3, de-hyphenated). You can therefore never read the new value while still believing your watch has not fired.

4. The bargain: linearizable writes, local reads

ZooKeeper promises exactly two orderings, and it is worth reading what is not in them.

"Linearizable writes: all requests that update the state of ZooKeeper are serializable and respect precedence; […] FIFO client order: all requests from a given client are executed in the order that they were sent by the client."

Hunt et al., §2.3 — de-hyphenated, and the two guarantees are separated by their labels in the original

Writes go through atomic broadcast to the leader and a majority — lesson 29's machinery, wearing a different name. Reads do not go anywhere:

"Because only update requests are A-linearizable, ZooKeeper processes read requests locally at each replica. This allows the service to scale linearly as servers are added to the system."

Hunt et al., §2.3

That is the whole trade, and the paper does not hide the bill:

"One drawback of using fast reads is not guaranteeing precedence order for read operations. That is, a read operation may return a stale value, even though a more recent update to the same znode has been committed."

Hunt et al., §4.4 — de-hyphenated

The escape hatch is one call:

"sync(path) : Waits for all updates pending at the start of the operation to propagate to the server that the client is connected to. […] To guarantee that a given read operation returns the latest updated value, a client calls sync followed by the read operation."

Hunt et al., §2.2 and §4.4 — de-hyphenated

You need it in exactly one situation, and it is worth being able to recognise: when the news reached you by some path other than ZooKeeper. A teammate's service tells you over HTTP that it has published new config; you read the znode and see the old value, because your replica has not caught up.

5. The recipes

Now the payoff. Every primitive below is client library code over the same four calls.

Group membership

"We take advantage of ephemeral nodes to implement group membership. […] If the process fails or ends, the znode that represents it under zg is automatically removed."

Hunt et al., §2.4 — de-hyphenated

Each member creates one ephemeral child of /members and then forgets about it. Membership is getChildren("/members"). There is no deregistration path to get wrong, no reaper job, no tombstone with a TTL — the liveness check is the session itself.

Configuration

Read the config znode with a watch; on notification, read it again with a new watch. The subtle part is publishing a set of values atomically, and the trick is a second znode used as a flag:

"the new leader can designate a path as the ready znode; other processes will only use the configuration when that znode exists. The new leader makes the configuration change by deleting ready , updating the various configuration znodes, and creating ready . […] Because of the ordering guarantees, if a process sees the ready znode, it must also see all the configuration changes made by the new leader."

Hunt et al., §2.3 — de-hyphenated

FIFO client order does the work. No transaction spans the writes; the ordering guarantee makes one unnecessary. And if the publisher dies halfway, ready simply never reappears, so nobody uses the half-written config.

Locks and leader election, the naive version

The simplest lock is a race to create one ephemeral znode: "To acquire a lock, a client tries to create the designated znode with the EPHEMERAL flag. If the create succeeds, the client holds the lock" (§2.4). Losers watch it and retry when it disappears. This works, and it has a failure mode you met in lesson 03:

"While this simple locking protocol works, it does have some problems. First, it suffers from the herd effect. If there are many clients waiting to acquire a lock, they will all vie for the lock when it is released even though only one client can acquire the lock."

Hunt et al., §2.4

One deletion wakes 500 clients. Of those, 499 lose and go back to watching. The cache stampede in lesson 03 had exactly this shape, and so does the fix: make sure only one waiter is woken.

The herd-avoiding version — the one to memorise

Here is the recipe, reproduced from the paper's Lock pseudo-code (§2.4), with its line numbers and spacing normalised:

Lock
  1  n = create(l + "/lock-", EPHEMERAL|SEQUENTIAL)
  2  C = getChildren(l, false)
  3  if n is lowest znode in C, exit
  4  p = znode in C ordered just before n
  5  if exists(p, true) wait for watch event
  6  goto 2

Unlock
  1  delete(n)

Six lines, and three of them are load-bearing. Line 1 gets you a queue position from the service: "The use of the SEQUENTIAL flag in line 1 of Lock orders the client's attempt to acquire the lock with respect to all other attempts" (§2.4, de-hyphenated). Line 3 is the entire winning condition — lowest wins, and no client has to be told it won. Line 5 is the herd fix:

"By only watching the znode that precedes the client's znode, we avoid the herd effect by only waking up one process when a lock is released or a lock request is abandoned."

Hunt et al., §2.4

Count the watches. Every znode in the queue is watched by exactly one other client — the one directly behind it. So a deletion anywhere in the queue can only ever fire one notification:

"The removal of a znode only causes one client to wake up, since each znode is watched by exactly one other client, so we do not have the herd effect; […] There is no polling or timeouts;"

Hunt et al., §2.4

Leader election is this recipe with the names changed. "Holds the lock" becomes "is the leader"; the queue becomes the succession order. Nothing else differs.

That last point is line 6 — goto 2 — and the paper spells out why it is not optional: "Once the znode being watched by the client goes away, the client must check if it now holds the lock. (The previous lock request may have been abandoned and there is a znode with a lower sequence number still waiting for or holding the lock.)" (§2.4, de-hyphenated). Waking up is not winning.

6. Residual risk

Three prices, all of them design choices rather than defects, and all of them things you will meet in production before you meet them in the documentation.

Your read may be stale, and there is no error code for it. A follower that has fallen behind answers happily. If a decision depends on a value another client wrote, and you learned of that write outside ZooKeeper, you need sync first — or you need to restructure so the news arrives as a watch. The authors were candid that this is the deal they struck:

"Although our consistency guarantees for reads and watches appear to be weak, we have shown with our use cases that this combination allows us to implement efficient and sophisticated coordination protocols at the client even though reads are not precedence-ordered and the implementation of data objects is wait-free."

Hunt et al., §7 — de-hyphenated

Watch semantics punish clever code. One shot; no payload; re-arm on every read. Two extra traps: notifications are tracked only by the server you happen to be attached to — "Only the server that a client is connected to tracks and triggers notifications for that client" (§4.4) — and connection-loss events arrive on the same callback, precisely "so that clients know that watch events may be delayed" (§2.1, de-hyphenated). Treat a session event as "everything you believe may now be wrong", not as noise to be logged and ignored.

Session expiry is the failure detector, and it is a timeout. That means it can be wrong:

"To detect client session failures, ZooKeeper uses timeouts. The leader determines that there has been a failure if no other server receives anything from a client session within the session timeout."

Hunt et al., §4.4 — de-hyphenated

And the boundary conditions of the service itself: availability holds only while "a majority of ZooKeeper servers are active and communicating" (§2.3, de-hyphenated), writes cost a quorum round trip plus a disk force, and the design is tuned for a read-heavy world — the abstract names a "2:1 to 100:1 read to write ratio". A coordination service used as a database will disappoint you in a way the paper never promised otherwise.

7. Check yourself

8. Back to your world

Find the place in your own system where exactly one thing must be true at a time — one scheduler, one migration runner, one consumer of a partition. Ask it three questions.

First: when the holder dies without cleaning up, what deletes its claim? If the answer is a timestamp column and a cron job, you have written an ephemeral node badly. Second: when the claim disappears, how many processes wake up? If the answer is "all of them", you have the naive lock, and the fix is to give the waiters an order and have each watch only the one in front. Third: when a waiter wakes, does it re-check, or does it assume it won? Line 6 exists for a reason.

Then the uncomfortable one. Your lock protects something — a table, a file, an external API. If the holder pauses for thirty seconds and loses its session, that something will receive writes from two processes that both believe they hold the lock. Does it reject the older one?