ロックフリーのデータ構造。 イテレータ：マルチレベル配列

opusの前の部分（ 1、2、3 ）では、ロックフリーマップの内部構造を調べ、すべての基本操作（キーの検索、追加、削除）がグローバルロックなしで、さらにはロックフリーな方法でも実行できることを確認しました。 しかし、標準のstd::mapは、別の非常に便利な抽象化-イテレータをサポートしています。 反復可能なロックフリーマップを実装することは可能ですか？
この質問への答えは控えめです。

一年前、私は原則として、ロックフリーのコンテナにはイテレータが実行可能ではないと確信していました。 自分で判断してください：イテレータを使用すると、コンテナのすべての要素をバイパスできます。 しかし、ロックフリーの世界では、コンテナの内容は常に変化しているので、「すべての要素をバイパスする」と考えられるものは何ですか？



反復-コンテナの要素を反復処理-時間がかかり、その間にコンテナからいくつかの要素が削除され、他の要素が追加されますが、トラバースの全時間にわたってコンテナに存在する安定した（空の可能性のある）要素のサブセットが存在する必要がありますlist.begin()からlist.end() 。 それらに加えて、追加された要素のいくつかと、削除された要素のいくつかを、カードが置かれるときに訪問できます。 明らかに、ロックフリーマップ内のすべての要素を訪問するタスクは不可能です。ラウンドの全時間にわたってコンテナの状態を凍結することはできません。 このような凍結とは、実際には、他のスレッドがコンテナに対して変更操作を実行することを禁止することを意味します。これは、ブロッキングと同等です。


したがって、安定したサブセットからのすべてのノードへの保証された訪問は、競合するコンテナのバイパスであると考えます。

「競合するコンテナのバイパスと見なされるもの」という質問に加えて、2つの問題があります。

問題1 。 イテレータは、本質的にコンテナ要素への特殊なポインタです。 イテレータを使用して、要素自体にアクセスします。 ただし、競合するコンテナでは、イテレータが配置されている要素はいつでも削除できます。 つまり、イテレータはいつでも無効になる可能性があります-削除された要素、つまりゴミを指します：



ハザードポインター回路におけるこの問題の解決策は、実際にはハザードポインターです。 HPスキームでは、ポインターが危険であると宣言されている間、ポインター（ポインター）を物理的に削除できない、つまり、ガベージカボチャにならないことを思い出してください。 以下の便利な抽象化、 guarded_ptr保護ポインターを導入します。

 template <typename T> struct guarded_ptr { hp_guard hp; //   T * ptr; //   guarded_ptr(std::atomic<T *>& p) { ptr = hp.protect( p ); } ~guarded_ptr() { hp.clear(); } T * operator ->() const { return ptr; } explicit operator bool() const { return ptr != nullptr; } }; 

ご覧のとおり、 guarded_ptrはハザードポインターを備えた単なるポインターです。 ハザードポインターhpは、 ptr要素へのポインターを保護し、物理的に削除されないようにします。 ストリームBがイテレータが配置されている要素を削除しても、この要素はコンテナから除外されますが、イテレータのハザードポインタにこの要素へのリンクが含まれるまで物理的に削除されません。

したがって、HPスキーマでは、反復子クラスは次のようになります。

 template <typename T> class iterator { guarded_ptr<T> gp; public: T* operator ->() { return gp.ptr; } T& operator *() { return *gp.ptr; } iterator& operator++(); }; 

問題2 ：次の項目に進みます。



特定のスレッドBが、イテレータが配置されている要素（この場合は42）に続く要素を削除すると、イテレータをインクリメントする操作は、削除された要素の呼び出し、つまりガベージになります。

この問題は、スレッドがコンテナをバイパスしていることを知らず、要素を自由に削除/追加できるため、最初の問題よりも複雑です。 イテレータが指す要素を何らかの方法でマークし、要素を削除するときにそのようなフラグを分析することを考えることができますが、これは少なくともコンテナの内部構造を複雑にします（そして、最大で、そのような推論は何にもつながりません）。 興味深いデータ構造からわかる別の方法があります-マルチレベル配列。

マルチレベル配列

このデータ構造は、2013年にSteve Feldmanによって提案された連想コンテナ、つまりハッシュマップです。



ハッシュが一定の長さのビット文字列であると想像してください。 この文字列のビットをマルチレベル配列のインデックスと見なします：最初のMビットは、ヘッド配列のヘッド配列のインデックスです（図ではM = 4、つまり、ヘッド配列のサイズは2 ** 4 = 16です）、Nビットの次の部分は基礎となるノード配列のインデックス（図では、N = 2で、ノード配列の次元は2 ** 2 = 4です）。 配列要素には次のものがあります。

• 空です
• データポインタ
• 次のレベルの配列へのポインター

空のマルチレベル配列は、すべてのセルが空のヘッド配列のみで構成されます。

次のアルゴリズムに従って、マルチレベル配列のキーキーを使用してデータdataを追加します。

• 1.キーハッシュを計算するh = hash( key )
• 2.ハッシュhの最初のMビットを取得します-これは、ヘッド配列のiセルのインデックスです
• 3a。 セルが空の場合（ head_array[i] == nullptr ）、データをその中に入れます： head_array[i].CAS( nullptr, &data ) -そして終了します。 ロックフリーのコンテナがあるので、アトミック操作、この場合はCAS（C ++ 11の観点では比較と交換、 std::compare_exchange ）をstd::compare_exchangeます。
• 3b。 セルにデータが含まれる場合（ head_array[i] = di ）、それを分割する必要があります。つまり、次のレベルのノード配列を作成し、その中にdiを入れて、ステップ4に進みます。
• 3c。 セルに基になるノード配列へのポインターが含まれている場合は、手順4に進みます。
• 4.現在の配列は特定のノード配列です。 キーhハッシュの次のNビットを取得します。これらのビットは、現在のノード配列のインデックスiになります。 ハッシュのすべてのビットが使い果たされた場合、コンテナにはすでに同じハッシュを持つ要素があり、データdata挿入は失敗します。
• 4a。 セルが空の場合（ current_node_array[i] == nullptr ）、その中にデータを配置します： current_node_array[i].CAS( nullptr, &data ) -そして終了
• 4b。 セルにデータが含まれる場合（ current_node_array[i] = di ）、それを分割する必要があります。つまり、次のレベルのノード配列を作成し、その中にdiを入れて、ステップ4に進みます。
• 4c。 セルに基になるノード配列へのポインターが含まれている場合は、手順4に進みます。

ご覧のように、挿入アルゴリズムは非常にシンプルで直感的です-言葉で説明するよりも描く方が簡単です。 削除アルゴリズムはさらに簡単です：削除されたキーのハッシュ値をビット文字列として考慮し、ビットを選択して配列内のインデックスとして解釈し、セルが空またはデータを含む配列へのリンクを下ります。 セルが空の場合、キー（より正確には、そのハッシュ）がコンテナー内になく、削除するものがないことを意味します。 セルにデータが含まれ、このデータのキーが目的のキーである場合、アトミックCAS操作を使用してセル値をnullptr変更します。 削除するとき、配列のセルをゼロにするだけで、node_array自体は決して削除されないことに注意してください-この事実は将来役に立つでしょう。

質問は未解決のままです。配列セルに含まれる内容を区別する方法-次のレベルの配列へのデータまたはポインター。 通常のプログラミングでは、配列の各スロットにブールタグを配置します。

 struct array_slot { union { T* data; node_array* array; }; bool is_array; // ,    — data  array }; 

しかし、私たちのプログラミングは異常であり、このアプローチは私たちには適していないでしょう。 異常なことは、データの長さに制限があるアトミックプリミティブCASを操作する必要があることです。 つまり、1つのCASでセルの値とis_array属性をアトミックに変更できる必要があります。
ロックフリーエピックの前の部分を読んで、 マークされたポインターのようなものがあることを知っていれば、これは問題ではありません。 is_arrayを配列セルポインターのis_arrayビットに保存します。

 template <typename T> using array_slot = marked_ptr<T*, 3 >; 

したがって、配列セルは単なるポインターであり、内部フラグには最後の2ビット（ marked_ptrマスク3）を使用します。「セルには次のレベルの配列へのポインターが含まれます」記号に1ビット、... ？..

挿入アルゴリズムをよく見てください。 ステップ3bおよび4bは、セルの分割、つまり、データを含むセルから基礎となる配列へのポインターを含むセルへの変換について説明しています。 そのような変換は、以下を必要とするため、非常に時間がかかります。

• 新しいnode_arrayを作成します。
• すべての要素のゼロ化。
• 分割されたセルデータの新しいnode_arrayで位置を見つける。
• 分割されたセルの見つかったデータ位置にある新しいnode_arrayに書き込みます。
• 最後に、新しい分割セル値を設定します

これらのすべてのアクションが実行されている間、分裂可能なセルは未定義の状態にあります。 2番目の最下位ビットでエンコードするのはこの状態です。 「セルが分割されています」というフラグを満たしたマルチレベルアレイ上のすべての操作は、このフラグでアクティブスピンを使用して、そのようなセルの分割が完了するのを待っています。


図では、黒のデータが追加されたキーDn 、青が既存のD


マルチレベル配列のデータ構造はシンプルで興味深いものですが、その機能（「欠陥」を書きたかったのですが、それでも機能です）は次のとおりです。

• 完全なハッシュが必要です。 理想的なハッシュ関数は、任意のキーk1およびk2に対してk1 != k2が異なるハッシュ値を与えるハッシュ関数hです： h(k1)!= h(k2) 。 つまり、マルチレベル配列は衝突を許可しません。
• 異なるサイズのキー（またはキーハッシュ）はサポートされていません。 つまり、可変長のstd::stringキーはビット文字列として使用できません。

ただし、キーのサイズが一定の場合（または理想的なハッシュ関数がある場合）、マルチレベル配列は非常に優れたロックフリーコンテナーであるIMHOです。

原則として、マルチレベル配列を一般化して衝突リストをサポートすることができます。このため、データの代わりにロックのないリストを衝突のリストとして使用するだけで十分です。 可変長キーの別の一般化：短いキーには、ビット文字列内の他のすべてのビットがゼロに等しいと仮定します。


ただし、この記事の目的上、マルチレベル配列の1つのプロパティが重要です。一度作成されたノード配列は削除されません。 そしてこれから強力な結果が得られます。 マルチレベル配列はスレッドセーフなイテレータをサポートし 、さらに、これらは双方向イテレータです。 実際、ノード配列は削除されないため、イテレーターはノード配列へのポインターに加えて、セルへの「ポインター」であるノード配列内のインデックスです。

 class iterator { guarded_ptr<T> gp_; node_array* node_; int node_index_; }; 

競合スレッドはイテレータが配置されているデータを削除できるため、ここでguarded_ptrが必要です。 guarded_ptr 、物理的な削除を防ぎます。 イテレータは、コンテナから削除された要素を指すことができることが判明しました。これは、ロックフリーデータ構造のもう1つの予期しないプロパティです。 しかし、慎重に考えると、このプロパティは理解できます。競争の激しいコンテナである絶えず変化する世界では、保証できるのは1つだけです。イテレータを配置する時点で、このセルには有効なデータが含まれていました。
node_へのnode_ポインターとその中のインデックスnode_index_ 、コンテナーの次（または前）の要素に移動するためにイテレーターで必要です。つまり、コンテナー内のイテレーターの現在の位置を実際に決定します。

ハッシュ値ではなく一定サイズのキーがある場合、マルチレベルの配列バイパスが順序付けられることに注意するのは興味深いことです。


要約すると、スレッドセーフなイテレータをサポートする競合するコンテナがまだあり、これらのコンテナの1つはマルチレベル配列です。 他にありますか？..多くの興味深いロックフリーマップの基礎となる反復可能なロックフリーリストを作成することは可能ですか？..

この質問に対する答えは次の記事にあります。