分散ID生成スキームとSnowflakeアルゴリズムの詳細な説明

I. 背景

インターネットビジネスシステムには、さまざまな種類のIDがあります。これらのIDはグローバルな一意性を保証する必要があり、そのようなIDは分散IDと呼ばれます。分散IDは、一意性、増加傾向、高可用性、高パフォーマンスなどの特性を満たす必要があります。

Snowflakeアルゴリズムは、Twitterが内部の分散プロジェクトに適用した分散ID生成スキームです。このアルゴリズムがオープンソース化された後、主要企業に認識されました。この影響下で、主要企業は独自の特性を持つ分散IDジェネレーターを相次いで開発しました。Snowflakeアルゴリズムを掘り下げる前に、一般的に使用される分散ID生成スキームの概要を説明する必要があります。

II. 分散ID生成スキーム

2.1 UUID

このアルゴリズムの中核となる考え方は、マシンのネットワークカード、ローカル時間、および乱数を組み合わせてUUIDを生成することです。

• 利点: ローカルで生成できます。生成プロセスはシンプルで、パフォーマンスが良く、高可用性の問題のリスクはありません。
• 欠点: 生成されたIDが長すぎるため、ストレージの冗長性が発生します。さらに、IDは順序付けられておらず、判読できないため、クエリ効率が低下します。

2.2 データベースの自動インクリメントID

MySQLのauto_incrementなど、データベースのID自動インクリメント戦略を採用します。高可用性を実現するために、複数のデータベースを使用でき、それぞれ異なるステップサイズを設定して、重複しない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で生成され、INCRを介してインクリメントされます。

• 利点: データベースに依存せず、柔軟で使いやすく、データベースよりもパフォーマンスが向上します。数値IDは自然に順序付けられているため、ページネーションやソートが必要なシナリオに非常に役立ちます。
• 欠点: システムでRedisが使用されていない場合、このコンポーネントを導入するとシステムの複雑さが増し、コーディングと構成のワークロードも比較的大きくなります。

2.4 Snowflakeアルゴリズム

Snowflakeアルゴリズムは、Twitterが内部の分散プロジェクトに適用し、オープンソース化された後、国内の主要企業に広く認識されています。Twitterは、2010年の子供の日に公式ブログを通じてこのアルゴリズムを導入し、各ツイートを識別しました。

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

Snowflakeアルゴリズムは、64ビットを使用してIDを保存します。

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

タイムスタンプ、マシンID、および自動インクリメントIDが占めるビット数は、実際の状況に応じて調整できます。Snowflakeアルゴリズムは、最初の数ビットがタイムスタンプであるため、基本的な順次性を持ち、IDは時間でソートできます。

III. Snowflakeアルゴリズムの詳細な説明

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
    // 最後に記録された時間と同じ場合は、ステップを1ずつ増やします。それ以外の場合は、ステップを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: 最高のサーバーレスWebホスティング

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

🚀 お気に入りの言語で構築

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

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

使用量に応じて支払い—リクエストも料金もありません。

⚡ 従量課金制、隠れたコストなし

アイドル料金はなく、シームレスなスケーラビリティのみです。

📖 ドキュメントを見る

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