--- title: Split-Ordered lists: lock-free hash tables tags: #programming author: [kumagi](https://www.docswell.com/user/kumagi) site: [Docswell](https://www.docswell.com/) thumbnail: https://bcdn.docswell.com/page/GJ559X5LJ4.jpg?width=480 description: Split-Ordered lists: lock-free hash tables by kumagi published: April 12, 23 canonical: https://www.docswell.com/s/kumagi/5988JL-lock-free-hash-table --- # Page. 1 ![Page Image](https://bcdn.docswell.com/page/GJ559X5LJ4.jpg) Split-ordered lists: lock-free extensible hash tables O.Shalev and N.Shavit. In Journal of the ACM, 53(3):379-405,NY,USA,2006, ACM Press 論文紹介 Ｍ１ 熊崎宏樹 # Page. 2 ![Page Image](https://bcdn.docswell.com/page/9E2N2XN37R.jpg) 概要 複数のスレッドから並列にアクセスしても構造 が破壊されないハッシュテーブル  ロックを用いず高いスケーラビリティを実現  テーブルの拡張にもロックを用いない  # Page. 3 ![Page Image](https://bcdn.docswell.com/page/D7YPY8P87M.jpg) 既存研究  細粒度ロックハッシュテーブル ◦ DougLea氏によるバケット単位でのロックによる 並列ハッシュテーブル  Java6ではgetを楽観的ロック(成功時非ロック)にて行う 改良版をjava.util.ConcurrentHashMapとしてサポート ◦ 広く実用されている並列ハッシュとして比較対象  リニアハッシュテーブル ◦ ハッシュサイズを変更した際の影響範囲を最小 限に抑えるハッシュテーブル ◦ ハッシュテーブルアルゴリズムとしては比較的古 いけれどこれから紹介するものの先祖 # Page. 4 ![Page Image](https://bcdn.docswell.com/page/VEN5PQ59J8.jpg) 細粒度ロックハッシュテーブル  バケット単位でロックを行うハッシュマップ ◦ ロック対象バケットをハッシュで決定 ◦ リサイズは再帰的(?)にロックを獲得しながら行う  2003年発表Rev1.3, in JSR-166, the proposed Java Concurrency Package. ◦ 下図はストライプドロックハッシュテーブルの例 0 1 2 3 4 5 6 7 # Page. 5 ![Page Image](https://bcdn.docswell.com/page/Y79Y3DY3E3.jpg) 細粒度ロックハッシュテーブル  バケット単位でロックを行うハッシュマップ ◦ ロック対象バケットをハッシュで決定 ◦ リサイズは再帰的(?)にロックを獲得しながら行う  2003年発表Rev1.3, in JSR-166, the proposed Java Concurrency Package. ◦ 下図はストライプドロックハッシュテーブルの例 赤い鍵をロックした場合 0, 3, 6番のバケットがロック 0 1 2 3 4 5 6 7 黄色い鍵をロックした場合 1, 4, 7番のバケットがロック 青い鍵をロックした場合 2, 5番のバケットがロック # Page. 6 ![Page Image](https://bcdn.docswell.com/page/G786M36LJD.jpg) 細粒度ロックハッシュテーブル  同一のロックを持つスレッドは一度に一つしか存在し ない ◦ スレッドは同時に一つのロックしか持たないのでデッド ロックもしない ◦ データ保持量に対してロック数を増やす実装もありうる 赤い鍵をロックした場合 0, 3, 6番のバケットがロック 0 1 2 3 4 5 6 7 黄色い鍵をロックした場合 1, 4, 7番のバケットがロック 青い鍵をロックした場合 2, 5番のバケットがロック # Page. 7 ![Page Image](https://bcdn.docswell.com/page/L7L93V9QER.jpg) リニアハッシュテーブル ハッシュのリサイズ時に移動するアイテムを 最少に抑えるハッシュテーブル  これ自身は特に並列性への配慮は無し   並列化は可能だけどそれが主眼ではない  1997年発表  Sorted Linear Hash Table Thomas Wang, March 1997last update July 1997 Hash(x) mod 4 == 0 0 1 2 3 Hash(x) mod 4 == 1 Hash(x) mod 4 == 2 Hash(x) mod 4 == 3 # Page. 8 ![Page Image](https://bcdn.docswell.com/page/4EMZDGVK7W.jpg) リニアハッシュテーブル  例)ハッシュをリサイズして1だけ拡大する ◦ Modの係数を倍々で増やしていく ◦ 計算後の値が存在しないバケットを指すなら Modを1減らして計算した値を採用する Hash(x) mod 8 == 0 0 1 2 3 4 追加 Hash(x) mod 4 == 1 Hash(x) mod 4 == 2 Hash(x) mod 4 == 3 # Page. 9 ![Page Image](https://bcdn.docswell.com/page/PER64Z26J9.jpg) リニアハッシュテーブル  下の例では、新しく追加されたバケットに既存 のバケットからアイテムを移動させた Hash(x) mod 8 == 0 0 1 2 3 4 Hash(x) mod 8 == 1 or 5 Hash(x) mod 8 == 2 or 6 Hash(x) mod 8 == 3 or 7 Hash(x) mod 8 == 4 # Page. 10 ![Page Image](https://bcdn.docswell.com/page/P7XM29DDJX.jpg) リニアハッシュテーブル  下の例では、新しく追加されたバケットに既存 のバケットからアイテムを移動させた ◦ Mod 8に変わる事によって移動する必要が 生じたのはMod 4 == 0だったバケットのみ 移動不要 Hash(x) mod 8 == 0 0 1 2 3 4 Hash(x) mod 8 == 1 or 5 Hash(x) mod 8 == 2 or 6 Hash(x) mod 8 == 3 or 7 Hash(x) mod 8 == 4 # Page. 11 ![Page Image](https://bcdn.docswell.com/page/37KGMPXDED.jpg) Split-ordered Hashtable  リニアハッシュの概念から拡張し、ハッ シュサイズが変わっても一切のノード移 動が無いよう工夫  「バケットの間をアイテムが移動するので はなく、アイテムの間をバケットが移動す る」という文章が印象的  順を追って説明します # Page. 12 ![Page Image](https://bcdn.docswell.com/page/LJ3NYX5PJ5.jpg) Split-ordered list      すべてのアイテムを一つの線形リストに投入 線形リスト内はhash値で昇順に並んでいる バケットの先頭を表すSentinel ノードも同一の 線形リストに投入 Sentinelノードへのショートカットをテーブルとし て保持 ListはLockfreeListを使うため並列に操作して も壊れない ◦ 更に操作失敗時にiteratorが先頭に飛ぶ欠点を最寄 りのSentinelノードへ飛ぶように改善 # Page. 13 ![Page Image](https://bcdn.docswell.com/page/8JDW52D3EG.jpg) 概念図  一本の線形リストにデータとSentinelノードが両方入る ◦ 水色がデータ、緑色がハッシュ値 リストの中身はハッシュに沿って昇順  Sentinelノードはバケットの値をビット逆転した物を使う  ◦ 説明のためhash最大値は1byteにします 00000010 ↓ 01000000 00 0 1 2 3 02 40 48 00000001 ↓ 10000000 6d 7f 80 00000011 ↓ 11000000 8a c0 74 # Page. 14 ![Page Image](https://bcdn.docswell.com/page/VEP9G1XP78.jpg) データの挿入 1. 2. 対象となるデータのハッシュ値を算出 ハッシュ値に対応するテーブルにアクセス 図左の縦長のテーブル  3. テーブルにSentinelノードへのポインタが書いてあるため 対応するノードへジャンプ 図中の赤い線  4. Sentinelノードの指すポインタを手繰っていけばハッシュの 昇順にデータが並んでいるため、対応する場所に挿入 00 69 0 1 2 3 02 40 48 6d 7f 80 8a c0 74 # Page. 15 ![Page Image](https://bcdn.docswell.com/page/27VM6YLV7Q.jpg) テーブルの拡張  Sentinelノードの間に挟まるアイテムの数が一定数を 超えた場合にテーブルを拡張する ◦ リニアハッシュと違い必ず倍々オーダー  あらかじめテーブルはそれなりの広さが用意してあり、 コピー無しで拡張可能,そのためロック不要 ◦ それ以上の拡大は後述します 00 0 1 2 3 4 5 6 7 02 40 48 6d 69 7f 80 8a c0 74 # Page. 16 ![Page Image](https://bcdn.docswell.com/page/5JGGN9X1JL.jpg) テーブルの拡張 1. 2. テーブル拡張後は新規探索は新しいテーブル上で行う テーブル上に無かったらその一個左のSentinelノードを探索 ◦ もしそこにも無かったら更にもう一個左 3. 4. Sentinelノードが挿入されているべき個所を見つけ次第、 Sentinelノードを挿入する 目的の場所を見つけたら挿入 00 0 1 2 3 4 5 6 7 02 40 48 6d 69 7f 80 8a c0 74 # Page. 17 ![Page Image](https://bcdn.docswell.com/page/47QXQW8NJP.jpg) テーブルの拡張 テーブル拡張後は新規探索は新しいテーブル上で行う テーブル上に無かったらその一個左のSentinelノードを探索 1. 2. ◦ もしそこにも無かったら更にもう一個左 3. 4. 00 62 0 1 2 3 4 5 6 7 Sentinelノードが挿入されているべき個所を見つけ次第、 Sentinelノードを挿入する 目的の場所を見つけたら挿入 02 40 48 60 6d 69 7f 80 8a c0 74 # Page. 18 ![Page Image](https://bcdn.docswell.com/page/KE46NK23J1.jpg) なぜリサイズがLockfreeなのか  検索中のスレッドが他のスレッドに追い抜かれ ても処理が続行可能 ◦ 新しいアイテムが挿入されようと ◦ Sentinelノードが挟まろうと ◦ ハッシュテーブルが拡張されようと ◦ ハッシュ値が一つの線形リスト上で昇順に並んでいる事 に変わりは無い 00 0 1 2 3 02 40 48 6d 7f 80 8a c0 74 # Page. 19 ![Page Image](https://bcdn.docswell.com/page/L71V5XMZJG.jpg) テーブルのリサイズ  もし確保しておいたテーブルサイズで足りなくなったら ◦ 必要なだけ新しい配列を確保してアサイン  左の配列は充分大きい  2段階間接参照のためオーバーヘッドはある 00 0 1 2 3 4 5 6 7 0 02 1 40 2 3 48 4 6d 5 6 7f 7 80 8 8a c0 74 9 10 11 12 13 14 16 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 21 22 23 24 25 26 27 28 29 30 31 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 # Page. 20 ![Page Image](https://bcdn.docswell.com/page/G7WL5N36J2.jpg) 性能評価  Java実装のDougLea式の並列Hashmapを C++に移植して比較 ◦ ロックは64に固定（それ以上増やしてもパフォーマン スが改善しなかったため  Split-ordered listもC++で実装  計算機 ◦ 30-processor Sun Enterprise 6000, a cache-coherent NUMA machine formed from 15 boards of two 300 MHz UltraSPARC® II processors and 2 GB of RAM on each.  コンパイラ ◦ a Sun cc compiler 5.3, -xO5 and -xarch=v8plusa # Page. 21 ![Page Image](https://bcdn.docswell.com/page/4JZMN3VR73.jpg) DougLea式ハッシュテーブル ロックを64以上増やしても性能が伸びなかったというグラフ # Page. 22 ![Page Image](https://bcdn.docswell.com/page/YE6N8X51EV.jpg) 二つのハッシュテーブルの比較 # Page. 23 ![Page Image](https://bcdn.docswell.com/page/GE559XYLE4.jpg) 二つのハッシュテーブルの比較 •DougLea式は24スレッドでピーク •新アルゴリズムは44スレッドでピーク •8スレッド以下の環境ではDougLea式のほうが高速 •新アルゴリズムはスケーラビリティに優れる •多スレッド時の速度がばらつくのはネットワークや並列マシン上で のスレッド配置が影響を与えるようになったから # Page. 24 ![Page Image](https://bcdn.docswell.com/page/972N2XG3JR.jpg) 利用パターンによる性能差 # Page. 25 ![Page Image](https://bcdn.docswell.com/page/DJYPY8V8JM.jpg) 利用パターンによる性能差 左から右にかけて、検索の割合が減ってい き削除の割合が増えていくテストケース  スレッド数が少ない場合を除く全ての場面 で新アルゴリズムが倍以上高速  # Page. 26 ![Page Image](https://bcdn.docswell.com/page/V7N5PQM9E8.jpg) まとめ Split-orderedなLockfreeListによる並列ハッ シュマップを提案  一般に使われている物よりスケーラビリティに 優れる  8コアまでならDougLea式の方が高速  # Page. 27 ![Page Image](https://bcdn.docswell.com/page/YJ9Y3DN373.jpg) 感想     DougLea式はJavaのメモリモデルを上手く利用していたのでそれ をどのようにC++に移植したのか興味深い（愚直にやると Segmentation Faultしてしまう 大規模計算機上でのみ真価を発揮するアルゴリズムかっこいい Lock-freeの利点は進行保証やリアルタイム性にも有るので価値 のあるアルゴリズムだと思った この論文を引用している論文を探したけれど比較対象として挙げ ている論文は見つからなかった。（実装が大変だから…？） # Page. 28 ![Page Image](https://bcdn.docswell.com/page/GJ86M3KLED.jpg) 他に読んだ論文  "A Pragmatic Implementation of Non-Blocking Linked-Lists" Timothy L. Harris ◦ CASベースのLock-freeな線形リスト  "Lock-Free Linked Lists and Skip Lists" Mikhail Fomitchev, Eric Ruppert ◦ 1本目の論文の改良版。CAS失敗時に線形リストの先頭まで 戻ってしまう欠点を補うため、削除操作をマーキング→削除の2 段階ではなくマーキング→直前ノードのポインタアサイン→削 除の3段階に分割したもの ◦ LockfreeSkipListはそれを利用して構成するようだけど差がよ く分からなかった ◦ 性能評価が無かったため紹介せず # Page. 29 ![Page Image](https://bcdn.docswell.com/page/LJL93VZQ7R.jpg) 他に読んだ論文  "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms“ Philippas Tsigas, Yi Zhang. 2001 ◦ Lockfree queueの論文。Enque操作を「末尾に繋げる」「tailポ インタを更新する」の2ステップに分割し、末尾に繋げる瞬間を 線形化ポイントとして定義し、2ステップ目を他のスレッドや Deque操作側で手伝うようにした画期的なQueue。同一の実 装がBoost.lockfree.fifoとして提案され現在レビュー中。  Software transactional memory for dynamic-sized data structures Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer 2003 ◦ HTMの生みの親であるMaurice氏がSTMについて書いた初め の論文。トランザクションマネージャーやグローバルロックが出 てきた辺りで中断。 # Page. 30 ![Page Image](https://bcdn.docswell.com/page/47MZDG4KJW.jpg) 他に読んだ論文  Transactional Memory Today: A Status Report Maurice Herlihy Conference: International Conference On Principles Of DIstributed Systems - OPODIS 2009 ◦ Maurice氏が自分へのCitationの増加も含め HTM,STMの最近のトピックをおさらいしている  Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects Maged M. Michael IEEE TRANSACTIONS 2004 ◦ CASベースのLockfreeデータ構造で常に問題にな るABA問題に対して、GCの考え方を取り入れて、 ハードウェア機能を利用したタグによるABA回避並 に効率的かつそれ以上に安全にオブジェクトの寿命 を管理する方法。実装でポインタ群を配列に入れて 2分探索する辺りから追えなくなった。 # Page. 31 ![Page Image](https://bcdn.docswell.com/page/P7R64ZW6E9.jpg) 他に読んだ論文  Lock-Free Data Structures Andrei Alexandrescu ,2007 ◦ WRRM(Write Rarely Read Many)な使用パターン においてはstd::mapなどの非並列データ構造を動 的に確保し、それへのポインタを経由して参照し、 データを追加・削除する際には全てコピーした上で 変更を加えた新しいポインタへCASすると良いよ、と いう論文（?） ◦ Segmentation Faultしないためにはオブジェクトの 寿命管理にはGCが妥当で、GCを用いた場合削除 や上書きの操作の線形一貫性は保たれないだろう けれど、これで充分な場面に適用するならとても簡 単に実装できるのでお勧め、という主張。