PAXOS Algoritması: Dağıtık Sistemlerde Konsensus Sağlama

5 Ocak 2025 • ☕️ 7 dk okuma • 🏷 bilgisayar, yazılım, algoritma

Yazar tarafından şu dillere çevrildi: English

Dağıtık sistemlerde birden fazla düğüm (node) arasında karar birliğine varmak (konsensus) zor bir problemdir. PAXOS algoritması, dağıtık sistemlerde güvenilir bir şekilde konsensus sağlamak için geliştirilmiş, akademik dünyada oldukça kabul görmüş bir protokoldür. Leslie Lamport tarafından 1990’larda tanıtılmış olan bu algoritma özellikle hata toleransının kritik olduğu sistemlerde kullanılır.

1. Dağıtık Sistemlerde Konsensusun Önemi

Dağıtık sistemler farklı coğrafi konumlarda veya farklı fiziksel makinelere yayılan bileşenlerden oluşan sistemlerdir.

Örnek: Mikro hizmet mimarisi, büyük veri işleme kümeleri, veritabanı replikasyonu gibi pek çok senaryoda dağıtık yaklaşımlar kullanılmaktadır. Konsensus (consensus) dağıtık bir sistemdeki node’ların (düğümlerin), belirli bir değerin veya durumun üzerinde ortak bir karara varma sürecini ifade eder.

Örnek: Aynı verinin birçok kopyası (replicas) varsa bunların tutarlı olması için bir karara varmak gerekir. Sorun: Ağ hataları, gecikmeler ve node hataları bu süreci karmaşıklaştırır. Özetle, dağıtık sistemlerdeki en kritik problemlerden biri, farklı node’ların aynı zamanda tek bir gerçeğe (ground truth) ulaşmasını sağlamaktır.

2. Paxos Nedir?

Paxos, dağıtık sistemlerde fault-tolerant bir şekilde ortak bir karara varmak için Leslie Lamport tarafından önerilmiş bir konsensus algoritmasıdır. 1990’ların sonunda ortaya atılan bu fikir, günümüzün modern dağıtık sistemlerinde hâlâ geçerliliğini korur ve benzeri algoritmaların çoğunun temelini oluşturur.

Amaç: Sistem içindeki çoğunluk (majority) node’un aynı değeri kabul etmesini sağlamak. Önemli Not: Paxos asenkron ağ modelinde (network’teki mesajların gecikmesi bilinemez) çalışmaya uygun bir şekilde tasarlanmıştır ve “Bir değer kabul edilirse, onu garanti altına al” mantığı üzerine kurulur.

3. Temel Bileşenler ve Roller

Paxos’ta üç temel rol vardır:

Proposer (Önerici)
- Yeni bir değer önermekten sorumludur.
- Sistemde bir veya birden fazla Proposer olabilir.
Acceptor (Kabul Edici)
- Önerileri kabul veya reddetme kararı veren node’lardır.
- Bir öneriyi kabul ederse, o önerinin değerini diğer node’lara aktarır.
Learner (Öğrenici)
- Kabul edilen değeri öğrenmekle yükümlüdür.
- Tipik olarak sistemin geri kalanına son kararın ne olduğunu bildirmekle görevlidir.

Gerçek hayatta bazı node’lar aynı anda hem Proposer hem Acceptor hem de Learner rollerini üstlenebilir. Ancak algoritmanın mantığı anlaşılır olması için bu roller kavramsal olarak ayrılmıştır.

4. Paxos Algoritmasının Adımları

Paxos süreci kabaca iki (bazı modellerde üç) temel fazdan oluşur. Literatürde bu fazlar genelde Prepare ve Accept olarak geçer. Kabul edilen değer tüm Learner’lara bildirildiği aşama da Learn olarak adlandırılır.

4.1 Faz 1: Prepare (Hazırlık)

Öneri Numarası (Proposal Number):
- Her Proposer benzersiz ve monoton artan bir öneri numarası seçer (örnek: 1, 2, 3…).
- Öneri numarasının benzersiz olması önemlidir; genelde node_id + timestamp gibi stratejilerle üretilir.
Prepare Mesajı:
- Proposer “prepare(n)” mesajını, bir çoğunluk (majority) kümedeki Acceptor’lara gönderir. Burada n öneri numarasıdır.
Promise (Söz Verme):
- Eğer bir Acceptor daha önce bir öneri numarası m ≥ n ile bir söz (promise) vermediyse, Proposer’a bir “promise” mesajı yollar. Bu “Bundan daha düşük numaralı başka hiçbir öneriyi kabul etmeyeceğim” anlamına gelir.
- Ayrıca Acceptor daha önce kabul ettiği en yüksek öneri numarasına (eğer varsa) ait değeri Proposer’a bildirir.

Amaç: Proposer yeterli sayıda Acceptor’dan “promise” cevabı alarak, bundan sonraki adımda sunacağı değerin çoğunluk tarafından dikkate alındığından emin olur.

4.2 Faz 2: Accept (Kabul)

Değer Belirleme:
- Proposer Faz 1’de Acceptor’lardan aldığı yanıtları inceler.
- Eğer Acceptor’lar daha önce belirli bir değer içeren bir öneriyi kabul etmişse, Proposer bu değeri en yüksek öneri numarasına sahip olan değeri seçerek tekrar önermek durumundadır.
- Eğer hiçbir Acceptor’dan önce kabul edilmiş bir değer bilgisi gelmezse, Proposer kendi önerdiği değeri sunabilir.
Accept Mesajı:
- Proposer “accept(n, v)” (öneri numarası n, değer v) şeklinde bir mesajı aynı çoğunluk kümesine (Acceptor’lara) gönderir.
Kabul (Accept):
- Acceptor eğer “promise” gönderdiği n numaralı öneriden daha yüksek numaralı bir öneriye “promise” vermediyse, bu değeri kabul eder ve kabul ettiğini Proposer’a (ve/veya Learner’lara) iletir.

Amaç: Faz 2 sonucunda, çoğunluk en az bir kere aynı değeri kabul etmiş olur. Bir değeri çoğunluk kabul ettiğinde, o değer Paxos tarafından seçilmiş (chosen) sayılır.

4.3 Faz 3: Learn (Öğrenme)

Kabul edilen (chosen) değer, Learner’lara dağıtılır.
Learner’lar Acceptor’lardan gelen “accepted” mesajına dayanarak sonucun ne olduğunu öğrenir.
Sistemin geri kalanı da bu değer üzerinde mutabık kalmış olur.

5. Paxos’un Özellikleri

Paxos, iki kritik özelliği hedefler:

Safety (Güvenlik)
- Aynı tur içinde veya farklı turlarda olsun, iki farklı değerin aynı anda seçilmesini önler.
- Bir değer seçildiyse sistemde o değerin yerine geçecek bir başka değerin seçilmesi mümkün değildir.
Liveness (Canlılık)
- Sistem yeterince istikrarlı (stable) durumda olduğunda, önerilen değerlerin bir süre sonra mutlaka seçilmesini garanti altına alır.
- Ancak ağda kalıcı bölünmeler (network partition) veya çok sık tekrar eden hatalar varsa liveness gecikebilir.

Paxos’un güvenlik özelliği, “aynı anda iki farklı değeri seçmeme” şeklinde garanti sunarken; liveness özelliği, “eninde sonunda bir değer seçilmesi”ni garanti eder.

6. Multi-Paxos ve Gelişmiş Versiyonlar

Tek bir değer üzerinde konsensus sağlamak yerine, bir dizi değer veya bir komut dizisi üzerinde anlaşılıyor olabilir. Örneğin; bir dağıtık veritabanında sıralı bir dizi komutun (insert, update, delete) sırasını belirlemek isteyebilirsiniz.

Multi-Paxos:
- Aynı node’lar tekrar tekrar Paxos çalıştırmak yerine, lider (leader) olarak adlandırılan sabit bir Proposer atanır ve bir dizi değeri sırayla kabul ettirmeye çalışır.
- Bu sayede her turda yeni bir lider seçme işlemi yapılmaz, performans artar.
Raft, Zab vb.:
- Paxos’tan esinlenen diğer konsensus algoritmaları da “lider seçimi”, “log replikasyonu” gibi benzer adımlarla yüksek performans ve basitlik sunmaya çalışır.

7. Paxos’un Avantajları ve Dezavantajları

Avantajları:

Temel Teorik Dayanak: Literatürde en çok incelenen ve ispatlanmış konsensus algoritmalarından biri olması.
Güvenlik Garantisi: Asenkron ağ ortamlarında bile tutarlı sonuçlar vermesi.
Esneklik: Birçok senaryoya ve farklı uygulama mimarilerine uyarlanabilir.

Dezavantajları:

Uygulama Karmaşıklığı: Paxos akademik makalelerde net olsa da uygulamada kodlamak ve yönetmek zordur.
Fazlar Arasındaki Mesaj Trafiği: Faz 1 ve Faz 2 mesajlaşmalarının maliyeti yüksektir. Özellikle yüksek performans gereken sistemlerde dikkatli tasarım ister.
Liderlik Seçimi Gerekebilir: Multi-Paxos’ta lider seçimi ve liderin başarısız olması gibi ek yönetim ve hata toleransı katmanları tasarlamak gerekir.

8. Gerçek Hayat Uygulamaları

Google Chubby: Google’ın dahili dağıtık kilit sistemi, Paxos temelli bir mekanizma kullanır.
Microsoft Azure: Dağıtık veritabanı ve blob saklama altyapısında benzer algoritmalara başvurulur.
Temel Veritabanı Replikasyonu: Büyük ölçekli, yüksek erişilebilirlik gerektiren kritik sistemlerde sıklıkla Paxos ya da benzer konsensus algoritmalarından yararlanılır.

Günümüzde Paxos’un sadeleştirilmiş ve üretim ortamlarında daha kolay yönetilebilen varyantları (örn. Raft) daha popüler hale gelmiş olsa da, Paxos’un teorik altyapısı hâlâ pek çok konsensus algoritmasının temelini oluşturmaktadır.

Paxos Algoritması dağıtık sistemlerde konsensus sağlamak için en önde gelen klasik çözümlerden biridir. Ağ gecikmeleri, node arızaları ve asenkron iletişim gibi zorluklara rağmen çoğunluğun ortak bir değeri kabul etmesini garanti altına alır.

Güvenlik (Safety) ve Canlılık (Liveness) garantisi sunar.
Multi-Paxos gibi geliştirilmiş sürümleri, pratik kullanımda birden fazla değeri sırayla kabul etmede yaygın olarak kullanılır.
Tasarım ve uygulama açısından karmaşık olduğu için, pratikte Raft gibi daha anlaşılır alternatifler de tercih edilir.

Yine de Paxos, dağıtık konsensus denince akla ilk gelen ve farklı algoritmaların atası sayılan çok önemli bir paradigmadır. Özellikle yüksek erişilebilirlik ve tutarlılık gerektiren sistemlerde, Paxos benzeri mekanizmalar inşa etmek kaçınılmaz bir gereksinim haline gelmiştir.

hkucuk