Taşınabilir ağaç CRDT'leri ve Loro'nun uygulaması

• Movable tree CRDTs and Loro's implementation

• Arka plan

  • Dağıtık sistemlerde ve iş birliğine dayalı yazılımlarda hiyerarşik ilişkileri yönetmek karmaşıktır
  • Veri yapılarında silme ve eklemeyi birleştirerek taşımayı modellediğinizde, çakışma çözümü ve kullanıcı beklentilerini karşılama zorlaşır
  • Örneğin, aynı düğüm aynı anda farklı ebeveynlere taşınırsa, aynı içeriğe sahip yinelenen düğümler oluşabilir

• Taşınabilir ağaçlardaki çakışmalar

  • Taşınabilir ağacın başlıca işlemleri: oluşturma, silme, taşıma
  • Eşzamanlı işlemler senkronize edilirken ortaya çıkabilecek çakışmalar:
    • Aynı düğümün silinmesi ve taşınması
    • Aynı düğümün farklı düğümlerin altına taşınması
    • Başka düğümlerin taşınmasıyla döngü oluşması
    • Ata düğüm silinirken torun düğümün taşınması

• Aynı düğümün silinmesi ve taşınması

  • Görece çözmesi kolaydır
  • Dağıtık sistemin zaman damgasına ya da uygulamanın özel gereksinimlerine göre bir işlem uygulanır, diğeri yok sayılır

• Aynı düğümün farklı ebeveynlerin altına taşınması

  • Eşzamanlı taşıma işlemlerini birleştirmek daha karmaşıktır
  • Uygulamaya göre çeşitli yaklaşımlar benimsenebilir:
    • Düğümü silip başka bir ebeveyn düğüm altında kopyasını oluşturmak
    • Düğümün iki ebeveyne bağlanmasına izin vermek (genellikle izin verilmez)
    • Tüm işlemleri sıralayıp art arda uygulamak

• Farklı düğümlerin taşınması sonucu döngü oluşması

  • Eşzamanlı taşıma işlemlerinden kaynaklanan döngüyü çözmek karmaşıktır
  • Birden çok çözüm vardır:
    • Hata üretmek
    • Döngüsel düğümü özel bir "timeout" alanında göstermek
    • Taşıma işlemlerini sunucuda işlemek
    • Topolojik sıralama kullanmak
    • Döngüye neden olan kenarı gizlemek

• Ata düğümün silinmesi ve torun düğümün taşınması

  • Ata düğüm silinirken torun düğümün taşınması kolayca gözden kaçabilir
  • Tüm torun düğümleri doğrudan silmek veri kaybı olarak algılanabilir

• Popüler uygulamalar çakışmaları nasıl ele alıyor?

  • Dropbox: Dosya taşımayı silme sonrası oluşturma olarak ele aldı, ancak veri kaybı riski vardı
  • Figma: Merkezi sunucu döngüyü tespit edip işlemi reddederek tutarlılığı korur

• Taşınabilir ağaç CRDT'leri

  • Merkezi çözümler yerine CRDT'ler kullanılır
  • İlk CRDT tabanlı algoritmaların uygulanması zordu ve depolama ek yükü büyüktü
  • Sürekli optimizasyonlarla bazı CRDT tabanlı ağaç senkronizasyon algoritmaları üretim ortamına uygun hale geldi

• Çoğaltılmış ağaçlar için yüksek erişilebilirlikli taşıma işlemi

  • Ağacın üç işlemi (oluşturma, silme, taşıma) taşıma işlemi altında birleştirilir
  • Taşıma işlemi Move t p m c olarak tanımlanır
  • Düğüm silme, TRASH düğümüne taşınarak ele alınır

• Küresel olarak sıralanmış mantıksal zaman damgaları

  • Dağıtık sistemde olayların nedensel sırasını belirlemek için Lamport zaman damgaları kullanılır
  • Daha küçük sayı daha erken olayı ifade eder

• Uzak işlemlerin uygulanması

  • Bir işlemin güvenliği, uygulandığı andaki ağaç durumuna bağlıdır
  • Uzak güncellemeler işlenirken en son işlemler geri alınır, yeni işlem eklenir, ardından geri alınan işlemler yeniden uygulanır

• CRDT: değişken ağaç hiyerarşisi

  • Her düğüm, geçmişteki tüm ebeveyn düğümlerini izler ve onlara sayaç atar
  • Senkronizasyon sırasında döngü oluşursa en yakın tarihsel ebeveyn düğüme yeniden bağlanır

• Loro'da taşınabilir ağaç CRDT'lerinin uygulanması

  • Martin Kleppmann'ın algoritması uygulanarak yüksek performans sağlanır
  • Alt düğümlerin sıralanabilmesi için Fractional Index algoritması entegre edilir

• Alt düğüm sıralamasındaki olası çakışmalar

  • Aynı konuma birden fazla düğüm eklenirken aynı Fractional Index atanabilir
  • Aynı Fractional Index için göreli sıralamayı belirlemek üzere PeerID kullanılır

• Uygulama ve kodlama boyutu

  • Fractional Index, düğüm sırasını sağlar
  • Kodlama boyutu en kötü durumda ek baytlar gerektirebilir, ancak bu nadir görülür

• İlgili çalışmalar

  • Fractional Index dışında taşınabilir liste CRDT'leri de vardır
  • Fractional Index, uygulaması basit olduğundan ve yalnızca göreli sıra gerektiğinde kullanışlıdır

• Benchmark

  • Loro'nun taşınabilir ağaç uygulamasının performans benchmark'ı yapıldı
  • Gerçek zamanlı iş birliği ve geçmiş sürümlere sorunsuz checkout desteği sağlanabilir

• Özet

  • Taşınabilir ağaç CRDT'lerini uygulamanın zorlukları ve iki yenilikçi algoritma tanıtılıyor
  • Loro, Martin Kleppmann'ın algoritması ile Fractional Index'i entegre ederek çeşitli uygulama senaryolarını karşılar

• GN⁺ özeti

  • Taşınabilir ağaç CRDT'leri, dağıtık sistemlerde hiyerarşik veri yapılarını yönetmede önemli rol oynar
  • Loro, yüksek performans ve verimli çakışma çözümü sunarak gerçek zamanlı iş birliği uygulamaları için uygundur
  • Alt düğüm sıralama sorununu Fractional Index kullanarak çözer
  • Benzer işlevlere sahip diğer projeler arasında Figma ve Dropbox bulunur

[GN⁺]

Hacker News yorumu

• Yeni bir çok oyunculu düzenleyici geliştiriliyor

  • Metin ve outliner çalışmalarını destekliyor
  • Belgeler büyük bir ağaç yapısına dönüştürülüyor
  • Senkronizasyon için insmov (taşıma veya ekleme) işlemi kullanılıyor
  • Sunucu değişiklikleri gönderdiğinde istemci bunları yeniden uyguluyor
  • Çoğu durumda işlemleri geri almaya gerek kalmıyor
  • Gerçek zamanlı güncellemelerde neredeyse hiç sorun yaşanmıyor

• React Table Library açık kaynak olarak sunuluyor

  • Klasör/dosya ağaç yapısını işliyor
  • Klasör/dosya taşıma, kopyalama, lazy loading gibi özellikleri destekliyor
  • Google Drive'ın neden yalnızca aynı hiyerarşi seviyesinde görüntüleme ve düzenleme yaptığını anlamayı sağlıyor

• Tavsiye isteniyor

  • Frontend'de büyük, denormalize bir ağaç kullanılıyor
  • Kullanıcı profilleri karo düzeniyle yönetiliyor
  • Güvenli güncellemeler için minimum veri gönderiliyor
  • CRDT kullanmanın durum yönetimini çok daha kolaylaştıracağı düşünülüyor
  • Tarayıcı sekmeleri arasında senkronizasyon mümkün hale geliyor

• Google Docs/Zoho Writer gibi biçimlendirilmiş metin içerikleriyle çalışırken ağaç manipülasyonu gerekiyor

  • Eşzamanlı çakışma sorunlarını çözmek zor
  • Liste CRDT ile ağaç CRDT'nin birleştirilebileceği düşünülüyor
  • Tüm işlemlere iki boyutlu adres eklemek gerekiyor

• Görüntü (piksel) ve 3D model gibi veri yoğun uygulamalar için pratik CRDT'ler olup olmadığı merak ediliyor

• İlk paragrafın ChatGPT'nin üslubunu andırdığı düşünülüyor