cola: Gerçek zamanlı ortak düzenleme için metin CRDT teknolojisi

 (nomad.foo)
1 puan yazan GN⁺ 2023-09-04 | 1 yorum | WhatsApp'ta paylaş
  • cola, Rust ile yazılmış, gerçek zamanlı ortak düzenleme için bir metin CRDT’sidir; merkezi bir koordinatör olmadan birden fazla eşin aynı anda düzenlediği belgeleri aynı duruma yakınsatmaya odaklanır
  • Belge konumlarını basit ofsetler yerine ReplicaId.n biçimindeki Anchor ile sabitleyerek, eşzamanlı düzenleme sırasında konum anlamının kayması sorununu önler
  • Ekleme çakışmaları Lamport timestamp ve ReplicaId sıralamasıyla tutarlı biçimde çözülür; silme işlemleri ise gerçek kaldırma yerine tombstone ve version vector ile birleştirme koşullarını yönetir
  • Uygulama tarafında, Rust’ın güvenli sahiplik modeli içinde logaritmik zamanlı arama ve ekleme hedefiyle EditRun tabanlı RLE ve Vec indeksleriyle ifade edilen bir G-tree kullanılır
  • Benchmark’larda cola, diamond-types, automerge, yrs ile karşılaştırıldı; upstream’de diamond-types’tan 1.4 ila 2 kat daha hızlıyken downstream’de de çok yüksek performans gösterdi

cola’nın ele aldığı ortak düzenleme problemi

  • cola, Rust ile yazılmış bir metin CRDT’sidir ve gerçek zamanlı ortak düzenlemede merkezi bir otorite olmadan birden fazla kopyanın aynı duruma yakınsaması için tasarlanmıştır
  • Ağ katmanında yalnızca, tüm düzenlemelerin eninde sonunda tüm eşlere ulaşacağı yönünde asgari bir varsayım yapılır
    • Düzenlemeler birden fazla kez iletilebilir
    • Düzenlemeler rastgele sırayla gelebilir
    • Tüm eşler eninde sonunda tüm düzenlemeleri almalıdır
  • Amaç, tüm düzenlemeler alındıktan sonra belge durumlarının aynı olması kadar, kullanıcı açısından ortaya çıkan belgenin de makul görünmesidir

Ofset yerine Anchor ile konumu sabitleme

  • insert "abc" at offset 8 gibi ofset tabanlı düzenlemeler, başka bir eş ön taraftaki bölgeyi aynı anda düzenlediğinde anlam değiştirebilir ve kopyaların ayrışmasına yol açabilir
  • cola, belge konumlarını karakter içeriği ya da ofset ile değil, kararlı tanımlayıcılarla referans alır
    • Her eş, eklediği karakterlere artan bir numara verir
    • Eş, benzersiz tanımlayıcı olan bir ReplicaId taşır
    • ReplicaId.n çifti, karakterin benzersiz konum tanımlayıcısı olan Anchor haline gelir
  • n değeri yerel sayaç artışıyla benzersiz kılınabilir, ancak merkezi sunucu olmadan ReplicaId için küresel benzersizlik garantisi vermek zordur
    • cola, UUID benzeri şekilde çakışma olasılığı ihmal edilebilir kadar düşük olan büyük rastgele tamsayılar kullanılacağını varsayar
  • Ekleme işlemi konumu tek bir Anchor ile belirtir; silme işlemi ise aralığı başlangıç ve bitiş olmak üzere iki Anchor ile belirtir

Ekleme çakışmalarını aynı sırada sıralama

  • Aynı Anchor’a birden fazla ekleme gelirse cola, sıralamayı Lamport timestamp ile belirler
  • Lamport saati şu kurallarla güncellenir
    • Yerelde metin eklenirken saat 1 artırılır
    • Uzak bir ekleme alındığında max(current, remote_timestamp) + 1 olarak ayarlanır
  • Herhangi bir A eklemesi, B eklemesini zaten birleştirmiş bir ortamda üretildiyse, A’nın Lamport timestamp’i B’den büyük olur
  • Çakışan eklemeler, Lamport timestamp azalan sırayla sıralanır
  • Anchor ve Lamport timestamp’in de aynı olduğu eşzamanlı eklemelerde, kullanıcı açısından daha doğru bir sıra bulunmadığından, eşler arası tutarlılık için ReplicaId artan sırayla sıralama yapılır

Silme işlemleri tombstone ve version vector ile ele alınıyor

  • Silme işlemleri, başlangıç ve bitiş ofsetleri Anchor’a çevrildikten sonra diğer eşlere yayılır
  • İki eş aynı bölgeyi aynı anda silerse, undo hesaba katılmadığında sonuç tek kez silinmiş olmasıyla aynıdır
    • cola şu anda silme undo’sunu desteklemiyor
  • Silme işlemlerinin ele alınmasında üç zorluk vardır
    • Silinen metin tamamen kaldırılırsa, henüz ulaşmamış düzenlemelerin Anchor’ları o bölgenin içinde olabilir
    • Uzak bir silme işlemi çok erken birleştirilirse, silmeyi üreten eşin gördüğü içerik ile alıcı eşin içeriği farklı olabilir ve kopyalar ayrışabilir
    • Silme aralığı içinde olsa bile, silmeyi üreten eşin henüz görmediği karakterler silinmemelidir
  • İlk sorun tombstone ile çözülür
    • Silinen karakterler belgede kalır ancak silinmiş olarak işaretlenir
    • Bu yaklaşım bellek kullanımını artırır
  • Kalan sorunlar, silme mesajına version vector eklenerek çözülür
    • Anahtar ReplicaId, değer ise silmeyi üreten eşin o anda gördüğü son karakter timestamp’idir
    • Alıcı eşin version vector’ü, silme mesajındaki version vector’ün seviyesine ulaşana kadar silmenin birleştirilmesi bekletilir
    • Silme version vector’ündeki timestamp’ten büyük karakterler silme hedefinden atlanır
  • cola’da version vector yerine version map adı kullanılır

Replica ile metin tamponunun ayrılması

  • Her eşin yerel belge durumu cola’da Replica ile ifade edilir
  • cola’nın CRDT algoritmasının gerçek dize içeriğini bilmesine gerek yoktur
    • API işlevleri dizeyi argüman olarak almaz
    • cola, belge içeriğiyle değil yalnızca sayısal bloklarla çalışır
  • Bu tasarım, CRDT mekanizmasını gerçek metin tamponu uygulamasından ayırır

RLE ve EditRun ile meta veriyi azaltma

  • Her karaktere meta veri eklemek yüksek performanslı bir uygulama geliştirmeyi zorlaştırdığı için cola, ardışık timestamp’lere sahip blokları run-length encoding ile birleştirir
  • Örneğin Wikipedia’daki Manhattan Project sayfasının tamamı yapıştırıldığında 107.000 blok yerine tek bir blok olarak temsil edilebilir
  • İmleç taşınmadan veya silme yapılmadan bir cümle karakter karakter yazıldığında da, her tuş vuruşu için ayrı blok oluşturmak yerine tek bir run olarak temsil edilebilir
  • cola’da bu tür ardışık bloklara EditRun denir
    • Bir kez bölünmüş bir EditRun, belge ömrü boyunca sabit kalır ve artık genişlemez
    • Henüz bölünmemiş run’lar active durumdadır
  • Var olan bir EditRun’ın ortasına metin eklenirse run ikiye bölünür ve yeni metin araya yerleştirilir
  • Metin silinirse ilgili bölüm run’dan ayrılır ve tombstone olarak işaretlenir
    • Silinmiş run’lar da aynı şekilde RLE ile temsil edilebildiği için tombstone’un bellek yükü azaltılabilir

Bağlı listeden B-tree’ye

  • Yerel düzenlemelerin upstream yolu, ofset tabanlı düzenlemeleri diğer eşlere gönderilebilir düzenlemelere dönüştürme sürecidir
    • Hem ekleme hem silme için, ofseti içeren run bulunmalı ve Anchor oluşturulmalıdır
    • Gerekirse run’lar eklemede en fazla 2, silmede ise en fazla 3 parçaya bölünür
  • Bağlı listede run bölme O(1) olsa da, ofseti içeren run’ı bulmak için baştan tarama gerektiğinden doğrusal zaman gerekir
  • Mevcut active run ve onun ofseti önbelleğe alınırsa aynı konumda tekrar eden düzenlemeler hızlı olabilir, ancak en kötü durum yine doğrusaldır
  • cola, en kötü durumda logaritmik zaman performansı için B-tree yapısını değerlendirir
    • Run’lar B-tree’nin yaprakları olarak ifade edilir
    • inode’lar çocukları ve çocuk uzunluklarının toplamını saklar
    • tombstone run’lar uzunluğa 0 olarak katkı verir
    • root’un uzunluğu tüm belge uzunluğuna eşittir
  • B-tree, arama ve eklemeyi O(log n) sürede yapabildiği için yerel düzenlemeler logaritmik zamanda işlenebilir
  • Ancak uzak düzenlemelerde Anchor -> run dönüşümünü verimli yapmak için Anchor’ın bulunduğu yaprağın bulunması gerekir

G-tree: Vec indeksleriyle ifade edilen B-tree

  • Sıradan bir B-tree yaprağına giden işaretçiye sahip olmak, top-down ekleme sürecinde yaprağa nasıl inileceğini anlamak için yeterli değildir
  • Bottom-up işlemlerde her düğüm için ebeveyn işaretçisi gerekir; Rust’ın güvenli sahiplik modelinde bu, Rc<RefCell<_>> gibi yapılar gerektirebilir ve yavaşlayıp karmaşıklaşabilir
  • cola, tüm düğümleri Vec gibi dinamik bir dizide tutar ve düğümler arası referansları işaretçi yerine indeks ile ifade eder
    • Vektör tüm düğümlerin sahibidir
    • Her düğüm ebeveyn indeksini tutabilir
    • unsafe kod kullanmadan çift yönlü gezinme mümkündür
  • Bu yapı, düğüm indekslerinin değişmemesi varsayımına dayanır
    • Yeni düğümler vektörün sonuna append edilir
    • cola, run’ları kaldırmak yerine tombstone ile işaretlediği için indeks geçersizleşmesi yaşanmaz
  • cola, vektör içindeki bu yalnızca büyüyen ağaç yapısına G-tree adını verir
  • G-tree Rust kodu, B-tree’nin ebeveyn-çocuk yapısını korurken yalnızca bellek temsilini değiştiren bir biçimdedir

G-tree’nin oluşturduğu performans özellikleri

  • G-tree, B-tree gibi top-down arama ve eklemeyi logaritmik zamanda gerçekleştirir
  • Yaprağın vektör indeksi olan LeafIdx, kararlı bir yaprak tanımlayıcısı olarak kullanılabilir
  • Mevcut active run, işaretçi yerine LeafIdx ile önbelleğe alınabilir
    • Aynı imleç konumunda tekrar eden düzenlemelerde active run genişletilir ve yalnızca ataların uzunlukları root’a kadar güncellenir
    • Bu işlem, ağaç dolaşımı ve yeni tahsis gerektirmeden birkaç tamsayı karşılaştırması ve 2-4 tamsayı toplamasıyla yapılabilir
  • cola’nın G-tree’si 32 dallanma faktörü kullanır ve inode ortalama doluluğu yaklaşık 20 çocuktur
    • Yalnızca 4 seviye ile genellikle yaklaşık 160 bin farklı EditRun saklanabilir
    • automerge-paper düzenleme trace’i işlendiğinde cola’nın G-tree’si yaklaşık 15 bin EditRun içerir
    • Söz konusu trace 260 bin düzenleme içerir ve birkaç güne yayılarak kaydedilmiştir
  • G-tree’de düğümler zaten doğrusal bellekte tutulduğu için serileştirme ve serileştirmeden geri yükleme de basittir

Anchor’ı LeafIdx’e dönüştürme

  • Uzak düzenlemelerin downstream yolu, insert 2.3..7 at 1.2, delete between 3.4 and 2.2 gibi Anchor tabanlı düzenlemeleri yerel belge ofset düzenlemelerine dönüştürme sürecidir
  • G-tree yukarı ve aşağı yönde gezinebildiği için, bir Anchor’ı içeren run’ın LeafIdx değeri biliniyorsa ilgili ofset hesaplanabilir
  • Kilit nokta Anchor -> LeafIdx dönüşümüdür
  • Basit tasarımda yardımcı bir G-tree veya B-tree tutulur; yapraklarda ReplicaId, zamansal aralık ve ana G-tree’deki LeafIdx saklanır
    • Yapraklar ReplicaId ve zamansal aralık sırasına göre tam sıralıdır
    • Anchor temelinde ağaç aşağı inilerek istenen LeafIdx bulunabilir
    • Arama ve ekleme işlemleri de O(log n)’dir
  • Gerçek cola kaynak kodu bu yardımcı G-tree yaklaşımını birebir kullanmaz
    • Gerçek uygulamada arama ve ekleme O(log f)’dir
    • Burada f, Anchor’ı içeren EditRun’ın zaman içinde bölündüğü fragment sayısıdır
    • f her zaman n’den küçüktür ya da eşittir ve çoğu zaman çok daha küçüktür

Mevcut olgunluk seviyesi ve kalan işler

  • cola’nın tasarımı, yakınsama, niyet koruma ve performansı hedefleyen bir temel sunar
  • Üretime hazır hale gelmesi için undo/redo desteği ve birkaç ek çalışma daha gereklidir

Rust CRDT benchmark’ları

  • cola, Rust tabanlı 3 CRDT ile karşılaştırıldı
  • Benchmark’lar, gerçek character-by-character düzenleme trace’lerini işleme süresini ölçer
    • Rust benchmark kütüphanesi criterion kullanılır
    • Hem upstream hem downstream yönü ölçülür
    • Benchmark kodu crdt-benches deposunda yer alır
  • Grafikler, cola performansının 100 katını referans çizgisi olarak alır; cola’dan 100 kattan daha yavaş ölçümler gösterilmez
  • Çalışma ortamı 2018 MacBook Pro, 2.2GHz 6-Core Intel Core i7’dir
    • Farklı makinelerde sayılar değişebilir, ancak göreli performansın benzer olacağı düşünülür

Benchmark sonuçları

  • Upstream yönünde yrs ve automerge referans çizgisini aşıyor
  • Upstream’de cola, diamond-types’tan 1.4 ila 2 kat daha hızlı
  • Downstream yönünde diamond-types, tüm trace’lerde crash olduğu için ölçüm sonucu alınamıyor
    • Kütüphanenin yanlış kullanılmış olması durumunda sonuçların güncelleneceği notu eklenmiş
  • Downstream’de cola önceye göre yaklaşık 2 kat daha yavaş
    • Uzak düzenlemeleri birleştirmenin, genel olarak yerel düzenleme üretmekten daha maliyetli olması nedeniyle bu beklenen bir sonuç
  • cola, her iki yönde de hızlı rope kütüphaneleriyle benzer ya da daha iyi düzeyde çalışıyor ve şu anda en hızlı metin CRDT uygulaması olarak değerlendiriliyor

İlgili okumalar

1 yorum

 
GN⁺ 2023-09-04
Hacker News yorumları

  • G-tree’nin hâlâ ebeveyn işaretçisi eklenmiş bir B-tree olduğunu düşünüyorum
    Dizide saklanması yalnızca bir temsil meselesi; yapıyı temelden değiştirmiyor
    Hâlâ işaretçi saklıyor, sadece bayt birimleriyle değil düğüm boyutu birimleriyle; adres alanının başlangıcına göre değil, ilk dizi elemanına göre göreli konumlar olarak
    Örneğin açık referanslar olmadan bir dizide saklanan tam ikili ağaç da, indeks x’in çocuklarının 2x + 1 ve 2x + 2’de olduğu örtük bir temsilden ibaret olsa da hâlâ ikili ağaç diye adlandırılır

    • Yine de temsil biçiminden bahsetmek faydalı
      Özellikle mutlak referanslar yerine göreli ve kendi kendini yöneten referanslara yönlendiren dillerde daha da öyle
      İlginç bulduğum ağaç temsil biçimlerinden biri, düğümleri derinlik öncelikli dolaşım sırasıyla düz bir dizide saklamak
      Salt okunur olduğunda ve okuyucu zaten derinlik öncelikli dolaşacaksa oldukça verimli olabilir
      Aklıma S-expression ve HTML geliyor

  • API’de gözden kaçırmadıysam, bu kalın/italik gibi biçimlendirme aralıklarını desteklemiyor gibi görünüyor
    Bildiğim kadarıyla zengin metin CRDT algoritmalarında hâlâ en ileri nokta Peritext https://www.inkandswitch.com/peritext/
    Bu projenin Peritext algoritmasının zengin metin özelliklerini de alması iyi olurdu

    • CRDT alanını biraz ilgiyle izleyen biri olarak, daha genel amaçlı bir yapılandırılmış veri CRDT’si yapmanın mümkün olup olmadığını hep merak etmişimdir
      Kullanıcının anlamsal olarak geçerli bir durumu tarif eden bir model veya şema tanımladığı bir yaklaşım
      Örneğin JSON’u doğrudan birleştirirseniz sözdizimsel olarak geçerli, ama anlamsal olarak saçma bir durum ortaya çıkabilir
      Peritext algoritmasının kalın/italik/alt çizginin eklemeli işlemler olduğunu, vurgulama renginin ise olmadığını bilmesi gibi; kullanıcının şemada state: notStarted ile completionDate: 2023-09-04 değerlerinin bir arada olamayacağını ilan edebilmesi güzel olurdu diye düşünüyorum
    • Soru: Yazıda Cola’nın bilinmeyen veri türleri için yalnızca çakışmasız düzenlemeyle ilgilendiği, fiilen yalnızca karakter akışı ve konumlarla çalıştığı söyleniyor
      O hâlde HTML’de olduğu gibi biçimlendirmenin kendisini metnin içinde ifade etmek mümkün olmaz mı?
      Diğer zengin metin temsillerini iyi bildiğim söylenemez, o yüzden emin değilim
      Ayrıca yukarıda bağlantısı verilen Peritext belgesine bakınca tam da RTF’ye özgü bu zorlukları ele aldığını gördüm ve oldukça ilginç buldum

  • Automerge veya Y.js/Yrs ile karşılaştırıldığında performans ya da özellik farkları var mı?

    • Yazının “üçüncü bölümü”, “Rust ile uygulanmış diğer 3 CRDT olan diamond-types, automerge, yrs ile cola’yı benchmark ettim” diye başlıyor
      Bu cola kütüphanesi işlem hızı açısından epey avantajlı görünüyor
      Bellek kullanımı da merak konusu

  • Ian Piumarta’nın aynı adlı çalışmasıyla karıştırılmamalı
    https://www.piumarta.com/software/cola/
    https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=91...

    • Ya da bir dönem MergeTree’ye (LSM) alternatif olarak görülen, ama artık kullanılmayan Cache Oblivious Lookahead Arrays de var https://github.com/giannitedesco/cola
    • coda.io diye Notion klonu tarzı bir uygulama da var

  • İyi yapılmış bir çalışma, ama adil bir benchmark gibi görünmüyor
    İşlemleri hesaplayıp saklamıyor, gerçek metni de saklamıyor
    Bunun üzerine delta güncellemelerini destekleyen bir metin CRDT’si yapmak için kullanıcının ayrı bir yapıda OpID => Text saklaması gerekir; bunun maliyeti de düşük değil

  • slotmap crate’i (https://docs.rs/slotmap/latest/slotmap/) kullanılırsa indeks kayması ya da bir “indeksin” başka bir değeri göstermesi endişesi olmadan silme desteklenebilir
    slotmap’te buna anahtar deniyor ve anahtarın içinde sürüm numarası da bulunuyor

    • CRDT bağlamında da çalışır mı?
      Sıralama belirlemek zor, sürüm de yalnızca yerelde anlamlı olabilir diye merak ediyorum

  • Etherpad ve Word’ün kaldıramadığı bir projede bunu denemeyi düşünüyorum

  • Bağlı tüm istemcilerin tüm düzenlemeleri aldığını varsayarsak, ofset ve ekle/sil/değiştir komutlarının önüne mevcut metin durumunun beklenen hash’ini koyamaz mıyız?
    Böylece düzenlemenin yalnızca uygun duruma uygulanacağını neredeyse garanti edebiliriz; sonraki değişiklikler de “uygulanması beklenen veri durumunun hash’i” anahtar olarak kullanılan bir sözlükte biriktirilebilir
    Elbette aynı veri üzerinde hash işlemini tekrar tekrar hesaplamak gerekeceği için maliyetli olur, ama anlaması ve uygulaması çok basit

    • Bu yöntemle asenkron düzenlemeler asla uygulanmaz
      Ben belgede yerel bir düzenleme yaparsam, siz de uzaktan bir düzenleme yaparsanız, sizin “beklenen durum” hash’iniz bundan sonra benim belge durumumla asla eşleşmez
      Çünkü ben yerel değişikliği zaten yapmış olurum
      CRDT’nin yakınsamayı garanti etmesi için tüm istemcilerin tüm düzenlemeleri alması gerektiği doğru; ama güncellemeleri belirli bir sırayla uygulamak zorunda olmama özelliği, gerçek dünyadaki dağıtık kullanım senaryolarında önemli

  • Tarayıcıda formlarda birlikte düzenlemeyi kolayca açmanın bir yolu olup olmadığını merak ediyorum
    İki kişi aynı sayfayı veya formu açtığında, diğerinin şu anda hangi giriş alanını düzenlediği görülebilse ve metin giriş alanlarında metin CRDT’si kullanılsa güzel olurdu
    Yjs ile benzer bir şey uygulamaya çalışmıştım ama oldukça zordu ve iyi çalışmadı

    • Yjs’in neden uymadığını merak ettim
      Bu kullanım için biçilmiş kaftan gibi görünüyor