Mencapai Kesepakatan Seluruh Sistem (Konsensus) untuk Database Terdistribusi

Bagian ini adalah jantung dari sistem terdistribusi. Kita akan menjelaskan mengapa konsensus diperlukan dan memberikan deep dive (penyelaman mendalam) ke dalam algoritma Raft, menghubungkan prinsip-prinsipnya secara langsung dengan implementasi toydb.

Mencapai Kesepakatan Seluruh Sistem (Konsensus) untuk Database Terdistribusi.

Kebutuhan akan Konsensus

Dalam sistem terdistribusi, kita mereplikasi data di beberapa mesin (node) untuk mencapai toleransi terhadap kesalahan (fault tolerance). Jika satu node gagal, sistem dapat terus beroperasi menggunakan replika lainnya. Namun, ini menimbulkan masalah baru: bagaimana kita memastikan bahwa semua replika tetap konsisten satu sama lain? Jika klien menulis nilai ‘A’ ke satu replika dan nilai ‘B’ ke replika lain secara bersamaan, keadaan sistem menjadi tidak konsisten.

Masalah menjaga konsistensi mesin keadaan yang direplikasi (replicated state machines) adalah masalah fundamental dalam sistem terdistribusi. Di sinilah Teorema CAP menjadi relevan. Teorema ini menyatakan bahwa dalam sistem terdistribusi, mustahil untuk secara bersamaan memberikan lebih dari dua dari tiga jaminan berikut: Consistency (C), Availability (A), dan Partition Tolerance (P).

• Consistency: Setiap operasi baca menerima data tulis terbaru atau sebuah galat. Semua node melihat data yang sama pada saat yang sama.

• Availability: Setiap permintaan menerima respons (non-galat), tanpa jaminan bahwa respons tersebut berisi data tulis terbaru.

• Partition Tolerance: Sistem terus beroperasi meskipun terjadi pemisahan jaringan (network partition), di mana pesan antara node dapat hilang atau tertunda.

Karena partisi jaringan adalah keniscayaan dalam sistem terdistribusi, toleransi partisi (P) harus diterima. Ini memaksa perancang sistem untuk membuat pilihan antara konsistensi dan ketersediaan. Sistem berbasis Raft, seperti toydb, adalah sistem CP: mereka memprioritaskan konsistensi di atas ketersediaan. Jika terjadi partisi jaringan yang mencegah mayoritas node berkomunikasi, klaster akan menjadi tidak tersedia untuk operasi tulis demi memastikan tidak ada data yang tidak konsisten yang di-commit.

Ketika membahas Teorema CAP, referensi utamanya ada 2, presentasi Brewer¹ pada tahun 2000 adalah yang memperkenalkan konsepnya, dan paper Gilbert dan Lynch² pada tahun 2002 adalah yang membuktikannya secara formal.

Raft: Konsensus untuk Keterpahaman

Algoritma konsensus adalah mekanisme yang digunakan node untuk menyetujui urutan operasi. Meskipun Paxos³⁴ secara historis menjadi standar emas, ia terkenal sulit untuk dipahami. Algoritma Raft⁵ diperkenalkan dengan tujuan utama untuk menjadi alternatif yang lebih mudah dipahami daripada Paxos, tanpa mengorbankan toleransi kesalahan atau performa.

Tujuan desain Raft untuk “keterpahaman” dicapai melalui dua teknik utama :

1. Dekomposisi: Masalah konsensus yang kompleks dipecah menjadi sub-masalah yang relatif independen: Leader Election, Log Replication, dan Safety.

2. Reduksi Ruang Keadaan (State Space Reduction): Raft mengurangi tingkat non-determinisme dan cara-cara di mana log server bisa menjadi tidak konsisten, membuatnya lebih mudah untuk dinalar.

Filosofi desain Raft ini sangat selaras dengan tujuan edukasi toydb. Sinergi ini bukanlah kebetulan; inilah mengapa Raft adalah pilihan yang sangat baik untuk proyek pembelajaran. Dengan mempelajari implementasi Raft di toydb, Anda mendapat manfaat dari desain pedagogis berlapis: implementasi yang berfokus pada pembelajaran dari sebuah algoritma yang dirancang untuk dipelajari.

Lebih jauh tentang Raft, seluruh upaya pembahasan Raft dikumpulkan di GitHub⁶.

Deep Dive: Pemilihan Pemimpin (Leader Election)

Raft menggunakan model kepemimpinan yang kuat. Pada waktu tertentu, sebuah klaster Raft memiliki tepat satu pemimpin (leader). Semua permintaan klien diarahkan ke pemimpin. Setiap node dalam klaster Raft dapat berada dalam salah satu dari tiga keadaan :

• Follower: Secara pasif merespons RPC dari leader dan candidate.

• Candidate: Digunakan selama proses pemilihan untuk memilih leader baru.

• Leader: Menangani semua permintaan klien dan mengelola replikasi log ke para follower.

Waktu dalam Raft dibagi menjadi periode-periode yang disebut term, yang diberi nomor secara berurutan. Setiap term dimulai dengan pemilihan. Jika seorang follower tidak menerima komunikasi (misalnya, pesan heartbeat) dari leader saat ini selama periode waktu yang disebut election timeout, ia mengasumsikan leader telah gagal dan memulai pemilihan baru.

Untuk memulai pemilihan, seorang follower akan:

1. Meningkatkan nomor term saat ini.

2. Bertransisi ke keadaan candidate.

3. Memilih dirinya sendiri.

4. Mengirimkan RPC RequestVote ke semua node lain di klaster.

Seorang candidate memenangkan pemilihan jika ia menerima suara dari mayoritas node dalam klaster. Setelah terpilih, ia menjadi leader dan mulai mengirimkan pesan heartbeat (dalam bentuk RPC AppendEntries kosong) ke semua follower untuk menegaskan otoritasnya dan mencegah pemilihan baru. Untuk mencegah suara terpecah (split votes) di mana beberapa candidate memulai pemilihan pada saat yang sama, Raft menggunakan election timeout yang diacak untuk setiap node.

Deep Dive: Replikasi Log (Log Replication)

Setelah seorang leader terpilih, ia bertanggung jawab untuk melayani permintaan klien. Setiap permintaan berisi perintah yang akan dieksekusi oleh mesin keadaan yang direplikasi. Leader menambahkan perintah tersebut sebagai entri baru ke log-nya.

Kemudian, leader mengirimkan RPC AppendEntries secara paralel ke setiap follower untuk mereplikasi entri tersebut. RPC ini berisi satu atau lebih entri log untuk ditambahkan ke log follower. Ketika seorang follower menerima RPC AppendEntries, ia akan menambahkan entri tersebut ke log-nya dan mengirimkan respons berhasil kembali ke leader.

Sebuah entri log dianggap committed setelah leader mengetahui bahwa entri tersebut telah berhasil direplikasi ke mayoritas node. Setelah sebuah entri di-commit, leader dapat dengan aman menerapkannya ke mesin keadaannya dan mengembalikan hasilnya ke klien.

Leader juga melacak indeks commit tertinggi yang diketahuinya dan menyertakan informasi ini dalam RPC AppendEntries berikutnya, sehingga para follower juga dapat mengetahui entri mana yang telah di-commit dan menerapkannya ke mesin keadaan lokal mereka.

Kita akan membandingkan kedua karakteristik RPC RequestVote dan RPC AppendEntries.

RPCRequestVote

• Dipanggil oleh: Candidate

• Diterima oleh: Semua node lain

• Tujuan: Meminta suara dalam pemilihan.

• Argumen Kunci: term, candidateId, lastLogIndex, lastLogTerm

• Kondisi Berhasil: Penerima belum memilih di term ini DAN log candidate setidaknya sama barunya.

• Kondisi Gagal: term candidate kedaluwarsa ATAU penerima sudah memilih ATAU log candidate tidak cukup baru.

RPCAppendEntries

• Dipanggil oleh: Leader

• Diterima oleh: Semua follower

• Tujuan: Mereplikasi entri log; berfungsi sebagai heartbeat.

• Argumen Kunci: term, leaderId, prevLogIndex, prevLogTerm, entries, leaderCommit

• Kondisi Berhasil: term penerima tidak lebih baru DAN log penerima berisi entri di prevLogIndex dengan prevLogTerm.

• Kondisi Gagal: term leader kedaluwarsa ATAU log penerima tidak cocok di prevLogIndex.

Deep Dive: Mekanisme Keamanan

Raft menyertakan beberapa mekanisme untuk menjamin konsistensi dan keamanan sistem:

• Kelengkapan Pemimpin (Leader Completeness): Properti ini menjamin bahwa setiap leader yang terpilih untuk term tertentu memiliki semua entri yang telah di-commit dari term-term sebelumnya. Hal ini dicapai selama proses pemungutan suara: seorang candidate hanya bisa memenangkan pemilihan jika log-nya “setidaknya sama barunya” dengan log mayoritas pemilih. Ini memastikan bahwa tidak ada entri yang di-commit yang dapat hilang.

• Properti Pencocokan Log (Log Matching Property): Raft menjaga konsistensi log dengan memaksa log para follower untuk meniru log leader. Jika ada ketidakcocokan, leader akan menemukan titik ketidakcocokan terakhir dan menimpa entri-entri yang bertentangan di log follower dengan entri-entri dari log-nya sendiri. Proses ini terjadi secara otomatis melalui RPC AppendEntries.

Penelusuran Kode: Raft di toydb

Analisis ini didasarkan pada struktur repositori toydb dan praktik umum dalam proyek Rust, dengan mempertimbangkan bahwa toydb sengaja menggunakan pendekatan sinkron yang disederhanakan untuk tujuan edukasi.

• Struktur Modul: Logika inti Raft dienkapsulasi dalam modul raft di src/raft/. Namun, server jaringan yang menangani komunikasi antar-node berada di src/server.rs.
  Pemisahan ini secara bersih membedakan antara logika konsensus dan logika transportasi jaringan.

• Definisi Pesan (src/raft/message.rs): Alih-alih mendefinisikan RPC formal, toydb kemungkinan besar menggunakan sebuah enum Message yang komprehensif.
  Enum ini akan memiliki varian untuk setiap interaksi Raft, seperti AppendEntries {... }, RequestVote {... }, dan respons yang sesuai.
  Struct ini dapat diserialisasi dan dideserialisasi (menggunakan serde), yang secara efektif berfungsi sebagai protokol RPC kustom.

• Server Jaringan (src/server.rs): File ini bertanggung jawab untuk mendengarkan koneksi TCP masuk dari node Raft lainnya. Ketika koneksi diterima, ia akan masuk ke dalam loop untuk:

  1. Membaca byte dari stream TCP.

  2. Mendeserialisasi byte tersebut menjadi enum Message.

  3. Meneruskan Message yang telah dideserialisasi ke state machine Raft untuk diproses.

  4. Menerima Message balasan dari state machine, menyerialisasikannya, dan menulisnya kembali ke stream TCP.

• Raft State Machine (src/raft/node.rs): Ini adalah inti dari implementasi Raft. File ini akan berisi struct Node yang memegang semua keadaan Raft (persisten dan volatil) dan enum Role (Follower, Candidate, Leader).
  Fungsi utamanya, seperti step(message: Message), akan berisi match statement besar yang menangani setiap varian dari enum Message.
  Di sinilah logika sebenarnya untuk AppendEntries (memeriksa term, mencocokkan log) dan RequestVote (memeriksa term, memberikan suara) diimplementasikan.

Pendekatan ini sangat pedagogis karena memecah masalah menjadi bagian-bagian yang dapat dikelola: server.rs hanya peduli tentang jaringan dan serialisasi, sementara node.rs hanya peduli tentang logika algoritma Raft.

1. Brewer, E. (2000). Towards Robust Distributed Systems. Presentasi pada Symposium on Principles of Distributed Computing (PODC).

2. Gilbert, S., & Lynch, N. (2002). Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. ACM SIGACT News, 33(2), 51-59.

3. Lamport, L. (1998). The Part-Time Parliament. Digital Equipment Corporation. Diakses pada 4 Oktober 2025, dari https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf

4. Lamport, L. (2001). Paxos Made Simple. Diakses pada 4 Oktober 2025, dari https://lamport.azurewebsites.net/pubs/paxos-simple.pdf

5. Ongaro, D., & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm. Proceedings of the 2014 USENIX Annual Technical Conference (ATC ‘14). Diakses pada 4 Oktober 2025, dari https://web.stanford.edu/~ouster/cgi-bin/papers/raft-atc14.pdf

6. https://raft.github.io/