- CRDT (Conflict-free Replicated Data Type, çatışmasız çoğaltılmış veri tipi), ağ bölünmesi veya eşzamanlı değişiklikler durumunda bile uzlaştırma olmadan tutarlı veri birleştirmeyi mümkün kılan dağıtık bir veri yapısıdır
- Veri birleştirme değişme özelliği, birleşme özelliği ve idempotentlik sağlıyorsa, tüm kopyalar sonunda aynı duruma yakınsar
- Temsili türler arasında G-Counter, PN-Counter, G-Set, 2P-Set, OR-Set, LWW-Register, MV-Register, RGA, WOOT, Logoot bulunur; bunların her biri farklı ekleme, silme, yeniden ekleme ve sıralamayı koruma gereksinimlerini karşılar
- Delta CRDT, tüm durum yerine yalnızca değişiklikleri göndererek verimliliği artırır; Garbage Collection ise meta verinin birikmesi sorununu çözmek için temel bir zorluktur
- CRDT kusursuz bir çözüm değildir, ancak anlık tutarlılıktan daha önemli olanın kullanılabilirlik olduğu sistemlerde güçlü bir seçenek olarak değerlendirilir
CRDT'nin temel kavramları
- CRDT, dağıtık ortamlarda eşzamanlı değişiklikler olsa bile uzlaştırma olmadan birleştirilebilen veri yapılarıdır
- Birleştirme işlemi değişmeli (commutative), birleşmeli (associative) ve idempotent ise tüm kopyalar aynı duruma yakınsar
- Lattice (kafes) kavramına dayanır; durumun her zaman yalnızca “yukarı” doğru ilerleyeceği şekilde tasarlanır
- Örnek: G-Counter, her kopyanın sayacını
max ile birleştirerek kayıpsız toplama sağlar
- CRDT için iki yaklaşım vardır: State-based (CvRDT) ve Operation-based (CmRDT)
- CvRDT tüm durumu birleştirir, CmRDT ise işlemleri yayar
Başlıca CRDT türleri
- G-Counter: Yalnızca artırılabilen sayaç; her kopyadaki değerler toplanır
- PN-Counter: Artırma ve azaltma için iki G-Counter'ın birleşimiyle çift yönlü sayım sağlar
- G-Set: Yalnızca ekleme yapılabilen küme
- 2P-Set: Ekleme ve silme mümkündür, ancak yeniden ekleme yapılamaz
- LWW-Element-Set: Zaman damgası tabanlıdır; en son işlem kazanır
- OR-Set: Benzersiz etiketler kullanarak eşzamanlı eklemelerde veri kaybı olmadan birleştirme sağlar; add-wins davranışı gösterir
- LWW-Register / MV-Register: Tek bir değer saklamak içindir; LWW tek kazanan belirler, MV ise tüm eşzamanlı değerleri korur
- OR-Map: Her anahtar için OR-Set'i birleştiren harita yapısı
- RGA / WOOT / Logoot / LSEQ: Sıralı dizi verileri için CRDT'ler
- RGA ağaç tabanlıdır, WOOT çift yönlü referans tabanlıdır, Logoot/LSEQ ise konum tanımlayıcı tabanlıdır
İleri CRDT kavramları
- Causal CRDTs: Sürüm vektörleri kullanarak nedensel ilişkileri izler ve daha doğru çatışma tespiti sağlar
- Delta CRDTs: Tüm durum yerine yalnızca değişiklikleri (delta) göndererek ağ verimliliğini artırır
- Tree CRDTs: Hiyerarşik veri yapılarını (dosya sistemi vb.) çoğaltmayı destekler; ebeveyn-çocuk ilişkisinin korunması gerekir
- Observed-Remove Shopping Cart: OR-Set ile PN-Counter'ı birleştiren bir e-ticaret sepeti örneği
Garbage Collection sorunu
- CRDT, yakınsama sağlamak için meta veriyi sürekli biriktirdiğinden sonsuz büyüme sorunu ortaya çıkar
- Örnek: OR-Set etiketleri, RGA tombstone'ları
- Zaman tabanlı sona erdirme, uzlaşma tabanlı silme, sürüm vektörü tabanlı nedensel izleme, meta veri üst sınırı belirleme, checkpoint/rebase gibi çeşitli stratejiler vardır
- Her yaklaşım, güvenlik (zombi geri yüklemeyi önleme) ile alan verimliliği arasında bir ödünleşim gerektirir
Performans ve seçim rehberi
- CRDT türlerine göre alan ve zaman karmaşıklığı; kopya sayısı, öğe sayısı ve etiket sayısı gibi faktörlere göre değişir
- G/PN-Counter kopya sayısıyla orantılıdır, OR-Set etiket sayısıyla orantılıdır, RGA ise tombstone biriktirir
- Delta CRDT, birleştirme performansını büyük ölçüde iyileştirir
- Seçim ölçütleri:
- Yalnızca ekleme gerekiyorsa → G-Counter, G-Set
- Silme gerekiyorsa, yeniden ekleme gerekmiyorsa → 2P-Set
- LWW kabul edilebiliyorsa → LWW-Set/Register
- Eşzamanlı değişiklikler korunacaksa → OR-Set, MV-Register
- Sıralamanın korunması gerekiyorsa → RGA, Logoot
- İç içe yapılar için → OR-Map
Sonuç
- CRDT, uzlaştırma olmadan yakınsamayı garanti eder, ancak meta veri artışı ve karmaşıklık dezavantajlarıdır
- Kullanılabilirlik öncelikli sistemlerde faydalıdır ve her CRDT belirli problem türleri için optimize edilmiştir
- Pratikte geleneksel veritabanlarıyla birlikte kullanılır; garbage collection stratejisi zorunludur
- “Mükemmel CRDT” diye bir şey yoktur; önemli olan uygulama gereksinimlerine uygun seçim yapmaktır
1 yorum
Hacker News yorumu
CRDT ile ilgili ilginç noktalardan biri, bunun sadece birden fazla düşük seviyeli CRDT’yi birleştiren bir kütüphane olmaması
Örneğin Automerge başlı başına tam bir CRDT’dir ve matematiksel kanıtlar sayesinde eşzamanlılık altında da tutarlılığı garanti eder
Automerge ekibi, tasarımı Isabelle gibi teorem ispat araçlarıyla doğruluyor ve veritabanı dünyasındaki en güncel performans tekniklerini uygulayarak hızlı ve doğru bir gerçekleştirim hedefliyor
Gerçek zamanlı işbirliği gerektiren bir SaaS ürünü (ör. Notion, Figma) geliştiriyorsanız, karmaşık teoriyi bilmeden işbirlikçi veri yapılarını doğrudan kullanabilirsiniz
Backend tarafında basit bir key-value depolama yeterli, frontend tarafında ise tek bir kütüphane yetiyor
Ben de Redis tabanlı bir automerge kütüphanesi yaptım ve pub/sub kullanarak tam teşekküllü bir kalıcı senkronizasyon sunucusu kurabildim
Ayrıca Webdis’in websocket özelliğini kullanarak birden fazla tarayıcı arasında belge senkronizasyonu demosunu da hızlıca tamamladım
Daha iyi bir DX ve CRDT tabanlı full-stack DB istiyorsanız Triplit.dev’i öneririm. Geliştirme hızı biraz yavaşlamış olsa da özellikler yeterince olgun durumda
Kişisel olarak Loro’yu da seviyorum, ama hâlâ belge tabanlı bir yapı olduğu için sorgu motoru eksik kalıyor. İstediğiniz veriyi almak için belirli iç içe geçmiş öğeleri doğrudan belirtmeniz gerekiyor
CRDT’nin temellerinden ileri düzey kavramlara kadar gayet iyi derlenmiş bir yazıydı
Bu arada Riak hâlâ OpenRiak olarak sürdürülüyor
Son iki yıldır bizzat CRDT geliştirdim, ama çok fazla trade-off olduğunu fark edip sonunda ID tabanlı bir OT framework’üne geçtim
Bu salı Docnode.dev’i yayına almayı planlıyorum. Geri bildirim duymak isterim
İleride P2P gereken durumlar için bir CRDT modu da eklemeyi düşünüyorum
CRDT ya da OT, insanların aynı paragrafı aynı anda düzenlemesi sorununu çözmeyi amaçlayan yapılar; ama pratikte böyle durumlar neredeyse hiç yaşanmıyor
Bu yazıda anlatılan OR-Set, Monotone’un 2005’ten beri kullandığı birleştirme yöntemiyle benzer görünüyor
İlgili materyallere MarkMerge belgelerinde bakabilirsiniz
CRDT hâlâ elle uygulanması gereken bir alan
Ben de iki ay önce diamond types’tan ilham alarak dizi tabanlı bir CRDT motoru yaptım
Yapay zekadan yardım istedim ama bu tür mantık odaklı problemlerde hiç yardımcı olmadı
LLM’lerin yeni mantıkları anlayabildiğini doğrulamak için bir kara kutu testi gerektiğini düşünüyorum
Yazı harikaydı ama terimler sözlüğünde mutlaka bir indeks olması gerektiğini düşünüyorum
CRDT’nin sonuçta birleştirme çakışmalarını DB’den uygulama mantığına itmekten ibaret olup olmadığı aklıma geliyor
Doğru yazıldığında hangi katmanda olursa olsun otomatik birleştirme çözümü mümkündür
En büyük sorun UNIQUE/PRIMARY KEY çakışmalarını ele almaktı
Her sunucuya bir ID namespace’i dağıtıp, ilk oluşturulanın kazanması ve çakışma durumunda adın değiştirilmesi ya da silinmesiyle bu çözülebilir
EAV şeması kullanılırsa SQL’de özyinelemeli CTE ile graf gezinmesini kolayca uygulayabilirsiniz
Ancak PostgreSQL’de ANY tipi olmadığı için özellikleri farklı nesneleri ifade etmek zor ve FOREIGN KEY işlevini de kendiniz uygulamak zorundasınız
Yine de EAV yapısı, kalıtım gibi meta şema tasarımları için avantajlı
PostgreSQL’de CRDT türlerini doğrudan tanımlayabilmek güzel olurdu, ama şu anda monoid işlemlerine kısıt koymak mümkün değil
Sonuç olarak anahtar olmayan sütunlar için CRDT’yi uygulama katmanında ele almak gerekiyor
Kısacası CRDT, RDBMS içinde de uygulanabilir; ancak iş mantığını nereye koyacağınıza göre yaklaşım değişir