詳しく説明すると.. a) テーブル (BIGTABLE) には、主キーを ID として 100 万行を保持する容量があります。(ランダムで一意) b) これまで使用されていない ID に到達するために使用できるアルゴリズム。この番号は、テーブル BIGTABLE に別の行を挿入するために使用されます。
詳細について質問を更新しました.. C) このテーブルにはすでに約 10 万行あり、主キーは ID として設定されていません。d) 現在、主キーとして乱数が生成され、このテーブルに行が挿入されます。挿入が失敗すると、別の乱数が生成されます。問題は、ループに陥ることがあり、生成される乱数はかなりランダムですが、残念ながら、それらは既にテーブルに存在します。したがって、しばらくしてから乱数生成番号を再試行すると、機能します。e) sybase rand() 関数を使用して乱数を生成します。
この質問への追加がいくつかの点を明確にするのに役立つことを願っています。
もちろん、質問は次のとおりです。なぜランダムIDが必要なのですか?
私が同様の要件に遭遇した 1 つのケースは、webapp のクライアント ID の場合でした。クライアントは自分のクライアント ID (Cookie に保存されている) で自分自身を識別します。彼のデータをハイジャックします）。
私が行った解決策は、シーケンシャルな int32 とランダムな int32 を組み合わせて、クライアント ID として使用した int64 を取得することでした。PostgreSQL の場合:
CREATE FUNCTION lift(integer, integer) returns bigint AS $$
SELECT ($1::bigint << 31) + $2
$$ LANGUAGE SQL;
CREATE FUNCTION random_pos_int() RETURNS integer AS $$
select floor((lift(1,0) - 1)*random())::integer
$$ LANGUAGE sql;
ALTER TABLE client ALTER COLUMN id SET DEFAULT
lift((nextval('client_id_seq'::regclass))::integer, random_pos_int());
生成された ID は「半分」ランダムですが、残りの「半分」は同じ ID を 2 回取得できないことを保証します。
select lift(1, random_pos_int()); => 3108167398
select lift(2, random_pos_int()); => 4673906795
select lift(3, random_pos_int()); => 7414644984
...
一意のIDがランダムなのはなぜですか？IDENTITYを使ってみませんか？既存の行のIDはどのように選択されましたか。
最も簡単な方法は、おそらく（BIGTABLEからMax（ID）を選択）、新しい「ランダム」IDがそれよりも大きいことを確認することです...
編集：追加された情報に基づいて、私はあなたが失敗していることを提案します。
オプションの場合：テーブルをコピーしてから再定義し、ID列を使用します。
別の答えが推測しているように、真にランダムな識別子が必要な場合は、PKを2つのフィールドにします。IDフィールド、次に乱数。
挿入を試みる前にIDが存在するかどうかを確認するためにテーブル構造を変更できない場合は、おそらく唯一の手段です。
これには本当に良いアルゴリズムはありません。この基本的な構成を使用して、未使用のIDを見つけることができます。
int id;
do {
id = generateRandomId();
} while (doesIdAlreadyExist(id));
doSomethingWithNewId(id);
箱から少し外れています。
事前に乱数を生成してみませんか? そうすれば、新しい行を bigtable に挿入するときに、チェックはすでに行われています。これにより、bigtable への挿入が一定時間の操作になります。
最終的にはチェックを実行する必要がありますが、bigtable への挿入という機密性の高いプロセスを含まない 2 番目のプロセスにオフロードされる可能性があります。
または、数十億の乱数を生成し、重複を削除すれば、しばらく心配する必要はありません.
最善の策は、衝突の可能性が非常に低くなるようにキー空間を十分に大きくすることです。その後は心配する必要はありません。前述のように、GUID がこれを行います。または、十分なビットがある限り、純粋な乱数を使用できます。
これを頻繁に行う必要がある場合は、この質問にすばやく回答できるように、ライブ（非db）データ構造を維持することをお勧めします。10ウェイツリーが良いでしょう。アプリが起動すると、データベースからキーを読み取ってツリーにデータが入力され、データベースで行われたさまざまな挿入と削除との同期が維持されます。アプリがデータベースを更新する唯一のアプリである限り、次の大きなランダムキーがまだ使用されていないことを確認するときに、ツリーを非常に迅速に調べることができます。
乱数を選び、それが既に存在するかどうかを確認します。存在する場合は、存在しないものにヒットするまで試行を続けます。
編集:または、さらに良いことに、チェックをスキップして、機能するまで異なる ID の行を挿入してみてください。
キー フィールドを UNIQUE と IDENTITY にすれば、心配する必要はありません。
最初の質問: これは計画されたデータベースですか、それともすでに機能しているデータベースですか。内部に既にデータがある場合は、bmdhacks による回答が正しいです。それが計画されたデータベースである場合、ここで 2 番目の質問があります:
主キーは本当にランダムである必要がありますか? 答えが「はい」の場合は、関数を使用して、既知のシードとカウンターからランダムな ID を作成し、作成された ID の数を確認します。作成された ID ごとにカウンターが増加します。
シードを秘密にしておく (つまり、シードを呼び出して非公開として宣言する) 場合、他の誰も次の ID を予測できないはずです。
これは、乱数ジェネレーターを使用してブルートフォースを介してこれまで何度も行われたことがありますが、これは常に悪い考えです。データベースの外部で乱数を生成し、それが存在するかどうかを確認しようとすると、アプリとデータベースに大きな負担がかかります。また、2つのプロセスが同じIDを選択する可能性があります。
最善のオプションは、MySQLの自動インクリメント機能を使用することです。他のデータベースにも同様の機能があります。一意のIDが保証され、同時実行性の問題は発生しません。
一意の値を探すたびに、そのテーブル内のすべての値をスキャンすることはおそらく悪い考えです。これを行う方法は、別のテーブルに値を設定し、そのテーブルをロックし、値を読み取り、次のIDの値を計算し、次のIDの値を書き込み、ロックを解除することだと思います。次に、現在のプロセスがその一意の値を保持している唯一のプロセスであるという確信を持って、読み取ったIDを使用できます。どれだけうまくスケーリングできるかわかりません。
または、IDにGUIDを使用します。これは、新しく生成された各GUIDが一意であると想定されているためです。
乱数作成者に現在の日付を秒単位で追加してみませんか。この方法で同一の ID を持つ唯一の方法は、2 人のユーザーが同時に作成され、ジェネレーターによって同じ乱数が与えられる場合です。
ID が純粋にランダムである場合、未使用の ID をブルート フォースなしで同様にランダムな方法で見つけるアルゴリズムはありません。ただし、ランダムな一意の ID のビット深度がかなり大きい (たとえば 64 ビット) 限り、100 万行しかなくても衝突から十分に安全です。挿入時に衝突した場合は、もう一度やり直してください。
データベースによっては、シーケンサー (oracle) または自動インクリメント (mysql、ms sql など) を使用するオプションがある場合があります。または、最後の手段として select max(id) + 1 as new id - 同時リクエストに注意して、同じ max-id を2回使用しないようにしてください - 今後の挿入ステートメントでロックにラップします
新しい ID もランダムにする必要がありますか? もしそうなら、最良の答えは、存在しないものが見つかるまでループすることです (ランダム化、存在のテスト)。
データがたまたまランダムであるが、それが強い制約ではない場合は、SELECT MAX(idcolumn) を使用して、データに適した方法でインクリメントし、それを次のレコードの主キーとして使用できます。
これはアトミックに行う必要があるため、テーブルをロックするか、DB 構成とスキーマに適した他の同時実行制御を使用してください。ストアド プロシージャ、テーブル ロック、行ロック、SELECT...FOR UPDATE など。
どちらのアプローチでも、失敗したトランザクションを処理する必要がある場合があることに注意してください。理論的には、最初に重複キーの問題が発生する可能性があり (ただし、キー スペースがまばらに設定されている場合はありそうにありません)、SELECT...FOR UPDATE などのアプローチを使用すると、一部の DB でデッドロックが発生する可能性があります。したがって、エラーが発生した場合は必ずトランザクションを確認して再起動してください。
その場合の最適なアルゴリズムは、乱数を生成し、選択を行ってそれが存在するかどうかを確認するか、データベースが正常にエラーになった場合に追加することです。キーの範囲とレコードの数によっては、これはわずかな時間になる可能性があります。また、スパイクする能力があり、まったく一貫性がありません。
BigTable でいくつかのクエリを実行して、悪用できる範囲があるかどうかを確認することは可能でしょうか? すなわち。100,000 から 234,000 の間はまだ ID がないので、そこに ID を追加できますか?
最初に Max(ID) + 1 が使用されていないかどうかを確認し、それを使用します。
Max(ID) + 1 が最大値を超える場合は、一番上にある順序付けられたチャンクを選択し、穴を探して逆方向にループを開始します。数がなくなるまでチャンクを繰り返します (この場合、大きなエラーがスローされます)。
「穴」が見つかった場合は、ID を別のテーブルに保存します。それを次のケースの開始点として使用して、ループを保存できます。
タスク自体の推論をスキップして、
乱数を生成し、それがすでに使用されているかどうかを確認しています