Leapcell: The Best of Serverless Web Hosting

分散型ID生成スキームとスノーフレイクアルゴリズムの詳細解説

Ⅰ. 背景

インターネットビジネスシステムには、様々な種類のIDが存在します。これらのIDは、グローバルな一意性を保証する必要があり、このようなIDを分散型IDと呼びます。分散型IDは、一意性、増加傾向、高可用性、高性能などの特性を満たす必要があります。

スノーフレイクアルゴリズムは、分散型ID生成スキームの一つで、ツイッターが内部の分散型プロジェクトに適用していました。このアルゴリズムがオープンソース化された後、各大企業によって認知されました。この影響を受けて、各大企業は次々と独自の特徴を持つ分散型IDジェネレータを開発しました。スノーフレイクアルゴリズムを詳しく調べる前に、一般的に使用される分散型ID生成スキームの概要を説明する必要があります。

Ⅱ. 分散型ID生成スキーム

2.1 UUID

このアルゴリズムの核心アイデアは、マシンのネットワークカード、ローカルタイム、乱数を組み合わせてUUIDを生成することです。

利点：ローカルで生成できます。生成プロセスはシンプルで、性能が良好で、高可用性の問題のリスクがありません。
欠点：生成されたIDが長すぎて、ストレージの冗長性を引き起こします。また、IDは無秩序で読み取りにくく、照会効率が低くなります。

2.2 データベースの自動増分ID

データベースのid自動増分戦略を採用します。例えば、MySQLのauto_incrementです。高可用性を実現するために、複数のデータベースを使用し、それぞれ異なるステップサイズを設定して、重複しないIDを生成することができます。

利点：データベースで生成されたIDは絶対に順序付けられ、高可用性を実現する方法は比較的シンプルです。
欠点：データベースインスタンスの独立したデプロイが必要で、コストがかかり、性能のボトルネックがあります。

2.3 RedisによるID生成

Redisのすべてのコマンド操作はシングルスレッドです。Redis自体は、incrやincrebyなどの自動増分原子コマンドを提供しているため、生成されたIDが一意かつ順序付けられていることを保証できます。単一ノードの性能ボトルネックに対処するために、Redisクラスタを使用してより高いスループットを得ることができます。例えば、5つのRedisノードを含むクラスタでは、各Redisの初期値をそれぞれ1、2、3、4、5に設定し、ステップサイズを5に設定することができます。各Redisで生成されるIDは次のとおりです：

A: 1, 6, 11, 16, 21
B: 2, 7, 12, 17, 22
C: 3, 8, 13, 18, 23
D: 4, 9, 14, 19, 24
E: 5, 10, 15, 20, 25

ステップサイズと初期値は事前に決定する必要があります。Redisクラスタを使用することで、単一障害点の問題も回避できます。また、Redisは、毎日0から始まる連番を生成するのに適しています。例えば、注文番号は「日付 + 毎日の自動増分番号」の形式を採用することができます。Redisで毎日Keyを生成し、INCRを通じて増分させます。

利点：データベースに依存せず、使い勝手が柔軟で便利で、データベースよりも性能が良好です。数値IDは自然に順序付けられており、ページングやソートが必要なシナリオなどに非常に役立ちます。
欠点：システムでRedisを使用していない場合、このコンポーネントを導入するとシステムの複雑性が増し、コーディングと構成の作業量も比較的大きくなります。

2.4 スノーフレイクアルゴリズム

スノーフレイクアルゴリズムは、ツイッターが内部の分散型プロジェクトに適用しており、オープンソース化された後、国内の各大企業によって広く認知されています。ツイッターは2010年の子供の日に公式ブログを通じてこのアルゴリズムを紹介し、各ツイートを識別しています。

+--------------------------------------------------------------------------+
| 1 Bit Unused | 41 Bit Timestamp |  10 Bit NodeID  |   12 Bit Sequence ID |
+--------------------------------------------------------------------------+

スノーフレイクアルゴリズムは、64ビットを使用してIDを保存します：

最上位ビットは予約されており、現在は使用されていません。
次の41ビットはタイムスタンプとして使用され、最小の時間単位はミリ秒です。41ビットのタイムスタンプは約69年間（2^41 -1）使用できます。時間表現範囲を最大限に活用するために、タイムスタンプはシステムが最初にデプロイされた時刻からカウントを開始することができます。例えば、2020-02-02 00:00:00です。
次の10ビットはマシンID（worker id）として使用され、1024台のマシンをサポートできます。10ビットはまた、2つの部分に分割することもできます。一方をデータセンターIDとし、もう一方をマシンIDとします。例えば、5:5の比率で分割すると、32のデータセンターをサポートでき、各データセンターは最大32台のマシンを収容することができます。
最後の12ビットは、単位時間（ミリ秒）内の自動増分IDで、4096個のIDを表すことができます。つまり、各マシンは1ミリ秒あたり最大4096個のIDを生成することができます。

タイムスタンプ、マシンID、自動増分IDが占めるビット数は、実際の状況に応じて調整することができます。スノーフレイクアルゴリズムは、最初の数ビットがタイムスタンプであるため、基本的に順序性を持っており、IDを時間でソートすることができます。

Ⅲ. スノーフレイクアルゴリズムの詳細解説

3.1 Golangのコアコード

var (
    // システムが最初に起動された時刻として設定できます。ミリ秒単位で、41ビットを占め、69年間使用できます。
    Epoch int64 = 12345688374657

    // インスタンスのIDは10ビットを占め、最大1024個のインスタンスをサポートできます。
    NodeBits uint8 = 10

    // ステップサイズは12ビットを占めます。各インスタンスは1ミリ秒あたり最大2^12 = 4096個の重複しないデータを生成できます。
    StepBits uint8 = 12
)

// 生成アルゴリズム
func (n *Node) Generate() ID {

    n.mu.Lock()
    // 設定されたタイムスタンプから現在まで経過したミリ秒数
    now := time.Since(n.epoch).Nanoseconds() / 1000000
    // 前回記録した時間と同じ場合は、stepを1増やします。それ以外の場合は、stepを0にリセットします。
    if now == n.time {
        n.step = (n.step + 1) & n.stepMask

        if n.step == 0 {
            for now <= n.time {
                now = time.Since(n.epoch).Nanoseconds() / 1000000
            }
        }
    } else {
        n.step = 0
    }

    n.time = now
    // タイムスタンプ41ビット | ノード10ビット | ステップ12ビット
    r := ID((now)<<n.timeShift |
        (n.node << n.nodeShift) |
        (n.step),
    )

    n.mu.Unlock()
    return r
}

特定のビット割り当ては、独自のニーズに応じて調整することができます。例えば、(41, 10, 12)、(41, 6, 16)などです。完全なGolangコードリポジトリ：snowflake github。

3.2 利点

ストレージ量が少ない：8バイトしか必要ありません。
読み取りやすさが高い：IDには一定の構造と意味があります。
性能が良好：IDは集中的に生成することも、独立したノードで生成することもできます。

3.3 欠点

時間の巻き戻しにより、IDの重複生成が発生します。

3.4 クロック巻き戻しの解決策

マシンIDの10ビットのうち2ビットをクロック巻き戻しビットとして使用することができます。クロック巻き戻しが検出された場合、巻き戻しビットを1増やし、最大値に達すると0から循環します。例えば、10ビットのマシン番号を8ビットのマシン番号 + 2ビットの巻き戻しビットに調整します。クロック巻き戻しが検出されるたびに、巻き戻しビットを1増やします。巻き戻しビットが最大値（3）を超えると、0にリセットします。同じ時間帯では、クロック巻き戻しは最大3回サポートされます。各巻き戻しの後、クロック巻き戻しビットが異なるため、最終的に生成されるIDも異なります。

Leapcell: The Best of Serverless Web Hosting

最後に、Goサービスをデプロイするのに最適なプラットフォームをお勧めします：Leapcell

🚀 好きな言語で構築

JavaScript、Python、Go、またはRustで簡単に開発できます。

🌍 無料で無制限のプロジェクトをデプロイ

使用する分だけ支払います—リクエストがなければ、請求はありません。

⚡ 使った分だけ支払い、隠したコストはありません

アイドル料金はなく、シームレスなスケーラビリティがあります。

📖 ドキュメントを探索

🔹 Twitterでフォローしてください：@LeapcellHQ