DHT上のフェイルセーフリソースアロケーター

0からNまでの数値の特定の範囲があり、2つの関数int alloc（）およびfree（int）を記述する必要があります。 最初のものは範囲[0、N）から無料の識別子の1つを選択し、2番目のものは再利用のためにそれを「返します」識別子の特定の時点）。 同時に、「下位レベル」にはDHTのみがあります。 ロックはありません。さらに、アルゴリズムにはフォールトトレランスが必要です。クラスターノードのいずれかがアルゴリズムの実行中に「開発」される場合、システムの動作は予測可能である必要があります。 タスクが面白く、そのような署名を持つフェイルセーフサービスを正しく使用できない理由と、署名を修正してそれを可能にする方法を見つけるのも興味深いです。

API

実際、「アロケーター」のAPIを明確にすることから始めましょう。 上記のように、現在のAPIは正しくありません-呼び出し元のコードが特定のプール要素の特定の状態を常に理解できるとは限らないため、分散システムでは使用できません。

簡単な例。
1）allocate（）関数を呼び出すと成功しますが、allocate（）からの応答が送信されると、呼び出し元のコードは機能しなくなります。 問題-識別子は際立っていましたが、それについては何も知りません。 物理的に何らかの回復手順を記述して削除する方法はありません。 一方、リソースの割り当てを担当するコードはすでに機能しており、その観点からは識別子が割り当てられています。 そして、彼自身がそれを削除することはできません。なぜなら彼は電話が無料になるまで待たなければならないからです。 そうではありません。
2）free（）関数のべき等性が必要です。 明らかに、呼び出しコードは、いずれの場合でもfree（）を呼び出すように作成する必要があります。 明らかに、allocateから回答を受け取ったら、それを永続メモリ（RDBMS、キー値ストレージ、または単にプリンターに印刷してスキャナーに用紙をロードする）に入れます。 そして、ある時点で、あるノードがリソースの削除を決定すると、free（）を呼び出します。 ただし、空きノードが実行中の場合、ノードがオフになり、「コーリングパーティ」は明らかに再度呼び出しを試みます（これをどのように実装するかは重要ではありません。実装することが重要です）。 これは、不快な驚きが私たちを待っている場所です。 事実、無料でもリソースを解放できる可能性があります。 さらに、サードパーティのalloc（）が再び強調表示する場合があります。 その後、リソースを再び解放しますが、今回は既に他の誰かのリソースになっています。

一般的に、これらのAPIの問題を解決するにはいくつかの方法があります。

最も単純で非常に普遍的なのは、リソースの各割り当てにタグをアタッチすることです。これは、割り当て/解放操作の各ペアに対して一意に選択されます。

つまり、メソッドシグネチャはint alloc（T t）およびfree（int id、T t）に変更されます。 どのタイプのTであっても、特定の同値関係が存在し、それを使用して上記の2つの問題を解決できることが重要です。 まず、無料のメソッドをべき等にすることができます。 第二に、割り当てられたが古い情報を受け取らなかった「ファントム」識別子を削除するための比較的簡単な手順を導入できます（問題1を参照）。 記事を膨らませないために、これについては詳しく説明しません。

ほとんどの場合、この方法で変更されたサービスをほぼ常に使用できることに注意してください。 ほとんどの場合、「識別子」を何かに割り当て、いつでもこの「何か」をタグとして使用できます。

ここでもう少し、「部分的な」実行の場合にallocとfreeがどのように動作するかを正確に理解する必要があります。

明らかに、一般的な場合、呼び出し元のコードはallocが実行されたかどうかを知ることができません。 したがって、呼び出しコードの最初のルールは次のようになります

•呼び出し元のコードは、最初にallocが呼び出される識別子をどこかに書き込み、次にそれを呼び出す必要があります。 このため、呼び出し元のコードは、逆の順序で回復手順を実装できます。選択されたすべてのペア（id、t）を反復処理し、ストレージで言及されていないすべてのペアに対して無料で呼び出します。
同様に、呼び出されたかどうかに関係なく、フリーメソッドについては学習できません。
ここからさらに2つのルールが生まれます。
•freeメソッドに渡される識別子は、freeメソッドを呼び出す前に、システムで「無料」である（つまり、使用されていない）と見なされる必要があります。
•それにもかかわらず、少なくとも1つの呼び出しが正常に完了するまで、freeメソッドを呼び出してください（許容される-数回）。

それでは、実装に移りましょう。

実装

入り口にDHTがあります。 Javaで書いている人のために、 ConcurrentMapを持っていると仮定します（ちなみに、そのインターフェイスは他の言語を使用している開発者には明らかです）。 同時に、異なるホストのConcurrentMapは同じコンテンツを「見ます」。

それ自体では、DHTの操作はアトミックです（これはDHTの多くの実装で完全にサポートされています）。

ただし、DHTの課題間にアトミック性はないため、この部分を考慮して、その実装をサポートする必要があります。

実装

明らかに、DHTではid-> t（またはその逆）という形式の何らかのマップがあります。 問題は、すべてのビジーノードを経由せずに最初の空きIDを取得する方法ですか？

このような解決策が提案されています。 次のようなバイナリ区間ツリーを構築しましょう
•ツリールート-間隔[0、N）
•非リーフノードX [a、b）の下には、正確に2つのノード[a、c）および[c、b）があります。cは、これらの間隔の長さが等しくなるように選択されます。
•そして、[id、id + 1）の形式の間隔は、ツリーの葉です。
明らかに、そのようなツリーにはN個のシートがあり、それぞれがln（N）遷移のルートから到達できます。

次に、ツリーの各非リーフノードに、このノードが表す間隔で予約されている識別子の数を入力しましょう。 そして、ツリーのリーフノードに、対応する識別子がビジーの場合はタグを配置し、フリーの場合はnullを配置します。
これで、このツリーをDHTに保存することができます。 さらに、ノードの情報を正しい順序で更新することが重要です。これは、任意のステップで割り込んだ場合でも、アルゴリズムが正しく機能する必要があるためです。

fromとtoの2つのフィールドを持つInterval構造があり、ハーフオープンの間隔（fromを含むがtoは含まない）を定義するとします。 明らかに、そのような構造はツリーノードをエンコードします。 また、ツリーには重複ノードがなく、さらに、そのようなツリーの間隔の位置を決定するために何も必要ないことに注意してください。 言い換えれば、ツリー要素を「ポインタ」にバインドする必要はありません。 どのノードが「下」にあり、どのノードが「上」にあるかをノードXから判断できるアルゴリズムをいつでも構築できます。
これは私たちの生活を簡素化する重要な財産です。

この構造に、必要なコンストラクター、明らかなイコールとハッシュコードがあり、さらに3つの有用なメソッドがあります：left（）、right（）-子ノードを決定し、up（）-親を決定します デザイナーとハッシュコードがあれば、誰もがそれを処理できると思います。 左（）と右（）もあります。 up（）関数の使用は多少難しくなりますが、それを書くことは可能です（不必要な詳細でテキストがぼやけないように記事の最後に戻ります）。

現在、スパニングツリーをコード化できる「魔法の」間隔構造を持っているため、問題は小さいままです。
allocateでは、空でないシートを選択してタグを書き込む必要があります。次に、選択したシートから上に移動して値を更新します。 2つのことを覚えておくことが重要です。
•アトミック操作putIfAbsentによってタグがリストに追加されます
•リーフ以外のノードの値は、read-modify-atomicUpdateを使用してループを介して更新されます。 つまり、更新されたノードから値を読み取り、子ノード内の値を読み取り、原子置換を通じて子の合計を更新されたノードに書き込みます。 アトミック置換が機能しなかった場合は、操作を繰り返します。
•ノードのサブツリーに空き葉があることをDHTから読み取ったとしても、それが実際にそこにあるという意味ではありません。
したがって、空のシートを見つけて更新するためのフェイルファースト手順からの「成功まで」サイクルとして割り当てが書き込まれます。 ツリーの最初の変更は、シートの更新であり、その後のみ-親ノードの更新であることに注意してください。 これが必要な理由は allocateはいつでも完了できます。

Freeは同じように機能します。タグが要求されたものと一致し、ツリーの上のノードを更新すると、識別子を「解放」します（つまり、DHTからノードを削除します）。 同時に、ノードの更新は、割り当ての方法と一致します。 注意すべき重要なことは、リーフノードに値が含まれていない場合でも（つまり、freeが既に呼び出されている場合でも）freeがツリーの更新を実行することです。 これが必要な理由は 以前のfreeは部分的に実行され、シートは解放されますが、親ノードは更新されません。 実際には、このために、freeを複数回呼び出すことができ、最後に呼び出しが正常に完了したことが疑わしい場合は再度呼び出す必要があるというAPIの要件が必要です。

機能アップ

実際、約束された（）関数。 トップレベルの間隔の長さが2 ^ nであることに同意する場合、左（）、右（）、および上（）のスペルが大幅に簡略化されることに注意してください。 その場合、ツリー内の他の間隔は2 ^ nの長さを持ち、さらに、ツリーの同じ「レベル」の間隔は同じ長さを持ちます。 一般的に、3つのsabj関数はすべて、任意のトップレベルの間隔で記述できます（ただし、「現在の」間隔に加えて、常に上位レベルの間隔を知る必要があります）。 しかし、これは不便であり、2 ^ nに一般化しても何も害はありません。

したがって、間隔の長さが2 ^ nの場合、左（）および右（）は簡単に記述され、上（）については、現在の間隔がその親間隔に対して「右」または「左」であるかどうかを判断するだけです。 これは単純なルールによって決定されます-「左」の間隔で、初期値は残りの間隔なしで間隔の2倍の長さで除算されます。 したがって、間隔（左（）または右（）関数のどちらから取得したか）を知っていれば、反対のアクションを適用して上位レベルの間隔を取得するのは簡単です。