日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

LSM–tree における

C1 tree の数と読み出し性能の関係
高塚 康成

矢口 尭

首藤 一幸

データベース管理システムには読み出し性能に特化したものと書き込み性能に特化したものがある．どちらに特化しているかは，その設計で採用したインデックス構造によって決まる．伝統的なインデックス構造には B–tree の類があり，これは読み出し性能に特化しており，書き込みは比較的遅い．また，書き込み性能に特化したインデックス構
造に LSM–tree がある．LSM–tree の読み出しが比較的遅いのは，読み出しの際，複数の C1 tree を読むことがあるためである．しかし，C1 tree が 1 つだけの状況での読み出し性能は B–tree の類と同等となると予想できる．そこで，C1 tree の数に応じて LSM–tree の読み出し性能がどうなるかを調べた．データベース管理システム Apache
Cassandra で，LSM–tree を用いた場合，C1 tree が減るに従い読み出し性能は向上した．また，予想の通り，C1tree が 1 つの場合には B–tree の類を用いた場合と同等の性能となった．

1 はじめにオフの関係にある．
従来のデータベース管理システムに使われてきた

MySQL [3] や Apache Cassandra [2] [7]，Apache

伝統的なインデックス構造に B–tree がある．これはHBase [8] など，データベース管理システムには多く読み出し性能に特化したインデックス構造であり，企の種類があり，それらが読み出し性能と書き込み性能業の業務データ等を扱うデータベース管理システムのどちらに特化しているかは，そのストレージエンジで使われている．

ンの設計に採用したインデックス構造により決まる．

Amazon や Facebook のような大規模なウェブサー

インデックス構造とは，データをどのように配置する

ビスが扱うデータ量や利用者数は，企業の業務システかを決める，ディスク上のデータ構造のことである．

ムで扱うデータ量や利用者数に比べると桁違いであ

例えば，目的のデータを見つけるために，二分探索なる．そのような，データ量が膨大となるサービスではど，効率的な探索を行えるようにディスク上にデータNoSQL と呼ばれるデータベース管理システムが使わを配置することで読み出しを速くすることが出来る．

れている．NoSQL では書き込み性能に特化したイン

しかし，書き込み時にはデータを書き込む場所を探デックス構造が用いられており，そのようなインデッすためにディスクへのランダムアクセスが必要となクス構造に LSM–tree [4] がある．

るため，書き込みは比較的遅くなる．逆に，書き込み

本研究では LSM–tree の読み出し性能に注目し，そをシーケンシャルに行う事で書き込み性能を高めるの構成要素である C1 tree の数を減らした際の読み出事ができるが，読み出し時には複数箇所からデータし性能を B–tree の類と比較する．

を読み出す必要が生じるため，読み出しは遅くなる．
このように，読み出し性能と書き込み性能はトレード

2 関連研究B–tree と LSM–tree の構造や読み出し，書き込みPerformance Evaluation of LSM–Tree with Various
Numbers of C1 Trees.
Yasunari Takatsuka, Takashi Yaguchi, Kazuyuki
Shudo, 東京工業大学, Tokyo Institute of Technology.の仕組みを説明する．

図1B–tree の構造例

図2

バケットの分割例

2. 1 B–treeの高さが極端に深くなるようなことはなく，最悪計算読み出し特化なインデックス構造であり，平衡木の量も O(log n) である．

一種である．図 1 に B–tree の構造例を示す．木の節

2. 1. 2 B–tree の書き込み

点はバケットと呼ばれ，各バケットにはキーと他のバ新たなキーの書き込みは常に葉に対して行う．読みケットへのポインタが格納されている．図 1 の数字出しと同様の手順で，葉バケットにたどり着くまではキーを，矢印は他のバケットへのポインタを表して木を探索する．そして，たどり着いた葉バケット内のいる．

キーの大小関係を壊さないように新たなキーを書き

2. 1. 1 B–tree の読み出し込む．たどり着いた葉バケットがキーで埋まっていたキーの総数を n とし，1 つの節点から出る枝の数，場合，平衡木を維持するために，その葉バケットの分つまり 1 つのバケットに格納されているポインタの割を行う．図 2 はバケット分割の例である．分割は以数を m とする．目的のキーを見つけるための木の探下の手順で行う．

索は以下の手順で行われる．

1. 根を対象とし，探索を開始する．
2. バケットの中で目的のキーを探す．あれば，探索を終了する．

1. 新たに書き込むキーを含めて，葉バケット内の全てのキーから中心のキーを決める．

2. そのキーを中心として，左右のキーをそれぞれ二つの新しいバケットに入れる．

3. なければ，目的のキーとバケット内の各キーと3. 中心のキーを，分割したバケットの親バケットの大小を比較し，目的のキーがバケット内でどのに大小関係を崩さないように入れ，新しく作成しキーの間に位置するかを決める．その位置を i 番目とする．

4. i 番目のポインタで次のバケットへ進み，目的た二つのバケットへのポインタを持たせる．

4. 親バケットもキーで埋まっていた場合は，同様の分割操作を親バケットでも行う．のキーが見つかるまで同様の探索を繰り返す．
根から葉までたどる計算量は O(log n) であり，1 つ

2. 2 LSM–treeのバケット内でのキーの大小比較の計算量は，二分探書き込み特化なインデックス構造であり，三つのコ索を使った場合 O(log m) である．つまり，木探索のンポーネントから構成される．それぞれの名称と役割計算量は O(log n) × O(log m) である．しかし，一般に m は定数としてみなせる程度の数値である．そのため，木の探索は計算量 O(log n) で行う事が出来る．
また，平衡木の特徴として、全ての葉から根の高さはほぼ等しく、任意の二つの葉の高さの差が１以下となるような構造をしている．そのため，一部の葉から根は以下の通りである．

• C0 tree（メモリ上のインデックス）– データの書き込みが行われる．メモリ上にあるため書き込みは速い．書き込まれた内容はキーでソートされて保存されている．

• C1 tree（ディスク上のインデックス）

– C0 tree の内容をディスクに書き出したもの．
書き換え不可で，B–tree などの構造を用いる．

LSM–tree の読み出し性能の調査，比較を行う．

C0 tree がある程度埋まると新しい C1 tree を

4 実験作成し，C0 tree は空にする．ディスク上の C1

LSM–tree にて，C1 tree の数を調整して性能に与tree は定期的にマージし，数を減らす．
• ログファイルえる影響を調べる．また，C1 tree の数が少ない場合の読み出し性能を B–tree の類と比較する．

– ディスク上にあり，C0 tree への書き込み操作を記録する．書き込みはシーケンシャルに行わ

4. 1 データベース管理システム

れるため速い．これにより，メモリ上にある C0実験に用いたデータベース管理システムは以下のtree 上データの消失を防ぐ．
2. 2. 1 LSM–tree の書き込み
まず，ログファイルへ書き込みが行われる．これは二つである．

• MySQL（InnoDB）• Apache Cassandra

追記のみであり，ランダムアクセスが不要であるためInnoDB は MySQL で使うことのできるストレージエ速い．そして，C0 tree へデータの書き込みが行われ，ンジンの 1 つであり，インデックス構造として B+–書き込みは終了する．このように，書き込みはディスtree [5] を用いている．また Apache Cassandra はイクへのシーケンシャルな書き込みと，メモリへの書きンデックス構造として LSM–tree を用いている．

込みだけで終わるため速い．

図３，4 は本研究の実験で使うベンチマークツール

しかし，このままではメモリ容量にデータ量を制限

YCSB の論文 [1] から引用したグラフである．2 つのされてしまう．そこで，C0 tree には容量等のしきい

データベース管理システムに対して，書き込みの多い値が設定されており，そのしきい値を超えた時に C0ワークロード（図 3）と読み出しの多いワークロード

tree は C1 tree に変換され，ディスク上に書き出され（図 4）における平均遅延を測定したものである．書きる．そして，C0 tree は削除され，ログファイルも削込みが多いワークロードでは Apache Cassandra の方除される．

が平均遅延が小さく，読み出しが多いワークロードでまた，C1 tree を書き出したままでは C1 tree の数

は MySQL の方が平均遅延が小さくなっている．つまは増える一方であるため，定期的に C1 tree はマージり，Apache Cassandra は書き込み性能に，MySQLし，数を減らす．

は読み出し性能に特化している事を確認できる．

2. 2. 2 LSM–tree の読み出し
C0 tree と全ての C1 tree から目的のデータを読み出す．データは複数の C1 tree にまたがって保存されているため，目的のデータの内容を持つ全ての C1tree を読み取らなければならない．

3 インデックス構造二種の比較
読み出しは 1 つの木だけを探索すれば良い B–treeの方が速く，書き込みはディスクへのランダムアクセ
スが発生しない LSM–tree の方が速い．
本研究では LSM–tree の読み出し性能に注目する．

LSM–tree の構造より，LSM–tree の読み出し性能はそのときどきの C1 tree の数に左右される．その関係を調べるため，我々は C1 tree の数を調整し，

図3

update heavy ワークロードでの読み出しアクセスの遅延クロードは読み出しのみで，100 万件に対して処理を行う．

4. 3 C1 tree の数の調整法
C1 tree の数の調整は，まず C1 tree を 1 つにした後，数を 1 つずつ増やしていくことで行う．

C1 tree を１つにするために，Apache Cassandraの以下の二つのコマンドを利用する．

• flush C0 tree を C1 tree へ強制的に変換し，C0tree を空にする．

図4

read heavy ワークロードでの読み出しアクセスの遅延

また，両データベース管理システムの性能を測定する際，インデックス構造以外の違いを少なくするために，本実験では MyCassandra [6] [9] を使う．これはApache Cassandra を拡張したものであり，ストレージエンジンの差し替えを可能にしたものである．

を 1 つにする．

C1 tree の数を増やすために，YCSB の更新処理を用いる．更新処理はデータベース上のデータを書き換える処理であり，LSM–tree の場合，更新処理のための新しいデータは C0 tree に書き込まれる．C0 tree
は容量等のしきい値を超えると C1 tree へ変換されるため，更新処理を続けると C1 tree が増える．したがって，更新処理を用いる事でデータ件数を変える事無く C1 tree の数を増やす事ができる．YCSB では，

4. 2 ベンチマーク環境
表 2 に利用したマシンの構成を示す．ストレージデバイスには SSD を使用する．
表1• compact 全ての C1 tree をマージし，C1 tree

1 つのカラムの内容を変更することで 1 レコードの更新を行う．
また，C0 tree 上のデータ量の違いも読み出し性能

ベンチマーク環境に影響を与えると考えられる．そのため，C0 tree 上のデータ量に差が出ないよう，今回は C0 tree に 10

OSLinux 3.3.4–3

CPU

2.40 GHz Xeon(R) E5620 × 2

メモリ

8 GB RAMYCSB による更新や上述のコマンドを利用し，具体JavaJava SE 7 Update 4

的には以下の手順で C1 tree の数の調整を行う．まず，万カラム分のデータが載るように調整する．

データベースへの 1000 万件のデータの読み込みを終性能測定には Yahoo! Cloud Serving Bencmark（YCSB） [1] を用いる．YCSB は NoSQL 向けのベンチマークツールであり，読み出し処理や更新処理の比率などを指定する事が出来る．
データ件数は 1000 万件で実験を行う．今回，1 つのレコードは 10 個のカラムを持ち，1 カラムの容量を 100 バイトとしたため，1 レコードの容量は 1 KBとなる．つまり，データ全体のサイズは 10 GB となり，これにさらにスキーマの情報が加わるため，8 GBのメモリに全データが載ることはない．また，ワーえた時，C1 tree が複数存在し，C0 tree にもデータが書き込まれている状態となる．そこで，最初は flush
コマンドで C0 tree の中身を空にし，compact コマンドにより C1 tree を 1 つにする．その後，YCSB による更新を行って C0 tree に 10 万カラム分のデータを載せ，読み出し性能を測定する．次に，C1 tree が 1つ増えるまで更新処理を繰り返す．C1 tree が増えた
ら，更新するレコード数を調整し，C0 tree に 10 万カラム分のデータを載せ，読み出し性能を測定する．
読み出し性能の測定を行う毎にこの操作を繰り返す．
この C1 tree の調整法の場合，増加する各 C1 tree

の大きさは同程度であるが，最初に compact コマンるため，平均遅延にはより大きな差が生じると考えら

ドで生成された C1 tree と，それ以外の C1 tree で大れる．

きさは異なる．例えば，C1 tree が 3 つの場合，１つ

図 6 は C1 tree 1 つの場合の平均遅延とストレージの C1 tree は大きく，他 2 つの C1 tree は小さい状態

エンジンを MySQL に差し替えた場合の平均遅延をとなる．実際のワークロードでは，C1 tree は一定数比較したものである．参考に，C1 tree の数が 20 の増えるたびにマージされ，C1 tree が小さいまま増え場合の平均遅延も示す．

続ける事は無い．そのため，この調整法においては，

C1 tree 数が 1 つの場合の実験結果は他の場合の結果と公正に比較できない．そこで，C1 tree が 2 つ以上の場合の実験結果は，1 つの場合との差分を示すこととする（図 5）．

4. 4 実験結果と考察性能評価の基準として，読み出しアクセスの平均遅延を測定する．
図 5 に，C1 tree の数を変えた場合の平均遅延を示す。ただし，値は，C1 tree が 1 つの場合の平均遅延との差分であり，このため 1 つの場合は 0 となって

図6

B+–tree を用いている MySQL（InnoDB）とのアクセス遅延の比較

いる．C1 tree が 1 つの時の平均遅延は 0.87 ミリ秒であった．

C1 tree 1 つの場合の平均遅延は，B–tree の類をインデックス構造に採用している MySQL の平均遅延とほぼ同じとなった．これは，LSM–tree でのディスクアクセス回数は B–tree の類とほぼ同じとなったためと考えられる．また，LSM–tree は C1 tree だけでなく，C0 tree からも読み出しを行うため，その分のオーバヘッドが考えられたが，実験では読み出し性能に差は出なかった．これは，C0 tree がメモリ上にあり，C0 tree に載るデータ量が C1 tree に載る総データ量に対して小さいため，C0 tree が読み出し遅延にあまり影響を与えなかったためと考えられる．

図5

C1 tree の数とアクセス遅延の関係（C1 tree が 1 つの場合の値との差分）

5 まとめと今後の課題
C1 tree の数を減らした場合の，LSM–tree と B–

C1 tree の数が少ないほど遅延も小さくなった．まtree 類の読み出し性能の比較を行った．結果は，C1た，C1 tree 数の増減に応じた遅延の増減は，C1 treetree の数を減らすと読み出し性能は向上し，C1 tree数が少ないほど小さかった．今回の C1 tree の数の調の数を 1 つにすると，LSM–tree は B–tree 類と同等

整法においては，C1 tree の数が 1 の場合と 25 の場の読み出し性能を発揮した．

合で，平均遅延に約 3 ミリ秒の差が出た．実際のワー課題としては，MySQL がチューニング不足であっクロードでは，今回の実験より各 C1 tree が大きく，た可能性や，他のデータベース管理システムを使っそれぞれの探索に要する時間が増える事が想定された場合に異なる結果となる可能性が考えられるため，実装によらない，より純粋なインデックス構造のみの比較実験を行えるようにしたい．また今回は，大きな C1 tree が 1 つ存在し，大きさの等しい小さな C1tree を増やすという形で C1 tree の数を調整したが，実際のワークロードで見られるようなより自然な形で，C1 tree の数の調整を行えるようにしたい．
謝辞
本研究は JSPS 科研費 24650025，25700008 の助成を受けたものである．
参 考 文 献[1] Brian F. Cooper, Adam Silberstein, Erwin Tam,
Raghu Ramakrishnan, and Russell Sears.: Benchmarking Cloud Serving Systems with YCSB, Proc.
SOCC 10, pp. 143–154, 2010.
[2] Lakshman, A. and Malik, P.: Cassandra – A
Decentralized Structured Storage System, Proc.

LADIS 09 (2009).
[3] Oracle Corporation: MySQL, http://www.mysql.com/.
[4] Patrick O Neil, Edward Cheng, Dieter Gawlick,
and Elizabeth O Neil.: The Log-Structured MergeTree (LSM-Tree), Acta Inf., Vol. 33, No. 4, pp. 351–385, 1996.
[5] Rudolf Bayer and Edward M. McCreight.: Organization and Maintenance of Large Ordered Indexes,Acta Inf., Vol. 1, Fasc. 3, pp. 173–189, 1972.
[6] Shunsuke Nakamura and Kazuyuki Shudo: MyCassandra: A Cloud Storage Supporting both Read
Heavy and Write Heavy Workloads, Proc. 5th Annual Int’l Systems and Storage Conference, SYSTOR 12, 2012.
[7] The Apache Software Foundation: Apache Cassandra, http://cassandra.apache.org/.
[8] The Apache Software Foundation:Apache
HBase, http://hadoop.apache.org/hbase/.
[9] 中村俊介, 首藤一幸.: 読み出し性能と書き込み性能を両立させるクラウドストレージ, 先進的計算基盤システ
ムシンポジウム（SACSIS2011）論文集, pp. 171–180,
2011.