Konsensüs algoritmaları

1) Konsensüs nedir ve neden gereklidir

Konsensüs - Arızalar ve gecikmeler için birden fazla düğüm arasındaki değerlerin aynı değerini/sırasını müzakere edin. Geleneksel olarak, durum çoğaltma problemi (State Machine Replication, SMR) çözülür: deterministik bir durum makinesi ve genel bir işlem sırası vardır.

• Consensus (SMR): tek bir toplam komut sırası - doğrusallaştırılabilir depolama/kayıt defteri, küme meta verileri, işlem koordinatörleri.
• Toplam sipariş olmadan Quorum işlemleri (Dinamo benzeri, CRDT): ıraksama ve sonraki birleşme izin; Global serileştirmenin gerekli olduğu durumlarda konsensüsün yerini almayın.

2) Zaman ve başarısızlık modeli

2. 1 Zaman modeli

Asenkron ağ: gecikmeler sınırsızdır; FLP teoremi, ek varsayımlar olmadan hem güvenliği hem de canlılığı garanti etmenin imkansız olduğunu ⇒.
Kısmen eşzamanlı (genellikle pratikte): Bilinmeyen bir T'den sonra, sistem eşzamanlı olarak "davranır" - çoğu algoritma (Raft, Paxos) buna güvenir.
Senkron: kanallar için katı zaman sınırları (nadiren satışlarda, özel ağlar/PRT hariç).

2. 2 Başarısızlık modeli

Crash-fault toleranslı (CFT): Düğümler düşebilir/asılabilir, ancak kötü niyetli davranmazlar.
Byzantine-fault toleranslı (BFT): Düğümler mesajları yalanlayabilir/taklit edebilir. F Bizans'a tolerans için 3f + 1 knot gerekir.

3) Konsensüsün özellikleri

Güvenlik: tutarlılık (iki doğru düğüm farklı değerleri çözmez).
Canlılık: Ağ "sağlıklı'ise, bir çözüm elde edilir.
Doğrusallaştırılabilirlik (lineerlik): işlemler tek bir sırayla atomik olarak "görülür".
Dayanıklılık: Alınan kararlar geri alınmaz (log/quorum koruması).

4) Kuorumlar, çoğunluklar ve kavşaklar

CFT dünyasında, klasik: quorum> N/2. Kayıtlar ve lider seçimleri nisap geçişi kullanır, bu nedenle iki "geçerli" işlem çakışmaz.
BFT dünyasında: 3f + 1'in 2f + 1 kuorumları, en az f + 1 dürüst düğümlerin kesişimini sağlar.

Geçiş kuralı: Herhangi iki çekirdek ≥1 ortak adil düğüm (CFT) veya ≥f+1 (BFT) olmalıdır.

5) Durum çoğaltma (log + uygulama)

• Anlık görüntüler (daha sonra erken kayıtların silinebileceği/derlenebileceği bir durum dilimi).
• Günlük sıkıştırma ve log triem.
• Determinizm kontrolleri (aynı kod/yapılandırma sürümü).

6) Liderlik ve liderlik dışı programlar

Liderlik (Raft, Multi-Paxos, ZAB): Bir lider kayıtları seri hale getirir - zihinsel ve operasyonel olarak daha kolay, istikrarlı bir lider üzerinde daha iyi gecikme.
Lidersiz/çoklu lider (EPaxos, Caesar): Lider için daha fazla paralellik ve hoşgörü, ancak daha zor uygulama ve çatışma çözümü; Kâr, ekiplerin küçük çatışmalarıyla görülebilir.

7) Klasik CFT algoritmaları

7. 1 Paxos/Çoklu Paxos (ve uygulamaları)

Fikir: iki aşama (hazırlama/önerme), kabul edenlerin vaatleri, çoğunluk quorum'ları. Multi-Paxos "istikrarlı bir lider" bırakır ve "ısınma'dan sonra işlemleri tek turlu (yeni girişler için) haline getirir.

• Esnek ama uygulanması zor bir model.
• Özel girişler yoluyla yeniden yapılandırmalar (ortak konsensüs).
• Uygulamada, kütüphaneler/motorlar (Chubby/Spanner üretimi).

7. 2 Sal

Öğrenme için ayrıştırılmış: lider seçimi, log replikasyonu, yeniden yapılandırma.

Seçim: rastgele zaman aşımları, dönem oylama; dönem başına bir lider.
AppendEntries: lider kayıtları yayınlar, ön ekin (dizin/terim) eşleşmesini izler, çoğunluk sabitlemesini taahhüt eder.
Okuma yolu: Doğrusal okumalar için lease-reads (güçlü bir lider ile) veya read-index.
Yeniden yapılandırma: "ortak" - düğümler değiştirmeden önce iki kümede oy kullanır.

Artıları: geliştirmek/hata ayıklamak daha kolay, güçlü düzen değişmezleri. Eksiler: Lider bir baskı noktasıdır.

7. 3 ZAB (ZooKeeper Atom Yayını )/Viewstamped Replication (VRR)

ZAB: lider yayın işlemleri, kurtarma aşaması, zxid (epoch + index).
VRR: Ruhu Multi-Paxos benzer bir birincil replikant ile "görünümler".

8) Lider Olmayan/Çok Lider CFT'ler

8. 1 EPaxos

Kalıcı bir lider yoktur: herhangi bir düğüm bir komut başlatabilir.
Çatışma ekipleri kısmi emir alır; Çatışmasız - yerel olarak 1-2 RTT'ye bağlı kalın.
Düşük çatışma, ancak karmaşık bağımlılık/grafik kodları ile coğrafi dağılımda kazanç.

8. 2 Sezar, Mencius

Gecikme/dengeleme ve WAN işlemlerini optimize eden varyasyonlar.

9) BFT algoritmaları ve PoS ailesi

9. 1 PBFT (Pratik BFT)

Üç aşama (ön hazırlık/hazırlık/taahhüt), 3f + 1 düğüm gerektirir.
Yerel ağlarda, çok adımlı yollarda ve O (N ²) mesajlarında düşük gecikme süresi.

9. 2 Bonfile (BFT-PoS stili)

Teklifli turlar ve iki oy (önleme/ön sipariş).
Deterministik doğrulayıcı-önerici, zaman aşımları, kısmi eşzamanlılık.
Düzinelerce/yüzlerce doğrulayıcı ile izin verilen/PoS ağları için iyidir.

9. 3 HotStuff (ve türevleri)

Üç fazlı şema, çekirdek sertifikaları (QC) ile "paketler" halinde birleştirilmiştir.
İletişimin doğrusal karmaşıklığı, paketleme ve paralel boru hattı desteği, blok zincirlerindeki uygulamalar için uygundur (örneğin, Diem/Move ekosistemi).
Eşik imzaları ile trafik azalır.

9. 4 PoW/kümülatif konsensüs (kısaca)

Kesin anlamda BFT değil, olasılıksal yakınsama (en çok işe sahip zincir). Avantajları: sadelik/açıklık; Dezavantajları: Enerji, ~ saniyeden dakikalara kadar.

10) Okur: doğrusal, sıralı ve önbelleğe alınmış

Doğrusal okur: Aktif kiralama veya okuma indeksi (Raft) üzerinden lider - çoğunluk yoluyla onay.
Sıralı: herhangi bir düğümden okunabilir, ancak tazelik garantisi olmadan.
Takipçi okur: zayıf gereksinimler altında izin verilebilir; önbellekler için - tamam.

11) Yeniden yapılandırma (küme kompozisyonunun değiştirilmesi)

İki örtüşen konfigürasyon gerektirir (ortak konsensüs): herhangi bir taahhüt, her iki konfigürasyonun kuorumlarını "delikler" olmadan geçirir.
Her seferinde bir tane ekleyin/çıkarın, çekirdek boyutunu gözlemleyin.
Liderlik transferi duraklamaları azaltır.

12) Performans ve ayarlama

12. 1 Gecikmeler

Liderlik algoritmaları: Yazma başına 1 RTT (istikrarlı bir liderle) + replikasyon.
Coğrafi dağıtım: WAN RTT hakimdir - yerel bölgeler + bölgeler arası çoğaltma veya EPaxos/HotStuff yaklaşımlarını kullanın.

12. 2 işlem hacmi

Gruplama (komut gruplama), paralel AppendEntries, günlük sayfası önbelleği, paralel uygulama (işlemler değiştirildiğinde).
Diskler: Ayrı bir cihazda NVMe/Log, 'O _ DIRECT'/AIO, SLA kısıtlamaları ile büyük' fsync 'aralığı (dayanıklılık/gecikme uzlaşma).

12. 3 p99 kuyrukları

Sıcak düğümlerden kaçının (her zaman bir lider vardır): takipçiler üzerinde periyodik rotasyon veya okuma-boşaltma.
Monitör GC duraklatır (JVM/Go), CPU pinleri, NUMA.

13) Coğrafya ve Topolojiler

1 bölge, 3 bölge: klasik CFT kümesi (N = 3/5).
2 bölge: kaçının - 1-1 bölünmede güvenilir çoğunluk yok.
3 + bölge: "orta" veya lidersiz algoritmalarda lider; bölgesel vekiller/asenkron log ile yerel cepheler mümkündür.

14) Operasyonun pratik konuları

14. 1 Anlık görüntüler ve kurtarma

Günlük boyutuna/işlem sayısına göre eşik.
Bir anlık görüntünün yeni düğümlere aktarılması; Checksum kontrolü.

14. 2 İzleme

Liderlik: Lider kimdir, kaç terim (terim/dönem) değişti.
Лаги: 'append _ latency', 'commit _ index - applied_index'.

Yeterli çoğunluk sağlığı: "Çoğunluk hayatta mı/2f + 1?"

Günlük boyutu/sıkıştırma hızı, anlık görüntüler kuyruğu.

BFT için: oy payı, imzacıları atma, QC gecikmeleri

14. 3 Kod Güvenliği/Tutarlılık

Kablo üzerinde protokol sürümleri, günlük uyumluluğu olan geçişler.
Dış etkiler üzerine eskrim belirteçleri (bkz. "Dağıtılmış kilitler"): CRON/işlere geçmek için teslim süresi (terim).

15) Anti-desenler

Bir DBMS veya çoğunluğun serileştirmeden okuduğu "moda uğruna" konsensüs koymak yeterlidir.
Net sınırlar olmadan CP ve AP'yi karıştırın (CAP) - öngörülemeyen UX.
Düzinelerce düğüm içeren kurumsal görevler için PoW/PoS'u abartın (zor/pahalı).
Kompozisyon değiştiğinde yeniden yapılandırmayı ve "kesişen kuorumları" yoksayın.
Okuma engeli eksikliği (kiralama/okuma indeksi) - kirli okumalar.
2 düğümlü kümeleri çalıştırın (çoğunluk yok).
Diskleri ve fsync'yi hafife almak:'her şey bellekte uçar "- ilk yeniden başlatmaya kadar.

16) Seçim kontrol listesi

1. Arıza modeli: CFT (çökmeler) veya BFT (kötü amaçlı)?
2. Coğrafya: Bir bölge/üç bölge veya WAN? RTT karar veriyor.
3. Okuma semantiği: doğrusal okumalar gerekli midir? Kiralama/okuma-indeksi/takip.
4. Yük: p50/p99 ile beklentiler, verim; Çoklu liderliğin gerekli olup olmadığı.
5. Operasyonel karmaşıklık: Kütüphane/kullanıma hazır motor (etcd/ZK/Consul/Raft-libs) vs yerel uygulama.
6. Yeniden yapılandırma: Sık mı? Ortak uzlaşı ve göç araçlarına ihtiyacımız var.
7. Entegrasyonlar: dış yan etkiler - çağa/terime göre eskrim var mı?
8. Güvenlik: ana bilgisayar kimlik doğrulaması, kanal şifreleme, protokol sürüm denetimi.
9. Test playbook'ları: bölüm, GC-stop, kill leader, yavaş disk, saat eğriltme.
10. Gözlemlenebilirlik: Lider/Gecikmeler/Günlük ve Uyarı metrikleri ayarlanır.

17) Mini rehber: ne zaman ne alınır

DC içindeki konfigürasyonlar/kilitler/koordinasyonlar için etcd/sal kümesi.
ZooKeeper/ZAB zaten ZK bağlı hizmetler için (eski yığınları, kuyruklar, liderlik).
Multi-Paxos, son derece uzmanlaşmış sistemlerde hazır bir servis/kütüphane aracılığıyla.
Coğrafi dağıtım ve düşük komut çakışması için EPaxos.
İzin verilen ağlar/PoS katmanı için onlarca ila yüzlerce doğrulayıcı ve kesinlik gereksinimi olan Tendermint/HotStuff.
Fikir birliğine ihtiyaç duyulmadığında dinamo benzeri/CRDT, ancak sonraki birleşme ile erişilebilirlik/ölçek önemlidir.

18) Arabirim örnekleri (pseudo)

18. 1 Commit kayıtları (Raft tarzı)

pseudo client -> leader: Propose(cmd)
leader. appendLog(cmd)
leader. replicateToQuorum()
if quorum_acked:
leader. commit(index)
leader. apply(index)
leader. reply(client, ok)

18. 2 Doğrusal okuma için okuma indeksi (Raft)

pseudo client -> any: LinearizableRead node -> leader: ReadIndex?
leader -> quorum: Heartbeat (barrier)
leader -> node: ReadIndex=commit_index node. wait_until(applied_index >= ReadIndex)
node. reply(client, state_at(ReadIndex))

18. 3 Ortak yapılandırma

pseudo old_conf + new_conf # quorums must intersect commit (entries under joint)
switch_to(new_conf)

18. 4 BFT (HotStuff yaklaşık)

pseudo propose(block)
collect votes -> QC lock on highest QC commit when have consecutive QCs across phases

19) SSS

S: Neden iki düğüm ve bir tie-breaker kullanmıyorsunuz?
C: Üçüncü bir hakem olmadan iki düğüm, bölünmede yeterli çoğunluk vermez. ≥3 (CFT) veya 3f + 1 (BFT) gerekir.

S: Raft'daha basit "Paxos nedir?
C: Açık ayrışma, log ve konfigürasyonun anlaşılabilir değişmezleri; Uygulaması ve bakımı daha kolaydır.

S: Lideri yüklemeden nasıl hızlı okursunuz?
C: Kritik olmayan için follower-reads (ardışık) veya lineer için lease-reads/read-index; önbellek.

S: P99'u ne öldürür?
C: WAN-RTT, disk fsync, GC-stops, aşırı ısınmış lider, yoğun saatlerde büyük anlık görüntüler.

S: Önbellek/katalog fikir birliğine ihtiyaç duyuyor mu?
C: Yeterli nihai tutarlılık varsa - hayır. Eğer işlem değişmezleri gerekiyorsa, evet.

20) Toplam

Konsensüs, katı tutarlılık ve sipariş için bir araçtır. Başarısızlık modeline ve coğrafyaya dayalı bir algoritma seçin; Yeterli çoğunluk geçişleri, doğru yeniden yapılandırma, kritik yerlerde doğrusal okumalar ve gözlemlenebilirlik sağlar. Dış efektler, anlık görüntüler ve dergi disiplini için eskrim yapmayı unutmayın. O zaman devlet kopyalanması öngörülebilir olacak ve olaylar nadir ve anlaşılabilir olacaktır.