シンプルなID生成戦略: MySQLテーブルからグローバルに一意のIDを生成する実装

グローバル ID を生成する方法は多数あります。ここでは簡単な解決策を紹介します。MySQL の自動増分 ID を使用して、グローバルに一意の ID を生成します。

1. 2 つのフィールドのみを必要とするテーブルを作成します。

テーブル `guid` を作成します (
 `id` bigint(20) 符号なし NOT NULL AUTO_INCREMENT,
 `stub` char(1) NOT NULL DEFAULT '' COMMENT 'ピットを占有するために使用されるスタブフィールド',
 主キー (`id`)、
 UNIQUE KEY `uk_stub` (`stub`) -- スタブを一意のインデックスとして設定します) ENGINE=MyISAM AUTO_INCREMENT=1000000000 DEFAULT CHARSET=utf8;

自動増分開始値を指定します: alter table guid auto_increment=1000000000。これにより、ID が 10 桁になることが保証されます (11 桁に増やすことはほとんど不可能です)。

2. Mybatis マッパーを定義します。

@マッパー
パブリックインターフェースGuidMapper{


 //グローバルに一意のIDを取得する
  * @戻る
  */
 // afs_guid(stub) に置き換えます values('a');
 // last_insert_id() を選択します。
 @Insert("guid (stub) VALUES('a') に置き換える")
 @SelectKey(ステートメント = {"SELECT LAST_INSERT_ID()"}、keyProperty = "guidHolder.id"、before = false、resultType = long.class)
 int getGuid( @Param("guidHolder") GuidHolder guidHolder);

 @データ
 パブリック静的クラス GuidHolder{
  プライベートロングID;
  プライベート文字列スタブ;
 }

3. テスト

 GuidMapper.GuidHolder guidHolder = 新しい GuidMapper.GuidHolder();
 guidMapper の GUID を取得します。
 長い guid = guidHolder.getId();
 // guidは返されるIDです

しっぽ

並行性の安全性の問題

REPLACE INTO は INSERT に似ており、安全です。まず、主キーまたは一意キーが重複していないかどうかを確認します。重複している場合は、元のキーを削除し、新しいキーを追加して元のキーを置き換えます。

SELECT LAST_INSERT_ID() は MySQL 接続にバインドされています。現在の接続では、この操作によって auto_increment 値の変更がトリガーされ、新しい値が取得されます。この値は現在の接続にのみ表示されます。他の接続は、auto_increment が変更された後にのみ値を取得します。

上記の 2 つの点により、同時実行の安全性が確保されます。

また、id の値を手動で減らした場合でも、次の replace into 以降は前回の自動増分に基づいて増加し続けます。これは、id の値を手動で変更しても auto_increment の値は変更されないためです。

補足知識:高同時実行クラスタで分散された一意のグローバル ID を確実に生成する方法

序文

システムの一意の ID は、システムを設計するときによく遭遇する問題であり、私たちはこの問題に苦労することがよくあります。

この記事は、分散型の一意のグローバル ID 生成ソリューションを生成するためのアイデアを提供することを目的としており、皆様のお役に立てば幸いです。

欠点があれば遠慮なく指摘してください！ ！

質問

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

複雑な分散システムでは、Meituan Dianpingの金融、支払い、ケータリング、ホテルなどのシステムでは、大量のデータとメッセージを一意に識別する必要があることがよくあります。

Maoyan Moviesなどの製品システム内のデータは徐々に増加しています。データベースが異なるテーブルに分割された後、データまたは情報を識別するために一意のIDが必要になります。

特に、イアンの注文、ライダー、クーポンはすべて一意の ID で識別する必要があります。

現時点では、グローバルにユニークなIDを生成できるシステムが非常に必要である。

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

世界的にユニーク

増加傾向

クラスター化インデックスは、MySQL InnoDB エンジンで使用されます。ほとんどの RDBMS はインデックスの保存に Btree データ構造を使用するため、主キーを選択するときは、書き込みパフォーマンスを確保するために順序付けされた主キーを使用するようにしてください。

単調増加

トランザクションバージョン番号、IM増分メッセージ、ソート、その他の特別な要件など、次のIDが前のIDよりも大きいことを確認します。

情報セキュリティ

ID が連続している場合、悪意のあるユーザーが URL を連続してクロールしやすくなります。注文番号の場合は、競合他社が当社の毎日の注文量を直接知ることができるため危険です。したがって、一部のアプリケーション シナリオでは、競合他社が推測しにくいように ID を不規則にする必要があります。

タイムスタンプ付き

開発中にこの分散IDがいつ生成されたかすぐに理解することもできます

ID番号生成システムの可用性要件

高可用性

分散 ID を取得するリクエストを発行すると、サーバーは 99.999% のケースで一意の分散 ID を作成することを保証します。

低遅延

分散IDを取得するためにリクエストを送信するには、サーバーは高速でなければなりません。非常に高速である必要があります。

高いQPS

たとえば、100,000 個の分散 ID 作成リクエストが同時に来た場合、サーバーはそれを処理し、100,000 個の分散 ID を一度に正常に作成できる必要があります。

一般的な普遍的な解決策

言語

UUID.randomUUID() は、UUID の標準形式であり、ハイフンで 5 つのセグメントに分割された 32 桁の 16 進数、8-4-4-4-12 形式の 36 文字で構成され、パフォーマンスが非常に高く、ローカルで生成され、ネットワークを消費しません。

問題

UUIDが順序付けられていないため、データベースアクセスのパフォーマンスが低下する

順序がないので、生成順序を予測できず、増加する順序付き数字を生成することはできない。

まず、分散IDは一般的に徐々に使用されていますが、MySQLの公式推奨事項によると、主キーは可能な限り短くする必要があります。各UUIDは非常に長いため、推奨されません。

主キー: ID を主キーとして使用すると、特定の環境で問題が発生します。

たとえば、UUID は DB の主キーとして使用するには適していません。MySQL には明確な説明があります。

インデックス、B+ツリーインデックス分割

分散 ID は主キーであり、主キーにはインデックスが含まれており、MySQL インデックスは B+ ツリーを通じて実装されているため、新しい UUID データが挿入されるたびに、インデックスの基礎となる B+ ツリーが変更され、クエリが最適化されます。UUID データは順序付けされていないため、UUID データを挿入するたびに主キーの B+ ツリーに大きな変更が加えられ、非常に悪影響があります。挿入は完全に順序付けされていないため、一部の中間ノードが分割されるだけでなく、多くの飽和していないノードが無駄に作成され、データベース挿入のパフォーマンスが大幅に低下します。

UUID はグローバルな一意性のみを保証できますが、増加または単調増加の傾向を満たしません。

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

単一マシン

分散システムでは、データベースの自動増分 ID メカニズムの主な原理は、データベースの自動増分 ID と MySQL データベースの replace into によって実装されます。ここでの replace into は insert 関数に似ていますが、replace into は最初にデータ リストに挿入しようとする点が異なります。このデータ行がテーブルに既に存在することが判明した場合 (主キーまたは一意のインデックスに基づく)、最初に削除されてから挿入されます。それ以外の場合は、新しいデータが直接挿入されます。

REPLACE INTO はレコードを挿入することを意味します。テーブル内の一意のインデックスの値が競合する場合は、古いデータが置き換えられます。

t_test(stub) の値('b') に置き換えます。

LAST_INSERT_ID() を選択します。

挿入するたびに元のデータが置き換えられ、IDが増加します。

これは満足だ

増分

単調性

ユニークさ

同時実行性が低い分散状況では、このソリューションを使用してグローバルに一意の ID を取得できます。

クラスター 分散クラスター

データベースの自己増分 ID メカニズムは分散 ID に適していますか?回答は適切ではありません

システムを水平方向に拡張することは困難です。たとえば、ステップ サイズとマシンの数を定義した後、マシンを追加する必要がある場合はどうすればよいですか? 1、2、3、4、5 (ステップ サイズは 1) の番号が付けられたマシンがあり、1 台のマシンの容量を拡張する必要がある場合、これを行うことができます。2 台目のマシンの初期値を 1 台目よりもはるかに高く設定します。問題ないように見えますが、オンラインのマシンが 100 台ある場合、この時点で容量を拡張する方法は悪夢です。そのため、システムの水平拡張計画は複雑で、実装が困難です。

データベースの負荷は依然として非常に高く、ID を取得するたびにデータベースの読み取りと書き込みを行う必要があるため、パフォーマンスに大きく影響し、分散 ID の低レイテンシと高 QPS のルールを満たしていません (同時実行性が高い場合、データベースから ID を取得すると、パフォーマンスに大きく影響します)。

Redis に基づくグローバル ID 戦略を生成する

スタンドアロン版

Redisはシングルスレッドなので、アトミック性は本質的に保証されており、アトミック操作INCRとINCRBYを使用して実現できます。

INCRBY: 成長ステップのサイズを設定する

クラスター分布

注: Redis クラスターの場合、MySQL と同様に異なる成長ステップを設定する必要があり、キーに有効期間を設定する必要があります。Redis クラスターを使用すると、より高いスループットを得ることができます。

クラスター内に 5 つの Redis サーバーがあると仮定します。各 Redis サーバーの値をそれぞれ 1、2、3、4、5 に初期化し、ステップ サイズを 5 に設定できます。

各 Redis によって生成される ID は次のとおりです。

答え: 1 6 11 16 21

バ: 2 7 12 17 22

3 8 13 18 23 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 30 31 32 33 34 35 36 38 40 41 42 43 44 45 46 47 50 52 53 54 55

4 9 14 19 2 ...19 24 24 19 24 24 19 24 14 14 19 24 19 24 14 19 24 19 24 19 24 19 24 19 24

E: 5 10 15 20 25

しかし、問題は、Redis クラスターのメンテナンスと構成がかなり面倒だということです。単一障害点が必要なため、センチネル

しかし、主な問題は、ID の場合、Redis クラスター全体を導入する必要があることです。これはやり過ぎのように思われます。

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

何ですか

Twitterの分散型自動増分IDアルゴリズム「Snowflake」

Twitter は当初、ストレージシステムを MySQL から Cassandra (Facebook が開発したオープンソースの分散型 NoSQL データベース システム) に移行しました。Cassandra にはシーケンシャル ID 生成メカニズムがなかったため、このようなグローバルに一意な ID 生成サービスを開発しました。

Twitter の分散スノーフレーク アルゴリズム SnowFlake は、1 秒あたり 260,000 個の自動増分ソート可能 ID を生成できます。

TwitterのSnowFlakeは時系列順にIDを生成する

SnowFlake アルゴリズムによって生成された ID の結果は、64 ビットの整数で、Long 型です (文字列に変換した後の最大長は 19 です)。

分散システム（データセンターとワーカーIDで区別）ではIDの衝突が発生せず、効率が高くなります。

分散システムでは、グローバルに一意の ID が必要となるシナリオがいくつかあります。ID を生成するための基本的な要件は次のとおりです。

分散環境では、グローバルな一意性が求められる

通常、データベースには一意の ID が存在し、InnoDB の特性として主キー インデックス上のリーフ ノードにコンテンツを格納するため、左から右に増加するため、単調増加である必要があります。したがって、データベースのパフォーマンスを考慮すると、一般的に単調増加する ID を生成するのが最適です。 ID の競合を防ぐために 36 ビット UUID を使用できますが、UUID にはいくつかの欠点があります。まず、UUID は比較的長く、次に、UUID は一般に順序付けられていません。

注文番号として一意の ID を使用する場合は、他のユーザーが 1 日あたりの注文数を知ることができないようにするためにこのルールが必要になるため、ルールが不要な場合もあります。

構造

スノーフレークアルゴリズムのいくつかのコアコンポーネント

Java では、64 ビット証明書は long 型であるため、SnowFlake アルゴリズムによって生成された ID は long クラスに格納されます。

パート1

2 進数の最上位ビットは符号ビットで、1 は負の数を表し、0 は正の数を表します。生成される ID は通常整数なので、最上位ビットは 0 に固定されます。

パート2

2 番目の部分は 41 ビットのタイムスタンプ ビットで、タイムスタンプをミリ秒単位で記録するために使用されます。

41ビットは2^41 -1の数値を表現できる

正の整数を表すためにのみ使用される場合、表すことができる範囲は 0 - 2^41 -1 です。マイナス 1 の理由は、表すことができる値の範囲が 1 ではなく 0 から始まるためです。

つまり、41 ビットは 2^41 - 1 ミリ秒の値を表すことができ、これは年単位に換算すると 69.73 年になります。

パート3

3番目の部分は作業機械IDで、10ビットは作業機械IDを記録するために使用されます。

5 桁の datacenterId (データセンター、コンピュータ ルーム) と 5 桁の workerID (マシン コード) を含む 2^10 = 1024 ノードに展開できます。

5 ビットで表すことができる最大の正の整数は 2^5 = 31 個であり、さまざまなデータ センターやマシン コードを表すことができます。

パート4

12 ビットで表すことができる正の整数は 2^12 = 4095 です。つまり、0 1 2 … 4094 を使用して、同じマシンと同じタイムスタンプで生成された 4095 個の ID 番号を表すことができます。

SnowFlakeは保証します

生成されたすべてのIDは時間とともに増加します

datacenterId と workerId を使用して区別するため、分散システム全体で重複する ID は発生しません。

成し遂げる

スノーフレークアルゴリズムはScalaで書かれており、Javaで実装する人もいます。githubのアドレスは

/**
 * Twitter の Snowflake アルゴリズム -- Java 実装 * 
 * @author より
 * @日付 2016/11/26
 */
パブリッククラスSnowFlake {

 /**
  * 開始タイムスタンプ */
 プライベート最終静的ロングSTART_STMP = 1480166465631L;

 /**
  * 各部分が占めるビット数*/
 private final static long SEQUENCE_BIT = 12; //シリアル番号が占める桁数 private final static long MACHINE_BIT = 5; //マシン識別子が占める桁数 private final static long 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;

 private long datacenterId; //データセンターprivate long machineId; //マシンIDprivate long sequence = 0L; //シリアル番号private long lastStmp = -1L; //最終タイムスタンプpublic SnowFlake(long datacenterId, long machineId) {
  データセンター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 の生成を拒否します");
  }

  （現在のスタンプ == 最後のスタンプ）の場合{
   //同じミリ秒内に、シーケンス番号が自動的に増加します。sequence = (sequence + 1) & MAX_SEQUENCE;
   // 同じミリ秒内のシーケンスの数が最大値に達した if (sequence == 0L) {
    currStmp = getNextMill();
   }
  } それ以外 {
   //異なるミリ秒では、シーケンス番号は0に設定されます
   シーケンス = 0L;
  }

  最後のStmp = currStmp;

  return (currStmp - START_STMP) << TIMESTMP_LEFT //タイムスタンプ部分 | datacenterId << DATACENTER_LEFT //データセンター部分 | machineId << MACHINE_LEFT //マシンID部分 | sequence; //シリアル番号部分}

 プライベートlong getNextMill() {
  ロングミル = getNewstmp();
  while (ミル <= lastStmp) {
   ミル = getNewstmp();
  }
  リターンミル;
 }

 プライベートlong getNewstmp() {
  System.currentTimeMillis() を返します。
 }

 パブリック静的voidメイン(String[] args) {
  スノーフレーク snowFlake = new SnowFlake(2, 3);

  (int i = 0; i < (1 << 12); i++) の場合 {
   System.out.println(snowFlake.nextId());
  }

 }
}

プロジェクト実施経験

hutools ツールキット

アドレス: https://github.com/looly/hutool

SpringBootはスノーフレークアルゴリズムを統合

hutoolツールクラスの紹介

<依存関係>
 <groupId>cn.hutool</groupId>
 <artifactId>hutool-all</artifactId>
 <バージョン>5.3.1</バージョン>
</依存関係>

統合

/**
 * スノーフレークアルゴリズム*
 * @著者: Moxi* @作成: 2020-04-18-11:08
 */
パブリッククラスSnowFlakeDemo {
 プライベートロングワーカーId = 0;
 プライベートロングデータセンターId = 1;
 プライベート Snowflake snowFlake = IdUtil.createSnowflake(workerId, datacenterId);

 @投稿コンストラクト
 パブリックvoid init() {
  試す {
   //ネットワークIPをlongに変換する
   ワーカー ID を NetUtil.ipv4ToLong(NetUtil.getLocalhostStr());
  } キャッチ (例外 e) {
   e.printStackTrace();
  }
 }

 /**
  * スノーフレークIDを取得する
  * @戻る
  */
 パブリック同期された長いスノーフレークID（）{
  this.snowFlake.nextId() を返します。
 }

 パブリック同期された長いスノーフレークID(長いワーカーID、長いデータセンターID) {
  スノーフレーク snowflake = IdUtil.createSnowflake(workerId, datacenterId);
  snowflake.nextId() を返します。
 }

 パブリック静的voidメイン(String[] args) {
  SnowFlakeDemo を新しい SnowFlakeDemo() に追加します。
  (int i = 0; i < 20; i++) の場合 {
   新しいスレッド(() -> {
    System.out.println(snowFlakeDemo.snowflakeId());
   }, String.valueOf(i)).start();
  }
 }
}

結果を得る

1251350711346790400
1251350711346790402
1251350711346790401
1251350711346790403
1251350711346790405
1251350711346790404
1251350711346790406
1251350711346790407
1251350711350984704
1251350711350984706
1251350711350984705
1251350711350984707
1251350711350984708
1251350711350984709
1251350711350984710
1251350711350984711
1251350711350984712
1251350711355179008
1251350711355179009
1251350711355179010

長所と短所

アドバンテージ

ミリ秒は高次元にあり、自動インクリメント シーケンスは低次元にあり、ID 全体は増加傾向にあります。

データベースなどのサードパーティシステムに依存せず、サービスとして展開されるため、ID生成の安定性とパフォーマンスが非常に高くなります。

ビットはビジネス特性に応じて割り当てることができ、非常に柔軟です。

欠点

マシンのクロックに依存します。マシンのクロックを戻すと、重複した ID が生成されます。

単一のマシン上で増加していますが、分散環境であるため、各マシンのクロックを完全に同期することはできず、グローバルな増加が存在しない状況が発生する場合があります。この欠点は重要ではないと考えられます。一般に、分散 ID では増加傾向のみが必要であり、厳密に増加傾向は必要ではありません。要件の 90% では、増加傾向のみが必要です。

その他のサプリメント

時計の針を戻すことで ID が重複する問題を解決するために、後に誰かが解決策を提案しました。

Baidu のオープンソース分散型ユニーク ID ジェネレーター UidGenerator

Leaf - 美団点評分散ID生成システム

上記の記事、シンプルな ID 生成戦略: Mysql テーブルからグローバルに一意の ID を生成する実装が、私が皆さんと共有できるすべてです。この記事が皆さんの参考になれば幸いです。また、123WORDPRESS.COM をサポートしていただければ幸いです。