Key Sorting Bufferを用いた時系列データのデータベース処理高速化

DEIM Forum 2016 G8-1

Key Sorting Buffer

を用いた時系列データのデータベース処理高速化

曽我

樹大

†

華井

雅俊

††

高塚

康成

††

首藤

一幸

††

†

東京工業大学 理学部 情報科学科

††

東京工業大学 大学院情報理工学研究科 数理・計算科学専攻

〒 152-8552 東京都目黒区大岡山 2-12-1-W8-43

E-mail: [email protected], [email protected], [email protected], [email protected]

あらまし メッセージングや SNS でのメッセージや投稿といった時系列データは，多くの場合データベース上では

キーの一部に実時間を含む形で表現する．Google Bigtable，Apache HBase，Apache Cassandra など多くの NoSQL

型データベースで用いられているインデックス構造である LSM-Tree においては，キー順に従ってデータを処理する

とランダムである場合よりも高速に処理できる．我々はその点に着目し，サーバ・クライアント毎の遅延の差やクロッ

クのずれなどによって崩れた時系列データのキー順を Key Sorting Buffer を用いてソートし直すことでデータベース

処理の高速化を実現する．また，既存のデータベース管理システムを用いて設計及び実装したミドルウェアの評価を

行い，実際に Key Sorting Buffer によってデータベース処理の高速化が可能であることを確認した．

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

1.

は じ め に

モバイル端末の普及と発達に伴って，LINE, Skypeなどの メッセージングアプリケーションや，Twitter, Facebook, In-stagramなどのSNSを利用する機会が増えている．メッセージ ングアプリケーションやSNS上の投稿など，時間経過に従って 生成されるデータを時系列データといい，多くのユーザによる 投稿・閲覧が行われる．そのような多くのリクエストに対応す るためには，分散環境で高い処理性能を発揮できるデータベー スを用いることが必要になる．そのために用いられているのが

NoSQL型データベースである．Google Bigtable [1]，Apache Cassandra [2], [3]，Apache HBase [4]などのNoSQL型データ ベースでは，データの索引として利用するインデックス構造に LSM-Tree [5]を主に採用している．LSM-Treeの内部で利用さ れているアルゴリズムを解析した結果，データをキー順に従っ て処理するとランダムである場合よりも高速に処理することが 可能であると我々は考えた．  今回研究対象とする時系列データは，多くの場合データベー ス上ではキーの一部に実時間を含む形で表現される．しかし， 複数クライアントで生成された時系列データをサーバ（データ ベース）に送る際に発生する遅延時間の差や，各クライアント 毎のクロックのずれが原因となり，サーバにはキー順ではなく 少し順序が崩れた状態でデータが到着してしまう．

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

を配置し，クライアントから送られてくるデータを一時的に バッファリングし，ソートし直した状態でサーバへデータを渡 す仕組みを提案する．提案手法はリバースプロキシに実装する ことで，データベース管理システムに手を加えないミドルウェ アとして機能させることが可能である．我々は既存のデータ ベース管理システムを用いてミドルウェアを設計及び実装し， 提案手法の評価を行う．  本論文の構成は以下のとおりである．2章では本研究の背景 を述べ，3章では我々の提案手法について述べる．4章では予 備実験及び提案手法に基づいて実装したミドルウェアの性能評 価を行う．5章では関連研究について述べる．6章では本研究 についてまとめ，また今後の課題を述べる．

2.

背

景

本章では，本研究の背景を述べる．特に研究対象としている 時系列データと，提案手法の有効性を述べるにあたって必要と なるLSM-Treeに対するデータの読み書きについて述べる． 2. 1 時系列データ 1章で述べたように，時間経過に従って生成される時系列デー タはキーの一部に実時間を含む形で表現されることが多い．例 えば，次のような形である． Key = "（実時間のタイムスタンプ）" + "（その他）"  このようなキーを採用する理由は，時系列データに対するリ クエストは「データを時系列で読み出す」ことが多いからであ る．実時間のタイムスタンプをキーの頭に持つデータを利用す るとき，データを時系列に読み出す際には近いキーを順々に読 み出せば良い．近いキーを順々に読み出す操作はディスクシー クを抑えることが可能であり，読み出し効率が良くなる．我々 は，このような時系列データに対する処理について高速化を実 現する． 2. 2 LSM-Treeとコンパクション 1章で述べた通り，NoSQL型データベースではインデッ ク ス 構 造 と し てLSM-Tree を 用 い る 場 合 が 多 い ．MySQL [6],PostgreSQL [7]などのデータの読み出し性能に特化した データベースとは異なり，LSM-Treeを用いたデータベースは 書き込み性能に特化している．  LSM-Treeは図1に示すような構造をとっている．書き込み

図 1 LSM-Treeの構造 はメモリ上で行うため高速であるが，読み出し時はディスクか ら複数のC1 treeを読む必要があるため比較的遅く，書き込み が行われC1 treeの数が増えるにつれて読み出し性能は徐々に 落ちていく．この読み出し性能の過度な低下を抑えるために複 数のC1treeをまとめて整理する処理がコンパクションである． 図１に見られるようにC1 treeは木構造になっていて，各Tree はデータがキー順にソートされている．データを読みだす際， 目的のキーを範囲に含むC1treeの数が少ないほど読み出しの コストが小さくなる．コンパクション処理によって，複数のC1 treeをまとめて数を減らすことや，各Treeのキー範囲の被り が少なくなるように整理することができる． 2. 3 コンパクション手法 コンパクションの対象となるC1 treeをどのように選択する かはデータベース管理システム毎に異なっており，様々なコン パクション手法がとられている．本節では，広く用いられてい る2つのコンパクション手法について述べる． 2. 3. 1 Google Bigtable型コンパクション

Apache Cassandra [2], [3] の デ フォル ト 設 定 や Google Bigtable [1] などにおいて用いられているのが，この手法で ある．CassandraにおいてはSize Tiered Compaction Strat-egyと呼ばれている．これは最も単純な方法であり，同程度の 大きさのC1 treeがある程度集まってきたらコンパクションを

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

2. 3. 2 Google LevelDB型コンパクション

Google LeveleDB [8]やRiak [9]などにおいて用いられてい るのが，この手法である．Cassandraでも使用可能であり Lev-eled Compaction Strategyと呼ばれている．これは，各Tree

のキー範囲の被りをなるべく減らすことに主眼を置いた手法で ある．この手法によってディスク内がどのような構造になるか を図2に示す．小さなTree複数を用いて，階層構造で管理を 行う．各レベルの容量は1つ下のレベルの容量の10倍となる ようになっている．コンパクションが行われるのは，あるレベ ルnの容量が一杯になった時であり，まずレベルn内のtree が1つ選択される．その選択されたtreeとキー範囲が被るtree がレベルn + 1内から全て選択され，そのレベルn内の1つの treeとレベルn + 1内の複数のtreeがコンパクションの対象と なる．これらのtreeを一度まとめたら，レベルn + 1内にキー 順に新たな小さなtreeを出力する．これによってレベルnから レベルn + 1へのコンパクションが完了したことになり，結果 図 2 LevelDB型コンパクションによる構造 的に同レベル内であればキー範囲が被るtreeが存在しないよう にすることができる．従って，データの読み出しの際に調べる treeの数は高々レベル数分だけである．各レベルの容量は指数 関数的に増えていくので，レベル数が増加し過ぎることもない． 2. 3. 3 Bigtable型とLevelDB型の比較 LevelDB型はBigtable型と比べてコンパクションの処理が 重いため，コンパクション処理に長い時間がかかる．コンパク ション処理の最中はデータベースの読み書き性能に悪影響を及 ぼすため，これは好ましくない．よって，コンパクションが起 こる原因となるデータの書き込みが非常に沢山行われる場合は LevelDB型はBigtable型に比べて不利である．  一方，LevelDB型は各Treeのキー範囲の被りを減らす工 夫をしているのに対して，Bigtable型はそれを行っていない． よって，データの読み出しにおいてはLevelDB型がBigtable 型に比べて有利となる．

3.

提 案 手 法

本章では，コンパクション処理の負荷を減らす方法を述べ， これを複数クライアントが存在する状況において実現できる手 法を提案する． 3. 1 キー順に従ったデータの書き込み 現時点ではBigtable型コンパクションとLevelDB型コンパ クションは書き込み性能と読み出し性能のトレードオフにある． しかし，データの書き込みをキー順に従った形で行うことで二 者に差が生まれるのではないかと我々は考える．Bigtable型は キー範囲を考慮したコンパクションを行わないため特に変化は 無いと考えられる．しかし，LevelDB型のアルゴリズムを考慮 すると，データの書き込みをキー順にすることで古いTreeと 新しいTreeのキー範囲の被りをなくすことが可能であり，こ れによってコンパクション処理時間を大きく削減できると考え られる．また，コンパクション処理の負荷が軽くなることで， データベースの処理性能が向上すると考えられる．我々の考え を検証する実験については，次章の予備実験の節（4.1節）で 述べる． 3. 2 提 案 手 法 前節にて，キー順に従ってデータを書き込むことによってコ ンパクション時間を短くし，処理性能を上げられることを述べ た．しかし，時系列データを生成するアプリケーションを考える と，複数クライアントで生成された時系列データをサーバに送 る際に発生する遅延時間の差や，各クライアント毎のクロック

図 3 Key Sorting Buffer（KSB）

のずれが原因となり，サーバにはキー順ではなく少し順序が崩 れた状態でデータが到着してしまう．この状況では，キー順に 従ってデータを書き込むと高速に処理ができるというLevelDB

型の特性を活かすことができない．

 そこで我々は，Key Sorting Buffer（以下KSBとする）を 用いた仕組みを提案する．KSBは図3に示すように複数クラ イアントとサーバ（データベース）の間に配置する．KSBでは クライアントから来る時系列データを適切な時間バッファリン グし，時系列データをキー順にソートし直した状態でサーバへ 送る．これによりサーバではキー順にデータが書き込まれるこ とになり，処理性能の向上が期待できる．

4.

実

験

本章では，3.1節で述べた我々の考えを検証するために行っ た予備実験と，既存のデータベース管理システムを用いて設計 及び実装したKSBに対する評価実験について述べる． 4. 1 予 備 実 験 本節では，3.1節で述べた我々の考え，すなわちキー順に従っ たデータの書き込みによってコンパクション時間が削減でき， データベース処理高速化が可能であるという考えを検証する ために行った予備実験について述べる． 図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型と比 表 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

図 4 コンパクション時間の比較 図 5 読み出し遅延の比較 べて書き込み性能と読み出し性能の両方において有利になると 考えられる．  図5は，実際にコンパクション時間の差が読み出し遅延に与 える影響を示したものである．図4において最もコンパクショ ン時間に差のあったLevelDB型のキー順とランダムで比較を 行っている．両者ともデータの書き込みが行われている最中に 読み出しを開始し，書き込みが終了した後もしばらく読み出し を続けている．なお，遅延測定にはYCSBを用いている． 読み出し遅延が不安定になっている箇所がコンパクション処 理の最中だと考えられ，キー順の方がランダムである場合より も早くコンパクション処理が終わっていることを確認できる． さらに，全体を通して，特にコンパクション処理の最中はキー 順の方がランダムである場合よりも読み出し遅延が小さいこ とを確認できる．従って，コンパクション処理の負荷の大小が データベースの処理性能に影響していると考えられる．

4. 2 Key Sorting Bufferを用いた実験

本節では，実際にKSBを用いて行った評価実験について述 べる．

表 2 各クライアントのタイムスタンプ生成 タイムスタンプの生成 クライアント 1 基準（± 0 [ms]） クライアント 2 クライアント 1 のタイムスタンプ + 1000 [ms] クライアント 3 クライアント 1 のタイムスタンプ + 2000 [ms] クライアント 4 クライアント 1 のタイムスタンプ + 3000 [ms]

4. 2. 1 Key Sorting Bufferの実装と実験環境

提案手法を評価するために，3章で述べた手法に基づきKSB をリバースプロキシとして実装した．リバースプロキシに実装 することで，DBMSに手を加えないミドルウェアとして機能さ せることが可能である．この設計には以下のような利点がある． • 様々なDBMSに対応することが可能である • DBMS側に手を加えないため，開発・改良が容易である • KSBが故障したとしても，元々のDBMSに影響を与え ることがない  KSBは起動時にデータをバッファリングする時間をミリ秒 単位で指定できるようにしている．  KSBの評価の際，前節と同様にDBMSにはCassandraを 用いて，クライアントにはYCSBを用いた．Cassandraでは LevelDB型コンパクションを利用する．また，利用したマシン の構成も前節と同様に表1の通りである． 4. 2. 2 実 験 まず，次のようなキーを生成するように，YCSBに対して改 造を行った． Key = "（実時間のタイムスタンプ）-"    + "（ランダムな5桁の数字）-"   + "（クライアントの番号）"  例えば以下の様なキーが生成される． 1453890479952-75034-user1 1453890480025-82028-user2  また，今回はクライアントを4台利用したが，サーバ・クラ イアント間の遅延の差がほとんど無いため，YCSBでキーを生 成する際にタイムスタンプの数字を調節することで，擬似的に 遅延の差が発生している状況を作り出して実験を行った．各ク ライアントによるタイムスタンプ生成は表2のようにした． このような状況のもとで，KSBを利用しないデータの書き 込みと，バッファリング時間を3,000ミリ秒に設定したKSB を用いたデータの書き込みそれぞれについて，コンパクション 時間を比較した．また，スループットを2,000∼14,000 [opera-tions/sec]の範囲で変更することによる結果の変化についても 記録した．実験は次のような条件で行った． • クライアント（YCSB）の数は4 • サーバ（Cassandra）のノード数は1 • 1クライアントあたり，1,000,000件のデータの書き込み • 1件あたりのデータの大きさは1KB すなわち，データベースが受け取るデータの合計量は1KB ×1,000,000×4 = 4GBとなる．実験結果は図6の通りであ る．この結果から，以下の様なことが言える． 図 6 コンパクション時間の比較（KSB） • KSBを利用しない書き込みに着目すると，スループット を12,000に指定した時に最もコンパクション時間がかかって いる．12,000よりスループットが小さい時にコンパクション時 間が短い理由は，データの書き込み処理の負荷が小さいからだ と考えられる．12,000よりスループットが大きい時にコンパク ション時間が短い理由は，データを全て書き込み終わるまでの 時間が短くなることにより，コンパクション処理とデータの書 き込み処理を並行しなければならない時間が短くなり，コンパ クションの負荷が全体的には低くなるからだと考えられる． • KSBを利用することによって必ずコンパクション時間 が短くなっている訳ではない．しかし，KSBを利用しない時に 最もコンパクション時間が長かったスループット12,000の時， KSBを利用すると最も高い割合（約15.8%）でコンパクション 時間を削減できている．このことから，比較的コンパクション 負荷の高い条件下においてKSBは効率よく働くといえる． • スループット14,000の時は，KSBを利用した書き込み の方がコンパクション時間が長くなっている．これは，KSBに バッファリングして一気にデータを書き込むことでできるC1 treeの大きさが大きくなってしまい，それが高負荷の原因に なってしまっていることが理由の一つとして考えられる． • 前節の予備実験の図4におけるLevelDB型コンパクショ ンのキー順とランダムの差のように，コンパクション時間が大 きな割合で削減されている結果は現れなかった．予備実験ほど 大きな差がでなかった理由は，崩れた順で来る時系列データは 短期的に見ればランダムであるが，長期的に見れば大体キー順 に従っているからだと考えられる．  実際に時系列データを生成するようなアプリケーションで は，大量のデータの書き込みが絶えず行われている．このよう なワークロードではコンパクションの負荷が大きくなることが 予測される．今回の結果から，データ書き込みのスループット が一定の値を超えなければ，KSBを利用することでコンパク ションの負荷を高い割合で削減することが可能であると考えら れる．したがって，実際のデータの読み書きなどのデータベー ス処理を高速化することも可能であると考えられる．

5.

関 連 研 究

本章では，本研究の関連研究について述べる． 5. 1 LSM-Treeの研究 本研究では，LSM-Treeの特にコンパクション処理に着目し ていた．Ahmadら[11]の研究では，コンパクション処理が性 能に与える影響について述べている．さらに，分散環境におい てコンパクション処理のみを行う専用のサーバを用いることで この問題を解決する手法を提案している．本研究と同様にコン パクション処理と性能の関係について述べているが，本研究は サーバにデータを送る前に工夫をしているのに対して，Ahmad らの研究ではサーバ側で工夫を行っている点が異なっている．  Ghoshら[12]の研究では，数学的なアプローチでコンパク ションについて考えている．既存のコンパクションのアルゴリ ズムについて解析した本研究とは異なり，Ghoshらの研究では さらに新たなコンパクションのアルゴリズムを提案している．   ま た ，LSM-Tree自 体 に つ い て 改 善 を 施 すbLSM [13] や pLSM [14]といった研究も行われている． 5. 2 プロキシの利用 本研究は，提案手法をプロキシに実装した．4.2.1項でも述 べたようにこの設計には様々な利点があるため，プロキシ実装 を利用している研究は他にも行われている．  memcached [15]は分散メモリキャッシュサーバであるが，本 研究と同様にプロキシとして利用することでパフォーマンスの 向上が可能である．本研究はプロキシを利用してデータベース 側の処理性能を向上させたが，memcachedをプロキシとして 利用することで，アプリケーション側の読み出し性能を向上さ せることができる．  プロキシを別の目的で利用する研究もある．高塚ら[16]の研 究では，プロキシを利用して読み出しの遅延とキャッシュの利 用率を調節することを行っている．また，矢口ら[17]の研究で は，プロキシを利用してデータの因果整合性を保障できるよう にすることを行っている．

6.

まとめと今後の課題

データベースに対してキー順にデータを書き込むことの有効 性について述べ，時系列データをキー順に処理するためのKSB を用いた仕組みを提案し，提案手法に基づいて実装したミドル ウェアの性能評価を行った．  実験により，データベースの処理性能に影響を及ぼすコンパ クション処理について，一定の条件下でKSBを用いることで コンパクション処理の負荷を削減できることを確認し，実際の データベース処理を高速化することが可能であると結論づけた．  今後の課題としては，以下の様なことが挙げられる． • 現状ではKSBはデータをバッファリングする機能しか 提供していないため，バッファリング中のデータに対する読み 出し命令を処理することができない．KSBをより実用的にす るために，バッファリング中のデータに対するデータ読み出し の機能を実装し，KSBを利用したデータの読み出し性能と利 用しない場合のデータの読み出し性能を実際のワークロードの 中で比較測定すること． • 時間のみでなくデータ量による制限の機能をつけること などを行い，より高いスループットにも対応できるようにKSB の改良を行うこと． • 今回はデータベースノード1台のみを想定していた．よ り実用的に利用できるようにするために，KSBの配備方法を 検討すること． • 時系列ではなく一般のデータに対しても処理の高速化が できる仕組みを考えること． • KSBによる効果を十分検証し，データベース内でもKSB と同様の効果を得られるようにデータベース自体の改良方法を 考えること． 謝 辞     本研究はJSPS科研費25700008，26540161の助成を受けた ものです． 文 献

[1] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C Hsieh, Deborah A Wallach, Mike Burrows, Tushar Chan-dra, Andrew Fikes, and Robert E Gruber. Bigtable: A dis-tributed storage system for structured data. ACM

Trans-actions 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 de-centralized structured storage system. ACM SIGOPS

Op-erating 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

In-formatica, 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

Ra-makrishnan, and Russell Sears. Benchmarking cloud serving systems with ycsb. In Proceedings of the 1st ACM

sympo-sium on Cloud computing, pp. 143–154. ACM, 2010.

[11] Muhammad Yousuf Ahmad and Bettina Kemme. Com-paction 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 Nir-man 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 the

2012 ACM SIGMOD International Conference on Manage-ment of Data, pp. 217–228. ACM, 2012.

[14] Jin Wang, Yong Zhang, Yang Gao, and Chunxiao Xing. pLSM: A Highly Efficient LSM-Tree Index Supporting Real-Time Big Data Analysis. In Computer Software and

Appli-cations Conference (COMPSAC), 2013 IEEE 37th Annual,

pp. 240–245. IEEE, 2013.

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