Saya mengimplementasikan algoritma konsensus Raft (ikon algoritma terdistribusi) dengan Python. Implementasinya cukup buruk! Tapi juga (kurang lebih) benar.
Berikut beberapa catatan yang ingin saya bagikan kepada siapa pun yang tertarik mencoba tantangan serupa.
Setelah menjalaninya, menurut saya inilah sumber rujukan yang paling berguna untuk mempelajari Raft dan mengimplementasikannya dengan benar.
- Makalah Raft (baca hingga bagian 5 dan sering-seringlah merujuk ke gambar 2)
- Panduan Raft untuk Mahasiswa
- salah satu implementasi Raft yang paling banyak digunakan
- kloning repositorinya, baca sekilas
raft.go, lalu berdialoglah dengan LLM untuk memahami basis kode dan keputusan desainnya
- kloning repositorinya, baca sekilas
- Seri artikel blog Eli Bendersky
Saya menyarankan untuk meluangkan sekitar satu jam membaca makalahnya terlebih dahulu, lalu membuat kerangka kode untuk server UDP atau TCP yang membaca byte yang masuk dan menambahkannya ke sebuah array. Setelah itu, saya mengikuti implementasi Eli, menambahkan fitur ke implementasi Raft saya dengan urutan yang sama.
Setelah mekanisme yang tampak seperti pemilihan pemimpin berhasil berjalan, saya mulai mencari bug dan kekeliruan dalam pemahaman saya tentang algoritma tersebut. Saya bolak-balik merujuk ke panduan untuk mahasiswa, Gambar 2 dalam makalah Raft, dan implementasi saya, sambil memikirkan dengan cermat bagian mana dari implementasi saya yang sama (atau berbeda). Saya juga banyak menggunakan LLM untuk meninjau kode ini, dengan memasukkan materi dari sumber-sumber di atas ke dalam konteksnya.
Ulangi proses di atas untuk replikasi log, persistensi, dan seterusnya.
soal implementasi
Saya membuat beberapa pilihan desain untuk menyederhanakan implementasi saya. Tanpa urutan tertentu:
- setiap node berjalan dan memproses pesan dalam satu thread
- gunakan "jam logis" untuk melacak "waktu" lokal pada sistem (misalnya, panggil
tick()dan naikkan nilai penghitung lokal di setiap node alih-alih menggunakan waktu sistem) - buat implementasinya "ruwet" dengan menempatkan semuanya dalam satu file, misalnya parsing data jaringan, penyimpanan/persistensi, algoritma inti Raft, dan utilitas/perintah untuk mengendalikan node itu sendiri
2 tampaknya merupakan pilihan desain yang masuk akal dan benar (jam logis memang digunakan dalam implementasi etcd). 3 bisa dibilang lebih baik untuk pembelajaran/pengajaran. Praktis kalau semuanya ada dalam satu file sehingga Anda bisa melihatnya sekaligus, dan Anda pun punya implementasi yang mudah dibongkar untuk melihat abstraksi mana yang paling cocok dengan algoritma tersebut.
Bagi saya, pilihan 1 agak keterlaluan. Pilihan ini memang membuat implementasinya jauh lebih sederhana (Anda tidak perlu terlalu khawatir tentang deadlock dan pembaruan atomik pada status internal node), tetapi hasilnya pun tidak sepenuhnya bisa disebut Raft. Untuk implementasi pertama, rasanya ini tidak masalah. Algoritmanya sudah cukup kompleks, dan menurut saya Anda akan lebih memilih menghabiskan waktu untuk menelusuri kesalahan logika dalam algoritma inti Raft daripada berkutat dengan mutex.
Menurut saya, mengimplementasikan Raft dengan cara ini bisa dianggap sebagai proyek berdurasi ~30 jam. Pembacaan awal makalah Raft dan peninjauan materi terkait seharusnya memerlukan beberapa jam. Saya mengerjakan sebagian besar kodenya dalam ~3 hari selama liburan, dengan mengutak-atik kode sekitar 6-8 jam/hari. Saya masih perlu merapikan dan meningkatkan beberapa hal (misalnya memperbaiki sejumlah bug yang sulit dideteksi) dalam implementasi yang ada, yang mungkin membutuhkan setengah hari kerja lagi.
Secara keseluruhan, lumayan juga untuk memahami salah satu algoritma inti yang menopang begitu banyak infrastruktur.