Section 5: Generation Numbers Are the Whole Trick - Data Modeling

Executive Summary: The whole lock service is three record kinds: the node (a file or directory, with its content and four counters), the lock attached to every node, and the session. The design turns on two decisions. First, each node carries separate generation numbers (instance, content, lock, ACL), because caches, compare-and-set and fencing each need a different question answered. Second, the state is split cleanly: anything that defines correctness (nodes, held locks, session existence, ephemeral ownership) goes through the replicated log, and anything a client can tell the master again (lease timers, handles, the cache registry, waiter queues) lives only in the master's memory. The whole database is about 1.3 GB in RAM on every replica.

The interviewer taps the API from Section 4 that's still on the board. "Every one of those calls reads or writes something. Show me the records, and tell me which of them survive the master dying."

You: "Three record kinds, and one rule for each field: if losing it on failover could produce two leaders or a stale read, it goes through consensus. If the client can repeat it to a new master, it stays in memory. That rule is what keeps the peak write rate at 500 per second, instead of adding another 8,300 for KeepAlives."

The Three Records

node     (path PK, type {file | dir}, permanence {permanent | ephemeral},
          owner_session_id            -- ephemeral nodes only
          content                     -- whole-file bytes, <= 256 KB
          instance_number             -- bumps when this name is deleted and re-created
          content_generation          -- bumps on every SetContents
          lock_generation             -- bumps on every free -> held transition
          acl_generation              -- bumps when the ACL names change
          content_checksum            -- 64-bit
          acl_names {read, write, change_acl}   -- paths of ACL files)

lock     (path PK, mode {free | exclusive | shared}, holder_session_ids[],
          lock_delay_seconds,         -- chosen by the holder at Open, 0-60 s
          released_by_expiry)         -- set by the session-expiry entry, cleared on next grant
          -- volatile: lock_delay_deadline, waiters[]

session  (session_id PK, client_identity  -- from the mTLS certificate
          created_at)                 -- deliberately NOT the lease expiry

An ACL is just a file listing principals; a new node inherits its parent directory's ACL names, one reason Section 4 chose a hierarchy. Every node is lockable, so the lock record is really part of the node, listed separately only because half of it is volatile.

Here is the running example's file just after master-b wins:

path                /ls/ny1/orders-db/master        file, permanent
content             "10.4.7.22:7000"                written by master-b via SetContents
lock                EXCLUSIVE, holder = orders-db-master-b's session, lock-delay 0 s
lock_generation     41                              -> sequencer /ls/ny1/orders-db/master:EXCLUSIVE:41
content_generation  g                               -> g+1 when master-c writes its address
instance_number     unchanged since the file was first created
acl_names           read  = /ls/ny1/acl/orders-db-readers
                    write = /ls/ny1/acl/orders-db-masters
                    change_acl = /ls/ny1/acl/orders-db-admins