Simulator konsensus Raft
Beberapa komputer, satu daftar yang sama.
Layanan besar tidak menyimpan datanya di satu komputer — kalau komputer itu mati, habis sudah. Datanya disimpan di beberapa komputer sekaligus, dan semuanya harus punya daftar catatan yang isinya persis sama. Masalahnya: komputer bisa mati kapan saja, dan jaringan bisa putus di tengah pengiriman. Raft adalah aturan main yang membuat mereka tetap sepakat meski hal-hal itu terjadi.
Bagian yang baru saja Anda baca adalah bagian yang mudah. Yang sulit adalah beberapa aturan kecil di Raft yang terlihat berlebihan — sampai Anda mematikannya. Itulah yang bisa Anda lakukan di sini: matikan satu aturan, lalu tonton jaminan yang dijaganya runtuh di depan mata.
Cara kerjanya, singkatnya
Satu ketua dipilih
Setiap komputer menunggu kabar. Yang paling lama tidak mendengar kabar akan mencalonkan diri dan meminta suara. Begitu lebih dari separuh memilihnya, ia menjadi leader — satu-satunya yang boleh mencatat hal baru.
Catatan disalin ke semua
Setiap catatan baru dikirim leader ke semua anggota. Begitu lebih dari separuh menyimpannya, catatan itu dinyatakan committed: sah, dan tidak boleh berubah lagi selamanya.
Yang tertinggal disusulkan
Komputer yang sempat mati atau terputus akan disamakan catatannya begitu tersambung lagi. Kalau catatannya sempat menyimpang, bagian yang salah ditimpa oleh milik leader.
- 11
- 21
- 32
- 11
- 21
- 32
- 11
- 21
- 3—
Cara membaca gambar
Setiap bentuk adalah satu komputer. Kotak kecil di antaranya adalah pesan yang sedang dalam perjalanan — pesan butuh waktu untuk sampai, dan sebagian tidak pernah sampai.
Leader
Ketua. Satu-satunya yang boleh menerima catatan baru dan menyebarkannya.
Follower
Anggota biasa. Menunggu kabar dari leader dan menyalin catatannya.
Candidate
Sedang mencalonkan diri dan meminta suara untuk menjadi leader.
Mati
Sedang mati. Tidak mengirim dan tidak menerima apa pun.
Mulai dari mana
Tonton satu pemilihan
Lima komputer, tidak ada yang memimpin, lalu satu terpilih. Mulailah dari sini.
Matikan sebuah aturan
Setiap aturan menjaga satu janji. Matikan salah satunya, lalu lihat janjinya gagal.
Figure 8, hidup
Diagram paling terkenal di makalah Raft — di sini ia berjalan, dan catatan yang sudah sah tertimpa.
Lima janji yang tidak boleh dilanggar
Raft berjanji lima hal. Aplikasi ini memeriksa kelimanya setelah setiap peristiwa — bukan di akhir, tapi terus-menerus — dan menyebutkan mana yang gagal begitu ada yang gagal.
Tidak pernah ada dua ketua sekaligus dalam satu putaran.
Election Safety · At most one leader can be elected in a given term.
Ketua hanya menambah catatan di ujung; ia tidak pernah menghapus catatannya sendiri.
Leader Append-Only · A leader never overwrites or deletes entries in its log; it only appends new entries.
Kalau dua komputer punya catatan yang sama di satu baris, seluruh catatan di atasnya juga sama.
Log Matching · If two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index.
Catatan yang sudah sah tidak akan pernah hilang dari ketua mana pun sesudahnya.
Leader Completeness · If a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms.
Tidak akan ada dua komputer yang menjalankan isi berbeda pada baris yang sama.
State Machine Safety · If a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.
Untuk yang sudah kenal Raft
Simulator Raft yang bisa Anda rusak dengan sengaja. Simulasi diskret deterministik, pemeriksaan invariant keamanan yang berjalan terus, dan mode ablasi yang mematikan satu per satu aturan Raft supaya jaminan yang dijaganya benar-benar terlihat gagal.
Karya terdahulu
RaftScope sudah ada, kualitasnya bagus, dan ditulis oleh penulis makalah Raft sendiri. Ia adalah visualiser Raft yang kanonis — kalau Anda ingin melihat Raft berjalan, mulailah dari sana. The Secret Lives of Data juga penjelasan yang baik.
Yang ditambahkan proyek ini
Bukan pengganti keduanya. Kontribusinya sempit: ablasi dan pemeriksaan invariant. RaftScope menunjukkan mekanismenya; di sini Anda mematikan sebuah aturan lalu menonton properti keamanan yang dijaganya runtuh, sementara lima indikator invariant menyebutkan mana yang gagal dan mengapa.
Sumber normatif
Ongaro & Ousterhout, In Search of an Understandable Consensus Algorithm (USENIX ATC 2014), versi extended — terutama Figure 2. Setiap aturan di lib/raft menyebutkan nomor figure dan rule yang diimplementasikannya.