大手メーカーの分散ID設計ソリューションをいくつかご紹介します

[[403803]]

この記事はWeChatの公開アカウント「Learning Java from Boring」から転載したもので、著者はBoredです。この記事を転載する場合は、「Learn Java with Wulin」公式アカウントまでご連絡ください。

序文

最近、この会社では上級バックエンド開発者を募集しており、幸運にも私は面接官の一人に選ばれました。最も頻繁に尋ねられた質問の 1 つは、分散 ID に関するいくつかのソリューションに関するものでした。率直に言って、以前の中小企業の開発者で完全な回答をくれた人はほとんどいませんでした。

そこで私は週末に少し時間を取って、主流の分散 ID 生成ソリューションをいくつか整理し、皆さんのお役に立てればと願っています。

いくつかの最初の質問

1. 分散型グローバル一意 ID が必要な理由と、分散型 ID のビジネス要件は何ですか?

複雑な分散システムでは、多くの場合、大量のデータとメッセージを一意に識別する必要があります。

美団点評の金融、支払い、ケータリング、ホテルなどのビジネスシナリオなど
Maoyan Moviesなどの製品のシステム内のデータは日々増加しています。データがデータベースとテーブルに分割された後、データまたはメッセージを表すために一意の ID が必要になります。
注文、ライダー、クーポンなどの特別なアイテムにも、識別子として一意の ID が必要です。

このとき、固有の ID を生成できるシステムが非常に必要になります。

2. ID生成ルールに関する厳格な要件

グローバル一意性: 一意の識別子であるため、グローバル一意性は最も基本的な要件です。
増加傾向: MySQL の InnoDB エンジンではクラスター化インデックスが使用されています。ほとんどの RDBMS はインデックスデータを格納するために Btree データ構造を使用するため、主キーを選択するときは、書き込みパフォーマンスを確保するために順序付けられた主キーを使用するようにしてください。
単調増加: トランザクションバージョン番号、IM 増分メッセージ、ソート、その他の特別な要件など、次の ID が前の ID よりも大きいことを確認します。
情報セキュリティ: ID が連続している場合、悪意のあるユーザーがそれをスクレイピングすることは非常に簡単です。指定された URL を順番にダウンロードするだけです。注文番号の場合は、競合他社が当社の毎日の注文量を知ることができるため、さらに危険です。したがって、一部のアプリケーションシナリオでは、競合他社が推測しにくくするために、ID を不規則にする必要があります。
タイムスタンプ付き: これにより、開発中にこの分散 ID の生成時刻をすばやく把握できます。

3. ID生成システムの可用性要件

高可用性: 分散 ID を取得するためのリクエストを送信する場合、サーバーは 99.999% のケースで一意の分散 ID が作成されるようにする必要があります。
低レイテンシ: 分散IDを取得するためのリクエストを送信するには、サーバーが高速でなければならず、非常に高速でなければなりません。
高い QPS: 100,000 個の分散 ID 作成リクエストが同時に送信された場合、サーバーは 100,000 個の分散 ID に耐え、正常に作成できる必要があります。

いくつかの一般的な解決策

システムアーキテクチャとビジネスの進化に伴い、分散 ID 生成のためのソリューションが数多く存在します。いくつか簡単なものを挙げます。

1. UUID

この解決策は誰もがよく知っていると思いますが、最も単純なものです。

公共 静的void main(String[] args) {
    文字列 uuid = UUID.randomUUID().toString();
    System.out.println (uuid) ;
 }

一意性だけを考慮すると、UUID は基本的にニーズを満たすことができます。

欠点

無秩序: 生成される順序を予測できず、増加する順序付き数字を生成することは不可能です。
主キー: ID を主キーとして使用すると、特定の環境で問題が発生します。たとえば、UUID は DB の主キーとして使用するには適していません。 MySQL では主キーをできるだけ短くすることが公式に推奨されており、36 ビットの UUID はこの要件を満たしていません。
インデックス: これにより、B+ ツリーインデックスが分割されます。

2. データベースの自動増分主キー

このソリューションには一定の制限があり、高同時実行クラスターでは使用できません。

3. Redisに基づくグローバルID戦略の生成

Redis はシングルスレッドであり、本質的にアトミック性を保証しているため、INCR と INCRBY を使用してこれを実現できます。
クラスター分布

Redis クラスターでは、MySQL と同様に異なる成長ステップを設定する必要があり、キーには有効期間が必要です。より高いスループットを得るには、Redis クラスターを使用できます。クラスター内に 5 つの Redis がある場合、各 Redis の初期化ステップは 1、2、3、4、5 となり、ステップの長さはすべて 5 になります。

4. スノーフレーク

Twitter のスノーフレークアルゴリズムは、タイムリーかつ秩序正しく ID を生成します。
スノーフレークアルゴリズムによって生成された ID の結果は、64 ビットの整数で、Long 型です (文字列に変換した後の最大長は 19 です)。
分散システムでは ID の衝突が発生せず (datecenter と workerId で区別)、効率が高くなります。

構造

スノーフレークアルゴリズムのいくつかのコアコンポーネントを以下に示します。

数値セグメント分析

1 ビットの符号ビット: バイナリの最上位ビットは符号ビットであり、1 は負の数、0 は正の数を表し、生成される ID は通常正の数であるため、最上位ビットは 0 に固定されるため、不要です。
41 ビットのタイムスタンプ。タイムスタンプをミリ秒レベルで記録するために使用されます。
- 41ビットは2^41 - 1の数値を表現できる
- 正の整数を表すためだけに使う場合（コンピュータの正の数には 0 も含まれる）、表せる値の範囲は 0～2^41 - 1 です。マイナス 1 の理由は、表せる値の範囲が 1 ではなく 0 から始まるからです。
- つまり、41 ビットは 2^41 - 1 ミリ秒の値を表すことができ、これは年単位に換算すると 69 年になります。
10ビットの作業プロセスビット。作業機械IDを記録するために使用します。
- 5桁のデータセンターIDと5桁のワーカーIDを含む2^10 = 1024ノードにデプロイ可能
- 5ビットで表現できる最大の整数は2^5 - 1 = 31です。つまり、0、1、2...31の32の数字を使用して、異なるデータセンターIDとワーカーIDを表すことができます。
12ビットのシリアル番号、シリアル番号、同じミリ秒内に生成された異なるIDを記録するために使用される
- 12 ビットで表現できる最大の正の整数は 2^12 - 1 = 4095 です。つまり、0、1...4094 の 4095 個の数値を表現できることになります。
- 同じマシンで同じタイムスタンプ（ミリ秒）で生成された 4095 個の ID 番号を示します。

アドバンテージ

生成されたすべてのIDは時間とともに増加します
datacenterId と workerId によって区別されるため、ディストリビューション全体で重複する ID は存在しません。
ミリ秒は高いレベルにあり、自動インクリメントシーケンスは低いレベルにあり、ID 全体が増加傾向にあります。
データベースや Redis などのサードパーティのシステムに依存せず、サービスとして展開されます。 ID 生成において、より高い安定性と非常に高いパフォーマンスを備えています。
自社の業務に合わせてビットを割り当てることができるため、非常に柔軟です。

欠点

マシンクロックに依存します。マシンクロックが逆行すると、重複した ID が生成されます。
単一のマシン上では増分ですが、分散環境の設計上、各マシンのクロックを完全に同期することはできず、クロックがグローバルに増加しない場合があります。 (この欠点はロックと見なすことができます。一般に、分散 ID では増加傾向のみが求められ、増加傾向は厳密には求められません。要件の 90% では増加傾向のみが求められます。)

ソースコード

/**
 * Twitter の Snowflake アルゴリズム-- Java 実装 
 *
 * @author より
 * @日付2016/11/26
 */
パブリッククラスSnowFlake { 
 
    /**
     * 開始タイムスタンプ
     */
    プライベート最終静的ロングSTART_STMP = 1480166465631L; 
 
    /**
     * 各部分が占めるビット数
     */
    プライベート最終静的ロングSEQUENCE_BIT = 12; //シーケンス番号が占める桁数
    プライベート最終静的ロングMACHINE_BIT = 5; //マシンIDで使用されるビット数
    プライベート最終静的ロングDATACENTER_BIT = 5; //データセンターが占有するビット数
 
    /**
     * 各パーツの最大値
     */
    プライベート最終静的ロング MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
    プライベート最終静的ロング MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    プライベート最終静的ロング MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT); 
 
    /**
     * 各パーツの左への変位
     */
    プライベート最終静的ロング MACHINE_LEFT = SEQUENCE_BIT;
    プライベート最終静的ロング DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    プライベート最終静的ロング TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT; 
 
    プライベート長いデータセンターID; //データセンター
    プライベートロングマシンID; //マシンID
    プライベートロングシーケンス= 0L; //シリアルナンバー
    プライベートロングlastStmp = -1L; //最後のタイムスタンプ
 
パブリックSnowFlake(longデータセンターID、longマシンID) {
        データセンターID > MAX_DATACENTER_NUM || データセンターID < 0 の場合 {
            throw new IllegalArgumentException( "datacenterId は MAX_DATACENTER_NUM より大きく、0 より小さくすることはできません" );
        }
        マシンID > MAX_MACHINE_NUM || マシンID < 0 の場合 {
            throw new IllegalArgumentException( "machineId は MAX_MACHINE_NUM より大きく、0 より小さくすることはできません" );
        }
        this.datacenterId = データセンターId;
        this.machineId = マシンID;
    } 
 
    /**
     * 次のIDを生成する
     *
     * @戻る 
     */
パブリック同期された長いnextId（）{
        長いcurrStmp = getNewstmp();
        （現在のスタンプ<最後のスタンプ）の場合{
            throw new RuntimeException( "時計が逆方向に動きました。ID の生成を拒否します" );
        } 
 
        （現在のスタンプ == 最後のスタンプ）の場合{
            //同じミリ秒で、シリアル番号が自動的に増加します
シーケンス= (シーケンス+ 1) & MAX_SEQUENCE;
            //同じミリ秒内のシーケンスの数が最大値に達しました
            if (シーケンス== 0L ) {
                currStmp = getNextMill();
            }
        }それ以外{
            //異なるミリ秒では、シーケンス番号は0に設定されます
シーケンス= 0L;
        } 
 
        最後のStmp = currStmp; 
 
 return (currStmp - START_STMP) << TIMESTMP_LEFT //タイムスタンプ部分
                | datacenterId << DATACENTER_LEFT //データセンター部分
                | machineId << MACHINE_LEFT //マシン識別部分
                |順序; //シーケンス番号部分
    } 
 
    プライベートlong getNextMill() {
        ロングミル = getNewstmp();
        while (ミル <= lastStmp) {
            ミル = getNewstmp();
        }
リターンミル;
    } 
 
    プライベートlong getNewstmp() {
 System.currentTimeMillis()を返します。
    } 
 
公共 静的void main(String[] args) {
        スノーフレーク snowFlake = new SnowFlake(2, 3); 
 
 ( int i = 0; i < (1 << 12); i++) {
            システム。出力.println(snowFlake.nextId());
        } 
 
    }
 }

テスト

//スノーフレークアルゴリズムを使用してIDを生成するテスト
// コンストラクタにデータセンターIDとワーカーIDを渡す
スノーフレーク snowFlake = new SnowFlake(1,1);
 ( int i = 0; i < 10; i++) {
    長いID = snowFlake.nextId();
    システム。出力.println( "id:" + id + "\t" + String.valueOf(id).length() + "bit" );
    システム。出力.println( "-------------------------------------------" );
 }

Spring Boot がスノーフレークアルゴリズムを統合

次のように hutool-all と Maven 依存関係をインポートします。

 <依存関係>
    <依存関係>
        <groupId>cn.hutool</groupId>
        <artifactId>hutool-すべて</artifactId>
        <バージョン>5.4.2</バージョン>
    </依存関係>
    <依存関係>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-web</artifactId>
        <バージョン>2.2.1.RELEASE</バージョン>
    </依存関係>
    <依存関係>
        <groupId>org.projectlombok</groupId>
        <artifactId>ロンボク</artifactId>
        <バージョン>1.18.16</バージョン>
    </依存関係>
 </依存関係>

SnowFlake構成クラスを作成する

@構成
パブリッククラスSnowFlakeConfig {
    @Value( "${application.datacenterId}" )
    プライベート Long データセンター ID;
    @Value( "${application.workerId}" )
    プライベート Long ワーカー ID; 
 
    /***
     * スノーフレークIDを生成するオブジェクトを挿入する
     * @戻る 
     */
    @ビーン
パブリックスノーフレークスノーフレーク() {
新しいSnowflake(workerId,datacenterId)を返します。
    }
 }

yml 構成ファイル:

応用：
  データセンターID: 2
  ワーカーID: 1
サーバ：
  ポート: 7777

サービス層:

 @サービス
パブリッククラスOrderService {
    オートワイヤード
    プライベート スノーフレーク スノーフレーク; 
 
パブリック文字列 getIdBySnowFlake() {
 String.valueOf(snowflake.nextId())を返します。
    }
 }