フレームワーク: 分散グローバルユニークID

[[407823]]

この記事はWeChatの公開アカウント「Sneak Forward」から転載したもので、著者はcscwです。この記事を転載する場合は、Qianxingqianxing の公開アカウントにご連絡ください。

序文

HTTP リクエストが行われ、データベーストランザクションが実行されるたびに、コード実行を追跡するときに、これらのビジネス操作に関連付ける一意の値が必要になります。スタンドアロンシステムの場合、データベースの自動増分 ID またはタイムスタンプとローカルに増分された値を使用することで、一意の値を実現できます。しかし、分散システムでは、どうすれば一意の ID を実現できるのでしょうか?

分散IDの特徴
データベース自動増分ID
Redis 分散 ID
Zookeeper 分散 ID
グローバルに一意なUUIDの利点と欠点
Twitterのスノーフレークアルゴリズムは分散IDを生成する

分散IDの特徴

世界的な独自性、必要性
冪等性: 特定の情報に基づいて生成される場合、冪等性が保証される必要がある
セキュリティに注意してください。ID には推測できない情報が隠されており、推測することはできません。 IDを生成する方法
トレンド増分、クエリと比較すると、ビジネスオペレーションの時系列を判断できます

データベース自動増分ID

実装はシンプルで、ID は単調増加し、数値型のクエリ速度は高速ですが、シングルポイント DB ではダウンタイムのリスクがあり、高同時実行シナリオに耐えられません。

作成する テーブルFLIGHT_ORDER (
    id int (11) 符号なしNOT   NULL auto_increment、#自動インクリメント ID
主要な キー（ID）、
 )ENGINE=innodb;

クラスター内のデータベースIDの一意性を確保する方法

事業が発展するにつれて、サービスは複数の大規模なクラスターに拡張されます。単一ポイントデータベースの圧迫を解決するために、データベースもそれに応じてクラスター化されます。クラスター内のデータベース ID の一意性を確保するにはどうすればよいですか?
各データベースインスタンスは、開始値と増加ステップサイズを設定します。

デメリット: その後の拡張には役立ちません。後で拡張が必要になった場合は、開始値と成長ステップを変更するために手動で介入する必要があります。

Redis 分散 ID

システムに数十億のデータがある場合、データベースの自動増分 ID に依存してテーブルとデータベースをシャーディングした後、各データベースインスタンスを手動で変更する必要がありますが、スケーラビリティと保守性が低下します。

Redis INCRコマンドに基づいて分散グローバル一意IDを生成する

サービスは Redis から ID を取得し、ID はデータベースから分離されるため、ID とサブテーブルおよびサブデータベースの問題を解決できます。さらに、Redis はデータベースよりも高速であり、クラスターサービスが ID を同時に取得するニーズをサポートできます。
redis の INCR コマンドには、INCR AND GET というアトミック操作があります。 redisはシングルプロセス、シングルスレッドのアーキテクチャであり、INCRコマンドはIDの重複を引き起こしません。

オートワイヤード
プライベート StringRedisTemplate stringRedisTemplate;
プライベート静的最終文字列 ID_KEY = "id_good_order" ;
パブリックLong incrementId() {
 stringRedisTemplate.opsForValue().increment(ID_KEY)を返します。
 }

HINCRBY コマンド

実際、シリアル番号に関するより関連性の高い情報を保存するには、Redis のハッシュデータ構造を使用できます。 Redis は、ハッシュに「INCR AND GET」アトミック操作を実装するための HINCRBY コマンドも提供します。

 //KEY_NAMEはハッシュ構造に対応するキー、FIELD_NAMEはハッシュ構造のフィールド、INCR_BY_NUMBERは増分値です
redis 127.0.0.1:6379> HINCRBY キー名 フィールド名 INCR_BY_NUMBER

ダウンタイムのシリアル番号回復の問題

Redis はインメモリデータベースです。 RDB または AOF の永続性が有効になっていない場合、クラッシュが発生すると ID データが失われます。 RDB 永続性が有効になっている場合でも、最新のスナップショットと最新の HINCRBY コマンドの間に時間差がある場合があり、ダウンタイム後に RDB スナップショットを介してデータセットを復元すると、重複した ID 値が発生する可能性があります。
Redis ダウンタイムシーケンス番号回復ソリューション
- リレーショナルデータベースを使用して、短時間で使用可能な最大シーケンス番号 MAX_ID を記録します。 redis から ID を取得する場合、MAX_ID 未満のシーケンス番号のみが取得されます。
- 最大値を計算するには、ID消費率RATEを定期的に計算し、redisに保存するスケジュールされたタスクが必要です。クライアントは、CUR_ID、RATE、MAX_ID を取得すると、ID 消費率 RATE に基づいて CUR_ID が MAX_ID に近いかどうかを計算します。そうであれば、データベース内の MAX_ID を更新します。

Zookeeper 分散 ID

Zookeeper の永続的な順序付きノードを使用することで、自己増分分散 ID を実装できます。 Zookeeper は可用性の高いクラスターサービスであり、正常に送信されたメッセージは永続的であるため、マシンのダウンタイムや単一マシンの問題を心配する必要はありません。

 <依存関係>
    <グループ ID>org.apache.curator</グループ ID>
    <artifactId>キュレーターフレームワーク</artifactId>
    <バージョン>4.2.0</バージョン>
 </依存関係>
 <依存関係>
    <グループ ID>org.apache.curator</グループ ID>
    <artifactId>キュレーターレシピ</artifactId>
    <バージョン>4.2.0</バージョン>
 </依存関係>

再試行ポリシー retryPolicy = 新しい ExponentialBackoffRetry(500, 3);
 CuratorFramework クライアント = CuratorFrameworkFactory.builder()
      .connectString( "localhost:2181" )
      .接続タイムアウトMs(5000)
      .セッションタイムアウトMs(5000)
      .retryPolicy(再試行ポリシー)
      。建てる（）;
クライアントを起動します。
文字列sequenceName = "root/sequence/distributedId" ;
分散アトミックロング distAtomicLong = 新しい分散アトミックロング(クライアント、シーケンス名、再試行ポリシー);
 //DistributedAtomicLongを使用して自動インクリメントシーケンスを生成する
パブリックLongシーケンス() は例外をスローします {
    AtomicValue<Long>シーケンス= this.distAtomicLong.increment();
    if (シーケンス.succeeded()) {
戻る シーケンス.postValue();
    }それ以外{
戻る ヌル;
    }
 }

UUIDの利点と欠点

データベース、Redis、Zookeeper に基づく分散 ID はすべて、外部サービスに大きく依存しています。いくつかのシナリオでは、これらの外部サービスが存在しない場合に分散 ID を生成するにはどうすればよいでしょうか?
JDK には、グローバルに一意の ID ジェネレーターが付属しています。これは UUID ですが、意味のない文字列であり、ストレージパフォーマンスが低く、クエリに時間がかかります。注文システムの固有IDとしては適していません。一般的な最適化ソリューションは、「保存用に 2 つの uint64 整数に変換する」か、「半分に保存する」ことです (半分にした後は一意性が保証されません)
ただし、ログ記録システムの場合、またはデータ内のシリアル番号を一意に識別できる属性を関連付ける場合は、UUID を使用できます。

文字列 uuid = UUID.randomUUID().toString().replaceAll( "-" , "" );

Twitterのスノーフレークアルゴリズムは分散IDを生成する

UUIDと同様に、スノーフレークアルゴリズムは外部サービスに依存しません。
スノーフレークアルゴリズムは、Twitter社内の分散プロジェクトで使用されているID生成アルゴリズムであり、国内企業から高く評価されています。サードパーティのサービスに依存せず、高い効率性

Snowflake ID 構造は、正の数字 (1 ビット) + タイムスタンプ (41 ビット) + マシン ID (5 ビット) + データセンター (5 ビット) + 自動増分値 (12 ビット) の合計 64 ビットの Long 型で構成されます。

1: 最初のビット (1 ビット): Java の long の最上位ビットは符号ビットであり、正または負を表します。正の数は 0、負の数は 1 です。通常、生成される ID は正の数なので、デフォルト値は 0 です。

2: タイムスタンプ部分（41ビット）：ミリ秒レベルの時間。現在のタイムスタンプを保存することはお勧めしません。代わりに、(現在のタイムスタンプ - 固定開始タイムスタンプ) の差を使用して、生成される ID が小さい値から開始されるようにします。

3: 作業マシン ID (10 ビット): workId とも呼ばれ、コンピュータルームまたはマシン番号の組み合わせで柔軟に構成できます。

4: シーケンス番号部分（12ビット）、自己増分サポート同じノードから同じミリ秒内に4096個のIDを生成可能

//TwitterのSnowFlakeアルゴリズム、SnowFlakeアルゴリズムを使用して整数を生成する
パブリッククラスSnowFlakeShortUrl {
    //開始タイムスタンプ
静的long START_TIMESTAMP = 1624698370256L;
    //各部分が占めるビット数
静的ロングSEQUENCE_BIT = 12; //シーケンス番号が占めるビット数
静的ロングMACHINE_BIT = 5; //マシンIDが占めるビット数
静的ロングDATA_CENTER_BIT = 5; //データセンターが占有するビット数
    //各パーツの最大値
静的ロング MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
静的ロング MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
静的ロング MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT);
    //各パーツを左にずらす
静的long MACHINE_LEFT = SEQUENCE_BIT;
静的long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
静的long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;
    //dataCenterId + machineId は 10 ビットの作業マシン ID に等しい
    プライベート長いデータセンターID; //データセンター
    プライベートロングマシンID; //マシンID
    プライベート揮発性ロングシーケンス= 0L; //シリアルナンバー
    プライベート volatile long lastTimeStamp = -1L; //最後のタイムスタンプ
    プライベート volatile long l currTimeStamp = -1L; //現在のタイムスタンプ
     
    プライベートlong getNextMill() {
        ロングミル = System.currentTimeMillis();
        mill <= lastTimeStamp の場合、 mill = System.currentTimeMillis();
リターンミル;
    }
    //指定されたデータセンターIDとマシンIDに基づいて指定されたシリアル番号を生成します
パブリックSnowFlakeShortUrl(longデータセンターId、longマシンId) {
        Assert.isTrue(dataCenterId >=0 && dataCenterId <= MAX_DATA_CENTER_NUM, "dataCenterId が不正です!" );
        Assert.isTrue(machineId >= 0 || machineId <= MAX_MACHINE_NUM, "machineId が不正です!" );
        this.dataCenterId = データセンターId;
        this.machineId = マシンID;
    }
    //次のIDを生成する
パブリック同期された長いnextId（）{
        currTimeStamp = System.currentTimeMillis();
        Assert.isTrue(currTimeStamp >= lastTimeStamp, "時計が逆方向に動きました" );
        （カレントタイムスタンプ == ラストタイムスタンプ）の場合{
            //同じミリ秒で、シリアル番号が自動的に増加します
シーケンス= (シーケンス+ 1) & MAX_SEQUENCE;
            if ( sequence == 0L) { // 同じミリ秒内のシーケンスの数が最大値に達した場合は、次のミリ秒を取得します
                currTimeStamp = getNextMill();
            }
        }それ以外{
シーケンス= 0L; //異なるミリ秒では、シーケンス番号は0に設定されます
        }
        最後のタイムスタンプ = currTimeStamp;
 return (currTimeStamp - START_TIMESTAMP) << TIMESTAMP_LEFT //タイムスタンプ部分
                | dataCenterId << DATA_CENTER_LEFT //データセンター部分
                | machineId << MACHINE_LEFT //マシン識別部分
                |順序; //シーケンス番号部分
    } 
     
公共 静的void main(String[] args) {
        SnowFlakeShortUrl snowFlake = 新しい SnowFlakeShortUrl(10, 4);
 ( int i = 0; i < (1 << 12); i++) {
            //10進数
            システム。出力.println(snowFlake.nextId());
        }
    }
 }