120

私は一般的に、過去にデータベースのシーケンスを使用してシーケンス番号の生成を実装しました。

たとえば、Postgres SERIAL タイプを使用http://www.neilconway.org/docs/sequences/

ただし、データベースがない大規模な分散システムのシーケンス番号を生成する方法については興味があります。複数のクライアントに対してスレッドセーフな方法でシーケンス番号の生成を達成するためのベストプラクティスの経験や提案はありますか?

4

14 に答える 14

134

OK、これは非常に古い質問で、今初めて見ました。

シーケンス番号と、(オプションで) 特定の基準 (通常は生成時間) によって大まかにソートできる一意の IDを区別する必要があります。真のシーケンス番号は、他のすべてのワーカーが行ったことの知識を意味するため、共有状態が必要です。分散型の大規模な方法でこれを行う簡単な方法はありません。ネットワーク ブロードキャスト、各ワーカーのウィンドウ範囲、一意のワーカー ID の分散ハッシュ テーブルなどを調べることができますが、それは大変な作業です。

一意の ID は別の問題です。分散型の方法で一意の ID を生成するいくつかの良い方法があります。

a) Twitter の Snowflake ID ネットワーク サービスを使用できます。スノーフレークは次のとおりです。

  • ネットワーク サービス。つまり、一意の ID を取得するためにネットワーク呼び出しを行います。
  • 生成時間順に並べられた 64 ビットの一意の ID を生成します。
  • サービスは拡張性が高く、(潜在的に) 可用性が高い。各インスタンスは毎秒数千の ID を生成でき、LAN/WAN 上で複数のインスタンスを実行できます。
  • Scala で記述され、JVM 上で実行されます。

b) UUIDと Snowflake の ID の作成方法から派生したアプローチを使用して、クライアント自体で一意の ID を生成できます。複数のオプションがありますが、次のようなものがあります。

  • 最上位の 40 程度のビット: タイムスタンプ。IDの生成時間。(タイムスタンプに最上位ビットを使用して、ID を生成時間でソートできるようにしています。)

  • 次の 14 程度のビット:ジェネレーターごとのカウンター。各ジェネレーターは、生成された新しい ID ごとに 1 ずつインクリメントします。これにより、同じ瞬間 (同じタイムスタンプ) に生成された ID が重複しないことが保証されます。

  • 最後の 10 程度のビット:各ジェネレーターの一意の値。これを使用すると、すべてのジェネレーターがこの値のために重複しない ID を生成するため、ジェネレーター間の同期を行う必要はありません (これは非常に困難です)。

c)タイムスタンプとランダム値のみを使用して、クライアントで ID を生成できます。これにより、すべてのジェネレーターを知る必要がなくなり、各ジェネレーターに一意の値が割り当てられます。反対に、そのような ID はグローバルに一意であるとは保証されておらず、一意である可能性が非常に高いだけです。(衝突するには、1 つ以上のジェネレーターがまったく同じ時間に同じランダム値を作成する必要があります。) 次の行に沿ったもの:

  • 最上位 32 ビット:タイムスタンプ、 ID の生成時刻。
  • 最下位 32 ビット: ID ごとに新たに生成される 32 ビットのランダム性。

d) 簡単な方法として、UUID / GUID を使用します。

于 2011-04-16T10:21:29.670 に答える
18

各ノードに一意の ID (とにかく持っている可能性があります) を持たせ、それをシーケンス番号の前に追加することができます。

たとえば、ノード 1 はシーケンス 001-00001 001-00002 001-00003 などを生成し、ノード 5 は 005-00001 005-00002 を生成します。

個性的 ：-）

あるいは、ある種の集中型システムが必要な場合は、シーケンス サーバーをブロック単位で提供することを検討できます。これにより、オーバーヘッドが大幅に削減されます。たとえば、割り当てる必要がある ID ごとに中央サーバーに新しい ID を要求する代わりに、中央サーバーに 10,000 のブロックで ID を要求し、不足したときに別のネットワーク要求を行うだけで済みます。

于 2010-04-20T01:08:34.167 に答える
17

今、より多くのオプションがあります。

この質問は「古い」ですが、私はここに来たので、私が知っているオプションを（これまでのところ）残すことが役立つかもしれないと思います：

  • Hazelcastを試すことができます。1.9リリースでは、java.util.concurrent.AtomicLongの分散実装が含まれています。
  • Zookeeperを使用することもできます。シーケンスノードを作成するためのメソッドを提供します（ノードのバージョン番号を使用することを好みますが、znode名に追加されます）。ただし、これには注意してください。シーケンスで数字を見逃したくない場合は、希望どおりでない可能性があります。

乾杯

于 2010-10-04T19:13:45.543 に答える
12

Redissonで実行できます。の分散型でスケーラブルなバージョンを実装しAtomicLongます。次に例を示します。

Config config = new Config();
config.addAddress("some.server.com:8291");

Redisson redisson = Redisson.create(config);
RAtomicLong atomicLong = redisson.getAtomicLong("anyAtomicLong");
atomicLong.incrementAndGet();
于 2014-01-12T06:56:01.803 に答える
8

単純に一意ではなく、グローバルに連続している必要がある場合は、これらの番号を配布するための単一の単純なサービスを作成することを検討します。

分散システムは、相互作用する多くの小さなサービスに依存しています。この単純な種類のタスクに対して、他の複雑な分散ソリューションが本当に必要なのか、それとも本当にメリットがあるのでしょうか?

于 2010-04-20T01:22:35.393 に答える
6

いくつかの戦略があります。しかし、私が知っていることは、実際に分散して実際のシーケンスを与えることはできません。

  1. 中央のナンバージェネレーターを持っています。大きなデータベースである必要はありません。 memcachedは高速なアトミック カウンターを備えており、ほとんどの場合、クラスター全体に対して十分に高速です。
  2. ノードごとに整数範囲を区切ります（Steven Schlanskterの回答のように）
  3. 乱数または UUID を使用する
  4. ノードのIDと一緒にデータの一部を使用し、すべてをハッシュします（またはhmac）

個人的には、ほとんど連続したスペースが必要な場合は、UUID または memcached を使用します。

于 2010-04-20T01:28:07.387 に答える
5

(スレッドセーフな) UUID ジェネレーターを使用しないのはなぜですか?

私はおそらくこれを拡張する必要があります。

UUID は、グローバルに一意であることが保証されています (一意である可能性が非常に高い乱数に基づくものを避ける場合)。

「分散」要件は、使用する UUID ジェネレーターの数に関係なく、各 UUID のグローバルな一意性によって満たされます。

「スレッド セーフ」の要件は、「スレッド セーフ」の UUID ジェネレーターを選択することで満たすことができます。

「シーケンス番号」の要件は、各 UUID の保証されたグローバルな一意性によって満たされると想定されます。

多くのデータベース シーケンス番号の実装 (Oracle など) は、単調に増加する、または ("接続" ごとに) 増加するシーケンス番号を保証しないことに注意してください。これは、シーケンス番号の連続したバッチが、接続ごとに「キャッシュされた」ブロックに割り当てられるためです。これにより、グローバルな一意性が保証され、適切な速度が維持されます。しかし、複数の接続によって割り当てられている場合、実際に (時間の経過とともに) 割り当てられるシーケンス番号がごちゃ混ぜになる可能性があります。

于 2010-04-20T01:20:59.533 に答える
2

分散 ID の生成は、Redis と Lua でアーカイブできます。Githubで利用可能な実装。分散型で k ソート可能な一意の ID を生成します。

于 2017-04-05T09:50:38.610 に答える