GoSuda

Randflake IDの紹介：分散型で均一、予測不可能、かつユニークなランダムIDジェネレーター。

By Lemon Mint
views ...

一意な64ビット乱数を生成する必要があり、外部の第三者が次の乱数または以前の乱数を予測できない状況を考慮します。

ここで、8バイトのランダムな値を生成し、それがデータベースに既に存在するかどうかを確認し、一意であればそれを保存することができます。

しかし、この方法にはいくつかの欠点があります。一意性を確保するために、生成されたすべての番号をデータベースに保存する必要があります。データベースへの少なくとも1回のラウンドトリップが必要となるため、特にスケーラビリティが重要となる分散環境では、レイテンシーの問題が発生します。

これらの問題を解決するために、我々はRandflake IDを導入します。これは、分散型で均一、予測不可能、かつ一意なランダムIDジェネレーターです。

Randflake IDの仕組み

Randflake IDは、X（旧Twitter）が開発した広く使用されているkソートID生成メカニズムであるSnowflake IDに触発されています。

Snowflake IDは、現在のタイムスタンプ、ノードID、およびローカルカウンターを使用して識別子を生成します。

我々はこのアプローチをさらに拡張し、ランダムで一意なID生成のために、新しい秘密鍵要素を追加しました。

主要なアイデアは、既存の一意なIDジェネレーターにブロック暗号層を追加することで、数値間の関係を予測することを不可能にすることです。

ブロック暗号は、固定長の平文ブロックを同じ長さの暗号文ブロックに変換する基本的な暗号機能です。この変換は暗号鍵によって制御されます。ブロック暗号の際立った特徴は、その可逆性です。つまり、一対一（全単射）関数である必要があり、各一意の入力が一意の出力に対応し、その逆もまた然りであることを保証します。この特性は復号化にとって不可欠であり、正しい鍵が適用されたときに暗号文から元の平文を復元することを可能にします。

ブロック暗号を一対一関数として採用することにより、定義された範囲内で各一意の入力が対応する一意の出力を生成することを保証できます。

構造と設計上の考慮事項

これらの基本的な概念に基づいて、Randflake IDがこれらのアイデアを実際にどのように実装しているかを検証しましょう。

Randflake IDの構造には、秒単位の精度を持つ30ビットのUnixタイムスタンプ、17ビットのノード識別子、17ビットのローカルカウンター、およびsparx64アルゴリズムに基づく64ビットのブロック暗号が含まれます。

以下にいくつかの設計上の決定事項を示します。

  • Google Cloud Platformの一部のVMインスタンスは0.2msの精度でクロックを同期できますが、そのレベルの精度は公共のインターネットや他のクラウドプロバイダーでは利用できません。

  • 我々が秒単位の精度を選択したのは、ノード間のクロックを数ミリ秒の解像度内で効果的に同期できるためです。

  • 17ビットのノード識別子により、同時に131072個の個別ジェネレーターが可能になり、これらはプロセスごと、コアごと、スレッドごとに割り当てることができます。

  • 高スループットシステムでは、17ビットのローカルカウンターでは不十分な場合があります。スループットに合わせるために、それぞれ異なるノードIDを持つ複数のジェネレーターを単一のプロセスまたはスレッド内で動作させることができます。

  • 我々は、現代の軽量なARXベースのブロック暗号であるsparx64を64ビットブロック暗号として採用しました。

  • Randflake IDは内部的なトレーサビリティを提供し、秘密鍵を所有する者のみにその生成元ノードIDとタイムスタンプを開示します。

  • 理論上の最大スループットは17,179,869,184 ID/秒であり、これはほとんどのグローバルスケールアプリケーションにとって十分です。

Randflake ID生成の擬似コード

Randflake IDの生成プロセスをさらに説明するために、以下のPython擬似コードは簡略化された実装を提供します。

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# 定数
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # 2024年10月27日(日) 午前3時33分20秒 UTC
 7
 8# ビット割り当て
 9RANDFLAKE_TIMESTAMP_BITS = 30  # タイムスタンプ用30ビット（有効期間34年）
10RANDFLAKE_NODE_BITS = 17  # ノードID用17ビット（最大131072ノード）
11RANDFLAKE_SEQUENCE_BITS = 17  # シーケンス用17ビット（最大131072シーケンス）
12
13# 派生定数
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]

ノードIDリース機構を特徴とするRandflakeのプロダクションレディな実装は、GitHubで入手可能です。

その他の考慮事項

このセクションでは、Randflake IDを実装するための追加の考慮事項について説明します。

ノードIDの調整

我々はリースベースのノードID調整を提案します。

このアプローチでは、中央の調整サービスが各ジェネレーターに一意のノードIDを割り当てます。

このノードIDは、一意性を確保するためにリース期間中再割り当てされないため、調整サービスとの頻繁な通信の必要性が減ります。

リースを保持するジェネレーターは、更新条件が満たされた場合、調整サービスにリースの更新を要求できます。

更新条件とは、ジェネレーターがまだアクティブであり、ノードIDを必要としているなど、リースが更新されるために満たされなければならない一連の基準を指します。

リースホルダーは、ノードID範囲の現在の保持者です。

リースが有効な期間内である場合、リースはアクティブであり、期限切れではないと見なされます。

この方法により、リース更新期間ごとに1回のラウンドトリップに削減でき、分散システムにおけるレイテンシーを最小限に抑え、効率を向上させることができます。

不良クロックに対する緩和策

リースサービスは、リースを割り当てる際にタイムスタンプの一貫性をチェックする必要があります。割り当てられたリースの開始時刻は、最後のリースの開始時刻以上でなければなりません。

現在のタイムスタンプがリースの開始時刻より小さいか、リースの終了時刻より大きい場合、ジェネレーターは要求を拒否すべきです。

この手順は、クロックが逆行した場合に生成されるIDの一意性を保護するために重要です。例えば、クロックが逆行した場合、以前に割り当てられたリースよりも早い開始時刻を持つ新しいリースが割り当てられ、重複するIDが生成される可能性があります。既存のリース期間内のタイムスタンプを持つ要求を拒否することにより、このシナリオを防ぎ、IDの一意性を維持します。

ID分布の均一性

ID分布のヒストグラム

上記のヒストグラムから、生成されたRandflake IDの分布が非常に均一であることがわかります。これは、ID分布をシャーディングキーとして直接使用できることを示唆しています。

結論

この記事では、SnowflakeとSparx64の利点を組み合わせた新しいID生成アルゴリズムであるRandflakeを紹介しました。

この記事が、Randflakeとその実装について包括的な理解を提供できたことを願っています。

Randflakeの完全なソースコードはGitHubで入手できます。

ご質問やご提案がありましたら、お気軽にお問い合わせください。Randflakeの改善と他のプログラミング言語での実装を支援してくれる貢献者も募集しています。

RandflakeおよびSnowflake向けのプロダクションレディな調整サービスをリリースする予定であり、これはGitHubでオープンソース化されます。今後の更新にご期待ください！