PAXOS Algoritması

Bu yazımızda Paxos Blockchain ve piChain blokzincir ağlarında uzlaşı (consensus) algoritması olarak kullanılan PAXOS algoritmasını inceleyeceğiz. Gelin basit sorulara bulacağımız cevaplarla PAXOS algoritmasını kavrayalım.

  1. PAXOS Nedir?

PAXOS bir İyonya adasının ismidir. İyonya döneminde Paxos adası Ege Denizi’ndeki gelişen ticaret merkezlerinden biridir. Bunun beraberinde getirdiği zenginlik Paxos’ta yaşayan insanların teokratik yönetim anlayışını terkedip meclis hükumeti yönetimine geçmeleriyle son bulur. Fakat, bununla da kalınmaz. Dönemin meclis üyeleri ömürlerini bu meclise adamaktansa ticaret yapıp zengin olmanın derdine düşerler. Bunu takip eden zamanda kısmi zamanlı meclis üyeliği yapmaya başlarlar. Meclis, milletvekillerinin zaman zaman meclise gelip zaman zaman gelmediği şu durumda bir şekilde işleyişini sorunsuz devam ettirmelidir. Bilgisayar bilimlerinde milletvekilinin karşılığı bilgisayar/node/process tir. Bir milletvekilinin meclisi terketmesi ise bir bilgisayarın başarısız olması (failing) anlamına gelmektedir.

Bilgisayar bilimlerindeki PAXOS ise uzlaşıya varmak adına üretilmiş bir dağıtık algoritmalar ailesidir. Aile denmektedir çünkü; ilk olarak 1998 yılında ortaya çıkan bu algoritmanın daha sonraki yıllarda çıkan türlü versiyonları bulunmaktadır.

Kaynak: http://paxos.systems/variants.html

Sistemler Neden Bir Uzlaşıya Varmaya İhtiyaç Duyarlar?

Yanıt çok basit. Yüksek kaynak gerektiren bir işlemi bir bilgisayar ile gerçekleştiremiyorsak o bilgisayarın kaynaklarını artırırız. Fakat sonsuza kadar tek bir bilgisayara kaynak ekleyerek bunu sürdüremeyiz. Bu durumda ihtiyaçlarımıza kaynak oluşturmak için bir bilgisayarlar kümesi/topluluğu kullanmamız gerekecektir. Bu kümedeki birbirinden farklı makinelerin bir işlemi gerçekletirirken vereceği tepki, oluşturacağı çıktı veya kaydedeceği sistem son durumu aynı olmalıdır ki sistem doğru ve güvenilir olsun. İşte bu amaç uğruna, kümedeki makinelerin bir işlemin kayda geçmesi için bir uzlaşıya varmaları gerekmektedir. Sistemdeki çoğunluk karar ne ise bu küme tek bir makine gibi o kararı vermiştir denilebilir.

PAXOS Algoritması ile Uzlaşıya Varmak Ne Demektir?

Maddeler halinde sıralarsak;

  • Uzlaşı, 2N adet düğümün bulunduğu bir sistemde en az N+1 makine tarafından aynı sonuçta karar kılınmasıdır.
  • Eğer kümedeki herhangi bir düğümün verdiği karar çoğunluğun verdiği karardan farklıysa bu düğüm kendi kararında ısrarcı olmaz ve çoğunluğun karar verdiği sonucu kabul eder ve aynı sonucu bildirir.
  • Sonuç olarak ulaşılan uzlaşı ağdaki her düğüm tarafından bilinmektedir.

PAXOS Algoritmasının Temelleri

  1. Bu algoritmaya göre ağda bulunan düğümler aşağıdaki rollerden en az birine sahiptir fakat bu rollerin hepsine de sahip olabilir:

Önerenler (Proposers): Üzerinde uzlaşmaya varılan değeri öneren düğümlerdir.

Kabul Edenler (Acceptors): Üzerinde uzlaşmaya varılan değerleri kabul ederek uzlaşıya katılan düğümlerdir.

Öğreniciler (Learners): Üzerinde uzlaşılan değeri Kabul Eden Düğümlerin bildirmesinden sonra öğrenen düğümlerdir.

Yukarıdaki rollerden herhangi birine sahip olan bu düğümlere, daha önce uzlaşmaya vardıkları değerler sorulabilir. Bu düğümler bunlara cevap vermek zorundadırlar. Yani daha önce uzlaşıya varılmak üzere söylenen değerlerin kaydını tutmaktadırlar.

Ağdaki bütün düğümler Kabul Eden Düğümlerin sayısı kaç olunca çoğunluğa ulaştığını bilmek zorundadırlar. Aksi durumda çoğunluk kararı verilemez ve uzlaşıya varılamaz.

PAXOS düğümleri ısrarcı olmak zorundadırlar. İletişim kanallarında hatalar oluşsa bile daha önce hangi değerde uzlaşıya vardıklarını hatırlamak zorundadırlar.

Bir değerde uzlaşıya varıldığında başka bir değer işleme alınamaz. Başka bir değerin işleme alınması ancak ve ancak bir başka iterasyonda mümkün olabilir.

PAXOS algoritmasını başlangıç versiyonu iki aşamadan oluşmaktadır ve bu aşamalar şu biçimdedir:

  • Aşama 1: Proposer düğüm çalışmakta olan bütün Acceptor düğümlere daha önce diğer herhangi bir Proposer’dan bir öneri alıp almadıklarını sorar. Eğer Proposer’a verilen cevap hayırsa Proposer yeni bir değer önerir.
  • Aşama 2: Kabul Eden Düğümlerin çoğunluğu bu değerde uzlaşırsa uzlaşı değeri budur.

Aşağıdaki görselde 1 Proposer ve 3 Acceptor’un bulunduğu bir senaryo ele alınmıştır.

Kaynak: Doktora Dersi Sunumum

Buradaki ID değeri eşsiz (unique) ve artan zamanla birlikte artan bir değer olmalıdır. Eşsiz olması için nanosaniye seviyesindeki zamandamgası değerleri veya ardışık artan tamsayılar kullanılabilir.

PREPARE ID mesajı ile uzlaşıya varılmak üzere bir değer önerilir. Eğer Acceptor düğümler bu ID değerinden daha yüksek bir ID’ye sahip bir PREPARE mesajına PROMISE (söz) vermedilerse bu değere söz verebilirler. Bu ID den daha yüksek bir ID ye sahip bir PREPARE mesajı daha önce Acceptor’lara ulaştıysa küçük ID ye sahip mesaj reddedilir. Eğer Acceptor düğümlerin çoğu bir ID ile gelen değerde uzlaşıya vardılarsa daha küçük bir ID ile gelen herhangi bir değer her ne olursa olsun uzlaşı değeri olarak kabul göremez.

Proposer düğüm Acceptor düğümlerin çoğunluk kısmının söz mesajını aldıktan sonra, kabul aldığı ID ile birlikte uzlaşıya varılan değeri kabul etmeleri için tüm Acceptor düğümlere ACCEPT-REQUEST (kabul-ricası) mesajı gönderir. Acceptor düğümler bu ID ile gelen değeri kabul ettiklerini hem Proposer düğüme hem de öğrenici rolüne sahip Learner düğümlerine bildirirler. Uzlaşıya varılan şey ID değil bu ID’ye sahip mesajın içerdiği değerdir. Yukarıdaki örnek özelinde uzlaşı değeri ‘cat’ tir diyebiliriz.

Kronolojik olarak daha sonra olan fakat daha düşük ID ye sahip bir mesajın varlığı söz konusuysa ve kronolojik olarak daha önce olan ve daha yüksek ID ye sahip mesajın sözü daha önce Acceptor düğümlerin çoğunluğu tarafından verilmişse düşük ID ye sahip mesajın bir geçerliliği olmaz. Aşağıdaki görselde bu durum ifade edilmiştir:

Paralel doğrular zaman düzlemindedir.

Referanslar

  1. Lamport, L. (1998). The part-time parliament. ACM Transactions on Computer Systems (TOCS), 16(2), 133-169.
  2. Lamport, L. (2001). Paxos made simple. ACM Sigact News, 32(4), 18-25.
  3. https://www.youtube.com/watch?v=d7nAGI_NZPk
  4. https://www.cs.rutgers.edu/~pxk/417/notes/paxos.html

  • Kerem Ataşen
  • • PhD Student at ITU Computer Engineering Department
    • Research Assisstant at Kirklareli University Software Engineering Department

Leave a Comment

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir