488

ハイ/ロー アルゴリズムとは何ですか?

これはNHibernateのドキュメント (一意のキーを生成する方法の 1 つ、セクション 5.1.4.2) で見つけましたが、それがどのように機能するかについての適切な説明は見つかりませんでした。

Nhibernate が処理することは知っています。内部を知る必要はありませんが、気になるところです。

4

5 に答える 5

575

基本的な考え方は、主キーを構成する 2 つの数値 (「高い」数値と「低い」数値) があるということです。クライアントは、基本的に「高」シーケンスをインクリメントできます。その後、さまざまな「低」値を使用して、前の「高」値の範囲全体からキーを安全に生成できることがわかっています。

たとえば、現在の値が 35 の「高」シーケンスがあり、「低」数が 0 ～ 1023 の範囲にあるとします。次に、クライアントはシーケンスを 36 に増やし (35 を使用している間に他のクライアントがキーを生成できるようにするため)、キー 35/0、35/1、35/2、35/3... 35/1023 がすべて利用可能です。

主キーなしで値を挿入してクライアントにフェッチする代わりに、クライアント側で主キーを設定できると非常に便利です (特に ORM の場合)。他のことは別として、親子関係を簡単に作成し、挿入を行う前にキーをすべて配置できることを意味します。これにより、バッチ処理が簡単になります。

于 2008-11-11T20:57:35.020 に答える
166

ジョンの答えに加えて：

切断された状態で作業できるように使用されます。その後、クライアントはサーバーに hi 番号を要求し、lo 番号自体を増やすオブジェクトを作成できます。lo の範囲が使い果たされるまで、サーバーに接続する必要はありません。

于 2008-11-11T22:08:43.860 に答える
27

Lo は、キースペースを大きなチャンクに分割するキャッシュ アロケータです。これは通常、人間が賢明に選択する意味のあるサイズの範囲 (一度に 200 個のキーを取得するなど) ではなく、マシン ワードのサイズに基づいています。

Hi-Lo の使用は、サーバーの再起動時に大量のキーを浪費する傾向があり、人間にとって扱いにくい大きなキー値を生成します。

Hi-Lo アロケーターより優れているのは、「リニア チャンク」アロケーターです。これは同様のテーブルベースの原則を使用しますが、小さくて便利なサイズのチャンクを割り当て、人間に優しい素敵な値を生成します。

create table KEY_ALLOC (
    SEQ varchar(32) not null,
    NEXT bigint not null,
    primary key (SEQ)
);

次の、たとえば 200 個のキーを割り当てるには (これらはサーバーで範囲として保持され、必要に応じて使用されます):

select NEXT from KEY_ALLOC where SEQ=?;
update KEY_ALLOC set NEXT=(old value+200) where SEQ=? and NEXT=(old value);

このトランザクションをコミットできる (競合を処理するために再試行を使用する) ことができれば、200 個のキーが割り当てられ、必要に応じて分配できます。

チャンクサイズがわずか 20 のこのスキームは、Oracle シーケンスから割り当てるよりも 10 倍速く、すべてのデータベース間で 100% 移植可能です。割り当て性能はhi-loと同等です。

Ambler のアイデアとは異なり、キースペースを連続した線形数列として扱います。

これにより、複合キー (これは決して良いアイデアではありませんでした) の推進力を回避し、サーバーの再起動時に無駄な単語全体を無駄にすることを回避します。「フレンドリーな」人間規模のキー値を生成します。

比較すると、Ambler 氏のアイデアは、上位 16 ビットまたは 32 ビットを割り当て、hi-words が増加するにつれて、人間にとって使いにくい大きなキー値を生成します。

割り当てられたキーの比較: 

Linear_Chunk       Hi_Lo
100                65536
101                65537
102                65538
.. server restart
120                131072
121                131073
122                131073
.. server restart
140                196608

設計に関しては、彼のソリューションは数直線 (複合キー、大きな hi_word 製品) で Linear_Chunk よりも基本的に複雑ですが、比較上の利点はありません。

Hi-Lo 設計は、OO マッピングと永続化の初期に生まれました。最近の Hibernate などの永続化フレームワークは、デフォルトとしてよりシンプルで優れたアロケーターを提供しています。

于 2013-08-26T09:29:34.877 に答える
1

Hi/Lo アルゴリズムは、私の経験に基づくレプリケーション シナリオを使用する複数のデータベースに最適であることがわかりました。これを想像してみてください。ニューヨーク (エイリアス 01) にサーバーがあり、ロサンゼルス (エイリアス 02) に別のサーバーがあり、PERSON テーブルがあるとします。ニューヨークで人が作成されるときは、HI 値として常に 01 を使用します。 LO 値は次のシーケンシャルです。たとえば。

  • 010000010 ジェイソン
  • 010000011 デビッド
  • 010000012 テオ

ロサンゼルスでは、常に HI 02 を使用します。例:

  • 020000045 ルパート
  • 020000046 オズワルド
  • 020000047 マリオ

そのため、データベース レプリケーションを使用すると (ブランドに関係なく)、主キーの重複や衝突などを心配することなく、すべての主キーとデータが簡単かつ自然に結合されます。

このシナリオでは、これが最善の方法です。

于 2016-09-23T17:08:32.163 に答える