CRDT'ler (Conflict-free Replicated Data Types): Dağıtık Sistemlerde Veri Tutarlılığı

15 Ekim 2024 • ☕️☕️ 8 dk okuma • 🏷 bilgisayar, yazılım, algoritma

Yazar tarafından şu dillere çevrildi: English

Dağıtık sistemler günümüzde giderek daha fazla popüler hâle gelmiştir. Mikroservis mimarileri, veri merkezleri arası replikasyonlar, coğrafi olarak dağıtık veri tabanları, çoklu erişim noktalarına sahip uygulamalar ve benzeri senaryolar, veri tutarlılığının sağlanmasını oldukça karmaşık bir hâle getirir. Verinin aynı anda birden fazla lokasyonda bulunması, güncellenmesi veya okunması sırasında çatışmalar (conflicts) ortaya çıkabilir. İşte bu noktada CRDT (Conflict-free Replicated Data Types) kavramı devreye girer.

CRDT’ler, dağıtık ortamda veri kopyaları (replica) arasında sonunda güçlü tutarlılık (Strong Eventual Consistency) sağlamayı amaçlayan özel veri yapılarıdır. Bu tür veri yapılarını kullanarak, kopyalar arasında tutarlılığın sağlanması için sürekli bir senkronizasyon veya pahalı bir küresel kilit (global lock) mekanizmasına başvurulmaksızın, veri güncellemelerinin bir şekilde deterministik olarak birleştirilmesi (merge) mümkün olmaktadır.

1. CRDT Nedir ve Özellikleri

CRDT (Conflict-free Replicated Data Type), bir veri tipinin dağıtık ortamlarda tutarsızlıklar yaşanmadan replikasyonunun yapılabilmesi için tasarlanmış bir türüdür. Geleneksel yöntemlerde farklı kopyalardaki değişikliklerin bir araya getirilmesi, çatışmaların (conflicts) çözümü esnasında karmaşık algoritmalar veya ek bir koordinasyon gerektirir. CRDT’ler ise bu çatışmaları en aza indirebilecek (veya tamamen ortadan kaldırabilecek) şekilde tasarlanmışlardır.

Temel Özellikler

Idempotent Operasyonlar: CRDT’lerdeki birleşme (merge) fonksiyonları sıklıkla idempotent olarak tasarlanır. Yani aynı güncelleme birden fazla kez uygulanırsa aynı sonuca ulaşılır.
Commutativity (Değişme Özelliği): Operasyonlar farklı sırayla uygulanırsa da nihai durum aynı kalır.
Monotonik Büyüme: Bazı CRDT türlerinde (özellikle state-based CRDT’lerde) veri yapısı her zaman büyüyormuş gibi görülür. Güncellemeler eklemeler veya işaretlemeler şeklinde yapılır, ancak bu daha sonra farklı bir formülasyonla “çıkarmalara” (removals) da izin verir (örn: OR-Set).
Güçlü Sonunda Tutarlılık (Strong Eventual Consistency): Belirli bir zaman diliminde, tüm kopyalar birbirlerinden güncellemeleri alıp birleştirdiklerinde, nihai durumda hepsi aynı veriye ulaşırlar.

CRDT’lerin sağladığı bu özellikler, dağıtık sistemlerin en büyük zorluklarından biri olan tutarlılık problemini hafifletmeyi amaçlar. Özellikle CAP Teoremi gereği, bir sistemi hem yüksek erişilebilirlik (availability) hem de bölünme toleransı (partition tolerance) yüksek biçimde tasarlamak istersek, tutarlılık sorunlarına ayrı bir özen göstermemiz gerekir. CRDT’ler, “eventual consistency” yaklaşımı içinde çatışma çözümünü basitleştirerek bu soruna kısmi ama etkili bir çözüm sunar.

2. CRDT Türleri

CRDT’ler genel olarak Operation-based ve State-based olmak üzere iki temel kategoride incelenir. Ayrıca Delta-based denilen bir yaklaşım da vardır.

2.1. Operation-based (Op-based) CRDT’ler

Op-based CRDT’lerde, gerçekleşen her bir değişiklik (örneğin bir sayının artırılması, bir elemana ekleme yapılması) “operation log” benzeri bir sistem aracılığıyla diğer replikalara gönderilir. Bu replikalar gelen güncellemeyi uygular ve kendi durumlarını güncel tutarlar.

Örnek: GCounter (Grow-only Counter), PN-Counter (Positive-Negative Counter).

2.2. State-based (Convergent) CRDT’ler

State-based CRDT’lerde, her replikada bir “durum” (state) tutulur. Farklı replikalar zaman zaman birbirlerinin durumunu kopyalar (gossip mekanizması gibi) ve durumu birleştirir (merge). Bu birleşme işlemi idempotent, değişmeli (commutative) ve birleşmeli (associative) olduğundan, sıralama farkı gözetmeksizin aynı nihai duruma ulaşılabilir.”

Örnek: OR-Set (Observed-Removed Set), MV-Register (Multi-Value Register).

2.3. Delta-based CRDT’ler

Delta-based CRDT’ler, state-based yaklaşımın daha verimli hâlidir. Tam durumu göndermek yerine, sadece “delta” denilen özet (küçük bir parça) paylaşılır. Böylece bant genişliği ve senkronizasyon maliyeti azalır. Büyük veri setlerinde oldukça kullanışlıdır.

2.4. Bazı Popüler CRDT Örnekleri

G-Counter: Yalnızca artırım (increment) işlemlerini destekleyen bir sayaçtır.
PN-Counter: Hem artırım hem de eksiltme (decrement) işlemlerini destekler.
OR-Set (Observed-Removed Set): Eleman ekleme ve çıkarma operasyonlarını destekleyen bir küme yapısıdır. Aynı elemanın farklı zamanlardaki eklenme/çıkarılma bilgisini tutmak için ek metadata içerir.
LWW-Register (Last-Write-Wins Register): Son yazılan değerin baskın geldiği bir kayıt yapısıdır. Bir tür “en son değiştiren kazanır” (last-writer-wins) mantığı kullanır.
MV-Register (Multi-Value Register): Aynı anda farklı replikalarda farklı değerler yazıldığında birden fazla değeri tutar ve uygulamanın bu değerler arasındaki seçimi yapmasına izin verir.
RGA (Replicated Growable Array): Metin düzenleme veya doküman paylaşımı gibi senaryolarda kullanılır.

3. CRDT’lerin Kullanım Alanları ve Avantajları

Veri Tabanları ve Data Stores: Riak gibi bazı veritabanları CRDT kavramlarını benimsemiş veya kısmen kullanmıştır. Redis gibi bellek içi veri yapısı kullanan teknoloji stack’lerinde de CRDT kütüphaneleri bulunmaktadır.
Gerçek Zamanlı İşbirliği Uygulamaları: Google Docs benzeri uygulamalarda aynı dokümanı birden fazla kişi eş zamanlı olarak düzenler. CRDT’ler, bu senaryolarda çatışmaların çözümlenmesini kolaylaştırabilir.
Oyun Sunucuları ve Multiplayer Senaryolar: Oyuncuların hareketleri, skor tablosu, envanter bilgileri gibi gerçek zamanlı güncellemelerin yapıldığı ortamlarda CRDT’ler kullanılabilir.
Dağıtık Cache Sistemleri: Coğrafi olarak dağınık bölgelerde cache tutmak ve senkronize etmek için CRDT’ler, yüksek performans ve veri bütünlüğü sunar.

3.1. Avantajlar

Basit Çatışma Çözümü: CRDT’ler, tasarımları gereği çatışmaları minimize eder veya tamamen ortadan kaldırır.
Eventual Consistency: CRDT’ler, CAP Teoremi bağlamında erişilebilirlik (availability) ve bölünme toleransını (partition tolerance) öne çıkarmak isteyen sistemlerde tutarlılığı “eventually” düzeyinde sağlar.
Kolay Geliştirilebilirlik: CRDT yapıları bir kez anlaşıldığında, uygulamada karmaşık çatışma çözümü algoritmaları yazmaya gerek kalmaz.
Idempotent ve Commutative Operasyonlar: Dağıtık sistemlerde mesaj kaybı, tekrar iletimi veya farklı sıralama gibi durumlar yaşandığında, CRDT’ler aynı veriyi tekrarlayarak veya farklı sıralarla işleme almaktan etkilenmez.

3.2. Dezavantajlar

Ek Metadata: CRDT’ler genellikle ek metadata tutar. Bu, bellek kullanımı açısından ek yük oluşturabilir.
Her Türlü Operasyonu Kapsamaz: CRDT modelleri, tüm veri yapısı türleri veya tüm uygulama ihtiyaçları için en uygun çözüm olmayabilir.
İşlemin “Son Hali” Anlamı Değişebilir: Eventual consistency doğası gereği, veri durumunun “anlık” hâli sistem genelinde tutarlı olmayabilir. Zamanla tutarlı hâle gelir.

4. Örnek CRDT Uygulaması

Aşağıdaki örnekte, dağıtık ortamda G-Counter (sadece artım yapan sayaç) mantığını Go diliyle basit bir şekilde göstereceğiz. Bu sayaç, her bir replikada artan değerleri tutar ve replikalar arasındaki değerler birleştirilerek (merge) toplam sonuca ulaşır.

Not: Bu kod örneği tümüyle “production-grade” düzeyde bir CRDT olmayıp, konsepti açıklamaya yöneliktir.

package main

import (
    "fmt"
    "sync"
)

// GCounter represents a simple grow-only counter CRDT.
type GCounter struct {
    // internal slice holds the counters for each replica
    values []int
    mu     sync.Mutex
}

// NewGCounter initializes a GCounter with a given number of replicas.
func NewGCounter(numReplicas int) *GCounter {
    return &GCounter{
        values: make([]int, numReplicas),
    }
}

// Increment increments the counter for the given replica ID.
func (c *GCounter) Increment(replicaID int) {
    c.mu.Lock()
    defer c.mu.Unlock()
    c.values[replicaID]++
}

// Value returns the total count by summing all replica counters.
func (c *GCounter) Value() int {
    c.mu.Lock()
    defer c.mu.Unlock()

    total := 0
    for _, v := range c.values {
        total += v
    }
    return total
}

// Merge merges another GCounter into the current one. 
// It takes the maximum value for each replica index.
func (c *GCounter) Merge(other *GCounter) {
    c.mu.Lock()
    defer c.mu.Unlock()

    // We assume both counters have the same length.
    for i := 0; i < len(c.values); i++ {
        if other.values[i] > c.values[i] {
            c.values[i] = other.values[i]
        }
    }
}

func main() {
    // Suppose we have 3 replicas in the system
    gc1 := NewGCounter(3)
    gc2 := NewGCounter(3)
    gc3 := NewGCounter(3)

    // Replica 1 increments its local counter
    gc1.Increment(0) // increment by replicaID = 0
    gc1.Increment(0)
    gc1.Increment(0)

    // Replica 2 increments its local counter
    gc2.Increment(1) // increment by replicaID = 1
    gc2.Increment(1)

    // Replica 3 increments its local counter
    gc3.Increment(2) // increment by replicaID = 2
    gc3.Increment(2)
    gc3.Increment(2)
    gc3.Increment(2)

    // Let's merge them to simulate synchronization
    gc1.Merge(gc2)
    gc1.Merge(gc3)

    // Now all replicas would eventually do the same merges:
    gc2.Merge(gc1)
    gc3.Merge(gc1)

    // The total value of any merged replica should be:
    // gc1 replica: 3 increments (by replica 0)
    // gc2 replica: 2 increments (by replica 1)
    // gc3 replica: 4 increments (by replica 2)
    // => total = 3 + 2 + 4 = 9
    fmt.Println("Final merged value at gc1:", gc1.Value())
    fmt.Println("Final merged value at gc2:", gc2.Value())
    fmt.Println("Final merged value at gc3:", gc3.Value())
}

Program çalıştırıldığında çıktısı aşağıdaki gibi olacaktır.

Final merged value at gc1: 9
Final merged value at gc2: 9
Final merged value at gc3: 9

Programın çalışır haline şuradan erişilebilir.

GCounter Yapısı (Struct): values dizisi her bir replikanın kendi lokal sayacını tutar.
Increment: Belirtilen replicaID’nin sayacını artırır.
Value: Tüm replikaların sayacını toplayarak o anki toplam değeri döndürür.
Merge: İki GCounter’ı birleştirir. Aynı index (replicaID) için maksimum değeri alır. Böylece kimsenin yaptığı artış kaybolmaz. Bu, “grow-only” mantığına dayanır.

Gerçek bir sistemde bu değerlerin ağ üzerinden diğer replikalara taşınması, gossip protokolleri veya bir mesajlaşma sistemiyle yapılabilir. Ayrıca, replikalarda belirli aralıklarla gelen güncellemeler birleştirilebilir.

CRDT’ler (Conflict-free Replicated Data Types), günümüz dağıtık sistemlerinde sık sık karşılaşılan veri tutarlılığı ve çatışma (conflict) problemlerine etkin çözümler sunarlar. Geleneksel dağıtık veri yapılarına göre daha fazla metadata gerektirmelerine rağmen, güçlü sonunda tutarlılık (Strong Eventual Consistency) sağlamada önemli bir kavramdır.

CRDT yaklaşımı, mikroservisler, gerçek zamanlı işbirliği (collaborative editing) ortamları ve veri tutarlılığının kritik olduğu birçok senaryoda sıklıkla karşımıza çıkmaktadır. Uygulama gereksinimlerinize uygun CRDT yapısını seçerek, dağıtık ortamdaki veri tutarlılığı sorunlarını büyük oranda yönetilebilir bir seviyeye çekebilirsiniz. Özellikle artan kullanıcı sayısı, veri merkezi sayısı ve coğrafi dağıtım gibi karmaşık problemlerin yaşandığı ortamlarda CRDT’lerin sağladığı kolaylıklar son derece değerlidir.

hkucuk