System Model'leri: Synchronous, Asynchronous Network, Crash-Stop, Crash-Recovery ve Byzantine Failure

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

Önce Tahmin Et

Bookstore'un OrderService'i her sipariş için Inventory'ye bir OrderPlaced message'ı gönderiyor. Arada mesajların beşte birini kaybeden kötü bir network var. Ekip "message kaybolmasın" diye basit bir kural koyuyor: ack gelene kadar tekrar gönder. Ack de aynı network'ten döndüğü için o da beşte bir ihtimalle kayboluyor.

1000 sipariş gönderildiğinde Inventory kaç farklı sipariş görür? Peki toplamda kaç kez stok düşmeye çalışır? Bu yazının sonunda iki sorunun da gerçek cevabı ve neden "tam bir kez" diye bir seçeneğin olmadığı belli olacak.

Neden Bir Model Gerekir?

Bir önceki yazıda belirsizliği bir HTTP (Hypertext Transfer Protocol) çağrısında yaşadık: timeout geldi ve isteğin ne olduğunu bilemedik. Bunun üzerine bir algoritma kurmak istediğinde ilk iş, hangi kötülüklere karşı dayanıklı olduğunu söylemektir. "Network bazen mesaj kaybeder" mi, "mesajları değiştirebilir" mi? "Node çökerse bir daha dönmez" mi, "diskini koruyarak geri döner" mi? "Mesajlar en geç 100 milisaniyede ulaşır" mı, "ne zaman ulaşacağı belli değil" mi?

Bu varsayımların toplamına system model denir. Dağıtık algoritmalar literatürü her sonucu bir modele bağlar: Raft "crash-recovery node'lar, fair-loss link'ler, partially synchronous network" varsayar; Byzantine fault tolerant protokoller node'ların yalan söyleyebileceğini varsayar ve bunun bedelini daha fazla node ve mesajla öder. Modeli bilmeden bir sistemin garantisini okursan, o garantinin hangi koşulda geçersiz olduğunu da bilemezsin. Kleppmann'ın ders notları modeli üç eksende kurar: network, node davranışı ve zamanlama. Bu yazı da aynı sırayı izliyor.

Network: Reliable, Fair-Loss ve Arbitrary Link

İki node arasındaki bağlantı için üç model vardır. Reliable link, gönderilen her message'ın bir kez ve mutlaka ulaştığını varsayar; mesajlar yeniden sıralanabilir ama kaybolmaz. Fair-loss link, mesajların kaybolabileceğini, çoğaltılabileceğini ve yeniden sıralanabileceğini ama sonsuz kez tekrar denersen sonunda geçeceğini varsayar. Arbitrary link'te ise araya giren bir saldırgan mesajları okuyabilir, değiştirebilir ya da sahte mesaj üretebilir.

Gerçek network fair-loss'a yakındır. TCP (Transmission Control Protocol) tek bir bağlantı içinde kayıp paketleri yeniden gönderip sıralayarak reliable link'e benzer bir şey sunar, ama bağlantı koptuğu anda o garanti biter ve yarıda kalan isteği uygulama yeniden göndermek zorunda kalır. Arbitrary link'i de TLS (Transport Layer Security) ile fair-loss'a indiririz: şifreleme ve bütünlük kontrolü mesajın değiştirilmesini fark edilir kılar, ama saldırganın paketleri düşürmesini engelleyemez.

Fair-loss link'i bir Channel<T> ile simüle edelim. Her message sabit bir olasılıkla düşürülüyor:

using System.Threading.Channels;

namespace Bookstore.Simulation;

public record Message(int Id, string Body);

// Fair-loss link: her message sabit bir olasılıkla düşürülür
public sealed class LossyLink(double dropRate, int seed)
{
    private readonly Channel<Message> _channel = Channel.CreateUnbounded<Message>();
    private readonly Random _random = new(seed);

    public int Dropped { get; private set; }

    public ChannelReader<Message> Reader => _channel.Reader;

    public void Send(Message message)
    {
        if (_random.NextDouble() < dropRate)
        {
            Dropped++;
            return;
        }
        _channel.Writer.TryWrite(message);
    }

    public void Close() => _channel.Writer.Complete();
}

İlk deneme at-most-once: her siparişi bir kez gönder, hiç tekrar deneme. İkincisi at-least-once: ack gelene kadar tekrar gönder, ack da kayıplı bir link'ten dönsün. Rastgelelik sabit seed'li, böylece koşu tekrarlanabilir:

using Bookstore.Simulation;

// 1) At-most-once: bir kez gönder, asla tekrar deneme
LossyLink link = new(dropRate: 0.2, seed: 42);
for (int i = 1; i <= 1000; i++)
{
    link.Send(new Message(i, $"OrderPlaced {i}"));
}
link.Close();
int received = 0;
await foreach (Message _ in link.Reader.ReadAllAsync())
{
    received++;
}
Console.WriteLine($"at-most-once : sent=1000 received={received} lost={link.Dropped}");

// 2) At-least-once: ack gelene kadar tekrar gönder; ack da kayıplı bir link'ten döner
LossyLink requests = new(dropRate: 0.2, seed: 7);
LossyLink acks = new(dropRate: 0.2, seed: 8);
Dictionary<int, int> deliveries = [];
for (int i = 1; i <= 1000; i++)
{
    bool acked = false;
    while (!acked)
    {
        requests.Send(new Message(i, $"OrderPlaced {i}"));
        if (requests.Reader.TryRead(out Message? delivered))
        {
            deliveries[delivered.Id] = deliveries.GetValueOrDefault(delivered.Id) + 1;
            acks.Send(new Message(delivered.Id, "ack"));
        }
        acked = acks.Reader.TryRead(out _);
    }
}
int duplicates = deliveries.Values.Sum(count => count - 1);
Console.WriteLine($"at-least-once: distinct={deliveries.Count} duplicates={duplicates} " +
                  $"lost requests={requests.Dropped} lost acks={acks.Dropped}");

at-most-once : sent=1000 received=774 lost=226
at-least-once: distinct=1000 duplicates=271 lost requests=354 lost acks=271

At-most-once 1000 siparişin 226'sını kaybetti. At-least-once hiçbirini kaybetmedi ama Inventory 271 siparişi iki kez işledi ve bu sayı kaybolan ack sayısıyla birebir aynı. Tesadüf değil: istek ulaştığı halde ack kaybolduğunda gönderen, isteğin ulaşmadığı durumla bunu ayırt edemez ve tekrar gönderir. Her kayıp ack bir duplicate demek. Fair-loss link'e retry eklemek onu reliable link'e çevirir, ama yalnız "kaybolmama" anlamında; "çoğalmama" için alıcı tarafında deduplication gerekir.

Two Generals ve Exactly-Once'ın Neden İmkânsız Olduğu

Bu ikilemin klasik adı Two Generals problemidir (Akkoyunlu, Ekanadham ve Huber'in 1975 makalesinde ortaya çıktı, adını Jim Gray 1978'de koydu). İki ordu bir şehri ancak aynı anda saldırırlarsa alabilir; generaller birbirine yalnız düşman bölgesinden geçen ulaklarla haber yollayabilir ve ulaklar yakalanabilir. Birinci general "şafakta saldırıyoruz" der. İkinci general mesajı aldığını bildirmek için ulak yollar; ama bu ulağın ulaşıp ulaşmadığını bilmeden saldıramaz, o yüzden birinci general de "onayını aldım" ulağı yollamalıdır, ve bu böyle sonsuza kadar gider. Sonlu sayıda mesajla iki tarafın da emin olduğu bir anlaşma mümkün değildir, çünkü son mesajın kaybolması durumunda gönderen davranışını değiştiremez.

Ödeme senaryosu da aynı yapıdadır: online mağaza ve ödeme sağlayıcısı "sipariş tamam" konusunda anlaşmak istiyor. Bunun pratik sonucu, mesaj teslimi için üç seçeneğin olması: at-most-once (kaybedebilirim ama çoğaltmam), at-least-once (çoğaltabilirim ama kaybetmem) ve hiçbir network'ün tek başına veremeyeceği exactly-once. Broker'ların "exactly-once" diye pazarladığı şey, aslında at-least-once teslim artı alıcı tarafta idempotent işleme ya da deduplication'dır; doğru adı "effectively once"tır. Messaging ve Event-Driven Architecture serisinin "Delivery Guarantee'leri: At-Most-Once, At-Least-Once ve "Exactly-Once" Gerçeği" yazısı bu ayrımı broker'lar üzerinden işliyor; burada gördüğün şey onun teorik tabanı.

Byzantine Generals: Node Yalan Söylerse

Two Generals'ta generaller dürüst, sorun ulaklarda. Lamport, Shostak ve Pease'in 1982 tarihli "The Byzantine Generals Problem" makalesinde ise generallerin bir kısmı hain olabilir: farklı generallere farklı mesajlar gönderebilir, sahte emir uydurabilir. Makalenin sonucu, f hain generale dayanmak için en az 3f + 1 general gerektiği (imzasız mesajlarla). Yani tek bir hainle başa çıkmak için dört node, iki hain için yedi node.

Bir şirketin kendi data center'ında çalışan sistemlerin çoğu bu modeli kullanmaz; node'ların kötü niyetli olmadığını varsayar. Byzantine fault tolerance, birbirine güvenmeyen tarafların ortak bir defter tuttuğu blockchain'lerde ve tek bir sensörün hatalı veri vermesinin uçağı düşürebileceği havacılık sistemlerinde gereklidir. Yine de "node yalan söylemez" varsayımını bilinçli yapmak gerekir: bozuk bir disk ya da bellekte bir bit hatası da yanlış veri üretir. Checksum'lar ve input doğrulaması bu yüzden Byzantine olmayan sistemlerde de vardır; yalnız hedefleri kötü niyet değil, kazadır.

Node Failure Modelleri: Crash-Stop, Crash-Recovery, Byzantine

Crash-stop modelinde bir node çöktüğünde sonsuza kadar çöker; bir daha mesaj göndermez, almaz. Crash-recovery modelinde node çöker, bir süre sonra geri döner; bellekteki her şey kaybolmuştur, yalnız kalıcı depolamaya (diske) yazdıkları kalır. Byzantine modelinde node keyfi davranır.

.NET dünyasında çalışan bir servis, pratikte crash-recovery modeline uyar. Kubernetes bir pod'u öldürüp yeniden başlattığında process'in bellekteki ConcurrentDictionary'si, static field'ları, MemoryCache'i gider; veritabanına commit edilmiş olanlar kalır. Bu ayrım algoritma seviyesinde kritiktir: Raft'ta bir node'un verdiği oy ve gördüğü en yüksek term diske yazılmadan cevap gönderilmez, çünkü yeniden başladığında aynı term'de ikinci bir oy vermesi iki leader seçilmesine yol açabilir. "Diske yazıldı" demek için de FileStream.Flush(flushToDisk: true) gibi işletim sisteminin cache'ini atlayan bir çağrı gerekir; yalnız Write çağırmak verinin işletim sisteminin page cache'inde beklediği anlamına gelir.

Timing: Synchronous, Partially Synchronous, Asynchronous

Synchronous modelde mesaj gecikmesinin ve process'lerin çalışma hızının bilinen bir üst sınırı vardır: "her mesaj en geç 10 milisaniyede ulaşır". Bu varsayım altında algoritma yazmak kolaydır, çünkü 10 milisaniyede cevap gelmeyen node kesinlikle çökmüştür. Asynchronous modelde hiçbir üst sınır yoktur; mesaj ulaşır ama ne zaman ulaşacağı belli değildir ve process'ler keyfi süre duraklayabilir. Bu modelde yavaş bir node ile çökmüş bir node ayırt edilemez.

Gerçek sistemler ikisinin arasındadır. Dwork, Lynch ve Stockmeyer'in 1988'de tanımladığı partially synchronous model bunu yakalar: sistem çoğu zaman synchronous gibi davranır, ama bazen sınırsız sürelerle asynchronous'a kayar. Switch'lerin queue'ları dolar, bir sanal makine başka bir tenant yüzünden CPU (Central Processing Unit) zamanı alamaz, garbage collector (GC) stop-the-world duraklaması yapar, işletim sistemi belleği swap'e atar. Bunların hepsi geçicidir ama ne kadar süreceği belli değildir. Bir algoritmanın safety garantisini synchronous varsayıma bağlaması bu yüzden tehlikelidir; doğru tasarım, safety'yi asynchronous modelde korur, yalnız liveness için (ilerleme için) zamanlamaya güvenir. Bu ayrıma birazdan döneceğiz.

Failure Detector ve Timeout Seçimi

Bir node'un çöktüğünü anlamanın tek pratik yolu, ondan bir süre haber alamamaktır. Timeout tabanlı failure detector her node'dan düzenli heartbeat bekler; belirli bir süre heartbeat gelmezse node'dan şüphelenir. Asynchronous modelde böyle bir detector mükemmel olamaz: çok kısa timeout canlı ama yavaş node'ları ölü ilan eder (false positive), çok uzun timeout gerçekten çökmüş bir node'u geç fark eder. Bunu görmek için bir saatlik simüle edilmiş trafik üretelim. Node her 100 milisaniyede heartbeat gönderiyor, hiç çökmüyor; network gecikmesi çoğunlukla birkaç milisaniye ama arada uzun; seyrek de olsa gönderen 0,3 ile 4 saniye arası GC duraklamasına giriyor:

namespace Bookstore.Simulation;

// Simüle edilmiş zaman: node her 100 ms'de heartbeat gönderir ve hiç çökmez
public static class FailureDetectorExperiment
{
    public static void Run()
    {
        Random random = new(2026);
        List<double> arrivals = [];
        double now = 0;
        while (now < 3_600_000) // simüle edilmiş bir saat
        {
            if (random.NextDouble() < 0.0005)
            {
                now += random.Next(300, 4000); // gönderen tarafta stop-the-world GC duraklaması
            }
            double networkDelay = 2 + -8 * Math.Log(1 - random.NextDouble()); // exponential dağılım: çoğu kısa, arada uzun
            arrivals.Add(now + networkDelay);
            now += 100;
        }
        arrivals.Sort();

        Console.WriteLine("timeout(ms)  false suspicions/hour  real crash noticed after(ms)");
        foreach (int timeoutMs in new[] { 150, 250, 500, 1000, 5000 })
        {
            int suspicions = 0;
            for (int i = 1; i < arrivals.Count; i++)
            {
                if (arrivals[i] - arrivals[i - 1] > timeoutMs)
                {
                    suspicions++;
                }
            }
            Console.WriteLine($"{timeoutMs,11}  {suspicions,21}  {timeoutMs,28}");
        }
    }
}

timeout(ms)  false suspicions/hour  real crash noticed after(ms)
        150                     39                           150
        250                     20                           250
        500                     19                           500
       1000                     16                          1000
       5000                      0                          5000

Hiç çökmeyen bir node için 150 milisaniyelik timeout saatte 39 kez yanlış alarm verdi. Her alarm gerçek bir sistemde bir failover, bir leader seçimi ya da bir circuit breaker'ın açılması demek; failover'ın kendisi yük yaratıp yeni timeout'lara sebep olabilir. Timeout'u 5 saniyeye çıkarınca yanlış alarm sıfırlandı, ama gerçek bir çöküşü fark etmek de 5 saniye sürüyor. 250 ile 1000 milisaniye arasında yanlış alarm sayısının neredeyse değişmemesi de öğretici: o bölgedeki alarmların hepsi GC duraklamalarından geliyor ve duraklamadan uzun bir timeout seçmedikçe onları elemiyorsun.

Pratikte timeout, gözlemlenen gecikme dağılımına göre seçilir (ör. p99.9'un birkaç katı) ve sabit olmak zorunda değildir. Hayashibara ve arkadaşlarının 2004 tarihli phi accrual failure detector'ü (Akka ve Cassandra'da kullanılır) "çöktü / çökmedi" yerine heartbeat aralıklarının geçmiş dağılımına göre bir şüphe seviyesi üretir; uygulama eşiği kendi maliyetine göre seçer.

Safety ve Liveness

Bir algoritmanın garantileri iki türe ayrılır. Safety, "kötü bir şey asla olmaz" demektir: iki leader aynı term'de seçilmez, aynı ödeme iki kez alınmaz, commit edilmiş veri kaybolmaz. Safety ihlali sonlu bir anda gözlemlenebilir ve geri alınamaz. Liveness ise "iyi bir şey sonunda olur" demektir: bir leader eninde sonunda seçilir, her istek sonunda cevaplanır. Liveness ihlali hiçbir sonlu anda kesin olarak gösterilemez, çünkü "biraz daha bekleseydin olacaktı" denebilir. Kavramı Lamport 1977'de ortaya attı, Alpern ve Schneider 1985'te biçimsel olarak tanımladı.

Bu ayrım partial synchrony ile birleşince dağıtık sistem tasarımının ana kuralını verir: safety'yi zamanlamaya bağlama, liveness'ı bağlayabilirsin. Raft iki leader'ın aynı anda commit etmesini timeout'larla değil, term numaraları ve çoğunluk oylarıyla engeller; timeout'u yalnız "yeni seçim başlat" kararı için kullanır. Network ne kadar kötüleşirse kötüleşsin Raft yanlış bir şey commit etmez, sadece ilerleyemeyebilir. Onuncu yazıda göreceğimiz lease tabanlı kilitler ise safety'yi doğrudan saatlere bağladığı için GC duraklamasında bozulur.

Sık Düşülen Tuzaklar

Model belirtmeden garanti okumak. "Bu sistem tutarlıdır" cümlesi, "hangi failure'lara karşı?" sorusunun cevabı olmadan anlamsızdır. Bir veritabanının dokümantasyonunda replication garantisini okurken network partition'ı, node'un diski kaybetmesini ve saat kaymasını ayrı ayrı ara.

Exactly-once vaadine güvenmek. Kütüphane ya da broker "exactly-once" diyorsa, hangi sınırın içinde dediğine bak; o sınırın dışına (veritabanına, e-posta servisine, ödeme sağlayıcısına) çıkan her yan etki için idempotency senin işin.

Belleği kalıcı sanmak. Crash-recovery modelinde process'in belleği bir sonraki başlangıca taşınmaz. "Bu message'ı işledim" bilgisini bir HashSet<Guid>'te tutan bir consumer, yeniden başladığında her şeyi baştan işler.

Timeout'u tahminle seçmek. Kopyala yapıştırla gelen "30 saniye" ya da "100 milisaniye" değerleri yerine, ölçülmüş gecikme yüzdeliklerine ve bir false positive'in maliyetine bakarak seç.

Failure detector'ün kararını kesin bilgi saymak. "Node B öldü" kararı bir şüphedir. B hâlâ yaşıyor ve yazmaya devam ediyor olabilir; bu ihtimali hesaba katmayan failover, split brain'e yol açar. Beşinci ve onuncu yazılar bu sorunun iki farklı yüzünü ele alıyor.

Küçük Bir Deneme

★☆☆ dropRate'i 0,2'den 0,5'e çıkar. At-least-once'ta duplicate sayısı ile kayıp ack sayısı hâlâ eşit mi? Neden?

★★☆ At-least-once döngüsüne alıcı tarafında deduplication ekle: Inventory gördüğü Id'leri bir HashSet<int>'te tutsun ve tekrar gelenleri işlemeden yalnız ack'lesin. Ardından alıcının ortada bir kez "yeniden başladığını" (set'in temizlendiğini) simüle et. Kaç sipariş iki kez işleniyor?

★★★ FailureDetectorExperiment'e sabit timeout yerine son 100 heartbeat aralığının ortalamasının ve standart sapmasının üzerine kurulu bir eşik ekle (ortalama + 4 standart sapma gibi). Aynı simülasyonda yanlış alarm sayısı ve gerçek çöküşü fark etme süresi nasıl değişiyor?

Bu yazıda network'ü ve node'ları modelledik ama zamanlamayı yalnız "gecikme" olarak düşündük. Bir sonraki yazıda zamanın kendisine bakıyoruz: makinelerin saatleri neden kayar, NTP (Network Time Protocol) bunu nasıl ve ne kadar düzeltir, .NET'te süre ölçmek için neden DateTime.UtcNow değil monotonic clock kullanılır ve last-write-wins neden saat kayması yüzünden veri kaybettirir.