Posisi Konsensus

Raft dan Paxos pada tingkat konsep serta kapan sistem nyata menuntut konsensus.

Daftar isi

Topik ini menempatkan konsensus pada porsinya yang tepat dalam desain sistem terdistribusi. Pembahasan dimulai dari masalah yang diselesaikan konsensus, dilanjutkan dengan gambaran konseptual Raft dan Paxos beserta matematika kuorum mayoritas, dan diakhiri pertimbangan kapan sistem nyata memang menuntut konsensus serta kapan biayanya tidak sebanding. Tidak ada implementasi yang ditulis, karena tujuan topik ini adalah intuisi yang menopang keputusan arsitektur.

Masalah yang diselesaikan konsensus#

Konsensus adalah masalah membuat sekelompok node menyepakati satu nilai dari usulan-usulan yang mungkin berbeda. Pada sistem data, nilai yang disepakati biasanya berupa urutan event, sehingga hasilnya berupa log replikasi yang identik di semua node yang berpartisipasi. Algoritma konsensus harus memenuhi tiga sifat: kesepakatan bahwa tidak ada dua node menerima keputusan yang berbeda, validitas bahwa keputusan diambil dari usulan yang benar-benar diajukan, dan penghentian bahwa keputusan akhirnya tercapai selama mayoritas node masih hidup.

Masalah ini sulit justru karena kegagalan tidak pernah bersih. Pesan dapat tertunda tanpa batas, node dapat mati lalu kembali dengan keadaan lama, dan tidak ada jam bersama yang dapat dipercaya untuk memutuskan urutan. Tanpa protokol yang dirancang khusus, dua kelompok node dapat masing-masing memilih pemimpin dan menerima tulisan yang tidak pernah bersatu, keadaan yang disebut otak terbelah. Konsensus menyelesaikannya dengan memastikan hanya satu kelompok yang dapat membuat kemajuan pada satu waktu, yaitu kelompok yang memegang mayoritas.

Raft dan Paxos pada tingkat konsep#

Paxos menyelesaikan masalah itu dengan dua fase pada peran proposer dan acceptor. Fase pertama membuat acceptor berjanji tidak menerima usulan dengan nomor yang lebih lama, dan fase kedua meminta acceptor menerima satu nilai tertentu. Nomor usulan yang meningkat memastikan dua mayoritas tidak pernah beririsan pada nilai yang bertentangan tanpa salah satunya mengetahui nilai yang lain, sehingga keputusan yang sudah diterima mayoritas tidak pernah ditimpa. Paxos membuktikan bahwa protokolnya benar, tetapi bentuk aslinya dikenal sulit diterapkan secara langsung.

Raft menyusun idenya menjadi tiga mekanisme yang lebih mudah diikuti. Setiap node menjalankan leader election dengan istilah (term) yang meningkat, pemimpin yang terpilih menerima seluruh tulisan dari klien, dan tulisan dinyatakan berkomitmen setelah tersalin ke mayoritas node. Bila pemimpin mati, istilah baru memilih penggantinya, dan log mayoritas yang paling mutakhir menang. Konsep log, istilah, dan mayoritas inilah yang perlu dipegang, sedangkan detail pesannya ada di spesifikasi kedua algoritma.

Kedua algoritma bertumpu pada kuorum mayoritas, dan ukurannya dapat dihitung untuk setiap ukuran klaster. Tulisan berkomitmen bila tersalin ke $\lfloor n/2 \rfloor + 1$ node, sehingga dua mayoritas dari klaster yang sama selalu beririsan paling tidak pada satu node. Node yang beririsan itulah yang menjamin keputusan lama tidak hilang. Simulasi berikut menghitung kuorum dan toleransi kegagalannya.

python kuorum.py

# Perhitungan quorum mayoritas untuk ukuran klaster ganjil.
# Tulisan berkomitmen bila tersalin ke mayoritas node.

for n in (3, 5, 7):
    mayoritas = n // 2 + 1
    toleransi = n - mayoritas
    print(f"n = {n}: mayoritas = {mayoritas}, "
          f"node gagal yang masih ditoleransi = {toleransi}")

print()
print("Dua mayoritas dari klaster yang sama selalu beririsan:")
lama = {1, 2}
baru = {2, 3}
print(f"mayoritas lama {lama} dan mayoritas baru {baru} "
      f"beririsan di {lama & baru}")

text Keluaran

n = 3: mayoritas = 2, node gagal yang masih ditoleransi = 1
n = 5: mayoritas = 3, node gagal yang masih ditoleransi = 2
n = 7: mayoritas = 4, node gagal yang masih ditoleransi = 3

Dua mayoritas dari klaster yang sama selalu beririsan:
mayoritas lama {1, 2} dan mayoritas baru {2, 3} beririsan di {2}

Tabel keluaran memperlihatkan tradeoff yang pasti: setiap tambahan dua node menambah satu kegagalan yang ditoleransi, tetapi juga menambah jumlah node yang harus mengonfirmasi setiap tulisan. Baris terakhir memperlihatkan sifat beririsan yang menjadi fondasi kebenarannya, yaitu keputusan yang diterima mayoritas lama pasti dilihat oleh mayoritas baru.

Kapan sistem menuntut konsensus#

Konsensus dibutuhkan ketika satu kebenaran harus dipertahankan lintas partisi dengan konsistensi linier. Kasus yang paling umum adalah leader election untuk penulis tunggal, alokasi tugas yang tidak boleh dikerjakan dua kali, metadata konfigurasi yang dibaca seluruh klaster, dan layanan lock yang menuntut kebenaran sebagaimana dibahas pada topik Lock Terdistribusi. Untuk kebutuhan ini, biaya kuorum terasa wajar karena frekuensinya rendah dan akibat kegagalannya besar.

Biayanya nyata dan harus dihitung sebelum memutuskan. Setiap tulisan menunggu konfirmasi mayoritas, sehingga latensinya minimal sebesar rute ke node tercepat yang membentuk mayoritas. Apabila mayoritas tidak tercapai, seluruh kelompok konsensus berhenti melayani tulisan, termasuk sisi yang sisa node-nya sehat. Konsensus juga tidak menggantikan kebutuhan di tempat lain: sumber daya di luar log konsensus, misalnya penyimpanan berkas yang dituju pemegang lock, tetap memerlukan pemeriksaan fencing token sendiri.

Kesalahan umum#

Kesalahan pertama adalah menyamakan replikasi kuorum dengan konsensus. Menulis ke mayoritas saja belum menyelesaikan sifat kesepakatan, karena dua usulan yang bertentangan masih perlu diurutkan, dan itulah yang diselesaikan fase serta istilah pada protokol. Perbaikannya adalah menggunakan algoritma konsensus yang lengkap, bukan menyusun kuorum sendiri untuk kebutuhan kebenaran.

Kesalahan kedua adalah memasang kelompok konsensus berukuran genap, misalnya dua node. Mayoritas dari dua node adalah dua, sehingga toleransi kegagalannya nol dan seluruh biaya konsensus tidak membawa manfaat apa pun. Perbaikannya adalah ukuran ganjil tiga, lima, atau tujuh sesuai tabel keluaran simulasi.

Kesalahan ketiga adalah menganggap konsensus membuat semua operasi menjadi linier secara otomatis. Pembacaan pada Raft tetap memerlukan pengakuan tambahan atau pembacaan lewat pemimpin, dan tanpa itu pembacaan bisa menyentuh log yang belum berkomitmen. Perbaikannya adalah menyebut tingkat konsistensi yang benar-benar diberikan oleh implementasi yang dipilih, bukan asumsi dari namanya.

Ringkasan#

Konsensus menghasilkan satu keputusan yang disepakati, biasanya berupa log replikasi, dengan sifat kesepakatan, validitas, dan penghentian selama mayoritas hidup.
Raft dan Paxos bertumpu pada kuorum mayoritas $\lfloor n/2 \rfloor + 1$ , dan dua mayoritas selalu beririsan sehingga keputusan lama tidak pernah hilang.
Konsensus dibutuhkan untuk kebenaran lintas partisi seperti penulis tunggal dan lock kebenaran, dengan biaya latensi kuorum dan berhentinya saat mayoritas hilang.

Referensi#

In Search of an Understandable Consensus Algorithm — raft.github.io — Makalah Raft yang menjabat leader election, istilah, dan replikasi log dengan mayoritas.
Paxos Made Simple — Leslie Lamport — Ringkasan Paxos oleh perumusnya dengan dua fase proposer dan acceptor.