10

分散環境と並行環境で一意のシーケンス番号を生成するための制約とトレードオフに興味があります。

これを想像してみてください:私は、あなたが尋ねるたびに一意のシーケンス番号を返すだけのシステムを持っています。このようなシステムの理想的な仕様 (制約) は次のとおりです。

  • 高負荷の下で起きていてください。
  • できるだけ多くの同時接続を許可します。
  • 分散: 複数のマシンに負荷を分散します。
  • パフォーマンス: 可能な限り高速に実行し、可能な限り多くのスループットを実現します。
  • 正確性: 生成される数値は次の条件を満たしている必要があります。
    1. 繰り返さない。
    2. リクエストごとに一意である必要があります (2 つのリクエストがまったく同時に発生した場合、関係を解消する方法が必要です)。
    3. (昇順) 順番に。
    4. リクエスト間にギャップはありません: 1,2,3,4... (事実上、合計 # リクエストのカウンター)
  • 耐障害性: 1 つ以上のマシン、またはすべてのマシンがダウンした場合、障害が発生する前の状態に再開できます。

明らかに、これは理想化された仕様であり、すべての制約を完全に満たすことはできません。CAP定理を参照してください。ただし、制約のさまざまな緩和についての分析をお聞きしたいと思います。どのようなタイプの問題が残り、残りの問題を解決するためにどのアルゴリズムを使用するか。たとえば、カウンター制約を取り除くと、問題ははるかに簡単になります。ギャップが許容されるため、数値範囲を分割して、それらを異なるマシンにマップするだけです。

参考文献 (論文、書籍、コード) は大歓迎です。また、既存のソフトウェア (オープン ソースかどうか) のリストも保持したいと思います。

ソフトウェア:

  • Snowflake : 一意の ID 番号を大規模に生成するためのネットワーク サービスで、いくつかの単純な保証があります。
  • keyspace : ID を任意の目的に使用できる、公的にアクセス可能な一意の 128 ビット ID ジェネレーター
  • RFC-4122 の実装は、多くの言語で存在します。RFC 仕様は、システム間の調整の必要性を防止するため、おそらく非常に優れたベースであり、UUID は 128 ビットであり、仕様の特定のバージョンを実装するソフトウェアから ID を使用する場合、タイム コード部分が含まれています。仕分け可能 など
4

2 に答える 2

1

(マシンごとに) シーケンシャルである必要があるが、ギャップ/カウンター要件を削除できる場合は、 RFC 4122で指定されているバージョン 1 UUID の実装を探します。

.NET で作業していて、シーケンシャルおよびギャップ/カウンターの要件を排除できる場合は、System.Guidを使用してください。それらは RFC 4122 バージョン 4 を実装しており、マシンと要求全体で既に一意です (衝突確率が非常に低い)。これは、Web サービスとして簡単に実装することも、ローカルで使用することもできます。

于 2011-10-28T19:38:24.077 に答える
0

多くのユースケースに適合しない可能性がある重要な注意点はありますが、すべての要件を満たすアプローチの概要を次に示します。

シーケンス番号が 2 つあることを許容できる場合は、論理的な番号がすぐに返されます。一意で順序付けられていることが保証されていますが、ギャップがあります-そして、別の物理的なものは、ギャップがなく連続した順序であることが保証され、しばらくしてから利用可能になります-その場合、ソリューションは簡単に見えます:

  • 高解像度クロック + マシン ID を論理シーケンス番号として提供できる 1 つの分散システム
  • すべての論理シーケンス番号を、論理シーケンス番号を順序付けて物理シーケンス番号にマップする別の分散システムにストリーミングします。

2 番目のシステムの処理が完了するとすぐに、論理から物理へのマッピングをオンデマンドで行うことができます。

于 2014-10-31T17:56:14.780 に答える