DEIM Forum 2017 P1-1

並行実行木 Masstree の調査渡辺 敬之†

川島 英之††

建部修見††† 筑波大学情報学群情報科学類 〒 305–8571 茨城県つくば市天王台 1–1–1†† 筑波大学計算科学研究センター 〒 305–8571 茨城県つくば市天王台 1–1–1
E-mail: †watanabe@hpcs.cs.tsukuba.ac.jp, ††{kawasima,tatebe}@cs.tsukuba.ac.jp
あらまし

本論文では並行実行木 Masstree の一括挿入法を提案する．提案技法は 16 スレッドを用いた場合，既存手法に比べて 2.48 倍の高性能化を達成した．
キーワード 索引，並行実行制御，Masstree

1. 序論

タ構造である．264 のファンアウトを持つトライ木であり，トライ木のそれぞれのノードが B+木で構成されている．トライ

複 数 の ス レッド が 同 一 の デ ー タ 構 造 に ア ク セ ス し て木は prefix を共有させることによって長いキーを効率良く探索

READ/WRITE 検索を行うとき，並行データ構造が必要にすることができる．一方，B+木は短いキーに対してはとてもなる．並行データ構造において最も直観的な方式は全体を停止効率が良い．よってどちらの側面も持っている Masstree はよ

させ，高々1 つのスレッドだけにデータ構造へのアクセスを許り効率良く探索を行える．

す手法である．この手法はマルチコアやメニーコアが常識である現代において不適である．

言い換えると，Masstree は一つ以上のレイヤーから成る B+木で構成されている．それぞれのレイヤーは異なった 8 バイト

効率的な並行データ構造として，2012 年に EuroSys 会議でに区切られたキーによってインデックスされている．図 1 にこ発表された Masstree [4] がある．この論文では，Masstree が前の例を示す．トライ木のルートノードであるレイヤー 0 には各述の全体停止を行わず，複数のスレッドが並行的にデータ構造キーの 0-7 バイトの部分がインデックスされている．さらに 1へアクセスしても，性能が 16 スレッドまでスケールアップすつ下のレイヤー 1 には各キーの 8-15 バイトの部分がインデッることが示されている．Masstree は効率的な楽観的並行実行クスされている．次に深いレイヤー 2 では各キーの 16-23 バイ制御手法 Silo [6] で導入され，不揮発メモリを前提とした高性トの部分がインデックスされるというように以下同様に続いて

能 OLTP システム FOEDUS [2] にアイディアが用いられておいく．つまり同じ h レイヤーにインデックスされているキー同り，現代の高性能トランザクション処理システムの基礎の一つ士は同じ 8h バイトの prefix を持っているということである．

だと考えられる．

それぞれのレイヤーには 1 個以上の border ノードと 0 個以

前述の通り，Masstree は範囲検索を含む処理が並行的に実行上の interior ノードが含まれている．border ノードとは一般される時に高い性能を発揮することが分かっている．一方，巨的な B+木の leaf ノードとほぼ同じである．しかし，leaf ノー大な入力データが存在する時，そのデータのために Masstree

ドがキーとその value しか持たないのに対して，Masstree のを高速に構築するには一括構築を行うことが自然な選択肢であborder ノードは次のレイヤーへのポインターを持つ場合がある

る．Masstree はトライ木のノード部分に B+木を格納する構造点が異なる．

である．B+木，トライ木ならば，一括挿入法による高性能化手段がそれぞれ知られている [3] [1]．一方，Masstree の一括挿入法は我々の知る限り存在しない．
我々は Masstree の一括挿入法を新たに提案し，その性能を実験的に評価した．これを本論文は報告する．提案技法はMasstree がトライ木と B+木から構成されている点に着目す
る．データを整列した後，トライ木のレベルでのデータ分散を行い，各トライ木において B+木の構築を行う．
本論文の構成は次の通りである．2 章では Masstree とその再実装について述べる．3 章では提案手法である Masstree の図 1 Masstree の構造一括挿入法を述べる．4 章では提案手法の評価結果を述べる．5
章では本論文の結論を述べる．

2. Masstree
Masstree は B+木とトライ木の性能を合わせた高性能なデー

3. 提案

Masstree は B+木同様に挿入時に split が生じるため，多数の入力データから構造を構築するには一括挿入が望ましい．

我々が調査した限りでは Masstree の一括挿入法は存在しな

1e+08

かった為，その技法を提案する．提案技法は Masstree がトライ木と B+木から構成されている点に着目する．データを整列において B+木の構築を行う．これをアルゴリズム 1 に示す．
ここで，data は挿入をするデータの集まりであり，len はその1e+07

Throughputした後，トライ木のレベルでのデータ分散を行い，各トライ木

1e+06

Proposed
MasstreeB+-tree

データの数を表している．また，node は B+木におけるノードを表しており，nkeys はそのノードに現在入っているキーの数100000
1e+06を示している．2 行目からのループでこれから挿入したいデー

1e+07

1e+08

#Keys

タを全て入れ終わるまでループを行っている．同じ prefix を持
つキーを挿入をする場合の処理は 11 行目から 21 行目に示して

図 2 データサイズの影響いる．
2.5e+07

Algorithm 1 一括挿入法
1: node = create new border node;
2: for i = 0 to len - 1 do
3:
4:

while node→next != NIL do

1.5e+07end while6:n = node;7:

key = Key(data[i]);8:value = data[i].value;

9:next layer:

10:nkeys = n→nkeys;

11:

if n→keyslice[nkeys-1] == key then
if n→lv[nkeys-1] does not have next layer thencreate new layer;

13:
14:

end if15:

shift key to next 8 bytes;

16:

n = n→lv[nkeys-1].next layer;

17:

while n→next != NIL don = n→next;

18:

1e+07
5e+06

node = node→next;

5:

12:

Throughput

Data: char** data, int len

Proposed
Masstree

2e+07

00246

81012

14

16

#Threads

図 3 スレッド数の影響

5. 実 験 環 境
表 1 に示す環境で実験を行った。実験に用いたノードの仕表1 実験環境

OSCentOS release 6.6 (Final)

KernelLinux 2.6.32-642.1.1.el6.x86 64
Intel(R) Xeon(R) CPU E5-2695 v2 @ 2.40GHz × 2

19:

end whileCPU

20:

goto next layer;# of CPU cores 12 × 2Memory64 GB

21:

end if22:

if nkeys == NODE MAX then23:

nn = create new border node;

様は次の通りである：プロセッサが Intel(R) Xeon(R) CPU

24:

nn→version = n→version;

E5-2695 v2 @ 2.40GHz，コア数は 24，メモリは 64GB，OS

25:n→next = nn;

26:

nn→prev = n;27:

insert n, nn, and key to interior node;28:

n = nn;は CentOS release 6.6 (Final)．キー長は 10 とした．整列には並列基数ソート [5] を用いた．
提案手法，Masstree，B+木に関してデータサイズを変えな29:

end if

がら挿入スループットを測定した結果を図 2 に示す．いずれも

30:

insert key and value to n;

スレッド数は 16 とした．Masstree が B+木よりも高い性能を

31:

n→nkeys = n→nkeys + 1;

示し，提案手法が Masstree よりも優れることが観察された．

32: end for

キー数が 1 億の時，提案手法は Masstree，B+木に対してそれぞれ 2.48 倍，26.6 倍の性能向上を示した．

4. 評 価 結 果
本章では前章で紹介した提案手法の評価を行うために実施した実験の概要と結果を示す。

提案手法と Masstree についてスレッド数を変えながら挿入スループットを測定した結果を図 3 に示す．提案手法が全てのスレッド数で Masstree を上回ることが観察された．

6. 結論本論文では並行実行木 Masstree の一括挿入法を提案した．

提案技法は 16 スレッドを用いた場合，既存手法に比べて 2.48倍の高性能化を達成した．

謝

辞

本研究の一部は，JST CREST「ポストペタスケールデータインテンシブサイエンスのためのシステムソフトウェア」，JSTCREST「EBD：次世代の年ヨッタバイト処理に向けたエクストリームビッグデータの基盤技術」，JST CREST「広域撮像探査観測のビッグデータ分析による統計計算宇宙物理学」，科研費「#16K00150」による．

文

献[1] Daniar Achakeev and Bernhard Seeger. Eﬃcient bulk updates on multiversion b-trees. PVLDB, Vol. 6, No. 14, pp.
1834–1845, 2013.
[2] Hideaki Kimura. Foedus: Oltp engine for a thousand coresand nvram. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp. 691–706, 2015.
[3] Dongzhe Ma and Jianhua Feng. A generic approach forbulk loading trie-based index structures on external storage.
In Web-Age Information Management - 15th International
Conference, pp. 55–66, 2014.
[4] Yandong Mao, Eddie Kohler, and Robert Tappan Morris.
Cache craftiness for fast multicore key-value storage. InProceedings of the 7th ACM European Conference on Computer Systems, pp. 183–196, 2012.
[5] Nadathur Satish, Changkyu Kim, Jatin Chhugani, Anthony D. Nguyen, Victor W. Lee, Daehyun Kim, andPradeep Dubey. Fast sort on cpus and gpus: A case forbandwidth oblivious simd sort. In SIGMOD Conference,
pp. 351–362, 2010.
[6] Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov,and Samuel Madden. Speedy transactions in multicore inmemory databases. In Proceedings of the Twenty-Fourth
ACM Symposium on Operating Systems Principles, pp. 18–32, 2013.