Raft Simulator

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.

Tonton sebuah pemilihan Matikan sebuah aturan
Menghitung jejak…
 Pemilihan yang bersih, diputar langsung dari simulator ini.

Mulai dari mana

Cara kerjanya, singkatnya

  1. 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.

  2. 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.

  3. 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.

n0leader
  • 11
  • 21
  • 32
n1anggota
  • 11
  • 21
  • 32
n2mati
  • 11
  • 21
  • 3—
Baris 3 hanya ada di dua dari tiga komputer — dan itu sudah cukup. Dua dari tiga adalah mayoritas, jadi baris itu sah (committed) meski n2 sedang mati. Begitu n2 hidup lagi, ia akan menyusul sendiri.

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.

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.

  • Election Safety

    Tidak pernah ada dua ketua sekaligus dalam satu putaran.

    At most one leader can be elected in a given term.

  • Leader Append-Only

    Ketua hanya menambah catatan di ujung; ia tidak pernah menghapus catatannya sendiri.

    A leader never overwrites or deletes entries in its log; it only appends new entries.

  • Log Matching

    Kalau dua komputer punya catatan yang sama di satu baris, seluruh catatan di atasnya juga sama.

    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.

  • Leader Completeness

    Catatan yang sudah sah tidak akan pernah hilang dari ketua mana pun sesudahnya.

    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.

  • State Machine Safety

    Tidak akan ada dua komputer yang menjalankan isi berbeda pada baris yang sama.

    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 mengenal Raft

Simulasi deterministik, checker invariant yang tidak berbagi kode dengan algoritmanya, Figure 2 yang diimplementasikan aturan per aturan, dan fuzzing di setiap deploy.

Cara simulator ini dibuat →