Jawaban singkat untuk pertanyaan yang paling sering diajukan pembaca tentang topik ini.
Cara kerja leader election di distributed systems: lease Postgres dengan fencing epoch, alternatif Redis dan etcd, Lease Kubernetes, dan split-brain.
Matthews Wong
Software Engineer
Ringkasan Utama
Leader election memastikan hanya satu node yang menjalankan pekerjaan yang tidak boleh berjalan dua kali, seperti singleton job atau primary database. Desain paling sederhana yang aman adalah lease: row atau key dengan batas waktu yang terus diperpanjang leader, ditambah fencing token yang naik setiap pergantian sehingga write dari leader lama ditolak.
Jalankan aplikasi NestJS sebagai dua replika Docker, bukan satu, dan job malam yang menyapu invoice belum dibayar diam-diam berjalan dua kali. Tidak ada yang crash. Kedua salinan membaca row yang sama, keduanya mengirim pengingat yang sama, dan pelanggan menerima dua pesan.
Post ini menjawab pertanyaan di balik bug itu: bagaimana leader election bekerja di distributed systems? Kita bangun lease yang bisa dijalankan di Postgres dengan output psql asli, membandingkannya dengan Redis, etcd, dan objek Lease Kubernetes, lalu menghabiskan sebagian besar waktu pada bagian yang sering dilewati: apa yang terjadi saat leader lama tidak tahu dirinya sudah digantikan. Sumbernya adalah esai Kleppmann tentang distributed locking, dokumentasi Kubernetes dan etcd, referensi Redis SET, dan paper Raft.
Sebagian pekerjaan hanya benar jika dikerjakan satu pihak pada satu waktu. Menjalankannya di semua node bukan redundansi, melainkan duplikasi dengan side effect. Tiga kasus umum:
Leader election adalah protokol yang memilih satu node itu, memberi tahu semua node lain siapa orangnya, dan memilih pengganti saat ia hilang. Bagian sulitnya bukan memilih, tetapi mengganti, karena node yang tidak bisa dihubungi bisa saja mati, atau hanya lambat, dan cluster tidak bisa membedakannya. Saya pernah membahas versi database dari masalah ini di post replication, dan sketsa leader berbasis advisory lock di post desain distributed job scheduler; post ini masuk lebih dalam dari keduanya.
Lease adalah lock dengan tanggal kedaluwarsa. Sebuah node menulis namanya ke tempat bersama bersama dengan deadline, dan ia tetap jadi leader hanya selama terus memajukan deadline itu. Jika berhenti, deadline lewat dan siapa pun boleh mengambil alih. Expiry inilah yang membuat lock tahan terhadap holder yang crash. Tempatnya bisa berupa row database, key Redis, atau consensus store:
| Tempat lease disimpan | Cara kedaluwarsa | Yang perlu diwaspadai |
|---|---|---|
| Row Postgres | Kolom expires_at dibandingkan dengan now() milik database | Hanya satu clock, dan kolom epoch memberi fencing token tanpa biaya tambahan |
| Advisory lock Postgres | Dilepas saat session berakhir, tanpa deadline | Node yang terjeda tapi masih terhubung tetap memegang lock, dan tidak ada token |
| Redis SET NX PX | Key kedaluwarsa setelah PX milidetik | Cepat dan sederhana, tetapi tanpa fencing token dan TTL berjalan di clock Redis |
| etcd, ZooKeeper, Consul | Lease atau session dengan TTL yang dijaga client lewat keepalive | Berbasis consensus dan berurutan, tetapi berupa cluster terpisah yang harus dioperasikan |
Referensi Redis mendokumentasikan bentuk minimalnya: SET dengan NX (hanya jika key belum ada) dan PX (kedaluwarsa dalam milidetik), lalu menyarankan menyimpan token acak dan melepas lock dengan script yang memeriksa token dulu, supaya client yang terlambat tidak menghapus key milik client yang lebih baru. Halaman yang sama menyebut pola SET sederhana ini kurang disarankan dibanding Redlock, posisi yang dibantah Kleppmann, dan itu tema bagian berikutnya.
# Redis: acquire. NX = only if absent, PX = expire in milliseconds.
SET lock:invoice-sweeper node-a-7f3c NX PX 15000
# Redis: release. Compare the token first, or you delete someone else's lock.
# (Lua script, run with EVAL ... 1 lock:invoice-sweeper node-a-7f3c)
if redis.call("get", KEYS[1]) == ARGV[1] then
return redis.call("del", KEYS[1])
else
return 0
endUntuk stack yang sudah punya Postgres, seperti NestJS dan Postgres di satu VPS, tabel dengan empat kolom sudah cukup menjadi coordination service. Triknya adalah satu UPDATE yang WHERE-nya menyatakan siapa yang boleh mengambil lease. Postgres mengunci row, jadi dua node yang berlomba pada statement yang sama tidak mungkin keduanya cocok. Kolom epoch naik satu pada setiap pengambilalihan dan tidak pernah pada perpanjangan; angka itulah fencing token.
CREATE TABLE leader_lease (
name text PRIMARY KEY,
holder text,
epoch bigint NOT NULL DEFAULT 0, -- the fencing token
expires_at timestamptz NOT NULL DEFAULT '-infinity'
);
INSERT INTO leader_lease (name) VALUES ('invoice-sweeper');import { Pool } from "pg";
const pool = new Pool({ connectionString: process.env.DATABASE_URL });
const NAME = "invoice-sweeper";
const LEASE_SECONDS = 15;
const TICK_MS = 5_000; // one third of the lease: two missed ticks are survivable
const GIVE_UP_MS = 10_000; // stop leading before a rival can legally take over
// Compare-and-swap: the WHERE clause is the whole election.
// Only one concurrent UPDATE can match, because Postgres re-checks the
// predicate after taking the row lock.
const ACQUIRE = "UPDATE leader_lease SET holder = $2, epoch = epoch + 1, " +
"expires_at = now() + make_interval(secs => $3) " +
"WHERE name = $1 AND (holder IS NULL OR holder = $2 OR expires_at < now()) " +
"RETURNING epoch";
// Renewal must NOT bump the epoch, and must name the epoch we believe we hold.
const RENEW = "UPDATE leader_lease SET expires_at = now() + make_interval(secs => $3) " +
"WHERE name = $1 AND holder = $2 AND epoch = $4 AND expires_at > now() " +
"RETURNING epoch";
export function runElection(
nodeId: string,
lead: (epoch: number, signal: AbortSignal) => Promise<void>,
): () => void {
let epoch: number | null = null;
let lastRenewOk = 0;
let abort = new AbortController();
const stepDown = () => {
epoch = null;
abort.abort(); // the job must observe this signal and stop
abort = new AbortController();
};
const tick = async () => {
try {
if (epoch === null) {
const r = await pool.query(ACQUIRE, [NAME, nodeId, LEASE_SECONDS]);
if (r.rowCount === 1) {
epoch = Number(r.rows[0].epoch); // bigint arrives as a string
lastRenewOk = Date.now();
void lead(epoch, abort.signal);
}
return;
}
const r = await pool.query(RENEW, [NAME, nodeId, LEASE_SECONDS, epoch]);
if (r.rowCount === 1) lastRenewOk = Date.now();
else stepDown(); // someone else holds a newer epoch
} catch {
// Database unreachable: we cannot prove we still lead. Stop on OUR clock
// before the lease can expire on the database's clock.
if (epoch !== null && Date.now() - lastRenewOk > GIVE_UP_MS) stepDown();
}
};
const timer = setInterval(tick, TICK_MS);
void tick();
return () => {
clearInterval(timer);
if (epoch !== null) stepDown();
};
}Saya menjalankan statement persis seperti ini di psql pada PostgreSQL 16.15 lokal, dengan node-a dan node-b sebagai dua instance aplikasi. Berikut outputnya, dipangkas ke baris hasil:
-- 1. node-a acquires the empty lease
holder | epoch | live
--------+-------+------
node-a | 1 | t
-- 2. node-b tries while node-a holds it
holder | epoch
--------+-------
(0 rows)
-- 3. node-a renews (same epoch)
holder | epoch
--------+-------
node-a | 1
-- (expiry forced with: UPDATE leader_lease SET expires_at = now() - interval '1 second')
-- 4. node-b takes over after expiry
holder | epoch
--------+-------
node-b | 2
-- 5. node-a wakes up and renews with its stale epoch 1
holder | epoch
--------+-------
(0 rows)Langkah 2 adalah election yang bekerja: UPDATE milik node-b cocok dengan nol row karena lease node-a masih hidup. Langkah 5 adalah bagian terpenting. node-a, yang bangkit dengan keyakinan lamanya, mencoba memperpanjang epoch 1 dan cocok dengan nol row, jadi ia tahu sudah digantikan pada tick berikutnya dan tidak lanjut sebagai leader kedua. Loop TypeScript mengubah nol row menjadi stepDown().
Split-brain berarti dua node sama-sama yakin dirinya leader. Lease mengurangi kemungkinannya tetapi tidak bisa menghilangkannya, karena leader memeriksa lease, lalu mengerjakan pekerjaan, dan jeda di antara dua momen itu tidak terbatas. Contoh Kleppmann adalah client yang memegang lock, lalu terhenti oleh garbage collection pause yang panjang, bangun setelah lease-nya kedaluwarsa dan menulis ke storage seolah tidak terjadi apa-apa. Ia menunjukkan bahwa memeriksa expiry tepat sebelum write tidak menolong, karena pause bisa menyerang di titik mana pun.
Solusinya adalah fencing token: angka yang naik setiap kali lock diberikan. Client mengirimnya bersama setiap write dan storage menolak write yang tokennya lebih rendah dari yang pernah dilihat. Pada skema di atas, epoch adalah angka itu. Syarat utamanya, pengecekan harus berada di dalam resource yang dilindungi, dalam statement yang sama dengan write, bukan di kode leader sendiri:
CREATE TABLE sweep_state (id int PRIMARY KEY, last_epoch bigint NOT NULL, note text);
INSERT INTO sweep_state VALUES (1, 2, 'written by node-b');
-- Wrong: a stale leader (epoch 1) writes unconditionally and wins by arriving last.
UPDATE sweep_state SET note = 'stale write by node-a' WHERE id = 1;
-- Right: the write carries its epoch and the resource refuses anything older.
UPDATE sweep_state SET last_epoch = 1, note = 'stale write by node-a'
WHERE id = 1 AND last_epoch <= 1 RETURNING *;
-- (0 rows) rejected: the table has already seen epoch 2
UPDATE sweep_state SET last_epoch = 2, note = 'sweep by node-b'
WHERE id = 1 AND last_epoch <= 2 RETURNING *;
-- id | last_epoch | note
-- ----+------------+-----------------
-- 1 | 2 | sweep by node-bLease saja bukan mutual exclusion. Jika hal yang dilindungi tidak bisa membandingkan token, misalnya API email eksternal, Anda hanya punya pengecualian best-effort, jadi buat aksinya idempotent juga. Kleppmann menyebut lock yang dipakai hanya untuk efisiensi boleh longgar, tetapi lock untuk kebenaran butuh token.
Lease bergantung pada waktu, dan waktu adalah hal paling tidak andal di sebuah cluster. Kleppmann mencatat bahwa expiry Redis bergantung pada system clock yang bisa melompat, sehingga key bisa kedaluwarsa lebih cepat atau lambat dari rencana. Process pause lebih buruk karena tidak butuh kerusakan clock sama sekali. Berikut timeline contoh dengan lease 15 detik dan stall 20 detik:
Konstanta waktunya adalah aritmetika, bukan keberuntungan. Dengan lease 15 detik dan tick tiap 5 detik, leader punya tiga kesempatan per jendela lease (pada detik 0, 5, dan 10). Jika 10 detik tanpa perpanjangan sukses, ia turun sendiri, sehingga tersisa jeda 5 detik sebelum rival boleh mengambil alih pada detik 15. Failover butuh 15 sampai 20 detik pada kasus terburuk, karena lease harus kedaluwarsa dulu dan rival baru sadar pada tick 5 detik berikutnya. Pada versi Postgres, skew antar server aplikasi tidak berpengaruh, karena setiap deadline ditulis dan dibandingkan dengan now() milik database sendiri.
Pilih durasi lease dari waktu failover yang bisa Anda toleransi, lalu set tick perpanjangan sepertiganya. Lease lebih pendek membuat failover lebih cepat tetapi membuat round trip database yang lambat terlihat seperti leader yang mati.
Satu row di satu Postgres hanya seandal Postgres itu. Jika database mati, tidak ada yang bisa memperpanjang, sehingga semua leader turun; ini aman tetapi pekerjaan berhenti. Consensus store menyimpan state di beberapa replica dan menyepakati urutan. Dokumentasi etcd menjelaskan lease yang punya time to live dan dijaga client lewat keepalive, key yang ikut mati bersama lease-nya, counter revision seluruh store yang naik tiap perubahan, dan transaksi yang memberi compare-and-swap. Counter revision itu adalah fencing token siap pakai, dan Kleppmann merekomendasikan sistem consensus seperti ZooKeeper ditambah fencing token setiap kali lock melindungi kebenaran data.
Di bawah sistem-sistem itu ada leader election mereka sendiri. Algoritma bully klasik membiarkan node hidup dengan ID tertinggi menang, dan mengasumsikan Anda bisa mendeteksi siapa yang hidup dengan andal. Raft memilih leader memakai term dan election timeout acak, dan kandidat butuh suara mayoritas. Nomor term berperan sama seperti epoch kita: pesan dengan term lebih lama diabaikan. Paper Raft adalah sumber primernya, dan mekanisme consensus layak punya post sendiri.
Aturan praktis saya: jika Anda sudah menjalankan satu Postgres dan failover 20 detik tidak masalah, pakai row. Jika Anda sudah mengoperasikan etcd atau ZooKeeper, atau leader menentukan siapa yang menulis ke primary database, pakai consensus store, karena di sana biaya dua leader adalah kehilangan data.
Kubernetes memakai pola lease di control plane-nya sendiri. Halaman Leases mencantumkan leader election sebagai salah satu kegunaan objek Lease: pada setup high availability, kube-controller-manager dan kube-scheduler menjalankan beberapa instance sementara hanya satu yang aktif, dan controller buatan Anda bisa melakukan hal sama. Referensi kube-controller-manager mencantumkan parameter dan default-nya: lease duration 15 detik, renew deadline 10 detik, dan retry period 2 detik, dengan leases sebagai tipe lock.
# kube-controller-manager defaults, from the Kubernetes reference
kube-controller-manager \
--leader-elect=true \
--leader-elect-lease-duration=15s \
--leader-elect-renew-deadline=10s \
--leader-elect-retry-period=2s \
--leader-elect-resource-lock=leases
# The lock object lives in the coordination.k8s.io/v1 API group:
apiVersion: coordination.k8s.io/v1
kind: Lease
spec:
holderIdentity: <pod-name>_<uuid>
leaseDurationSeconds: 15
renewTime: <timestamp>Baca default itu sebagai aritmetika yang sama seperti tadi. Renew deadline 10 detik lebih pendek dari lease 15 detik, jadi leader berhenti memimpin sebelum rival boleh mengambil alih, dan retry tiap 2 detik memberinya sekitar lima percobaan di jendela itu. Halaman Lease juga menyarankan menamai lease sesuai komponen Anda, misalnya example-foo, supaya dua operator tidak bertabrakan pada satu objek.
Telusuri berurutan dan berhenti di yang pertama cocok:
Leader adalah lease, bukan gelar: ia harus diperpanjang, bisa hilang tanpa disadari pemegangnya, sehingga setiap write butuh token yang diperiksa oleh resource itu sendiri. Bangun lease di store yang sudah Anda jalankan, berhenti memimpin berdasarkan clock sendiri sebelum lease berakhir, dan pakai consensus store hanya saat dua leader akan merugikan data Anda.
Sumber dan bacaan lanjutan