Gerçek Sistemlerden Dersler: CRDT, Spanner TrueTime, CockroachDB HLC ve Jepsen

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

Önce Tahmin Et

Yedinci yazıdaki sepeti hatırla: partition sırasında Ada telefondan sepete bir kitap ekledi, laptop'tan başka bir kitabı çıkardı ve partition bitince replica'lar birleşimle (union) uzlaştırıldı. Sonuç: çıkarılan kitap sepete geri döndü. Birleşimin yerine "her iki tarafta da olanları al" (intersection) koysak, eklenen kitap kaybolurdu.

Peki koordinasyon olmadan, yani replica'lar partition sırasında birbirine hiç sormadan, hem eklemeleri hem silmeleri doğru birleştiren bir sepet mümkün mü? Ve tam tersi uçta: bir veritabanı, saatlerinin milisaniyelerce yanılabileceğini bilerek, gerçek zamana uyan (linearizable) transaction'ları nasıl sağlar?

CRDT: Koordinasyonsuz Merge

Shapiro, Preguiça, Baquero ve Zawirski'nin 2011'de tanımladığı CRDT'ler (Conflict-free Replicated Data Type), her replica'nın yazmayı yerel olarak kabul ettiği ve replica'ların durumlarını sonradan merge ettiği veri tipleridir. Merge fonksiyonu üç property'ye sahip olduğu sürece sonuç, mesajların hangi sırayla, kaç kez geldiğinden bağımsızdır: commutative (a ile b'yi merge etmek b ile a'yı merge etmekle aynı), associative (gruplama önemsiz) ve idempotent (aynı durumu iki kez merge etmek bir kez merge etmekle aynı). Matematiksel adıyla durumlar bir join-semilattice oluşturur.

Bu üç property, ikinci yazıda gördüğümüz network'ün kötü huylarının üçünü birden etkisiz kılar: mesajlar yeniden sıralanabilir (commutative), çoğaltılabilir (idempotent) ve gruplanarak ya da gecikerek gelebilir (associative). Sonuç, altıncı yazıda adını andığımız strong eventual consistency: aynı güncellemeleri almış iki replica, hangi sırayla almış olursa olsun aynı durumdadır. Burada gösterdiğimiz türe state-based CRDT denir; güncellemeleri işlem olarak gönderen ve teslim sırası hakkında daha güçlü varsayımlar yapan op-based CRDT'ler de vardır.

G-Counter ve PN-Counter

En basit CRDT, yalnız artan sayaç (G-Counter): her replica yalnız kendi slot'unu artırır, merge slot slot maksimumu alır, değer de slot'ların toplamıdır. Dördüncü yazıdaki vector clock'un merge kuralıyla aynı. Azalmaya da izin vermek için iki G-Counter kullanılır (PN-Counter): biri artışları, biri azalışları sayar. Üçüncüsü OR-Set; ona birazdan geleceğiz:

using System.Collections.Immutable;

namespace Bookstore.Crdt;

// Grow-only counter: replica başına bir slot, merge = slot slot maksimum
public sealed record GCounter(ImmutableSortedDictionary<string, long> Slots)
{
    public static GCounter Empty { get; } = new(ImmutableSortedDictionary<string, long>.Empty);

    public long Value => Slots.Values.Sum();

    public GCounter Increment(string replica, long by = 1) =>
        new(Slots.SetItem(replica, Slots.GetValueOrDefault(replica) + by));

    public GCounter Merge(GCounter other) =>
        new(other.Slots.Aggregate(Slots, (acc, kv) => acc.SetItem(kv.Key, Math.Max(acc.GetValueOrDefault(kv.Key), kv.Value))));
}

// Positive-negative counter: iki G-Counter
public sealed record PNCounter(GCounter Plus, GCounter Minus)
{
    public static PNCounter Empty { get; } = new(GCounter.Empty, GCounter.Empty);

    public long Value => Plus.Value - Minus.Value;
    public PNCounter Increment(string replica) => this with { Plus = Plus.Increment(replica) };
    public PNCounter Decrement(string replica) => this with { Minus = Minus.Increment(replica) };
    public PNCounter Merge(PNCounter other) => new(Plus.Merge(other.Plus), Minus.Merge(other.Minus));
}

// Observed-remove set: remove yalnız gördüğü add etiketlerini siler
public sealed record ORSet(ImmutableHashSet<(string Item, Guid Tag)> Adds, ImmutableHashSet<Guid> Removed)
{
    public static ORSet Empty { get; } = new([], []);

    public IEnumerable<string> Items => Adds.Where(a => !Removed.Contains(a.Tag)).Select(a => a.Item).Distinct().Order();

    public ORSet Add(string item) => this with { Adds = Adds.Add((item, Guid.NewGuid())) };

    public ORSet Remove(string item) =>
        this with { Removed = Removed.Union(Adds.Where(a => a.Item == item).Select(a => a.Tag)) };

    public ORSet Merge(ORSet other) => new(Adds.Union(other.Adds), Removed.Union(other.Removed));
}

using System.Globalization;
using Bookstore.Crdt;

CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;

// Bir kitabın "wishlist" sayısı; iki replica birbirine ulaşamazken sayıyor
GCounter istanbul = GCounter.Empty.Increment("ist").Increment("ist").Increment("ist");
GCounter frankfurt = GCounter.Empty.Increment("fra").Increment("fra");
GCounter ab = istanbul.Merge(frankfurt), ba = frankfurt.Merge(istanbul);
Console.WriteLine($"G-Counter  ist={istanbul.Value} fra={frankfurt.Value} merged={ab.Value} " +
                  $"commutative={ab.Value == ba.Value} idempotent={ab.Merge(ab).Value == ab.Value}");

PNCounter stockA = PNCounter.Empty.Increment("ist").Increment("ist").Decrement("ist");
PNCounter stockB = PNCounter.Empty.Decrement("fra");
Console.WriteLine($"PN-Counter ist={stockA.Value} fra={stockB.Value} merged={stockA.Merge(stockB).Value}");

G-Counter  ist=3 fra=2 merged=5 commutative=True idempotent=True
PN-Counter ist=1 fra=-1 merged=0

İstanbul'daki replica üç, Frankfurt'taki iki "wishlist" kaydı saydı; birleşim beş ve merge sırası ya da tekrar merge etmek sonucu değiştirmiyor. Bir LWW (last-write-wins) register'ı burada iki değerden birini seçip diğerini kaybederdi. PN-Counter da doğru topluyor: İstanbul iki giriş ve bir satış, Frankfurt bir satış gördü, sonuç sıfır.

Ama PN-Counter'ın neyi yapamadığına dikkat et. Stokta tek bir kitap varken iki replica partition sırasında birer satış kabul ederse, birleşim eksi bire iner. CRDT merge'ü garanti eder, invariant'ı (stok sıfırın altına inmez) garanti etmez. Bir invariant'ı korumak için replica'ların birbirine sorması gerekir; bu da yedinci yazıdaki CAP'in (Consistency, Availability, Partition tolerance) C tarafıdır. Pratik çözüm, stoğu replica'lara önceden pay etmek (her replica yalnız kendi payı kadar satabilir, pay bitince koordinasyon ister) ya da stoğu düşen işlemi tek bir yerde tutmaktır.

OR-Set ve Sepetin Düzeltilmesi

Sepet bir küme, ama birleşimle uzlaştırılan basit bir küme silmeyi tanımaz. OR-Set (Observed-Remove Set) her eklemeye benzersiz bir etiket verir. Silme, item'ın kendisini değil, silen replica'nın o an gördüğü etiketleri siler. Merge sırasında eklemeler ve silinen etiketler ayrı ayrı birleştirilir; bir item, silinmemiş en az bir etiketi varsa kümededir:

// CAP yazısındaki sepet, bu sefer OR-Set olarak
ORSet cart = ORSet.Empty.Add("ddia").Add("clean-code");
ORSet phone = cart.Add("refactoring");      // partition sırasında replica C
ORSet laptop = cart.Remove("clean-code");   // partition sırasında replica A
Console.WriteLine($"OR-Set     merged cart = {string.Join(", ", phone.Merge(laptop).Items)}");
ORSet again = laptop.Add("clean-code");     // remove'dan sonraki yeni bir add korunur
Console.WriteLine($"OR-Set     re-added    = {string.Join(", ", again.Merge(phone).Items)}");

OR-Set     merged cart = ddia, refactoring
OR-Set     re-added    = clean-code, ddia, refactoring

Yedinci yazıdaki senaryonun aynısı, ama bu sefer clean-code geri gelmiyor: laptop'taki silme, telefonun da gördüğü etiketi sildi. refactoring korunuyor, çünkü onun etiketini kimse görmeden silmedi. Ve silmeden sonra yapılan yeni bir ekleme yeni bir etiket ürettiği için o da korunuyor. Bir silme ile concurrent bir ekleme karşılaştığında ekleme kazanır (add-wins); sepet için doğru seçim bu, ama her domain için değil. Bedeli de var: silinen etiketler (tombstone) birikir; gerçek implementasyonlar bunları version vector'lerle sıkıştırır.

CRDT'ler bugün pek çok yerde: Riak'ın veri tipleri, Redis Enterprise'ın active-active replication'ı, Kleppmann ve arkadaşlarının Automerge'i ve Yjs gibi collaborative editing kütüphaneleri. Metin düzenleme en zor durum: birden fazla kişinin aynı metne concurrent yazdığı bir belgede her karakterin konumu bir sequence CRDT ile tutulur ve iyi bir algoritma, iki kişinin aynı noktaya yazdığı kelimeleri harf harf birbirine karıştırmamalıdır. crdt.tech bu alanın makalelerini ve implementasyonlarını bir arada topluyor.

Spanner: TrueTime ve Commit Wait

Yelpazenin diğer ucunda Google Spanner var. 2012'de OSDI (Operating Systems Design and Implementation) konferansında yayımlanan makale, dünyaya yayılmış bir veritabanında external consistency, yani altıncı yazıdaki strict serializability sağlar: bir transaction commit edildikten sonra başlayan her transaction, ondan daha büyük bir timestamp alır. Bunun için fiziksel saate güvenmek zorundadır ve üçüncü yazıda saatlerin neden güvenilmez olduğunu gördük.

Spanner'ın çözümü saatin belirsizliğini saklamamak, ölçmek. Her data center'da GPS (Global Positioning System) alıcıları ve atomik saatlerle donatılmış time master'lar var; makinelerdeki TrueTime API'si (Application Programming Interface) tek bir an değil, gerçek zamanın içinde olduğu garanti edilen bir aralık döndürür: TT.now() = [earliest, latest]. Makaleye göre bu aralığın yarı genişliği ε tipik olarak 1 ile 7 milisaniye arasında testere dişi gibi değişir, çoğu zaman yaklaşık 4 milisaniyedir.

Bir transaction commit ederken timestamp'i s = TT.now().latest olarak seçilir. Sonra commit wait gelir: TT.now().earliest s'yi geçene kadar, yani s'nin bütün makinelerde kesin olarak geçmişte kaldığı ana kadar beklenir ve kilitler ancak ondan sonra bırakılır. Ortalama bekleme yaklaşık 2ε'dir. Aynı mantığı Stopwatch'ın monotonic saatiyle simüle edelim:

using System.Diagnostics;

namespace Bookstore.Crdt;

public readonly record struct TTInterval(double Earliest, double Latest);

// TrueTime benzeri API: now() gerçek zamanı içeren bir aralık döndürür
public sealed class TrueTime(double epsilonMs)
{
    private readonly Stopwatch _clock = Stopwatch.StartNew();

    public TTInterval Now()
    {
        double t = _clock.Elapsed.TotalMilliseconds;
        return new(t - epsilonMs, t + epsilonMs);
    }

    // Commit wait: s = now().latest seç, sonra s kesin olarak geçmişte kalana kadar bekle
    public async Task<(double Timestamp, double WaitedMs)> CommitAsync()
    {
        double s = Now().Latest;
        long start = Stopwatch.GetTimestamp();
        while (Now().Earliest <= s)
        {
            await Task.Delay(1);
        }
        return (s, Stopwatch.GetElapsedTime(start).TotalMilliseconds);
    }
}

// epsilon = 4 ms ile commit wait (Spanner'daki tipik değer)
TrueTime tt = new(epsilonMs: 4);
for (int i = 0; i < 3; i++)
{
    (double ts, double waited) = await tt.CommitAsync();
    Console.WriteLine($"commit wait: timestamp={ts:F1} ms, waited {waited:F1} ms before acknowledging");
}

commit wait: timestamp=4.2 ms, waited 8.7 ms before acknowledging
commit wait: timestamp=13.3 ms, waited 9.1 ms before acknowledging
commit wait: timestamp=22.4 ms, waited 9.1 ms before acknowledging

Teorik bekleme 2ε = 8 milisaniye; ölçülen 8,7 ile 9,1 milisaniye arası, çünkü Task.Delay(1)'in çözünürlüğü bir milisaniyeden biraz kaba. Spanner'ın tasarım kararı açık: daha iyi saat donanımı ε'yi küçültür, küçük ε her yazmanın bekleme süresini kısaltır. Belirsizlik ortadan kalkmaz, ama sınırlı ve bilinir hale gelir; sistem de onu yazma latency'si olarak öder. Bu, yedinci yazıdaki PACELC'in (if Partition: Availability or Consistency, Else: Latency or Consistency) E kolunda bilinçli bir EC (Else: Consistency) seçimidir.

CockroachDB: NTP, HLC ve Uncertainty Interval

Atomik saati olmayanlar ne yapar? Cockroach Labs'in "Living Without Atomic Clocks" yazısı CockroachDB'nin cevabını anlatır. Node'lar sıradan NTP (Network Time Protocol) ile senkronize edilir ve timestamp'ler dördüncü yazıdaki hybrid logical clock'tan (HLC) gelir, böylece causal olarak sonra gelen event hep büyük timestamp alır. Saat farkı için configuration'da bir üst sınır belirlenir (varsayılan maximum offset 500 milisaniye) ve node'lar sürekli birbirinin saatini ölçer; bir node diğer node'ların en az yarısından bu sınırın yüzde 80'inden fazla saparsa kendini kapatır.

Bir transaction okurken, kendi timestamp'i ile timestamp + maximum offset arasındaki bir aralıkta (uncertainty interval) yazılmış bir değer görürse, o değerin gerçekte kendisinden önce mi sonra mı yazıldığını bilemez. Bu durumda transaction'ını o değerin hemen üstündeki bir timestamp ile yeniden başlatır (uncertainty restart). Spanner her yazmada bekler; CockroachDB yalnız belirsizlik gerçekten bir değere denk geldiğinde, okuma tarafında bekler. Bedeli garanti tarafında: CockroachDB serializable isolation ve tek key üzerinde linearizability sağlar, ama farklı key'lere dokunan causal olarak bağlı transaction'larda Spanner'ın verdiği strict serializability'yi vermez. Ve sınırın kendisi bir varsayım: saat farkı configuration'daki değeri aşarsa garanti de bozulur, bu yüzden node'ların kendini kapatması bir güvenlik mekanizmasıdır.

Jepsen: Dokümantasyon Davranış Değildir

Bu serideki her garanti bir system model'e bağlıydı. Kyle Kingsbury'nin Jepsen projesi, veritabanlarının bu garantileri gerçek failure'lar altında sağlayıp sağlamadığını test eder: client'ların işlemlerini kaydeder, network partition'ları, process çökmeleri ve saat atlamaları üretir, sonra geçmişi altıncı yazıdaki gibi bir checker ile vaat edilen modele karşı kontrol eder. Yıllar içinde test edilen sistemlerin büyük kısmında vaat ile davranış arasında fark bulundu ve bulguların çoğu düzeltildi.

İki örnek bu seriyle doğrudan bağlantılı. 2020'deki PostgreSQL 12.3 analizi, serializable isolation'da hiçbir failure üretmeden, sağlıklı tek bir node'da G2-item anomalisi (transaction'ların birbirinin yazmasını görmeden ilerlediği bir anti-dependency döngüsü) buldu; sebep serializable snapshot isolation'ın conflict tespitindeki bir hataydı, test edilen 9.5'ten 13'e bütün sürümlerde vardı; rapor yayımlandığında düzeltme commit edilmiş ve Ağustos 2020'deki minor sürümler için planlanmıştı. Aynı rapor, PostgreSQL'in "repeatable read" dediği seviyenin aslında snapshot isolation olduğunu ve dokümantasyonun bunu açıkça söylemesi gerektiğini not etti. Yine 2020'deki etcd 3.4.3 analizi, key-value işlemlerinde strict serializability gözlemledi, ama etcd'nin kilitlerinin temelden güvensiz olduğunu, sağlıklı bir cluster'da bile iki process'in aynı kilidi aynı anda tutabildiğini gösterdi ve onuncu yazıdaki çözümü önerdi: kilit key'inin revision'ını fencing token olarak kullanmak.

Ders: bir garantiyi dokümantasyondan değil, hangi failure'lar altında test edildiğinden oku. Kullandığın veritabanının Jepsen raporu varsa oku; yoksa kritik garantileri kendi ortamında, kendi failure senaryolarınla test et.

Serinin Özeti: Hangi Garanti, Hangi Bedel?

On bir yazıda gördüğümüz mekanizmaların her biri bir garanti verir ve bir bedel ödetir. Bir mimari kararında aradığın şey "en güçlü garanti" değil, işlemin ihtiyaç duyduğu garantiyi en düşük bedelle veren mekanizma:

Sık Düşülen Tuzaklar

CRDT'yi her şeyin çözümü sanmak. CRDT merge'ü garanti eder, iş kurallarını değil. "Stok negatif olamaz" ya da "bir kupon bir kez kullanılır" gibi invariant'lar koordinasyon ister.

Add-wins'i her domain için doğru sanmak. Sepette eklemenin kazanması makul; bir erişim izinleri listesinde, concurrent bir silme ile eklemeden eklemenin kazanması güvenlik açığı olabilir. Remove-wins varyantları da var; semantik bilinçli seçilmeli.

Spanner tarzı garantileri saat altyapısı olmadan beklemek. TrueTime'ın değeri, sınırlı ve ölçülen ε'den gelir. Sıradan NTP ile çalışan bir sistemde aynı garanti ya daha uzun beklemeyle ya da CockroachDB gibi daha zayıf bir garantiyle gelir.

Maksimum saat farkı ayarını izlemeden yükseltmek. CockroachDB tarzı sistemlerde bu değer hem bir performans ayarı (restart'lar) hem bir doğruluk varsayımıdır; saat senkronizasyonunu izlemeden artırmak garantiyi sessizce zayıflatır.

"Bizim veritabanımız bunu garanti ediyor" demek. Hangi sürüm, hangi ayar, hangi failure altında? Jepsen'in bulguları, bu sorunun cevabının çoğu zaman dokümantasyonda olmadığını gösteriyor.

Küçük Bir Deneme

★☆☆ PN-Counter'da stoğu 1 olarak başlat (İstanbul'da bir giriş), sonra iki replica'da birer satış yap ve merge et. Sonuç ne? Bu durumu satışın kendisinde engellemek için ne gerekirdi?

★★☆ ORSet'e bir remove-wins varyantı ekle: concurrent bir ekleme ile silme karşılaştığında silme kazansın. Sepet senaryosunu her iki varyantla çalıştır; hangisi hangi domain için doğru?

★★★ TrueTime'a ε'nin 30 saniyede bir 1'den 7 milisaniyeye testere dişi gibi büyüdüğü bir model ekle ve 1000 commit için ortalama commit wait süresini ölç. Ardından ε'yi sabit 250 milisaniye yap (sıradan NTP ile internet üzerinden senkronize edilen bir makineyi düşün). Commit wait yaklaşımı bu sayılarla hâlâ makul mü?

Seri burada bitiyor. Partial failure ile başladık, saatlerin ve sıralamanın neden zor olduğunu, replica'ların nasıl anlaşıp anlaşamadığını, CAP ve PACELC'in gerçekte ne söylediğini, consensus'u, two-phase commit'i (2PC) ve kilitleri gördük; son olarak gerçek sistemlerin bu sınırlarla nasıl yaşadığına baktık. Bundan sonra bir veritabanının, cache'in ya da broker'ın dokümantasyonunda "consistent", "exactly-once" ya da "highly available" gördüğünde, ilk sorun şu olsun: hangi model, hangi failure'lar altında ve bedeli ne?