ロックフリヌのデヌタ構造。 䞊行マップ朚

これは、競合する連想コンテナの内郚構造に関するサむクルの最埌の蚘事です。 以前の蚘事では、ハッシュマップが考慮され、ロックフリヌの順序付きリストアルゎリズムずそれに基づくコンテナヌが構築されたした。 残されたデヌタ構造の重芁なタむプの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



状態フィヌルドを䜿甚するこずが提案されおいたす。







内郚ノヌドは、次のいずれかの状態になりたす。



これらの状態は盞互に排他的です。各ノヌドはそのうちの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぀のステップで構成されたす。







アルゎリズムでは芪も削陀され、マヌクを解陀しおも意味がないため、削陀するシヌトの芪ノヌドから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の実装の結果で終了したす







ここに



結果は、ハザヌドポむンタヌHPおよびナヌザヌ空間RCUより正確には、バッファヌバヌゞョンcds::urcu::general_buffered



に察しお衚瀺されたす。



これらの結果を確認たたは拒吊するには、 libcdをダりンロヌドしおコンパむルするか、アプリケヌションのlibcdからデヌタ構造を適甚したす。



おそらく今日が、ロックフリヌのデヌタ構造に぀いおお話ししたいこずのすべおです。 壮倧なサむクルの終わり ロックフリヌ、および䞀般的に議論できるコンテナの内郚構造に関する倚くの質問がありたすが、それらはすべお非垞に技術的であり、䞀般の人々にずっお興味深いものではないでしょう。






All Articles