Lock-Free ve Wait-Free: CAS Döngüsü, ABA Problemi ve Linearizability

Sürüm notu: Bu yazıdaki kodlar .NET 10 (C# 14) ile derlenip denenmiştir; testler xUnit v3 4.0.3, ölçümler BenchmarkDotNet 0.15.8 ile yapıldı. Çıktılar ARM64 (Arm'ın 64-bit işlemci mimarisi) üzerinde alınmıştır; x64 için söylenenler Intel dokümanlarına dayanır.

Önce Tahmin Et

Sitedeki serilerin ortak örnek uygulaması Bookstore'da (bir online kitapçı) satış sayacını kilitsiz yazmak istiyorsun: değeri oku, bir ekle, değer hâlâ okuduğun gibiyse yenisini yaz, değilse baştan dene. Sekiz thread toplam 8 milyon satış kaydettiğinde "değer değişmiş, baştan dene" durumu kaç kez yaşanır? Ve bu kilitsiz sayaç, sıradan bir lock ile korunan sayaçtan hızlı mıdır, yavaş mı?

İkinci soru: kilitsiz bir stack yazdın ve allocation'ı azaltmak için pop edilen node'ları bir havuza koyup tekrar kullanıyorsun. Algoritma aynı, yalnız node'lar yeniden kullanılıyor. Sekiz thread 8 milyon id push edip pop ettiğinde kaç id kaybolur? Önceki yazıda kilitlerin ve Interlocked'ın neden doğru çalıştığını memory model'den çıkardık. Bu yazıda kilidi tamamen bırakıyoruz.

Progress Garantileri: Blocking'den Wait-Free'ye

Kilitli kodun temel zayıflığı şu: kilidi tutan thread OS tarafından askıya alınırsa, page fault yaşarsa ya da bir exception ile takılırsa, o kilidi bekleyen herkes de durur. Bir thread'in yavaşlığı bütün sistemi durdurabilir. Bu tür algoritmalara blocking denir. Kilitsiz algoritmalar ilerleme için farklı seviyelerde garanti verir ve bu seviyelerin adları literatürde belli:

• Obstruction-free: bir thread diğerleri dursa, tek başına çalıştığında işini sonlu adımda bitirir. Rekabet varsa herkes birbirini sonsuza kadar engelleyebilir.
• Lock-free: rekabet olsa bile her an sistemdeki thread'lerden en az biri ilerler. Tek tek thread'ler aç kalabilir ama sistem bir bütün olarak takılmaz.
• Wait-free: her thread kendi işini, diğerleri ne yaparsa yapsın, sınırlı sayıda adımda bitirir. En güçlü garanti budur.

Bu sınıflandırmanın arkasında Maurice Herlihy'nin 1991'de yayımladığı "Wait-Free Synchronization" makalesi var. Herlihy, yalnız okuma ve yazma yapan bir belleğin iki thread arasında wait-free bir uzlaşma (consensus; birden çok thread'in aynı değer üzerinde anlaşması) bile sağlayamayacağını, compare-and-swap'ın ise istenen sayıda thread için sağlayabileceğini gösterdi. Üçüncü yazıdaki Peterson algoritmasıyla bağı burada: yalnız okuma ve yazmayla mutual exclusion kurulabiliyor ama o çözüm blocking. Wait-free ya da lock-free bir veri yapısı için donanımın atomik talimatları gerekiyor.

CAS Döngüsü: Lock-Free Sayaç

CAS (compare-and-swap; bir adresteki değer beklenen değerse yenisini yazan, değilse hiçbir şey yapmayan atomik işlem) kilitsiz algoritmaların temel aracı. .NET'teki karşılığı Interlocked.CompareExchange. Kalıp hep aynı: oku, yeni değeri hesapla, kimse araya girmediyse yayınla, girdiyse baştan dene. Yeni klasör LockFree/:

// CAS döngüsü: oku, hesapla, araya kimse girmediyse yayınla, girdiyse tekrar dene
public sealed class LockFreeCounter
{
    private long _value;

    public long Value => Volatile.Read(ref _value);

    // Bizimki başarılı olana kadar kaç CAS denemesinin başarısız olduğunu döndürür (contention ölçüsü)
    public int Add(long amount)
    {
        int failed = 0;
        while (true)
        {
            long seen = Volatile.Read(ref _value);
            if (Interlocked.CompareExchange(ref _value, seen + amount, seen) == seen)
                return failed;
            failed++;
        }
    }
}

Bu sayaç lock-free ama wait-free değil: bir thread'in CAS'ı başarısız olduysa, başka bir thread'inki başarılı olmuş demektir, yani sistem ilerledi. Ama şanssız bir thread teoride her seferinde kaybedebilir. Sekiz milyon artışı 1, 2, 4 ve 8 thread'e bölüp başarısız CAS sayısını ölçtüm:

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- cas-counter

threads=1 value=8,000,000 failed CAS=         0 (27 ms)
threads=2 value=8,000,000 failed CAS= 2,268,002 (167 ms)
threads=4 value=8,000,000 failed CAS= 5,988,556 (325 ms)
threads=8 value=8,000,000 failed CAS=27,774,810 (1316 ms)

Sonuç her zaman doğru, ama 8 thread'le 8 milyon başarılı CAS'a karşılık 27,7 milyon başarısız deneme var; her artış ortalama dört buçuk deneme sürdü. Tek thread'de 27 ms süren iş 8 thread'de 1,3 saniye sürdü. JIT'in (kodu çalışma anında makine koduna çeviren compiler) ürettiği koda baktığımda döngünün kalbi ARM64'ün casal talimatı; Interlocked.Increment ise döngü olmadan tek bir ldaddal (atomik fetch-and-add) talimatına dönüşüyor. İkincisi donanımda hiç "başarısız" olmaz; bu yüzden basit sayaçlar için CAS döngüsü değil, hazır atomik işlem kullanılır. CAS döngüsü, yeni değerin eskisinden karmaşık bir hesapla çıktığı durumlar içindir; ikinci yazıdaki TryUpdate döngüsü buna örnekti.

Treiber Stack

Kilitsiz veri yapılarının en bilinen öğretici örneği R. Kent Treiber'in 1986'da bir araştırma raporunda yayımladığı stack. Fikir basit: paylaşılan tek şey _head referansı ve her değişiklik bu referans üzerinde tek bir CAS.

// Treiber (1986): paylaşılan tek word'ü head referansı olan lock-free stack
public sealed class TreiberStack<T> : IConcurrentStack<T>
{
    private sealed record Node(T Value, Node? Next);

    private Node? _head;

    public void Push(T value)
    {
        while (true)
        {
            Node? head = Volatile.Read(ref _head);
            Node node = new(value, head);
            if (Interlocked.CompareExchange(ref _head, node, head) == head)
                return;
        }
    }

    public bool TryPop(out T value)
    {
        while (true)
        {
            Node? head = Volatile.Read(ref _head);
            if (head is null)
            {
                value = default!;
                return false;
            }
            if (Interlocked.CompareExchange(ref _head, head.Next, head) == head)
            {
                value = head.Value;
                return true;
            }
        }
    }
}

Doğruluk argümanı da kısa. Node'lar immutable; bir node oluşturulduktan sonra Next'i değişmez. Push, yeni node'u ancak _head hâlâ okuduğu node ise yayınlar; Pop, _head'i ancak hâlâ okuduğu node ise bir sonrakine taşır. Araya giren her değişiklik CAS'ı başarısız yapar ve işlem baştan başlar. CompareExchange bir full fence olduğu için node'un içeriği, referansı yayınlandığında diğer thread'lere görünür durumdadır.

Sekiz thread'in her biri bir milyon kez kendine özgü bir id push edip ardından bir pop yapıyor; sonunda stack'te kalanlar da boşaltılıyor ve her id'nin tam bir kez çıkıp çıkmadığı sayılıyor. Treiber stack'te sonuç 8 milyon id'de sıfır kayıp ve sıfır tekrar (aşağıdaki çıktının ilk satırı).

ABA Problemi ve GC'nin Sessiz Yardımı

Şimdi baştaki ikinci soruya gelelim. Pop edilen node'u bir havuza koyup sonraki push'ta tekrar kullanan sürüm, algoritmanın kendisini hiç değiştirmiyor:

public bool TryPop(out int value)
{
    while (true)
    {
        Node? head = Volatile.Read(ref _head);
        if (head is null)
        {
            value = 0;
            return false;
        }
        Node? next = head.Next;
        // head biz okuduktan sonra pop edilip, havuza dönüp tekrar push edilmiş olabilir: CAS yine başarılı olur
        if (Interlocked.CompareExchange(ref _head, next, head) == head)
        {
            value = head.Value;
            _pool.Enqueue(head);
            return true;
        }
    }
}

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- stack-stress 1000000

Treiber (new nodes)     pushed=8,000,000 missing=      0 popped twice=      0
Treiber (pooled nodes)  pushed=8,000,000 missing=699,298 popped twice=570,668
racy read-then-write    pushed=8,000,000 missing= 72,802 popped twice=242,240

Havuzlu sürümde 699.298 id kayboldu, 570.668 id iki kez çıktı. İlk koşuda bu sayılar 2,6 ve 2 milyon civarındaydı. Üçüncü satır, hiç CAS kullanmadan önce okuyup sonra yazan bir stack; onu birazdan linearizability için kullanacağız.

Havuzlu sürümü bozan şey ABA (bir değerin A'dan B'ye, sonra yine A'ya dönmesi ve CAS'ın bunu "hiç değişmemiş" sanması) problemi. Senaryo şöyle: thread 1 head olarak N1'i, onun Next'i olarak N2'yi okur ve CAS'tan hemen önce askıya alınır. Bu sırada thread 2, N1'i ve N2'yi pop eder, ikisi de havuza döner. Sonra yeni bir değer push edilir ve havuzdan çıkan node yine N1'dir; artık Next'i başka bir node'u gösterir. Thread 1 uyanır, head'in hâlâ N1 olduğunu görür ve CAS başarılı olur: head artık havuzdaki N2'yi gösteriyor. Stack'in geri kalanı kaybolur, havuzdaki bir node iki yerde birden kullanılır.

Yeni node oluşturan sürüm neden etkilenmiyor? Çünkü GC (garbage collector; kullanılmayan belleği otomatik geri kazanan bileşen) thread 1'in elinde N1'e bir referans varken N1'in belleğini başka bir node'a vermez. Her push gerçekten yeni bir object, yani CAS'ın karşılaştırdığı referans eşitliği aynı zamanda "aynı node, aynı içerik" anlamına geliyor. Bu, C ve C++'ta lock-free kod yazanların en büyük sorunu olan bellek geri kazanımını (memory reclamation) .NET'in bizim yerimize çözdüğü anlamına geliyor. Native dünyada bunun için pointer'ın yanına bir sürüm sayacı koyup ikisini birlikte CAS'lamak (tagged pointer), Maged Michael'ın 2004'te yayımladığı hazard pointer'lar ya da epoch tabanlı geri kazanım gibi teknikler gerekir. .NET'te tek kural: lock-free bir yapının node'larını havuzlama. Pooling ile allocation'dan kazandığın, yukarıdaki tabloda kaybettiğin doğrulukla kıyaslanamaz.

Linearizability: Doğruluk Ölçütü

Treiber stack'in "doğru" olduğunu söyledik ama doğru tam olarak ne demek? Tek thread'de cevap kolay: stack'in sıralı tanımına uyuyorsa doğru. Concurrent bir object'te işlemler zamanda üst üste biniyor. Maurice Herlihy ve Jeannette Wing 1990'da yayımladıkları "Linearizability: A Correctness Condition for Concurrent Objects" makalesinde bu soruya bugün standart kabul edilen cevabı verdi. Kendi cümlelerimizle: her işleme, çağrıldığı an ile döndüğü an arasında bir an atayabiliyorsan ve işlemler bu anların sırasıyla dizildiğinde sıradan, tek thread'lik bir stack'in geçerli bir çalışması ortaya çıkıyorsa, gözlenen geçmiş (history) linearizable'dır.

Treiber stack'te bu "an" başarılı CAS'ın kendisi; buna linearization point denir. Distributed Systems Temelleri serisinin consistency modelleri yazısında aynı tanımı dağıtık bir key-value store için kullanmıştık; burada aynı ölçütü tek bir process içindeki bir veri yapısına uyguluyoruz.

Bu tanım test edilebilir. Üç thread'in her biri dört çağrı yapıyor (push, pop, push, pop); paylaşılan bir sayaç her çağrının başlangıç ve bitiş anını damgalıyor. Ardından küçük bir checker, bütün olası sıralamaları deneyerek bu geçmişi açıklayan bir sıralı çalıştırma arıyor. Bu kaba kuvvet arama fikri Wing ve Gong'un 1993'teki çalışmasına dayanır:

private static bool Search(ImmutableList<StackCall> pending, ImmutableStack<int> stack)
{
    if (pending.IsEmpty)
        return true;
    // bir çağrı ancak bekleyen hiçbir çağrı o başlamadan önce bitmemişse sıradaki olabilir
    long firstReturn = pending.Min(c => c.Returned);
    foreach (StackCall call in pending.Where(c => c.Invoked < firstReturn))
    {
        ImmutableStack<int> next;
        if (call.IsPush)
            next = stack.Push(call.Value);
        else if (!call.Popped)
        {
            if (!stack.IsEmpty) continue;
            next = stack;
        }
        else
        {
            if (stack.IsEmpty || stack.Peek() != call.Value) continue;
            next = stack.Pop();
        }
        if (Search(pending.Remove(call), next))
            return true;
    }
    return false;
}

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- linearizability 20000

Treiber  histories=20,000 not linearizable=0
racy     histories=20,000 not linearizable=63
    [ 1.. 8] T2 Push(200)
    [ 2.. 6] T0 Push(0)
    [ 3.. 4] T1 Push(100)
    [ 5..14] T1 TryPop() -> 200
    [ 7..19] T0 TryPop() -> 200
    [ 9..10] T2 TryPop() -> empty
    [11..12] T2 Push(202)
    [13..24] T2 TryPop() -> 202
    [15..16] T1 Push(102)
    [17..18] T1 TryPop() -> 102
    [20..21] T0 Push(2)
    [22..23] T0 TryPop() -> 2

Treiber stack'in 20.000 geçmişinin hepsi linearizable. Önce okuyup sonra yazan stack'te 63 geçmiş açıklanamadı ve checker ilkini yazdırdı. Kâğıt üzerinde okuyalım: 10. anda üç push (200, 0, 100) bitmiş durumda. O ana kadar en fazla iki pop başlamış ve her pop en fazla bir eleman çıkarabilir; yani stack'te en az bir eleman olmalı. Ama T2'nin 9 ile 10 arasındaki pop'u "boş" dedi. Üstüne iki thread aynı 200'ü pop etti. Bu iki gözlemi aynı anda açıklayan hiçbir sıralı çalıştırma yok. Checker'ın bulduğu şey, "bu çıktı hiçbir doğru stack'ten çıkamaz" diyen somut bir karşı örnek. Gerçek sistemlerde aynı fikri Jepsen'in Knossos'u ya da Go ile yazılmış Porcupine gibi araçlar, çok daha verimli arama algoritmalarıyla uygular.

Lock-Free Her Zaman Daha Hızlı mı?

Kilitsiz kodun daha hızlı olduğu yaygın bir varsayım. Aynı 10 milyon artışı lock, Interlocked.Increment ve CAS döngüsüyle BenchmarkDotNet ile ölçtüm; tablo artış başına süreyi gösteriyor (ARM64, 10 core'lu makine, ortam bilgisi satırları çıkarıldı):

dotnet run -c Release --project bench/Bookstore.ConcurrencyLab.Benchmarks -- --filter "*CounterBenchmarks*"

| Method               | Threads | Mean       | StdDev     | Ratio |
|--------------------- |-------- |-----------:|-----------:|------:|
| Locked               | 1       |   4.901 ns |  0.4104 ns |  1.01 |
| InterlockedIncrement | 1       |   1.678 ns |  0.0172 ns |  0.34 |
| CasLoop              | 1       |   1.970 ns |  0.1725 ns |  0.40 |
|                      |         |            |            |       |
| Locked               | 2       |   8.321 ns |  0.0368 ns |  1.00 |
| InterlockedIncrement | 2       |   5.220 ns |  0.2469 ns |  0.63 |
| CasLoop              | 2       |  21.704 ns |  3.2255 ns |  2.61 |
|                      |         |            |            |       |
| Locked               | 4       |   7.116 ns |  0.2942 ns |  1.00 |
| InterlockedIncrement | 4       |  11.631 ns |  0.7229 ns |  1.64 |
| CasLoop              | 4       |  86.109 ns | 20.2068 ns | 12.12 |
|                      |         |            |            |       |
| Locked               | 8       |  11.130 ns |  0.4049 ns |  1.00 |
| InterlockedIncrement | 8       |  22.508 ns |  4.7180 ns |  2.02 |
| CasLoop              | 8       | 179.745 ns | 51.9046 ns | 16.17 |

Tek thread'de beklenen sıralama var: kilitsiz yollar lock'tan üç kat hızlı. Contention arttıkça tablo tersine dönüyor. 8 thread'de CAS döngüsü lock'tan 16 kat yavaş ve standart sapması da çok yüksek; buna CAS fırtınası deniyor. Her başarısız CAS, cache line'ı bir core'a çekip boşuna geri veriyor ve bütün core'lar aynı line için sıraya giriyor. 4 ve 8 thread'de lock, Interlocked.Increment'ı bile geçiyor. Benim yorumum şu: kilit, bekleyen thread'leri spin edip sonra bekletiyor ve kilidi alan thread birkaç artışı cache line elindeyken art arda yapabiliyor; Interlocked'da ise her artışta line core değiştiriyor. Bu sonuç bu makineye ve bu iş yüküne ait. x64'te ve farklı core sayılarında oranlar değişir; kendi makinende ölçmeden genelleme yapma.

BCL'deki (Base Class Library; .NET'in standart kütüphanesi) ConcurrentStack<T> tam bu yüzden düz bir Treiber stack değil. dotnet/runtime'daki kaynak koduna baktığımda, CAS başarısız olduğunda SpinWait ile beklediğini ve rastgele artan bir backoff kullandığını gördüm. Dördüncü yazıda livelock'u kıran şey de rastgele backoff'tu.

Üretimde Dikkat

Lock-free veri yapısını kendin yazma. ConcurrentStack<T>, ConcurrentQueue<T>, ConcurrentDictionary<TKey, TValue> ve Channel<T> yıllarca farklı donanımlarda test edildi ve memory model'i doğru kullanıyor. Kullanımlarını C# Asenkron Programlama serisinin senkronizasyon ve Channels yazılarında anlatmıştık. Kendi CAS döngüne gerçekten ihtiyaç duyduğun yer genellikle tek bir alanın karmaşık bir kuralla güncellenmesi (en yüksek fiyatı tutmak, bir durumu yalnız belirli bir durumdan diğerine geçirmek) ve orada da döngü birkaç satırı geçmemeli.

Kilitsiz kodu ekip içinde sürdürmenin maliyetini hesaba kat. Bu yazıdaki havuzlu stack, normal stack'ten yalnız birkaç satır farklı ve code review'da kolayca "allocation'ı azaltan güzel bir optimizasyon" diye geçebilir. Lock-free bir değişikliği onaylamak için, her CAS'ın neden doğru olduğunu ve linearization point'in nerede olduğunu yazılı olarak isteyin. Bunu yazamayan bir ekip için lock daha doğru tercih.

Performans gerekçesini ölç. Kilitsiz kodun asıl faydası çoğu zaman ortalama hız değil, kilidi tutan thread'in yavaşlamasının diğerlerini durdurmamasıdır. Ortalama hız için yazıyorsan, yukarıdaki tablo gibi bir ölçüm olmadan karar verme.

Sık Düşülen Tuzaklar

Lock-free'yi her zaman hızlı sanmak. Deneyde 8 thread'de CAS döngüsü lock'tan 16 kat yavaştı. Contention yüksekse tek bir kilit, CAS fırtınasından daha iyi ölçeklenebilir.

Node havuzlamak. GC, ABA'nın en yaygın sebebini sessizce ortadan kaldırıyor; pooling bu korumayı kaldırır. Havuzlu stack 8 milyon id'nin yüz binlercesini kaybetti.

Lock-free'yi wait-free sanmak. CAS döngüsü sistem olarak ilerlemeyi garanti eder, tek tek thread'in ilerlemesini değil. Gecikme sınırı gereken yerlerde bu fark önemli.

Doğruluğu stress testiyle kanıtladığını sanmak. Bozuk stack 20.000 geçmişin yalnız 63'ünde yakalandı. Stress testi bir hatayı gösterebilir ama yokluğunu kanıtlayamaz; doğruluk argümanı linearization point'ler üzerinden kurulur.

Küçük Bir Deneme

★☆☆ LockFreeCounter'a RecordPeak(long candidate) method'unu ekle: o ana kadarki en yüksek günlük satış adedini tutsun ve aday yalnız mevcut değerden büyükse yazılsın. Bunu neden Interlocked.Increment gibi tek bir atomik işlemle yapamadığını ve CAS döngüsünün nasıl kurulduğunu açıkla.

★★☆ Havuzlu stack'te ABA'yı tagged pointer fikriyle düzelt: _head'i bir node referansı ve bir long sürüm sayacı içeren immutable bir object yap, her başarılı CAS'ta sürümü artır. stack-stress ile kayıpların sıfıra indiğini doğrula. Bu çözüm neden yine her işlemde bir allocation yapıyor?

★★★ Linearizability checker'ını bir queue için yaz (FIFO kuralıyla) ve ConcurrentQueue<T> ile 20.000 geçmiş üzerinde çalıştır. Sonra queue'yu bilerek bozan bir sürüm yaz ve checker'ın bulduğu ilk karşı örneği kâğıt üzerinde açıkla.

Bu yazıda shared memory modelinin en uç noktasına, kilitsiz veri yapılarına ve onları doğrulamanın zorluğuna baktık. Serinin son yazısında farklı bir yöne gidiyoruz: paylaşılan bellek yerine mesajla haberleşen actor ve CSP (Communicating Sequential Processes; channel üzerinden mesajlaşan sıralı süreçler) modelleri, Bookstore'un sipariş işleme akışını bu modellerle kurmak ve concurrent kodu testin ötesinde, Leslie Lamport'un TLA (Temporal Logic of Actions; zamana bağlı eylemler mantığı) üzerine kurduğu TLA+ diliyle model checking yaparak doğrulamak.