Your technical library
Landmark Cloud Systems
10 modules · 69 topics
About this book
Landmark Cloud Systems
Engineers meet DynamoDB, S3, Spanner, Lambda and Kubernetes every day as black boxes with documented limits: a per-partition throughput ceiling, a read-after-write guarantee, a cold start, a reconciliation loop that "eventually" converges. Those limits follow from a handful of design decisions, each taken against a named alternative for a stated reason. This course teaches the decisions, read from the systems' own papers and engineers, so that you can predict a system's behaviour beyond its documentation, model your data and workload to its grain, and reuse its ideas in your own designs. It builds on System Design and the courses beneath it: replication, consensus, clocks and the rest are recapped in a line and linked, and each lesson spends its length on what this system decided and why.
There is one module per system: DynamoDB; Aurora; S3; EBS and Physalia, the consensus store behind Amazon's block volumes; Firecracker and Lambda; Spanner; Aurora DSQL; Borg to Kubernetes; and Zanzibar, Google's authorization system. Each opens with the problem that forced the system into existence, then the contract it exposes, the decisions behind that contract and what it forces on its users. Modules are independent: take any system once you have its prerequisites. Reading the systems against each other closes the course by comparing them on the ideas they share — where consensus sits, how blast radius is contained, and how a contract shapes the data models built on it.
69 topics across 10 modules, in dependency order.
69 of 69 topics are authored. Modules are independent: take any system after its cross-course prerequisites. Each topic opens with the problem it inherits and closes with what it leaves open. Planned lessons are labelled and excluded from progress; references cover authored material.
Read at your own pace. Each topic is one continuous page; mark it done as you finish.
Start with 01.1 · From Dynamo to DynamoDB: why the service dropped leaderless replicationReview what you have finished↷ 0 skipped topics- 01.1From Dynamo to DynamoDB: why the service dropped leaderless replication
- 01.2Log replicas and leader failure: healing a replication group in seconds
- 01.3Metadata routing: why request routers do constant work
- 01.4Throughput dilution: why dividing a table's capacity among partitions failed
- 01.5Global admission control, split for consumption, and on-demand
- 01.6One-shot transactions without locks or versions
- 01.7Global secondary indexes as asynchronously replicated tables
- 01.8Access-pattern-first modelling and single-table design
- 01.9The operating envelope: partition ceilings and hot keys
- 02.1The log is the database: shipping only redo to storage
- 02.2Six copies in three zones: sizing a quorum for correlated failure
- 02.3Ten-gigabyte segments: repair time as the durability lever
- 02.4The storage node: foreground acknowledgement, background everything
- 02.5Consistency points instead of consensus: VCL, VDL and asynchronous commit
- 02.6Reading from one segment: why Aurora avoids quorum reads
- 02.7Read replicas that share the volume
- 02.8Recovery without redo replay
- 02.9Changing quorum membership without stalling: quorum sets and epochs
- 02.10The operating envelope: one writer, fast clones, and where Aurora does not help
- 03.1The object contract: immutable versions, no rename, no append
- 03.2Durability as arithmetic: erasure coding, repair and eleven nines
- 03.3Heat management: why spreading data across millions of drives smooths load
- 03.4ShardStore: an LSM-indexed, extent-based storage node with soft-updates crash consistency
- 03.5Strong read-after-write consistency at no added cost
- 03.6Conditional writes: building coordination on an object store
- 03.7Prefix scaling and 503 SlowDown: the index's partitioning, seen from outside
- 05.1The isolation requirements that ruled out containers and QEMU
- 05.2A minimal VMM: fewer devices, one process per VM, and a jailer
- 05.3Slots, placement and oversubscription
- 05.4Loading 10 GB container images on demand, block by block
- 05.5Deduplication without trust: convergent encryption
- 05.6A tiered cache erasure-coded for the tail
- 05.7Snapshot restore and the uniqueness problem
- 05.8What the design forces on users: concurrency, cold starts and retries
- 06.1External consistency: the contract, and why Bigtable and Megastore fell short
- 06.2Two-phase commit over Paxos groups
- 06.3TrueTime's engineering: GPS, atomic clocks and a bounded ε
- 06.4Commit wait and leader leases: proving external consistency
- 06.5Snapshot reads at safe time
- 06.6Interleaved tables, splits and hotspots: what the layout forces on schemas
- 06.7Becoming a SQL system: distributed union, range extraction and query restarts
- 06.8Availability and CAP: a CP system that is effectively CA
- 07.1Coordination only at commit: the disaggregated architecture
- 07.2Reads at a timestamp: precise clocks instead of coordination
- 07.3Adjudicators and optimistic concurrency: strong snapshot isolation
- 07.4The journal and the crossbar: durability and total order
- 07.5Multi-region commit in one round trip, with a witness region
- 07.6What OCC and disaggregation force on applications
- 08.1Shared cells: why mixing production and batch raises utilisation
- 08.2Scheduling by feasibility and scoring, and making it fast
- 08.3Limits versus reservations: reclaiming what tasks do not use
- 08.4From Borgmaster to Omega: shared state and optimistic schedulers
- 08.5The declarative API: desired state, observed state and optimistic concurrency
- 08.6Level-triggered reconciliation: acting on state, not on events
- 08.7Watches, informer caches and stale reads
- 08.8Deletion as a protocol: owner references, garbage collection and finalizers
- 08.9The scale envelope: what bounds a cluster's size
- 09.1The serving contract: global checks at millisecond latency, consistent with content
- 09.2Zookies: carrying a consistency token with the content
- 09.3Check evaluation, snapshot quantisation and a distributed cache
- 09.4Leopard: flattening nested groups into set intersections
- 09.5Hot spots, performance isolation and request hedging
01.2Log replicas and leader failure: healing a replication group in seconds
01.3Metadata routing: why request routers do constant work
01.4Throughput dilution: why dividing a table's capacity among partitions failed
01.5Global admission control, split for consumption, and on-demand
01.6One-shot transactions without locks or versions
01.7Global secondary indexes as asynchronously replicated tables
01.8Access-pattern-first modelling and single-table design
01.9The operating envelope: partition ceilings and hot keys
02.1The log is the database: shipping only redo to storage
02.2Six copies in three zones: sizing a quorum for correlated failure
02.3Ten-gigabyte segments: repair time as the durability lever
02.4The storage node: foreground acknowledgement, background everything
02.5Consistency points instead of consensus: VCL, VDL and asynchronous commit
02.6Reading from one segment: why Aurora avoids quorum reads
02.7Read replicas that share the volume
02.8Recovery without redo replay
02.9Changing quorum membership without stalling: quorum sets and epochs
02.10The operating envelope: one writer, fast clones, and where Aurora does not help
03.1The object contract: immutable versions, no rename, no append
03.2Durability as arithmetic: erasure coding, repair and eleven nines
03.3Heat management: why spreading data across millions of drives smooths load
03.4ShardStore: an LSM-indexed, extent-based storage node with soft-updates crash consistency
03.5Strong read-after-write consistency at no added cost
03.6Conditional writes: building coordination on an object store
03.7Prefix scaling and 503 SlowDown: the index's partitioning, seen from outside
04.1The re-mirroring storm: when the configuration store is the availability
04.2Millions of tiny databases: partitioning consensus by key
04.3Placing consensus next to its clients: availability where it matters
05.1The isolation requirements that ruled out containers and QEMU
05.2A minimal VMM: fewer devices, one process per VM, and a jailer
05.3Slots, placement and oversubscription
05.4Loading 10 GB container images on demand, block by block
05.5Deduplication without trust: convergent encryption
05.6A tiered cache erasure-coded for the tail
05.7Snapshot restore and the uniqueness problem
05.8What the design forces on users: concurrency, cold starts and retries
06.1External consistency: the contract, and why Bigtable and Megastore fell short
06.2Two-phase commit over Paxos groups
06.3TrueTime's engineering: GPS, atomic clocks and a bounded ε
06.4Commit wait and leader leases: proving external consistency
06.5Snapshot reads at safe time
06.6Interleaved tables, splits and hotspots: what the layout forces on schemas
06.7Becoming a SQL system: distributed union, range extraction and query restarts
06.8Availability and CAP: a CP system that is effectively CA
07.1Coordination only at commit: the disaggregated architecture
07.2Reads at a timestamp: precise clocks instead of coordination
07.3Adjudicators and optimistic concurrency: strong snapshot isolation
07.4The journal and the crossbar: durability and total order
07.5Multi-region commit in one round trip, with a witness region
07.6What OCC and disaggregation force on applications
08.1Shared cells: why mixing production and batch raises utilisation
08.2Scheduling by feasibility and scoring, and making it fast
08.3Limits versus reservations: reclaiming what tasks do not use
08.4From Borgmaster to Omega: shared state and optimistic schedulers
08.5The declarative API: desired state, observed state and optimistic concurrency
08.6Level-triggered reconciliation: acting on state, not on events
08.7Watches, informer caches and stale reads
08.8Deletion as a protocol: owner references, garbage collection and finalizers
08.9The scale envelope: what bounds a cluster's size
09.1The serving contract: global checks at millisecond latency, consistent with content
09.2Zookies: carrying a consistency token with the content
09.3Check evaluation, snapshot quantisation and a distributed cache
09.4Leopard: flattening nested groups into set intersections
09.5Hot spots, performance isolation and request hedging
10.1The log as the source of truth
10.2Where consensus sits, and where it is avoided
10.3How each system bounds blast radius
10.4How each contract shapes its users' data and code
Skipped topics
Moved past without finishing. A skipped topic still closes its module, and Continue goes on without it — open one to read it or mark it understood.
Glossary
Terms as the lessons define them, each linked to the lesson that defines it.
DynamoDB table
A DynamoDB table is a set of items, and each item is a set of attributes named by a primary key.
Go to From Dynamo to DynamoDB: why the service dropped leaderless replication →partition key
The key is either a partition key alone, or a partition key plus a sort key.
Go to From Dynamo to DynamoDB: why the service dropped leaderless replication →sort key
The key is either a partition key alone, or a partition key plus a sort key.
Go to From Dynamo to DynamoDB: why the service dropped leaderless replication →replication group
Each partition is stored as a replication group: three replicas in three different Availability Zones.
Go to From Dynamo to DynamoDB: why the service dropped leaderless replication →conditional write
A conditional write is a put, update or delete with a condition on the item's current attributes, such as seats_left > 0 or attribute_not_exists(pk).
Go to From Dynamo to DynamoDB: why the service dropped leaderless replication →strongly consistent read
A strongly consistent read sets ConsistentRead to true and is served by the leader, so it reflects every write that succeeded before it.
Go to From Dynamo to DynamoDB: why the service dropped leaderless replication →eventually consistent read
An eventually consistent read — the default — may be served by any replica, and "might not reflect the results of a recently completed write", in the developer guide's words.
Go to From Dynamo to DynamoDB: why the service dropped leaderless replication →log replica
A log replica stores only recent write-ahead-log entries — no B-tree, no items.
Go to Log replicas and leader failure: healing a replication group in seconds →gray failures
These are gray failures: the component is neither up nor down but up for some observers and down for others.
Go to Log replicas and leader failure: healing a replication group in seconds →constant work
That is constant work: the dependency's load no longer depends on the state of the cache.
Go to Metadata routing: why request routers do constant work →read capacity unit
A read capacity unit (RCU) is one strongly consistent read per second of an item up to 4 KB.
Go to Throughput dilution: why dividing a table's capacity among partitions failed →write capacity unit
A write capacity unit (WCU) is one write per second of an item up to 1 KB.
Go to Throughput dilution: why dividing a table's capacity among partitions failed →Burst capacity
Burst capacity lets a partition bank unused capacity and spend it later, best-effort, to absorb a short spike.
Go to Throughput dilution: why dividing a table's capacity among partitions failed →Adaptive capacity
Adaptive capacity handled the long-lived skew (§4.1.2).
Go to Throughput dilution: why dividing a table's capacity among partitions failed →Global admission control
Global admission control (GAC) replaced adaptive capacity (§4.2).
Go to Global admission control, split for consumption, and on-demand →weighted median
The natural point is the weighted median of the observed load: the key where the load on keys below it and the load on keys above it are each at most half of the total.
Go to Global admission control, split for consumption, and on-demand →On-demand
On-demand tables are sized from what they consume (§4.5).
Go to Global admission control, split for consumption, and on-demand →one-shot transaction
A one-shot transaction is submitted as a single request containing every operation it will perform, and it "either succeed[s] or fail[s] without blocking" (§1).
Go to One-shot transactions without locks or versions →transaction coordinators
Transactions reach a fleet of transaction coordinators, any of which can take any transaction (§3.1).
Go to One-shot transactions without locks or versions →global secondary index
A global secondary index (GSI) is organised by a key of the user's choosing — a partition key, and optionally a sort key — that "does not need to have any of the key attributes from the table", in the developer guide's words.
Go to Global secondary indexes as asynchronously replicated tables →projects
Each entry carries the table's primary key plus whatever other attributes the index projects.
Go to Global secondary indexes as asynchronously replicated tables →sparse index
A GSI is therefore a sparse index by default: it holds only items that carry its key attributes.
Go to Global secondary indexes as asynchronously replicated tables →local secondary index
A local secondary index (LSI) makes every choice the other way.
Go to Global secondary indexes as asynchronously replicated tables →item collection
An item collection is all the items sharing one partition-key value, together with their LSI entries.
Go to Global secondary indexes as asynchronously replicated tables →single-table design
Several entity types then share one table: single-table design.
Go to Access-pattern-first modelling and single-table design →overloaded
A pattern keyed on something else — orders by status, not by customer — gets a GSI, often with generic, overloaded key attributes that different item types fill with different meanings, and often sparse, so it holds only the items that pattern wants.
Go to Access-pattern-first modelling and single-table design →write sharding
The first is the one the developer guide describes as write sharding: spread one logical key over physical keys by adding a suffix, as for a vote counter here:
Go to The operating envelope: partition ceilings and hot keys →log applicator
In a conventional engine that job belongs to the log applicator: the code that applies a redo record to the before-image of a page to produce its after-image.
Go to The log is the database: shipping only redo to storage →page materialisation
That is page materialisation: producing a current page from an older version plus the chain of redo records that changed it, in the background or on demand when a read asks for the page.
Go to The log is the database: shipping only redo to storage →Availability Zone
In AWS, an Availability Zone (AZ) is a part of a Region with its own power, networking and facilities, connected to the Region's other zones by low-latency links and isolated from most of their faults — the 2017 paper lists power, networking, software deployments and flooding (§2.1).
Go to Six copies in three zones: sizing a quorum for correlated failure →AZ+1
The combination has a name: AZ+1, the loss of an entire Availability Zone plus one more, unrelated node.
Go to Six copies in three zones: sizing a quorum for correlated failure →Aurora segment
Each such piece is an Aurora segment: at most 10 GB of addressable data blocks in the papers' description (2017 paper, §2.2; 2018 paper, §2.1).
Go to Ten-gigabyte segments: repair time as the durability lever →protection group
Each segment is copied six ways, and the six copies form a protection group (PG): six copies of the same 10 GB range, two in each of three Availability Zones, written with the four-of-six and read with the three-of-six quorums of the previous topic.
Go to Ten-gigabyte segments: repair time as the durability lever →foreground path
The paper then makes the design's central claim: every step is asynchronous, and "only steps (1) and (2) are in the foreground path potentially impacting latency".
Go to The storage node: foreground acknowledgement, background everything →Segment Complete LSN
That point is the segment's Segment Complete LSN (SCL): in the 2018 paper's words, "the inclusive upper bound on log records continuously linked through the segment chain without gaps" (§2.3).
Go to Consistency points instead of consensus: VCL, VDL and asynchronous commit →Protection Group Complete LSN
So the instance advances a group's Protection Group Complete LSN (PGCL) once it sees SCL reach a point at four of the six members.
Go to Consistency points instead of consensus: VCL, VDL and asynchronous commit →Volume Complete LSN
The Volume Complete LSN (VCL) is the highest LSN such that every record at or below it, in every protection group, has met its write quorum.
Go to Consistency points instead of consensus: VCL, VDL and asynchronous commit →mini-transaction
The engine therefore groups records into mini-transactions (MTRs): short runs of contiguous log records that must be applied atomically, several of which make up one database transaction (2017 §4.1; 2018 §3.3).
Go to Consistency points instead of consensus: VCL, VDL and asynchronous commit →CPL
The last record of each MTR is marked as a consistency point LSN (CPL).
Go to Consistency points instead of consensus: VCL, VDL and asynchronous commit →Volume Durable LSN
The Volume Durable LSN (VDL) is the highest CPL at or below the VCL.
Go to Consistency points instead of consensus: VCL, VDL and asynchronous commit →LSN Allocation Limit
The 2017 paper gives the rule (§4.2.1): no LSN is allocated above the current VDL plus a constant, the LSN Allocation Limit (LAL), then set to 10 million.
Go to Consistency points instead of consensus: VCL, VDL and asynchronous commit →read point
When the instance issues a page read, it fixes a read point: the VDL at the moment the request is issued (2017 §4.2.3).
Go to Reading from one segment: why Aurora avoids quorum reads →Protection Group Min Read Point LSN
The result is the Protection Group Min Read Point LSN (PGMRPL), the "low water mark" below which the group's log records are no longer needed (2017 §4.2.3).
Go to Reading from one segment: why Aurora avoids quorum reads →Aurora Replica
An Aurora Replica is a read-only database instance that mounts the writer's storage volume and serves queries from it; one writer and up to 15 replicas can mount the same volume (2017 paper, §4.2.4; the current User Guide gives the same limit).
Go to Read replicas that share the volume →Structural consistency
Structural consistency is the property that a reader never observes part of an MTR — every physical structure it traverses, such as a B-tree, is as it was between two MTRs.
Go to Read replicas that share the volume →truncation range
Having recomputed the protection groups' PGCLs, VCL and VDL, the instance records a truncation range: a durable instruction to storage that every log record with an LSN above the new VDL, up to and including an end LSN, is annulled and must be ignored (2017 paper, §4.3; 2018 paper, §2.4).
Go to Recovery without redo replay →volume epoch
After recovery, once the volume is available for reads and writes, it increments the volume epoch — a counter kept in its storage metadata service — and records the new value in a write quorum of every protection group (2018 paper, §2.4).
Go to Recovery without redo replay →quorum set
A quorum set is a quorum rule written as a Boolean expression over groups of segments, rather than a single "any of ".
Go to Changing quorum membership without stalling: quorum sets and epochs →membership epoch
Each membership change has a membership epoch, a number for the group's configuration that increases by one with every change.
Go to Changing quorum membership without stalling: quorum sets and epochs →full segment
A full segment stores the group's redo log records and the data pages materialised from them.
Go to Changing quorum membership without stalling: quorum sets and epochs →tail segment
A tail segment stores redo log records only.
Go to Changing quorum membership without stalling: quorum sets and epochs →Aurora clone
An Aurora clone is a new cluster whose volume initially shares every data page with its source; a page is copied only when either side changes it.
Go to The operating envelope: one writer, fast clones, and where Aurora does not help →object version
An object version is one immutable value stored under a key, identified by a version ID that S3 generates.
Go to The object contract: immutable versions, no rename, no append →delete marker
A delete adds a delete marker: "Amazon S3 inserts a delete marker instead of removing the object permanently.
Go to The object contract: immutable versions, no rename, no append →multipart upload
A multipart upload separates sending the bytes from creating the object.
Go to The object contract: immutable versions, no rename, no append →Durability (annual)
Annual durability is the probability that a stored object is still intact, and readable in full, one year later.
Go to Durability as arithmetic: erasure coding, repair and eleven nines →durability review
Warfield calls the central mechanism a durability review: "a human mechanism that's not in the statistical 11 9s model, but it's every bit as important".
Go to Durability as arithmetic: erasure coding, repair and eleven nines →Heat (storage)
Warfield defines heat as "the number of requests that hit a given disk at any point in time", and describes what a hot drive does to the whole system.
Go to Heat management: why spreading data across millions of drives smooths load →workload decorrelation
This is workload decorrelation: when enough independent, bursty workloads share a pool of capacity, each one's burst is a small, uncorrelated addition to the total, and the aggregate's peak-to-mean ratio falls towards 1.
Go to Heat management: why spreading data across millions of drives smooths load →ShardStore
ShardStore is the key-value store that runs on each S3 storage node.
Go to ShardStore: an LSM-indexed, extent-based storage node with soft-updates crash consistency →Extent (ShardStore)
The chunks live in extents.
Go to ShardStore: an LSM-indexed, extent-based storage node with soft-updates crash consistency →Chunk reclamation
Chunk reclamation is the background task that recovers that space (§2.1).
Go to ShardStore: an LSM-indexed, extent-based storage node with soft-updates crash consistency →soft updates
Its answer is soft updates: controlling the order in which writes reach the disk so that every possible crash state is consistent, without writing anything twice.
Go to ShardStore: an LSM-indexed, extent-based storage node with soft-updates crash consistency →Consistency witness
So a witness is a component that is told about every change to an object and can answer one question: has this object changed since the version the cache holds?
Go to Strong read-after-write consistency at no added cost →read barrier
A read barrier is a check that a read must pass before it may return: a cached answer is served only if the barrier says it is current.
Go to Strong read-after-write consistency at no added cost →ETag
An object's ETag ("entity tag") is a string that S3 returns with every object and changes whenever the object's content changes.
Go to Conditional writes: building coordination on an object store →Prefix (S3)
A prefix is, in the user guide's words, "a string of characters at the beginning of the object key name". logs/2026/ is a prefix of logs/2026/09/24/a.gz, and so are l and logs/2026/09/2.
Go to Prefix scaling and 503 SlowDown: the index's partitioning, seen from outside →503 SlowDown
A 503 Slow Down is S3's throttling response: HTTP status 503 with the error code SlowDown, meaning "this part of the key space is receiving more requests than it currently serves".
Go to Prefix scaling and 503 SlowDown: the index's partitioning, seen from outside →Re-mirroring (EBS)
The summary calls this re-mirroring: the node searches its cluster for another node with enough free space, connects to it, and copies the volume's data across.
Go to The re-mirroring storm: when the configuration store is the availability →Control plane
So each promotion is a negotiation between the instance, the nodes holding the data and the EBS control plane — the set of services that accept user API calls (create, attach, detach, snapshot), send them to the clusters, and "act as the authority" when a cluster elects a volume's primary.
Go to The re-mirroring storm: when the configuration store is the availability →re-mirroring storm
A re-mirroring storm is the summary's name for the state the cluster entered: so many volumes re-mirroring at once that free space runs out, and every stuck node keeps searching for space that is not there.
Go to The re-mirroring storm: when the configuration store is the availability →Cell (Physalia)
A cell manages the data of a single partition key, and is a replicated state machine spread over seven nodes.
Go to Millions of tiny databases: partitioning consensus by key →colony
A colony is one Physalia installation: a mesh of nodes, the cells placed on them, and a control plane that creates, repairs and moves cells.
Go to Millions of tiny databases: partitioning consensus by key →distinguished proposer
A cell runs Paxos with one node acting as the distinguished proposer, which plays the role a leader plays in Raft: it puts client transactions into the log (§2.1–§2.2).
Go to Millions of tiny databases: partitioning consensus by key →discovery cache
Physalia uses a discovery cache: a distributed, eventually consistent cache that maps each partition key to the nodes currently holding its cell.
Go to Placing consensus next to its clients: availability where it matters →poison pill
A particularly nasty case is the poison pill: a transaction that passes validation and is accepted into the log, but cannot be applied without causing an error.
Go to Placing consensus next to its clients: availability where it matters →Colour (Physalia)
Every cell is given a colour (the paper's "color"), and a cell is built only from nodes of its colour.
Go to Placing consensus next to its clients: availability where it matters →covert channel
A covert channel is the same kind of effect used on purpose: two workloads that are not allowed to talk agree to signal each other, say by one of them alternately loading and idling a shared cache while the other times its own accesses.
Go to The isolation requirements that ruled out containers and QEMU →Soft allocation
Soft allocation means the platform hands out resources when they are used, not when a function starts.
Go to The isolation requirements that ruled out containers and QEMU →virtual machine monitor
A virtual machine monitor (VMM) is the user-space program that asks KVM to create a VM, loads the guest kernel, and emulates the devices the guest sees.
Go to The isolation requirements that ruled out containers and QEMU →microVM
A microVM is a virtual machine stripped to what a Linux function or container needs, so that it costs a few megabytes and boots in a fraction of a second.
Go to The isolation requirements that ruled out containers and QEMU →device model
The device model is the set of virtual devices a monitor presents to its guests, and so it is also the list of places a guest can attack.
Go to A minimal VMM: fewer devices, one process per VM, and a jailer →jailer
It asks what happens if a bug does let a guest run code inside the monitor, and answers with a second boundary around the process, the jailer: a wrapper that confines the Firecracker process before it runs any guest code (§3.4.1).
Go to A minimal VMM: fewer devices, one process per VM, and a jailer →one-time burst
Each bucket can also have a one-time burst: an extra allowance spent before the regular bucket and never refilled, which the paper says exists "to accelerate booting".
Go to A minimal VMM: fewer devices, one process per VM, and a jailer →Slot (Lambda)
A slot is one microVM on one Lambda server, loaded with one function's code, that serves that function only, one invocation at a time, and is reused for many invocations in a row (§4.1.1).
Go to Slots, placement and oversubscription →cold start
Users call that wait a cold start.
Go to Slots, placement and oversubscription →Worker Manager
The Worker Manager is a stateful router that knows, for every function, which slots exist and which are idle.
Go to Slots, placement and oversubscription →Placement service
The Placement service decides which worker gets a new slot.
Go to Slots, placement and oversubscription →MicroManager
The MicroManager is the one process per worker that manages all of these.
Go to Slots, placement and oversubscription →oversubscription ratio
Define the oversubscription ratio of a worker as the total resource configured for its slots divided by the resource the worker actually has.
Go to Slots, placement and oversubscription →lazy loading
The idea that follows from it is lazy loading: start the function without its data, and fetch each piece the first time something reads it.
Go to Loading 10 GB container images on demand, block by block →Chunk (Lambda image)
Cut the resulting file system into fixed-size chunks of 512 KiB each.
Go to Loading 10 GB container images on demand, block by block →deterministic flattening
The paper calls the first two steps a deterministic flattening process.
Go to Loading 10 GB container images on demand, block by block →local agent
The second device is served by a new local agent process that the MicroManager starts beside the microVM.
Go to Loading 10 GB container images on demand, block by block →FUSE
The agent presents the image to Firecracker through FUSE (Filesystem in Userspace), a Linux kernel interface that lets an ordinary user-space program implement a file system: the kernel forwards every operation on files under the mount point to that program.
Go to Loading 10 GB container images on demand, block by block →userfaultfd
Lambda is moving the agent to userfaultfd and mmap.
Go to Loading 10 GB container images on demand, block by block →convergent encryption
In convergent encryption, each block's key is derived from a hash of the block's own content, so identical plaintexts produce identical keys and therefore identical ciphertexts, while nobody who lacks the plaintext can compute the key.
Go to Deduplication without trust: convergent encryption →Manifest (Lambda image)
Each image then gets a manifest: the list of its chunks with each one's offset in the image, its key and its SHA-256 hash.
Go to Deduplication without trust: convergent encryption →Root (Lambda chunk store)
The design instead uses roots.
Go to Deduplication without trust: convergent encryption →Metastable failure
The paper avoids that on purpose, because retries are "known to lead to metastable failure modes in large systems".
Go to A tiered cache erasure-coded for the tail →LRU-k
The L2 cache uses LRU-k instead, an algorithm from database buffer management that tracks the last times each item was used rather than only the most recent one.
Go to A tiered cache erasure-coded for the tail →Post-initialisation snapshot
A post-initialisation snapshot is one taken after the function's initialisation has finished and before it has served a request.
Go to Snapshot restore and the uniqueness problem →Clone (microVM)
Each environment resumed from the same snapshot is a clone: a separate microVM that starts life with a byte-for-byte copy of the same memory.
Go to Snapshot restore and the uniqueness problem →UUID (version 4)
A version 4 UUID is a 128-bit identifier of which 122 bits are random (RFC 4122).
Go to Snapshot restore and the uniqueness problem →CSPRNG
A cryptographically secure PRNG (CSPRNG) is one whose outputs cannot be predicted by anyone who does not know its state; NIST calls such generators DRBGs, deterministic random bit generators.
Go to Snapshot restore and the uniqueness problem →Concurrency (Lambda)
So a function's concurrency, the number of requests it is handling at the same moment, is also the number of busy environments it has.
Go to What the design forces on users: concurrency, cold starts and retries →provisioned concurrency
To pay for initialisation in advance instead, a function can set provisioned concurrency: a number of environments Lambda keeps initialised at all times, at an extra charge.
Go to What the design forces on users: concurrency, cold starts and retries →concurrency scaling rate
The documentation retrieved in September 2026 gives the concurrency scaling rate as "1,000 execution environment instances every 10 seconds" per function, in each Region.
Go to What the design forces on users: concurrency, cold starts and retries →Reserved concurrency
Reserved concurrency sets aside part of the account's concurrency for one function and also limits the function to that amount.
Go to What the design forces on users: concurrency, cold starts and retries →external consistency
Its guarantee is called external consistency: if one transaction commits before another starts, in real time as an outside observer would measure it, the first transaction's commit timestamp is smaller.
Go to External consistency: the contract, and why Bigtable and Megastore fell short →Strict serializability
The database literature calls serializability plus the real-time rule strict serializability.
Go to External consistency: the contract, and why Bigtable and Megastore fell short →spanserver
Each server, a spanserver, holds 100 to 1000 tablets.
Go to Two-phase commit over Paxos groups →Paxos group
The set of replicas that together hold one tablet is a Paxos group.
Go to Two-phase commit over Paxos groups →Directory (Spanner)
Spanner buckets keys into a directory: a set of contiguous keys that share a prefix, such as one user's rows (§2.2).
Go to Two-phase commit over Paxos groups →Split (Spanner)
It speaks of tables divided into contiguous key ranges called splits, each replicated by Paxos across failure domains (Life of Spanner reads and writes).
Go to Two-phase commit over Paxos groups →coordinator leader
The leader of that group is the coordinator leader, and the leaders of the others are participant leaders.
Go to Two-phase commit over Paxos groups →Participant leader
The leader of that group is the coordinator leader, and the leaders of the others are participant leaders.
Go to Two-phase commit over Paxos groups →TrueTime
TrueTime is the clock API that every Spanner server calls.
Go to TrueTime's engineering: GPS, atomic clocks and a bounded ε →Error bound (TrueTime)
The paper defines the instantaneous error bound as half the interval's width, and as its average over time.
Go to TrueTime's engineering: GPS, atomic clocks and a bounded ε →Time master
TrueTime runs a set of time masters in every datacentre.
Go to TrueTime's engineering: GPS, atomic clocks and a bounded ε →Armageddon master
The rest are Armageddon masters, with atomic clocks.
Go to TrueTime's engineering: GPS, atomic clocks and a bounded ε →Timeslave daemon
Every machine runs a timeslave daemon, and the daemon is what answers TT.now().
Go to TrueTime's engineering: GPS, atomic clocks and a bounded ε →Marzullo's algorithm
The daemon applies "a variant of Marzullo's algorithm" to detect and reject liars (§3).
Go to TrueTime's engineering: GPS, atomic clocks and a bounded ε →Applied drift rate
The paper calls the applied drift rate and sets it to 200 microseconds per second.
Go to TrueTime's engineering: GPS, atomic clocks and a bounded ε →Start rule (Spanner)
The start rule: the coordinator assigns no less than TT.now().latest, read after .
Go to Commit wait and leader leases: proving external consistency →commit wait
The commit wait rule: the coordinator makes sure no client can see data committed by until TT.after() is true.
Go to Commit wait and leader leases: proving external consistency →Monotonicity invariant (Spanner)
Spanner's timestamps also serve as version numbers for multiversion reads, and that use needs a second invariant, the monotonicity invariant: within each Paxos group, timestamps increase in the order the group's writes enter its log, "even across leaders" (§4.1.2).
Go to Commit wait and leader leases: proving external consistency →Leader lease (Spanner)
A leader lease is a timed grant of leadership from a quorum of the group's replicas (§4.1.1).
Go to Commit wait and leader leases: proving external consistency →Disjointness invariant (Spanner)
The disjointness invariant: in each Paxos group, each leader's lease interval is disjoint from every other leader's.
Go to Commit wait and leader leases: proving external consistency →Single-vote rule (Spanner)
The single-vote rule.
Go to Commit wait and leader leases: proving external consistency →Follower (Spanner)
Versions alone do not make a follower's answer correct.
Go to Snapshot reads at safe time →Safe time (Spanner)
Safe time, written , is "the maximum timestamp at which a replica is up-to-date".
Go to Snapshot reads at safe time →Prepare timestamp
Each participant leader, other than the coordinator, takes its write locks and picks a prepare timestamp for transaction in group .
Go to Snapshot reads at safe time →Prepared transaction
Between steps 1 and 3 the transaction is prepared: a participant knows it may commit but not whether it will, or at what timestamp.
Go to Snapshot reads at safe time →Read-only transaction (Spanner)
A read-only transaction also needs a timestamp to read at.
Go to Snapshot reads at safe time →Snapshot read (Spanner)
Spanner has two kinds of lock-free read (§4.1): a read-only transaction, which is declared in advance to have no writes and is given a timestamp by the system, and a snapshot read, whose timestamp the client supplies or bounds.
Go to Snapshot reads at safe time →Scope expression
To know which case applies, Spanner needs a scope expression for every read-only transaction: a summary of the keys the whole transaction will read.
Go to Snapshot reads at safe time →Strong read (Spanner)
Strong, the default: see every transaction that committed before the read started.
Go to Snapshot reads at safe time →Exact staleness
Exact staleness: read at a timestamp the client gives, either absolute or a fixed age such as "15 seconds ago".
Go to Snapshot reads at safe time →Bounded staleness
Bounded staleness: read at a timestamp no older than a bound.
Go to Snapshot reads at safe time →Hotspot (Spanner)
The load consequence has a name in Google's documentation: a hotspot, where "too many requests are sent to the same server which saturates the resources of the server" (Schema design best practices, retrieved September 2026).
Go to Interleaved tables, splits and hotspots: what the layout forces on schemas →Interleaved table
The child's primary key must begin with the parent's whole primary key, and the child is declared interleaved in the parent.
Go to Interleaved tables, splits and hotspots: what the layout forces on schemas →Load-based splitting
Load-based splitting is the second half of that sentence.
Go to Interleaved tables, splits and hotspots: what the layout forces on schemas →bit-reversed sequence
A bit-reversed sequence is a Spanner schema object that keeps a private counter and hands out the counter's values with their bits reversed, so the keys are unique but not in order.
Go to Interleaved tables, splits and hotspots: what the layout forces on schemas →Shard (Spanner)
The SQL paper (Bacon et al., SIGMOD 2017) calls each key range a shard; the layout topic called it a split, and the Cloud documentation still does.
Go to Becoming a SQL system: distributed union, range extraction and query restarts →coprocessor framework
Every read and write is addressed to a key or a key range, and a routing layer the paper calls the coprocessor framework finds the Paxos group that owns it and the nearest replica up to date enough to serve it.
Go to Becoming a SQL system: distributed union, range extraction and query restarts →Distributed Union
The compiler replaces every table scan with a Distributed Union: an operator that ships a subplan to each shard of the table, runs it there, and concatenates the results, in table-key order when the plan needs order (§3.1):
Go to Becoming a SQL system: distributed union, range extraction and query restarts →partitionability
The paper calls this partitionability:
Go to Becoming a SQL system: distributed union, range extraction and query restarts →sharding key filter
As Distributed Union moves up through filters, it collects every condition on the sharding key and merges them into one sharding key filter, here c.ckey IN UNNEST(@customer_key_arr).
Go to Becoming a SQL system: distributed union, range extraction and query restarts →Query range extraction
Query range extraction is the analysis that turns a query's predicates into intervals of primary-key values: the parts of the table the query can possibly touch (§4.1).
Go to Becoming a SQL system: distributed union, range extraction and query restarts →filter tree
At run time a filter tree computes the ranges bottom-up, one key column at a time (§4.3).
Go to Becoming a SQL system: distributed union, range extraction and query restarts →Apply (join)
The paper expresses such joins as apply operators: evaluates the subplan map once for every row of input and concatenates the results (§2).
Go to Becoming a SQL system: distributed union, range extraction and query restarts →Distributed Apply
Distributed Apply batches it.
Go to Becoming a SQL system: distributed union, range extraction and query restarts →restart token
Results are sent in batches, and each batch carries a restart token: an opaque blob that, passed back with the original request, "prevents the rows already returned to the client to be returned again" (§5.2).
Go to Becoming a SQL system: distributed union, range extraction and query restarts →Ressi
Ressi, the replacement, keeps the log-structured merge tree and changes what is inside each file:
Go to Becoming a SQL system: distributed union, range extraction and query restarts →differential availability
What matters is differential availability: how often the user is up and making a request while Spanner is down.
Go to Availability and CAP: a CP system that is effectively CA →active-active
What the second group wanted is called active-active: every region serves reads and writes at the same time, as opposed to active-standby, where one region takes the writes and the others wait to take over.
Go to Coordination only at commit: the disaggregated architecture →Coordination (DSQL)
In this module, coordination means one component waiting for a message from another before it can proceed — a lock request and its grant, a vote, a replication acknowledgement.
Go to Coordination only at commit: the disaggregated architecture →Disaggregated architecture
DSQL is disaggregated: instead of one database process that parses SQL, stores pages, manages locks and writes a log, each of those jobs is a separate, horizontally scalable service (§2).
Go to Coordination only at commit: the disaggregated architecture →Query processor (DSQL)
ServiceIts jobWhat it holdsHow it scales Query processor (QP)Runs PostgreSQL's parser, planner, executor and wire protocol for one transaction at a time; reads from storage; buffers the transaction's writes; drives the commitThe open transaction's buffered writes and a cached catalog; nothing durableMore microVMs, added in the AZs and regions where connections arrive StorageKeeps rows and index entries for a key r…
Go to Coordination only at commit: the disaggregated architecture →Adjudicator (DSQL)
ServiceIts jobWhat it holdsHow it scales Query processor (QP)Runs PostgreSQL's parser, planner, executor and wire protocol for one transaction at a time; reads from storage; buffers the transaction's writes; drives the commitThe open transaction's buffered writes and a cached catalog; nothing durableMore microVMs, added in the AZs and regions where connections arrive StorageKeeps rows and index entries for a key r…
Go to Coordination only at commit: the disaggregated architecture →Journal (DSQL)
ServiceIts jobWhat it holdsHow it scales Query processor (QP)Runs PostgreSQL's parser, planner, executor and wire protocol for one transaction at a time; reads from storage; buffers the transaction's writes; drives the commitThe open transaction's buffered writes and a cached catalog; nothing durableMore microVMs, added in the AZs and regions where connections arrive StorageKeeps rows and index entries for a key r…
Go to Coordination only at commit: the disaggregated architecture →Crossbar (DSQL)
ServiceIts jobWhat it holdsHow it scales Query processor (QP)Runs PostgreSQL's parser, planner, executor and wire protocol for one transaction at a time; reads from storage; buffers the transaction's writes; drives the commitThe open transaction's buffered writes and a cached catalog; nothing durableMore microVMs, added in the AZs and regions where connections arrive StorageKeeps rows and index entries for a key r…
Go to Coordination only at commit: the disaggregated architecture →Write set
At COMMIT, the QP sends the transaction's write set — the keys it changed, with their new values — to the adjudicator that owns key 5.
Go to Coordination only at commit: the disaggregated architecture →Heartbeat (DSQL)
DSQL closes it with heartbeats: adjudicators "move their commit points forward in lockstep with the physical clock" and those commit points reach storage through the journals, so every stream keeps advancing with time whether or not anything is written (§5).
Go to Reads at a timestamp: precise clocks instead of coordination →write skew
The one that matters is write skew, which isolation anomalies derives with the on-call doctors.
Go to Adjudicators and optimistic concurrency: strong snapshot isolation →strong snapshot isolation
DSQL promises strong snapshot isolation: snapshot isolation plus linearizability, so a transaction that starts after another has committed always sees it (§2.4).
Go to Adjudicators and optimistic concurrency: strong snapshot isolation →post-image
What the adjudicator writes is a post-image: the new value of every row the transaction changed, stamped with (§5).
Go to The journal and the crossbar: durability and total order →Witness region
The third region is a witness region: it holds a copy of the journal and nothing else.
Go to Multi-region commit in one round trip, with a witness region →Conflict window (DSQL)
Call a transaction's conflict window : the stretch of commit time during which anyone else's commit to one of its keys makes it abort.
Go to What OCC and disaggregation force on applications →Borg
Google had exactly this split before Borg.
Go to Shared cells: why mixing production and batch raises utilisation →Cell (Borg)
A cell is a set of machines managed as one unit by one Borg controller.
Go to Shared cells: why mixing production and batch raises utilisation →Job (Borg)
Users submit jobs.
Go to Shared cells: why mixing production and batch raises utilisation →Task (Borg)
A job runs in one cell and consists of one or more tasks that all run the same binary.
Go to Shared cells: why mixing production and batch raises utilisation →Prod (Borg)
The paper calls higher-priority jobs prod and the rest non-prod.
Go to Shared cells: why mixing production and batch raises utilisation →Priority (Borg)
Every Borg job has a priority, a small positive integer.
Go to Shared cells: why mixing production and batch raises utilisation →Preemption (Borg)
That act is preemption.
Go to Shared cells: why mixing production and batch raises utilisation →Priority band
Priorities are grouped into non-overlapping priority bands.
Go to Shared cells: why mixing production and batch raises utilisation →preemption cascade
That chain is a preemption cascade.
Go to Shared cells: why mixing production and batch raises utilisation →Quota (Borg)
Quota decides what may enter at all.
Go to Shared cells: why mixing production and batch raises utilisation →Admission control (Borg)
Checking it is admission control, and it happens when a job is submitted, before any scheduling: a job whose requests exceed its owner's quota at that priority is rejected immediately.
Go to Shared cells: why mixing production and batch raises utilisation →cell compaction
The paper's authors chose a different metric: cell compaction (§5.1).
Go to Shared cells: why mixing production and batch raises utilisation →Pending queue (Borg)
When a job is submitted and admitted, the Borg controller records it durably and adds its tasks to a pending queue (Borg paper, §3.2).
Go to Scheduling by feasibility and scoring, and making it fast →Feasibility checking
Feasibility checking: find the machines on which the task could run.
Go to Scheduling by feasibility and scoring, and making it fast →Scoring (scheduling)
Scoring: pick one of those machines as the best.
Go to Scheduling by feasibility and scoring, and making it fast →Stranded resource
Borg now scores to reduce stranded resources: "ones that cannot be used because another resource on the machine is fully allocated".
Go to Scheduling by feasibility and scoring, and making it fast →Equivalence class (Borg)
Borg computes feasibility and scores for one task per equivalence class, a group of tasks with identical requirements, instead of for every pending task.
Go to Scheduling by feasibility and scoring, and making it fast →relaxed randomization
With relaxed randomization, the scheduler examines machines in a random order until it has found "enough" feasible ones, then scores only those and picks the best of that set (§3.4).
Go to Scheduling by feasibility and scoring, and making it fast →Limit (Borg)
Every Borg task states a limit for each resource: "an upper bound on the resources that each task should be granted" (Borg paper, §5.5).
Go to Limits versus reservations: reclaiming what tasks do not use →resource reclamation
The paper calls the whole process resource reclamation, and the estimate the task's reservation.
Go to Limits versus reservations: reclaiming what tasks do not use →Reservation (Borg)
The paper calls the whole process resource reclamation, and the estimate the task's reservation.
Go to Limits versus reservations: reclaiming what tasks do not use →Compressible resource
A compressible resource is rate-based, such as CPU cycles or disk I/O bandwidth: it "can be reclaimed from a task by decreasing its quality of service without killing it".
Go to Limits versus reservations: reclaiming what tasks do not use →Non-compressible resource
A non-compressible resource, such as memory or disk space, is held rather than consumed over time, and "generally cannot be reclaimed without killing the task".
Go to Limits versus reservations: reclaiming what tasks do not use →head-of-line blocking
That is head-of-line blocking, and the only way round it is to schedule more than one job at a time.
Go to From Borgmaster to Omega: shared state and optimistic schedulers →Borgmaster
The Borgmaster, a cell's central controller, is "logically a single process but is actually replicated five times" (Borg paper, §3.1).
Go to From Borgmaster to Omega: shared state and optimistic schedulers →monolithic scheduler
A monolithic scheduler has one instance and one code base that implements every policy.
Go to From Borgmaster to Omega: shared state and optimistic schedulers →Two-level scheduling
Two-level scheduling, as in Mesos, puts a central resource manager in front of independent scheduler "frameworks".
Go to From Borgmaster to Omega: shared state and optimistic schedulers →Resource offer
The manager sends each framework a resource offer: a set of currently unused resources that it offers to that framework only, until the framework accepts or returns it.
Go to From Borgmaster to Omega: shared state and optimistic schedulers →Shared-state scheduling
Shared-state scheduling, Omega's design, gives every scheduler the whole cell and lets them all claim resources freely.
Go to From Borgmaster to Omega: shared state and optimistic schedulers →Cell state (Omega)
Omega keeps one resilient master copy of the cell's allocations, called cell state.
Go to From Borgmaster to Omega: shared state and optimistic schedulers →Precedence (Omega)
They must agree on what allocations are allowed, such as when a machine counts as full, and on a common scale of job importance the paper calls precedence.
Go to From Borgmaster to Omega: shared state and optimistic schedulers →Fine-grained conflict detection
Fine-grained conflict detection rejects a placement only if it would overcommit the machine as it is now.
Go to From Borgmaster to Omega: shared state and optimistic schedulers →Coarse-grained conflict detection
Coarse-grained conflict detection rejects a placement if anything changed on the target machine since the scheduler synced, which needs only "a simple sequence number in the machine's state object".
Go to From Borgmaster to Omega: shared state and optimistic schedulers →Incremental transaction
An incremental transaction accepts "all but the conflicting changes".
Go to From Borgmaster to Omega: shared state and optimistic schedulers →All-or-nothing transaction
An all-or-nothing transaction is rejected entirely if any part conflicts; it gives gang scheduling, where all of a job's tasks start together or none do.
Go to From Borgmaster to Omega: shared state and optimistic schedulers →conflict fraction
The paper measures the conflict fraction: the average number of conflicts per successful transaction.
Go to From Borgmaster to Omega: shared state and optimistic schedulers →declarative API
A declarative API stores the end state the user wants as data, not as an action to perform, and leaves it to the system to make the world match. "There should be three copies of image 1.4" stays true as a statement after the machine dies, after the program acting on it restarts, and after a second copy of that program is started beside the first.
Go to The declarative API: desired state, observed state and optimistic concurrency →Deployment
Here is a real object, a Deployment, which asks for a number of identical copies of a program to be kept running and updated in a controlled way.
Go to The declarative API: desired state, observed state and optimistic concurrency →Spec (Kubernetes)
spec is the spec, the desired state, written by users and their tools.
Go to The declarative API: desired state, observed state and optimistic concurrency →Status (Kubernetes)
status is the status, the most recently observed state, written by the system.
Go to The declarative API: desired state, observed state and optimistic concurrency →pod
The template inside the spec describes a pod: the unit Kubernetes schedules onto a machine, one or more containers that are always placed together and share resources, much like the outer container Borg calls an alloc.
Go to The declarative API: desired state, observed state and optimistic concurrency →ReplicaSet
It creates a ReplicaSet, whose only job is to keep a given number of pods matching a template alive.
Go to The declarative API: desired state, observed state and optimistic concurrency →Controller (Kubernetes)
A controller is a process that reads objects of one kind and acts to bring the world in line with their specs.
Go to The declarative API: desired state, observed state and optimistic concurrency →Condition (Kubernetes)
Status is reported as a list of conditions, each a named observation with a value of True, False or Unknown and a one-word reason: Available above says the Deployment has at least its minimum number of pods available.
Go to The declarative API: desired state, observed state and optimistic concurrency →API server (Kubernetes)
The API server (kube-apiserver) is that server: an HTTP server that validates, defaults and versions every object, and keeps no durable state of its own.
Go to The declarative API: desired state, observed state and optimistic concurrency →etcd
Behind it is etcd, a replicated key-value store kept consistent by the Raft consensus protocol, which the Kubernetes documentation describes as the store "for all API server data".
Go to The declarative API: desired state, observed state and optimistic concurrency →resourceVersion
Every object carries a resourceVersion in its metadata: a string the server changes on every successful write to that object, whether to spec, status or metadata.
Go to The declarative API: desired state, observed state and optimistic concurrency →Generation (Kubernetes)
The generation says which version of the desired state is current.
Go to The declarative API: desired state, observed state and optimistic concurrency →observedGeneration
The observedGeneration says which version the status describes.
Go to The declarative API: desired state, observed state and optimistic concurrency →Label (Kubernetes)
Kubernetes groups objects with labels instead.
Go to The declarative API: desired state, observed state and optimistic concurrency →label selector
A label selector is a query over labels, such as app == checkout && track == stable, and the group is simply whatever currently matches.
Go to The declarative API: desired state, observed state and optimistic concurrency →Edge-triggered
An edge-triggered circuit acts when the signal changes, at the moment of the transition.
Go to Level-triggered reconciliation: acting on state, not on events →Level-triggered
A level-triggered circuit acts on the signal's current value, for as long as it holds.
Go to Level-triggered reconciliation: acting on state, not on events →Reconciliation (Kubernetes)
This is reconciliation, and one run of it for one object is called a reconcile.
Go to Level-triggered reconciliation: acting on state, not on events →Work queue (controller)
The queue that holds those keys is the work queue from client-go, the Go client library that Kubernetes' own controllers use.
Go to Level-triggered reconciliation: acting on state, not on events →Resync (informer)
The first is resync.
Go to Level-triggered reconciliation: acting on state, not on events →Convergence distance
Give each object a distance : a whole number that measures how far the observed state is from the desired state, and is 0 exactly when they match.
Go to Level-triggered reconciliation: acting on state, not on events →Watch (Kubernetes)
A watch is a long-lived request that returns a stream of change notifications for a resource type, each one naming the change (added, modified or deleted) and carrying the object as it now is.
Go to Watches, informer caches and stale reads →Relist (Kubernetes)
Kubernetes has every one of those parts: CDCKubernetes The source of truth, with a log of changesetcd, whose revision counter orders every write Initial snapshotLIST The snapshot's log positionThe list's metadata.resourceVersion Following the logWATCH from that resourceVersion Log retentionThe history etcd and the API server keep before compacting it away A consumer that has lost its placeA watch refused with 410 …
Go to Watches, informer caches and stale reads →Reflector (client-go)
A reflector runs list-then-watch against the API server (step 1 in that diagram) and pushes each change into a queue (step 2).
Go to Watches, informer caches and stale reads →Informer (Kubernetes)
An informer pops the changes (step 3) and applies them to an in-memory, indexed store of the objects (steps 4 and 5).
Go to Watches, informer caches and stale reads →watch cache
The API server keeps a watch cache: for each resource type it runs one watch against etcd and holds an in-memory mirror of the current objects plus a sliding window of recent change events.
Go to Watches, informer caches and stale reads →Watch bookmark
A bookmark fixes this.
Go to Watches, informer caches and stale reads →Expectations (controller)
The ReplicaSet controller guards against this with expectations, described in the source as "a cache mapping controllers to what they expect to see before being woken up for a sync".
Go to Watches, informer caches and stale reads →Owner reference
An owner reference says "this object exists on behalf of that one".
Go to Deletion as a protocol: owner references, garbage collection and finalizers →Dependent (Kubernetes)
The object carrying it is a dependent of its owner.
Go to Deletion as a protocol: owner references, garbage collection and finalizers →Garbage collector (Kubernetes)
The garbage collector is a controller in the controller manager that watches every resource type it can list and keeps an in-memory graph of owners and dependents.
Go to Deletion as a protocol: owner references, garbage collection and finalizers →finalizer
A finalizer is a key in an object's metadata.finalizers list that tells the API server not to remove the object until the key is gone.
Go to Deletion as a protocol: owner references, garbage collection and finalizers →deletionTimestamp
It sets metadata.deletionTimestamp to the time of the request and answers 202 Accepted.
Go to Deletion as a protocol: owner references, garbage collection and finalizers →Cluster (Kubernetes)
A Kubernetes cluster is a set of machines, called nodes, managed by one control plane: the API server tier, etcd behind it, and the scheduler and controllers.
Go to The scale envelope: what bounds a cluster's size →Node (Kubernetes)
A Kubernetes cluster is a set of machines, called nodes, managed by one control plane: the API server tier, etcd behind it, and the scheduler and controllers.
Go to The scale envelope: what bounds a cluster's size →Scalability envelope (Kubernetes)
SIG Scalability, the Kubernetes group that runs the tests behind these numbers, calls the set of supported configurations the scalability envelope.
Go to The scale envelope: what bounds a cluster's size →Compaction (etcd)
etcd keeps history. etcd is a multi-version store: an update does not overwrite a key but adds a new revision holding the whole new value, and "all data held by previous revisions remains unchanged" until the history is compacted away.
Go to The scale envelope: what bounds a cluster's size →Space quota (etcd)
Its documentation (v3.5, System limits) gives a default storage size limit of 2 GiB, configurable, and says "8 GiB is a suggested maximum size for normal environments".
Go to The scale envelope: what bounds a cluster's size →Node Lease
A node Lease is a tiny object, one per node in the kube-node-lease namespace; "every kubelet heartbeat is an update request to this Lease object, updating the spec.renewTime field".
Go to The scale envelope: what bounds a cluster's size →Watch fan-out
A watch fan-out is the number of copies of one change the control plane must send: one to every client whose watch matches the changed object.
Go to The scale envelope: what bounds a cluster's size →Fleet management
That layer is called fleet management.
Go to The scale envelope: what bounds a cluster's size →Authorisation check
Authorisation is the question "may this user do this to this object?", asked after authentication has settled who the user is.
Go to The serving contract: global checks at millisecond latency, consistent with content →relation tuple
A permission is a relation tuple, written object#relation@user, where an object is namespace:id (§2.1, Table 1):
Go to The serving contract: global checks at millisecond latency, consistent with content →userset
The part after @ is a userset, an object#relation pair standing for a set of users, which is how groups nest.
Go to The serving contract: global checks at millisecond latency, consistent with content →userset rewrite
A userset rewrite is a rule in a namespace's configuration that derives one relation from others for every object at once (§2.3.1).
Go to The serving contract: global checks at millisecond latency, consistent with content →New-enemy problem
The new-enemy problem is the failure in which a user who has just lost access sees content added after the removal, because the check either ignored the order of two permission changes or applied an old ACL to new content (§2.2).
Go to The serving contract: global checks at millisecond latency, consistent with content →Evaluation timestamp (Zanzibar)
A check is evaluated at an evaluation timestamp : every tuple it reads is read as of , so it sees exactly the ACL writes with .
Go to The serving contract: global checks at millisecond latency, consistent with content →zookie
A zookie is an opaque byte string that encodes a timestamp on Zanzibar's timeline (§2.4).
Go to Zookies: carrying a consistency token with the content →content-change check
When a user is about to save a content modification, the client sends a content-change check: an ordinary check ("may Charlie edit doc:plan?") marked as authorising a content change.
Go to Zookies: carrying a consistency token with the content →Default staleness (Zanzibar)
For requests without a zookie it uses a default staleness, "chosen to ensure that all transactions are evaluated at a timestamp that is as recent as possible without impacting latency" (§3.2.1).
Go to Zookies: carrying a consistency token with the content →Safe request (Zanzibar)
Its storage sends replication heartbeats every 8 seconds, so it calls a request Safe when its zookie is more than 10 seconds old, and usually servable in-region, and Recent otherwise (§4.1).
Go to Zookies: carrying a consistency token with the content →Recent request (Zanzibar)
Its storage sends replication heartbeats every 8 seconds, so it calls a request Safe when its zookie is more than 10 seconds old, and usually servable in-region, and Recent otherwise (§4.1).
Go to Zookies: carrying a consistency token with the content →Forwarding key (Zanzibar)
For most namespaces, the forwarding key is the object ID.
Go to Check evaluation, snapshot quantisation and a distributed cache →timestamp quantisation
Zanzibar's answer is timestamp quantisation: evaluation timestamps are "rounded up to a coarse granularity, such as one or ten seconds, while respecting staleness constraints from request zookies" (§3.2.5).
Go to Check evaluation, snapshot quantisation and a distributed cache →Lock table (Zanzibar)
Zanzibar's lock table is that fix, on every server, keyed by the same (question, snapshot) key as the cache (§3.2.5).
Go to Check evaluation, snapshot quantisation and a distributed cache →Leopard
Leopard is the specialised index Zanzibar uses for this, for selected namespaces whose groups are deep or wide (§3.2.4).
Go to Leopard: flattening nested groups into set intersections →blast radius
The blast radius of a failure is the set of clients it affects: the tenants, keys or requests that see errors or delays because of it.
Go to How each system bounds blast radius →Unit of isolation
It chooses a unit of isolation: a piece of the system that can fail on its own, whose failure reaches only the clients placed inside it.
Go to How each system bounds blast radius →modelling rule
A modelling rule is what the user must do, in keys, transactions or code, to stay on the cheap path of a contract, and each rule exists because the system leaves that piece of coordination to the user.
Go to How each contract shapes its users' data and code →