Dağıtılmış kimlik üretiminin evrimi, merkezi veritabanı dizilerinden, mikro hizmet mimarilerindeki darboğaz haline gelen merkezi dizilerden, Twitter'ın Snowflake ve UUID varyantlarına kadar uzanır. Başlangıçta, NTP-senkronize saatlere büyük ölçüde güvenilmiştir; bu, sıçrama saniyeleri, saat kayması ve ağ bölünmeleri sırasında kırılganlık göstermiştir. Olay kaynakları ve küresel tutarlı kayıt gereksinimleri, koordinasyon yükü olmadan nedenselliği dikkate alan kesin monoton sıraları talep etmektedir.
Geleneksel yaklaşımlar, kullanılabilirlik ve sıralama arasında saat kayması ikilemi ile karşı karşıyadır. Saf fiziksel zaman damgaları, yoğun senkronizasyon gerektirir ve CAP teoremi gereği bölünme toleransını ihlal ederken, saf mantıksal saatler (örneğin, Lamport zaman damgaları veya Vektör saatler) zamana bağlı yerellik ve veritabanı sıkıştırma verimliliğinden feragat eder. K-sıralılığı gerektiren zorluk, veritabanı indeksleme verimliliğiyle birlikte yaşanmalıdır. Bu kaba zaman sıralaması, kesin monotonluk ile birlikte var olmalıdır, böylece başarısızlık senaryolarında geriye dönüş yoktur. Ayrıca, denizaltı kablosu kesildiğinde bölgesel izolasyon, kimlik çakışmasına veya kullanılabilirlik kaybına neden olmamalıdır.
Fiziksel zamanı (milisaniye bileşeni) mantıksal sayıcılarla birleştiren bir Hibrit Mantıksal Saat (HLC) mimarisi uygulayın, düğüm ID partisyonlamasını artırın. Her bölgesel küme, bir konsensüs hizmetinden (örneğin, etcd veya ZooKeeper) yalnızca başlangıçta veya üyelik değiştiğinde bir düğüm ID (10-16 bit) alır. Her düğümde, HLC fiziksel zaman ilerlemediğinde mantıksal bileşenini artırır ve saat ayarlamalarına rağmen monotonluğu garanti eder.
Kimlik yapısı, epoch milisaniyeleri (41 bit) + mantıksal sayıcı (12 bit) + düğüm ID (10 bit) birleşimini içerir. Bölünmeler sırasında, düğümler yerel mantıksal sayıcı alanlarından tahsis yapmaya devam eder. Bölünme iyileşmesi sırasında, HLC'nin max-plus-one birleştirme kuralı, merkezi koordinasyon olmadan nedenselliği korur.
Küresel bir kripto para borsası, AWS us-east-1, eu-west-1 ve ap-southeast-1 arasında işlem kimliklerinin üretilmesi gerekti. Sistem, düzenleyici denetim izleri için kesin zaman sıralamasını korurken, piyasa oynaklığı sırasında saniyede 8 milyon sipariş işlemek zorundaydı. Ağ bölünmeleri sırasında denizaltı kablosu bakımı nedeniyle, önceki sistemlerinde UUIDv4 çakışma riskleri ortaya çıkmış ve bu da veritabanı benzersiz kısıtlama ihlallerine ve ticaret duraklamalarına neden olmuştur.
Çözüm 1: Merkezi PostgreSQL dizisi ile önbellekleme
Bir PostgreSQL dizisiyle uygulama düzeyinde toplu tahsis (bir seferde 10.000 kimlik alma) veritabanı yuvarlama turlarını azaltmıştır. Ancak, Asya-Pasifik ağ bölünmesi sırasında, önbellek düğümleri tahsis edilen alanlarını 90 saniye içinde tüketmiş ve UUID üretimine geri dönmeye zorlamıştır bu, denetim yolu sıralamasını bozmuştur. Tek bir RDS örneği, bölgeden bölgeye yazımlar için 140 ms gecikme cezası da yaratarak 50 ms altındaki üretim gereksinimini ihlal etmiştir.
Çözüm 2: Snowflake ilhamlı Twitter algoritması
ZooKeeper yönetimindeki düğüm ID'leri ile Snowflake uygulamak, düğüm başına 22.000 ID/saniye başardı ve kompakt 64-bit ID’lerle mükemmel sıralanabilirlik sağladı. Ancak, Avrupa düğümlerinde NTP daemon'ları sıçrama saniyeleri esnasında kayma yaşarken, ABD düğümleri hemen adımlama gerçekleştirdiği için sistem, tekrar eden milisaniye zaman damgaları üretti ve bu durum, veritabanı kısıtlama kontrollerini maliyetli hale getirdi ve verimliliği %40 oranında düşürdü.
Çözüm 3: Hibrit Mantıksal Saat ile CRDT birleşimi
CockroachDB'nin HLC desenini benimseyerek, her bölgesel lider, 4096 ID'yi milisaniye başına düğüm başına tutabilen bir yerel mantıksal sayıcıyı korudu ve düğüm ID alanı bölgeye göre partisyonlandı. Singapur kablo kesintisi sırasında, izole düğümler mantıksal sayıcılarını kullanarak ID üretmeye devam etti ve bağlantı yeniden sağlandığında, HLC karşılaştırma işlevi hiç çakışma olmadan nedenselliği korudu. Bu yaklaşım, doğruluk garantileri için 128-bit ID genişliğinden feragat etti ve bölünmeler sırasında kullanılabilirliği korudu.
Seçilen Çözüm ve Sonuç
Çözüm 3, bölünme toleransı ve monotonluk garantileri nedeniyle seçildi. Sistem, Güney Çin Denizi kablosu bakımında 4 saatlik bir bölünmeye dayanarak, izolasyon altındaki Tokyo bölgesinde 12 milyon ID/saniye işleyerek çakışma olmadan başarılı oldu. Yeniden uzlaşma sırasında HLC’nin önce olur takibi sayesinde sıfır ID yeniden yazımı gerekti ve depolama maliyetleri UUID'ye kıyasla %15 azaldı, bu da lexikografik sıralamanın RocksDB sıkıştırmalarını azalttı.
Çoğu aday, NTP'nin her zaman zamanı ileriye taşıdığı varsayımında bulunur. Gerçekte, agresif saat kayması düzeltmesi, zamanı yüzlerce milisaniye geri ayarlayabilir. Çözüm, kalıcı monoton bir saat (benzer şekilde CockroachDB'deki "sentetik" zaman) sürdürmektir: işletim sistemi, son tahsis edilen ID'nin fiziksel bileşeninden daha düşük bir zaman damgası rapor ettiğinde, sistem fiziksel gerilemeyi göz ardı eder ve yalnızca mantıksal sayıcıyı artırmaya devam eder, gerçek zaman geriye yetişene kadar.
Ayrıca, düğümler maksimum kayma güven aralıklarını yaymak için saat sınırları yayma uygulayın; yerel belirsizlik 10 ms'yi aşarsa, tahsis taleplerini reddedin. Bu mekanizma, düğümlerin ID vermeden önce senkronizasyonunu tespit eder. Bu, dış tutarlılığı ihlal eden "geri sarma" anormalliklerini önler.
Adaylar, 10 bitlik düğüm ID'lerin 1.024 benzersiz üreticiye izin verdiğini sık sık göz ardı eder. Kubernetes ortamında sık sık pod yeniden başlatmaları ile, dikkatsiz ID tahsisi birkaç hafta içinde alanı tüketir. Çözüm, dönem tabanlı geri dönüşümü uygulamaktır: düğüm ID'leri etcd'de TTL'lerle (Yaşam Süresi) kiralanır ve geri dönüşüm yapılan ID'ler, maksimum saat kaymasını aşan bir "mezar taşı" karantina dönemine girer (genellikle 24 saat).
Yeniden dağıtım sırasında, sistem, o düğüm ID tarafından tahsis edilen son ID'nin HLC'sini kontrol eder. Eğer mevcut küresel zaman ile o zaman damgası arasındaki fark, karantina süresini aşarsa, ID yeniden tahsis edilmeye uygundur. Bu, emekli düğüm meta verilerini izleyen bir mezarlık hizmeti gerektirir.
K-sıralı kimlikler (Snowflake gibi), en son SSTable veya en sağdaki yaprak sayfasında aşırı yüklenme ile "sıcak uçta" yazma yoğunlaşmasına neden olur. Adaylar sık sık, k-sıralılığın okuma yerelliğini artırmasına rağmen, bunun Cassandra veya TiKV'de yazma çoğaltmaya yol açtığını kaçırır. Hafifletme, yazmaları 16 RocksDB memtablosuna dağıtan şard ön ekleri ile entropy kodlaması tanıtarak gerçekleştirilir: ID'ye, düğüm ID'sinin veya istemci oturumunun 4 bitlik hash'ini ekleyin, kaba zaman sıralamasını korurken yazmaları dağıtın.
CockroachDB için, ID sütununun üzerine hash-parçalanmış dizinler kullanın. Alternatif olarak, yakın zamandaki ID'lerin Redis Akışlarında toplu depolama öncesinde tamponlandığı yazma yığılması uygulayın. Bu, alım işlemlerini sıkıştırma döngülerinden ayırır.