-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path11-distributed-databases.html
More file actions
579 lines (543 loc) · 55.6 KB
/
Copy path11-distributed-databases.html
File metadata and controls
579 lines (543 loc) · 55.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0">
<script>try{var t=localStorage.getItem("dbms-theme")||"dark";document.documentElement.setAttribute("data-theme",t)}catch(e){document.documentElement.setAttribute("data-theme","dark")}</script>
<title>Distributed Databases — DBMS Illustrated</title>
<link rel="stylesheet" href="../css/style.css">
<style>:root{--topic-color:#A855F7}</style>
</head>
<body>
<div class="reading-progress" id="reading-progress"></div>
<nav class="navbar">
<div class="navbar-inner">
<a class="navbar-brand" href="../index.html"><span class="brand-icon" style="color:var(--primary-soft)">◆</span>DBMS Illustrated</a>
<div class="navbar-links"><a href="../index.html#topics">All Topics</a></div>
<div class="navbar-actions"><button class="btn-icon" id="theme-toggle" title="Toggle theme">☼</button></div>
</div>
</nav>
<div class="container">
<div class="breadcrumb">
<a href="../index.html">Home</a><span class="breadcrumb-sep">›</span>
<a href="../index.html#topics">Course</a><span class="breadcrumb-sep">›</span>
<span>Distributed Databases</span>
</div>
<div class="topic-header">
<div class="topic-badge">Topic 11</div>
<h1>Distributed <span class="accent">Databases</span></h1>
<p class="subtitle">A single computer can only store so much data and handle so many requests. When one machine is not enough, databases spread their data across many machines. That sounds simple, but it creates hard problems: how do all those machines agree on what the latest data is? What happens when the network between them fails? This topic explains how modern databases solve those problems.</p>
<div class="company-badges">
<span class="badge">Spanner (Google)</span><span class="badge">CockroachDB</span><span class="badge">YugabyteDB</span>
<span class="badge">Vitess</span><span class="badge">TiDB</span>
</div>
</div>
<div class="at-a-glance reveal">
<h3>At a Glance</h3>
<ul>
<li><strong>Raft consensus</strong> — a protocol for making a group of servers agree on a sequence of changes. One server is elected leader and handles all writes. The others follow. A change is only considered committed once a majority of servers have acknowledged it. If the leader dies, the remaining servers hold an election and pick a new one.</li>
<li><strong>CAP theorem</strong> — when the network between servers breaks, you face an unavoidable choice: either stop answering requests until the network is fixed (prioritizing Consistency), or keep answering requests even if some data might be stale (prioritizing Availability). No distributed system can avoid this trade-off.</li>
<li><strong>Sharding</strong> — splitting a huge table across multiple machines, each holding a slice of the data. Range sharding groups nearby keys together (great for range queries, but all new inserts might pile onto one machine). Hash sharding spreads data evenly but makes range queries expensive.</li>
<li><strong>2PC (Two-Phase Commit)</strong> — when a transaction spans multiple machines, this protocol coordinates them. First, every machine says "I'm ready to commit." Then, if all agree, the coordinator tells everyone to commit. The flaw: if the coordinator crashes between those two steps, the other machines are stuck waiting — holding locks indefinitely.</li>
<li><strong>PACELC model</strong> — even when nothing is broken, distributed systems still face a trade-off between responding fast (possibly with slightly stale data) or responding slowly (but guaranteed fresh). PACELC extends CAP to cover this everyday trade-off, not just the failure case.</li>
</ul>
</div>
<!-- ── CAP Theorem ───────────────────────────────────────── -->
<div class="section-label">CAP Theorem</div>
<h2 class="section-title">Consistency, Availability, and Partition Tolerance</h2>
<p class="section-desc">The CAP theorem (Brewer, 2000) states that a distributed data store can guarantee at most two of three properties simultaneously. In practice, network partitions happen — so the real choice is between Consistency and Availability during a partition.</p>
<div class="mini-cards">
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>Consistency (C)</h4>
<p>Every read returns the most recent write. If you update a value on one server, any other server in the cluster must immediately reflect that update. To achieve this, servers must synchronize before responding — which adds latency. The strongest form, where reads always reflect writes in real time, is called linearizability. Examples: etcd, ZooKeeper, Spanner.</p>
</div>
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>Availability (A)</h4>
<p>Every request gets a response — the system never says "I am unavailable." Even if some servers are unreachable, the remaining ones keep serving requests. The trade-off is that those responses might be based on slightly stale data that has not yet been updated on that particular server. Examples: Cassandra, DynamoDB, and CouchDB prioritize staying available over being perfectly up to date.</p>
</div>
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>Partition Tolerance (P)</h4>
<p>A network partition is when some servers in the cluster can no longer communicate with others — a cable gets cut, a router fails, a data center loses connectivity. Partition tolerance means the system keeps running despite this. Since network failures are inevitable at scale, partition tolerance is not a choice you can opt out of. Every real distributed system must be partition tolerant. The genuine choice is: when a partition happens, do you preserve Consistency or Availability?</p>
</div>
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>PACELC Extension</h4>
<p>CAP only tells you what happens during a network failure. But most of the time, nothing is broken — and even then, trade-offs exist. The PACELC model adds the everyday dimension: when there is no partition (E = "Else"), you still choose between Latency (fast but possibly stale) and Consistency (accurate but slower). Confirming a write on 3 servers before responding is correct but adds network round-trips. Confirming on 1 and updating the others in the background is fast but risks data loss if that one server crashes. Every distributed database lives somewhere on this spectrum.</p>
</div>
</div>
<div class="table-wrap">
<table class="compare-table">
<thead>
<tr><th>Database</th><th>CAP Classification</th><th>During Partition</th><th>Without Partition</th><th>PACELC</th></tr>
</thead>
<tbody>
<tr><td>Spanner / CockroachDB</td><td>CP</td><td>Rejects writes to minority shards</td><td>Linearizable reads (higher latency)</td><td>PC/EL (low latency traded for consistency)</td></tr>
<tr><td>Cassandra (quorum)</td><td>AP</td><td>Accepts writes to any live node</td><td>Tunable consistency (ONE to ALL)</td><td>PA/EL</td></tr>
<tr><td>DynamoDB (eventual)</td><td>AP</td><td>Serves stale reads</td><td>Low latency reads</td><td>PA/EL</td></tr>
<tr><td>PostgreSQL (sync standby)</td><td>CP</td><td>Blocks until quorum available</td><td>Strong consistency, higher write latency</td><td>PC/EC</td></tr>
<tr><td>MySQL (async replication)</td><td>AP</td><td>Primary keeps serving</td><td>Stale reads from replicas possible</td><td>PA/EL</td></tr>
<tr><td>etcd / ZooKeeper</td><td>CP</td><td>Refuses requests without quorum</td><td>Linearizable, low read latency</td><td>PC/EC</td></tr>
</tbody>
</table>
</div>
<!-- ── Core Concepts ──────────────────────────────────────── -->
<div class="section-label">Core Concepts</div>
<div class="mini-cards">
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>Raft Consensus</h4>
<p>Raft is an algorithm for getting a group of servers to agree on a shared log of changes. Think of it like a group of people trying to keep a shared notebook in sync. One person (the leader) writes all new entries. Everyone else copies them. A new entry is considered official only once more than half of the group has written it down. If the leader drops out, the group holds a quick election and picks someone else. Raft was designed to be easier to understand than its predecessor, Paxos.</p>
</div>
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>Sharding</h4>
<p>Imagine a library that has grown so large it cannot fit in one building. You split it across multiple buildings — "A-M" in one, "N-Z" in the other. Sharding does the same for databases: it splits rows across multiple machines based on a shard key. You need a strategy for how to split: Range sharding keeps rows in alphabetical or numerical order (good for range queries, but new rows might pile up at the end). Hash sharding scrambles the assignment (even distribution, but range queries become expensive).</p>
</div>
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>Replication</h4>
<p>Replication means keeping copies of the same data on multiple machines so that if one fails, the others can take over. The key question is timing. Synchronous replication waits for the copies to confirm they received the data before telling the client "done" — no data is ever lost, but every write takes longer. Asynchronous replication tells the client "done" immediately and updates the copies in the background — faster writes, but if the primary crashes before the copies catch up, the recent writes are gone.</p>
</div>
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>Two-Phase Commit</h4>
<p>When a single transaction needs to update data on two or more separate machines, those machines need to agree: either all commit or none do. Two-Phase Commit (2PC) coordinates this. Phase 1: the coordinator asks everyone "are you ready to commit?" Each machine does the work, holds the locks, and says "yes" or "no." Phase 2: if everyone said yes, the coordinator sends the final commit signal. The known flaw: if the coordinator crashes after all the "yes" votes but before sending the final signal, every participant is stuck indefinitely — holding locks with no way to proceed.</p>
</div>
</div>
<!-- ── Raft Protocol ───────────────────────────────────────── -->
<div class="section-label">Raft Protocol</div>
<h2 class="section-title">Raft Leader Election and Log Replication</h2>
<p class="section-desc">Raft breaks consensus into three sub-problems: leader election, log replication, and safety. Its key design goal: understandability — one correct implementation path, not a proof of equivalence to Paxos.</p>
<div class="steps">
<div class="step-item">
<div class="step-num">1</div>
<div>
<h4>Heartbeats and election timeouts</h4>
<p>The leader keeps followers informed by sending periodic heartbeat messages — essentially "I am still alive" pings. Each follower has a countdown timer. Every time a heartbeat arrives, the timer resets. If the timer runs out before the next heartbeat, the follower concludes the leader is gone and starts an election. Timers are randomized (150–300ms) so that two followers do not start elections at the exact same moment, which would split the votes and delay the outcome.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">2</div>
<div>
<h4>RequestVote — becoming a candidate</h4>
<p>When a follower's timer runs out, it becomes a candidate and asks the other servers to vote for it. A server will vote "yes" only if two conditions are met: it has not already voted in this election round, and the candidate's log is at least as complete as its own. This second condition is crucial — it prevents a server with outdated data from becoming leader and potentially overwriting committed changes with old ones.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">3</div>
<div>
<h4>Majority quorum and victory</h4>
<p>If the candidate collects votes from more than half the cluster, it wins and immediately starts sending heartbeats to assert its leadership. With 3 servers, you need 2 votes. With 5, you need 3. With 7, you need 4. Larger clusters can survive more failures, but also require more ACKs before a write is considered committed — which adds latency. This is why most Raft clusters run with 3 or 5 nodes, not dozens.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">4</div>
<div>
<h4>Log replication</h4>
<p>When a client sends a write to the leader, the leader appends it to its own log and then sends the entry to all followers. Once a majority of servers have written the entry to their logs and confirmed it, the entry is considered committed. The leader applies the change and responds to the client. Followers apply committed entries in the same order. The guarantee: once any server considers entry number N to be committed, no server will ever record a different entry at position N.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">5</div>
<div>
<h4>Leader completeness</h4>
<p>Raft's core safety rule is that a newly elected leader always has all previously committed entries in its log. This is guaranteed by the voting rule: if a server has a more up-to-date log than the candidate, it refuses to vote for that candidate. So any candidate that wins a majority must already have all committed entries — because the majority of voters that confirmed those entries will refuse to elect anyone who is missing them.</p>
</div>
</div>
</div>
<!-- ── Two-Phase Commit ───────────────────────────────────── -->
<div class="section-label">2PC Protocol</div>
<h2 class="section-title">Two-Phase Commit in Detail</h2>
<p class="section-desc">Two-Phase Commit (2PC) enables atomic distributed transactions — all-or-nothing across multiple database shards. It is the workhorse protocol for cross-shard ACID, despite its well-known blocking limitation.</p>
<div class="steps">
<div class="step-item">
<div class="step-num">1</div>
<div>
<h4>Phase 1: PREPARE</h4>
<p>The coordinator (the server managing the transaction) sends a PREPARE message to every machine involved. Each machine does the actual work — runs the query, acquires locks, and writes a safety record to its journal so the work can be completed later — and then responds YES if it is ready to commit, or NO if something went wrong. After responding YES, each machine is in a waiting state: it has done everything except make the final commitment, and it is holding all its locks.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">2</div>
<div>
<h4>Phase 2: COMMIT or ABORT</h4>
<p>Once all participants respond YES, the coordinator writes a COMMIT record to its own journal and sends COMMIT to everyone. Each machine commits its piece of the transaction, releases its locks, and confirms. If even one participant said NO, or if a timeout occurs with no response, the coordinator sends ABORT instead. Every machine rolls back and releases locks. The transaction is canceled as if it never started.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">3</div>
<div>
<h4>The blocking problem</h4>
<p>Here is the fundamental flaw of 2PC. Imagine the coordinator crashes after collecting all the YES votes but before it can send the COMMIT signal. Every participant is stuck: they have done the work, they are holding their locks, and they cannot decide on their own whether to commit or roll back — they need the coordinator's final word. Until the coordinator recovers (which could take minutes), those locks are held and no other transaction can touch that data. This is called the blocking problem, and it is an inherent limitation of the two-phase design.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">4</div>
<div>
<h4>Overcoming the blocking problem</h4>
<p>Three-Phase Commit (3PC) inserts an extra step to break the blocking scenario, but it adds more network round trips and makes assumptions about timing that are hard to guarantee in practice. Real production systems like Spanner and CockroachDB take a different approach: they run the coordinator itself on a Raft group. If the coordinator crashes, the Raft group elects a new leader that can read the coordinator's log and resume exactly where it left off. This effectively eliminates the blocking window, at the cost of more complex failure recovery logic.</p>
</div>
</div>
</div>
<!-- ── Sharding Strategies ────────────────────────────────── -->
<div class="section-label">Sharding</div>
<h2 class="section-title">Sharding Strategies and Consistent Hashing</h2>
<p class="section-desc">Sharding splits data horizontally across multiple independent database instances. The shard key determines which node holds each row. Shard key selection is the most consequential design decision in a sharded architecture.</p>
<div class="table-wrap">
<table class="compare-table">
<thead>
<tr><th>Strategy</th><th>How it works</th><th>Pros</th><th>Cons</th><th>Used by</th></tr>
</thead>
<tbody>
<tr><td>Range sharding</td><td>Partition by key ranges: shard 1 holds keys 0–999, shard 2 holds 1000–1999</td><td>Efficient range queries; easy routing</td><td>Hot spots on sequential keys (all new writes go to last shard)</td><td>CockroachDB, TiDB, HBase</td></tr>
<tr><td>Hash sharding</td><td>shard = hash(key) mod N</td><td>Uniform load distribution; no hot spots</td><td>Range queries require scatter-gather to all shards</td><td>MongoDB, Vitess</td></tr>
<tr><td>Consistent hashing</td><td>Keys and nodes placed on a ring; key goes to next node clockwise</td><td>Adding/removing nodes moves only k/n keys; minimal resharding</td><td>Still no range queries; virtual nodes needed for uniform load</td><td>Cassandra, DynamoDB, Amazon S3</td></tr>
<tr><td>Directory sharding</td><td>Separate lookup service maps each key to a shard</td><td>Arbitrary key placement; easy manual rebalancing</td><td>Lookup service is a bottleneck and SPOF if not replicated</td><td>Flickr (historical), some SaaS multi-tenant systems</td></tr>
</tbody>
</table>
</div>
<div class="steps">
<div class="step-item">
<div class="step-num">1</div>
<div>
<h4>Consistent hashing — virtual nodes</h4>
<p>Basic consistent hashing places each machine at one point on a ring. When you remove a machine, all its data moves to the single neighbor clockwise — which can overwhelm that one machine. Virtual nodes (vnodes) fix this: instead of one position per machine, each physical machine gets many positions spread around the ring (Cassandra uses 150 by default). Now when a machine is removed, its data spreads evenly across many machines rather than piling onto one. Adding a machine works the same way: it claims small slices from many neighbors, spreading the impact.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">2</div>
<div>
<h4>Shard key selection criteria</h4>
<p>Picking the right shard key is the most important design decision in a sharded system. A good shard key has enough distinct values that data spreads evenly — user_id, device_id, or tenant_id are typical good choices. It should rarely change (if the shard key changes, the row has to physically move to a different machine). Most queries should include the shard key, so the database can go directly to one machine rather than asking all of them. The worst choice is an auto-incrementing number — all new rows have the highest value, so all new writes pile onto the same shard. Use random UUIDs or time-bucketed IDs (like ULID) instead.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">3</div>
<div>
<h4>Cross-shard queries</h4>
<p>If a query cannot be answered from one machine, the database has to send the query to every machine (scatter), collect all their partial results, and merge them into a single answer (gather). This scatter-gather approach is much more expensive — if you have 10 shards, the query now involves 10 machines instead of 1. Cross-shard transactions are even heavier since they require 2PC coordination. The rule of thumb: design your data model so the queries you run most often touch only one shard. Related data that is frequently read together should share the same shard key.</p>
</div>
</div>
</div>
<!-- ── Replication ────────────────────────────────────────── -->
<div class="section-label">Replication</div>
<h2 class="section-title">Replication Topologies</h2>
<div class="table-wrap">
<table class="compare-table">
<thead>
<tr><th>Topology</th><th>Write Path</th><th>RPO</th><th>RTO</th><th>Read Scale</th><th>Complexity</th></tr>
</thead>
<tbody>
<tr><td>Single-leader (async)</td><td>Primary only; async to replicas</td><td>> 0 (replica lag)</td><td>Manual failover: minutes</td><td>Yes — from replicas</td><td>Low</td></tr>
<tr><td>Single-leader (sync)</td><td>Primary + wait for N replicas</td><td>0</td><td>Auto failover: seconds</td><td>Limited — sync replica is busy</td><td>Medium</td></tr>
<tr><td>Multi-leader</td><td>Any node; async conflict resolution</td><td>> 0</td><td>Automatic</td><td>Yes — all leaders</td><td>High (conflict resolution)</td></tr>
<tr><td>Leaderless (quorum)</td><td>W nodes (W + R > N for strong)</td><td>Tunable</td><td>Automatic</td><td>Yes — quorum reads</td><td>High (sloppy quorum, hinted handoff)</td></tr>
<tr><td>Raft/Paxos group</td><td>Leader only; sync to majority</td><td>0</td><td>Auto election: <1s</td><td>Limited unless stale reads allowed</td><td>Medium (well-understood)</td></tr>
</tbody>
</table>
</div>
<!-- ── Code Block ─────────────────────────────────────────── -->
<div class="code-block">
<div class="cb-header"><span class="cb-lang">Distributed — Sharding and Consistent Hashing Concepts</span></div>
<pre><span class="cmt">-- Consistent hashing ring: adding a node moves only k/n keys
-- Physical node → vnode positions on a 0..2^32 ring
-- Each key maps to the nearest vnode clockwise</span>
<span class="cmt">-- CockroachDB: automatic range-based sharding
-- Each range = Raft group with 3–5 replicas
-- Ranges auto-split when they exceed 512MB
-- Co-location: pin related rows together with zone configs</span>
<span class="kw">ALTER TABLE</span> orders <span class="kw">CONFIGURE ZONE USING</span>
num_replicas = <span class="num">5</span>,
constraints = <span class="str">'[+region=us-east1]'</span>;
<span class="cmt">-- Vitess (MySQL horizontal sharding)</span>
<span class="kw">ALTER</span> VSCHEMA <span class="kw">ON</span> orders ADD VINDEX hash_customer (customer_id)
<span class="kw">USING</span> hash;
<span class="cmt">-- All orders for a customer route to the same shard
-- Cross-customer queries: scatter-gather across all shards</span>
<span class="cmt">-- PostgreSQL read replica with application-level routing</span>
<span class="cmt">-- Primary: writes; replica lag typically 10ms–2s</span>
<span class="cmt">-- Read replicas: dashboards, reports, analytics</span>
<span class="cmt">-- Use pg_is_in_recovery() to check if you're on a replica</span>
<span class="kw">SELECT</span> pg_is_in_recovery(); <span class="cmt">-- true on replica, false on primary</span>
<span class="cmt">-- 2PC in pseudocode</span>
<span class="cmt">-- Phase 1: PREPARE
-- coordinator → shard_A: "PREPARE txn_id"
-- coordinator → shard_B: "PREPARE txn_id"
-- shard_A → coordinator: "YES" (work done, locks held, log written)
-- shard_B → coordinator: "YES"
-- Phase 2: COMMIT
-- coordinator → shard_A: "COMMIT txn_id"
-- coordinator → shard_B: "COMMIT txn_id"
-- shard_A: commits, releases locks, responds OK
-- shard_B: commits, releases locks, responds OK</span></pre>
</div>
<!-- ── Interactive Demo ───────────────────────────────────── -->
<div class="section-label">Interactive Demo</div>
<h2 class="section-title">Raft Consensus Simulator</h2>
<p class="section-desc">Send a write to the leader and watch log replication to followers. Kill the leader to trigger an election — watch the election timer and the new leader emerge from the remaining nodes.</p>
<div class="diagram-box">
<svg viewBox="0 0 700 230" role="img" aria-label="Raft consensus: leader sends AppendEntries to two followers, both ACK">
<!-- Leader -->
<rect x="260" y="10" width="180" height="62" rx="8" class="svg-box-p"/>
<text x="350" y="32" text-anchor="middle" class="svg-label" style="fill:#7C3AED">LEADER</text>
<text x="350" y="50" text-anchor="middle" class="svg-soft">term=4 log=[1..17]</text>
<text x="350" y="66" text-anchor="middle" class="svg-mono" style="font-size:10px">heartbeat every 150ms</text>
<!-- Follower 1 -->
<rect x="40" y="140" width="180" height="62" rx="8" class="svg-box-c"/>
<text x="130" y="163" text-anchor="middle" class="svg-label" style="fill:#0EA5E9">FOLLOWER 1</text>
<text x="130" y="180" text-anchor="middle" class="svg-soft">term=4 log=[1..16]</text>
<text x="130" y="197" text-anchor="middle" class="svg-mono" style="font-size:10px">election timer: 320ms</text>
<!-- Follower 2 -->
<rect x="480" y="140" width="180" height="62" rx="8" class="svg-box-c"/>
<text x="570" y="163" text-anchor="middle" class="svg-label" style="fill:#0EA5E9">FOLLOWER 2</text>
<text x="570" y="180" text-anchor="middle" class="svg-soft">term=4 log=[1..17]</text>
<text x="570" y="197" text-anchor="middle" class="svg-mono" style="font-size:10px">election timer: 480ms</text>
<!-- AppendEntries arrows leader -> followers -->
<line x1="290" y1="72" x2="175" y2="140" class="svg-line" style="stroke:#7C3AED"/>
<line x1="410" y1="72" x2="525" y2="140" class="svg-line" style="stroke:#7C3AED"/>
<text x="192" y="113" text-anchor="middle" class="svg-soft" style="fill:#7C3AED;font-size:10px">AppendEntries</text>
<text x="508" y="113" text-anchor="middle" class="svg-soft" style="fill:#7C3AED;font-size:10px">AppendEntries</text>
<!-- ACK arrows -->
<line x1="175" y1="155" x2="290" y2="87" class="svg-line svg-dash" style="stroke:#10B981"/>
<line x1="525" y1="155" x2="410" y2="87" class="svg-line svg-dash" style="stroke:#10B981"/>
<text x="192" y="136" text-anchor="middle" class="svg-soft" style="fill:#10B981;font-size:10px">ACK</text>
<text x="508" y="136" text-anchor="middle" class="svg-soft" style="fill:#10B981;font-size:10px">ACK</text>
<!-- Commit note -->
<rect x="240" y="94" width="220" height="36" rx="6" class="svg-box-g"/>
<text x="350" y="109" text-anchor="middle" class="svg-soft">Quorum = 2/3 ACKs</text>
<text x="350" y="124" text-anchor="middle" class="svg-soft">Commit when majority reply</text>
<!-- Client request -->
<rect x="310" y="195" width="80" height="30" rx="6" class="svg-box-a"/>
<text x="350" y="208" text-anchor="middle" class="svg-soft">Client</text>
<text x="350" y="222" text-anchor="middle" class="svg-mono" style="font-size:10px">SET x=5</text>
<line x1="350" y1="195" x2="350" y2="130" class="svg-line svg-dash" style="stroke:#F59E0B"/>
<!-- Packets -->
<circle class="pkt" cx="290" cy="72" r="5" fill="#7C3AED"/>
<circle class="pkt" cx="175" cy="140" r="5" fill="#7C3AED"/>
<circle class="pkt" cx="175" cy="155" r="5" fill="#10B981"/>
<circle class="pkt" cx="350" cy="195" r="5" fill="#F59E0B"/>
</svg>
<p class="diagram-caption">Raft elects one leader per term. The leader appends entries to its log then sends AppendEntries RPCs to followers. A write is committed once a majority (quorum) ACKs. If the leader crashes, followers whose election timer fires first request votes — whoever gets majority becomes the new leader.</p>
</div>
<div class="demo-section" id="demo-distributed">
<div class="demo-header">
<h3>Raft Consensus (3-node cluster)</h3>
<div class="demo-controls">
<button class="demo-btn" data-action="raft-write" style="background:var(--topic-color);color:#fff;border-color:var(--topic-color)">Send Write</button>
<button class="demo-btn danger" data-action="kill-leader">Kill Leader</button>
<button class="demo-btn" data-action="reset-raft">Reset</button>
</div>
</div>
<div class="demo-canvas-wrap"></div>
<div class="demo-hint">Leader = gold border. Green packets = AppendEntries RPCs. Election timer bar animates on leader failure. Log entries shown inside each node.</div>
</div>
<!-- ── Sharding Comparison ────────────────────────────────── -->
<div class="comparison-grid">
<div class="comparison-card">
<h4>Range Sharding</h4>
<ul>
<li>Keys sorted — great for range queries within a shard</li>
<li>Hot spot risk on sequential keys (auto-increment PKs)</li>
<li>Used by CockroachDB, TiDB, HBase</li>
<li>Easy rebalancing by splitting a range</li>
<li>Uneven load if key distribution is skewed</li>
</ul>
</div>
<div class="comparison-card">
<h4>Hash Sharding</h4>
<ul>
<li>Uniform load distribution — no hot spots</li>
<li>Range queries require scatter-gather (expensive)</li>
<li>Used by Cassandra, DynamoDB, Vitess, MongoDB</li>
<li>Consistent hashing minimizes key movement on resize</li>
<li>Resharding is operationally complex</li>
</ul>
</div>
</div>
<!-- ── Change Data Capture ────────────────────────────────── -->
<div class="section-label">Data Propagation</div>
<h2 class="section-title">Change Data Capture (CDC)</h2>
<p class="section-desc">CDC streams database changes (inserts, updates, deletes) to downstream consumers — analytics databases, search indexes, caches, and event streams. It works by reading the database's replication log (WAL in PostgreSQL, binlog in MySQL) rather than polling tables.</p>
<div class="steps">
<div class="step-item">
<div class="step-num">1</div>
<div>
<h4>How CDC works</h4>
<p>Instead of repeatedly querying the database to check what changed, CDC (Change Data Capture) reads directly from the database's internal journal — the WAL in PostgreSQL, or the binlog in MySQL. Every time a row is inserted, updated, or deleted, the journal records it. A CDC connector (like Debezium, AWS DMS, or Google Datastream) reads that journal and converts each change into a structured event containing the table name, the type of change, and the before and after values. Those events are published to a message queue like Kafka for other systems to consume.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">2</div>
<div>
<h4>Use cases</h4>
<p>CDC is how many real systems stay in sync across multiple data stores. When a product is updated in your database, CDC can automatically update your Elasticsearch search index without you writing any extra code to do so. When a row changes, CDC can tell Redis to invalidate the cached version. It can write every change to an immutable audit log. It can publish domain events to other microservices — replacing the fragile pattern of writing to the database and also publishing to a message queue at the same time (which could get out of sync if either step fails).</p>
</div>
</div>
<div class="step-item">
<div class="step-num">3</div>
<div>
<h4>At-least-once semantics</h4>
<p>CDC connectors guarantee that every change event is delivered at least once. After a restart, the connector picks up from its last saved position and may re-send events it already delivered before the crash. This means the systems receiving those events must be able to handle duplicates gracefully: applying the same event twice should produce the same result as applying it once. This property is called idempotency. In practice, this means using patterns like INSERT … ON CONFLICT DO NOTHING, or conditional updates that only apply if the version number matches what you expect.</p>
</div>
</div>
</div>
<!-- ── Paxos vs Raft ──────────────────────────────────────── -->
<div class="section-label">Consensus Comparison</div>
<h2 class="section-title">Paxos vs Raft</h2>
<div class="table-wrap">
<table class="compare-table">
<thead>
<tr><th>Property</th><th>Paxos (Multi-Paxos)</th><th>Raft</th></tr>
</thead>
<tbody>
<tr><td>Design goal</td><td>Mathematical correctness proof</td><td>Understandability — one correct implementation path</td></tr>
<tr><td>Leader</td><td>Distinguished proposer; can be complex</td><td>Explicit, durable leader state; one leader per term</td></tr>
<tr><td>Log management</td><td>Gaps allowed in log; complex to implement</td><td>No gaps — log always contiguous</td></tr>
<tr><td>Leader election</td><td>Prepare phase is reused for election</td><td>Separate RequestVote phase</td></tr>
<tr><td>Implementation complexity</td><td>High — many valid implementations, easy to get subtly wrong</td><td>Lower — Raft paper includes a full reference implementation</td></tr>
<tr><td>Used by</td><td>Spanner (Paxos), Chubby, Zookeeper (ZAB, Paxos variant)</td><td>CockroachDB, etcd, TiKV, CockroachDB</td></tr>
<tr><td>Performance (WAN)</td><td>Similar — both need majority quorum</td><td>Similar — one round-trip per commit with stable leader</td></tr>
</tbody>
</table>
</div>
<!-- ── Anti-patterns ──────────────────────────────────────── -->
<div class="section-label">Anti-patterns</div>
<div class="antipatterns">
<div class="antipattern">
<h4>Auto-increment PKs as shard keys</h4>
<p>Sequential keys route all writes to the shard holding the latest range — a "write hot spot." One shard gets 100% of write traffic while others sit idle. Use random UUIDs (UUID v4), time-prefixed IDs (ULID/KSUID with random suffix), or hash(user_id) to distribute writes uniformly. In CockroachDB, use UUID primary keys instead of SERIAL.</p>
</div>
<div class="antipattern">
<h4>Cross-shard transactions for every operation</h4>
<p>2PC is expensive: 2 network round-trips, multiple synchronous log flushes, and blocking on coordinator failure. Design your data model so related entities share the same shard key (all rows for a user on the same shard, all rows for a tenant on the same shard). Cross-shard 2PC is unavoidable for some operations — minimize it, don't eliminate it at the cost of your data model's correctness.</p>
</div>
<div class="antipattern">
<h4>Under-sized Raft groups</h4>
<p>A 2-node cluster provides no fault tolerance — one node failure loses quorum. Always use odd numbers: 3 nodes (tolerate 1 failure), 5 nodes (tolerate 2 failures). Do not add more than 7 nodes to a single Raft group — write latency grows proportionally because the majority quorum is larger (4 ACKs for a 7-node group). For larger clusters, use multiple Raft groups (shards), each with 3–5 replicas.</p>
</div>
<div class="antipattern">
<h4>Assuming replica reads are strongly consistent</h4>
<p>Async replication means read replicas have lag — typically milliseconds but can be seconds during high write load or network issues. Reads from replicas may return stale data. Application code must either: (1) always read from the primary for consistency-critical paths, (2) route to replica only for explicitly eventually-consistent reads (dashboards, analytics), or (3) implement "read-your-writes" routing (a session always reads from the same replica it just wrote to).</p>
</div>
<div class="antipattern">
<h4>Using wall-clock timestamps for distributed ordering</h4>
<p>NTP-synchronized clocks on different nodes can drift by 100ms or more, and can go backwards. Using wall-clock timestamps to order distributed events gives wrong results: a write on Node A at time T and a write on Node B at time T+1ms may actually be concurrent, or Node B's write may causally precede Node A's. Use logical clocks (Lamport timestamps), vector clocks, or database-provided timestamps (Spanner's TrueTime, CockroachDB's hybrid logical clocks).</p>
</div>
</div>
<!-- ── Quiz ──────────────────────────────────────────────── -->
<div class="section-label">Quiz</div>
<div class="quiz-section">
<div class="quiz-question">
<div class="quiz-q-num">Question 1 of 5</div>
<div class="quiz-q-text">In Raft, a new leader is elected when:</div>
<div class="quiz-options">
<div class="quiz-option" data-correct="false" data-explanation="In Raft, any follower can trigger an election — not just nodes that explicitly request leadership."><span class="opt-letter">A</span>Any node explicitly requests a leadership change</div>
<div class="quiz-option" data-correct="true" data-explanation="A follower starts an election when its randomized election timeout expires without receiving a heartbeat from the current leader. This indicates the leader may be dead or unreachable."><span class="opt-letter">B</span>A follower's election timeout expires without receiving a leader heartbeat</div>
<div class="quiz-option" data-correct="false" data-explanation="Elections in Raft are triggered by timeout, not by explicit agreement of a majority."><span class="opt-letter">C</span>50%+1 nodes simultaneously agree to elect a new leader</div>
<div class="quiz-option" data-correct="false" data-explanation="Raft does not have a designated master — any follower can start an election."><span class="opt-letter">D</span>The designated master fails over to a standby</div>
</div>
<div class="quiz-feedback"></div>
</div>
<div class="quiz-question">
<div class="quiz-q-num">Question 2 of 5</div>
<div class="quiz-q-text">Two-Phase Commit (2PC) can block indefinitely when:</div>
<div class="quiz-options">
<div class="quiz-option" data-correct="false" data-explanation="All nodes responding is the happy path — no blocking occurs."><span class="opt-letter">A</span>All participant nodes respond promptly to PREPARE</div>
<div class="quiz-option" data-correct="true" data-explanation="The fundamental blocking problem: if the coordinator fails after sending PREPARE but before sending COMMIT/ABORT, participants are stuck in the PREPARED state — holding locks and unable to commit or abort without the coordinator's decision."><span class="opt-letter">B</span>The coordinator fails after PREPARE but before sending COMMIT/ABORT</div>
<div class="quiz-option" data-correct="false" data-explanation="Fast networks reduce 2PC latency but don't prevent the coordinator-failure blocking scenario."><span class="opt-letter">C</span>The network is fast and all nodes are healthy</div>
<div class="quiz-option" data-correct="false" data-explanation="Participants in PREPARED state do hold locks — the absence of locks would make the scenario less severe, not more."><span class="opt-letter">D</span>No locks are held by any participant</div>
</div>
<div class="quiz-feedback"></div>
</div>
<div class="quiz-question">
<div class="quiz-q-num">Question 3 of 5</div>
<div class="quiz-q-text">Consistent hashing reduces resharding cost because:</div>
<div class="quiz-options">
<div class="quiz-option" data-correct="false" data-explanation="That is what naive modulo hashing does — consistent hashing was invented to avoid this."><span class="opt-letter">A</span>All keys are rehashed when the node count changes</div>
<div class="quiz-option" data-correct="true" data-explanation="With consistent hashing, adding or removing a node only affects k/n keys (where k=total keys, n=node count) — only the keys assigned to the adjacent slots on the ring move to their new neighbor. Naive modulo hashing remaps k×(n-1)/n keys."><span class="opt-letter">B</span>Only k/n keys need remapping when adding or removing a node</div>
<div class="quiz-option" data-correct="false" data-explanation="Consistent hashing works for any number of nodes — the ring is a conceptual structure, not a physical limit."><span class="opt-letter">C</span>The system is limited to exactly 3 nodes</div>
<div class="quiz-option" data-correct="false" data-explanation="Consistent hashing uses hash functions to place keys and nodes on a ring — not B-trees."><span class="opt-letter">D</span>Data is stored in B-trees internally, avoiding rehashing</div>
</div>
<div class="quiz-feedback"></div>
</div>
<div class="quiz-question">
<div class="quiz-q-num">Question 4 of 5</div>
<div class="quiz-q-text">According to CAP theorem, during a network partition a distributed system must choose between:</div>
<div class="quiz-options">
<div class="quiz-option" data-correct="false" data-explanation="Speed and safety are practical concerns but not the formal CAP theorem properties."><span class="opt-letter">A</span>Speed and safety</div>
<div class="quiz-option" data-correct="true" data-explanation="During a partition, you must choose: keep serving requests (Availability) but risk returning stale data, or refuse requests to partitioned nodes (Consistency) to ensure all reads see the latest write. Partition tolerance is not a choice — all real distributed systems must tolerate partitions."><span class="opt-letter">B</span>Consistency and Availability (Partition Tolerance is mandatory)</div>
<div class="quiz-option" data-correct="false" data-explanation="Consistency and Partition Tolerance are indeed two CAP properties, but the choice during a partition is between C and A — you cannot give up P in any real distributed system."><span class="opt-letter">C</span>Consistency and Partition Tolerance</div>
<div class="quiz-option" data-correct="false" data-explanation="Availability and Partition Tolerance are two CAP properties, but the trade-off during a partition is between A and C."><span class="opt-letter">D</span>Availability and Partition Tolerance</div>
</div>
<div class="quiz-feedback"></div>
</div>
<div class="quiz-question">
<div class="quiz-q-num">Question 5 of 5</div>
<div class="quiz-q-text">Why is using auto-increment IDs as a shard key a problem?</div>
<div class="quiz-options">
<div class="quiz-option" data-correct="false" data-explanation="Auto-increment IDs are unique — there is no collision issue."><span class="opt-letter">A</span>They cause key collisions across shards</div>
<div class="quiz-option" data-correct="true" data-explanation="Auto-increment IDs are sequential — all new inserts have the highest value, so they all route to the shard holding the highest range. This creates a write hot spot: one shard receives all writes while others are idle. Use UUID v4 or ULID for uniform distribution."><span class="opt-letter">B</span>Sequential keys route all writes to the shard holding the highest range (write hot spot)</div>
<div class="quiz-option" data-correct="false" data-explanation="Auto-increment IDs are fine as primary keys for lookup — the problem is using them as the shard key that determines data distribution."><span class="opt-letter">C</span>Auto-increment IDs cannot be used as primary keys in sharded systems</div>
<div class="quiz-option" data-correct="false" data-explanation="Replication is unrelated to the shard key type — both UUID and auto-increment replicate equally well."><span class="opt-letter">D</span>They prevent proper replication across nodes</div>
</div>
<div class="quiz-feedback"></div>
</div>
</div>
<!-- ── Interview Q&A ──────────────────────────────────────── -->
<div class="section-label">Interview Q&A</div>
<div class="qa-section">
<div class="qa-item">
<div class="qa-q">How does the Raft consensus algorithm ensure linearizability?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">Raft ensures linearizability through: (1) <strong>Leader completeness:</strong> a leader always has all committed log entries — votes are only granted to candidates whose log is at least as up-to-date as the voter's. (2) <strong>Majority commit:</strong> an entry is committed only after being replicated to a majority of nodes — any future majority quorum will include at least one node with the entry. (3) <strong>State machine safety:</strong> all nodes apply log entries in the same order — state machine determinism guarantees identical state. (4) <strong>Read linearizability:</strong> reads from the leader must verify leadership before serving (via a read-index round-trip or lease renewal) — a partitioned stale leader must not serve reads. CockroachDB uses leader leases (with expiry time) to serve reads without a heartbeat round-trip while still guaranteeing freshness.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">What is the difference between synchronous and asynchronous replication?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner"><strong>Synchronous:</strong> before ACKing a write to the client, wait for at least one (or more) replicas to confirm they have durably written the data. Zero RPO (no committed data lost on primary failure). Tradeoff: write latency includes replica round-trip — if the replica is 50ms away, every write is at least 50ms. Used by Raft/Paxos (majority quorum), PostgreSQL synchronous_standby_names. <strong>Asynchronous:</strong> ACK the write immediately after writing to the primary. Replicas catch up in background. Lower write latency but RPO > 0 — failover to an async replica may lose recently committed transactions. MySQL binlog replication and PostgreSQL streaming replication are async by default. Rule: use synchronous for primary data stores where data loss is unacceptable; async for read replicas where slight staleness is explicitly tolerable.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">How do you choose a shard key? What makes a bad shard key?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">Good shard key criteria: (1) <strong>High cardinality:</strong> enough distinct values to distribute data evenly across shards. (2) <strong>Low update rate:</strong> changing a shard key requires moving the row — high update shard keys create constant data movement. (3) <strong>Query alignment:</strong> most queries filter on the shard key — avoid cross-shard scatter-gather. (4) <strong>No sequential hot spots:</strong> monotonically increasing keys (auto-increment IDs, timestamps) put all writes on the latest shard. Bad shard keys: auto-increment ID (sequential), status/enum (low cardinality, imbalanced), created_at alone (time-based hot spot). Good shard keys: user_id (high cardinality, user-centric queries), tenant_id (multi-tenant SaaS), hash(user_id) (if user_id is sequential).</div></div>
</div>
<div class="qa-item">
<div class="qa-q">How does Google Spanner achieve global ACID transactions?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">Spanner combines four innovations: (1) <strong>TrueTime API:</strong> GPS + atomic clocks in every datacenter. TrueTime returns a time interval [earliest, latest] with bounded uncertainty (~7ms). Commit timestamps are chosen after the TrueTime interval's latest bound — ensuring external consistency: if Txn2 starts after Txn1 commits in real time, Txn2's commit timestamp is strictly greater. (2) <strong>Paxos groups:</strong> each data shard is a Paxos replication group for strong per-shard consistency. (3) <strong>2PC over Paxos:</strong> cross-shard distributed transactions use 2PC, with each shard's Paxos group providing fault-tolerant coordinator state — eliminating the 2PC blocking window. (4) <strong>MVCC:</strong> multi-version storage enables consistent snapshots across all shards globally. Result: RPO=0, RTO ~seconds for regional failures, with true external consistency at global scale.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">What is Change Data Capture and how does it differ from polling?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">CDC reads the database's replication log (WAL in PostgreSQL, binlog in MySQL) to stream every committed change as a structured event. It differs from polling (SELECT * WHERE updated_at > last_check) in: (1) <strong>Completeness:</strong> CDC captures DELETEs; polling cannot detect what was deleted without keeping tombstones. (2) <strong>Low latency:</strong> CDC emits events within milliseconds; polling adds lag equal to the poll interval. (3) <strong>No DB load from polling:</strong> CDC reads a log; polling runs queries that must be indexed. (4) <strong>Ordering:</strong> CDC events arrive in commit order; polling results are unordered unless sorted. Tools: Debezium (open source, connects to PostgreSQL/MySQL/SQL Server), AWS DMS, Google Datastream, Confluent Platform. Use cases: search index sync, cache invalidation, audit log, event-driven microservice communication (outbox pattern). Limitation: CDC is at-least-once — consumers must be idempotent.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">Explain the CAP theorem and what it means for real-world database design.<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">CAP (Consistency, Availability, Partition Tolerance) states that during a network partition, a distributed system can provide at most two of the three. Partition tolerance is not optional — network partitions happen in any real distributed system. So the real choice is C vs A during a partition. CP systems (etcd, Spanner, CockroachDB): refuse to serve requests to the minority side of a partition — no stale reads, but some nodes are unavailable. AP systems (Cassandra, DynamoDB, Riak): continue serving all nodes during a partition, accepting that different nodes may return different values — stale reads possible. Practical implication: most OLTP databases choose CP (strong consistency). Cassandra lets you tune per-operation: read ONE (AP) or read QUORUM (CP-like). The PACELC extension adds: even without partitions, there is a latency vs consistency tradeoff. All systems live somewhere on this spectrum — no free lunch.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">What is Vitess and when would you use it over a native distributed database?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">Vitess is a horizontal sharding and connection pooling layer for MySQL — originally built at YouTube, now used by GitHub, Slack, Square. It sits in front of multiple MySQL instances and handles: query routing (rewrite SQL for the correct shard), connection pooling (reduce MySQL connections from thousands to hundreds), cross-shard queries (scatter-gather), online schema changes (blocking-free ALTER TABLE), and automatic failover. Use Vitess when: your MySQL database is hitting write limits (disk, CPU, connections), you want to stay on MySQL for operational familiarity and existing tooling, and you don't need global consistency across shards. Prefer CockroachDB/YugabyteDB when: you're greenfield, need strong ACID across shards, want a simpler operational model (no Vitess orchestration layer), or need geographic distribution with zone-aware reads.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">How does multi-leader replication work and what problems does it create?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">In multi-leader replication, multiple nodes can accept writes independently and replicate to each other asynchronously. Used in: multi-datacenter setups (Galera Cluster for MySQL, PostgreSQL BDR), collaborative editing (Google Docs), offline-capable apps (CouchDB). Benefit: writes are local to the datacenter — low write latency. Problem: write conflicts. If two leaders concurrently update the same row, both updates are "correct" locally but the replicated state is inconsistent. Conflict resolution strategies: Last Write Wins (LWW) — use timestamp to pick one, discarding the other. Silently loses data. Merge — attempt to union the changes (works for counters and sets, not arbitrary fields). Application-defined resolution — propagate conflict to application to resolve. CRDTs (Conflict-Free Replicated Data Types) — mathematically designed data structures where any merge is valid and commutative (counters, sets, maps). Multi-leader is best used when conflicts are rare and any conflict resolution strategy is acceptable — not for inventory, financial, or booking systems where correctness is critical.</div></div>
</div>
</div>
<div class="section-label">Further Reading</div>
<div class="reading-links">
<a class="reading-link" href="https://raft.github.io/" target="_blank">The Raft Consensus Algorithm</a>
<a class="reading-link" href="https://cloud.google.com/spanner/docs/true-time-external-consistency" target="_blank">Spanner TrueTime and External Consistency</a>
<a class="reading-link" href="https://planetscale.com/docs/concepts/vitess-primer" target="_blank">Vitess Primer (PlanetScale)</a>
<a class="reading-link" href="https://www.cl.cam.ac.uk/research/dtg/www/files/publications/public/mk428/cap-critique.pdf" target="_blank">Critique of the CAP Theorem (Kleppmann)</a>
<a class="reading-link" href="https://debezium.io/documentation/reference/stable/" target="_blank">Debezium CDC Documentation</a>
</div>
<div class="topic-nav">
<a href="10-nosql.html" class="topic-nav-link"><div class="topic-nav-arrow">←</div><div><div class="topic-nav-label">Previous</div><div class="topic-nav-title">NoSQL Databases</div></div></a>
<a href="12-interview-guide.html" class="topic-nav-link next"><div class="topic-nav-arrow">→</div><div><div class="topic-nav-label">Next</div><div class="topic-nav-title">Interview Guide</div></div></a>
</div>
</div>
<footer class="site-footer">
<p class="footer-sub"><a href="../index.html">Back to Course</a> — DBMS Illustrated</p>
</footer>
<script src="../js/main.js"></script>
<script src="../js/demos.js"></script>
</body>
</html>