Jawaban singkat untuk pertanyaan yang paling sering diajukan pembaca tentang topik ini.
Cara mendesain distributed key-value store ala Dynamo: consistent hashing, quorum N/W/R, vector clock, hinted handoff, Merkle tree, gossip, dan node LSM.
Matthews Wong
Software Engineer
Ringkasan Utama
Key-value store ala Dynamo me-hash setiap key ke sebuah ring, menyalinnya ke N replica, lalu menjawab setelah W replica mengonfirmasi write atau R replica menjawab read. Vector clock menandai write yang bentrok, hinted handoff dan anti-entropy Merkle tree memperbaiki kegagalan, gossip melacak membership, dan tiap node menyimpan data dalam LSM tree.
Saya menjalankan Postgres, Redis, dan Docker di satu VPS untuk pekerjaan ERP dan POS, dan satu primary Postgres dengan satu replica selalu cukup. Jadi saya belum pernah mengoperasikan cluster ala Dynamo, dan saya tidak mau berpura-pura sebaliknya. Saya menulis post ini, beserta dua program TypeScript kecil di dalamnya, untuk memahami mengapa desainnya berbentuk seperti itu.
Rujukan utamanya adalah paper Amazon Dynamo tahun 2007, paper LSM-tree tahun 1996, serta halaman referensi vector clock dan Merkle tree, semuanya ditautkan di akhir. Setiap angka dikutip dari sumber tersebut atau dihitung dengan aritmetika yang ditunjukkan, dan kedua output kode berasal dari menjalankan kodenya.
Ini adalah database dengan satu bentuk operasi, get(key) dan put(key, value), yang tersebar di banyak node setara tanpa leader. Paper Dynamo membangunnya untuk layanan yang harus merespons dalam 300 ms untuk 99,9 persen request, dan sengaja memilih availability di atas strong consistency. Replica boleh berbeda isi untuk sementara, dan sistem hanya menjanjikan eventual consistency.
Tabel ringkasan di paper itu sendiri adalah peta terbaik untuk desainnya, karena setiap masalah punya tepat satu teknik. Saya memakainya sebagai kerangka post ini, satu bagian per baris.
| Masalah | Teknik | Manfaatnya |
|---|---|---|
| Partitioning | Consistent hashing | Scalability bertahap |
| High availability untuk write | Vector clock, direkonsiliasi saat read | Ukuran versi tidak bergantung pada laju update |
| Menangani kegagalan sementara | Sloppy quorum dan hinted handoff | High availability dan durability saat sebagian replica tidak terjangkau |
| Pulih dari kegagalan permanen | Anti-entropy dengan Merkle tree | Menyinkronkan replica yang berbeda di background |
| Membership dan deteksi kegagalan | Protokol membership berbasis gossip | Menjaga simetri dan menghindari registry terpusat |
Penyimpanan di tiap node adalah urusan terpisah. Paper menganggap local persistence engine bisa diganti-ganti dan menyebut Berkeley DB Transactional Data Store, BDB Java Edition, MySQL, dan in-memory buffer dengan persistent backing store. Post ini memakai LSM tree untuk lapisan itu, karena itulah yang dipakai kebanyakan penerus modernnya.
Hash key ke sebuah ring lalu berjalan searah jarum jam. Node pertama menjadi coordinator, dan N dikurangi 1 node berikutnya menyimpan replica lainnya. Daftar berurutan itu disebut preference list. Menambah atau menghapus node hanya memindahkan key di sekitarnya, dan itulah alasan adanya ring.
Cara kerja ring dan virtual node: consistent hashing explained
Ada satu detail penting untuk durability. Preference list harus berisi N mesin fisik yang berbeda. Dengan virtual node, penelusuran bisa mendarat di dua token milik server yang sama, sehingga paper melewati posisi milik mesin yang sudah ada di daftar. Tiga replica di satu disk sama dengan satu replica dengan tiga nama.
N adalah jumlah node yang menyimpan salinan sebuah key. W adalah jumlah node yang harus mengonfirmasi write, dan R adalah jumlah yang harus menjawab read. Bila R ditambah W lebih besar dari N, setiap himpunan read berbagi minimal satu node dengan setiap himpunan write, sehingga read menyentuh replica yang melihat write terakhir yang sudah dikonfirmasi. Paper mencatat bahwa latency ditentukan replica paling lambat dari R atau W, jadi keduanya biasanya di bawah N, dan konfigurasi umum yang dilaporkan adalah (3, 2, 2). Program di bawah memeriksa overlap-nya dengan brute force.
// Can a read set of R replicas miss every replica that a write set of W replicas touched?
const N = 3;
function subsets(size: number, from = 0): number[][] {
if (size === 0) return [[]];
const out: number[][] = [];
for (let i = from; i < N; i++) {
for (const rest of subsets(size - 1, i + 1)) out.push([i, ...rest]);
}
return out;
}
function everyReadSeesEveryWrite(W: number, R: number): boolean {
return subsets(W).every((w) => subsets(R).every((r) => r.some((x) => w.includes(x))));
}
for (const [W, R] of [[2, 2], [2, 1], [1, 1]]) {
console.log(`N=${N} W=${W} R=${R} R+W=${R + W} overlap guaranteed: ${everyReadSeesEveryWrite(W, R)}`);
}
// Output (run with tsx):
// N=3 W=2 R=2 R+W=4 overlap guaranteed: true
// N=3 W=2 R=1 R+W=3 overlap guaranteed: false
// N=3 W=1 R=1 R+W=2 overlap guaranteed: falseAritmetikanya untuk N sama dengan 3: dengan W dan R sama-sama 2, jumlahnya 4, lebih besar dari 3, dan program mengonfirmasi bahwa setiap pasangan himpunan beririsan. Dengan W sama dengan 2 dan R sama dengan 1, jumlahnya 3, sehingga read bisa mendarat di satu replica yang dilewati write. Tabel mengubah aritmetika yang sama menjadi pilihan.
| Konfigurasi (N, W, R) | R ditambah W | Apakah read melihat write terakhir yang dikonfirmasi? | Perilaku saat ada replica yang mati |
|---|---|---|---|
| (3, 2, 2) | 4 | Ya, overlap dijamin | Read dan write masing-masing tahan satu replica mati |
| (3, 1, 1) | 2 | Tidak, stale read mungkin terjadi | Paling cepat; write tahan dua replica mati |
| (3, 3, 1) | 4 | Ya, overlap dijamin | Read tahan dua replica mati, tetapi write gagal bila satu replica saja mati |
| (3, 1, 3) | 4 | Ya, overlap dijamin | Write tahan dua replica mati, tetapi read gagal bila satu replica saja mati |
Jaminan overlap hanya berlaku untuk strict quorum pada N node yang sama. Dynamo memakai sloppy quorum: read dan write dikirim ke N node sehat pertama, bukan N node pertama di ring. Saat terjadi kegagalan, R ditambah W lebih besar dari N tidak lagi membuktikan bahwa read melihat write terakhir.
Last-write-wins menempelkan timestamp dan menyimpan yang lebih besar. Cara ini sederhana, bergantung pada jam yang bisa melenceng antar mesin, dan diam-diam membuang salah satu dari dua update yang bersamaan. Paper Dynamo menyebutnya sebagai kebijakan yang dipakai data store saat store itu sendiri yang menyelesaikan konflik. Vector clock justru menyimpan satu counter per coordinator node, dalam bentuk pasangan (node, counter), sehingga dua versi bisa dibandingkan secara kausal.
Jika setiap counter di satu clock minimal sama dengan counter yang sesuai di clock lain, versi itu turunan dari yang lain dan versi lama bisa dibuang. Jika tidak ada yang turunan dari yang lain, kedua versi bersifat concurrent. Store menyimpan keduanya, mengembalikan keduanya saat read, dan menyerahkan merge ke aplikasi. Contoh di paper adalah shopping cart yang di-merge dengan union, karena add to cart tidak boleh sampai hilang.
type Clock = Record<string, number>; // coordinator node -> counter
type Order = "equal" | "descends" | "ancestor" | "concurrent";
function compare(a: Clock, b: Clock): Order {
const nodes = new Set([...Object.keys(a), ...Object.keys(b)]);
let aAhead = false;
let bAhead = false;
for (const n of nodes) {
if ((a[n] ?? 0) > (b[n] ?? 0)) aAhead = true;
if ((b[n] ?? 0) > (a[n] ?? 0)) bAhead = true;
}
if (aAhead && bAhead) return "concurrent"; // neither saw the other: keep BOTH versions
if (aAhead) return "descends"; // a is newer, b can be dropped
if (bAhead) return "ancestor";
return "equal";
}
const v1: Clock = { a: 1 }; // ticket written via node a
const v2: Clock = { a: 2 }; // updated again via a
const v3: Clock = { a: 2, b: 1 }; // one client updates v2 via node b
const v4: Clock = { a: 2, c: 1 }; // another client updates v2 via node c, during a partition
console.log("v2 vs v1:", compare(v2, v1));
console.log("v3 vs v2:", compare(v3, v2));
console.log("v3 vs v4:", compare(v3, v4));
// Output:
// v2 vs v1: descends
// v3 vs v2: descends
// v3 vs v4: concurrent <- a real conflict; return both, let the application mergeBiayanya adalah pertumbuhan ukuran. Paper membatasi ukuran clock dengan menyimpan timestamp di samping tiap pasangan, dan begitu jumlah pasangan mencapai threshold (paper memberi contoh 10), pasangan paling lama dibuang. Paper mengakui hal ini bisa menimbulkan inefisiensi dalam rekonsiliasi, karena sebagian garis keturunan tidak bisa lagi dibuktikan.
Dengan sloppy quorum, coordinator menulis ke N node sehat pertama. Jika replica A mati, salinannya dikirim ke node berikutnya, D, dengan hint yang menyebut A di metadata. D menyimpan replica berhint di local store terpisah dan mengirimkannya ke A setelah A pulih, lalu menghapus salinannya sendiri. Write tetap tersedia, dan paper mencatat cara ini paling baik saat churn membership rendah.
Hint hilang jika D mati sebelum A kembali, jadi replica juga membandingkan data di background. Setiap node menyimpan satu Merkle tree per key range: leaf adalah hash tiap key dan setiap parent adalah hash dari child-nya. Dua replica bertukar root hash. Jika sama, range itu identik, dan jika beda mereka hanya turun ke subtree yang berbeda. Range berisi 1.024 key punya tree sedalam 10 level, karena 2 pangkat 10 adalah 1.024, sehingga menemukan satu key yang berbeda butuh sekitar 10 level kali 2 hash child, kira-kira 20 perbandingan, bukan 1.024.
Paper mencantumkan biaya Merkle tree: saat node bergabung atau keluar, key range berubah dan tree yang terdampak harus dihitung ulang. Rencanakan proses repair dengan memperhitungkan itu, dan jangan anggap anti-entropy gratis hanya karena langkah perbandingannya murah.
Dengan gossip. Di paper, setiap node menghubungi satu peer yang dipilih acak tiap detik, dan kedua node merekonsiliasi riwayat perubahan membership yang tersimpan. Hasilnya setiap node punya pandangan eventually consistent tentang siapa saja yang ada di ring. Deteksi kegagalan juga tetap lokal: node yang tidak bisa menjangkau peer menganggapnya gagal dan mengambil jalur lain, tanpa coordinator yang ditanya.
Perkiraan hitungan menunjukkan mengapa ini scalable. Jika tiap node yang sudah tahu memberi tahu satu node baru per putaran, jumlah node yang tahu paling baik berlipat dua tiap putaran, jadi 1.000 node butuh sekitar 10 putaran, karena 2 pangkat 10 adalah 1.024. Pada satu pertukaran per detik, itu sekitar 10 detik. Penyebaran sebenarnya lebih lambat dari idealnya, jadi anggap ini batas bawah waktu konvergensi, bukan hasil pengukuran.
Gagasan paper LSM-tree adalah menampung write di memori lalu menggabungkannya ke disk dalam batch sekuensial. Dalam istilah node: tulis write ke write-ahead log (WAL), masukkan ke memtable di memori, dan saat memtable penuh, flush sebagai file terurut yang immutable, yaitu SSTable. Read memeriksa memtable, lalu tabel dari yang terbaru ke yang terlama. Delete berupa tombstone, dan compaction menggabungkan tabel. Sketch ini memuat semuanya dalam sekitar 60 baris.
import { appendFileSync, existsSync, readFileSync, writeFileSync, rmSync } from "node:fs";
const TOMBSTONE = "\u0000deleted";
const FLUSH_AT = 3; // entries in the memtable before it becomes an SSTable
class TinyLsm {
private mem = new Map<string, string>();
private sstables: Array<Array<[string, string]>> = []; // newest first, each sorted by key
constructor(private walPath: string) {
if (existsSync(walPath)) {
for (const line of readFileSync(walPath, "utf8").split("\n").filter(Boolean)) {
const [k, v] = JSON.parse(line) as [string, string];
this.mem.set(k, v); // replay: the WAL rebuilds the memtable after a crash
}
}
}
put(key: string, value: string): void {
appendFileSync(this.walPath, JSON.stringify([key, value]) + "\n"); // log first, then memory
this.mem.set(key, value);
if (this.mem.size >= FLUSH_AT) this.flush();
}
delete(key: string): void { this.put(key, TOMBSTONE); } // a delete is just a newer write
get(key: string): string | undefined {
const hit = this.mem.get(key) ?? this.fromTables(key);
return hit === TOMBSTONE ? undefined : hit;
}
private fromTables(key: string): string | undefined {
for (const t of this.sstables) { // newest table wins
const row = t.find(([k]) => k === key);
if (row) return row[1];
}
return undefined;
}
private flush(): void {
this.sstables.unshift([...this.mem.entries()].sort(([a], [b]) => (a < b ? -1 : 1)));
this.mem.clear();
writeFileSync(this.walPath, ""); // data now lives in a table, so the log can be truncated
}
compact(): void { // merge every table: newest value per key, tombstones dropped
const merged = new Map<string, string>();
for (const t of [...this.sstables].reverse()) for (const [k, v] of t) merged.set(k, v);
this.sstables = [[...merged.entries()]
.filter(([, v]) => v !== TOMBSTONE)
.sort(([a], [b]) => (a < b ? -1 : 1))];
}
stats() { return { memtable: this.mem.size, sstables: this.sstables.map((t) => t.length) }; }
}
const wal = "/tmp/tiny-lsm.wal";
rmSync(wal, { force: true });
const db = new TinyLsm(wal);
db.put("wash:101", "basic");
db.put("wash:102", "premium");
db.put("wash:103", "basic"); // third entry: memtable flushes to SSTable 1
db.put("wash:101", "wax"); // the newer version lives in the memtable
db.delete("wash:102"); // a tombstone, not an in-place delete
console.log("after writes ", db.stats(), db.get("wash:101"), db.get("wash:102"));
console.log("after restart ", new TinyLsm(wal).stats(), new TinyLsm(wal).get("wash:101"));
db.put("wash:104", "basic"); // second flush: two SSTables
console.log("before compact", db.stats());
db.compact();
console.log("after compact ", db.stats(), db.get("wash:101"), db.get("wash:102"));
// Output:
// after writes { memtable: 2, sstables: [ 3 ] } wax undefined
// after restart { memtable: 2, sstables: [] } wax
// before compact { memtable: 0, sstables: [ 3, 3 ] }
// after compact { memtable: 0, sstables: [ 3 ] } wax undefinedBaca outputnya sebagai bukti. Setelah write, memtable berisi 2 entri (wash:101 yang lebih baru dan tombstone untuk wash:102) dan satu SSTable berisi 3. Instance baru yang dibangun hanya dari WAL tetap menjawab wax untuk wash:101, yang membuktikan log bisa di-replay. WAL hanya berisi 2 entri karena di-truncate saat flush. Compaction lalu menggabungkan dua tabel berisi 3 baris menjadi satu tabel 3 baris: wash:101 yang lama kalah dari yang baru dan wash:102 yang di-tombstone hilang.
Sketch ini jujur soal apa yang dilewatinya. SSTable disimpan di memori, bukan file, tidak pernah memanggil fsync, dan tidak punya checksum, index, atau Bloom filter. Itulah bagian yang menghabiskan sebagian besar kode engine sungguhan, dan itulah alasan memakai engine yang sudah ada.
Untuk workload ERP di satu VPS, hampir pasti tidak. Store ala Dynamo membayar write availability dengan penanganan konflik dan kerja repair yang tidak pernah diminta Postgres primary plus replica. Sebelum memilihnya, jalani daftar ini secara berurutan.
Aturan yang saya ambil: setiap kotak dalam desain ala Dynamo ada karena kotak sebelumnya memilih availability, dan setiap pilihan meninggalkan tagihan. Replica berbeda isi, jadi butuh versi. Node mati, jadi butuh hint dan repair. Menuliskannya lebih dulu memberi tahu apakah Anda mau membayarnya.
Bacaan terkait