CSE Roadmap

Common tier · about 4 hours · 7 parts

Part 3 of 7 · 2 min read

Core

Consensus, a small tree, sessions.

Replicas and consensus. Run 3 or 5 replicas, in separate failure zones. They agree on every change through a consensus algorithm (Raft or Paxos, Level 5), which gives a single order of all writes. One replica is the leader of the group. Writes go through it, and a write counts when a majority has it. 3 replicas tolerate 1 failure and 5 tolerate 2. A majority also stops two sides of a network split from both making decisions: only one side can have a majority.

Data model. A small tree of named entries, like a file system. Each entry has a name, a small value, a version number, and a type: persistent or ephemeral. The tree is kept in memory and written to disk for safety.

Operations.

  • Read an entry, write an entry, list the children of an entry.
  • Compare-and-set (CAS): change the entry only if its version is still the one the client saw. Because the group agrees on a single order, only one of several concurrent CAS calls can succeed. This is the base of a lock.
  • Create an entry that must not already exist. If two clients try at once, one wins.

Sessions and failure detection. A client opens a session with the service and sends heartbeats (small "I am alive" messages). If heartbeats stop for longer than the session timeout, the service declares the session dead. A short break in the connection, or the failure of one replica, does not end a session, since the session lives in the replicated state.

Ephemeral entries. An entry tied to a session. When the session dies, the entry disappears. This is the basis of automatic lock release and membership: a client's entry exists exactly while the client is alive.

Watches (change notifications). A client can ask to be told when an entry changes, so it need not poll. When the leader's entry vanishes, every waiting client is told at once.

A worked example (made up). 100,000 clients each send a heartbeat every 5 seconds. That is 20,000 messages a second, a modest load for the leader of a group. To keep the cost low, heartbeats are handled by the leader without a consensus round for each. Only the session creation and expiry go through the log.

Reads. Reads can be served by any replica, which is fast but may return slightly old data. A client that needs the latest value asks the leader, or asks the replica to first catch up to the leader's position.

Ephemeral entry

An ephemeral entry is an entry that the service deletes automatically when the session that created it ends.

Example: a server registers "server-7" as ephemeral. When server 7 crashes and stops heartbeating, the entry disappears and watchers learn it is gone.

Check yourself: 1. What does CAS guarantee, and why? 2. What happens to an ephemeral entry when a session dies? 3. Why can a single replica failure not end a session?