分散環境でIDの一意性を確保する方法

[[408786]]

この記事はWeChatの公開アカウント「Java Geek Technology」から転載したもので、著者はYaxue Fansです。この記事を転載する場合は、Java Geek Technology の公開アカウントにお問い合わせください。

序文

まず、分散 ID が必要な理由と、分散 ID を使用して解決する問題について説明します。私たちのプロジェクトがまだモノリシックアーキテクチャだった頃は、データベースの自動増分 ID を使用して、多くのデータ識別の問題を解決できました。しかし、ビジネスが発展するにつれて、私たちのアーキテクチャは徐々に分散アーキテクチャへと進化していきます。現時点では、ビジネスのデータは複数のデータベースに保存される可能性があるため、データの自己増分 ID を使用することはできません。このとき、データを識別するには分散 ID が必要なので、分散 ID 生成サービスが必要になります。では、分散 ID サービスの要件と課題は何でしょうか?

必要とする

グローバルに一意: データを一意に識別するために使用されるため、分散 ID はグローバルに一意であり、同じビジネスのすべてのサービスで一貫している必要があります。これは基本的な要件です。

グローバル増分：増分も分かりやすいです。多くの場合、ID は人が見るためのものであるため、生成された ID が順番に増加していくことを確認する必要があります。増分しない場合は、読みやすさが大幅に低下します。

情報セキュリティ：分散IDのセキュリティも非常に重要です。前述したように、生成された ID は増分的であるため、競合他社が ID 生成の頻度を知ることができる可能性があります。これは電子商取引やその他のシナリオでは大きな問題を引き起こしますが、これは世界的な増加と矛盾することがよくあります。

高可用性: 分散 ID 生成サービスは高可用性を備えている必要があります。結局、ID を生成できなければ、その後のすべてのサービスが使用できなくなります。

一般的な分散ID実装

今日のインターネットでは、ビジネスシナリオとニーズに応じて、分散 ID を実装する方法がいくつかあります。

識別子;
レディス;
変形されたデータベース自動増分 ID。
Twitter スノーフレークアルゴリズム
Meituan の Leaf — Snowflake アルゴリズムのバリエーション。

言語

Java を書く友人は UUID に精通している必要があります。 7dbb9f04-d15e-4c88-b74b-72a35e0d7580 は標準の UUID です。 UUID はグローバルに一意であり、前述の最初の要件を満たしていると言われていますが、明らかにグローバル増分はありません。この分散 ID は読みやすさが悪いです。ログ記録や人間の理解を必要としないシナリオにのみ使用する場合は使用できますが、ここで説明しているビジネスデータの一意の識別には適していません。さらに、この順序付けられていない UUID を主キーとして使用すると、パフォーマンスに重大な影響を及ぼします。

レディス

Redis には incr コマンドがあり、アトミックな増分を保証し、ある程度のグローバル ID を生成できます。ただし、Redis の使用には 2 つの問題があります。

それは美しくありません。グローバル ID が必要ですが、incr コマンドは 1 から始まる整数であるため、グローバル ID の長さが不一致になります。固有のビジネスデータを識別するためにも使用できますが、日付情報が含まれていないため、シナリオによっては読みにくくなります。
Redis の高可用性に依存しますが、Redis はメモリベースであるため、ID が失われないようにするには、Redis を永続化する必要がありますが、Redis の 2 つの永続化方法にはそれぞれ長所と短所があります。詳細は公式アカウントの前回の記事をご参照ください。インタビュアー: Redis ではクラッシュ後にデータが失われないようにどのように保証するのか教えてください。

データベース自動増分ID

先ほど、分散環境内の単一のデータベースでは、各 MySQL インスタンスの自動インクリメント ID が 1 から始まり、ステップサイズが 1 ずつ増加するため、自動インクリメント ID を使用できなくなったことを説明しました。この場合、データベースごとに異なるステップサイズを設定することを検討するのは簡単です。異なるステップサイズを設定すると、各データベースインスタンスが重複することなく ID を生成できるようになります。シンプルなシステムをこのように使用することもできますが、いくつか問題があります。

データベースへの依存。分散環境では、データベースに過度に依存することはリスクがあり、特に 1 秒あたり数十万 QPS の電子商取引トランザクションシナリオでは、高い同時実行性をサポートできません。

異なるデータベースインスタンスのデータは直接リンクできず、データを連結するには追加のストレージが必要になるため、ビジネスの複雑さが増します。

Twitterのスノーフレークアルゴリズム

スノーフレークアルゴリズムは、Twitter のオープンソース分散 ID 生成アルゴリズムです。このアルゴリズムは標準的な考え方を提供します。多くの企業がこのアルゴリズムに基づいて独自の実装を行っています。最も有名なのは美団の葉です。ここでは、スノーフレークアルゴリズムがどのように実装されるかに焦点を当てます。

ご興味がございましたら、https://tech.meituan.com/2017/04/21/mt-leaf.html の記事を参照して、Meituan の leaf の実装原理をご確認ください。

スノーフレークアルゴリズムの考え方は、全体を部分に分割し、分散 ID の生成を各コンピュータールームとマシンに分散させることです。 ID を表すために 64 ビットの long 型構造体が使用されます。 64 ビット構造を以下に示します。最初の符号ビットは 0 で、その後に 41 ビットのタイムスタンプが続き、次の 10 ビットはコンピュータルームとマシン、最後の 12 ビットはシリアル番号です。

上記の構造は、スノーフレークアルゴリズムの基本構造です。各社は自社の事業内容に応じて適宜調整を行っていきます。 32 ビットやその他のビットを使用でき、実際の状況に応じてタイムスタンプのビット数を調整することもできます。 10 ビットの workerID は、コンピュータルームがある企業の場合はコンピュータルームとマシンで構成でき、コンピュータルームがない企業の場合はマシンを直接使用できます。状況に応じてシーケンスビットも適切に調整できます。

簡単な計算ができます。 41 ビットの時間は 2 ^ 41 / (365 * 24 * 3600 * 1000) = 69 年です。各マシンは 1 ミリ秒あたり 2 ^ 12 = 4096 個の ID を生成できます。

つまり、私たちのコードは 69 年間しか実行できないということですか?実はそうではありません。サービスは開始時に初期値を設定します。ここでのタイムスタンプは、マシン時間と初期値の差です。では、SnowFlake アルゴリズムの利点と欠点は何でしょうか?

タイムスタンプがあるため、自己増分の要件を満たし、一定の可読性も備えています。
各サービスは独自のマシン上で一意の ID を直接生成でき、コンピュータルームとマシン番号を構成するだけで済みます。
用途に応じて長さを調整できます。
欠点は、マシンのクロックに依存することです。マシンのクロックに問題がある場合は、生成された ID が繰り返される可能性があり、これを制御する必要があります。

上記の原則を組み合わせることで、Java コードを通じて実装できます。コードは次のとおりです。

パブリッククラスSnowFlakeUtil { 
 
    // 初期タイムスタンプ
    プライベート最終静的long START_TIMESTAMP = 1624796691000L;
    //データセンターが占有するビット数
    プライベート最終静的ロングDATA_CENTER_BIT = 5;
    //マシンIDで使用されるビット数
    プライベート最終静的ロングMACHINE_BIT = 5;
    //シリアル番号の桁数
    プライベート最終静的ロングSEQUENCE_BIT = 12; 
 
 
    /**
     * 各パーツの最大値
     */
    プライベート最終静的ロング MAX_SEQUENCE = ~(-1L << SEQUENCE_BIT);
    プライベート最終静的ロング MAX_MACHINE_NUM = ~(-1L << MACHINE_BIT);
    プライベート最終静的ロング MAX_DATA_CENTER_NUM = ~(-1L << DATA_CENTER_BIT); 
 
    /**
     * 各パーツの左への変位
     */
    プライベート最終静的ロング MACHINE_LEFT = SEQUENCE_BIT;
    プライベート最終静的ロング DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    プライベート最終静的ロング TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT; 
 
    プライベートファイナルロングIDC;
    プライベート最終長いサーバーID;
    プライベートロングシーケンス= 0L;
    プライベートロングlastTimeStamp = -1L; 
 
    プライベートlong getNextMill() {
        ロングミル = System.currentTimeMillis();
        while (ミル <= lastTimeStamp) {
            ミル = System.currentTimeMillis();
        }
リターンミル;
    } 
 
    /**
     * 指定されたデータセンターIDとマシンIDに基づいて指定されたシリアル番号を生成します
     *
     * @param idc データセンター ID
     * @param serverId マシンのロゴ ID
     */
 public SnowFlakeUtil(長いIDC、長いサーバーId) {
        idc > MAX_DATA_CENTER_NUM || idc < 0 の場合 {
            throw new IllegalArgumentException( "IDC データ センター番号が不正です!" );
        }
        if (サーバー ID > MAX_MACHINE_NUM || サーバー ID < 0) {
            throw new IllegalArgumentException( "serverId マシン番号が不正です!" );
        }
        this.idc = idc;
        this.serverId = サーバーID;
    } 
 
    /**
     * 次のIDを生成する
     *
     * @戻る 
     */
パブリック同期された長いgenNextId() {
        long currTimeStamp = System.currentTimeMillis();
        （現在のタイムスタンプが最後のタイムスタンプより小さい場合）
            throw new RuntimeException( "時計が逆方向に動きました。ID の生成を拒否します" );
        }
        （カレントタイムスタンプ == ラストタイムスタンプ）の場合{
            //同じミリ秒で、シリアル番号が自動的に増加します
シーケンス= (シーケンス+ 1) & MAX_SEQUENCE;
            //同じミリ秒内のシーケンスの数が最大値に達しました
            if (シーケンス== 0L ) {
                currTimeStamp = getNextMill();
            }
        }それ以外{
            //異なるミリ秒では、シーケンス番号は0に設定されます
シーケンス= 0L;
        }
        最後のタイムスタンプ = currTimeStamp;
戻り値(currTimeStamp - START_TIMESTAMP) << TIMESTAMP_LEFT | idc << DATA_CENTER_LEFT |サーバーID << MACHINE_LEFT |順序;
    } 
 
公共 静的void main(String[] args) {
        SnowFlakeUtil snowFlake = 新しい SnowFlakeUtil(4, 3);
 ( int i = 0; i < 100; i++)の場合{
            システム。出力.println(snowFlake.genNextId());
        }
    }
 }