ロックフリーのデータ構造。 並行マップ：木

これは、競合する連想コンテナの内部構造に関するサイクルの最後の記事です。 以前の記事では、ハッシュマップが考慮され、ロックフリーの順序付きリストアルゴリズムとそれに基づくコンテナーが構築されました。 残されたデータ構造の重要なタイプの1つは、ツリーです。 それらについて少し話す時間です。

外部からのアクセスの同期を必要としない競合ツリーアルゴリズムに関する研究は、かなり前に（前世紀の70年代に）始まり、DBMSの開発によって開始されたため、主にページツリーの最適化（ Bツリーとその修正）に関連していました。

2000年代初頭のロックフリーアプローチの開発はツリーアルゴリズムを通過しませんでしたが、最近になってようやく、2010年代に、競合するツリーに関する多くの興味深い研究が登場しました。 ツリーアルゴリズムは非常に複雑であるため、研究者は、適応をロックフリー/ノンブロッキングにするのに約10年かかりました。 この記事では、最も単純なケース、つまり自己バランスでさえない通常のバイナリツリーについて検討します。

順序付けられたデータでは、このようなツリーはO（N）の検索の複雑さで線形リストに縮退することを知っているので、通常のバイナリツリーの実際の意味は何ですか？ 主なポイントは、単純なデータ構造でアプローチをテストすることです。 さらに、ランダムデータの場合、バイナリツリーは非常にうまく機能し、O（log N）の複雑さを提供し、その内部の単純さが高効率の鍵となります。 そのため、そのようなツリーが使用されるタスクにすべて依存します。

そもそも-ロックフリー/ノンブロッキングツリーを構築する問題の回顧展 キューおよびリストに対してかなり効率的なロックフリーアルゴリズムが見つかった後、ロックフリーセルフバランシングツリー-AVLツリー、赤黒ツリーに作業が登場しました。 これらのアルゴリズムの擬似コードは複雑だったので、実装したくありません。たとえば、メモリ管理スキームを適用する方法（ハザードポインター、RCUなど）を理解できないため、アルゴリズムはガベージコレクターに依存していました。 （GC）言語、通常はJava。 さらに、CASプリミティブ（比較とスワップ）を使用してツリー内のキーを見つけるアルゴリズムは実装しません。CASはこれには重すぎます。 そして一般に、そのようなアルゴリズムの正当性の正式な証明にもかかわらず（GCの存在下ではこの予約が不可欠であり、GCの不在は証明に違反する可能性があります）、その複雑さ、多くの境界ケースの存在は、デバッグの観点から私には乗り越えられないようでした。

どうやら、私だけでなく、開発者によると、結果として得られるツリーのロックフリーアルゴリズムの非効率性が複雑さを恐れていました。 そのため、2010年代の初めに、アルゴリズムの開発の重点がいくぶん変化しました。何らかの手段でロックフリーを提供する代わりに、ツリー検索操作の効率が最優先される多くの作業が現れ始めました。 実際、ツリーは主に検索タスクで使用され（検索は操作の70〜90％であると考えられています）、高速である必要があるのは検索です。 したがって、検索がロックフリーで、ノードのグループのレベルで挿入/削除をロックできる非ブロックアルゴリズムが登場しました（細粒度ロック）-ミューテックスを明示的に使用するか、フラグなどを暗黙的に使用します。それは本質的に回転しています。 このアプローチにより、より複雑で理解しにくいアルゴリズムが得られました。そのうちの1つを検討します。

バイナリ検索ツリー

データがリーフに配置され、内部ノードがルートであり、キーのみを含むツリーを検討します。



これは、いわゆるリーフ指向のツリーです。 内部ノードに目的のキーが存在するということは、キーがツリーに存在することを意味するものではありません。リーフにはキーと対応するデータのみが含まれ、内部ノードにはリモートキーが含まれます。

このようなツリーでは、各ノードには正確に2つの子孫があります。 このようなツリーに挿入すると、常に1つのシートと1つの内部ノードが生成され、キーが削除されると、1つのシートとその親である1つの内部ノードが削除されます。 バランスは提供されません。

競合する操作を実行する際に、どのような驚きが待っているかを考えてください。 特定のツリーがあり、フローAとBがそれぞれキー15と27を削除するとします。



キー15を削除するストリームAは、このキーとその親であるシート、キー20を持つ内部ノードを削除する必要があります。これを行うには、右側のリンクを祖父-ノード10-からノード20から削除されたノードの兄弟であるノード30に変更します。 競合ツリーを検討しているため、この操作はアトミックに、つまりCAS（compare-and-swap）を使用して実行する必要があります。

同時に、スレッドBはキー27を削除します。上記と同様に、スレッドBはノード20（祖父27）の右リンクを介して30からシート45にCASをスローします。

これらの2つのアクションが並行して実行される場合、結果として、到達可能なノード30と到達可能なリーフ27が取得されますが、これらは削除する必要があります。

競合する削除と挿入を実行する場合、状況は同様です。



ここで、キー27でシートを削除するスレッドAは、新しいキー29を挿入するスレッドBと競合します。27（およびその親である内部ノード30）を削除するには、スレッドAはノード20の右息子のポインターを30から45に反転します。時間が経過すると、キー29と対応する内部ノード29がノード30の左息子として、スレッドAがキー27を削除する位置と同じ位置に挿入されます。その結果、新しいキーは到達不能になります-メモリリーク。

明らかに、CASプリミティブだけでは上記のケースを解決できません。 挿入/削除する前に、何らかの方法で操作に関係するノードをマークする必要があります。 挿入ノードには、リーフノードとその親である内部ノードが含まれます。 挿入を実行する前に、このノードで競合する挿入/削除を実行できないように、親ノードを「挿入が実行されています」とマークする必要があります。 削除操作には、削除されたシート、その親、およびその親の親（削除されたシートの祖父）が含まれます。 両方の内部ノード（親と祖父）も、それらの競合を除外するようにマークする必要があります。

このペーパーでは、内部ノードごとにState状態フィールドを使用することが提案されています。



内部ノードは、次のいずれかの状態になります。

• Clean -ノードで挿入または削除は実行されません。 これがデフォルトのノード状態です。
• IFlagノードに対して挿入が実行されます。 このフラグは、少なくとも1人の息子が葉である内部ノードをマークします。
• DFlag除去がDFlagです。 このフラグは、削除するシートの内部祖父をマークします。
• Mark -内部ノードが削除されます。 このフラグは、削除するシートの親をマークします（ツリーでは、シートが削除されると、その親も削除されることに注意してください）。

これらの状態は相互に排他的です。各ノードはそのうちの1つのみに存在できます。 ノードの状態の変更は、CASプリミティブによって実行されます。
私たちの主な目標は、ツリー内のキー検索操作の最も効率的な実装であることを思い出してください。 これらの条件は検索にどのように影響しますか？ 明らかに、検索中に挿入操作と対応するIFlagフラグは無視できます。挿入時には削除は行われません。つまり、「制限されたリモートゾーンに入る」ことができません。 ただし、 DFlagおよびMarkフラグは検索に影響を与える必要があります。これらのフラグのいずれかでノードに到達すると、検索を最初から再開する必要があります（ここでアクションを変更できますが、最も簡単なのは検索を再開することです）。

そこで、キー29の挿入の例でこれらの状態がどのように機能するかを見てみましょう。



挿入ノードを見つけます-これは内部ノード30です。まず、ノード30のIFlag状態をCASプリミティブに設定します。 ここでCASは、競合状態の操作を除くClean状態からIFlag状態にのみ切り替えることを保証します。つまり、ノード30の排他的所有者になります。次に、内部ノード27を作成し、息子を既存のシート27と新しい29に割り当てます。ノード30の左の息子のポインターを新しく作成された内部ノード27に変更します。ここでCASが必要なのは、通常のアトミックストアを省くことができるからですか？ 答えは元のアルゴリズムでは不可能です。libcdsの実装では、アトミックストアを使用できます。これについては後で説明します。 そして最後に、3番目のステップ：ノード30からIFlagフラグを削除します。CASは元のアルゴリズムでもここで使用されます。CASは非常に必要でないものを拒否する場合、アトミックストアに置き換えることができます。

Stateフラグを使用した削除操作は、4つのステップで構成されます。

• CASを使用して、削除されたシートの祖父にDFlag状態をマークする
• 削除するシートMark親を「CASとしてMark状態でMarkします。
• 祖父ノードの子孫にCAS'omポインターを投げる
• 祖父からDFlagます。 ここではCASが使用されますが、アルゴリズムをいくらか簡略化してより単純なアトミックストアを使用できます

アルゴリズムでは親も削除され、マークを解除しても意味がないため、削除するシートの親ノードからMarkマークを削除しないことに注意してください。

競合削除の場合にフラグがどのように機能するかを見てみましょう。 状態フラグがなければ、キー15と27の競合除去により、先ほど見たように、削除されたシートに到達しました。



ステータスフラグには次のものがあります。



ストリームAがノード10でDFlagフラグを設定した場合、27を検索するときにストリームBがノード10より先に進まないように思われます。しかし、並行して実行される操作があるため、 DFlagフラグ。 次に、ノード20で競合が発生します。ストリームAはMarkでフラグを立て、ストリームBはDFlagフラグをDFlagます。 ノードの状態はClean状態からアトミックCASによって設定されるため、スレッドの1つだけがこの戦いに勝ちます。 スレッドAが勝った場合、つまりMarkフラグで20をマークできた場合、スレッドBは削除されたノード27の先頭から検索を開始し、Aが15を削除してからDFlagフラグを10から削除します。 10からラベルを削除し、ノード15の検索を繰り返します。どちらの場合も、キーの削除は最終的に成功し、ツリー構造に違反しません。

ご覧のとおり、状態フラグは、削除されたノードへの排他的アクセスを提供する内部ミューテックスの役割を果たします。 フラグが削除されたとき、つまりノードがClean状態になったときにCASプリミティブをアトミックストアに置き換えることの許容性に関するヒントを明確にするために残っています。

元のアルゴリズムは、ノードで競合を検出するときに相互支援（支援）フローを使用します。 このため、ステータスフラグに加えて、内部ノードには実行中の操作（挿入または削除）へのハンドルが含まれる場合があります。 Clean以外のノード状態を検出した競合するストリームは、この記述子を読み取って、対応する相手が操作を実行するのを助けることができます。 この場合、操作の終了時のClean状態への移行はCASプリミティブによってのみ行われる必要があります。これは、複数のスレッド（操作の開始者とヘルパー）がノードの状態をClean変換できるためです。 これをアトミックストアにすると、 Cleanステートになってから他の後続の挿入/削除操作に移行したノードが、レイトアシスタントによって再びCleanに転送される場合があります。

相互支援の受信は、擬似コードでは良好に見えますが、実際にはそれからあまり利益を得ていません。 さらに、ガベージコレクターがないC ++では、この手法を実装することは事実上非常に問題があります：記述子の割り当て方法（スタック上？Alloc？プール？）の問題がすぐに発生し、さらに深刻です-そのような記述子の寿命について（参照カウント？）。 実装では、libcdsの支援は無効になっています。実装するためのいくつかの試みは失敗しました-コードは不安定です（マネージャーの語彙からのこの美しいフレーズは、プログラムがクラッシュすることを意味します）。 そのため、libcdsのバイナリ検索ツリーアルゴリズムには、ノードの状態をCleanに変換するときにアトミックストアの代わりにCASを含むいくつかのアーティファクトが含まれます。これは将来削除します。

おわりに

この記事では、最も単純なバイナリツリーのアルゴリズムについて説明します。 バランスが取れていないにも関わらず、AVLツリーやRed-Blackツリーなどのより複雑で自己バランスのとれたツリーの実装に向けた最初のステップであるという理由だけでアルゴリズムが興味深い場合、それらをすぐにlibcdsに提出したいと考えています。

並行マップに関する一連の記事を、libcd（Intel Dual Xeon X5670 2.93 GHz 12コア24スレッド/ 24 GB RAM、平均要素数-100万、キー-int）の実装の結果で終了します：



ここに：

• MichaelMapは、リヘイジングのない最も単純なハッシュマップです。ここでレビューします
• SplitListMap- 分割順序リストアルゴリズム
• SkipListMap- スキップリストアルゴリズム
• BinTree-この記事で説明したバイナリツリー
• std :: map、std :: unordered_map-stdのSTLアルゴリズム:: mutex

結果は、ハザードポインター（HP）およびユーザー空間RCU（より正確には、バッファーバージョンcds::urcu::general_buffered ）に対して表示されます。

これらの結果を確認または拒否するには、 libcdをダウンロードしてコンパイルするか、アプリケーションのlibcdからデータ構造を適用します。

おそらく今日が、ロックフリーのデータ構造についてお話ししたいことのすべてです。 壮大なサイクルの終わり！ ロックフリー、および一般的に議論できるコンテナの内部構造に関する多くの質問がありますが、それらはすべて非常に技術的であり、一般の人々にとって興味深いものではないでしょう。