Ordering, IDs and Clocks - Systems - Jordi Villar
Interactive explainer

How distributed systems decide what came first

Clocks, logical timestamps, ID generators and sequencers, and how ClickHouse orders its own data with Keeper. Every diagram on this page runs: step through it, add events, drag the sliders, break the clock.

0 · Start here

There is no global clock

Every machine has its own quartz oscillator and its own idea of "now", and messages take a variable, unbounded time to arrive. No shared clock can settle which of two events on different machines came first, so every system picks a weaker question it can answer.

Physical vs logical time

Physical time is a wall-clock reading, synchronized only approximately. It means something to people and supports real-time bounds, but readings from two machines aren't directly comparable. Logical time is a counter that tracks only causality: exact about what could have influenced what, blind to real time.

Happens-before

a → b if a precedes b on one process, or a sends a message that b receives, or a chain of these links them. If neither a → b nor b → a, the events are concurrent: a ∥ b.

Causal vs total order

Causal order is happens-before itself, a partial order. A total order ranks every pair; a useful one never contradicts causality. A linearizable order also respects real time between clients.

Three ways to get an order
Diagram

How to read it. Each band is one strategy. Each box is a mechanism with the systems that use it underneath. Click a box to jump to its section. The further down you go, the stronger the order and the more coordination it costs.

Read a clock Comparable to real time, but only within the clock error Wall clock + NTPCassandra LWW TrueTime intervalSpanner Hybrid logical clockCockroachDB, MongoDB Count causality Exact about what influenced what, no coordination, blind to real time Lamport clockballots, tie-breaking Vector clockDynamo, Riak siblings HLC = clock+ counter Ask a sequencer One place hands out the order: strong, but it's a bottleneck Snowflake, ID blocksper-worker order only Consensus log indexetcd, Kafka partition Keeper block numbersReplicatedMergeTree
MechanismGives youDoesn't give youSize
Wall clockRough real-time order, human-readableAny guarantee; it can jump backwards8 B
Lamport clockA total order consistent with →Detecting concurrency8 B
Vector clockExact → and ∥Compactness8·N B
HLCCausal order within ε of wall timeReal-time guarantees tighter than ε8–12 B
TrueTime + commit waitExternal consistency without a central sequencerFree writes: each waits about 2ε8 B + GPS, atomic clocks
Consensus logOne linearizable total orderWrite scaling beyond one leader8 B
In the interview

There's no global clock, so first I decide which order I actually need (per key, causal, or total), and then I pay only for that.

1 · Physical time

Physical clocks drift, skew and jump

A quartz crystal drifts by roughly 10–100 parts per million, and the rate changes with temperature. At 50 ppm a free-running clock gains or loses about 4.3 seconds a day. Synchronization bounds the error; it never removes it.

NTP uses four timestamps: client sends at t0, server receives at t1 and replies at t2, client receives at t3. Offset θ = ((t1−t0)+(t2−t3))/2, round trip δ = (t3−t0)−(t2−t1). The formula assumes both directions take equal time, so path asymmetry becomes error, up to δ/2. Expect well under a millisecond inside a datacenter, and milliseconds to tens of milliseconds over the internet. PTP with hardware timestamps gets to microseconds.

NTP offset estimate
Interactive

How to use it. The server's clock is exact and the x axis is true time. With a symmetric path the estimate is perfect whatever the client's error. Switch to Asymmetric path: the estimate is now wrong by half the difference between the two delays, and nothing in the four timestamps reveals it.

Corrections, and why clocks go backwards

Monotonic vs wall clock. CLOCK_REALTIME is for timestamps people read. CLOCK_MONOTONIC (Java System.nanoTime(), Python time.monotonic()) never goes backwards but means nothing across machines or reboots. Use monotonic for durations and timeouts, wall time for display, and neither alone for ordering events across nodes.

Timing a 120 ms request during an NTP step
Interactive

How to use it. Drag the step to a negative value: the wall-clock duration goes negative, so a timeout check never fires. Drag it positive: a request that met its 200 ms deadline looks like it missed it. The monotonic clock is unaffected either way.

Last-write-wins loses data under skew

Cassandra and many key-value stores resolve conflicting writes by timestamp: the highest one wins. If the clock that stamped the later write is behind, the later write looks older and is silently discarded. There is no error and no conflict to inspect.

LWW with two skewed replicas
Step-through

How to use it. Pick a scenario and press Next. Writes are stamped by the replica that receives them. In A runs fast, the second write is 40 ms later in real time but gets a smaller timestamp, and both replicas converge on the old value. Drag the sliders to find the boundary: data is lost whenever the skew exceeds the gap between writes.

In the interview

Wall clocks are fine for people and for reasoning with a bounded error. I don't let them decide which write wins unless I can bound the skew and accept losing writes inside that bound.

2 · Logical time

Lamport clocks

One integer per process, attached to every message. It ignores real time and captures causality cheaply.

Local event
C = C + 1
Send m
C = C + 1; m carries C
Receive m
C = max(C, m.C) + 1
Total order
sort by (C, process id)

Clock condition: if a → b then C(a) < C(b). The converse is false: C(a) < C(b) doesn't mean a happened before b. Sorting by (C, pid) gives a total order that never contradicts causality. That's enough for mutual exclusion, deterministic tie-breaking, or Paxos ballot numbers. It can't tell you that two events were concurrent.

Lamport clocks, three processes
Step-through

How to use it. Press Next to run one event at a time. The number above each event is its Lamport timestamp. Below the diagram, the total order grows as events run. Watch the callout: it counts how many of the ranked pairs were actually concurrent. In Two concurrent writes, a and b both get C = 1 and are ordered only by process id.

Total order so far, by (C, pid)
3 · Logical time

Vector clocks

One counter per process, carried on every message. A vector timestamp records exactly which events of each process are in an event's causal past, so it can tell "before" from "concurrent".

Local or send at Pi
V[i] += 1 (a send carries V)
Receive m at Pi
V = max(V, m.V) per slot; V[i] += 1
a → b
V(a) ≤ V(b) in every slot, and V(a) ≠ V(b)
a ∥ b
neither vector ≤ the other

Dynamo-style stores (the original Dynamo, Riak) use the replica-keyed variant, version vectors, to detect conflicting writes and keep both as siblings instead of dropping one. Dotted version vectors fix the sibling explosion caused by keying on clients.

Event lab: build your own history
Interactive

How to use it. Add events with the buttons: a local event, or a send to another process. A send stays in flight (dashed) until you press its Deliver button, so you choose the delivery order. Then click any two events in the diagram to compare them. Try two Local events on different processes before any message: Lamport ranks them, vectors prove they are concurrent. Back and Next replay your history; adding an event after Back discards what came after.

Lamport total order, by (C, pid)

The cost: size grows with participants

Every timestamp, and every message, carries N counters. Systems bound N by keying on replicas rather than clients, and prune old entries. Pruning can turn real orderings into false conflicts.

Timestamp overhead
Interactive

How to use it. Drag the number of participants. Bars use a log scale. At a thousand participants a vector costs 8 KB per message, a thousand times a Lamport clock.

In the interview

Lamport gives me an order; vectors tell me when there wasn't one. I need vectors when concurrent updates must be detected and merged, not just ranked.

4 · Hybrid time

Hybrid logical clocks

An HLC timestamp is a pair (l, c). l is the largest physical time this node has seen, from its own clock or from any message. c is a small counter that breaks ties when l doesn't move. The pair respects causality like a Lamport clock and stays within the clock skew ε of real time, so it fits in 64 bits and still reads as a date.

Local or send, physical pt
l' = max(l, pt); c = (l' == l) ? c + 1 : 0
Receive (lm, cm)
l' = max(l, lm, pt); c = 1 + max of the c's whose l equals l', else 0
Bound
0 ≤ l − pt ≤ ε
HLC across three skewed nodes
Step-through

How to use it. Set each node's clock skew, then press Next. Above each event is its HLC (l, c); below it, the node's physical clock pt. Red "pt < send" marks a receive whose physical clock reads earlier than the send: ordering by wall time would break causality there. The HLC never does. Make the skews larger and watch l − pt in the table stay within ε.

Where it's used

If one node's clock jumps far ahead, everyone's l follows it. HLC keeps causality but inherits the bad wall time, which is why systems enforce a maximum offset.

5 · Physical time with bounds

TrueTime and commit wait

Spanner's TT.now() returns an interval [earliest, latest] guaranteed to contain true time. GPS receivers and atomic clocks in every datacenter keep its half-width ε small: in the 2012 paper it sawtoothed between about 1 and 7 ms, 4 ms on average.

A read-write transaction takes commit timestamp s = TT.now().latest, then waits until TT.now().earliest > s before releasing locks and acknowledging. That wait is about 2ε. After it, true time has definitely passed s, so any transaction that starts later, anywhere, picks a larger timestamp. That's external consistency. The wait overlaps with Paxos replication, so it only adds latency when 2ε exceeds replication time.

Commit wait on a true-time axis
Step-through

How to use it. Drag ε and watch the amber wait bar and the added latency. Then pick Skip commit wait: T1 acknowledges while true time is still before s1, a later T2 on a server whose clock runs slow gets s2 < s1, and the order of the two commits contradicts real time. Slow Paxos shows the wait hidden behind replication.

Without special hardware, CockroachDB takes the other path: no commit wait on ordinary writes, uncertainty restarts on reads, and a weaker guarantee (serializable, but not linearizable across unrelated keys). AWS offers bounded clock error through Amazon Time Sync and the open-source ClockBound daemon.

In the interview

TrueTime turns clock uncertainty into latency: every write pays about 2ε. Shrinking ε is a hardware problem; hiding it means overlapping the wait with replication.

6 · Sequencers

Unique ID generation

Pin down the requirements first. Must IDs be strictly increasing, roughly time-sortable, gap-free, 64-bit, unguessable? How many per second, and must generation survive a coordinator outage?

Auto-increment

Simple, compact, ordered. Every ID is a round trip to one primary: a throughput ceiling and a single point of failure. Rollbacks leave gaps, and commit order can differ from ID order.

MySQL, Postgres sequences

UUIDv4

122 random bits, no coordination, collisions negligible (about 2.7·10¹⁸ IDs for a 50% chance). Random keys scatter inserts across an index.

128 bits, unordered

UUIDv7, ULID

48 bits of Unix milliseconds, then random bits, so IDs sort by creation time. Order across machines is only as good as their clocks.

RFC 9562 (2024) · 128 bits
Generate and decode
Interactive

How to use it. Press Generate. Rows are 3 ms apart. The bold prefix of v7 and ULID is the millisecond timestamp, which is why they sort by time and v4 doesn't.

Index locality: random vs time-ordered keys
Interactive

How to use it. Each box is a leaf page of a B-tree index holding up to 8 keys; its fill shows how full it is. Insert 40 UUIDv4 keys: the batch touches most pages and splits them, leaving them half full. Insert 40 UUIDv7 keys: only the rightmost pages change.

ClickHouse has no B-tree, but the same reasoning applies to its sorting key: a random UUID first in ORDER BY wrecks compression and makes the sparse primary index useless for range scans. Recent versions have generateUUIDv7() and generateSnowflakeID().

Snowflake: 64 bits, no coordination per ID

Twitter's layout: 1 unused sign bit, 41 bits of milliseconds since a custom epoch (about 69.7 years), 10 bits of machine id (1,024 workers), 12 bits of sequence (4,096 IDs per millisecond per worker, about 4 million per second). IDs from one worker strictly increase; across workers they are only roughly time-ordered. Coordination happens once, when a worker gets its machine id.

Two failure modes need code. If the clock goes backwards, the generator could reuse timestamps it has already issued, producing duplicates; the original refuses with "Clock moved backwards". If the 4,096 sequence numbers run out within one millisecond, it spins until the next millisecond.

Snowflake bit layout and generator
Interactive

How to use it. Move the bit sliders to trade lifespan, workers and throughput, and watch the metrics. Generate an ID to fill the bit grid. Burst 5,000 overflows the 12-bit sequence. Clock −5 ms and Clock −200 ms simulate NTP steps: generate again under each policy. Too few time bits shows a layout that has already run out of time.

Worker ids must be unique while a worker is alive. Lease them from Keeper or ZooKeeper (an ephemeral node, or a lease with a TTL), and never give an id to a new process while the old one might still be running. Persist the last timestamp now and then, so a restart after a clock step can't reissue old IDs.

Block allocation from a coordinator

A coordinator owns a counter and hands out ranges: "you get 41–50". Each app server issues IDs from its range in memory and asks for a new block when it runs out, so the coordinator sees one write per B IDs. The coordinator can be a database row (UPDATE seq SET v = v + 1000 RETURNING v), a Keeper counter updated with compare-and-set, or Keeper sequential nodes. A ZooKeeper sequential suffix is a signed 32-bit counter, so it overflows after 2,147,483,647 children: fine for blocks, not for individual IDs. Meituan's Leaf prefetches the next block when the current one is 10% used, so a coordinator blip doesn't stall callers.

Coordinator handing out blocks
Interactive

How to use it. Issue IDs: each request lands on a random server. Every ID is unique, but the stream clients see isn't sorted (red outlines). Crash S2 to see the rest of its block lost as a gap. Drag the block size and target rate to see how rarely the coordinator is touched.

IDs in the order clients received them (last 48)

Comparison

Filter by what you need
Table

How to use it. Tick the requirements you have. Schemes that can't meet them fade out. Ticking both "strictly increasing" and "no coordination per ID" leaves nothing, which is the core trade-off.

SchemeOrderingCoordinationThroughputFailure modesIndex locality
In the interview

Snowflake if I need 64-bit, time-sortable IDs at millions per second. UUIDv7 if 128 bits is fine and I want zero coordination. A single sequencer only if I truly need gap-free or strictly global order, and I accept its throughput limit.

7 · Sequencers

Global order vs per-partition order

The simplest total order is a single sequencer: one node hands out the next number. Make it fault tolerant with consensus and you get a replicated log (Raft, Multi-Paxos, ZAB). The log index is a global sequence number: every replica applies entries in index order and sees the same history. etcd's revision, ZooKeeper's zxid and a Kafka offset within one partition are all this idea. An index becomes a sequence number only once the entry is committed, meaning a majority has stored it.

A Raft log as a global sequence
Step-through

How to use it. Normal commit shows an entry getting its index from the leader and becoming permanent once 3 of 5 servers have it. Two clients shows that the leader's arrival order, not anyone's clock, decides the order. Leader crash shows an uncommitted index being reused for a different entry. Blue cells are term 1, amber term 2; filled cells are committed.

The cost of one global order

Commit latency and throughput
Interactive

How to use it. Five servers, so the leader needs acknowledgements from 2 of its 4 followers: only the second-fastest follower matters. Switch to 3 regions to see latency jump, then raise the batch size to win throughput back.

Model: commit latency ≈ second-fastest follower RTT + fsync; throughput assumes one batch in flight. Pipelining raises it further until the leader saturates.

Partitioning: order where it matters

To scale writes, you split into partitions, each with its own log and its own leader. Kafka partitions, multi-Raft ranges in CockroachDB, and ClickHouse shards all work this way. Each partition is totally ordered; nothing orders one partition against another. Choose the partition key so that everything that must be ordered relative to each other (one user, one account, one entity) lands in the same partition.

Eight events through partitions
Step-through

How to use it. Events e1…e8 come from users a, b and c, produced in that order. Press Next to let the consumer poll one partition at a time, two records per poll. With Keyed by user, each user's events stay in order even though the overall order is scrambled. Switch to No key and some events of user a arrive before earlier ones (red outlines).

Consumer sees

When you do need one order across partitions, there are three options. Use a single partition and accept the throughput cap. Put a sequencer in front, which is a single partition in disguise. Or merge at read time by (event_time, partition, offset) with watermarks: deterministic, but only as accurate as the event-time clocks.

In the interview

A consensus log gives me a real global sequence, but every ordered write goes through one leader and a majority round trip. To scale I partition, and from then on I only have order per partition, so the partition key has to match the ordering requirement.

8 · The ClickHouse angle

Block numbers, parts and Keeper

Each INSERT into a MergeTree table writes one immutable part per partition it touches. Background merges combine parts. To merge and replicate safely, every part needs a place in an order that all replicas agree on, and that order comes from block numbers.

Block numbers come from Keeper sequential znodes

For ReplicatedMergeTree, the inserting replica allocates a block number by creating an ephemeral-sequential znode under <table path>/block_numbers/<partition_id>/block-. The sequence suffix is the block number: increasing per partition, shared by every replica of the shard, and ordered by Keeper's Raft log. A plain MergeTree uses an in-memory counter instead. Mutations also take a block number, and apply to data with smaller numbers.

Part names: partition_min_max_level

A fresh insert is 202410_7_7_0. Merging 202410_1_3_1 with 202410_4_7_0 gives 202410_1_7_2: lowest min, highest max, level one above the highest. A mutated part gets a fifth field, the mutation's block number. Tables without PARTITION BY use all. system.parts has the same data in min_block_number, max_block_number and level.

Read a part name
Interactive

How to use it. Pick an example or type any part name from system.parts.


Insert deduplication by block hash

Each inserted block gets a block_id: the partition id plus a hash of the block's data, or of insert_deduplication_token if you set one. Allocating the block number is a Keeper multi-op that also checks /blocks/<block_id>. If that node exists, the insert is a duplicate: the data is dropped and the client still gets success. The commit multi-op creates /blocks/<block_id> together with the part's log entry, so when two copies race, the loser fails at commit and its block number is abandoned. Abandoned numbers leave harmless gaps.

Keeper keeps the last replicated_deduplication_window hashes (1000 by default in current releases, 100 in older ones) for up to replicated_deduplication_window_seconds (one week). A client can therefore retry a timed-out insert on any replica, provided it resends exactly the same block.

Why merges need contiguous block ranges

A part named 1_7 claims every block number from 1 to 7. Two parts can merge only if no other part lies between them and no insert still holds a block number between them. If an insert holding block 2 is in flight, merging parts 1 and 3 into 1_3 would leave the future part 2 inside an already-covered range, and parts would overlap. So the merge selector waits. Block order also carries meaning: ReplacingMergeTree without a version column keeps the row from the part inserted last.

ReplicatedMergeTree: one partition, two replicas
Step-through

How to use it. Scenarios replay a prepared history with Back and Next. The action buttons add a step after the current one, so you can write your own. The strip shows block numbers 1, 2, 3… with the parts that cover them above. Striped amber is a number held by an in-flight insert, dashed is abandoned. The Keeper panel shows the znodes; green is the newest log entry.

Block numbers of partition 202410. Teal = level 0, blue = level 1, purple = level 2+.
Keeper
Active parts, both replicas

Distributed tables have no global order

A Distributed table splits each insert by sharding key and forwards the pieces. By default it does this asynchronously: rows are queued on the initiator's disk and sent in the background (distributed_foreground_insert, formerly insert_distributed_sync, makes it synchronous). Each shard has its own Keeper path and its own block numbers, and shards flush independently.

Six events through a Distributed table
Step-through

How to use it. Press Next to follow two batches through the initiator's queue to two shards. Both shards number their parts from block 1. Tick synchronous mode to see that waiting for the shards changes durability, not ordering. The last step compares a query with and without ORDER BY.

Why ClickHouse avoids a global order

In the interview

ClickHouse totally orders parts per partition per shard, using Keeper sequential nodes. That's exactly what merges and deduplication need. Across shards there's no order, so I carry an event-time column plus a tiebreaker and order at query time.

9 · Recap and follow-ups

What to remember, and what they'll ask

TopicOne line
Physical clocksDrift of tens of ppm; NTP error up to δ/2; a step goes backwards; time durations with the monotonic clock.
Lamporta → b ⇒ C(a) < C(b). Total order by (C, pid). Can't detect concurrency.
VectorExact causality and conflict detection, for O(N) bytes per timestamp.
HLC(l, c): causal, within ε of wall time, 64 bits. CockroachDB, MongoDB.
TrueTimes = latest; wait until earliest > s. External consistency for about 2ε per write.
Snowflake41 / 10 / 12 bits: 69.7 years, 1,024 workers, 4,096 IDs per ms. Guard against clock steps and sequence overflow.
Global vs partitionA log index is a global sequence once committed; partitioning trades it for per-partition order.
ClickHouseBlock numbers per partition via Keeper; part = partition_min_max_level; dedup by block hash; no order across shards.

Numbers to have ready

Quartz drift10–100 ppm · 50 ppm ≈ 4.3 s/day
NTP accuracy< 1 ms in a DC · 1–50 ms over the internet
TrueTime ε (2012)1–7 ms, 4 ms average
UUIDv748-bit ms · 74 random bits · 128 bits
ZK sequential suffix10 digits · signed int32 · overflows at 2,147,483,647
Dedup window1000 blocks · 7 days (replicated)

Likely follow-up questions

Answer out loud first, then open the model answer.

Q1Design an ID service that sustains 1M IDs per second.
  • Ask first: 64-bit? time-sortable? gap-free? Gap-free at 1M/s isn't realistic, and I'd say so.
  • Snowflake as an in-process library avoids a network hop; one worker can do 4.096M/s in theory, so a handful covers it with headroom. Lease worker ids from Keeper with ephemeral nodes.
  • Handle clock regression and sequence overflow explicitly; alert on NTP offset.
  • Alternative: blocks of 100k from a DB row or Keeper counter is 10 coordinator writes per second at 1M/s. Prefetch the next block in the background.
Q2Your Snowflake generator sees the clock go backwards. What happens, and what do you do?
  • Unguarded, it reissues timestamps it already used, and with the sequence reset, duplicate IDs follow.
  • Small regression: wait it out. Large: refuse, alert, and take the node out of rotation. Or keep the last timestamp (logical mode) and borrow future milliseconds on overflow, accepting drift from real time.
  • Persist the last timestamp so a restart can't reissue; prefer slew-only NTP after boot.
Q3When do you need vector clocks rather than Lamport clocks?
  • When concurrent updates must be detected and merged or surfaced: multi-leader replication, Dynamo-style siblings, CRDT sync.
  • If any order consistent with causality is enough (tie-breaking, ballots), Lamport costs 8 bytes and does the job.
Q4Why HLC instead of plain wall clocks or plain Lamport clocks?
  • Wall clocks can contradict causality under skew. Lamport respects causality but drifts arbitrarily far from real time, so you can't do "read as of 10:00" or bound staleness.
  • HLC gives both: causal, and within ε of wall time, in 64 bits. The cost is trusting a max-offset bound.
Q5How does Spanner get external consistency, and what does CockroachDB do without TrueTime?
  • Spanner: interval clock, commit at s = latest, commit-wait until earliest > s (about 2ε, overlapped with Paxos).
  • CockroachDB: HLC plus max offset; reads restart when they see values in the uncertainty window; nodes with bad clocks shut down. Serializable, without Spanner's real-time guarantee across unrelated transactions.
Q6How do you order events coming from many Kafka partitions?
  • Kafka orders only within a partition. If the requirement is per entity, key by entity and you're done.
  • Truly global: a single partition, or a sequencer before produce, both throughput-capped.
  • Usually enough: event time plus a deterministic tiebreak (event_time, partition, offset), merged with watermarks and allowed lateness.
Q7Why are ClickHouse block numbers allocated per partition, through Keeper?
  • Merges never cross partitions, so contiguity only matters within one. Per-partition counters spread contention across znodes.
  • Keeper is shared by all replicas of the shard, so any replica can insert and still get a number no other replica will reuse. The ephemeral node marks the number as in flight until the part commits.
Q8Why can't ClickHouse merge 1_1 and 3_3 while block 2 is being inserted?
  • The result would be 1_3 and would claim block 2. When part 2_2 commits it would sit inside an existing part's range: overlapping parts.
  • The merge selector checks for ephemeral block-number locks between candidates. Abandoned numbers are fine because no part will ever claim them.
Q9How does insert deduplication work, and what breaks it?
  • block_id = partition + hash of the block's data; checked and recorded under /blocks in Keeper atomically with the commit.
  • It breaks if the retry is batched differently (different hash), the window has passed (1000 blocks or 7 days), or rows are routed differently. Fix: send the same batch, or set insert_deduplication_token.
  • Async inserts and dependent materialized views have their own dedup settings, off by default (async_insert_deduplicate, deduplicate_blocks_in_dependent_materialized_views).
Q10What happens to inserts if Keeper is unavailable?
  • Replicated tables switch to read-only: INSERTs fail because no block number can be allocated and no part registered. SELECTs keep working on local parts.
  • Merges, fetches and mutations stop too, since they are coordinated through the replication log. Non-replicated MergeTree tables are unaffected.
Q11A customer needs a global order across shards in ClickHouse. What do you tell them?
  • Ask what for. Usually "latest value per key" or "events in time order" covers it, and both are data problems: event-time columns, ReplacingMergeTree(version), argMax, ORDER BY at query time.
  • If they truly need a sequence, assign it upstream (a Kafka partition offset, a Snowflake ID) and store it as a column. Don't make every insert coordinate across shards.
Q12Make Kafka → ClickHouse ingestion effectively exactly-once.
  • Build deterministic batches per partition offset range and set insert_deduplication_token to something like topic:partition:start-end.
  • Insert into a Replicated table, then commit offsets. A crash between the two causes a retry, which Keeper dedups within the window.
Q13A store uses last-write-wins. How can it lose data, and what would you do?
  • Skew larger than the gap between two writes makes the later write lose silently.
  • Options: conditional writes (compare-and-set), version vectors with siblings, CRDTs for mergeable types, HLC with a bounded offset, or route each key through one leader.
Q14Design gap-free invoice numbers.
  • Gap-free requires allocating the number inside the same transaction that commits the invoice, on one serialized counter. Blocks and Snowflake can't do it.
  • Throughput is one row lock's rate; shard by legal entity or series if the business allows.
10 · Reading list

Further reading

  1. Time, Clocks, and the Ordering of Events in a Distributed System
    Leslie Lamport · Communications of the ACM 21(7), 1978

    Happens-before, logical clocks, and the total order built on them, plus the physical-clock bound in the last section. Short, and still the clearest statement of the problem.

  2. Spanner: Google's Globally-Distributed Database
    Corbett et al. · OSDI 2012

    Know section 3 (the TrueTime API) and the commit-wait rule in section 4 well. The ε measurements are in the evaluation.

  3. Logical Physical Clocks
    Kulkarni, Demirbas et al. · OPODIS 2014

    The HLC algorithm, the (l, c) update rules and the bounds on l − pt and on c. The source for section 4.

  4. Designing Data-Intensive Applications, chapters 8–9
    Martin Kleppmann · O'Reilly, 2017

    Chapter 8, The Trouble with Distributed Systems: unreliable clocks, process pauses, fencing tokens. Chapter 9, Consistency and Consensus: linearizability, ordering guarantees, Lamport timestamps, total order broadcast. Chapter numbers are from the first edition.

  5. Data Replication (ReplicatedMergeTree)
    ClickHouse documentation

    Keeper paths, how replicas exchange parts, insert deduplication and its settings, and recovery after Keeper data loss.