DEIM Forum 2016 G8-1

Key Sorting Buﬀer を用いた時系列データのデータベース処理高速化
曽我樹大†

華井雅俊††

高塚康成††

首藤 一幸††† 東京工業大学 理学部 情報科学科†† 東京工業大学 大学院情報理工学研究科 数理・計算科学専攻〒 152-8552 東京都目黒区大岡山 2-12-1-W8-43
E-mail: soga.t.aa@m.titech.ac.jp, mhanai@acm.org, takatsuka.y.aa@m.titech.ac.jp, shudo@is.titech.ac.jp
あらましメッセージングや SNS でのメッセージや投稿といった時系列データは，多くの場合データベース上ではキーの一部に実時間を含む形で表現する．Google Bigtable，Apache HBase，Apache Cassandra など多くの NoSQL型データベースで用いられているインデックス構造である LSM-Tree においては，キー順に従ってデータを処理するとランダムである場合よりも高速に処理できる．我々はその点に着目し，サーバ・クライアント毎の遅延の差やクロックのずれなどによって崩れた時系列データのキー順を Key Sorting Buﬀer を用いてソートし直すことでデータベース処理の高速化を実現する．また，既存のデータベース管理システムを用いて設計及び実装したミドルウェアの評価を行い，実際に Key Sorting Buﬀer によってデータベース処理の高速化が可能であることを確認した．
キーワード

データベース，インデックス，時系列データ，高速化

1. は じ め に

本論文の構成は以下のとおりである．2 章では本研究の背景を述べ，3 章では我々の提案手法について述べる．4 章では予モバイル端末の普及と発達に伴って，LINE, Skype などの備実験及び提案手法に基づいて実装したミドルウェアの性能評

メッセージングアプリケーションや，Twitter, Facebook, In-価を行う．5 章では関連研究について述べる．6 章では本研究

stagram などの SNS を利用する機会が増えている．メッセージについてまとめ，また今後の課題を述べる．

ングアプリケーションや SNS 上の投稿など，時間経過に従って生成されるデータを時系列データといい，多くのユーザによる2. 背景

投稿・閲覧が行われる．そのような多くのリクエストに対応す

本章では，本研究の背景を述べる．特に研究対象としているるためには，分散環境で高い処理性能を発揮できるデータベー時系列データと，提案手法の有効性を述べるにあたって必要とスを用いることが必要になる．そのために用いられているのがなる LSM-Tree に対するデータの読み書きについて述べる．

NoSQL 型データベースである．Google Bigtable [1]，Apache

2. 1 時系列データ

Cassandra [2], [3]，Apache HBase [4] などの NoSQL 型データ

1 章で述べたように，時間経過に従って生成される時系列デー

ベースでは，データの索引として利用するインデックス構造にタはキーの一部に実時間を含む形で表現されることが多い．例

LSM-Tree [5] を主に採用している．LSM-Tree の内部で利用さえば，次のような形である．

れているアルゴリズムを解析した結果，データをキー順に従って処理するとランダムである場合よりも高速に処理することが可能であると我々は考えた．

Key = "（実時間のタイムスタンプ）" + "（その他）"
このようなキーを採用する理由は，時系列データに対するリ今回研究対象とする時系列データは，多くの場合データベークエストは「データを時系列で読み出す」ことが多いからであス上ではキーの一部に実時間を含む形で表現される．しかし，る．実時間のタイムスタンプをキーの頭に持つデータを利用す

複数クライアントで生成された時系列データをサーバ（データるとき，データを時系列に読み出す際には近いキーを順々に読ベース）に送る際に発生する遅延時間の差や，各クライアントみ出せば良い．近いキーを順々に読み出す操作はディスクシー毎のクロックのずれが原因となり，サーバにはキー順ではなくクを抑えることが可能であり，読み出し効率が良くなる．我々

少し順序が崩れた状態でデータが到着してしまう．

は，このような時系列データに対する処理について高速化を実

そこで我々は，サーバ・クライアント間に Key Sorting Buﬀer

現する．

を配置し，クライアントから送られてくるデータを一時的に2. 2 LSM-Tree とコンパクションバッファリングし，ソートし直した状態でサーバへデータを渡1 章で述べた通り，NoSQL 型データベースではインデッす仕組みを提案する．提案手法はリバースプロキシに実装する

ク ス 構 造 と し て LSM-Tree を 用 い る 場 合 が 多 い ．MySQL

ことで，データベース管理システムに手を加えないミドルウェ[6],PostgreSQL [7] などのデータの読み出し性能に特化したアとして機能させることが可能である．我々は既存のデータデータベースとは異なり，LSM-Tree を用いたデータベースはベース管理システムを用いてミドルウェアを設計及び実装し，書き込み性能に特化している．

提案手法の評価を行う．

LSM-Tree は図 1 に示すような構造をとっている．書き込み図 2 LevelDB 型コンパクションによる構造
図 1 LSM-Tree の構造的に同レベル内であればキー範囲が被る tree が存在しないようはメモリ上で行うため高速であるが，読み出し時はディスクかにすることができる．従って，データの読み出しの際に調べる

ら複数の C1 tree を読む必要があるため比較的遅く，書き込みtree の数は高々レベル数分だけである．各レベルの容量は指数が行われ C1 tree の数が増えるにつれて読み出し性能は徐々に関数的に増えていくので，レベル数が増加し過ぎることもない．

落ちていく．この読み出し性能の過度な低下を抑えるために複2. 3. 3 Bigtable 型と LevelDB 型の比較

数の C1 tree をまとめて整理する処理がコンパクションである．

LevelDB 型は Bigtable 型と比べてコンパクションの処理が図１に見られるように C1 tree は木構造になっていて，各 Tree重いため，コンパクション処理に長い時間がかかる．コンパクはデータがキー順にソートされている．データを読みだす際，ション処理の最中はデータベースの読み書き性能に悪影響を及目的のキーを範囲に含む C1 tree の数が少ないほど読み出しのぼすため，これは好ましくない．よって，コンパクションが起コストが小さくなる．コンパクション処理によって，複数の C1こる原因となるデータの書き込みが非常に沢山行われる場合はtree をまとめて数を減らすことや，各 Tree のキー範囲の被り

LevelDB 型は Bigtable 型に比べて不利である．

が少なくなるように整理することができる．

一方，LevelDB 型は各 Tree のキー範囲の被りを減らす工

2. 3 コンパクション手法

夫をしているのに対して，Bigtable 型はそれを行っていない．

コンパクションの対象となる C1 tree をどのように選択する

よって，データの読み出しにおいては LevelDB 型が Bigtableかはデータベース管理システム毎に異なっており，様々なコンパクション手法がとられている．本節では，広く用いられている 2 つのコンパクション手法について述べる．

2. 3. 1 Google Bigtable 型コンパクション
Apache Cassandra [2], [3] の デ フォル ト 設 定 や Google
Bigtable [1] などにおいて用いられているのが，この手法である．Cassandra においては Size Tiered Compaction Strat-型に比べて有利となる．

3. 提 案 手 法
本章では，コンパクション処理の負荷を減らす方法を述べ，これを複数クライアントが存在する状況において実現できる手法を提案する．

3. 1 キー順に従ったデータの書き込み

egy と呼ばれている．これは最も単純な方法であり，同程度の現時点では Bigtable 型コンパクションと LevelDB 型コンパ

大きさの C1 tree がある程度集まってきたらコンパクションをクションは書き込み性能と読み出し性能のトレードオフにある．

行い 1 つにまとめることを繰り返し行う．

しかし，データの書き込みをキー順に従った形で行うことで二2. 3. 2 Google LevelDB 型コンパクション者に差が生まれるのではないかと我々は考える．Bigtable 型はGoogle LeveleDB [8] や Riak [9] などにおいて用いられていキー範囲を考慮したコンパクションを行わないため特に変化はるのが，この手法である．Cassandra でも使用可能であり Lev-無いと考えられる．しかし，LevelDB 型のアルゴリズムを考慮

eled Compaction Strategy と呼ばれている．これは，各 Tree

すると，データの書き込みをキー順にすることで古い Tree とのキー範囲の被りをなるべく減らすことに主眼を置いた手法で新しい Tree のキー範囲の被りをなくすことが可能であり，こある．この手法によってディスク内がどのような構造になるかれによってコンパクション処理時間を大きく削減できると考えを図 2 に示す．小さな Tree 複数を用いて，階層構造で管理をられる．また，コンパクション処理の負荷が軽くなることで，行う．各レベルの容量は 1 つ下のレベルの容量の 10 倍となるデータベースの処理性能が向上すると考えられる．我々の考えようになっている．コンパクションが行われるのは，あるレベを検証する実験については，次章の予備実験の節（4.1 節）でル n の容量が一杯になった時であり，まずレベル n 内の tree

述べる．

が 1 つ選択される．その選択された tree とキー範囲が被る tree

3. 2 提 案 手 法がレベル n + 1 内から全て選択され，そのレベル n 内の 1 つの前節にて，キー順に従ってデータを書き込むことによってコtree とレベル n + 1 内の複数の tree がコンパクションの対象とンパクション時間を短くし，処理性能を上げられることを述べなる．これらの tree を一度まとめたら，レベル n + 1 内にキーた．しかし，時系列データを生成するアプリケーションを考える

順に新たな小さな tree を出力する．これによってレベル n からと，複数クライアントで生成された時系列データをサーバに送レベル n + 1 へのコンパクションが完了したことになり，結果る際に発生する遅延時間の差や，各クライアント毎のクロック表 1 利用したマシンの構成

OS Linux 3.16.0-51-generic，Ubuntu 14.04.2 LTS
CPU

2.40 GHz Xeon（R） E5620 × 2

メモリ

8 GB RAM

Java

Java SE 8 Update 45

図 3 Key Sorting Buﬀer（KSB）のずれが原因となり，サーバにはキー順ではなく少し順序が崩れた状態でデータが到着してしまう．この状況では，キー順に従ってデータを書き込むと高速に処理ができるという LevelDB型の特性を活かすことができない．
そこで我々は，Key Sorting Buﬀer（以下 KSB とする）を用いた仕組みを提案する．KSB は図 3 に示すように複数クラ
図 4 コンパクション時間の比較

イアントとサーバ（データベース）の間に配置する．KSB では
クライアントから来る時系列データを適切な時間バッファリングし，時系列データをキー順にソートし直した状態でサーバへ送る．これによりサーバではキー順にデータが書き込まれることになり，処理性能の向上が期待できる．

4. 実

験

本章では，3.1 節で述べた我々の考えを検証するために行った予備実験と，既存のデータベース管理システムを用いて設計及び実装した KSB に対する評価実験について述べる．

4. 1 予 備 実 験
本節では，3.1 節で述べた我々の考え，すなわちキー順に従ったデータの書き込みによってコンパクション時間が削減でき，データベース処理高速化が可能であるという考えを検証するために行った予備実験について述べる．

図5

図 4 はキー順（or-読み出し遅延の比較

dered）とランダム（random）で 1KB のデータを 5,000,000 件（合計 5GB）を書き込んだ際のコンパクションにかかった合計時間を，Bigtable 型と LevelDB 型それぞれについて示したものである．サーバは両方のコンパクション手法を採用している

Apache Cassandra [2], [3] を用いて計測した．また，サーバにデータを書き込むクライアントとして Yahoo! Cloud Serving

Benchmark（YCSB） [10] を使用した．YCSB は NoSQL に対して利用できるベンチマークツールであり，読み出し及び書き込みの比率や，サーバへのアクセス分布，1 秒あたりに発行する処理要求数の目標値（スループット）などの項目を指定できる．
本項の実験では，データを書き込む順番を示すパラメータである”insertorder”を変更することでキー順に従った（ordered）書き込みとランダム（random）な書き込みを実現した．また，利用したマシンの構成は表 1 の通りである．
図 4 のグラフから，LevelDB 型であってもデータの書き込みがキー順に行われるのであれば，Bigtable 型よりもコンパクション時間が短くなることが確認できる．従って，LevelDB 型に対してキー順に書き込みを行うのであれば，Bigtable 型と比べて書き込み性能と読み出し性能の両方において有利になると考えられる．
図 5 は，実際にコンパクション時間の差が読み出し遅延に与える影響を示したものである．図 4 において最もコンパクション時間に差のあった LevelDB 型のキー順とランダムで比較を行っている．両者ともデータの書き込みが行われている最中に読み出しを開始し，書き込みが終了した後もしばらく読み出しを続けている．なお，遅延測定には YCSB を用いている．
読み出し遅延が不安定になっている箇所がコンパクション処理の最中だと考えられ，キー順の方がランダムである場合よりも早くコンパクション処理が終わっていることを確認できる．
さらに，全体を通して，特にコンパクション処理の最中はキー順の方がランダムである場合よりも読み出し遅延が小さいことを確認できる．従って，コンパクション処理の負荷の大小がデータベースの処理性能に影響していると考えられる．

4. 2 Key Sorting Buﬀer を用いた実験
本節では，実際に KSB を用いて行った評価実験について述べる．

表 2 各クライアントのタイムスタンプ生成
タイムスタンプの生成
クライアント 1基準（± 0 [ms]）クライアント 2 クライアント 1 のタイムスタンプ + 1000 [ms]クライアント 3 クライアント 1 のタイムスタンプ + 2000 [ms]クライアント 4 クライアント 1 のタイムスタンプ + 3000 [ms]4. 2. 1 Key Sorting Buﬀer の実装と実験環境提案手法を評価するために，3 章で述べた手法に基づき KSBをリバースプロキシとして実装した．リバースプロキシに実装することで，DBMS に手を加えないミドルウェアとして機能させることが可能である．この設計には以下のような利点がある．

•

様々な DBMS に対応することが可能である•

DBMS 側に手を加えないため，開発・改良が容易である•

KSB が故障したとしても，元々の DBMS に影響を与えることがない•

KSB は起動時にデータをバッファリングする時間をミリ秒単位で指定できるようにしている．

KSB の評価の際，前節と同様に DBMS には Cassandra を用いて，クライアントには YCSB を用いた．Cassandra ではLevelDB 型コンパクションを利用する．また，利用したマシンの構成も前節と同様に表 1 の通りである．

4. 2. 2 実

図 6 コンパクション時間の比較（KSB）

験

まず，次のようなキーを生成するように，YCSB に対して改造を行った．

KSB を利用しない書き込みに着目すると，スループットを 12,000 に指定した時に最もコンパクション時間がかかっている．12,000 よりスループットが小さい時にコンパクション時間が短い理由は，データの書き込み処理の負荷が小さいからだと考えられる．12,000 よりスループットが大きい時にコンパクション時間が短い理由は，データを全て書き込み終わるまでの時間が短くなることにより，コンパクション処理とデータの書き込み処理を並行しなければならない時間が短くなり，コンパクションの負荷が全体的には低くなるからだと考えられる．

•KSB を利用することによって必ずコンパクション時間

Key = "（実時間のタイムスタンプ）-"が短くなっている訳ではない．しかし，KSB を利用しない時に+ "（ランダムな 5 桁の数字）-"

最もコンパクション時間が長かったスループット 12,000 の時，+ "（クライアントの番号）"

KSB を利用すると最も高い割合（約 15.8%）でコンパクション例えば以下の様なキーが生成される．

時間を削減できている．このことから，比較的コンパクション負荷の高い条件下において KSB は効率よく働くといえる．

1453890479952-75034-user1•

スループット 14,000 の時は，KSB を利用した書き込み

1453890480025-82028-user2の方がコンパクション時間が長くなっている．これは，KSB にまた，今回はクライアントを 4 台利用したが，サーバ・クラバッファリングして一気にデータを書き込むことでできる C1

イアント間の遅延の差がほとんど無いため，YCSB でキーを生tree の大きさが大きくなってしまい，それが高負荷の原因に成する際にタイムスタンプの数字を調節することで，擬似的になってしまっていることが理由の一つとして考えられる．

遅延の差が発生している状況を作り出して実験を行った．各クライアントによるタイムスタンプ生成は表 2 のようにした．

•前節の予備実験の図 4 における LevelDB 型コンパクショ

ンのキー順とランダムの差のように，コンパクション時間が大このような状況のもとで，KSB を利用しないデータの書ききな割合で削減されている結果は現れなかった．予備実験ほど込みと，バッファリング時間を 3,000 ミリ秒に設定した KSB

大きな差がでなかった理由は，崩れた順で来る時系列データはを用いたデータの書き込みそれぞれについて，コンパクション短期的に見ればランダムであるが，長期的に見れば大体キー順時間を比較した．また，スループットを 2,000〜14,000 [opera-に従っているからだと考えられる．

tions/sec] の範囲で変更することによる結果の変化についても記録した．実験は次のような条件で行った．

実際に時系列データを生成するようなアプリケーションでは，大量のデータの書き込みが絶えず行われている．このよう•クライアント（YCSB）の数は 4なワークロードではコンパクションの負荷が大きくなることが•サーバ（Cassandra）のノード数は 1予測される．今回の結果から，データ書き込みのスループット•

1 クライアントあたり，1,000,000 件のデータの書き込みが一定の値を超えなければ，KSB を利用することでコンパク•

1 件あたりのデータの大きさは 1KBションの負荷を高い割合で削減することが可能であると考えら

すなわち，データベースが受け取るデータの合計量は 1KB× 1,000,000 × 4 = 4GB となる．実験結果は図 6 の通りである．この結果から，以下の様なことが言える．

れる．したがって，実際のデータの読み書きなどのデータベース処理を高速化することも可能であると考えられる．

5. 関 連 研 究中で比較測定すること．

•

時間のみでなくデータ量による制限の機能をつけること

本章では，本研究の関連研究について述べる．などを行い，より高いスループットにも対応できるように KSB

5. 1 LSM-Tree の研究の改良を行うこと．

本研究では，LSM-Tree の特にコンパクション処理に着目し•今回はデータベースノード 1 台のみを想定していた．よていた．Ahmad ら [11] の研究では，コンパクション処理が性り実用的に利用できるようにするために，KSB の配備方法を能に与える影響について述べている．さらに，分散環境におい検討すること．てコンパクション処理のみを行う専用のサーバを用いることでこの問題を解決する手法を提案している．本研究と同様にコンパクション処理と性能の関係について述べているが，本研究は•時系列ではなく一般のデータに対しても処理の高速化ができる仕組みを考えること．

•KSB による効果を十分検証し，データベース内でも KSBサーバにデータを送る前に工夫をしているのに対して，Ahmadと同様の効果を得られるようにデータベース自体の改良方法をらの研究ではサーバ側で工夫を行っている点が異なっている．

考えること．

Ghosh ら [12] の研究では，数学的なアプローチでコンパクションについて考えている．既存のコンパクションのアルゴリズムについて解析した本研究とは異なり，Ghosh らの研究では謝辞
本研究は JSPS 科研費 25700008，26540161 の助成を受けたものです．

さらに新たなコンパクションのアルゴリズムを提案している．
ま た ，LSM-Tree 自 体 に つ い て 改 善 を 施 す bLSM [13] や

pLSM [14] といった研究も行われている．
5. 2 プロキシの利用
本研究は，提案手法をプロキシに実装した．4.2.1 項でも述
べたようにこの設計には様々な利点があるため，プロキシ実装を利用している研究は他にも行われている．

memcached [15] は分散メモリキャッシュサーバであるが，本研究と同様にプロキシとして利用することでパフォーマンスの向上が可能である．本研究はプロキシを利用してデータベース側の処理性能を向上させたが，memcached をプロキシとして利用することで，アプリケーション側の読み出し性能を向上させることができる．
プロキシを別の目的で利用する研究もある．高塚ら [16] の研
究では，プロキシを利用して読み出しの遅延とキャッシュの利用率を調節することを行っている．また，矢口ら [17] の研究では，プロキシを利用してデータの因果整合性を保障できるようにすることを行っている．

6. まとめと今後の課題
データベースに対してキー順にデータを書き込むことの有効性について述べ，時系列データをキー順に処理するための KSBを用いた仕組みを提案し，提案手法に基づいて実装したミドルウェアの性能評価を行った．
実験により，データベースの処理性能に影響を及ぼすコンパクション処理について，一定の条件下で KSB を用いることでコンパクション処理の負荷を削減できることを確認し，実際のデータベース処理を高速化することが可能であると結論づけた．
今後の課題としては，以下の様なことが挙げられる．

•

現状では KSB はデータをバッファリングする機能しか提供していないため，バッファリング中のデータに対する読み出し命令を処理することができない．KSB をより実用的にするために，バッファリング中のデータに対するデータ読み出しの機能を実装し，KSB を利用したデータの読み出し性能と利用しない場合のデータの読み出し性能を実際のワークロードの文

献[1] Fay Chang, Jeﬀrey Dean, Sanjay Ghemawat, Wilson CHsieh, Deborah A Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E Gruber. Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems (TOCS), Vol. 26, No. 2, pp.
4:1–4:26, 2008.
[2] The Apache Software Foundation. Apache Cassandra.
http://cassandra.apache.org/.
[3] Avinash Lakshman and Prashant Malik. Cassandra: a decentralized structured storage system. ACM SIGOPS Operating Systems Review, Vol. 44, No. 2, pp. 35–40, 2010.
[4] The Apache Software Foundation. Apache HBase. http://hbase.apache.org/.
[5] PatrickO Neil, Edward Cheng, Dieter Gawlick, ElizabethO
Neil. The log-structured merge-tree (LSM-tree). Acta Informatica, Vol. 33, No. 4, pp. 351–385, 1996.
[6] Oracle Corporation. MySQL. http://www.mysql.com/.
[7] The PostgreSQL Global Development Group. PostgreSQL.
http://www.postgresql.org/.
[8] Google Inc. LevelDB. http://leveldb.org/.
[9] Basho Technologies. Riak. http://basho.com/products/.
[10] Brian F Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. Benchmarking cloud serving
systems with ycsb. In Proceedings of the 1st ACM symposium on Cloud computing, pp. 143–154. ACM, 2010.
[11] Muhammad Yousuf Ahmad and Bettina Kemme. Compaction management in distributed key-value datastores.
Proceedings of the VLDB Endowment, Vol. 8, No. 8, pp.
850–861, 2015.
[12] Mainak Ghosh, Indranil Gupta, Shalmoli Gupta, and Nirman Kumar. Fast compaction algorithms for NoSQL
databases. In Distributed Computing Systems (ICDCS),
2015 IEEE 35th International Conference on, pp. 452–461.
IEEE, 2015.
[13] Russell Sears and Raghu Ramakrishnan. bLSM: a general
purpose log structured merge tree. In Proceedings of the2012 ACM SIGMOD International Conference on Management of Data, pp. 217–228. ACM, 2012.
[14] Jin Wang, Yong Zhang, Yang Gao, and Chunxiao Xing.
pLSM: A Highly Eﬃcient LSM-Tree Index Supporting RealTime Big Data Analysis. In Computer Software and Applications Conference (COMPSAC), 2013 IEEE 37th Annual,
pp. 240–245. IEEE, 2013.
[15] Brad Fitzpatrick. Distributed caching with memcached.

Linux journal, Vol. 2004, No. 124, pp. 5–, 2004.
[16] 高塚 康成, 長尾 洋也, 矢口 尭, 華井 雅俊, 首藤 一幸. 読み出し
データの新鮮度を考慮するキャッシュ機構. 第 6 回データ工学と情報マネジメントに関するフォーラム, 2014.
[17] 矢口 尭, 首藤 一幸. 広域分散データストアに因果整合性を付加するミドルウェア. 第 7 回データ工学と情報マネジメントに関するフォーラム, 2015.