Olasılıksal ve dağıtık sistemler · 50 / 53
Paxos, Raft ve çoğunlukla anlaşma
Anla → iz sür → uygula → gerekçelendir
2 dk okuma · uygulama için ayrıca zaman ayırConsensus, hata ve gecikmeler altında katılımcıların değer/log üzerinde anlaşmasını sağlar. Safety “farklı committed değerler oluşmasın”; liveness “uygun koşullarda ilerlesin” demektir. Network partition sırasında çoğunluğu olmayan tarafın yazı ilerlemesini durdurmak safety kararının parçasıdır. Beş replica, uygun crash-fault modelinde iki replica kaybına rağmen çoğunluk oluşturabilir.
Paxos proposal numaraları, promise ve accepted değerleri kullanır; quorum kesişimi seçilmiş değerlerin korunmasına yardım eder. Multi-Paxos bunu log için kullanır. Raft leader election, log replication ve safety kurallarını daha ayrışmış biçimde anlatır. Her yazıyı RAM'de çoğunluğa göndermek tek başına Raft değildir: term, log matching, election restriction, durable storage ve commit kuralları gerekir.
Crash fault, Byzantine davranış ve istemci exactly-once semantiği farklı problemler. Raft/Paxos sıradan modellerinde keyfi kötü niyetli node'a tolerans vaat etmez. FLP tam asenkron modelde belirli koşullarla deterministik termination sınırını anlatır; “pratik consensus imkânsız” sonucunu vermez. Timeout, failure detector ve partial synchrony ilerleme varsayımlarını değiştirir. Bunlar blockchain ile eş anlamlı değildir.
Adım adım iz sürme
5 node'da quorum 3'tür. İki 3'lü küme en az bir node paylaşır; kesişim gerekli olsa da tam safety kanıtı değildir.
Maliyet ve varsayımlar
Protokol maliyeti mesaj, ağ gecikmesi, log ve durable I/O modeliyle ölçülür; tek Big-O bütün sistemi anlatmaz.
Çalıştırılabilir örnek
Python 3 ile çalıştır. Assert küçük bir örneği denetler; genel doğruluk ispatı değildir. Bazı ileri örnekler özellikle küçük model veya referans oracle'dır; tam üretim uygulaması değildir.
from itertools import combinations
quorums=list(map(set,combinations(range(5),3)))
assert all(a&b for a in quorums for b in quorums)KAVRADIĞINI KONTROL ET
Sıra sende
2 node'lu partition neden 5 node'lu kümede yazmaya devam etmemeli?
Çözümün mantığını göster
Çoğunluğu yoktur; iki ayrı tarafın çelişkili kararları önlenmelidir. Gerçek commit şartları ayrıca protokole bağlıdır.
Bir adım ileri
- Örneği değiştirmeden önce girdi sözleşmesini ve invariantı yaz.
- Uygun olan boş, sınır, tekrar ve adversarial girdileri ekle. Basit bir oracle ile karşılaştır.
- Belirtilen modelde maliyeti çıkar; farklı girdi büyüklüklerini ölç ve farkları gerekçelendir.
Temel kaynaklar ve ders notları
Bu eğitimde özgün anlatım kullanıldı; aşağıdaki kaynaklar ispatlar ve ileri okumalar sunar. Bağlantılar daha geniş ders modülünü kapsayabilir.
Ongaro & Ousterhout · Raft ↗Leslie Lamport · Paxos Made Simple ↗