Raft & Paxos Uzlaşması: Lider Seçimleri, Dönem Epochları & Durum Makinesi Replikasyonu

Yönetici Özeti

Çoğaltılmış durum makineleri (Replicated State Machines), güçlü tutarlı dağıtık altyapıların temel taşıdır. Bağımsız düğümler kümesinin tamamen aynı deterministik durum geçişleri sırasını çalıştırmasını sağlayarak, kümenin tek bir hataya dayanıklı sistem gibi davranmasını mümkün kılar. Ongaro ve Ousterhout’un Raft protokolü, uzlaşmayı lider seçimi, log çoğaltma ve güvenlik kuralları olmak üzere anlaşılır alt problemlere ayırmıştır.

1. Quorum Formülü

Bir Raft kümesinin $F$ adet düğüm çökmesine dayanabilmesi için en az $2F + 1$ düğüme sahip olması gerekir. Lider seçmek veya bir log kaydını commit etmek için gereken asgari çoğunluk (quorum) $Q$: $$Q = \left\lfloor \frac{N}{2} \right\rfloor + 1$$ 5 düğümlü bir kümede ($N=5$), $F=2$ çökme tolere edilebilir ve $Q=3$ düğüm gereklidir. Herhangi iki $Q$ büyüklüğündeki quorum kümesi en az bir ortak düğümde kesişir; bu da yeni liderin önceki tüm commit edilmiş kayıtları mutlaka görmüş olmasını garanti eder.

2. Raft Lider Seçimi ve Dönem Epochları

• Rastgele Seçim Zamanlayıcıları (150ms - 300ms): Birden fazla adayın aynı anda seçime başlamasını ve bölünmüş oy kilitlenmelerini (split-vote) engeller.
• Pre-Vote Eklentisi: Adaylar dönem numarasını artırmadan önce hafif bir Pre-Vote yoklaması yapar. Çoğunluğu sağlayamayacak durumdaysalar kümeyi gereksiz yere seçim döngüsüne sokmazlar.
• Lider Eksiksizlik İlkesi: Bir takipçi, adayın logu kendi logundan daha eskiyse oy vermeyi reddeder ($ ext{Dönem}{aday} < ext{Dönem}{takipçi}$ veya $ ext{İndeks}{aday} < ext{İndeks}{takipçi}$).

3. Fencing Tokenları: Zombi Liderlerin Engellenmesi

Bir ağ bölünmesi lideri geçici olarak izole ettiğinde, lider kendisini hala geçerli sanabilir (zombi lider). Bu sırada kümenin geri kalanı daha yüksek bir dönem numarasıyla yeni bir lider seçmiştir. Fencing tokenları (monotonik artan dönem sayıları) her depolama çağrısına eklenir:

İstemci -> Eski Lider (Dönem 5, Token: 5) -> Depolama
Yeni Lider Seçildi (Dönem 6, Token: 6) -> Depolama Dönem 5 isteklerini FENCING_TOKEN_STALE ile reddeder