分散アーキテクチャシステムでグローバルに一意のシリアル番号を生成するためのアイデア

背景

分散アーキテクチャでは、一意のシリアル番号を生成することは、特にデータベースがシャーディングを使用する場合に、システムを設計するときによく発生する問題です。複数のシャーディング テーブルに分割されている場合、一意のシリアル番号をすばやく取得する方法がよく問題になります。

Ctrip のアカウント データベースを MySQL に移行するプロセス中に、Ctrip の既存の新規ユーザー登録量をサポートするために、ユーザー ID 生成スキームを再設計しました。

この記事では、Ctrip ユーザー ID ジェネレーターを実装し、サブライブラリとサブテーブルの一意の ID を設計するための新しいアイデアを提供することを目的としています。

[[210819]]

2. 機能要件

1. 世界的にユニーク
2. 高い同時実行性をサポート
3. 特定の属性を反映できる
4. 高い信頼性、単一障害点耐性
5. 高性能

3. 業界ソリューション

さまざまなシナリオ、ニーズ、パフォーマンス要件に合わせて ID を生成する方法は多数あります。

一般的な方法は次のとおりです。

1. データベース全体で一意のデータベース増分を使用します。

利点: 明白で制御可能。

デメリット: 単一のデータベースと単一のテーブル、高いデータベース負荷。

2. UUID、生成された文字列は長さ = 32 の 16 進形式です。合計 16 バイト要素を持つバイト配列に変換されると、UUID は 128 ビットの数値になり、通常は 16 進数で表されます。

利点: データベースへの負荷が軽減されます。

デメリット: では、ソートはどうでしょうか?

時間連結を追加する UUID のバリエーションもありますが、ID が非常に長くなります。

3. Twitter は、ストレージ システムを MySQL から Cassandra に移行する過程で、独自のグローバルに一意な ID 生成サービスである Snowflake を開発しました。これは、Cassandra にはシーケンシャル ID 生成メカニズムがなかったためです。

1. 41 ビットの時系列 (ミリ秒単位の精度、41 ビットは 69 年間使用可能)
2. 10 ビットのマシン ID (10 ビットで最大 1024 ノードの展開をサポートできます)
3. 12 ビットのカウント シーケンス番号 (12 ビットのカウント シーケンス番号は、各ノードが 1 ミリ秒あたり 4096 個の ID シーケンス番号を生成することをサポートします) 最後のビットは符号ビットであり、常に 0 です。

利点: 高性能、低レイテンシ。独立したアプリケーション。時間順に並べます。

デメリット: 独立した開発と展開が必要です。

4. RedisがIDを生成する

データベースを使用して ID を生成するパフォーマンスが十分でない場合は、Redis を使用して ID を生成してみることができます。これは主に、Redis がシングルスレッドであるという事実に依存しており、グローバルに一意の ID を生成するためにも使用できます。これは、Redis のアトミック操作 INCR と INCRBY を使用して実現できます。

より高いスループットを得るには、Redis クラスターを使用できます。クラスター内に 5 台の Redis サーバーがあるとします。各Redisの値はそれぞれ1、2、3、4、5に初期化でき、ステップの長さは5です。各Redisによって生成されるIDは次のとおりです。

答え: 1,6,11,16,21

B: 2,7,12,17,22

C: 3,8,13,18,23

4,9,14,19,24 （アメリカ）

E: 5,10,15,20,25

毎日 0 から始まるシリアル番号を生成するには、Redis を使用する方が適しています。たとえば、注文番号 = 日付 + その日の自動増分番号。毎日 Redis でキーを生成し、INCR を使用してそれを蓄積することができます。

アドバンテージ：

データベースから独立しており、柔軟性と利便性に優れ、パフォーマンスもデータベースよりも優れています。

数値 ID は自然にソートされるため、ページングやソートが必要な結果に役立ちます。

Redis クラスターを使用すると、単一障害点の問題も防ぐことができます。

欠点:

システムで Redis が利用できない場合は、新しいコンポーネントを導入する必要があり、システムの複雑さが増します。

コーディングや設定の作業量が比較的大きく、複数環境の運用・保守が非常に面倒です。

最初に、プログラム インスタンスがロードされる Redis インスタンスが決定されると、将来的にそれを変更することは困難です。

5. フリッカーの解決策

MySQL 自体が auto_increment 操作をサポートしているため、この機能を使用してこの関数を実装すると考えるのは当然です。

Flicker は、MySQL の自己増分 ID メカニズム (auto_increment + replace into + MyISAM) を使用して、グローバル ID 生成ソリューションを解決します。

6. JD.com や Taobao などの電子商取引プラットフォームの注文番号を生成するなどの他のソリューションもあります。注文番号とユーザー ID にはビジネス上の違いがあるため、注文番号には次のような冗長なビジネス情報をできるだけ多く含める必要があります。

Didi: 時間 + 出発地番号 + ナンバープレート番号

タオバオ注文: タイムスタンプ + ユーザーID

その他の電子商取引企業: タイムスタンプ + 注文チャネル + ユーザー ID。注文の最初のアイテムの ID を追加するものもあります。

ユーザー ID は、登録チャネルを含めて意味がシンプルで明確であり、できるだけ短くする必要があります。

4. 最終解決策

最終的に、ちらつきの解決策を最適化して改善することを選択しました。具体的な実装は、単一のテーブルを増分し、セグメント数をメモリにキャッシュすることです。

まず、次のようなテーブルを作成します。

シーケンスジェネレータテーブル

ID スタブ

1 192.168.1.1

IDは自動的に増加し、スタブはサーバーのIPです

新しいデータベースは MySQL を使用するため、MySQL の独自の構文 replace を使用してレコードを更新し、一意の ID を取得します。次に例を示します。

交換する  INTO SEQUENCE_GENERATOR_TABLE (スタブ) VALUES ("192.168.1.1");

次に、SELECT id FROM SEQUENCE_GENERATOR_TABLEWHERE stub = "192.168.1.1"; を使用します。それを取り戻すために。

これまでのところ、単一のデータベースでのみ ID を生成しました。高可用性の観点から、単一障害点の問題を解決する必要があります。

これが、このマシン IP フィールドが必要な理由です。これは、複数のサーバーが同時にデータを更新し、取得した ID に混乱が生じるのを防ぐためです。

したがって、サーバーが複数ある場合、表は次のようになります。

ID スタブ

5 192.168.1.1

2 192.168.1.2

3 192.168.1.3

4 192.168.1.4

各サーバーは自身のレコードのみを更新するため、単一行のレコードに対してシングルスレッド操作が保証されます。

このとき、各マシンはそれぞれ 5、2、3、4 の 4 つの ID を取得します。

これまでのところ、サーバーの分離とアトミック ID 取得の問題を解決したようですが、これは基本的にフリッカー ソリューションと同じです。

ただし、ソースを遡って考えると、原則として、ソリューションは依然としてデータベースの特性に依存します。 ID が生成されるたびにデータベースへのリクエストが必要となり、コストが非常に高くなります。これをさらに最適化し、この ID をシリアル番号ではなく番号セグメントとして使用して送信するようになりました。さらに、この数字セグメントの長さは 1000 または 10000 に設定できます。つまり、ID を何倍に拡大するかという問題です。

1 回のクエリ操作のオーバーヘッドで、1000 個のユーザー ID を DB からメモリに取得しました。

現在の問題は、同じサーバー上での高同時実行性の問題を解決し、重複や漏れなく全員が順番に番号を取得できるようにすることです。

簡単に言えば、この問題は、この数値セグメント内のオブジェクトの分離を維持することです。

AtomicLong は信頼できる方法です。

セグメント ID が初めて取得されるとき、セグメント ID は 1000 回拡張され、変数 atomic に割り当てられます。これはこのセグメントの最初の番号です。

アトミックセット( n*1000);

そして、この数字セグメントの最後の数字である***idをメモリに保存します。

現在の最大ID = (n + 1) * 1000;

数値セグメントが形成されます。

このとき、番号を取る要求があるたびに、最後の番号に達したかどうかが判断されます。そうでない場合は、番号を受け取って立ち去ってください。

長い uid = atomic.incrementAndGet();

最後の数字に達すると、他のリクエストスレッドはブロックされ、最も早いスレッドが DB にアクセスして数字セグメントを取得し、数字セグメントの 2 つの値を更新します。

このソリューションは、コア コード ロジックが 20 行未満で、分散システムにおけるシリアル番号生成の問題を解決します。

ここで小さな問題があります。サーバーを再起動すると、番号がメモリにキャッシュされるため、一部のユーザー ID が無駄になります。したがって、頻繁にリリースされる可能性のあるアプリケーションでは、無駄を減らすために、数値セグメント増幅のステップサイズ n をできるだけ小さくするのが最適です。

練習した後は、ID を無駄にするよりもパフォーマンスの向上の方がはるかに重要です。

再度ハッキングを続けたい場合は、Spring または Servlet コンテキストの破棄イベントを監視し、送信されようとしているユーザー ID を保存し、次回の起動時にそれをメモリに再度取得することができます。

5. オンライン効果

5か月以上稼働しており、非常に安定しています。

SOA サービスの平均応答時間は 0.59 ミリ秒です。

クライアント呼び出しの平均応答時間は 2.52 ミリ秒です。

フローチャートを添付します: