Belajar System Design - Distributed Consensus: Raft & Paxos

#Pendahuluan

Setelah di episode 10 kita memahami CAP, PACELC, dan berbagai consistency models, pada episode ini kita masuk ke masalah paling fundamental dalam distributed system: bagaimana banyak node sepakat pada satu nilai? Ini adalah masalah consensus — dan tanpa solusi yang benar, distributed system tidak akan bisa bekerja.

Masalah consensus muncul di mana-mana: siapa yang menjadi leader? Apakah write sudah ter-replikasi ke cukup banyak node? Apakah data yang di-read adalah yang terbaru? Paxos dan Raft adalah dua algoritma yang menjawab pertanyaan-pertanyaan ini — dan menjadi fondasi etcd, CockroachDB, TiKV, dan banyak distributed database lainnya.

#Masalah Fundamental

#Apa Itu Distributed Consensus?

Distributed consensus adalah masalah: bagaimana membuat N node mencapai kesepakatan (agreement) pada satu nilai, meskipun beberapa node bisa gagal atau jaringan terputus.

Persyaratan:

1. Agreement: semua node yang survive setuju pada satu nilai.
2. Validity: nilai yang disepakati harus dipilih oleh satu node.
3. Termination: semua node akhirnya mencapai kesepakatan (liveness).

Kemustahilan: di asynchronous network dengan satu Byzantine failure, consensus tidak bisa dicapai (Fischer-Lynch-Paterson). Tapi dengan model partial synchrony atau crash-stop failures, consensus bisa dipecahkan.

#Kapan Dibutuhkan?

#Raft: Algoritma yang Dipahami

Raft dirancang untuk lebih mudah dipahami dari Paxos, dengan outcome yang sama. Digunakan di etcd (Kubernetes backing store), CockroachDB, TiKV, dan HashiCorp Consul.

#Tiga Komponen Raft

#1. Leader Election

Node state: Follower → Candidate → Leader
Timeout: election timeout (randomized 150-300ms)
 
1. Semua node mulai sebagai Follower
2. Follower tidak menerima heartbeat dari Leader → timeout
3. Follower jadi Candidate → request votes dari node lain
4. Candidate dapat majority votes → jadi Leader
5. Leader kirim heartbeat ke semua Follower

Randomized timeout memastikan tidak ada split vote — salah satu Candidate akan menang duluan.

#2. Log Replication

Client → Leader: append entry (command)
Leader → Follower: replicate log entry
Follower → Leader: acknowledge
Leader: setelah majority acknowledge → commit entry
Leader → Client: return success

Log adalah sequence of commands yang identik di semua node. Setelah majority mengakui, entry di-commit dan di-apply ke state machine.

#3. Safety

Raft menjamin:

• Election safety: hanya satu leader per term.
• Leader append-only: leader tidak menghapus atau overwrite entry.
• Log matching: jika dua log punya entry dengan index dan term yang sama, semua entry sebelumnya juga identik.
• Leader completeness: leader harus punya semua committed entry.

#Raft di Dunia Nyata

#Paxos: Foundation yang Kompleks

Paxos (Lamport, 1989) adalah algoritma consensus pertama yang praktis, tapi sangat sulit dipahami dan diimplementasi.

#Basic Paxos

Phase 1 (Prepare):
  Proposer → Acceptors: "prepare(N)" (N = proposal number)
  Acceptors → Proposer: "promise" (jika N lebih tinggi dari yang pernah di-handle)
 
Phase 2 (Accept):
  Proposer → Acceptors: "accept(N, value)"
  Acceptors → Proposer: "accepted" (jika N sesuai promise)

#Multi-Paxos

Basic Paxos hanya consensus untuk satu nilai. Multi-Paxos mengulangi untuk sequence of values — digunakan untuk log replication.

#Paxos vs Raft

#Praktik: Simulasi Leader Election Raft

Mari simulasi bagaimana Raft election bekerja dengan 3 node:

Awal: Node A (Follower), Node B (Follower), Node C (Follower)
 
Step 1: Node A timeout → jadi Candidate (term 1)
Step 2: Node A kirim RequestVote ke B dan C
Step 3: Node B vote untuk A (A punya log yang lebih lengkap)
Step 4: Node C vote untuk A
Step 5: Node A dapat 2/3 votes → jadi Leader (term 1)
Step 6: Node A kirim AppendEntries heartbeat ke B dan C
Step 7: Semua node tahu A adalah Leader
 
Simulasi failure:
Step 8: Node A crash!
Step 9: Node B timeout → jadi Candidate (term 2)
Step 10: Node B kirim RequestVote ke C
Step 11: Node C vote untuk B
Step 12: Node B dapat 2/3 votes → jadi Leader (term 2)
Step 13: Node A recover → lihat term 2 → jadi Follower
 
Log tetap konsisten: semua committed entry ada di A, B, dan C

#Partisi Jaringan dalam Raft

Network partition: A (leader) terisolasi dari B dan C
 
Di partition A: A tetap kirim heartbeat tapi tidak ada response
Di partition B, C: B timeout → election → B jadi leader (term 2)
 
Saat partition heal: A lihat term 2 → mundur jadi follower
Semua committed entry tetap konsisten (sudah majority)

#Penutup

Inti yang harus dibawa pulang:

• Distributed consensus menjawab: bagaimana N node sepakat pada satu nilai.
• Raft: leader election + log replication + safety; lebih mudah dari Paxos; digunakan etcd, CockroachDB, Consul.
• Paxos: foundation historical; kompleks tapi powerful; digunakan Google Spanner, Chubby.
• Simulasi: election timeout → candidate → request votes → majority → leader; partition tolerance lewat term comparison.

Di episode 12 selanjutnya kita akan membahas replication strategies lanjut — leader-follower async vs semi-sync vs sync, multi-leader active-active dengan conflict resolution, dan leaderless (Dynamo-style) quorum read/write. Replication adalah bagaimana data didistribusikan untuk reliability dan performance!