Raft Uzlaşma Algoritması: Lider Seçimi ve Log Replikasyonu

Her Kubernetes kümesi durumunu etcd'de saklar ve etcd bu durum üzerinde Raft ile uzlaşır. Consul, CockroachDB, TiKV, RabbitMQ quorum kuyrukları ve Kafka 4.0 ZooKeeper'ı kaldırdığından beri Kafka'nın kendi controller'ları da öyle. Bunlardan herhangi birini çalıştırıyorsanız, Raft aksi hâlde keyfi görünen davranışları açıklar: Üç düğümlü bir küme iki düğüm çöktüğünde neden yazma kabul etmeyi bırakır, bir lider değişikliği sırasında yazmalar neden bir saniye duraklar ve dördüncü bir düğüm bir kümeyi neden daha güvenli yapmadan daha pahalı hâle getirir.

Bu yazı Raft'ı beş düğümlü bir kümede log replikasyonunu gösteren bir diyagramla açıklıyor: dönemler, lider seçimi, AppendEntries, commit kuralı, arızalar, küme boyutlandırma, okumalar ve üyelik değişiklikleri.

Model: çoğaltılmış bir log

Raft çoğaltılmış bir durum makinesi kurar. Her sunucu bir komut logu tutar. Tüm sunucular aynı komutları aynı sırayla uygularsa aynı duruma ulaşır. Raft'ın işi, sunucular çökse ve mesajlar kaybolsa ya da gecikse bile logları aynı tutmaktır.

Her sunucu üç durumdan birindedir: takipçi (follower), aday (candidate) ya da lider (leader). Zaman 1, 2, 3 diye numaralanan dönemlere (term) bölünür; her dönem bir seçimle başlar ve en fazla bir lideri olur. Kendi döneminden daha yüksek bir dönem gören sunucu dönemini günceller ve takipçi olur; böylece eski bir lider, yenisinden haber alır almaz geri çekilir.

Raft'ın yalnızca iki RPC'ye, artı snapshot'lar için bir tanesine ihtiyacı vardır:

Tasarım, Diego Ongaro ve John Ousterhout'un USENIX ATC 2014'te yayımlanan In Search of an Understandable Consensus Algorithm makalesinden gelir.

Lider seçimi

Bir takipçi liderden düzenli heartbeat'ler bekler. Seçim zaman aşımı içinde hiçbiri gelmezse liderin gittiğini varsayar:

1. Dönemini bir artırır, aday olur ve kendine oy verir.
2. Diğer tüm sunuculara, son log girdisinin indeksi ve dönemiyle birlikte RequestVote gönderir.
3. Her sunucu dönem başına en fazla bir oy verir ve yalnızca logu en az kendi logu kadar güncel olan bir adaya verir: Son dönemi daha yüksek olan kazanır, dönemler eşitse daha uzun log kazanır.
4. Çoğunluktan oy toplayan aday lider olur ve heartbeat göndermeye başlar.

İki aday oyları bölerse kimse kazanmaz ve dönem lidersiz biter. Raft bunu zaman aşımlarını rastgeleleştirerek nadir hâle getirir; makale 150 ile 300 ms gibi değerler önerir, böylece genellikle bir sunucu önce zaman aşımına uğrar ve diğerleri başlamadan kazanır.

Üretim sistemleri zaman aşımlarını ağlarına göre seçer. etcd varsayılan olarak 100 ms heartbeat ve 1.000 ms seçim zaman aşımı kullanır ve belgeleri seçim zaman aşımının üyeler arasındaki gidiş dönüş süresinin en az on katı olması gerektiğini söyler. Bir Kubernetes kontrol düzleminin etcd liderini kaybettikten sonra yeniden yazma kabul etmesinin bir saniye ya da daha uzun sürebilmesinin nedeni bu rakamlardır.

Log replikasyonu

Seçildikten sonra lider her yazmayı yönetir:

1. Bir istemci lidere bir komut gönderir, örneğin SET x=5.
2. Lider onu mevcut dönemle yeni bir girdi olarak kendi loguna ekler; örneğin 3. dönemde 7. indeks.
3. Lider her takipçiye yeni girdiyle birlikte, hemen önceki girdinin indeksini ve dönemini (6. indeks, 3. dönem) içeren AppendEntries gönderir.
4. Bir takipçi yalnızca logunda 6. indekste 3. döneme ait bir girdi varsa kabul eder. Bu tutarlılık kontrolü, iki log bir konumda uyuşuyorsa ondan önceki her şeyde de uyuştuklarını garanti eder.
5. Lider dahil sunucuların çoğunluğu girdiyi sakladığında lider onu commit edilmiş olarak işaretler, durum makinesine uygular ve istemciye yanıt verir.
6. Takipçiler yeni commit indeksini bir sonraki AppendEntries'ten öğrenir ve girdiyi onlar da uygular.

Bir takipçi logu ayrıştığı için bir girdiyi reddederse lider, loglar eşleşene kadar her seferinde bir indeks, optimizasyonlarla daha hızlı geri gider; ardından takipçinin çakışan girdilerinin üzerine kendi girdilerini yazar. Yalnızca commit edilmemiş girdilerin üzerine yazılır; bu güvenlidir, çünkü kimseye bunların başarılı olduğu söylenmemiştir.

Commit kuralı ve ince nokta

“Çoğunluk sakladığında commit edilir” kuralının bir istisnası vardır ve makaledeki en ünlü ayrıntı budur. Yeni bir lider, önceki dönemlerden kalan girdileri commit etmek için replikaları saymamalıdır. Onları dolaylı olarak, üzerlerine kendi döneminden bir girdiyi commit ederek commit eder. Bu kural olmasaydı, bir çoğunlukta saklanan bir girdinin üzerine sonraki bir lider yine de yazabilirdi. Pratikte yeni bir lider, öncesindeki her şeyi hızla commit etmek için döneminin başında boş bir no-op girdisi ekler.

Seçim kısıtlaması güvenlik argümanını tamamlar: Bir aday çoğunluğun oyuna ihtiyaç duyduğu ve commit edilmiş her girdi bir çoğunlukta bulunduğu için, kazanabilecek her aday commit edilmiş her girdiye zaten sahiptir.

Bir küme neye dayanır

n sunuculu bir kümenin lider seçmek ve yazmaları commit etmek için çoğunluğa ihtiyacı vardır; dolayısıyla yarıdan azının arızasına dayanır:

Dört sunucu, üç sunucu gibi tek bir arızaya dayanır, ama artık her yazma iki yerine üç onay bekler. Kümelerin tek sayıda olmasının nedeni budur. Birinde planlı bakım yapılırken bir başka arızaya dayanmak istediğinizde beş, olağan seçimdir.

Gecikme de aynı aritmetiği izler. Her yazma, liderin en hızlı çoğunluğa ulaşmasını ve o sunucuların girdiyi diske kalıcı olarak yazmasını bekler. Üç bölgeye yayılmış bir kümede her yazma en az bir kez en yakın diğer bölgeye gidiş dönüş maliyeti taşır. Yavaş diskler yavaş ağlar kadar zarar verir; etcd belgelerinin fsync gecikmesine zaman aşımları kadar yer ayırmasının nedeni budur.

Pratikte arızalar

• Lider çöker. Takipçiler zaman aşımına uğrar, biri seçimi kazanır ve yazmalar devam eder. O sırada uçuşta olan istekler commit edilmiş de olabilir, edilmemiş de; bu yüzden istemciler yeniden denemelidir ve yeniden denedikleri komutlar idempotent olmalıdır.
• Bir ağ bölünmesi. Çoğunluğun olduğu taraf bir lider seçer ve devam eder. Azınlık tarafındaki eski bir lider hiçbir şeyi commit edemez; bölünme iyileştiğinde daha yüksek dönemi görür ve geri çekilir.
• Yavaş bir takipçi. Commit'ler onu beklemez. Çok geride kalırsa lider, logun tamamını yeniden oynatmak yerine bir snapshot gönderir.
• Rahatsız edici bir sunucu. Liderden kopmuş bir sunucu zaman aşımına uğramayı ve dönemini artırmayı sürdürür; geri döndüğünde bu, gereksiz seçimlere yol açabilir. Ongaro'nun doktora tezinden gelen pre-vote, bir adayın dönemini artırmadan önce kazanabileceğini kontrol etmesini sağlar.

Okumalar bedava değildir

Bir lider okumaları körü körüne kendi durumundan yanıtlayamaz: Bir bölünmenin öbür tarafında yeni bir lider seçilmiş olabilir ve eski lider bayat veri döndürür. Doğrusallaştırılabilir (linearizable) okumalar, ya yanıt vermeden önce liderliği doğrulamak için bir tur heartbeat (Raft'ın ReadIndex'i) ya da sınırlı saat kaymasına dayanan zaman tabanlı bir lider kirası (lease) gerektirir. Takipçiler de okuma sunabilir, ama yalnızca liderin commit indeksini kontrol ettikten sonra ya da bayat sonuçları kabul ederek. etcd bunu açık hâle getirir: etcdctl get varsayılan olarak doğrusallaştırılabilirdir; --consistency=s ise daha hızlı, bayat olabilecek serileştirilebilir bir okuma ister.

Üyeliği değiştirmek

Sunucu eklemek ya da çıkarmak çoğunluğun ne olduğunu değiştirir ve yapılandırmaları dikkatsizce değiştirmek aynı anda iki çoğunluk yaratabilir. Raft bunu joint consensus ile ya da her seferinde tek bir sunucuyu değiştirerek ele alır. Birçok uygulama, etcd'nin yaptığı gibi, yeni sunucuları oy hakkı olmayan learner'lar olarak da ekler; böylece yeni bir düğüm çoğunluğa sayılmadan önce logu yakalar.

Log replikasyonu diyagramı

Nasıl okunur:

• İstemci tek bir komut gönderir: 3. dönemde lider S1'e. Lider onu 7. indekse yazar.
• Her tablo bir sunucunun logudur: indeks, dönem ve komut. Tablolar arasında eşleşen satırlar aynı girdidir.
• AppendEntries kenarları liderden dört takipçiye gider. S2 ve S3 7. indeksi onaylar.
• S4 geride kalmıştır, 6. indekstedir; S5'e ulaşılamaz, 5. indekstedir. İkisi de commit'i engellemez.
• Not, commit kuralını gösterir: Beş sunucudan üçü 7. girdiyi saklar, dolayısıyla girdi commit edilmiştir ve istemci yanıtını alır.

Öğreten uzlaşma diyagramları çizmek

• Yalnızca sunucuları değil, logları gösterin. Raft'ın garantileri loglar hakkındaki ifadelerdir. Beş kutu ve oklardan oluşan bir diyagram ilginç olan her şeyi gizler.
• Her girdinin yanına dönemi yazın. Dönemler seçimleri, çakışmaları ve commit kuralını açıklar.
• Sağlıksız bir küme çizin. Geride kalan ya da bölünmüş bir takipçi, çoğunlukların neden önemli olduğunu kusursuz bir kümeden daha iyi gösterir.
• Senaryo başına bir diyagram kullanın: Bir seçim, normal replikasyon ve bir failover sonrası çakışma onarımının her biri kendi resmini hak eder.

Replikasyonun veritabanı mimarilerine genel olarak nasıl oturduğu için veritabanı replikasyonu diyagramına bakın. Kubernetes mimari diyagramı etcd'nin bir kontrol düzleminde nerede durduğunu gösteriyor, Kafka mimari diyagramı ise KRaft controller'larını ele alıyor. CockroachDB gibi sistemler her veri aralığı için bir Raft grubu çalıştırır; bu da uzlaşmayı veritabanı sharding diyagramındaki fikirlere bağlar.

Archboard'da oluşturun

1. Google ya da GitHub ile giriş yapın ve bir diyagram oluşturun.
2. Küme için bir Temel Çerçeve ekleyin ve onu mevcut dönemle etiketleyin.
3. İçine, her sunucu için bir tane olmak üzere indeks, dönem ve komut sütunlarıyla beş Temel Tablo düğümü ekleyin. Lideri ortaya koyun.
4. Çerçevenin dışına istemci için bir Temel Kutu ekleyin ve onu komutla lidere bağlayın.
5. Liderden her takipçiye AppendEntries kenarları, girdiyi saklayan takipçilerden de geriye kesikli onay kenarları çizin. Ulaşılamayan takipçiyi uyarı renginde kesikli bir kenarla işaretleyin.
6. Commit kuralıyla Temel paketinden bir Markdown bloğu ve liderin yanına commit indeksini belirten bir Not ekleyin.

Örnek 8 diyagram düğümü kullanıyor ve Free planın sınırları içinde kalıyor.

SSS

Raft kümelerinde neden tek sayıda düğüm olur? Bir kümenin çalışması için çoğunluğa ihtiyacı vardır. Üç düğüme dördüncüyü eklemek, daha fazla arızaya dayanmadan çoğunluğu ikiden üçe çıkarır; dolayısıyla çift sayılar hata toleransı eklemeden gecikme ve para maliyeti getirir.

Bir lider seçimi sırasında yazmalara ne olur? Yeni bir lider seçilene kadar, genellikle bir ya da iki seçim zaman aşımı içinde, beklerler ya da başarısız olurlar. İstemciler idempotent isteklerle yeniden denemelidir, çünkü zaman aşımına uğrayan bir yazma commit edilmiş olabilir.

Raft ile Paxos arasındaki fark nedir? Aynı sorunu benzer garantilerle çözerler. Raft anlaşılması ve uygulanması daha kolay olacak şekilde tasarlandı: güçlü bir lider kullanır, seçimi replikasyondan ayırır ve üyelik değişikliklerini tanımlar.

Raft'ta takipçiler okuma sunabilir mi? Evet, önce liderin commit indeksini doğrularlarsa ya da uygulama bayat olabilecek veriyi kabul ediyorsa. Bir takipçinin yerel durumunu kontrol etmeden okumak eski değerler döndürebilir.

Raft kötü niyetli düğümlere karşı koruma sağlar mı? Hayır. Raft çökmelere, yeniden başlatmalara ve kaybolan ya da geciken mesajlara dayanır, ama sunucuların protokole uyduğunu varsayar. Bizans hata toleransı farklı algoritmalar ve daha fazla replika gerektirir.

Ücretsiz başlayın — tek kullanıcı, kredi kartı gerekmez.