Logical Clock'lar: Happens-Before, Lamport Clock ve Vector Clock

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

Önce Tahmin Et

Bookstore'da üç servis var: Catalog (C), Pricing (P) ve Search (S). Catalog bir kitabın adını güncelliyor (a) ve Pricing'e BookUpdated message'ı gönderiyor (b). O sırada Pricing, Catalog'dan habersiz bir fiyatı değiştiriyor (d), sonra message'ı alıyor (e). Search ise kendi işinde: configuration'ını yüklüyor, sonra index'ini yeniden kuruyor (f) ve kimseyle konuşmuyor.

Her servis saate bakmak yerine bir sayaç tutuyor ve bu sayaçlara göre d'ye 1, f'ye 2 değeri düşüyor. 1, 2'den küçük. Bu, d'nin f'den önce olduğu ve f'yi etkileyebileceği anlamına mı geliyor? Logları bu sayaçlara göre sıralayan bir debugging aracı sana doğru bir hikâye mi anlatır?

Happens-Before: Saate Bakmadan Sıralama

Bir önceki yazıda fiziksel saatlerin, farklı makinelerdeki event'leri sıralamak için güvenilir olmadığını gördük. Leslie Lamport 1978 tarihli "Time, Clocks, and the Ordering of Events in a Distributed System" makalesinde soruyu tersinden sordu: "hangisi önce oldu?" sorusunu saate hiç bakmadan cevaplayabilir miyiz? Cevabı, yalnız sistemin kendi içinde gözlemlenebilen bir ilişki üzerine kurdu: happens-before, yazılışıyla a → b.

Tanım üç kuraldan oluşur. Aynı process içinde a, b'den önce olduysa a → b. a bir message'ın gönderilmesi, b aynı message'ın alınmasıysa a → b. Ve geçişlilik: a → b ve b → c ise a → c. Bu üç kuralla bağlanamayan iki event concurrent'tır (a ∥ b). Concurrent "aynı anda" demek değildir; "birbirinden haberi olamaz" demektir. Search'ün f event'i ile Pricing'in d event'i arasında hiçbir message zinciri yok, o yüzden fiziksel zamanda hangisi önce olursa olsun ikisi concurrent'tır: biri diğerini etkilemiş olamaz.

Happens-before, fizikteki causality'nin dağıtık sistemdeki karşılığıdır. Lamport makalesinde bu benzetmeyi özel görelilikten aldığını açıkça söyler: iki event arasında ışık hızında bile bir sinyal gidemiyorsa, hangisinin önce olduğu sorusunun gözlemciden bağımsız bir cevabı yoktur. Dağıtık sistemde ışığın yerini message alır.

Lamport Clock

Lamport'un ikinci adımı, happens-before'a uyan sayılar üretmek. Her process bir sayaç tutar. Her local event'te ve her message gönderiminde sayacı bir artırır ve gönderdiği message'a sayacı ekler. Bir message aldığında sayacını, kendi değeri ile message'taki değerin büyüğünün bir fazlasına ayarlar:

namespace Bookstore.Clocks;

public sealed class LamportClock
{
    public long Time { get; private set; }

    // Local event ya da gönderim: bir artır
    public long Tick() => ++Time;

    // Alım: max(yerel, gelen) + 1
    public long Receive(long received)
    {
        Time = Math.Max(Time, received) + 1;
        return Time;
    }
}

Bu kurallar şu garantiyi verir: a → b ise L(a) < L(b). Yani bir event, causal olarak kendisinden önce gelen her event'ten daha büyük bir sayı alır. Eşitliği process kimliğiyle bozarsan (önce sayaç, eşitse process id), bütün event'ler üzerinde happens-before'a uyan bir total order elde edersin. Lamport makalede bu total order'ı bir distributed mutual exclusion algoritması için kullanır; bugün total order broadcast ve consensus tabanlı sistemlerin temelinde aynı fikir var.

Açılıştaki senaryoyu çalıştıralım:

using Bookstore.Clocks;

// Üç process: Catalog (C), Pricing (P), Search (S)
LamportClock c = new(), p = new(), s = new();
long a = c.Tick();            // a: C bir kitabın adını günceller
long b = c.Tick();            // b: C, P'ye "BookUpdated" gönderir
long d = p.Tick();            // d: P, C'den habersiz bir fiyatı değiştirir
long e = p.Receive(b);        // e: P message'ı alır
s.Tick();                     // S configuration'ını yükler
long f = s.Tick();            // f: S index'ini yeniden kurar, kimseyle konuşmaz
Console.WriteLine($"Lamport  a={a} b={b} d={d} e={e} f={f}");

Lamport  a=1 b=2 d=1 e=3 f=2

d'ye 1, f'ye 2 düştü. Ama tersi doğru değil: L(d) < L(f) olması d → f demek değil. Garanti tek yönlü: happens-before sayıların sırasını belirler, sayıların sırası happens-before'u belirlemez. Lamport clock iki event'in concurrent olup olmadığını söyleyemez. Search ve Pricing'in loglarını Lamport timestamp'ine göre birleştirirsen d'yi f'nin önüne koyarsın ve okuyan kişi d'nin f'ye yol açmış olabileceğini düşünür. Sıralama tutarlıdır ama causality bilgisi kaybolmuştur. Bir de a ile d'ye bak: ikisi de 1. Total order için eşitliği process id ile bozmak gerekiyor.

Vector Clock: Concurrent Olanı Tespit Etmek

Concurrency'yi tespit etmek için tek bir sayaç yetmez; her process'in, diğer process'lerden ne kadarını "gördüğünü" bilmesi gerekir. Colin Fidge ve Friedemann Mattern'in 1988'de birbirinden bağımsız olarak önerdiği vector clock bunu yapar: her process N element'li bir vektör tutar, kendi slot'unu her event'te artırır, message alınca vektörleri slot slot maksimumla merge eder ve sonra kendi slot'unu artırır.

using System.Collections.Immutable;

namespace Bookstore.Clocks;

public enum Ordering { Before, After, Equal, Concurrent }

public sealed record VectorClock(ImmutableSortedDictionary<string, long> Entries)
{
    public static VectorClock Empty { get; } = new(ImmutableSortedDictionary<string, long>.Empty);

    public long this[string node] => Entries.GetValueOrDefault(node);

    public VectorClock Increment(string node) => new(Entries.SetItem(node, this[node] + 1));

    // Slot slot maksimum; message alınınca kullanılır
    public VectorClock Merge(VectorClock other)
    {
        ImmutableSortedDictionary<string, long> merged = Entries;
        foreach ((string node, long value) in other.Entries)
        {
            merged = merged.SetItem(node, Math.Max(this[node], value));
        }
        return new VectorClock(merged);
    }

    public Ordering Compare(VectorClock other)
    {
        IEnumerable<string> nodes = Entries.Keys.Union(other.Entries.Keys);
        bool less = false, greater = false;
        foreach (string node in nodes)
        {
            if (this[node] < other[node]) less = true;
            if (this[node] > other[node]) greater = true;
        }
        return (less, greater) switch
        {
            (false, false) => Ordering.Equal,
            (true, false) => Ordering.Before,
            (false, true) => Ordering.After,
            _ => Ordering.Concurrent
        };
    }

    public override string ToString() => "[" + string.Join(", ", Entries.Select(e => $"{e.Key}:{e.Value}")) + "]";
}

Karşılaştırma kuralı şöyle: V(a)'nın her slot'u V(b)'ninkinden küçük ya da eşitse ve en az biri kesin küçükse a → b. Bazı slot'larda küçük, bazılarında büyükse a ∥ b. Lamport clock'tan farklı olarak bu kural iki yönlü çalışır: a → b ancak ve ancak V(a) < V(b). Aynı senaryo, vektörlerle:

VectorClock vc = VectorClock.Empty, vp = VectorClock.Empty, vs = VectorClock.Empty;
VectorClock va = vc = vc.Increment("C");
VectorClock vb = vc = vc.Increment("C");
VectorClock vd = vp = vp.Increment("P");
VectorClock ve = vp = vp.Merge(vb).Increment("P");
vs = vs.Increment("S");
VectorClock vf = vs = vs.Increment("S");
Console.WriteLine($"Vector   a={va} b={vb} d={vd} e={ve} f={vf}");
Console.WriteLine($"d vs f : Lamport {d} < {f}? {d < f}, vector says {vd.Compare(vf)}");
Console.WriteLine($"b vs e : vector says {vb.Compare(ve)}");
Console.WriteLine($"a vs d : Lamport {a} == {d}, vector says {va.Compare(vd)}");

Vector   a=[C:1] b=[C:2] d=[P:1] e=[C:2, P:2] f=[S:2]
d vs f : Lamport 1 < 2? True, vector says Concurrent
b vs e : vector says Before
a vs d : Lamport 1 == 1, vector says Concurrent

Vector clock, Lamport'un 1 < 2 dediği d ve f için doğru cevabı veriyor: concurrent. b ile e arasında message olduğu için b → e. a ile d ise aynı Lamport değerini almıştı; vektörler onların da concurrent olduğunu söylüyor. Bedeli ortada: timestamp artık tek bir sayı değil, sistemdeki process sayısı kadar element taşıyan bir map. Üç servis için önemsiz, ama binlerce client'ın doğrudan yazdığı bir sistemde her message'a binlerce element'li bir vektör eklemek pratik değildir.

xUnit ile Concurrency Testi

Bu tür kodun kenar durumları (eksik slot'lar, kendi kendisiyle karşılaştırma, merge sonrası artırma) gözle kaçabilir. Davranışı üç küçük testle sabitleyelim:

using Bookstore.Clocks;
using Xunit;

namespace Bookstore.Clocks.Tests;

public class VectorClockTests
{
    [Fact]
    public void Message_creates_happens_before()
    {
        VectorClock sent = VectorClock.Empty.Increment("C");
        VectorClock received = VectorClock.Empty.Increment("P").Merge(sent).Increment("P");

        Assert.Equal(Ordering.Before, sent.Compare(received));
        Assert.Equal(Ordering.After, received.Compare(sent));
    }

    [Fact]
    public void Independent_updates_are_concurrent()
    {
        VectorClock onCatalog = VectorClock.Empty.Increment("C");
        VectorClock onPricing = VectorClock.Empty.Increment("P");

        Assert.Equal(Ordering.Concurrent, onCatalog.Compare(onPricing));
    }

    [Fact]
    public void Lamport_order_does_not_imply_causality()
    {
        LamportClock pricing = new(), search = new();
        long d = pricing.Tick();
        search.Tick();
        long f = search.Tick();

        Assert.True(d < f);  // timestamp'ler sıralı...
        Assert.Equal(Ordering.Concurrent,  // ...ama event'ler değil
            VectorClock.Empty.Increment("P").Compare(VectorClock.Empty.Increment("S").Increment("S")));
    }
}

Passed!  - Failed:     0, Passed:     3, Skipped:     0, Total:     3, Duration: 10 ms - Clocks.Tests.dll (net10.0)

Üçüncü test yazının ana fikrini koda döküyor: Lamport timestamp'leri sıralı, ama event'ler concurrent. Bir code review'da "bu iki event'i Lamport timestamp'ine göre sıralıyoruz, demek ki d, f'den önce" cümlesini görürsen, bu test neden yanlış olduğunu gösteriyor.

Version Vector ile Conflict Tespiti

Vector clock'un en yaygın pratik kullanımı, replication'da conflict tespitidir. Burada adı genelde version vector olur ve küçük bir fark vardır: vektörün slot'ları process'ler değil replica'lardır ve her key için ayrı tutulur. Bir replica bir key'e yazdığında kendi slot'unu artırır. İki replica birbirleriyle senkronize olurken key'in iki versiyonunu karşılaştırır: biri diğerinden büyükse eskisi silinir; concurrent ise ikisi de saklanır.

Amazon'un 2007 tarihli Dynamo makalesi alışveriş sepetini tam olarak böyle tutuyordu. İki replica aynı sepete concurrent yazma aldığında Dynamo hangisinin "doğru" olduğuna karar vermez; iki versiyonu da (sibling) saklar ve bir sonraki okumada ikisini birden uygulamaya verir. Uygulama da sepetleri birleştirir. Bir önceki yazıdaki last-write-wins'ten (LWW) farkı büyük: LWW concurrent yazmalardan birini sessizce atar, version vector conflict'i görünür kılar ve çözümü veriyi anlayan koda bırakır. Riak gibi sistemlerde client sayısı büyüdüğünde vektörün şişmesini engellemek için dotted version vector gibi geliştirilmiş varyantlar kullanılır. Yedinci yazıda sepetin birleştirilmesinin kendine özgü bir tuzağını, on birinci yazıda ise bunu kendiliğinden doğru yapan CRDT'leri (Conflict-free Replicated Data Type) göreceğiz.

Hybrid Logical Clock: Fiziksel Zamana Yakın, Causality'ye Sadık

Logical clock'ların bir eksiği var: değerleri insan için anlamsız. "Bana dün saat 14:00'teki durumu göster" sorusunu bir Lamport sayacıyla cevaplayamazsın. Fiziksel saatin de causality'yi bozabildiğini gördük. Kulkarni ve arkadaşlarının 2014'te önerdiği hybrid logical clock (HLC) ikisini birleştirir: timestamp'in bir parçası fiziksel saatten gelir, ama kendi gördüğü en büyük değerin ve gelen message'taki değerin gerisine asla düşmez; aynı milisaniyede birden fazla event olursa ya da saat gerideyse aradaki farkı küçük bir sayaçla kapatır.

namespace Bookstore.Clocks;

public readonly record struct HlcTimestamp(long WallMs, int Counter) : IComparable<HlcTimestamp>
{
    public int CompareTo(HlcTimestamp other) =>
        WallMs != other.WallMs ? WallMs.CompareTo(other.WallMs) : Counter.CompareTo(other.Counter);

    public override string ToString() => $"{WallMs}.{Counter}";
}

// Hybrid logical clock (Kulkarni ve ark., 2014): fiziksel zamana yakın, ama asla geri gitmez
public sealed class HybridLogicalClock(Func<long> physicalMs)
{
    private HlcTimestamp _last;

    public HlcTimestamp Now()
    {
        long pt = physicalMs();
        _last = pt > _last.WallMs ? new(pt, 0) : _last with { Counter = _last.Counter + 1 };
        return _last;
    }

    public HlcTimestamp Receive(HlcTimestamp remote)
    {
        long pt = physicalMs();
        long wall = Math.Max(pt, Math.Max(_last.WallMs, remote.WallMs));
        int counter = (wall == _last.WallMs, wall == remote.WallMs) switch
        {
            (true, true) => Math.Max(_last.Counter, remote.Counter) + 1,
            (true, false) => _last.Counter + 1,
            (false, true) => remote.Counter + 1,
            _ => 0
        };
        _last = new(wall, counter);
        return _last;
    }
}

Bir önceki yazının LWW senaryosunu hatırla: B'nin saati 300 milisaniye geride ve bu yüzden daha yeni yazması kaybedilmişti. Bu sefer B, A'nın yazmasını replication ile aldıktan sonra kendi yazmasını yapıyor:

// Hybrid logical clock: B sunucusunun fiziksel saati A'nınkinden 300 ms geride
long trueMs = 1_000_000;
HybridLogicalClock hlcA = new(() => trueMs);
HybridLogicalClock hlcB = new(() => trueMs - 300);
HlcTimestamp writeOnA = hlcA.Now();                 // A'da price=450
trueMs += 100;
HlcTimestamp seenOnB = hlcB.Receive(writeOnA);      // B, A'nın yazmasını replike eder
HlcTimestamp writeOnB = hlcB.Now();                 // B'de price=399, 100 ms sonra
Console.WriteLine($"HLC      A write={writeOnA} B receive={seenOnB} B write={writeOnB} B > A? {writeOnB.CompareTo(writeOnA) > 0}");

HLC      A write=1000000.0 B receive=1000000.1 B write=1000000.2 B > A? True

B'nin fiziksel saati A'nın yazmasından 200 milisaniye geride olmasına rağmen, A'nın yazmasını gördükten sonra ürettiği timestamp ondan büyük. Causal olarak sonra gelen yazma, timestamp olarak da sonra geliyor. Dikkat: bu, bir önceki yazıdaki iki editörün durumunu tam olarak çözmez; B, A'nın yazmasını görmeden yazsaydı iki yazma concurrent olurdu ve HLC hangisinin gerçek zamanda sonra olduğunu bilemezdi. HLC causality'yi korur, saat kaymasını ortadan kaldırmaz. CockroachDB ve MongoDB bu yaklaşımın varyantlarını kullanır; on birinci yazıda CockroachDB'nin HLC'yi NTP (Network Time Protocol) ve bir uncertainty interval ile nasıl birleştirdiğine bakacağız.

Sık Düşülen Tuzaklar

Lamport sırasını causality sanmak. L(a) < L(b) yalnız "b, a'dan önce olmuş olamaz" der, "a, b'ye yol açtı" demez. Causality sorusu soruyorsan vector clock ya da açık bir causal metadata gerekir.

Vektöre client'ları koymak. Vector clock'un slot sayısı, yazma yapan aktör sayısıdır. Her kullanıcı ya da her HTTP (Hypertext Transfer Protocol) isteği bir aktör olursa vektör sınırsız büyür. Slot'lar az sayıda ve uzun ömürlü olmalı: replica'lar ya da servis instance'ları.

Merge'ten sonra kendi slot'unu artırmayı unutmak. Alım da bir event'tir. Merge'ü yapıp artırmazsan, gönderenin event'i ile alımın event'i aynı vektörü taşır ve "eşit" sanılır.

Total order için eşitliği bozmamak. İki process aynı Lamport değerini üretebilir. Sıralamayı deterministik yapmak için ikinci bir anahtar (process id) şarttır; aksi halde farklı node'lar aynı event'leri farklı sıraya koyar.

HLC'yi saat senkronizasyonunun yerine koymak. HLC'nin fiziksel parçası, en hızlı saate sahip node'un değerini takip eder. Bir node'un saati bir saat ileri kaçarsa bütün sistemin HLC değerleri bir saat ileri gider ve sayaç bunu kapatmak için şişer. Bu yüzden HLC kullanan veritabanları maksimum saat farkını izler ve aşılırsa node'u durdurur.

Küçük Bir Deneme

★☆☆ Senaryoya Search'ün f'den sonra Catalog'a bir message gönderdiği ve Catalog'un bunu alıp g event'ini ürettiği adımı ekle. g ile d arasındaki ilişki ne? Önce kâğıt üzerinde tahmin et, sonra vector clock ile doğrula.

★★☆ VectorClockTests'e "merge commutative'dir" testini ekle: x.Merge(y) ile y.Merge(x) aynı vektörü vermeli. Ardından merge'ün idempotent olduğunu (x.Merge(x)) test et. Bu iki property neden replication için önemli?

★★★ Bir VersionedCart yaz: her versiyon bir VectorClock ve bir ISet<string> taşısın. İki replica'dan gelen versiyonları karşılaştırıp eskisini atan, concurrent olanları sibling olarak saklayan bir Merge method'u ekle. Sepetten silinen bir kitap concurrent bir eklemeyle karşılaşırsa ne oluyor?

Bu yazıda event'lerin sırasını konuştuk. Bir sonraki yazıda verinin kopyalarına geçiyoruz: leader-based, multi-leader ve leaderless replication, quorum'un R + W > N kuralı ve bir node düştüğünde ne olduğunu gösteren bir C# simülasyonu.