Split-Ordered lists: lock-free hash tables

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 論文紹介 Ｍ１ 熊崎宏樹

概要 複数のスレッドから並列にアクセスしても構造 が破壊されないハッシュテーブル  ロックを用いず高いスケーラビリティを実現  テーブルの拡張にもロックを用いない 

既存研究  細粒度ロックハッシュテーブル ◦ DougLea氏によるバケット単位でのロックによる 並列ハッシュテーブル  Java6ではgetを楽観的ロック(成功時非ロック)にて行う 改良版をjava.util.ConcurrentHashMapとしてサポート ◦ 広く実用されている並列ハッシュとして比較対象  リニアハッシュテーブル ◦ ハッシュサイズを変更した際の影響範囲を最小 限に抑えるハッシュテーブル ◦ ハッシュテーブルアルゴリズムとしては比較的古 いけれどこれから紹介するものの先祖

細粒度ロックハッシュテーブル  バケット単位でロックを行うハッシュマップ ◦ ロック対象バケットをハッシュで決定 ◦ リサイズは再帰的(?)にロックを獲得しながら行う  2003年発表Rev1.3, in JSR-166, the proposed Java Concurrency Package. ◦ 下図はストライプドロックハッシュテーブルの例 0 1 2 3 4 5 6 7

細粒度ロックハッシュテーブル  バケット単位でロックを行うハッシュマップ ◦ ロック対象バケットをハッシュで決定 ◦ リサイズは再帰的(?)にロックを獲得しながら行う  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番のバケットがロック

細粒度ロックハッシュテーブル  同一のロックを持つスレッドは一度に一つしか存在し ない ◦ スレッドは同時に一つのロックしか持たないのでデッド ロックもしない ◦ データ保持量に対してロック数を増やす実装もありうる 赤い鍵をロックした場合 0, 3, 6番のバケットがロック 0 1 2 3 4 5 6 7 黄色い鍵をロックした場合 1, 4, 7番のバケットがロック 青い鍵をロックした場合 2, 5番のバケットがロック

リニアハッシュテーブル ハッシュのリサイズ時に移動するアイテムを 最少に抑えるハッシュテーブル  これ自身は特に並列性への配慮は無し   並列化は可能だけどそれが主眼ではない  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

リニアハッシュテーブル  例)ハッシュをリサイズして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

リニアハッシュテーブル  下の例では、新しく追加されたバケットに既存 のバケットからアイテムを移動させた 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

リニアハッシュテーブル  下の例では、新しく追加されたバケットに既存 のバケットからアイテムを移動させた ◦ 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

Split-ordered Hashtable  リニアハッシュの概念から拡張し、ハッ シュサイズが変わっても一切のノード移 動が無いよう工夫  「バケットの間をアイテムが移動するので はなく、アイテムの間をバケットが移動す る」という文章が印象的  順を追って説明します

Split-ordered list      すべてのアイテムを一つの線形リストに投入 線形リスト内はhash値で昇順に並んでいる バケットの先頭を表すSentinel ノードも同一の 線形リストに投入 Sentinelノードへのショートカットをテーブルとし て保持 ListはLockfreeListを使うため並列に操作して も壊れない ◦ 更に操作失敗時にiteratorが先頭に飛ぶ欠点を最寄 りのSentinelノードへ飛ぶように改善

概念図  一本の線形リストにデータとSentinelノードが両方入る ◦ 水色がデータ、緑色がハッシュ値 リストの中身はハッシュに沿って昇順  Sentinelノードはバケットの値をビット逆転した物を使う  ◦ 説明のためhash最大値は1byteにします 00000010 ↓ 01000000 00 0 1 2 3 02 40 48 00000001 ↓ 10000000 6d 7f 80 00000011 ↓ 11000000 8a c0 74

データの挿入 1. 2. 対象となるデータのハッシュ値を算出 ハッシュ値に対応するテーブルにアクセス 図左の縦長のテーブル  3. テーブルにSentinelノードへのポインタが書いてあるため 対応するノードへジャンプ 図中の赤い線  4. Sentinelノードの指すポインタを手繰っていけばハッシュの 昇順にデータが並んでいるため、対応する場所に挿入 00 69 0 1 2 3 02 40 48 6d 7f 80 8a c0 74

テーブルの拡張  Sentinelノードの間に挟まるアイテムの数が一定数を 超えた場合にテーブルを拡張する ◦ リニアハッシュと違い必ず倍々オーダー  あらかじめテーブルはそれなりの広さが用意してあり、 コピー無しで拡張可能,そのためロック不要 ◦ それ以上の拡大は後述します 00 0 1 2 3 4 5 6 7 02 40 48 6d 69 7f 80 8a c0 74

テーブルの拡張 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

テーブルの拡張 テーブル拡張後は新規探索は新しいテーブル上で行う テーブル上に無かったらその一個左の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

なぜリサイズがLockfreeなのか  検索中のスレッドが他のスレッドに追い抜かれ ても処理が続行可能 ◦ 新しいアイテムが挿入されようと ◦ Sentinelノードが挟まろうと ◦ ハッシュテーブルが拡張されようと ◦ ハッシュ値が一つの線形リスト上で昇順に並んでいる事 に変わりは無い 00 0 1 2 3 02 40 48 6d 7f 80 8a c0 74

テーブルのリサイズ  もし確保しておいたテーブルサイズで足りなくなったら ◦ 必要なだけ新しい配列を確保してアサイン  左の配列は充分大きい  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

性能評価  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

DougLea式ハッシュテーブル ロックを64以上増やしても性能が伸びなかったというグラフ

二つのハッシュテーブルの比較

二つのハッシュテーブルの比較 •DougLea式は24スレッドでピーク •新アルゴリズムは44スレッドでピーク •8スレッド以下の環境ではDougLea式のほうが高速 •新アルゴリズムはスケーラビリティに優れる •多スレッド時の速度がばらつくのはネットワークや並列マシン上で のスレッド配置が影響を与えるようになったから

利用パターンによる性能差

利用パターンによる性能差 左から右にかけて、検索の割合が減ってい き削除の割合が増えていくテストケース  スレッド数が少ない場合を除く全ての場面 で新アルゴリズムが倍以上高速 

まとめ Split-orderedなLockfreeListによる並列ハッ シュマップを提案  一般に使われている物よりスケーラビリティに 優れる  8コアまでならDougLea式の方が高速 

感想     DougLea式はJavaのメモリモデルを上手く利用していたのでそれ をどのようにC++に移植したのか興味深い（愚直にやると Segmentation Faultしてしまう 大規模計算機上でのみ真価を発揮するアルゴリズムかっこいい Lock-freeの利点は進行保証やリアルタイム性にも有るので価値 のあるアルゴリズムだと思った この論文を引用している論文を探したけれど比較対象として挙げ ている論文は見つからなかった。（実装が大変だから…？）

他に読んだ論文  "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はそれを利用して構成するようだけど差がよ く分からなかった ◦ 性能評価が無かったため紹介せず

他に読んだ論文  "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について書いた初め の論文。トランザクションマネージャーやグローバルロックが出 てきた辺りで中断。

他に読んだ論文  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分探索する辺りから追えなくなった。

他に読んだ論文  Lock-Free Data Structures Andrei Alexandrescu ,2007 ◦ WRRM(Write Rarely Read Many)な使用パターン においてはstd::mapなどの非並列データ構造を動 的に確保し、それへのポインタを経由して参照し、 データを追加・削除する際には全てコピーした上で 変更を加えた新しいポインタへCASすると良いよ、と いう論文（?） ◦ Segmentation Faultしないためにはオブジェクトの 寿命管理にはGCが妥当で、GCを用いた場合削除 や上書きの操作の線形一貫性は保たれないだろう けれど、これで充分な場面に適用するならとても簡 単に実装できるのでお勧め、という主張。