Alan düzeyinde son yazan kazanır: çevrimdışı çalışan en basit birleştirme kuralı

Cihazlar aynı veriyi internet yokken değiştirdiğinde, hâlâ işe yarayan en basit birleştirme kuralı "alan düzeyinde son yazan kazanır" kuralıdır: her alan en son zaman damgasına sahip değeri tutar, eşitlik sabit bir sırayla bozulur ve böylece her cihaz aynı sonuca varır. Bilerek sıkıcı bir kuraldır. Sınırları da o kadar açıktır: sayaçlar ve listeler daha akıllı bir saate değil, farklı bir veri biçimine ihtiyaç duyar.

Bu yazı sorunu, klasik çözüm ailelerini (işlem dönüştürme ve CRDT), Havenfold'un seçtiği kuralı ve bu kuralın nerede yetmediğini anlatıyor. Havenfold pre-alpha aşamasında: gerçek verinizle kullanmayın.

Sorun: telefonlar, ortak bir kayıt, internet yok

Aile defterinde "Kombi" adlı bir kayıt düşünün; alanlarında bakım tarihi ve servisin telefon numarası var. Havenfold'un tanıtımındaki örnek adlarla anlatalım: Alex'in telefonu çevrimdışıyken Alex bakım tarihini değiştiriyor. Maya'nın telefonu da çevrimdışıyken Maya servis numarasını değiştiriyor. Sonra telefonlar yeniden bağlanıyor.

Kayıt nasıl görünmeli? Çoğu kişi şöyle der: Alex'in yeni tarihi, Maya'nın yeni numarası. Şimdi işi zorlaştıralım: Alex de Maya da bakım tarihini farklı değerlere değiştirsin. Birinin değişikliği kazanmalı ve her cihaz, bir sunucuya sormadan ve değişiklikler hangi sırayla gelirse gelsin, kimin kazandığında anlaşmalı.

Klasik aileler: işlem dönüştürme ve CRDT

Birlikte çalışılan yazılımlarda bu soruna bilinen yaklaşımlar var.

• İşlem dönüştürme (operational transformation, OT): Gelen her değişikliği, henüz görmediği değişikliklere göre dönüştürür; böylece farklı sıralarla uygulansa da aynı sonuç çıkar. Gerçek zamanlı metin düzenlemede klasik yöntemdir ve çoğu zaman işlemleri sıraya koyan merkezi bir sunucuyla uygulanır.
• Çakışmasız çoğaltılmış veri türleri (CRDT): Kopyaların koordinasyon olmadan aynı sonuca varması için tasarlanmış veri yapılarıdır. Shapiro, Preguiça, Baquero ve Zawirski'nin 2011 tarihli makalesi CRDT'yi, güçlü nihai tutarlılık altında yakınsama için yeterli koşulları sağlayan veri türü olarak tanımlar. Bazı CRDT'ler, örneğin birlikte metin düzenleme için, çok zengindir.

Paylaşılan metin belgeleri yerine bir ailenin yapılı kayıtları için, alan başına basit bir kayıt hücresi çoğu zaman yeter. "Son yazan kazanır" hücresi, CRDT ailesinin en basit üyelerinden biridir.

Havenfold'un kuralı

Havenfold'un kayıt katmanı RFC-0001'de tanımlı. Özeti tek satır: birleştirmede alan düzeyinde son yazan kazanır, sıra karma mantıksal saatle (HLC) belirlenir. Ayrıntıda:

• Alan başına: Her alan için büyük olan kazanır; önce saat damgasına, sonra yazarın kimliğine, sonra işlemin kimliğine bakılır. Aynı yazarın aynı damgalı işlemleri bile belirlenimci biçimde çözülür.
• Silme: Silme, kaydın silinme işaretine aynı kuralla yazılır. Silmeden eski alanlar okumada yok sayılır. Daha sonra gelen bir yazma silinmiş kaydı geri getirebilir.
• Sıradan bağımsızlık: İşlemlerin uygulanma sırası sonucu değiştirmez. Geçerli işlemler kümesi değişince durum yeniden hesaplanır.
• Kural yetmediğinde: Sayaç ya da liste birleştirme gibi bu kuralın yetmediği yerlerde ürün her öğeyi ayrı bir kayıt yapar.

Kombi örneğinde Alex'in tarihi de Maya'nın numarası da kalır, çünkü farklı alanlardır. İkisi de tarihi değiştirdiyse, her cihazda daha sonraki damga kazanır.

Neden karma mantıksal saat?

"En son" demek için bir saat gerekir ve cihaz saatleri kayabilir ya da yanlış ayarlanmış olabilir. Kulkarni, Demirbaş ve arkadaşlarının 2014'te tanımladığı karma mantıksal saat (HLC), fiziksel zamanı mantıksal bir sayaçla birleştirir: duvar saatine yakın kalır ama cihazın gördüğü olayların sırasına da uyar.

RFC-0001 bunu şöyle kullanıyor:

• Her cihaz bir "son damga" tutar ve bir işlemi göndermeden önce bunu kalıcı olarak kaydeder.
• Yazarken yeni damga, "şimdi" ile son damgadan sonraki değerin büyüğüdür.
• Alırken cihaz son damgasını en az gelen damgaya kadar ilerletir.
• Gelen bir işlem çok ileri bir zaman iddia ediyorsa, yerel saat yetişene kadar bekletilir. Bu, işlemin ne zaman görüneceğini değiştirir, sonucunu değiştirmez.
• Damga yalnız birleştirme sırası içindir; yetki kararında hiç kullanılmaz. Kimin yazabileceği ailenin imzalı üyelik kaydına göre denetlenir.

Son yazan kazanır nerede bozulur?

Kural, bazı şeylerden vazgeçtiği için basit. Hangilerinden vazgeçtiğini dürüstçe söylemek gerekir:

• Sayaçlar: Telefonlar çevrimdışıyken "kedi bugün kaç kez beslendi" alanına ayrı ayrı ekleme yaparsa, kural yalnız birini tutar, ötekileri kaybeder. Havenfold'daki çözüm: her besleme ayrı bir kayıt olur ve kayıtlar sayılır.
• Listeler: Birden çok kişi aynı alışveriş listesi alanına aynı anda öğe eklerse, bir liste ötekilerin üstüne yazar. Yine çözüm: her öğe ayrı bir kayıt.
• Metin: Birden çok kişinin aynı paragrafı birlikte düzenlemesi için metin CRDT'si ya da işlem dönüştürme gerekir. Alan düzeyindeki kural yalnız bir sürümü tutar.
• Sessiz kayıp: Aynı alan gerçekten birden çok cihazda değiştirildiğinde, önceki değişiklik bir çakışma uyarısı olmadan kaybolur. Bir aile defteri için bu çoğu zaman kabul edilebilir; bazı veriler için değildir ve ürünün onları farklı modellemesi gerekir.

Özet

• Cihazlar veriyi çevrimdışı değiştirdiğinde, her cihazda ve her sırada aynı sonucu veren bir birleştirme kuralı gerekir.
• İşlem dönüştürme ve CRDT klasik ailelerdir; "son yazan kazanır" hücresi en basit CRDT'lerden biridir.
• Havenfold'un kayıt katmanı alan düzeyinde son yazan kazanır kuralını kullanır; sıra karma mantıksal saatle, sonra yazar ve işlem kimliğiyle belirlenir.
• Sayaçlar, listeler ve ortak metin bu kurala uymaz; Havenfold bu öğeleri ayrı kayıtlar olarak tutar.
• Havenfold pre-alpha aşamasında; RFC'leri yalnız proje lideri onaylıyor ve gerçek veri için henüz uygun değil.