Cache Craftiness for Fast Multicore Key-Value Storage

Cache Craftiness for Fast Multicore Key-Value Storage EuryoSys’12 Yandong Mao, Eddie Kohler, Robert Morris この説明資料を作った人: @kumagi

概要 • B+ treeをマルチコア環境向けに高速化した物 – キャッシュ効率に配慮したデータレイアウト – 楽観的並行制御 • 読み出しスレッドがキャッシュを汚さない • 読み出しスレッド同士は衝突しない – 挿入操作が読み出しスレッドを邪魔しない – 永続化もする • 16コアでmemcachedに匹敵する性能が出た – ちゃんと永続化しても性能が出る点が偉い

キャッシュ効率に配慮した データレイアウト • trie of B+tree と表現するデータ構造を取る – パフォーマンスが出て、可変長キーにも対応できる ナイーブなB+tree internal node leaf node struct internal_node { std::string key[15]; node* child[16]; }; key2 key1 key4 key3 key5 key6 key8 MassTree 間接参照 遅い！！ cmp命令で OK！ struct internal_node { uint64_t key[15]; node* child[16]; }; key key7 多いので省略 fanout大きくし過ぎた…

キャッシュ効率に配慮した データレイアウト • uint64_t をkeyとしたB+treeを複数階層作る – 1層目はキーの1～8byte目に対応 – 2層目はキーの9～16byte目に対応 – 中途半端な長さのkeyは0でパディングする • leaf nodeは、次の層へのポインタとその長さのkeyまでの値に対応するvalueの unionを持つ。 – ほら、trieに見えてきただろう？ 1～8byte 9～16byte 17～24byte

キャッシュ効率に配慮した データレイアウト • 2層目で同じB+treeに入っているデータは1層目の1～8バイトが完全一致 しているデータのみ • 例えば72byteのキーが挿入されたら9階立てのTrie of B+treeができる – 厳密には65byte目以降が異なる2つ目のkeyが挿入された瞬間に生成される が詳細は次のページ • この構造を採用する事で13～19%の高速化に成功したと主張 1～8byte 9～16byte 17～24byte

データレイアウト詳細 • leaf_nodeにはkeysuffixというメンバが入っていて、その層に収まら ない長さのkeyを先着1つだけ保存する事で、下の層を作るタイミン グを遅らせて高速化している（2つ目が挿入されるタイミングで諦め て下の層のB+treeを作成する） • uint64_tに強制的に落としてしまうと、バイナリ値としての ’\0’ と文 字列末尾の ‘\0’ が見分けをつけられないので、バイナリの長さは 別で保存する • 値が削除されて要素が減ってもsplitされたものはmergeしない – 速度面とシンプルさ両方で利点があると主張 • 末尾挿入の場合に限りsplitではなく親ノードに要素数1の新border nodeを挿入する最適化を適用 – splitはデータ移動が伴うけど、新規ノードを末尾に足すだけなら移動 が要らない＝既存ノードのキャッシュが汚れない&lockが要らない

中間ノード構造体 • B+ treeの繋ぎを為すデータ構造 複雑なので後で話す struct interior_node { 入っているキーの総数 uint32_t version; uint8_t nkeys; キーの値、nkeysだけ使われている uint64_t keyslice[15]; node* child[16]; 次のノードへのポインタ、nkeys+1個使われている node* parent; }; 親ノードへのポインタ sizeof(interior_node) == 261 およそキャッシュライン4本分、実測上一番パフォーマンスが出た、とのこと

リーフノード構造体 • B+ treeの値を保持する構造体 複雑なので後で話す struct border_node { 消されたキーの数 uint32_t version; uint8_t nremoved; n番目のキーの長さ uint8_t keylen[15]; uint64_t permutation; 複雑なので次のページで話す uint64_t keyslice[15]; n番目のキー link_or_value lv[15]; border_node* next; 次のB+treeへのポインタ、もしくは値への border_node* prev; ポインタ。どちらを意味しているかは keylen[n]の最上位ビットでスイッチ node* parent; keysuffix_t suffix; 左右及び親へのポインタ }; keysuffixのサイズはadaptivelyに決定するらしいので それを除くと残りのサイズは286byte、こちらもおよそキャッシュ4本分

permutation • readとinsertが衝突しても動く鍵となる機構 – 実体はノード当たり1つのuint64_t uint64_t 4bit が16個、と見做すと、0～15まで数えられるintが16個 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 keyslice[14]の順位 keyslice[0]の順位 keyslice[1]の順位 nkeys

permutation • key配列の順位は8byte整数なのでatomicに書き換えられる – keysliceに加えた末尾の値を含む論理順序を更新 – 末尾への挿入は古いpermutationを参照しているReaderからは見え ない c z k e d b c z k e d 5 4 3 2 6 1 0 7 keyslice[15] permutation 5 4 3 2 1 0 6 メモリバリア の後にmov a b a keyslice[15] permutation

permutation • Insert操作は「最後」にpermutationを更新する • Readerは「最初」にpermutationをローカルに複 製する • よってInsertの前か後のどちらかのkeyslice配列 だけがReaderから見える • つまりReaderとInsertが並行しても大丈夫！ • Erase操作はpermutationを更新する – メモリは別個ガベコレへ • なお、Writer同士は普通にLockで排他する

version