GoSudaRandflake ID: Sparx64 Blok Şifresi ile Dağıtık 64-Bit Benzersiz Kimlik Üretimi
Rastgele, benzersiz 64 bitlik sayılar üretmemiz gereken ve dış tarafların bir sonraki veya önceki sayıyı tahmin edememesi gereken bir durumu ele alalım.
Burada, 8 baytlık bir rastgele değer üretebilir, bu değerin veritabanında zaten var olup olmadığını kontrol edebilir ve benzersizse saklayabiliriz.
Ancak bu yöntemin birkaç dezavantajı vardır. Benzersizliği sağlamak için üretilen her sayıyı bir veritabanında saklamak zorundayız. Veritabanına en az bir gidiş-dönüş gerekliliği, özellikle ölçeklenebilirliğin kritik olduğu dağıtık bir ortamda gecikme sorunlarına yol açmaktadır.
Bu sorunları çözmek amacıyla, dağıtık, düzgün dağılımlı, tahmin edilemez ve benzersiz bir rastgele kimlik üreteci olan Randflake ID'yi tanıtıyoruz.
Randflake ID Nasıl Çalışır?
Randflake ID, X (eski adıyla Twitter) tarafından geliştirilen ve yaygın olarak kullanılan, k-sıralı bir kimlik üretim mekanizması olan Snowflake ID'den esinlenmiştir.
Snowflake ID, bir kimlik oluşturmak için mevcut zaman damgasını, bir düğüm kimliğini ve yerel bir sayacı kullanır.
Bu yaklaşımı rastgele benzersiz kimlik üretimi için daha da genişlettik ve yeni bir gizli anahtar öğesi ekledik.
Temel fikir, sayılar arasındaki ilişkinin tahmin edilmesini imkânsız kılmak için mevcut benzersiz kimlik üreticisine bir blok şifre katmanı eklemektir.
Blok şifre, sabit uzunluktaki bir düz metin bloğunu aynı uzunlukta bir şifreli metin bloğuna dönüştüren temel bir kriptografik fonksiyondur. Bu dönüşüm bir kriptografik anahtar tarafından yönetilir. Blok şifrenin ayırt edici özelliği tersinirliğidir: her benzersiz girdinin benzersiz bir çıktıya karşılık gelmesini ve tersine, her benzersiz çıktının benzersiz bir girdiye karşılık gelmesini sağlayan bire bir (bijektif) bir fonksiyon olmak zorundadır. Bu özellik, doğru anahtar uygulandığında orijinal düz metnin şifreli metinden geri elde edilmesini sağladığı için şifre çözme açısından çok önemlidir.
Blok şifreyi bire bir bir fonksiyon olarak kullanarak, her benzersiz girdinin tanımlı aralık içinde karşılık gelen benzersiz bir çıktı üretmesini garanti edebiliriz.
Yapı ve Tasarım Hususları
Bu temel kavramlardan yola çıkarak, Randflake ID'nin bu fikirleri pratikte nasıl uyguladığını inceleyelim.
Randflake ID yapısı, saniye hassasiyetinde 30 bitlik bir unix zaman damgası, 17 bitlik bir düğüm tanımlayıcısı, 17 bitlik bir yerel sayaç ve sparx64 algoritmasına dayanan 64 bitlik bir blok şifre içerir.
Burada bazı tasarım kararları yer almaktadır:
Google Cloud Platform'daki bazı VM örnekleri saati 0,2 ms hassasiyetle senkronize edebilir, ancak bu düzeyde doğruluk genel internette veya diğer bulut sağlayıcılarında mevcut değildir.
Düğümler arasında saati yalnızca birkaç milisaniyelik çözünürlükte etkin bir şekilde senkronize edebildiğimiz için saniye hassasiyetini seçtik.
17 bitlik düğüm tanımlayıcısı, aynı anda 131072 ayrı üreteca izin verir; bu üreteçler süreç, çekirdek veya iş parçacığı bazında atanabilir.
Yüksek verimli sistemlerde 17 bitlik yerel sayaç yetersiz kalabilir. Verimle eşleşmek için, her biri farklı bir düğüm kimliğine sahip birden fazla üreteci tek bir süreçte veya iş parçacığında çalışacak şekilde atayabiliriz.
64 bitlik blok şifre olarak, modern ve hafif bir ARX tabanlı blok şifre olan sparx64'ü benimsedik.
Randflake ID'ler dahili izlenebilirlik sunar; oluşturuldukları düğüm kimliğini ve zaman damgasını yalnızca gizli anahtara sahip olanlara açıklar.
Teorik maksimum verim 17.179.869.184 ID/s'dir; bu, çoğu küresel ölçekli uygulama için yeterlidir.
Randflake ID Üretiminin Sözde Kodu
Randflake ID üretim sürecini daha ayrıntılı göstermek için, aşağıdaki Python sözde kodu basitleştirilmiş bir uygulama sunmaktadır:
1import time
2import struct
3from .sparx64 import Sparx64
4
5# Sabitler
6RANDFLAKE_EPOCH_OFFSET = 1730000000 # Pazar, 27 Ekim 2024 03:33:20 UTC
7
8# Bit tahsisi
9RANDFLAKE_TIMESTAMP_BITS = 30 # Zaman damgası için 30 bit (34 yıllık ömür)
10RANDFLAKE_NODE_BITS = 17 # Düğüm kimliği için 17 bit (en fazla 131072 düğüm)
11RANDFLAKE_SEQUENCE_BITS = 17 # Sıra için 17 bit (en fazla 131072 sıra)
12
13# Türetilmiş sabitler
14RANDFLAKE_MAX_TIMESTAMP = RANDFLAKE_EPOCH_OFFSET + (1 << RANDFLAKE_TIMESTAMP_BITS) - 1
15RANDFLAKE_MAX_NODE = (1 << RANDFLAKE_NODE_BITS) - 1
16RANDFLAKE_MAX_SEQUENCE = (1 << RANDFLAKE_SEQUENCE_BITS) - 1
17
18class Randflake:
19 def __init__(self, node_id: int, secret: bytes):
20 self.node_id = int(node_id)
21 self.sequence = int(0)
22 self.rollover = int(time.time())
23 self.sbox = Sparx64(secret)
24
25 def _new_raw(self) -> int:
26 while True:
27 now = int(time.time())
28
29 self.sequence += 1
30 sequence = self.sequence
31
32 if sequence > RANDFLAKE_MAX_SEQUENCE:
33 if now > self.rollover:
34 self.sequence = 0
35 self.rollover = now
36 sequence = 0
37 else:
38 continue
39
40 timestamp = now - RANDFLAKE_EPOCH_OFFSET
41 return (timestamp << 34) | (self.node_id << 17) | sequence
42
43 def generate(self) -> int:
44 id_raw = self._new_raw()
45 src = struct.pack("<q", id_raw)
46 dst = bytearray(8)
47 self.sbox.encrypt(dst, src)
48 return struct.unpack("<q", dst)[0]
Düğüm kimliği kiralama mekanizmasını içeren, üretime hazır bir Randflake uygulaması GitHub üzerinde mevcuttur.
Diğer Hususlar
Bu bölümde, Randflake ID uygulamasına ilişkin bazı ek hususları ele alacağız.
Düğüm Kimliği Koordinasyonu
Kiralama tabanlı düğüm kimliği koordinasyonu öneriyoruz.
Bu yaklaşımda, merkezi bir koordinasyon hizmeti her üreteca benzersiz bir düğüm kimliği atar.
Benzersizliği korumak için bu düğüm kimliği kiralama süresi boyunca yeniden atanmaz ve bu da koordinasyon hizmetiyle sık iletişim ihtiyacını azaltır.
Kiralamayı tutan üreteç, yenileme koşulu sağlandığında koordinasyon hizmetinden kiralamanın yenilenmesini talep edebilir. Yenileme koşulu, kiralamanın yenilenmesi için karşılanması gereken ölçütler kümesini ifade eder; örneğin üretecin hâlâ etkin olması ve düğüm kimliğine ihtiyaç duyması gibi.
Kiralama sahibi, düğüm kimliği aralığının mevcut tutucusudur.
Kiralama, geçerli süre içindeyse etkin ve süresi dolmamış kabul edilir.
Bu sayede, kiralama yenileme süresi başına gidiş-dönüş sayısını bire indirebilir, dağıtık sistemlerde gecikmeyi en aza indirip verimliliği artırabiliriz.
Hatalı Saate Karşı Önlem
Kiralama hizmeti, bir kiralama tahsis ederken zaman damgası tutarlılığını kontrol etmelidir. Atanan kiralama başlangıç zamanı, son kiralama başlangıç zamanından büyük veya ona eşit olmalıdır.
Üreteç, mevcut zaman damgası kiralama başlangıç zamanından küçükse veya kiralama bitiş zamanından büyükse isteği reddetmelidir.
Bu prosedür, saat geriye doğru sıçradığında üretilen kimliklerin benzersizliğini korumak açısından önemlidir. Örneğin, saat geriye doğru sıçrarsa, daha önce atanmış bir kiralamadan daha erken bir başlangıç zamanına sahip yeni bir kiralama atanabilir ve bu da yinelenen kimliklerin üretilmesine yol açabilir. Mevcut bir kiralama süresi içindeki zaman damgalarına sahip istekleri reddederek bu senaryoyu engelleriz ve kimliklerin benzersizliğini sürdürürüz.
Kimlik Dağılımının Düzgünlüğü
Yukarıdaki histograma dayanarak, üretilen Randflake ID'lerinin dağılımının çok düzgün olduğunu görebiliriz. Bu, kimlik dağılımının doğrudan bir parçalama (sharding) anahtarı olarak kullanılabileceğini göstermektedir.
Sonuç
Bu makalede, Snowflake ve Sparx64'ün avantajlarını birleştiren yeni bir kimlik üretim algoritması olan Randflake'i tanıttık.
Bu makalenin size Randflake ve uygulaması hakkında kapsamlı bir anlayış sağladığını umuyoruz.
Randflake'in tam kaynak kodunu GitHub üzerinde bulabilirsiniz.
Herhangi bir sorunuz veya öneriniz varsa, lütfen çekinmeden iletişime geçin. Randflake'i geliştirmeye ve diğer programlama dillerinde uygulanmasına yardımcı olacak katkıda bulunanlar da arıyoruz.
Randflake ve Snowflake için üretime hazır bir koordinasyon hizmeti yayımlamayı planlıyoruz; bu hizmet GitHub üzerinde açık kaynak olarak sunulacaktır. Güncellemeler için takipte kalın!