Randflake ID'nin Tanıtımı: Dağıtılmış, Tek Biçimli, Tahmin Edilemez, Eşsiz Bir Rastgele ID Üreticisi.

64-bitlik tekil rastgele sayılar üretmemiz gereken ve harici tarafların bir sonraki veya önceki sayıyı tahmin edememesi gereken bir durumu düşünün.

Burada, 8 baytlık rastgele bir değer üretebilir, veri tabanında zaten var olup olmadığını kontrol edebilir ve tekil ise depolayabiliriz.

Ancak, bu yöntemin birkaç dezavantajı vardır. Tekilliği sağlamak için üretilen her sayıyı bir veri tabanında saklamamız gerekir. Veri tabanına en az bir gidiş-dönüş gereksinimi, özellikle ölçeklenebilirliğin kritik olduğu dağıtık bir ortamda gecikme sorunları yaratır.

Bu sorunları çözmek için Randflake ID'yi tanıtıyoruz: dağıtık, tek tip, tahmin edilemez, tekil rastgele bir ID üreteci.

Randflake ID Nasıl Çalışır?

Randflake ID, X (eski adıyla Twitter) tarafından geliştirilen, yaygın olarak kullanılan k-sıralı ID üretim mekanizması olan Snowflake ID'den esinlenmiştir.

Snowflake ID, bir tanımlayıcı oluşturmak için mevcut zaman damgasını, bir node ID'yi ve yerel bir sayacı kullanır.

Biz bu yaklaşımı rastgele tekil ID üretimi için daha da genişlettik ve yeni bir gizli anahtar öğesi ekledik.

Temel fikir, sayılar arasındaki ilişkiyi tahmin etmedeki imkansızlığı sağlamak için mevcut tekil ID üretecine bir block cipher katmanı eklemektir.

Bir block cipher, sabit uzunluktaki bir düz metin bloğunu aynı uzunluktaki bir şifreli metin bloğuna dönüştüren temel bir kriptografik fonksiyondur. Bu dönüşüm, bir kriptografik anahtar tarafından yönetilir. Bir block cipher'ın ayırt edici özelliği tersine çevrilebilirliğidir: her tekil girdinin tekil bir çıktıya karşılık gelmesini ve bunun tersini sağlayan birebir (bijektif) bir fonksiyon olmalıdır. Bu özellik, doğru anahtar uygulandığında orijinal düz metnin şifreli metinden kurtarılmasını sağladığı için şifre çözme için kritik öneme sahiptir.

Bir block cipher'ı birebir bir fonksiyon olarak kullanarak, her tekil girdinin tanımlanmış aralıkta karşılık gelen tekil bir çıktı üretmesini garanti edebiliriz.

Yapı ve tasarım değerlendirmesi

Bu temel kavramlar üzerine inşa ederek, 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 node identifier, 17-bitlik bir yerel sayaç ve sparx64 algoritmasına dayalı 64-bitlik bir block cipher içerir.

İşte bazı tasarım kararları:

• Google Cloud Platform'daki bazı VM örnekleri saati 0.2ms hassasiyetinde senkronize edebilir, ancak bu hassasiyet seviyesi genel internette veya diğer bulut sağlayıcılarında mevcut değildir.

• Saniye hassasiyetini seçtik çünkü düğümler arasında saati yalnızca birkaç milisaniye çözünürlükle etkili bir şekilde senkronize edebiliriz.

• 17-bit node identifier, aynı anda 131072 bireysel jeneratöre izin verir, bu da süreç başına, çekirdek başına, iş parçacığı başına atanabilir.

• Yüksek throughput sistemlerinde, 17-bit yerel sayaç yetersiz olabilir. Throughput'u eşleştirmek için, her biri farklı bir node ID'ye sahip birden fazla jeneratörü tek bir süreçte veya iş parçacığında çalışacak şekilde atayabiliriz.

• Modern, hafif bir ARX tabanlı block cipher olan sparx64'ü 64-bit block cipher olarak benimsedik.

• Randflake ID'ler, yalnızca gizli anahtara sahip olanlara kaynak node ID'lerini ve zaman damgalarını açıklayan dahili izlenebilirlik sunar.

• Teorik maksimum throughput, çoğu küresel ölçekli uygulama için yeterli olan 17.179.869.184 ID/s'dir.

Randflake ID üretimi için sözde kod

Randflake ID üretim sürecini daha fazla açıklamak için, aşağıdaki Python pseudocode basitleştirilmiş bir implementasyon 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  # Node ID için 17 bit (maks. 131072 node)
11RANDFLAKE_SEQUENCE_BITS = 17  # Sıra için 17 bit (maks. 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]

Node ID kiralama mekanizmasına sahip, üretime hazır bir Randflake implementasyonu GitHub üzerinde mevcuttur.

Diğer hususlar

Bu bölümde, Randflake ID implementasyonu için bazı ek hususları tartışacağız.

Node ID koordinasyonu

Kiralama tabanlı node ID koordinasyonunu öneriyoruz.

Bu yaklaşımda, merkezi bir koordinasyon servisi her jeneratöre tekil bir node ID atar.

Bu node ID, tekilliği sağlamak için kiralama süresi boyunca yeniden atanmaz, bu da koordinasyon servisiyle sık iletişime olan ihtiyacı azaltır.

Kiralamayı elinde bulunduran jeneratör, yenileme koşulu karşılanırsa koordinasyon servisinden kiralamanın yenilenmesini talep edebilir.

Yenileme koşulu, kiralamanın yenilenmesi için karşılanması gereken bir dizi kriteri ifade eder, örneğin jeneratörün hala aktif olması ve node ID'ye ihtiyaç duyması gibi.

Leaseholder, node ID aralığının mevcut sahibidir.

Kiralama, geçerli zaman dilimi içindeyse aktif ve süresi dolmamış kabul edilir.

Bu şekilde, gidiş-dönüşleri kiralama yenileme dönemi başına bire indirebilir, gecikmeyi en aza indirebilir ve dağıtık sistemlerde verimliliği artırabiliriz.

Arızalı saate karşı önleme

Kiralama servisi, 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 eşit olmalıdır.

Jeneratör, mevcut zaman damgası kiralama başlangıç zamanından küçük veya kiralama bitiş zamanından büyükse isteği reddetmelidir.

Bu prosedür, saat geriye sıçradığında üretilen ID'lerin tekilliğini korumak için önemlidir. Örneğin, bir saat geriye sıçrarsa, daha önce atanmış bir kiralamadan daha erken bir başlangıç zamanıyla yeni bir kiralama atanabilir, bu da potansiyel olarak çift ID'lerin üretilmesine yol açabilir. Mevcut bir kiralama dönemi içindeki zaman damgalarına sahip istekleri reddederek, bu senaryoyu önler ve ID'lerin tekilliğini koruruz.

ID dağılımının tekdüzeliği

Yukarıdaki histograma göre, üretilen Randflake ID'lerinin dağılımının çok tekdüze olduğunu görebiliriz. Bu, ID dağılımının doğrudan sharding key olarak kullanılabileceğini göstermektedir.

Sonuç

Bu makalede, Snowflake ve Sparx64'ün avantajlarını birleştiren yeni bir ID üretim algoritması olan Randflake'i tanıttık.

Bu makalenin size Randflake ve implementasyonu 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 bizimle iletişime geçmekten çekinmeyin. Ayrıca Randflake'i geliştirmeye ve diğer programlama dillerinde implemente etmeye yardımcı olacak katkıda bulunanlar arıyoruz.

Randflake ve Snowflake için üretime hazır bir koordinasyon hizmeti yayınlamayı planlıyoruz, bu hizmet GitHub'da açık kaynaklı olacaktır. Güncellemeler için takipte kalın!