Dağıtılmış sistemlerde "hayalet yeniden ortaya çıkış" nasıl çözülür?
1. "Hayalet Yeniden Görünme" Sorunu
Endüstride, yüksek düzeyde erişilebilir veri tutarlılığı sağlamak için yaygın olarak kullanılan Paxos, Raft, Zab ve Paxos varyantları gibi birçok dağıtılmış tutarlı çoğaltma protokolü olduğunu biliyoruz. Paxos grubu genellikle 3 veya 5 adet karşılıklı yedekli düğümden oluşur ve bu, azınlık düğüm arızası durumunda hizmet sağlamaya ve veri tutarlılığı sağlamaya devam etmeye izin verir. Bir optimizasyon olarak, protokol genellikle teklifin başlatılmasından sorumlu olacak düğümler arasından bir lider seçer Liderin varlığı, normal koşullar altında paralel tekliflerin karışmasını önler, bu da teklif işleme verimliliğini büyük ölçüde artırır.
Bununla birlikte, ağ izolasyonu, makine arızası vb. Gibi bazı aşırı anormallikler göz önünde bulundurulduğunda, Leader birden fazla geçiş ve veri kurtarmaya maruz kalabilir.Günlük yedekleme ve kurtarmayı işlemek için Paxos protokolünü kullanırken, çoğunluğu oluşturan günlüğün kaybolmamasını sağlayabilir. Ancak, "hayalet yeniden ortaya çıkma" denen bir olgudan kaçınılamaz. Şu durumu düşünün:
Yukarıdaki tabloda gösterildiği gibi, ilk turda A belirlenen Lider oldu ve 1-10 arasında bir günlük yayınladı, ancak sonraki 6-10 çoğunluk oluşturmadı ve rastgele düştü. Daha sonra ikinci turda B lider olarak atandı ve 6-20 log yayınlamaya devam etti (B 6-10 logun varlığını görmedi) Bu sefer 6 ve 20 numaralı iki log çoğunluğu oluşturdu. Geçiş tekrar rastgele gerçekleşir ve A geri gelir Çoğunluktan elde edilen en büyük LogId 20'dir, bu yüzden boşluğu doldurmaya karar verdi. Aslında, bu sefer 6'da başlayıp 20'ye kadar doğrulamaya devam etme olasılığı çok yüksek. Tek tek neler olacağını görelim:
Yukarıdaki dört tür durumun analizinde, 1, 3 ve 4 büyük sorunlar değildir. Esas olarak sahne 2'de, ikinci turda olmayan 7 ~ 10'a eşdeğerdir ve ardından üçüncü sütunda yeniden görünür. Oceanbase'e göre, veritabanı günlük senkronizasyon senaryolarında bu sorun kabul edilemez.Basit bir örnek transfer senaryosudur.Kullanıcı sonucu zaman içinde aktarırsa, genellikle transferin başarılı olup olmadığını kontrol edecek ve yeniden deneyip denemeyeceğine karar verecektir. biraz. Aktarım sonucu ilk kez sorgulanırsa, geçerli olmadığı ve tekrar deneyin ve aktarım işlem günlüğünün hayalet bir yineleme günlüğü olarak yeniden görünmesi, kullanıcının aktarımı tekrar etmesine neden olur.
2. Multi-Paxos'a dayalı "hayalet yeniden ortaya çıkma" sorununu çözün
Multi-Paxos tarafından uygulanan tutarlılık sistemine dayanan "hayalet yineleme" sorunuyla başa çıkmak için, her günlük içeriğine bir epochID kaydedilebilir ve Teklif Veren, bu günlüğü oluştururken epochID olarak geçerli Teklif Kimliği'ni kullanmak üzere atanır. LogID sırasına göre günlükleri yeniden oynatırken, lider hizmete başlamadan önce bir StartWorking günlüğü yazacağından, epochID önceki günlükten daha küçükse, bunun bir "hayalet yineleme" günlüğü olduğu anlamına gelir. Bu günlük göz ardı edilmelidir. (Açıklayın, sanırım buradaki sipariş önce boşlukları doldurmak, ardından StartWorkingID yazmak ve sonra hizmet sağlamaktır).
Yukarıdaki örnek, 3. Tur, A lider olarak başlatıldığında, günlük kayıttan yürütmenin yeniden onaylanması gerektiğini gösterir. Söylemeye gerek yok, 1 ~ 5 indeksinin günlüğü, epochID 1'dir ve sonra epochID aşama 2'ye girer, indeks 6, epochID'nin olduğunu doğrulayacaktır. 2 StartWorking günlüğü, ardından 7 ~ 10 dizini, çünkü bu, epochID 1 olan ve önceki günlük epochID'den daha küçük olan günlüktür ve yok sayılacaktır. Dizin 11 ~ 19'un günlükleri için EpochID, StartWorkingID'nin son turunu takip etmelidir (tabii ki, Teklif Kimliği 3'te tutulmalıdır) veya bir noop günlük olduğundan, özel olarak işlenebilir, yani bu kısım Günlük, epochID'nin boyut karşılaştırmasına katılmaz. Ardından indeks 20 günlüğü yeniden doğrulanacaktır. Son olarak, dizin 21 StartWorking günlüğüne yazıldıktan ve çoğunluk tarafından onaylandıktan sonra, A lider olarak istekleri almaya başlar.
3. Raft'a dayalı olarak "hayalet yeniden ortaya çıkma" sorununu çözün
3.1 Raft log kurtarma hakkında
Öncelikle, Raft'ın günlük kurtarma işleminden bahsedelim. Raft'ta, seçilen her lider, taahhüt edilmiş verileri içermelidir (çekmece ilkesi, seçilen lider çoğunluktaki en yeni verilerdir ve çoğu düğümde taahhüt edilen taahhüdü içermelidir. Veri), yeni lider diğer düğümlerdeki tutarsız verilerin üzerine yazacaktır. Yeni seçilen Lider, önceki dönem liderinin taahhüt ettiği Kayıt Girişini içermesi gerekmekle birlikte, önceki dönem liderinin taahhüt etmediği Kayıt Girişini de içerebilir. Günlük Girişinin bu kısmı, nispeten zahmetli olan Taahhütlü'ye dönüştürülmelidir.Lider'in birden çok kez geçiş yaptığını ve Günlük Kurtarma'nın tamamlanmadığını dikkate almak gerekir.Son teklifin tutarlı ve kararlı olduğundan emin olmak gerekir, aksi takdirde sözde hayalet yeniden üretim sorunu ortaya çıkacaktır.
Bu nedenle, Raft'a bir kısıtlama eklendi: Önceki terimin taahhüt edilmemiş verileri için, çoğu düğümde onarım ve yeni terim altında en az bir yeni Günlük Girişi, taahhüt edilmemiş sayılmadan önce çoğu düğüme kopyalanır veya onarılır. Günlük Girişi Gerçekleştirildi.
Süresi Taahhüt Edilmemiş olan son Günlük Girişini dönüştürmek için Raft'ın çözümü aşağıdaki gibidir:
Raft algoritması, Liderin seçildikten hemen sonra Noop'a özel bir dahili günlük eklemesini ve bunu diğer düğümlerle hemen senkronize etmesini gerektirir, böylece daha önce taahhüt edilmemiş tüm günlükler dolaylı olarak gönderilir.
Bu iki şeyi garanti eder:
- Hiçbir verinin kaybolmamasını, yani tüm Taahhütlü Günlük Girişlerinin kaybolmamasını sağlamak için maksimum Commit ilkesi aracılığıyla;
- Taahhüt edilmeyen verilerin okunmayacağı garanti edilir, çünkü yalnızca Noop çoğu düğüm tarafından onaylandıktan ve gönderildikten sonra (böylece önceki günlüklerle senkronize edilebilir), hizmet normal şekilde çalışacaktır; Noop günlüğünün kendisi de Noop'tan önce bir bölme çizgisidir. Günlük Girişi gönderilir ve sonraki Günlük Girişi iptal edilir.
3.2 Raft, "hayalet yeniden ortaya çıkma" sorununu çözer
Birinci bölümdeki sahne için, Raft lider seçilen A'nın üçüncü turunda yer almayacaktır.Öncelikle, seçim için adaylar son günlüğün dönem numarasını (lastLogTerm) ve günlüğün uzunluğunu (lastLogIndex) karşılaştırır. B ve C'nin lastLogTerm (t2) ve lastLogIndex (20) ikisi de A'nın lastLogTerm (t1) ve lastLogIndex (10) değerlerinden daha büyüktür, bu nedenle lider yalnızca B ve C'de görünebilir. C'nin lider olmasından sonra liderin, çalışan süreç sırasında kopyayı onaracağını varsayarsak, A için, günlük indeksinin 6 olduğu konumdan başlar ve C, günlük girişini kendi indeksi 6 ve daha sonra A'ya kopyalayacaktır, bu nedenle A'nın 6-10 dizinindeki orijinal dizin günlüğü silinir ve C ile tutarlı kalır. Son olarak, C noop'un log girişini follower'a gönderecektir.Çoğu tarafından alınır ve gönderilirse, normal çalışmaya başlayacak, dolayısıyla 7-10 indeksinin değerinin okunabileceği bir durum olmayacaktır.
Burada hayalet restorasyonunun daha genel bir sahnesini düşünün. Aşağıdaki günlük senaryolarını göz önünde bulundurun:
1) 1. Tur, A düğümü liderdir, Kayıt girişi 5 ve 6'nın içeriği işlenmemiştir ve A düğümü çalışmamaktadır. Şu anda, istemci Günlük girişi 5 ve 6'nın içeriğini sorgulayamaz.
2) 2. Tur, B Lider olur ve B'deki Log girişi 3, 4'ün içeriği C'ye kopyalanır ve B'nin baskın olduğu dönemde hiçbir şey yazılmaz.
3) 3. Tur, A geri yüklenir ve B ve C yeniden başlatılır ve A lider olarak yeniden seçilir, ardından Günlük girişi 5, 6'nın içeriği B ve C'ye kopyalanır. Bu sırada müşteri, Günlük 5, 6'yı sorgulamak için tekrar sorgular. İçerideki içerik.
Raft'a yeni bir lider eklemek, mevcut Terimin Günlük Girişini yazarak bu sorunu çözebilir.Aslında, bir StartWorking günlüğü yazmak MultiPaxos'un bahsettiği ile aynıdır.B Lider olduğunda, bir Dönem 3 girişi yazacaktır. Noop günlüğü, burada yukarıda belirtilen iki sorunu çözer:
- 3. Terimin noop günlüğü işleme alınmadan önce, B'nin 3. ve 4. dizinlerinin günlük içerikleri önce C'ye kopyalanmalıdır, bu da maksimum kesinleştirme ilkesini gerçekleştirir, hiçbir verinin kaybolmamasını sağlar ve önceden kaydedilmiş olan günlük girişleri kaybolmaz.
- A düğümü kurtarılsa bile, A'nın lastLogTerm'i B ve C'ninkinden daha küçük olduğu için lider olamaz. O zaman A'daki tamamlanmamış kesinleştirme sadece atılır, böylece sonraki okumalar Günlük Giriş 5, 6'yı okumaz. İçerideki içerik.
4. Zab'a dayalı olarak "hayalet yeniden görünme" sorununu çözün
4.1 Zab'ın günlük kurtarma hakkında
Zab iki aşamaya ayrılmıştır: atomik yayın ve çarpışma kurtarma Atomik yayının çalışma süreci aynı zamanda bir işlem gerçekleştirme sürecine benzer olabilir.
Kilitlenme kurtarma, iki aşamaya ayrılabilir: Lider seçimi ve veri senkronizasyonu.
Erken Zab anlaşmasıyla seçilen Lider aşağıdaki koşulları karşılar:
a) Yeni seçilen Lider düğümü, bu turdaki tüm adayların en büyük zxid'ini içerir.Ayrıca, Liderin en son verilere sahip olduğu da düşünülebilir. Bu garanti, Liderin mümkün olan en son verilere sahip olmasını sağlar.
b) Lider seçim sürecinde karşılaştırılacak zxid, her adayın taahhüt ettiği verilere göre oluşturulur. zxid bir 64-bittir, üstteki 32 bit epoch numarasıdır. Lider tarafından her yeni lider seçildiğinde, yeni lider epoch numarasını 1 ekleyecektir ve en alttaki 32 bit mesaj sayacıdır. Her mesaj alındığında bu değer +1 olur. Lider seçildikten sonra bu değer sıfırlanır. Bu tasarımın avantajı, eski liderin telefonu kapattıktan sonra yeniden başlatılması ve lider olarak seçilmemesidir, bu nedenle zxid değeri mevcut yeni liderden daha küçük olmalıdır. Eski lider, yeni lidere takipçi olarak katıldığında, yeni lider, eski çağ numarasıyla taahhüt edilmemiş tüm önerileri temizlemesine izin verecektir.
Lider seçildikten sonra log kurtarma aşamasına girer.Her bir takipçi düğümünün gönderdiği zxid'e göre her bir takipçiye hangi verinin gönderileceğini belirleyecek ve takipçinin veriyi bağlamasını sağlayarak maksimum commit ilkesini karşılayacak ve taahhüt edilen verinin olmasını sağlayacaktır. Follower'a kopyalayın, her takipçi veriyi eşitledikten sonra lidere bir ACK verecektir Lider, takipçinin ACK'sının yarısından fazlasını aldığında, lider bu anda çalışmaya başlar ve tüm zab protokolü atomik yayın aşamasına girebilir.
4.2 Zab, "hayalet yeniden ortaya çıkma" sorununu çözer
Bölüm 1 senaryosu için, ZAB'nin seçim aşamasının mekanizmasına göre dönem, her seçimden sonra +1 olacaktır ve bu, bir sonraki zxid turunun en yüksek 32 biti olacaktır. Dolayısıyla, 1. Tur aşaması, A, B, C'nin EpochId'sinin 1 olduğunu varsayarsak, 2.Tur aşamasında EpochId 2'dir, bu Epoch'a göre üretilen tüm zxidler A'daki tüm zxidlerden daha büyük olmalıdır. Bu nedenle, 3. Turda, B ve C'nin her ikisi de A'dan büyük olduğundan, Lider olarak A seçilmeyecektir. A, Takipçi olarak katıldıktan sonra, yeni Liderdeki veriler üzerindeki verilerin üzerine yazılacaktır. Birinci durumda zabın önlenebileceği görülebilir.
Bölüm 3.2'deki senaryo için, 2. Turdan sonra lider olarak B seçildi, hiçbir işlem gerçekleşmedi. 3. Tur seçiminde, A, B ve C'nin en son günlükleri değişmediğinden, A'nın son log zxid'i B ve C'ninkinden daha büyüktür. Bu nedenle, A lider olarak seçilecektir. A, verileri B ve C'ye kopyaladıktan sonra, "Hayalet yeniden ortaya çıkma" olgusu ortaya çıkıyor.
"Hayalet tekrarlama" problemini çözmek için, en son Zab protokolünde, her lider seçimi tamamlandıktan sonra, mevcut EpochId'i (CurrentEpoch olarak kaydedilir) kaydetmek için yerel bir dosya kaydedilecektir. Seçim sırasında, CurrentEpoch okunacak ve eklenecektir. Diğer adaylara gönderilen oy pusulaları arasında, aday, CurrentEpoch'un kendisinden daha küçük olduğunu tespit ederse, bu oy pusulasını dikkate almayacaktır, CurrentEpoch'un kendisinden daha büyük olduğunu tespit ederse, bu oy pusulasını seçecektir, eğer eşitse, zxid'i karşılaştırın. Bu nedenle, bu problem için 1. Turda, A, B ve C'nin CurrentEpoch'u 2'dir; 2.Turun CurrentEpoch'u, A 2'dir ve B'nin CurrentEpoch'u 3'tür; 3.Tur, çünkü B ve C'nin CurrentEpoch'u A'nınkinden daha büyüktür. Yani A lider olamaz.
5. Daha fazla tartışma
Alibaba Cloud'un Nuwa tutarlılık sisteminde, yaklaşım Raft ve Zab'a benziyor ve hayalet yinelemesini yaratabilecek rolün yeni bir seçim turunda lider olarak seçilememesini ve böylece hayalet günlüklerinin tekrar görünmesini engellemesini sağlıyor. Sunucu tarafında, "hayalet yeniden görünme" sorunu, yük devretme durumunda, yeni liderin mevcut kararlı dizin hakkında net olmaması, yani günlük girişinin kaydedilmiş durumda mı yoksa taahhüt edilmemiş durumda mı olduğu net değildir, bu nedenle belirli bir günlük aracılığıyla geri yüklenmesi gerekir. Belirsizliği önlemek için, gönderilen günlüklerin atılmamasını (maksimum kesinleştirme ilkesi) ve bir bölme çizgisinin (MultiPaxos StartWorking, Raft's noop, Zab's Current Epoch gibi) günlüğün işlenip işlenmeyeceğini belirlemek için kullanılması anlamına gelir. Farklı durumlar. "Hayalet yeniden ortaya çıkma" sorunu, esasen dağıtılmış sistemlerin "üçüncü durumuna" aittir, yani, bir ağ sisteminde, bir istek için üç geri dönüş sonucu vardır: başarı, başarısızlık ve bilinmeyen zaman aşımı. Bilinmeyen zaman aşımları için, sunucunun istek komutunun işleme sonucu başarılı veya başarısız olabilir, ancak ikisinden biri olmalı ve tutarsızlık olmamalıdır. İstemcide, istek bir zaman aşımı aldığında, müşteri mevcut temel durumun ne olduğunu bilmez ve başarı veya başarısızlık net değildir.Bu nedenle, genel müşterinin yaklaşımı yeniden denemektir, bu nedenle temel uygulamanın iş mantığı idempotent olmalıdır. Aksi takdirde, yeniden deneme tutarsız verilere neden olur.
Referans makale:
Bu makale resmi Ali Technology hesabından (ID: ali_tech) çoğaltılmıştır.
