WeChat PaxosStore: Paxos algoritma protokolünü basit bir şekilde açıklayın
Yazar Zheng Jianjun
Editör Cindy
"
"Geleceği tahmin etmektense, geleceği sınırlamak daha iyidir", Paxos protokolünün ana fikri bu olmalıdır. Paxos protokolünün kendisi nispeten basittir.Paxos protokolünün nasıl tasarlanacağı asıl problemdir. Bu, WeChat mühendislerinin referans amaçlı deneyimidir.
Giriş
1990 gibi erken bir tarihte, Leslie Lamport (LaTeX'teki "La", 2013'te Turing Ödülü'nü kazanan Microsoft Research'te bir bilim insanı), Bilgisayar Sistemlerinde ACM İşlemleri (TOCS) için Paxos algoritması üzerine Yarı Zamanlı Parlamento adlı bir makale sundu. Bazı eleştirmenler, makalenin özellikle yararlı olmasa da, yine de biraz ilginç olduğunu, ancak Paxos ile ilgili hikayelerin tüm arka planının silinmesi gerektiğini söyledi. Leslie Lamport kibirliydi ve eleştirmenin en ufak bir mizah anlayışına sahip olmadığını hissetti, bu yüzden makaleyi geri çekti ve artık yayınlamadı.
1998 yılına kadar kullanıcılar Paxos'u desteklemeye başladılar ve Leslie Lamport makaleyi yeniden yayınladılar, ancak 1990 versiyonuna kıyasla makale çok fazla modifikasyona sahip değildi, bu yüzden anlamak hala zor. Böylece 2001 yılında Leslie Lamport, popülerlik uğruna makaleyi sadeleştirdi ve Paxos Made Simple'ı yayınladı, bu sefer makalenin formülü yok.
Ama gerçek nedir? Herkes Paxos Made Simple'ı okumak isteyebilir. Leslie Lamport makalede aşamalı olarak ve sıfırdan Paxos protokolünü çıkardı ve bunu matematiksel tümevarımla kanıtladı. Sunum sırasından dolayı bu makalenin anlaşılması zor görünebilir.
Bu nedenle, bu arka plana dayanarak, bu makale Paxos Basit Yapımına dayalı Paxos protokolünü yeniden açıklar, iki kanıtlama yöntemi sunar ve yaygın yanlış anlamalar verir. Okuyucuların, Paxos Made Simple ile birlikte bu makaleyi okuyarak temel Paxos protokol teorisini derinlemesine anlayabilecekleri umulmaktadır.
temel kavram
-
Teklif Değeri: önerilen değer;
-
Teklif Numarası: Teklif numarası, teklif numarasının çakışmaması gerekir;
-
Teklif: Teklif = Teklif değeri + Teklif numarası;
-
Teklif veren: teklifin başlatıcısı;
-
Kabul Eden: Teklifi kabul eden;
-
Öğrenci: Önerilen öğrenci.
Tartışmayı kolaylaştırmak için, bu makalede, teklif numarası n ve teklifin değeri v ile teklif olarak {n, v} işaretleyin ve Hazırla (m) talebini vaat etmek ve teklifi kabul etmek için (m, {n, v}) işaretleyin {n, v}.
Anlaşma süreci
Aşama A
Teklif veren bir teklif numarası n seçer ve Hazırlama (n) isteklerini tüm Kabul Edenlere yayınlar.
Aşama 1 B
Kabul eden bir Hazırlama (n) isteği alır. Teklif numarası n, daha önce alınan Hazırlama talebinden büyükse, teklif numarası n'den küçük olan teklifi kabul etmeyeceğini ve n'den küçük sayı ile önceki Kabul teklifinin en büyük sayısını getireceğini vaat eder. Aksi takdirde, görmezden gelin.
Aşama II A
Teklif Veren, Kabul Edenlerin çoğunun vaatlerini aldıktan sonra, bir değeri kabul eden bir Kabul Eden bulunmazsa, kendi değerini ve tüm Kabul Edenlere n teklif numarasını başlatın, aksi takdirde, kabul edilen tüm değerlerden karşılık gelen teklif numarasını seçin. , Önerilen değer olarak, teklif numarası hala n'dir.
İkinci aşama B
Alıcı, teklifi aldıktan sonra teklif numarası verdiği sözü ihlal etmiyorsa teklifi kabul eder.
Teklif Sahibi bir Hazırlama (n) isteği gönderdikten sonra, çoğunluktan yanıt alır ve daha sonra isteğe bağlı olarak bir çoğunluk yayını Kabul isteğini seçebilirsiniz. Yanıtlanan Kabul Etme isteğini, yanıtlayan Kabul Etme'ye göndermeniz gerekmez. Bu yaygın bir durumdur. Paxos yanlış anlaşılmayı anlıyor.
özet
Yukarıdaki resimde P1, Hazırlama talebini yayınlar, ancak A3'e kaybolur, ancak A1 ve A2 başarıyla geri döner, yani Hazırlama talebi çoğunluk tarafından yanıtlanır ve ardından Kabul talebini yayınlayabilir, ancak A1'e kaybolur. A2 ve A3 teklifi başarıyla kabul etti. Bu öneri çoğunluk tarafından kabul edildiği için (A2, A3 çoğunlukta), çoğunluk tarafından kabul edilen teklife karşılık gelen değerin Seçilmiş olduğunu söylüyoruz.
Üç Kabul eden firmadan hiçbiri daha önce Kabul talebini kabul etmemiştir, bu nedenle kabul edilen teklifin iade edilmesine gerek yoktur, ancak teklif kabul edilmişse, ilk aşama B'ye göre, önceki Kabul teklifleri arasında en büyük sayısı n'den küçük olan teklif getirilmelidir.
Paxos protokolü nihayetinde hangi sorunu çözer?
Bir teklif çoğunluk tarafından kabul edildiğinde, bu teklife karşılık gelen değer Seçilmiş tarafından seçilir. Seçilmiş tarafından bir değer seçildikten sonra, etkileşim anlaşma kurallarına göre devam ettiği sürece, Seçilmiş'in sonraki değerlerinin tümü aynı değerde olacaktır, yani Bu Seçilmiş değerin tutarlılık sorunu.
Anlaşma kanıtı
Yukarıdakiler, aslında çok kesin bir matematik problemi olan temel Paxos protokolünün tüm içeriğidir. Aşağıdakiler matematiksel dille ifade edilir ve daha sonra titiz matematiksel dille kanıtlanır.
Paxos orijinal önerisi
Bir teklif {n0, v0} çoğu Kabul Eden tarafından kabul edilirse, çoğu Kabul Eden tarafından kabul edilen bir teklif {n1, v1} yoktur, burada n0 < n1, v0! = v1.
Paxos orijinal teklif geliştirme
Bir teklif {n0, v0} Kabul Edenlerin çoğunluğu tarafından kabul edilirse, {n1, v1} teklifini kabul edecek bir Kabul eden yoktur, burada n0 < n1, v0! = v1.
Paxos'un orijinal önerisi daha da güçlendirildi
Bir teklif {n0, v0} çoğu Kabul Eden tarafından kabul edilirse, o zaman Teklif Veren bir teklif vermez {n1, v1}, burada n0 < n1, v0! = v1.
Tümevarım ile kanıt
{M, v} teklifinin (kısaca teklif m) çoğunluk tarafından kabul edildiğini varsayalım, bu durumda m'den n'ye kadar olan tekliflerin değerlerinin tümü v'dir, burada n m'den küçük değildir.
İşte n için bir tümevarım hipotezi. N = m olduğunda, sonuç açıkça belirlenir.
Sonuç, n = k olduğunda, yani {m, v} önerisinin çoğunluk tarafından kabul edilmesi durumunda belirlenir,
Daha sonra, m'den k'ye karşılık gelen değerlerin tümünün v olduğu, burada k'nın m'den küçük olmadığı önerilmektedir.
N = k + 1 olduğunda, k + 1 önerisi yoksa, sonuç geçerli olur.
K + 1 teklifi varsa, karşılık gelen değer v1'dir,
Teklif m çoğunluk tarafından kabul edildiğinden, k + 1'in Hazırlanması çoğunluk tarafından taahhüt edilir ve sonucu iade edilir.
İki çoğunluk arasında bir kesişim olması gerektiği gerçeğine dayanarak, k + 1 teklifinin ilk aşaması B'nin teklifi geri getirdiğini bilmek kolaydır.
Ardından, döndürülen tekliflerden v1 seçilir, bu nedenle bu değer {t, v1} tekliflerinden seçilsin.
İkinci aşama B'ye göre, geri dönen tekliflerin en büyük sayısı t olduğundan, t > = m.
İlk aşamadan A, biliyoruz < n. Bu nedenle, karşılık gelen t değerinin v olduğu varsayılır.
Yani, v1 = v. Bu nedenle, n = k olduğu sonucuna varıldığında, n = k + 1'in kurulduğu sonucuna varılabilir.
Bu nedenle, teklif numarası m'den az olmayan herhangi bir teklif için karşılık gelen değer v'dir.
Yani önerme geçerli.
Çelişki ile kanıt
Var olduğunu varsayarsak, koşulu sağlayan en küçük teklif numarası n1 olsun.
Yani, {n1, v1} teklifleri var, burada n0 < n1, v0! = v1. ------------- (A)
Daha sonra n0, n0 + 1, n0 + 2, ..., n1-1'in v0 değerine karşılık gelmesi önerilmektedir. ------------- (B)
Bir teklif olduğu için {n1, v1}, çoğu Kabul Eden n1'in Hazırlanmasını zaten kabul etmiş ve n1'den küçük bir teklif numarasıyla teklifi kabul etmeyeceklerine söz vermiş demektir.
Ve {n0, v0} çoğu Kabul Eden tarafından kabul edildiğinden,
Dolayısıyla, hem n1'in Hazırlanmasını vaat eden hem de n0 teklifini kabul eden bir Kabul Eden vardır.
Sözleşmenin ikinci aşaması B'den bilerek, bu Kabul Eden önce {n0, v0} 'yi kabul etti.
Bu nedenle, {n1, v1} teklifini yayınlayan Teklif Sahibi çoğu Kabul eden iadeden öğrenecektir,
Numara n0'dan küçük olmayan ve v0 değerine sahip en az bir teklif kabul edildi. ------------- (C)
Anlaşmanın ikinci A aşamasından biliniyor,
Teklif Sahibi, önerilen değer olarak kabul edilen değerlerden en büyük teklif numarasına sahip olanı seçecektir.
Teklif numarasının n0'dan az olmadığı ve anlaşmanın ikinci aşaması B'nin teklif numarasının n1'den küçük olduğunu bildiği (C) 'den bilinmektedir,
Dolayısıyla (B) 'den v1 == v0 olduğunu biliyoruz, bu da (A) ile çelişir.
Yani önerme geçerli.
Yukarıdaki sertifikasyon süreci boyunca, biz de anlaşmanın ayrıntılarını gözden geçireceğiz.
-
Neden çoğunluk tarafından kabul edilmeli?
İki çoğunluk arasında bir kesişme olması gerektiğinden, Paxos protokolü genellikle 2F + 1 Acceptors'tır ve daha sonra protokolün hala normal şekilde devam etmesini ve nihayetinde belirli bir değer almasını sağlarken en fazla F Acceptors'ın durmasına izin verir.
-
Neden bir söz vermemiz gerekiyor?
A Aşamasında Teklif Sahibi seçiminin gelecekteki değişikliklerden etkilenmeyeceği garanti edilebilir. Ayrıca, bir Kabul eden için bu taahhüt, Hazırlama isteğine daha büyük bir teklif numarasıyla yanıt verme sırasını belirler ve daha küçük bir teklif numarasıyla Kabul isteğini kabul eder.
-
A Aşaması neden iade edilen sözleşmelerden en yüksek numaraya sahip olanı seçiyor?
Bu şekilde seçilen teklif sayısı, çoğunluk tarafından kabul edilen teklif sayısından az olmamalıdır ve teklif numarasına karşılık gelen değerin, Seçilmiş'in değeri olduğu varsayılabilir.
Orijinal B'nin ilk aşaması
Kabul eden, Hazırla (n) talebini alır, teklif numarası n, daha önce aldığı Hazırlama talebinden büyükse, teklif numarası n'den küçük olan teklifi kabul etmeyeceğini ve önceki Kabul teklifleri arasında en yüksek sayıya sahip teklifi getireceğini vaat eder. Aksi takdirde görmezden gelin.
Yukarıdaki ifadeyle karşılaştırıldığında "n'den küçük" eksik. Leslie Lamport'a bu konuyu e-posta yoluyla sorduktan sonra, Hazırlama talebine yanıt vermek de dahil olmak üzere bir teklifi kabul etti. Bu biraz belirsiz, ama aynı zamanda tamamen mantıklı ... Bu durumda yukarıdaki ispat düzgün olacaktır. Diğer bir deyişle, Kabul Eden tarafından kabul edilen teklifin sayısı her zaman söz verilen teklifin sayısından fazla değildir, bu nedenle bu "n'den küçük" çıkarılabilir. Gerçek mühendislik uygulamasında, genellikle yalnızca kabul edilen teklifi yalnızca en yüksek sayıda kaydederiz ve Söz verilen Hazırlama talebi en yüksek numaraya sahiptir.
Leslie Lamport ayrıca, "n'den küçük" kaldırılırsa, bir teklifin kabul edilmesi bir Hazırlama talebine yanıt verilmesini içermese bile, nihai sonucun doğru olduğunu, çünkü ilkinin açıkça ikincisini çıkarabileceğini, ancak onu kaldırmanın koşulları güçlendirdiğini belirtti.
Geri gönderilen teklif n'den büyük bir sayıya sahipse, örneğin {m, v}, o zaman m'den küçük Kabul isteklerini reddetmek için çoğunluk vaadi olmalıdır, bu nedenle {n, v} teklifi çoğunluk tarafından kabul edilemez.
öğrenme süreci
Bir teklif, Kabul Edenlerin çoğunluğu tarafından kabul edilirse, bu teklife karşılık gelen değer seçilir.
Basit ve doğrudan bir öğrenme yöntemi, Kabul Eden tarafından kabul edilen tüm teklifleri almak ve ardından hangi teklifin Kabul Edenlerin çoğunluğu tarafından kabul edildiğini görmek ve ardından teklife karşılık gelen değerin seçilmesidir.
Ek olarak, Öğrenciyi bir Teklif Veren olarak da görebilirsiniz.Protokol sürecine göre, normal bir teklif başlatın ve sonra bu teklifin çoğu Kabul Eden tarafından kabul edilip edilmediğine bakın.
Burada vurgulanan "bir değer Kabul Edenlerin çoğunluğu tarafından kabul edilir" yerine "bir teklif Kabul Edenlerin çoğunluğu tarafından kabul edilir" İkincisi ise sorun nedir?
Teklifler {3, v3}, {5, v3} sırasıyla B ve C tarafından kabul edildi, yani v3 çoğunluk tarafından kabul edildi, ancak v3'ün seçildiği (Seçildi) anlamına gelmez. Çoğunluk tarafından yalnızca {7, v1} teklifi kabul edildi (A Ve C) Kabul edin, v1 seçildi diyebiliriz ve bu seçilen değer anlaşma devam ettikçe değişmeyecektir.
sonuç olarak
"Geleceği tahmin etmektense, geleceği sınırlamak daha iyidir", Paxos protokolünün ana fikri bu olmalıdır. Paxos tarafından yazılan bu makaleyi okurken kafanız karışırsa, bir süre "kısıtlanmış" paragrafı bulmak isteyebilirsiniz. Paxos protokolünün kendisi nispeten basittir.Paxos protokolünün nasıl tasarlanacağı asıl problemdir.
Şu anda, WeChat çekirdek depolama PaxosStore'da, Paxos protokol süreci dakikada milyarlarca kez olarak adlandırılıyor ve "WeChat PaxosStore Bellek Bulutu: Bir Milyar Paxos / Min'in Zorluğu" makalesi bellek bulutu alt sistemini genişletiyor.
Gelecekte, trilyon düzeyinde toplu flash depolama, tek bir tablo milyar satırı destekleyen NewSQL çözümleri ve sektörden farklı açık kaynak uygulamaları dahil olmak üzere daha pratik çözümler yayınlayacağız.PaxosStore mimari çözümü, kiralama dışı Paxos uygulamalarına dayanmaktadır.
yazar hakkında
Zheng Jianjun , WeChat temel depolama hizmetlerinden şu anda sorumlu olan WeChat mühendisi, güçlü tutarlılık ve yüksek kullanılabilirliğe sahip büyük ölçekli dağıtılmış bir depolama sisteminin tasarımına ve geliştirilmesine adanmıştır.
Bugünün Tavsiyesi
Okumak için aşağıdaki resme tıklayın
WeChat PaxosStore bellek bulutu ortaya çıktı: Bir milyar Paxos / dakika zorluk
Çoğu insan için, büyük ölçekli uygulamaları işlemek ve yönetmek için mikro hizmet mimarisini kullanmak nispeten zor bir iştir ve karmaşık bir kapsayıcı yönetim mimarisini çalıştırmak kolay değildir. Bu nedenle, oldukça ölçeklenebilir ve yüksek performanslı bir konteyner yönetimi hizmeti olan Amazon EC2 Container Service (ECS), birçok kişi tarafından tercih edilmektedir.
Bu çevrimiçi ders, AWS baş bulut bilişim teknolojisi danışmanını, örnek olay incelemeleriyle birlikte Amazon ECS'nin nasıl daha iyi kurulacağını, yönetileceğini ve genişletileceğini ayrıntılı olarak açıklamaya davet ediyor. Tıklayın " Orijinali okuyun "Ücretsiz kayıt!
Bizi sevenler bundan hoşlanacak, bizi sevenler paylaşacak!
