Ortak Düzenleme Sistem Tasarımı: OT ve CRDT, Presence ve Senkronizasyon

İki kişi aynı anda aynı paragrafa yazıyor. Saniyenin küçük bir kesrinde iki ekran da aynı metni gösteriyor ve kimsenin yazdıkları kaybolmuyor. Bunu çalıştırmak, belirli bir sorunu, yani paylaşılan duruma yapılan eşzamanlı düzenlemeleri çözmek, artı bir dizi sıradan altyapı sorununu çözmek demektir: yönlendirme, kalıcılık, presence ve yeniden bağlanma.

Bu yazı gerçek zamanlı bir ortak editör tasarlıyor: örnek üzerinden eşzamanlılık sorunu, operasyonel dönüşüm (OT) ile çakışmasız çoğaltılmış veri tiplerinin (CRDT) karşılaştırması, Figma'nın kullandığı sunucu otoriteli yaklaşım ve bunların etrafındaki mimari, bir diyagramla.

Beş karakterde temel sorun

ABC dokümanıyla başlayın. Konumlar sıfırdan sayılır.

• Alice 1. konuma X ekler ve ekranında AXBC olur.
• Aynı anda Bob 2. konumu, yani C karakterini siler ve ekranında AB olur.

Her istemci şimdi diğerinin işlemini alır ve olduğu gibi uygular:

• Bob, “1. konuma X ekle” işlemini AB üzerine uygular ve AXB elde eder.
• Alice, “2. konumu sil” işlemini AXBC üzerine uygular, böylece B karakterini siler ve AXC elde eder.

Dokümanlar ayrışmıştır ve Alice'in kopyası kimsenin silmediği bir karakteri kaybetmiştir. Her ortak editör bunu önlemek için vardır. İki çözüm ailesi vardır.

Operasyonel dönüşüm

OT işlemleri konum olarak tutar ve gelen her işlemi, henüz görmediği eşzamanlı işlemlere karşı dönüştürür. Bob'un “2. konumu sil” işlemi, Alice'in 1. konuma eklemesinden önce yapılmıştı; bu ekleme kendisinden sonraki her şeyi bir konum sağa kaydırır. Eklemeye karşı dönüştürüldüğünde işlem “3. konumu sil” olur ve Alice'in AXBC metni AXB olur; Bob'unkiyle eşleşir.

Üretimdeki OT sistemleri işlemleri sıralamak için merkezi bir sunucu kullanır; bu yaklaşım 1995'teki Jupiter sistemine dayanır ve 2010'da editörünü yeniden yazarken Google Docs'un da anlattığı yöntemdir:

1. Her istemci işlemlerini, temel aldıkları sunucu revizyonuyla etiketleyerek gönderir.
2. Sunucu her işlemi o revizyondan bu yana kabul ettiği her şeye karşı dönüştürür, bir sonraki revizyon numarasını atar ve sonucu yayınlar.
3. Her istemci gelen işlemleri, kendi henüz onaylanmamış işlemlerine karşı dönüştürür.

OT'nin güçlü yanları kompakt işlemler ve metin konusunda uzun bir geçmiştir. Zayıf yanı ise dönüşüm fonksiyonlarının kendisidir: Zengin metin, tablolar ve iç içe yapılar için her işlem tipi çiftini doğru yapmak bilinen bir şekilde zordur ve tasarım, sırayı belirlemek için bir sunucuya bağımlıdır.

CRDT'ler

CRDT, eşzamanlı güncellemelerin herhangi bir sırayla uygulanabildiği ve her replikanın yine de aynı duruma vardığı şekilde tasarlanmış bir veri tipidir; 2011'de Shapiro ve meslektaşları tarafından formel hâle getirilmiştir. Metin için eklenen her karakter, istemci kimliği ve bir sayaç gibi benzersiz ve sıralı bir tanımlayıcı alır; bir ekleme işlemi “1. konuma” yerine “şu kimlikli karakterden sonra” der. Silmeler karakterleri silinmiş olarak işaretler ve geride tombstone'lar bırakır. İşlemler kayan konumlar yerine kararlı kimliklere atıfta bulunduğu için dönüştürülecek bir şey yoktur.

Örnekte Alice'in eklemesi “X, A'dan sonra gelir”, Bob'un silmesi “C'yi kaldır” der. Hangi sırayla uygulanırsa uygulansın iki replika da AXB ile sonuçlanır.

Yjs ve Automerge gibi CRDT kütüphaneleri bunu pratik hâle getirir. Güçlü yanları: Merkezi bir sıralama gerekmez, bu yüzden çevrimdışı düzenleme ve eşler arası senkronizasyon doğal olarak çalışır ve birleştirme her an mümkündür. Bedelleri: karakter başına ek meta veri, sıkıştırılması gereken tombstone'lar ve birleştirilmiş sonucun tutarlı olduğu ama iki kullanıcının da kastetmediği uç durumlar. Bir sunucu erişim kontrolü, kalıcılık ve dağıtım (fan-out) için yine de faydalıdır; yalnızca sırayı belirlemek zorunda değildir.

Sunucu otoriteli orta yol

Her editör uzun metin düzenlemez. Figma ne klasik OT'yi ne de gerçek CRDT'leri seçti: Sunucusu olayların sırasını belirler, dokümanlar özellikleri olan nesnelerden oluşan ağaçlardır ve iki kişi aynı nesnenin aynı özelliğini değiştirdiğinde sunucunun aldığı son değer kazanır. Sunucuları her çok oyunculu doküman için ayrı bir süreç çalıştırır ve o dokümanı düzenleyen herkes o sürece bağlanır. Çakışmaların özellik bazında olduğu tasarım araçları, hesap tabloları ve panolar için bu, iki alternatiften de daha basittir.

Mimari

Hangi algoritmayı seçerseniz seçin, çevredeki sistem benzer görünür:

1. İstemciler WebSocket üzerinden bir işbirliği servisine bağlanır ve doküman açık olduğu sürece bağlantıyı açık tutar.
2. Her dokümanın sahibi tek bir oturum sunucusudur. doc-123 dokümanının tüm istemcileri aynı sunucuya ulaşmalıdır ki sunucu düzenlemeleri bellekte sıralayabilsin ya da birleştirebilsin. Örneğin Redis'teki bir dizin, dokümanları bir kira (lease) ile sunuculara eşler ve yük dengeleyici ya da bir yönlendirme katmanı bağlantıları oraya gönderir. Doküman kimliği üzerinde tutarlı hashleme de işe yarar; yeter ki iki sunucu aynı anda bir dokümanın sahibi olduğuna asla inanmasın.
3. Oturum sunucusu canlı dokümanı bellekte tutar, gelen her düzenlemeyi uygular ve diğer istemcilere yayınlar.
4. Her düzenleme, sunucu onu onaylamadan önce kalıcı bir op log'a eklenir. Tüm dokümanın periyodik bir snapshot'ı nesne depolamaya gider; böylece bir dokümanı yüklemek, en son snapshot'ı ve ondan sonraki işlemleri okumak demektir.
5. İzinler bağlanırken ve her işlemde kontrol edilir; bir görüntüleyicinin düzenlemesi yalnızca gizlenmez, reddedilir.

Yorumlar, sürüm geçmişi, arama ve dışa aktarma, op log'u tüketen ayrı servislerdir; gerçek zamanlı yola ait değildir.

Presence farklı bir veridir

İmleçler, seçimler ve “kim burada” bilgisi sürekli değişir, yalnızca o an önemlidir ve bir dakika sonra değersizdir. Presence'ı geçici olarak ele alın: Aynı oturum sunucusu üzerinden yayınlayın, kullanıcı başına saniyede birkaç güncellemeyle sınırlayın, istemci bağlantıyı kestiğinde atın ve asla op log'a yazmayın. Örneğin Yjs, presence'ı doküman durumunun yanında ayrı bir awareness kanalında tutar.

Çevrimdışı düzenlemeler ve yeniden bağlanma

Bağlantılar sürekli kopar; trenlerde, asansörlerde. İstemci onaylanmamış işlemleri yerelde tutar ve yeniden bağlandığında tekrar gönderir:

• OT ile istemci bekleyen işlemlerini gördüğü son revizyonla birlikte gönderir; sunucu onları o zamandan bu yana olan her şeye karşı dönüştürür.
• CRDT'lerle istemci ve sunucu, her birinin ne gördüğünün kompakt özetlerini, çoğunlukla durum vektörleri (state vector) denen yapıları, değiş tokuş eder ve birbirine yalnızca eksik güncellemeleri gönderir.

Uzun çevrimdışı dönemler CRDT'lerin parladığı yerdir. OT ile bir gün çevrimdışı kalmış bir istemci yine de yeniden bağlanabilir, ama sunucunun onun işlemlerini bir günlük işleme karşı dönüştürmesi gerekir.

Ölçekleme ve arızalar

• Sıcak dokümanlar. Binlerce görüntüleyicisi ve birkaç editörü olan bir doküman, oturum sunucusunun her tuş vuruşunu binlerce sokete kendisinin itmesine yol açmamalıdır; görüntüleyicilere bir pub/sub katmanı üzerinden dağıtın ve güncellemeleri toplu gönderin.
• Oturum sunucusu çökmesi. İstemciler yeniden bağlanır, dizindeki kira süresi dolar, yeni bir sunucu snapshot'ı ve op log'u yükler ve istemciler bekleyen işlemlerini yeniden gönderir. Bunu kayıpsız yapan şey, yalnızca kalıcı olarak loglanmış düzenlemeleri onaylamaktır.
• Split brain. Aynı dokümanın sahibi olan iki sunucu çakışan sıralamaları kabul eder. Sahipliği kirayla çitleyin (fencing) ve kirası dolmuş bir sunucudan gelen yazmaları reddedin.
• Geri alma, ortak çalıştığınız kişinin değil kendi son değişikliğinizi geri almalıdır; bu yüzden diğer her işlem gibi dönüştürülen ya da birleştirilen yeni bir ters işlem hâline gelir.

İşbirliği diyagramı

Nasıl okunur:

• İki istemci yük dengeleyici üzerinden WebSocket ile bağlanır.
• Redis dizini doc-123 dokümanının hangi oturum sunucusuna ait olduğunu söyler; iki bağlantı da A sunucusuna düşer.
• A sunucusu düzenlemeleri bellekte sıralar ya da birleştirir; düzenlemeleri ve presence'ı iki istemciye geri yayınlar.
• Kalıcılık: Her düzenleme onaylanmadan önce Postgres'teki op log'a gider; snapshot'lar nesne depolamaya gider.
• Kimlik sağlayıcı istemciler bağlanırken erişimi kontrol eder; B sunucusu diğer dokümanların sahibidir ve servisin nasıl yatay ölçeklendiğini gösterir.
• Markdown bloğu OT ile CRDT'yi üç satırda karşılaştırır.

Gerçek zamanlı sistemleri net çizmek

• Sahipliği gösterin. Buradaki en önemli tek gerçek, bir dokümanın sahibinin tek bir sunucu olmasıdır; dizini ve yönlendirmeyi çizin.
• Kalıcı ve geçici veriyi ayırın. Op log'u ve snapshot'ları çizin; presence'ı kalıcı olmadığı belirtilerek etiketleyin.
• En az iki istemci çizin. Sorunun tamamı eşzamanlılıktır; tek istemci bunu gizler.
• Onay noktasını işaretleyin: Bir düzenleme op log'a girdiğinde güvendedir.

Uzun ömürlü bağlantılar ve dağıtım için sohbet uygulaması mimari diyagramı benzer konuları ele alıyor. Dokümanları sunuculara yönlendirmek, yük dengeleyici diyagramındaki fikirlerin bir uygulamasıdır; genel yöntem ise sistem tasarımı diyagramı örneğinde.

Archboard'da oluşturun

1. Google ya da GitHub ile giriş yapın ve bir diyagram oluşturun.
2. İstemciler için Ağ paketinden iki Cihaz düğümü, WebSocket girişi için de Bulut paketinden bir Bulut yük dengeleyici ekleyin.
3. İşbirliği servisi için bir Temel Çerçeve ekleyin ve içine iki Hesaplama düğümü koyun: doc-123 dokümanının sahibi olan oturum sunucusu A ve oturum sunucusu B.
4. Doküman dizini için Veri paketinden bir Redis düğümü, op log için bir Postgres düğümü ve snapshot'lar için Bulut paketinden bir Nesne depolama düğümü ekleyin.
5. Güvenlik paketinden bir Kimlik sağlayıcı ekleyin ve her şeyi etiketli kenarlarla bağlayın: WebSocket, düzenlemeler ve presence, ekleme, snapshot, kira.
6. Temel paketinden OT ve CRDT özetini içeren bir Markdown bloğu ekleyin.

Örnek 11 diyagram düğümü kullanıyor ve Free planın sınırları içinde kalıyor.

SSS

OT ile CRDT arasındaki fark nedir? OT eşzamanlı işlemleri birbirine karşı dönüştürür; sırayı genellikle bir sunucu belirler. CRDT'ler her öğeye kararlı bir kimlik verir; böylece işlemler sıradan bağımsız hâle gelir ve replikalar, merkezi sıralama olmadan, hangi sırayla olursa olsun aynı duruma varır.

Google Docs OT mi yoksa CRDT mi kullanır? Google, 2010'daki editör yeniden yazımını, değişiklikleri bir sunucunun sıraladığı operasyonel dönüşümle anlattı. Daha yeni birçok editör Yjs ya da Automerge gibi CRDT kütüphanelerini kullanıyor.

Bir dokümanın tüm editörleri neden aynı sunucuya bağlanmalı? Canlı dokümanı o sunucu tutar ve düzenlemelerin sırasına o karar verir. İki sunucu bir doküman için düzenlemeleri bağımsız olarak kabul etseydi, her tuş vuruşunda koordinasyon kurmaları gerekirdi.

Presence nasıl saklanır? Çoğunlukla saklanmaz. İmleçler ve seçimler gerçek zamanlı yayınlanır, sınırlandırılır ve istemci bağlantıyı kestiğinde atılır. Onları kalıcı hâle getirmek yük ekler, değer katmaz.

Bir ortak editör çevrimdışı çalışabilir mi? Evet. İstemciler işlemleri yerelde kuyruğa alır ve yeniden bağlanınca senkronize eder. Uzun çevrimdışı dönemleri en doğal şekilde CRDT'ler ele alır; OT de çalışır, ama dönüşte daha fazla işlemi dönüştürür.

Ücretsiz başlayın — tek kullanıcı, kredi kartı gerekmez.