İşbirlikçi metin düzenleme: CRDT veya OT olmadan uygulamak

 (mattweidner.com)
4 puan yazan GN⁺ 2025-05-23 | 1 yorum | WhatsApp'ta paylaş
  • İşbirlikçi metin düzenleme sorununu çözmeye yönelik yeni bir yaklaşım tanıtılıyor; karmaşık algoritmalar olmadan da uygulanabiliyor
  • Mevcut CRDT ve OT yaklaşımlarının karmaşıklığı ve kısıtlarından kaçınıp, basit bir ID tabanlı ekleme yöntemi kullanıyor
  • Bu yöntemde sunucuya 'neyin nereye ekleneceği' doğrudan belirtilerek işlem yaptırıldığı için esneklik yüksek
  • İyimser yerel güncellemeler için sunucu reconciliation stratejisi kullanılarak durum senkronizasyonu sorunları çözülüyor
  • Ölçeklenebilir ve anlaşılması kolay bu yaklaşım, mevcut işbirlikçi uygulama geliştirmede doğrudan uygulanabilir bir alternatif sunuyor

Collaborative Text Editing without CRDTs or OT

Sorunun ortaya konması

  • İşbirlikçi metin düzenleme çok zor bir özellik; özellikle eşzamanlı düzenlemede metin indekslerinin kayması sorunu (index rebasing) ortaya çıkıyor
  • Mevcut yaklaşımlar olan CRDT (çatışmasız çoğaltılmış veri tipi) ve OT (operational transformation) sırasıyla karmaşık matematiksel modellere dayanıyor
    • CRDT: her karakteri bir ID ile izleyip ağaç tabanlı sıralama kullanır
    • OT: diğer kullanıcı girdilerini yansıtmak için indeksleri dinamik olarak yeniden ayarlar
  • Her iki yaklaşım da büyük ölçüde kütüphanelere bağımlı ve geliştiriciye özel özelleştirme yapmak zor

Yeni yaklaşım

Temel fikir

  • Her karakter benzersiz bir ID (UUID) ile işaretlenir ve istemci sunucuya “hangi karakterin hangi ID'den sonra ekleneceği” komutunu gönderir
  • Örnek: "insert ' the' after f1bdb70a" → f1bdb70a, ekleme hedefinin karakter ID'sidir
  • Sunucu bunu aynen yorumlayıp ekleme yaparak çatışmaları önler

Silme işlemi

  • Karakter silindiğinde de ilgili ID dahili listede tutulur ve isDeleted bayrağıyla işlenir
  • Gerçek kullanıcı metninde görünmez, ancak referans korunur ve daha sonra işlem yapılabilir

İstemci işlemleri ve iyimser güncellemeler

  • Kullanıcının sonucu girişten hemen sonra görmesi gerektiği için, değişiklik sunucu yanıtı gelmeden önce yerelde uygulanır (iyimser güncelleme)
  • Sunucu reconciliation stratejisiyle:
    1. Yerelde kesinleşmemiş tüm işlemler geri alınır
    2. Sunucu işlemleri uygulanır
    3. Ardından yerel işlemler yeniden uygulanarak nihai senkronize durum elde edilir

Mevcut yaklaşımlardan farkı

  • CRDT'ler otomatik ID sıralama algoritması içerir; bu yaklaşımda ise sunucuya yalnızca açık ekleme konumu iletilir
  • Sonuç olarak daha basit ve daha net bir çalışma modeli elde edilir

Eşzamanlı eklemelerin işlenmesi

  • Örnek: “My name is” ifadesinde iki kullanıcı aynı anda aynı konuma “ Charlie” ve “ Dave” eklerse
    • Sunucunun alma sırasına göre sonuç “My name is Dave Charlie” olur
  • Bu doğal bir davranış olarak görülür ve bazı CRDT yaklaşımlarındaki gibi karakter düzeyinde iç içe geçme (interleaving) yaşanmaz

Esnek işlem desteği

  • Temel insert/delete dışında çeşitli işlemler de desteklenebilir:
    • insert-before
    • koşullu ekleme (ör. yalnızca “color” varsa “u” ekleme)
    • drag & drop sırasında konum yeniden ayarlama vb.
  • Bu esneklik, önceden tanımlı matematiksel özelliklere bağlı olmamasından gelir

Zengin metin desteği

  • Aralıklar ID tabanlı tanımlanarak biçimlendirme uygulanabilir (ör. “ID X'ten ID Y'ye kadar kalın”)
  • ProseMirror gibi editörlerle entegre edildiğinde çatışma çözümü basit bir şekilde yapılabilir
  • Temel yapı korunurken zengin metin özellikleri eklenebilir

Dağıtık sürüm (Decentralized)

  • Merkezi bir sunucu olmadan da, işlem sırası Lamport zaman damgalarına göre belirlenirse aynı yaklaşım çalışabilir
  • Bu durumda RGA, Peritext, Fugue gibi CRDT'lere benzer sonuçlar verir
  • Ağaçlar veya matematiksel ispatlar olmadan da CRDT düzeyinde tutarlılık sağlanabilir

Yardımcı kütüphane: Articulated

  • Array<{ id, isDeleted }> yapısını verimli şekilde ele almak için tasarlanmış bir kütüphane
  • UUID yerine bellek optimizasyonu için { bunchId, counter } yapısı kullanır
  • B+Tree tabanlı yapısıyla hızlı ID arama ve ekleme desteği sunar
  • Kalıcı (persistent) veri yapısı sayesinde sunucu reconciliation ile iyi uyum sağlar

Sonuç

  • Bu yaklaşım, CRDT/OT'ye kıyasla anlaması daha kolay ve doğrudan uygulanabilir
  • Çeşitli düzenleme özellikleri, yetkiler, kısıtlar ve biçimlendirmeler serbestçe uygulanabildiği için gerçekçi işbirlikçi editörler geliştirmede avantaj sağlar
  • Articulated kütüphanesi, bu yaklaşımı pratik hale getirmeye yardımcı olan bir araç olarak sunuluyor

İlgili okumalar

1 yorum

 
GN⁺ 2025-05-23
Hacker News görüşleri

  • Bu algoritma oldukça havalı görünüyor. Her karaktere küresel olarak benzersiz bir kimlik (ör. UUID) verip ona her zaman tutarlı biçimde referans verilebilmesini sağlama yaklaşımı anlatılıyor; istemci sunucuya belirli bir kimlikten sonra karakter ekleneceğini bildiriyor, sunucu da eklemeyi o konuma işliyor; silmeler ekranda gizleniyor ama iç yapıda konum referansı için korunmaya devam ediyor. Bu yaklaşımın yalnızca metin düzenleme için değil, oyun dünyası senkronizasyonu gibi başka alanlarda da kullanılabileceğini hayal edenler var

    • Bu, özünde basitleştirilmiş bir CRDT gibi görünüyor; tie-break ve merkezi sunucu kullanımı açısından Google Wave dönemindeki yapıya benziyor
    • Anlatılan şeyin zaten CRDT olup olmadığı soruluyor
    • Aslında o kadar da yeni bir şey olmadığı yönünde bir tepki var; dağıtık sistemleri serileştirirken merkezi bir süreç kullanmak geleneksel bir yöntem ve ağ bölünmesi (CAP vb.) ya da tek hata noktası gibi sorunlar hâlâ mevcut. Ayrıca yazıda performans tartışması olup olmadığı merak ediliyor
    • ctrl+a, ctrl+x, ctrl+v gibi toplu seçme/kopyalama/yapıştırma işlemlerinde bol şans diye şaka yapılıyor

  • CRDT’den farkının, merkezi sunucunun sıralama gibi senkronizasyon görevini üstlenmesi ve gerçek veri yapısına önceden tanımlı bir sıra vermek zorunda olunmaması olduğu görüşü paylaşılıyor. Yalnızca istemci-sunucu iletişimi olduğundan, sunucu istemcinin tüm yerel işlemlerini işledikten sonra uzak güncellemeleri gönderebilir

  • dict/map gibi başka veri yapıları ya da rastgele türlerden diziler hakkında hiç konuşulmamasına şaşıranlar var. Gerçek uygulamalarda, saf ortak metin düzenlemeden çok çeşitli işbirlikçi veri yapıları daha fazla gerekiyor. Veri doğrulama, kısmi yükleme, üst seviye işlemler gibi ilginç örnekler var; ancak bunların Yjs gibi araçlarda bulunmama nedeninin CRDT’nin kendisinden çok, bu tür özelliklerin başlı başına zor uygulanması olduğu düşünülüyor

    • Birden çok veri yapısı ihtiyacına güçlü biçimde katılım var. “Atomik” nesne dizileri oluştururken nesne özelliklerini değiştirmek mümkün değilse, dizgede olduğu gibi yalnızca tür değiştirilir; nesne içindeki değişiklikler ise ağaç gezinme/depolama sorunu olduğu için biraz daha karmaşıktır deniyor. Ayrıca yardımcı kütüphane kullanan tarafın, hatalı durumları önlemek için (ör. bir todo öğesinin hem isDone: true hem state: inProgress olması) kendi “anlamsal model” mantığını hook gibi bağlayabilmesi umuluyor; bu da bağlantı verilen yazıdaki zengin metin biçimlendirmesiyle benzer bağlamda

    • CRDT, çakışma olduğunda bir tarafı tutarlı bir yöntemle seçip birleştirir; sorun ise bunun veri kaybına ya da geçersiz veriye yol açabilmesidir. Bunu, git merge çakışmalarını her durumda taraflardan birini seçerek çözmek gibi düşünün; çoğu zaman yanlış sonuç ya da derleme hatası çıkar. Yalnızca otomatik çözümlemenin, verinin asıllığını ve anlamını yeterince koruyamayabileceği belirtiliyor. Bunun da CRDT’nin hâlâ neden yaygınlaşmadığının sebeplerinden biri olduğu düşünülüyor

  • Bu yaklaşımı anlatan yazının ilginç bulunduğu, kendisinin de uzun zamandır benzer bir yöntem kullandığı ve akademide neredeyse hiç anılmamasının şaşırtıcı olduğu söyleniyor. Bunu merkezsiz bir ortamda CRDT olarak uygulayarak birleşebilirlik, değişmezlik ve yer değiştirilebilirlik gibi özellikleri koruyabildiğini belirtiyor

    • Bunu CRDT’ye alternatif olarak geliştirdiyse, pratikte ne kazandığı soruluyor

  • Metnin ana mesajı, gerçekten karmaşık CRDT/OT’nin yalnızca merkezi sunucu olmadığında mı gerekli olduğu şeklinde özetlenmeye çalışılıyor

    • Merkezi sunucu olmasa bile, dağıtık bir yapıda işlemlerin küresel sırasını uzlaşıp uygulamanın bir yolu varsa CRDT/OT karmaşıklığından kaçınılabileceği söyleniyor. İlgili yazı bağlantısı paylaşılıyor. Elbette bu da bir tür CRDT sayılabilir (daha genelleştirilmiş biçimde), ancak undo/replay uygulaması kolay değil; buna rağmen geleneksel CRDT/OT yapıları fazla karmaşık geliyorsa değerlendirmeye değer bir alternatif olduğu vurgulanıyor

    • OT’nin (Operational Transformation) merkezi bir sunucu gerektirdiği belirtiliyor

  • Bunun özünde yine bir CRDT olduğu, ancak belgeye uygulanacak işlem sırasını merkezi sunucunun belirlediği söyleniyor. Google Docs ve Zoho Writer da OT + merkezi sunucu yaklaşımı kullanıyor. Sunulan yaklaşımın CRDT tarzında olduğu ama fiilen merkezi sunuculu hizmetlerde daha pratik olduğu kabul ediliyor

  • Automerge gibi CRDT’lerden ana farkın sunucu koordinasyonu olduğu düşünülüyor. Automerge eşzamanlı eklemeleri sıra numarası ve ajan kimliğinin tanımlı sırasına göre düzenlerken, bu yaklaşım sunucuya geliş sırasına göre işliyor. Bağlantı verilen yazıdan şu ifade alıntılanıyor: “Bir sürü fancy algoritmaya gerek yok, dolayısıyla daha basit.” Zaten birçok hizmet merkezi sunucu kullanacağından bu pratik görünüyor; ancak sunucu koordinasyonunda yerel düzenlemeleri geri alıp yeniden oynatmak gerektiğinden, gerçekte ne kadar daha basit olduğundan emin olunmadığı belirtiliyor

    • “rewind/replay” yaklaşımının da oldukça fancy geldiği ve Persistent B+Tree’nin de pek basit olmadığı yorumu yapılıyor

    • Automerge’in de sonuçta içerde küresel bir sıra oluşturabildiği, ama pratikte metin işlemlerini geleneksel CRDT (RGA vb.) tarzında ele aldığı; çünkü undo/replay’in kolay olmadığı açıklanıyor

  • Optimize edilmemiş bir CRDT hissi verdiği, sanki max set size=1 ayarlanmış bir set’i gelişi güzel kullanmak gibi olduğu yönünde bir şaka var

    • Buna karşılık, bu şekilde karmaşıklığı azaltmanın gerçek hayatta olan bitene daha yakın olduğu için çekici ve basit bulunduğu söyleniyor; optimize edilmemiş olsa da cazibesi var

  • Sunucu reconciliation kullanılırsa istemci tarafında birleştirme problemlerinin zorlaşabileceği riski dile getiriliyor. Sunucu güncellemeleri sırayla gelirken editör UX’inin nasıl akıcı tutulacağı soruluyor; örneğin ekleme isteği başarısız olursa yeniden mi denenecek, bu sırada başka güncellemeler geldiyse ne yapılacak? Önerilen çözümler olarak düzenleme geçmişini geri sarıp yeniden uygulama ya da bekleyip kuyruğu boşaltma anılıyor. Frontend açısından, açıkça belirtilmemiş çok sayıda UI/UX edge case olduğu ve bu yüzden CRDT’nin aslında daha basit olabileceği söyleniyor. Özellikle ağ bağlantısının dengesiz olduğu ortamlarda (ör. metroda) kullanıcı deneyiminin nasıl olacağı merak ediliyor

    • ProseMirror ve modern CodeMirror’ın belge değişikliklerini step düzeyinde yönettiği ve her adım için konum bilgisini (position map) güncelleyerek arabellek adımlarının belgeye uygulanmasını sağlayacak şekilde veri yapıları kurduğu açıklanıyor. Bunun gerçek ortak düzenleme senaryolarında pratikte iyi çalıştığı vurgulanıyor ve ilgili kaynak bağlantısı paylaşılıyor

  • Birisi, LLM’ler (ör. 4b model vb.) kullanılarak özellikle karmaşık CRDT ya da OT olmadan, basit vakaların ötesindeki birleştirme çakışmalarının çözülemeyeceğini soruyor. Enerji verimliliği düşük olabilir ama şaşırtıcı derecede iyi çalışabileceği öne sürülüyor

    • Örnekteki gibi My name is ifadesinde is sonrasına ayrı ayrı Charlie ve Dave eklenmesi çakışmasında, LLM’in bunu nasıl birleştireceği sorgulanıyor