CAP ve PACELC'i Doğru Okumak: "3'ten 2'sini Seç" Neden Yanlış?

Sürüm notu: Bu yazıdaki kodlar C# 14 ve .NET 10 ile derlenip denenmiştir.

Önce Tahmin Et

Bookstore'un verisi üç node'da (A, B, C) replike ediliyor. Bir gün C ile diğer ikisi arasındaki bağlantı kopuyor: network partition. Ada'nın telefonu C'ye, laptop'u A'ya bağlı. Ada telefondan sepetine bir kitap ekliyor, laptop'tan sepetindeki başka bir kitabı çıkarıyor, sonra telefondan ödemeye geçiyor.

Sepet bu sırada çalışmalı mı? Ödeme? Partition bitince sepette hangi kitaplar olur? Bir mimari toplantısında biri "bizim sistem AP (Available, Partition-tolerant), o yüzden ikisi de çalışır" ya da "bizim veritabanı CP (Consistent, Partition-tolerant), o yüzden ikisi de durur" diyor. Bu cümlelerin ikisi de neden eksik?

CAP'in Kısa Tarihi

Eric Brewer, 2000 yılındaki PODC (Principles of Distributed Computing) konferansının açılış konuşmasında bir conjecture ortaya attı: paylaşılan veri tutan bir web servisi consistency, availability ve partition tolerance property'lerinin üçünü birden sağlayamaz. İki yıl sonra Seth Gilbert ve Nancy Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services" makalesinde ifadeyi kesin tanımlarla yazdı ve ispatladı. Bugün CAP (Consistency, Availability, Partition tolerance) teoremi dediğimiz şey, Brewer'ın sezgisi değil, bu ispatın kendisidir. Ve ispatın tanımları, günlük kullanımdaki kelimelerden çok daha dardır.

Teoremin Kesin İfadesi

Gilbert ve Lynch'in tanımlarında C, bir önceki yazıdaki linearizability'dir (makalede "atomic consistency"): bütün işlemler tek bir sıraya dizilebilmeli ve her biri tek bir anda gerçekleşmiş gibi görünmeli. A, sistemdeki çökmemiş her node'un aldığı her isteğe sonunda bir cevap üretmesidir; cevabın ne kadar süreceği tanımda yoktur, ama "reddediyorum" bir cevap sayılmaz. P ise network'ün node'lar arasındaki istediği kadar mesajı kaybedebilmesidir.

Teorem şunu söyler: asynchronous bir network'te, mesajlar kaybolabiliyorsa, hem C'yi hem A'yı sağlayan bir algoritma yoktur. İspatın fikri birkaç cümleye sığar. Network iki parçaya bölünsün ve aralarında hiçbir mesaj geçmesin. Bir client birinci parçadaki bir node'a yazsın; A gereği o node yazmayı kabul edip cevap vermeli. Sonra bir client ikinci parçadaki bir node'dan okusun; A gereği o node da cevap vermeli. Ama yazmadan haberi olamaz, çünkü aradaki bütün mesajlar kayboldu. Eski değeri döndürürse C bozulur, cevap vermezse A bozulur.

"3'ten 2'sini Seç" Neden Yanlış?

CAP genelde üç köşeli bir üçgenle anlatılır ve sistemler CA (Consistent, Available), CP ya da AP diye etiketlenir. Bu özetin üç sorunu var.

Birincisi, P bir seçim değildir. Partition, sistemin başına gelen bir olaydır: switch arızası, yanlış bir firewall kuralı, uzun bir GC (garbage collector) duraklaması yüzünden heartbeat alamayan bir node. Birden fazla makineye yayılmış bir sistem "partition'a dayanıklı olmamayı" seçemez; seçebileceği tek şey partition olduğunda ne yapacağıdır. "CA sistem" ifadesi, ya tek makinede çalışan bir sistemi ya da partition olunca ne yapacağı belirsiz bir sistemi anlatır.

İkincisi, seçim yalnız partition sırasında yapılır. Partition yokken bir sistem hem linearizable hem available olabilir; CAP o zamanlar hakkında hiçbir şey söylemez. Brewer 2012'de IEEE (Institute of Electrical and Electronics Engineers) Computer dergisinde yayımlanan "CAP Twelve Years Later: How the 'Rules' Have Changed" yazısında bunu kendisi vurguladı: "üçten ikisi" formülasyonu yanıltıcıdır, çünkü partition'lar seyrektir ve partition olmadığında C ile A'dan vazgeçmek için bir sebep yoktur.

Üçüncüsü, seçim bütün sistem için tek bir kez yapılmaz. Aynı sistem bazı işlemler için C'yi, bazıları için A'yı seçebilir; aynı veritabanı istek başına farklı ayarlarla çalışabilir. Kleppmann bu yüzden 2015'teki "Please stop calling databases CP or AP" yazısında veritabanlarına bu etiketleri yapıştırmayı bırakmayı önerdi: pek çok gerçek sistem ne CAP anlamında C'yi ne de CAP anlamında A'yı sağlar.

CAP'in Söylemedikleri

CAP'in tanımları dar olduğu için, sonuçları da dardır. Teorem latency hakkında bir şey söylemez: A tanımında cevabın süresi yoktur, oysa pratikte 30 saniyede gelen bir cevap, gelmeyen bir cevaptan farksızdır. Kısmi availability hakkında bir şey söylemez: partition sırasında çoğunluk tarafındaki node'lar linearizable kalarak cevap verebilir, yalnız azınlık tarafı reddeder; CAP anlamında bu "available değil" sayılır ama kullanıcıların çoğu için sistem çalışıyordur. Linearizability dışındaki modeller hakkında bir şey söylemez: bir önceki yazıdaki haritada gördüğümüz causal consistency ya da read committed partition sırasında da sağlanabilir. Ve tek bir register'dan bahseder; transaction'lar, birden fazla key ya da failure'ın başka türleri (node çökmesi, disk kaybı) kapsamında değildir.

Bu yüzden CAP'i bir sınıflandırma aracı olarak değil, bir imkânsızlık sonucu olarak okumak gerekir: "linearizability istiyorsan, partition sırasında bazı isteklere cevap veremeyeceğini kabul et". Gerisi tasarım kararıdır ve o kararlar işlem işlem verilir.

Bookstore'da Karar: Sepet ve Ödeme

Açılıştaki senaryoyu kuralım. Üç node var; Isolate bir node'u diğerlerinden koparıyor. Sepet her durumda cevap veriyor ve partition bitince replica'lar, Dynamo makalesinde anlatıldığı gibi, ayrışan versiyonların birleşimiyle uzlaştırılıyor. Ödeme ise ancak node'ların çoğunluğuna ulaşabildiğinde kaydediliyor:

namespace Bookstore.Cap;

public sealed class Node(string name)
{
    public string Name { get; } = name;
    public HashSet<string> Cart { get; set; } = [];
    public List<string> Payments { get; } = [];
}

public sealed class Cluster
{
    private readonly HashSet<string> _isolated = [];

    public List<Node> Nodes { get; } = [new("A"), new("B"), new("C")];

    public void Isolate(string node) => _isolated.Add(node);
    public void Heal() => _isolated.Clear();

    // Partition'ın "from" ile aynı tarafındaki node'lar
    public List<Node> Reachable(string from) =>
        [.. Nodes.Where(n => _isolated.Contains(n.Name) == _isolated.Contains(from))];
}

// AP: her node cevap verir; replica'lar partition bitince uzlaştırılır
public sealed class CartService(Cluster cluster)
{
    public void Add(string via, string book) => cluster.Reachable(via).ForEach(n => n.Cart.Add(book));
    public void Remove(string via, string book) => cluster.Reachable(via).ForEach(n => n.Cart.Remove(book));
    public string Show(string via) => string.Join(", ", cluster.Reachable(via)[0].Cart.Order());

    // Dynamo tarzı uzlaştırma: ayrışan versiyonların birleşimi
    public void Reconcile()
    {
        HashSet<string> union = [.. cluster.Nodes.SelectMany(n => n.Cart)];
        cluster.Nodes.ForEach(n => n.Cart = [.. union]);
    }
}

// CP: ödeme ancak replica'ların çoğunluğuyla kaydedilir
public sealed class PaymentService(Cluster cluster)
{
    public string Charge(string via, string orderId)
    {
        List<Node> reachable = cluster.Reachable(via);
        int majority = cluster.Nodes.Count / 2 + 1;
        if (reachable.Count < majority)
        {
            return $"503 no quorum ({reachable.Count}/{cluster.Nodes.Count})";
        }
        reachable.ForEach(n => n.Payments.Add(orderId));
        return $"201 charged {orderId} on {string.Join(",", reachable.Select(n => n.Name))}";
    }
}

using Bookstore.Cap;

Cluster cluster = new();
CartService cart = new(cluster);
PaymentService payments = new(cluster);

cart.Add("A", "ddia");
cart.Add("A", "clean-code");
Console.WriteLine($"before partition : {cart.Show("A")}");

cluster.Isolate("C");                       // network partition: {A, B} | {C}
cart.Add("C", "refactoring");               // Ada'nın telefonu C ile konuşuyor
cart.Remove("A", "clean-code");             // Ada'nın laptop'u A ile konuşuyor
Console.WriteLine($"during, via A    : {cart.Show("A")}");
Console.WriteLine($"during, via C    : {cart.Show("C")}");
Console.WriteLine($"payment via C    : {payments.Charge("C", "order-1042")}");
Console.WriteLine($"payment via A    : {payments.Charge("A", "order-1042")}");

cluster.Heal();
cart.Reconcile();
Console.WriteLine($"after reconcile  : {cart.Show("A")}");

before partition : clean-code, ddia
during, via A    : ddia
during, via C    : clean-code, ddia, refactoring
payment via C    : 503 no quorum (1/3)
payment via A    : 201 charged order-1042 on A,B
after reconcile  : clean-code, ddia, refactoring

Partition sırasında iki taraf da sepete cevap verdi ve sepetler ayrıştı: A tarafında yalnız ddia, C tarafında üç kitap. Ödeme ise C tarafında reddedildi (azınlık, 1/3) ve A tarafında kabul edildi. Ada'nın telefonu bir hata gösterdi, ama aynı sipariş iki farklı tarafta iki kez ödenmedi; ödeme için doğru karar bu. Sepet içinse availability doğru tercih: müşterinin sepete kitap ekleyememesi doğrudan satış kaybı.

Ama uzlaştırmanın sonucuna bak: Ada'nın çıkardığı clean-code geri geldi. Birleşim (union) eklemeleri kaybetmez, ama silmeleri de tanımaz. Dynamo makalesi bu davranışı açıkça yazar: Amazon için bir "sepete ekle" işleminin kaybolması, silinen bir ürünün sepette yeniden belirmesinden daha kötüdür, bu yüzden bilinçli olarak kabul edilmiştir. Yani AP seçmek "her şey çalışır" demek değil; partition sonrası uzlaştırmanın semantiğini tasarlamak demek. On birinci yazıda aynı sepeti, silmeleri de doğru birleştiren bir CRDT (Conflict-free Replicated Data Type) ile yeniden yazacağız.

PACELC: Partition Yokken de Bir Seçim Var

CAP'in en büyük eksiği, sistemlerin zamanının çoğunu geçirdiği durumu, partition'sız normal çalışmayı, hiç konuşmaması. Daniel Abadi 2012'de IEEE Computer'da yayımlanan "Consistency Tradeoffs in Modern Distributed Database System Design" makalesinde bunu PACELC (if Partition: Availability or Consistency, Else: Latency or Consistency) ile tamamladı: partition (P) varsa availability (A) ile consistency (C) arasında, aksi halde (E, else) latency (L) ile consistency (C) arasında seçim yapılır. İkinci seçim her gün, her istekte yapılır: bir yazmayı başka bölgedeki replica'lar da onaylayana kadar beklersen tutarlılık kazanır, gecikme ödersin.

Bedeli kabaca hesaplamak için leader'ı Frankfurt'ta, replica'ları Dublin ve İstanbul'da olan bir kurulum düşünelim. Round-trip süreleri bir varsayım; kendi ortamında ölçmen gereken sayılar:

namespace Bookstore.Cap;

// PACELC'in "else" kolu: partition yok, ama her onay bir round trip'e mal olur
public static class Latency
{
    public static void Print()
    {
        // Frankfurt'taki leader'dan varsayılan round-trip süreleri, ms
        Dictionary<string, double> rtt = new() { ["frankfurt"] = 0, ["dublin"] = 25, ["istanbul"] = 45 };
        double local = 1; // yerel diske yazma

        double[] sorted = [.. rtt.Values.Order()];
        int majority = rtt.Count / 2 + 1;
        Console.WriteLine($"EL  ack after local write   : {local} ms, followers lag behind");
        Console.WriteLine($"EC  ack after majority {majority}/{rtt.Count}  : {local + sorted[majority - 1]} ms");
        Console.WriteLine($"EC  ack after all replicas  : {local + sorted[^1]} ms");
    }
}

EL  ack after local write   : 1 ms, followers lag behind
EC  ack after majority 2/3  : 26 ms
EC  ack after all replicas  : 46 ms

Yerel yazmayla onay vermek 1 milisaniye, ama o anda leader çökerse yazma kaybolabilir ve follower'lardan okuyanlar eski değeri görür. Çoğunluğu beklemek 26 milisaniye ve yazmayı bir node kaybına karşı güvenceye alır. Hepsini beklemek 46 milisaniye ve en yavaş bölgeyi her yazmanın kritik yoluna sokar. Bu fark, partition olsun olmasın, her yazmada ödenir. Abadi'nin vurguladığı nokta da bu: pek çok sistemin consistency'den ödün vermesinin asıl sebebi CAP değil, normal zamandaki latency'dir.

Bu harflerle sistemler iki eksende etiketlenir: partition'da PA (availability) ya da PC (consistency), normal zamanda EL (latency) ya da EC (consistency). Makalede, 2012'deki varsayılan ayarlarıyla, Dynamo, Cassandra ve Riak PA/EL; VoltDB/H-Store ve Megastore gibi tam ACID (Atomicity, Consistency, Isolation, Durability) sistemler PC/EC; MongoDB PA/EC; Yahoo'nun PNUTS (Platform for Nimble Universal Table Storage) sistemi PC/EL olarak sınıflandırılır. Bu etiketler sistemlerin bugünkü sürümleri için değil, kararın mantığını göstermek için okunmalı.

Aynı Veritabanı, Farklı Harfler

Etiketlerin yanıltıcı olmasının bir sebebi de, modern veritabanlarının bu kararı konfigürasyona, hatta isteğe bırakması. Cassandra'da aynı tablo için bir okuma ONE consistency level'ıyla (en hızlı replica'nın cevabı) yapılırken bir diğeri QUORUM ile yapılabilir; ilki PA/EL'e, ikincisi PC/EC'ye yakın davranır. MongoDB'de writeConcern, readConcern ve readPreference ayarları aynı collection üzerinde secondary'den hızlı ama eski okumayla, majority onaylı ve linearizable okuma arasında seçim yaptırır. SQL (Structured Query Language) Server availability group'unda synchronous-commit bir replica EC, asynchronous-commit bir replica EL tarafındadır; readable secondary'ye giden bir rapor sorgusu ise ayrıca eski veri görebilir.

Bunun pratik sonucu: "veritabanımız CP" cümlesi, hangi ayarla ve hangi işlem için olduğu söylenmedikçe bilgi taşımaz. Doğru soru, her işlem için şudur: partition'da bu işlem reddedilse mi, eski veriyle mi cevap verse? Normal zamanda bu işlem için kaç milisaniye ödemeye razıyız? Bookstore için kabaca: ödeme, stok düşme ve kupon kullanımı PC/EC; sepet, ürün yorumları ve öneri listesi PA/EL; katalog fiyatları ise okuma tarafında EL, fiyat değişikliği yazması tarafında EC. İlerideki System Design serisinin "Veri Katmanını Ölçeklemek: Replication, Sharding ve SQL mi NoSQL mi?" yazısı bu yazıyı tam olarak böyle bir karar lensi olarak kullanacak.

Sık Düşülen Tuzaklar

Bir veritabanını tek harfle etiketlemek. "MongoDB AP'dir" ya da "PostgreSQL CA'dır" gibi cümleler hem konfigürasyonu hem de CAP'in tanımlarını yok sayar. Garantiyi işlem ve ayar seviyesinde konuş.

"CA" seçmek. Network'e dağılmış bir sistem partition'ı reddedemez. "CA" diye tasarlanan bir sistemin partition'daki davranışı tanımsızdır ve genelde ikisinin de bozulması demektir.

CAP'i latency gerekçesiyle karıştırmak. Bir ekip "CAP yüzünden eventual consistency seçtik" dediğinde genelde gerçek sebep PACELC'in E kolundaki latency'dir. Bunu açıkça söylemek, kararın ne zaman yeniden değerlendirileceğini de netleştirir.

AP seçip uzlaştırmayı tasarlamamak. Partition bitince ayrışan veriyi kim, nasıl birleştirecek? LWW (last-write-wins) mı, birleşim mi, kullanıcıya sormak mı? Bu soru cevapsızsa AP, sessiz veri kaybı demektir.

Availability'yi CAP anlamıyla iş anlamı arasında karıştırmak. SLA (Service Level Agreement) yüzdesi, CAP'teki A değildir. Çoğunluk tarafı çalışan bir CP sistem, iş açısından yüksek availability'ye sahip olabilir.

Küçük Bir Deneme

★☆☆ Simülasyonda Isolate("C") yerine Isolate("A") çağır. Ada'nın telefonu (C) bu sefer partition'ın hangi tarafında? Ödeme hangi tarafta kabul ediliyor, sepet partition bitince ne gösteriyor? Partition'ın iki tarafını "çoğunluk" ve "azınlık" diye ayırmak neden önemli?

★★☆ Latency'ye dördüncü bir replica ekle (Virginia, 90 ms). Çoğunluk artık kaç node ve çoğunluk onayının latency'si ne oluyor? Replica eklemenin yazma latency'sini düşürmediği, hatta artırdığı durumu açıkla.

★★★ CartService'e her ekleme ve silme için bir version vector tutan bir uzlaştırma yaz: partition'da bir tarafın sildiği ve diğer tarafın hiç dokunmadığı kitap silinmiş kalsın, ama iki tarafın concurrent olarak eklediği kitap iki kez eklenmiş sayılmasın. Uzlaştırma kurallarını yazmak neden düşündüğünden zor?

Bu yazıda partition sırasında bazı node'ların cevap vermeyi reddetmesi gerektiğini gördük. Ama "hangi node'lar çoğunluk, kim leader?" sorusunun kendisi de bir anlaşma gerektirir. Bir sonraki yazıda bu anlaşmanın adını koyuyoruz: consensus, FLP (Fischer, Lynch ve Paterson) imkânsızlık sonucu ve Raft'ın leader election ile log replication'ı nasıl yaptığı.