- İşbirlikçi yazılımlarda hiyerarşik yapılar aynı anda düzenlendiğinde, yinelenen düğümler, döngüler ve silinmiş ataların alt düğümlerinin taşınması gibi ağaç çakışmaları ortaya çıkar; Loro bunu taşınabilir ağaç CRDT’si olarak uygular
- Martin Kleppmann ve diğerlerinin yaklaşımı, oluşturma-silme-taşıma işlemlerini
Move t p m c ile birleştirir ve silmeyi TRASH düğümüne taşıma olarak ele alarak eşzamanlı alt düğüm taşımalarını korur
- Küresel sıralama Lamport Timestamp ve Peer ID ile oluşturulur; uzak bir işlem mevcut sıranın ortasına girerse döngüleri önlemek için undo-do-redo kullanılır
- Loro, kardeş düğümlerin sıralanması için Fractional Index ile birleştirir ve aynı konuma eşzamanlı eklemelerde indeks çakışırsa bunu PeerID, jitter ve indeks sıfırlama ile ele alır
- Benchmark sonuçlarında Loro Movable Tree, 1000 düğüm oluşturduktan sonra 10000 rastgele taşıma işlemini 28 ms’de gerçekleştirerek gerçek zamanlı işbirliği ve geçmiş sürüm checkout’u için yeterli performans gösterir
İşbirlikçi ağaçlarda ortaya çıkan çakışmalar
- Dağıtık sistemlerde ve işbirlikçi yazılımlarda hiyerarşik ilişkileri yönetirken taşımayı silme ve ekleme birleşimi olarak modellemek, kullanıcı beklentileri ile çakışma çözümleme biçiminin kolayca uyumsuz hale gelmesine neden olabilir
- Aynı düğüm birden fazla replica’da aynı anda farklı ebeveynlere taşınırsa, bir düğüm iki kez silinip iki ebeveyn altında yeniden oluşturulabilir ve aynı içeriğe sahip yinelenen düğümler oluşabilir
- Taşınabilir ağacın temel işlemleri üç tanedir: oluşturma, silme, taşıma
- Senkronizasyon sırasında başlıca sorun çıkaran durumlar şunlardır
- Aynı düğüm silinirken aynı anda taşınır
- Aynı düğüm farklı ebeveynlerin altına taşınır
- Farklı düğüm taşımaları birleşerek döngü oluşturur
- Ata düğüm silinirken alt düğüm taşınır
Çakışma türlerine göre ele alma yöntemleri
- Aynı düğümün silinmesi ile taşınması çakışırsa, dağıtık sistemin timestamp’ine ya da uygulama gereksinimlerine göre bir işlem uygulanıp diğeri yok sayılabilir
- Aynı düğüm farklı ebeveynlerin altına taşındığında seçenekler uygulamaya göre değişir
- Düğüm silinip ardından farklı ebeveynler altında kopyaları oluşturulur ve sonrasında bağımsız biçimde ele alınır
- Bir düğümün iki ebeveyni işaret etmesine izin verilebilir, ancak bu ağaç yapısını bozduğu için genel olarak kabul edilmesi zordur
- Tüm işlemler sıralanıp sırayla uygulanırsa tüm peer’lerde aynı sonuç üretilebilir
- Farklı düğümlerin taşınması döngü oluşturduğunda, taşınabilir ağaçlarda çakışma çözümü özellikle karmaşık hale gelir
- Matthew Weidner; hata işleme, “time-out” alanı render etme, sunucu tabanlı reddetme, topolojik sıralamadan sonra döngü oluşturan işlemleri atlama, render sırasında belirli edge’leri gizleme ve önceki ebeveyne geri döndürme gibi yöntemleri derler
- Ata düğüm silinirken alt düğümün taşınması durumu da gözden kaçırılması kolay bir durumdur
- Atanın tüm alt düğümleri hemen silinirse kullanıcı kendi verisinin kaybolduğunu sanabilir
Dropbox ve Figma’nın yaklaşımı
- Dropbox başlangıçta dosya taşımayı, özgün konumdan silme ve yeni konumda oluşturma şeklinde iki adımda ele aldı
- Silme ile oluşturma arasında elektrik kesintisi ya da sistem çökmesi yaşanırsa veri kaybı riski vardı
- Günümüzde birden fazla kişi aynı dosyayı aynı anda taşımaya ve kaydetmeye çalıştığında çakışmayı algılar; genellikle özgün dosyanın bir sürümünü saklar ve bir kullanıcının değişikliği için “conflicted copy” oluşturur
- Figma, ağaç yapısını işbirlikçi sistemin en karmaşık kısmı olarak görür ve her öğeye bir
parent özelliği verir
- Merkezi sunucu, birden çok kullanıcının güncellemelerini izler ve herhangi bir işlem döngü oluşturabilecekse o işlemi reddeder
- Ağ gecikmesi nedeniyle sunucu reddetmeden önce geçici olarak döngü oluşabilir
- Bu durumda Figma, döngüye dahil olan öğeleri geçici olarak gizler ve sunucu işlemi resmen reddedene kadar durumu korur
- İlgili açıklamalar Figma’nın multiplayer technology yazısında görülebilir
Taşınabilir ağaç CRDT’lerine iki yaklaşım
- Merkezi çözüm yerine, işbirlikçi ağaç yapıları CRDT ile de ele alınabilir
- İlk dönem CRDT tabanlı ağaç algoritmalarının uygulanması zordu ve depolama ek yükü yüksekti; ancak optimizasyonlar ve iyileştirmelerle bazı üretim ortamlarına uygun ağaç senkronizasyon algoritmaları ortaya çıktı
- Temsili iki CRDT tabanlı yaklaşım vardır
Kleppmann yaklaşımı: tüm işlemleri Move ile birleştirmek
- A highly-available move operation for replicated trees, ağacın oluşturma-silme-taşıma işlemlerini tek bir move işlemi altında birleştirir
- Move işlemi
Move t p m c olmak üzere dört değerle tanımlanır
t: Lamport timestamp gibi benzersiz ve sıralanabilir bir timestampp: ebeveyn düğüm ID’sim: düğümle ilişkili metadatac: çocuk düğüm ID’si
- Ağaçta
c yoksa, ebeveyn p altında çocuk c oluşturan bir oluşturma işlemi olur
c zaten varsa, mevcut ebeveynden yeni ebeveyn p altına taşıyan bir taşıma işlemi olur- Silme, belirlenmiş
TRASH düğümüne taşıma şeklinde ele alınır
TRASH altındaki tüm alt düğümler silinmiş kabul edilir- Ancak bellekte tutulurlar; böylece eşzamanlı düzenlemeler bu düğümü başka bir düğümün altına taşıyabilir
- Bu, ata silme ile alt düğüm taşımanın aynı anda gerçekleştiği durumları ele almak için kullanılan bir mekanizmadır
Sıralama ve unsafe operation
- Silme de move işlemi olarak tanımlandığı için, “aynı düğümün silinmesi ve taşınması” iki move işleminin çakışmasına dönüşür
- Geriye kalan temel sorun iki tanedir
- Aynı düğümü farklı ebeveynlerin altına taşımak
- Farklı düğümleri taşıyıp döngü oluşturmak
- Tüm işlemler Lamport timestamp ve Peer ID ile doğrusal sıraya dizilirse, aynı düğümün eşzamanlı taşınması da sıralı iki işlem olarak ifade edilir
- Ağaç yalnızca move işlemleriyle modellendiğinde, eşzamanlı düzenlemenin istisnai durumları döngü üretmeye indirgenir
- Döngü oluşturan işlemler unsafe operation olarak ele alınır
- Algoritma tüm move işlemlerini timestamp sırasına göre sıralar
- Her işlem uygulanmadan önce döngü tespit edilir
- Döngü oluşturuyorsa ilgili unsafe operation yok sayılır ve doğru ağaç yapısı korunur
Lamport Timestamp ve uzak işlemlerin uygulanması
- Lamport Timestamp, dağıtık sistem olaylarının nedensel sırasını belirlemeyi mümkün kılar
- Her peer, 0’dan başlayan bir counter’a sahiptir
- Yerel bir olay oluştuğunda counter 1 artırılır ve bu değer timestamp olarak kullanılır
A peer’i B’ye mesaj gönderdiğinde timestamp’i eklerB, kendi mantıksal saati ile aldığı timestamp’i karşılaştırır ve daha büyük değere günceller
- Küresel sıralamada önce Lamport Timestamp karşılaştırılır; değerler eşitse tie-breaker olarak peer’in benzersiz ID’si kullanılır
- Uzak bir güncelleme mevcut sıralı işlem dizisinin ortasına girerse undo-do-redo gerekir
- En son işlemler geri alınır
- Yeni işlem araya eklenip uygulanır
- Geri alınan işlemler yeniden uygulanır
- Move işlemini hızlıca geri alabilmek için, her move uygulanmadan önce hedef düğümün old parent bilgisi cache’lenir
- Unsafe operation’ların etkisi yok sayılsa bile kayıtları tutulmalıdır
- İşlemin güvenli olup olmadığı dinamik olarak belirlenir
- Daha sonra döngüye neden olan başka bir düğüm önce silinirse, daha önce unsafe olan işlem safe hale gelebilir
- Undo sürecinde, en son etkili olan işlemin hedef ebeveynini bulmak için ineffective işaretlemesi gerekir
undo-do-redo örneği
- Yeni bir işlem, yerelde bulunmayan bir işleme bağımlıysa ara sürüm güncellemesi henüz eksik olduğundan önce geçici olarak önbelleğe alınmalı, ardından eksik güncelleme alındıktan sonra uygulanmalıdır
- Yeni
opId, mevcut tüm işlemlerden büyükse hemen uygulanabilir
- safe ise hedef düğümün mevcut ebeveyni old parent olarak kaydedilir ve move uygulanır
- unsafe ise ineffective olarak işaretlenir ve etkisi yok sayılır
- Yeni
opId, mevcut sıralamanın ortasına giriyorsa sonraki işlemler tek tek çıkarılıp geri alınır, yeni işlem uygulandıktan sonra geri alınan işlemler sırayla yeniden uygulanır
- Örnek akışta
Peer1, yerelde C'yi B altına taşıdıktan sonra Peer0'ın B'yi C altına taşıyan işlemini alır
- Lamport timestamp sıralamasında
0:3, 1:3'ten önce geldiği için önce 1:3 undo edilerek C, old parent A'ya geri döndürülür
- Ardından
0:3 ile B, C altına taşınır
- Sonra
1:3 redo edilerek C yeniden B altına taşınmaya çalışılır, ancak döngü tespit edildiği için uygulanmaz
- Ağaç durumu değişmeden kalır ve undo-do-redo süreci tamamlanır
Evan Wallace yaklaşımı: geçmiş ebeveynleri izleme
- Evan Wallace'ın CRDT: Mutable Tree Hierarchy yazısı, her düğümün geçmişteki tüm ebeveyn düğümlerini izlemesini sağlar
- Kaydedilen her ebeveyne bir sayaç bağlanır
- Yeni ebeveynin count değeri, ilgili düğümün tüm geçmiş ebeveyn count değerlerinden 1 daha büyüktür
- En yüksek count değerine sahip ebeveyn, mevcut ebeveyn olur
- Senkronizasyon sırasında ebeveyn kayıtları da birlikte senkronize edilir
- Döngü oluşursa sezgisel algoritma, döngüye neden olan düğümü, en yakın geçmiş ebeveynler arasından döngü oluşturmayan ve root'a bağlı olan bir ebeveyne yeniden bağlar
- Bu süreç, döngüdeki tüm düğümler yeniden ağaca bağlanana kadar tekrarlanarak replica'lar arasındaki ağaç yapısı senkronize edilir
- Bu yaklaşım pahalı undo-do-redo prosedürüne ihtiyaç duymaz, ancak her uzak move alındığında tüm düğümlerin root'a bağlı olup olmadığı kontrol edilip döngü düğümlerinin yeniden bağlanması gerektiğinden düğüm sayısı arttığında performans kötüleşebilir
- Performans karşılaştırması için ayrı bir benchmark hazırlanmıştır
Loro'nun Movable Tree uygulaması
- Loro, Martin Kleppmann ve diğerlerinin A highly-available move operation for replicated trees algoritmasını uygular
- Bu algoritma, çoğu gerçek dünya senaryosunda yüksek performans sunar
- Temel olan undo-do-redo süreci, Loro'da Eg-walker'ın (Event Graph Walker) uzak güncellemeleri uygulama biçimine çok benzer
- Yalnızca movable tree kullanmak, kardeş düğümlerin sıralanması sorununu çözmez
- outline notes veya grafik tasarım yazılımlarında layer yönetimi için alt düğümlerin sıralanması gerekir
- Kullanıcının düğüm sırasını ayarlayıp bunu diğer iş birlikçilere veya cihazlara senkronize etmesi gerekir
- Loro, movable tree içindeki alt düğümlerin sıralanabilir olmasını sağlamak için
Fractional Index algoritmasını entegre eder
Fractional Index ve eşzamanlı ekleme çakışmaları
Fractional Index, her nesneye sıralanabilir bir değer atar
- İki nesne arasına yeni bir öğe eklendiğinde yeni nesnenin
Fractional Index değeri sol ve sağ değerlerin arasında olur
- İlgili açıklamalar Figma blog ve Evan blog üzerinde görülebilir
- Dağıtık ortamda birden fazla peer aynı konuma yeni düğüm eklerse, içeriği farklı düğümlere aynı
Fractional Index atanabilir
- Loro, aynı
Fractional Index değerini korur ve aynı indeksler arasındaki göreli sıra, her peer'ın benzersiz kimliği olan PeerID ile belirlenir
- Aynı
Fractional Index her iki tarafta da varsa, bunların arasına yeni bir Fractional Index üretilemez
- Loro bu sorunu iki yöntemle ele alır
- Üretilen
Fractional Index değerine belirli miktarda jitter ekleyerek aynı indeksin oluşma olasılığını büyük ölçüde azaltır
- Örneğin 0 ile 1 arasındaki değer normalde 0.5 olacaksa, rastgele jitter ile
0.52712, 0.58312, 0.52834 gibi değerlere dönüşebilir
0.7@A ile 0.7@B arasına ekleme yapılması gerekiyorsa, 0.7 ile 1 arasından yeni düğüme ve 0.7@B düğümüne ayrı ayrı yeni Fractional Index atanacak şekilde yeniden ayarlama yapılabilir
Kodlama boyutu ve jitter ayarı
- Loro, drifting-in-space tarafından geliştirilen
Vec<u8> tabanlı Fractional Index uygulamasını kullanır
- Bu uygulama base 256 kullanır
- Varsayılan ayarda, ileri veya geri yönde art arda 128 değer eklenmesi ancak
Fractional Index byte boyutunu 1 artırır
- En kötü depolama overhead'i, her seferinde yeni değerlerin dönüşümlü olarak eklenmesi durumunda ortaya çıkar
- Örneğin
ab içinde a ile b arasına c, sonra c ile b arasına d, ardından c ile d arasına e eklemek gibi
- Bu durumda yeni bir işlem ek byte gerektirebilir, ancak bu oldukça nadir görülen bir durumdur
- Loro, özgün uygulamaya basit bir jitter çözümü ekler
Fractional Index değerinin sonuna, jitter değeri uzunluğu kadar rastgele byte eklenir- JavaScript'te
doc.setFractionalIndexJitter(number) içine pozitif bir sayı verilerek jitter etkinleştirilebilir
- Kodlama boyutu bir miktar artar ve her
Fractional Index için jitter byte'ları eklenir
- Aynı konumda
Fractional Index üretilirken çakışmanın %99 olasılıkla önlenmesi için gerekli jitter ile maksimum eşzamanlı düzenleme sayısı n arasındaki ilişki şöyledir
| jitter |
Maksimum eşzamanlı düzenleme sayısı |
| 1 |
3 |
| 2 |
37 |
| 3 |
582 |
- Sıralanmış çok sayıdaki
Fractional Index arasında ortak prefix sayısı artar
- Loro, kodlama sırasında önceki değerle aynı olan prefix bit sayısını ve kalan byte'ları saklayan prefix optimizasyonu ile toplam kodlama boyutunu azaltır
İlgili çalışmalar ve seçim nedeni
Fractional Index dışında, ağaçtaki sibling düğümleri sıralayabilen movable list CRDT'leri de vardır- Martin Kleppmann'ın Moving Elements in List CRDTs çalışması, Loro'nun Movable List yapısında kullanılır
Fractional Index çözümü uygulama açısından daha basittir- Ağaç düğümleri modellenirken alt düğümler için stable position representation sağlanmazsa tüm ağaç yapısı aşırı karmaşık hale gelir
Fractional Index için interleaving sorunu vardır
- Figma layer öğeleri veya çok seviyeli yer imleri gibi yalnızca göreli sıranın gerekli olduğu ve katı sıralı anlam bilgisinin gerekmediği durumlarda bu kabul edilebilir
Benchmark sonuçları
- Loro, Movable Tree uygulaması için rastgele düğüm taşıma, geçmiş sürümler arasında geçiş ve çok derin ağaç yapılarındaki uç koşul performansını benchmark etti
- Sonuçlar, gerçek zamanlı iş birliğini ve sorunsuz geçmiş sürüm checkout'unu destekleyebilecek düzeyde çıktı
- Test ortamı M2 Max CPU ve benchmark kodu tree.rs içinde yer alıyor
| İşlem |
Süre |
Ayar |
| 10000 rastgele taşıma |
28ms |
Önce 1000 düğüm oluştur |
| Farklı sürümlere 1000 geçiş |
153ms |
Önce 1000 düğüm oluştur, ardından 1000 taşıma yap |
| Derinliği 300 olan ağaçta farklı sürümlere 1000 geçiş |
701ms |
Yeni düğüm, önceki düğümün çocuğu |
Kullanım örneği ve demo
loro-crdt içindeki LoroTree; düğüm oluşturma, konum belirterek oluşturma, taşıma, root'a taşıma, başka bir düğümün önüne/arkasına taşıma, ebeveyn içindeki index sorgulama, Fractional Index sorgulama ve düğümün data map'ine erişim sunuyor
import { Loro, LoroTree, LoroTreeNode, LoroMap } from "loro-crdt";
let doc = new Loro();
let tree: LoroTree = doc.getTree("tree");
let root: LoroTreeNode = tree.createNode();
// By default, append to the end of the parent node's children list
let node = root.createNode();
// Specify the child's position
let node2 = root.createNode(0);
// Move `node2` to be the last child of `node`
node2.move(node);
// Move `node` to be the first child of `node2`
node.move(node2, 0);
// Move the node to become the root node
node.move();
// Move the node to be positioned after another node
node.moveAfter(node2);
// Move the node to be positioned before another node
node.moveBefore(node2);
// Retrieve the index of the node within its parent's children
let index = node.index();
// Get the `Fractional Index` of the node
let fractionalIndex = node.fractionalIndex();
// Access the associated data map container
let nodeData: LoroMap = node.data;
- Loro ile birden çok peer arasında veri senkronizasyonunu simüle eden bir Todo uygulaması demosu oluşturuldu
Movable Tree, subtask ilişkilerini ifade ediyorMap, task'ın çeşitli özelliklerini ifade ediyorText, task başlığını ifade ediyor- Oluşturma, taşıma, düzenleme ve silmenin yanı sıra Loro tabanlı sürüm geçişi de uygulanmış
- Scrollbar sürüklenerek yürütülen tüm geçmiş sürümler arasında geçiş yapılabiliyor
Özet
- Taşınabilir ağaç CRDT uygulaması; eşzamanlı taşıma, silme, döngü ve ata silme ile alt düğüm taşımanın birleşimi nedeniyle zor
- Loro, Kleppmann ve diğerlerinin yüksek erişilebilirlik sağlayan move işlemi algoritmasıyla ağaç hiyerarşisindeki taşımayı uyguluyor
- Çocuk düğümler arasındaki taşıma ve sıralama, drifting-in-space içindeki
Fractional Index uygulaması entegre edilerek ele alınıyor
- Bu kombinasyon, çeşitli iş birliğine dayalı uygulama senaryolarının gereksinimlerini karşılayabiliyor
1 yorum
Hacker News yorumları
Görevler/notlar için yeni bir çok oyunculu düzenleyici [1] geliştiriyorum; hem metin hem de outliner işlemlerini destekliyor.
Dışarıdan düz bir metin belgesi gibi davranıyor, ancak outliner özellikleri nedeniyle içeride büyük bir ağaç yapısına dönüşüyor. Değişiklik eşitleme için yüksek erişilebilirlikli taşıma işlemlerine benzer bir yöntem kullanıyor. Ağacı değiştiren tek işlem
insmov; istemci çevrim içiyse değişiklik kümesi C’yi sunucuyla eşitliyor. Sunucuda uzak değişiklikler varsa, son eşitlemeden bu yana yapılan tüm değişiklikleri R olarak küresel doğrusal sırayla geri döndürüyor; ardından yerel değişiklik C’dekiinsmovişlemlerini geri alıp R’yi ve henüz eşitlenmemiş yeni değişiklikleri yeniden uyguluyor.Kesirli indeks kullanmıyor;
insmovdemetinde ebeveyn P’nin yanı sıra önceki kardeşguidA da yer alıyor. Tüm ağaç işlemleri sonunda sunucunun belirlediği küresel doğrusal sıraya göre uygulandığından, sıralamainsmovişleminin kendisiyle ele alınıyor. Çoğu zaman geri alma gerekmiyor; yalnızca sunucuda benim bilmediğim birinsmovdeğişikliği varken aynı anda ben yeni birinsmovgönderirsem doğru sırayla yeniden oynatma gerekiyor. Uzun bir uçuştan sonra Wi‑Fi’a yeniden bağlanırken bu olabilir; ancak çevrim içiyken WebSocket üzerinden gerçek zamanlı push alındığında daha az yaygın ve metin güncellemeleri gibiinsmovolmayan işlemler için gerekli değil.[1] https://thymer.com
Örneğin Lamport zaman damgası yerine sunucu sırasını kullanan bir biçim.
[1] https://inria.hal.science/inria-00555588/
HN’de Thymer’ı arayınca 2009’dan bir Show HN[1] çıktı; Thymer son 15 yıldır kapalı betadaymış gibi görünüyor.
0. https://news.ycombinator.com/item?id=40786425
Bu yazıyı mutlaka okumam gerekecek. Bir freelance müşteri işinde React Table Library’yi [0] açık kaynak olarak yayımladım ve ağaç işlemlerine odaklandım.
Onlar 100 bin düğüm ölçeğinde klasör/dosya ağaç yapılarıyla uğraşıyor; klasör ve dosya taşıma, kopyalama, en üst ve iç içe seviyelerde lazy loading gibi şeyleri aynı tablo yapısı içinde ele alıyorlar. Projeyi bitirince Google Drive’ın neden aynı hiyerarşi seviyesinde yalnızca görüntüleme ve düzenlemeye izin verdiğini anladığımı düşündüm. Çok sayıda düğümü olan iç içe bir görünümde bunu uygulamak için dikkate alınması gereken çok fazla kısıt var.
[0] https://react-table-library.com/
Tavsiye almak istiyorum. Çok oyunculu bir uygulama değil ama frontend’de kullanıcı profili olarak kullanılan büyük ve birbirine bağlı denormalize ağaçlar var.
Kullanıcının karo ekleyip/silip/boyutlandırdığı, her karo yuvasına birden çok bileşen eklediği ve bu bileşenlerin de kendi profillerine sahip olduğu karo tabanlı bir yerleşim düşünün. Farklı karo dizilimlerine sahip birden fazla yerleşim olabilir; tekil karoların global durumun başka parçalarına referans vermesi ya da bunları paylaşması gibi karmaşıklıklar da var.
Bunu sıradan REST ile güvenli biçimde güncellemek zor. Çünkü aynı kullanıcının iki sekme açıp sekme 1’de güncelleme yaptıktan sonra sekme 2’de tekrar güncelleme yaparak tüm profili geçersiz hâle getirmemesini garanti etmek gerekiyor. Genel olarak sıra da önemli. İstemcide düzgün uygulanmış güncellemeler sunucuda atlanırsa yapı bozulabilir.
Çok basit bir çözüm olarak, belirli bir durum parçasını tamamen üzerine yazabilecek minimum veriyi gönderip kuyruğun arkasına ekleme yöntemini kullandım. Genelde sorun olmuyor ama gerçek değişiklik yalnızca birkaç baytken 50 KB göndermek gibi israfın olduğu durumlar olabiliyor.
Genel olarak CRDT gerektiren nedenler bizde yok; ama tek kullanıcıda bile durum yönetimini çok daha kolaylaştıracak gibi görünüyor. Öncelikle kullanıcının tarayıcı sekmeleri arasında eşitleme olur; daha da önemlisi frontend durumunu basitçe değiştirdiğimde CRDT’nin sunucuyla uygun biçimde uzlaştıracağına güvenebilirim. Artık bunu kendim yönetmek zorunda kalmam. Bunun mantıklı olup olmadığını, yoksa çok oyunculu ve local-first gerekmeyen bir durumda Yjs gibi bir şeyi eklemenin getirdiği ek yükün buna değip değmediğini merak ediyorum.
Ancak profil düzenleme tek kullanıcıya özelse CRDT getirmek fazla gibi görünüyor. Görünüşe göre en büyük hata kaynağı iki sekmenin açık olduğu senaryo; bu nedenle
BroadcastChannelile güncelleme olaylarını diğer tüm sekmelere bildirme yöntemi kullanılabilir.Paylaşılan durumu, sunucu durumunun bir kısmının üzerine yazan REST çağrılarıyla korumak gerçekten kırılgan ve yalnızca düz veri kayıtlarındaki alanların üzerine yazma düzeyine uygun. Ayrıca sunucu-istemci durum uzlaştırmasını her zaman dikkatle düşünmek gerekiyor; olağan akış dışındaki yollarda eşitleme kolayca sapabiliyor.
Söylediğiniz gibi, güncellemelerin nasıl birleştirileceğini açıkça tanımlayan bir CRDT oluşturmak bilişsel yükü ciddi biçimde azaltacaktır.
Google Docs veya Zoho Writer gibi zengin metin içeriklerinde bir liste öğesini aşağı taşımak ya da yeni bir sütun eklemek gibi işlemler; tablo/liste işlemleri özünde ağaç manipülasyon işlemleridir
Bu tür durumlarda eşzamanlı çakışmaların, bağlama özel işlem yapılmadan yakınsatılmasının zor olduğu kötü bir şöhrete sahip [1]. Bu uygulamanın bu tür kullanım senaryoları için de genelleştirilmiş bir çözüm sunup sunmadığını merak ediyorum
Muhtemelen yaprak düğümlerde, yani metin bloklarında liste veya dize CRDT’si kullanıp; yapısal düğümler olan listeler ve tablolarda bu ağaç CRDT’sini birleştirmek mümkün olabilir. Ama o zaman tüm işlemlere 2 boyutlu bir adres
(parent-id, index_offset_into_that_parent)eklemek gerekir[1] https://github.com/inkandswitch/peritext/issues/27
Metin CRDT’si temelde karakter verisi tutan bir liste CRDT’sinden ibarettir. Bu yüzden gömülü öğeler, dizenin diğer öğeleri gibi boyutu 1 olan özel öğeler, yani gömülü alt düğümler olarak kolayca modellenebilir. Doğru yaklaşım kullanılırsa, ihtiyaca göre ağacın içinde farklı CRDT’ler karıştırılıp kullanılabilir. Örneğin rich text içinde bir tablo, o tablonun hücrelerinden birinde de bir görsel olması gibi
Her işleme bir
parent-crdt-idalanı eklemek üzücü ama kaçınılması zor görünüyor. Neyse ki gerçek kullanım senaryolarının çoğunda ardışık işlemlerin aynı ebeveyn CRDT’yi paylaşması çok yaygın olacak gibi; bu yüzden bu tür ID alanları run-length encoding ile iyi sıkıştırılabilirAncak Seph’in söylediği gibi, aynı ebeveyn altındaki ardışık işlemler etkili biçimde sıkıştırılabildiğinden, bu ebeveyn ID’sinin amortize ek yükü genellikle büyük olmuyor
Görsel pikselleri veya 3D modeller gibi veri yoğunluğu yüksek uygulamalar için pratik bir CRDT olup olmadığını merak ediyorum
Belgenin somut temsili veri yoğun olsa bile, kullanıcının tekil düzenlemelerini ve işlemlerini kodlama biçimi hâlâ küçük olabilir
Photoshop gibi bir görüntü düzenleyici yaptığınızı düşünelim: kanal başına 16 bit renk derinliğine sahip, sıkıştırılmamış 102 milyon piksellik bir görüntü; örneğin bir Fujifilm GFX100 fotoğrafı TIFF olarak yaklaşık 610 MB tutar. Her pikseli ayrı bir son-yazma-kazanır register’ı olarak ifade ederseniz ek yük büyük olur; ama böyle bir temsil, kullanıcının niyetini korumak için aslında uygun değildir. Kullanıcının yapacağı düzenlemeler “görüntü kontrastını %15 artır” veya “Q fırçası ve #000 rengiyle [(0,0), (1500, 1500)] spline’ını boya” gibi şeylerdir. Her pikseli Lamport zaman damgasıyla senkronize ederseniz, kullanıcı 1’in kontrast değişikliği kullanıcı 2’nin boyadığı pikseller dışındaki tüm piksellere uygulanır ve üstüne boyanmış pikseller garip görünebilir
Bunun yerine kullanıcı niyetini bir düzenleme işlemleri listesi olarak ifade etmek daha iyidir. Bu, 102 MB’lık piksel ızgarasının tamamından çok daha küçüktür. CRDT veri yapısı, bu tür kullanıcı niyetini senkronize etmek için olası teknik mekanizmalardan biridir; fakat yapı, çıktının somut veri düzenine değil kullanıcı niyetinin semantiğine göre seçilmelidir
Yine de
"add new layer namedbgbelow layerfgwith pixelsdata:(10mb of pixels)at (1500, 1500)"gibi büyük miktarda veri içeren düzenleme işlemleri ortaya çıkabilir. Ancak bu tür düzenleme komutlarının senkronizasyon ek yükü çok düşüktür; boyutu O(1)’dir, düzenleme komutunun içindeki piksel sayısıyla orantılı O(pixels) değildir3D modeller ayrı bir mesele; piyasada işbirlikli bir 3D modelleme aracı olup olmadığını görmedim. Aktif olarak araştırmış da değilim
Kendim yapmadım ve pratikte kullanışlı olup olmayacağından da emin değilim. Yine de en azından belgenin tüm geçmişini koruyabilir
Verileri Yjs ile temsil ediyor ama ham pikselleri saklamak yerine dönüşümlerin tüm geçmişini saklıyor
https://digest.browsertech.com/archive/browsertech-digest-ho...
Yazının GPT ile kontrol edilip edilmediğini merak ediyorum. İlk paragrafta güçlü bir ChatGPT üslubu hissediliyor
This article introduces the implementation difficulties and challenges of Movable Tree CRDTs when collaboration, and how Loro implements it and sorts child nodes.