インタビュアー: どのような分散 ID 生成スキームをご存知ですか?

過去 2 年間の技術面接では、分散トランザクション、分散ロック、分散スケジューリング、分散ストレージ、分散 ID など、分散シリーズは面接官がよく尋ねる頻繁なトピックです。

今日は比較的シンプルな分散 ID についてお話します。まず、分散 ID はなぜ必要なのでしょうか?

システムデータの量が多すぎてデータベースとテーブルに分割されている場合、各データベーステーブルに散在するデータレコードを一意に識別する必要があり、この問題を解決するために分散 ID が使用されます。

次に、8 つの分散 ID 生成方式と、それぞれの長所と短所を見てみましょう。

写真

1. UUID

UUID は Universally Unique Identifier の略称で、中国語では「Universally Unique Identifier」と翻訳されます。 32 桁の 16 進数 + 4 つの「-」で構成され、合計の長さは 36 です。一意性を保証でき、衝突の可能性は極めて低くなります。

現在、UUID には 5 つのバージョンがあり、それぞれ生成方法が異なります。最も一般的に使用されるバージョンは、乱数によって生成されるバージョン 4 です。

UUID の生成と実装は非常に簡単で、java.util パッケージを通じて 1 行のコードだけで実現できます。

 import java.util.UUID; public class Test { public static void main(String[] args) { System.out.println(“本次生成的UUID为” + UUID.randomUUID()); } } //打印结果//本次生成的UUID为：05cb2d06-1aca-4121-acb0-dfafce04dc46

アドバンテージ：

（１）この技術は実装が簡単で、必要なコードは１行だけです。 （２）低いエラー率でローカルに生成できる。 （３）高いID生成性能

欠点:

（１）障害はデータベースのデータ書き込みパフォーマンスに影響を及ぼします。 （２）保管コストが高い。 4つの「-」を削除しても長さは32のままです。（3）読みにくい。

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

データベースを中央データベースとして選択し、データベース内のテーブルの自動増分主キー メカニズムを使用して分散 ID を生成します。

写真

対応する SQL ステートメントは次のとおりです。

 REPLACE INTO id_table (stub) values ('a') ; SELECT LAST_INSERT_ID();

この SQL ステートメントを使用すると、id_table テーブル内の 1 つのデータ レコードを維持しながら、主キー ID を増やし続けることができます。

アドバンテージ：

（１）単調増加なので、データベースのデータ書き込みパフォーマンスに影響を与えません。 （２）可読性が高い。

欠点:

（１）ID生成にはデータベース操作が伴い、パフォーマンスが低い。 （２）追加の中央データベースを導入する必要があり、リンクが長くなり、エラーの可能性が高まります。 （３）開発コストが比較的高い。 （4）データベースは大きな負荷を受けています。

3. Redisの自動インクリメントコマンド

Redis の INCR 自己増分コマンドを使用して分散 ID を生成します。

写真

以下のように表示されます。

 127.0.0.1:6379> set distributed_id 1 // 将分布式ID初始化为1 OK 127.0.0.1:6379> incr distributed_id // +1，并返回结果(integer) 2

アドバンテージ：

（１）単調増加なので、データベースのデータ書き込みパフォーマンスに影響を与えません。 （２）高いID生成性能（３）読みやすさが高い。

欠点:

（１）Redisを追加で導入する必要があり、リンクが長くなり、エラーが発生する可能性が高くなります。 （２）Redisがクラッシュした後、RDB + AOFデータのリカバリは遅く、リカバリ速度を上げるにはプランBが必要になります。 （３）開発コストが比較的高い。

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

SnowFlake は、Twitter が開発したオープンソースの分散 ID 生成アルゴリズムです。 hutool jar パッケージをローカルに導入することで実装できます。

スノーフレーク アルゴリズムによって生成される分散 ID は合計 64 ビットで、4 つの部分で構成されます。

写真

• パート1: 1ビット。 0 に固定され、正の整数として表されます。バイナリの最上位ビットは符号ビットであり、ID は正の整数であるため、0 に固定されます。
• パート2: 41桁。ミリ秒単位の精度のタイムスタンプを表します。タイムスタンプには自動増分属性があり、69 年間使用できます。
• パート3: 10桁。最大 1024 個のノードをサポートする 10 ビットのマシン ID を示します。
• パート4: 12ビット。自己増分シーケンスを示し、同じノードが同じミリ秒内に最大 4096 個の ID を生成することをサポートできます。

アドバンテージ：

（１）技術の実装が簡単で開発コストが低い。 （２）この傾向は増加傾向にあり、データベースのデータ書き込みパフォーマンスには影響しません。 （３）低いエラー率でローカルに生成できる。 （４）高いID生成性能

欠点:

（１）マシンクロックへの強い依存。マシンの時計を戻すと、ID の重複が発生します。 （２）読みにくさ

5. データベースセグメント

データベース セグメントは、「データベース自動増分 ID」ソリューションに基づく最適化です。実装は次のとおりです。

（１）中央データベースから分散IDのバッチを取得し、分散IDサービスにローカルにキャッシュする。ビジネス システムは、分散 ID を取得すると、このバッチ内で値を直接増分できます。 （２）分散IDのバッチの番号セグメントが使い果たされた場合、データベースの初期値を更新し、新しいバッチの分散IDを再度取得し、分散IDサービスにローカルに再キャッシュして使用する必要がある。

写真

CREATE TABLE id_generator ( id int(10) NOT NULL, max_id bigint(20) NOT NULL COMMENT '当前最大id', step int(10) NOT NULL COMMENT '号段的长度', biz_type int(10) NOT NULL COMMENT '业务类型', version int(10) NOT NULL COMMENT '版本号,是一个乐观锁，每次都更新version，保证并发时数据的正确性', PRIMARY KEY (`id`) )

アドバンテージ：

（１）増加傾向にあり、データベースのデータ書き込みパフォーマンスには影響しません。 （２）高いID生成性能（３）データベースの負荷が低い。 （４）読みやすさが高い。

欠点:

（１）開発コストが非常に高い。 （２）追加の分散IDサービスと中央データベースを導入する必要があり、リンクが長くなるにつれてエラーの確率が高くなります。

6. 美団葉

Leaf は、Meituan の技術チームによって実装された分散 ID 生成ソリューションです。データベース セグメント モード (Leaf-segment) とスノーフレーク アルゴリズム モード (Leaf-snowflake) を実装します。ここでは、Leaf-snowflake に焦点を当てます。

リーフスノーフレークソリューションは、スノーフレークアルゴリズムソリューションのビット設計に完全に従います。つまり、ID番号は「1+41+10+12」の形式で組み立てられます。変更点は次のとおりです: SnowFlake はローカル jar パッケージから独立したサービスに変更され、クロック ダイヤルバック問題を解決するために Zookeeper が導入されました。

写真

アドバンテージ：

（１）増加傾向にあり、データベースのデータ書き込みパフォーマンスには影響しません。 （２）元のマシンの時計を戻したときに発生するID重複の問題が解決されます。 （３）高いID生成性能

欠点:

（１）サードパーティのオープンソースソフトウェアには、一定の慣れと試行錯誤のコストがかかります。 （２）追加の分散IDサービスやZookeeperを導入する必要があり、リンクが長くなるにつれてエラー確率が増加する。 （３）読みにくさ

7. ディディ・ティニッド

Tinyid は、Didi 技術チームによって実装された分散 ID 生成アルゴリズムです。これは、上で紹介した数値セグメント モードに基づいています。これに基づいて、データベースのマルチマスター ノード モードをサポートし、tinyid-client クライアント アクセス メソッドも提供します。

さらに、Tinyid によるもう 1 つの最適化ポイントは、数値セグメントのプリロードです。

たとえば、現在使用可能な数値セグメント (1 ～ 1000) がメモリにロードされ、ID は 1 から増分的に取得されます。20% (デフォルト) が使用されている場合、次の使用可能な数値セグメント (4001 ～ 5000) が非同期的にメモリにロードされます。この時点で、メモリ内で使用可能な数値セグメントは (201-1000) と (4001-5000) です。

ID が 1000 に増加すると、現在の数値セグメントが使用され、次の数値セグメントが現在の数値セグメントに置き換えられます。

写真

アドバンテージ：

（１）増加傾向にあり、データベースのデータ書き込みパフォーマンスには影響しません。 （２）高いID生成性能（３）データベースの負荷が低い。 （４）読みやすさが高い。

欠点:

（１）サードパーティのオープンソースソフトウェアには、一定の慣れと試行錯誤のコストがかかります。 （２）追加の分散IDサービスと中央データベースを導入する必要があり、リンクが長くなるにつれてエラーの確率が高くなります。

8. Baidu の Uid ジェネレーター

UidGenerator は、Java で実装され、Snowflake アルゴリズムに基づいた一意の ID ジェネレーターです。

UidGenerator はアプリケーション プロジェクト内でコンポーネントとして動作し、カスタムの workerId 数字と初期化戦略をサポートします。

実装の面では、UidGenerator は将来の時間を借りることでシーケンスの自然な並行性の制限を解決し、生成された UID をキャッシュするために RingBuffer を採用し、UID の生成と消費を並列化し、同時に CacheLine を埋めることで、RingBuffer によって引き起こされるハードウェア レベルの「偽の共有」問題を回避します。最終的には、単一マシンの QPS は 600 万に達します。

写真

• 最初の部分: 1 ビット、符号識別子。つまり、生成された UID は正の数です。
• 2 番目の部分: 28 ビット、現在の時刻、時間基準点「2016-05-20」に対する増分値、秒単位で、最大約 8.7 年までサポートできます。
• 3 番目の部分: 22 ビット、マシン ID、最大約 420 万台のマシン起動をサポートできます。
• パート 4: 13 ビット、1 秒あたりの同時シーケンス、1 秒あたり最大 8192 の同時シーケンスをサポートします。

ここで、SnowFlake と比較すると、UidGenerator には時間ビットが少なく、マシン ID ビットが多いことがわかります。

アドバンテージ：

（１）増加傾向にあり、データベースのデータ書き込みパフォーマンスには影響しません。 （２）低いエラー率でローカルに生成できる。 （３）極めて高いID生成性能

欠点:

（１）サードパーティのオープンソースソフトウェアには、一定の慣れと試行錯誤のコストがかかります。 （２）マシンクロックに大きく依存する。マシンの時計を戻すと、ID が重複する原因になります。 （３）読みにくさ

結論

これら 8 つの分散 ID 生成方式の中で最も一般的に使用されているのは、スノーフレーク アルゴリズムとデータベース セグメント方式です。

もちろん、最も一般的に使用されているものが、担当するシステムに最も適しているとは限りません。やはり自分の特性に基づいて選択する必要があります。