分散 Database Jungle に関する研究

大城 信康
Feb 3, 2013

概要

非破壊的木構造データベースJungleに分散実装を行い掲示板システムに特化したデーターベースを作成し、その評価を行った。

分散データベースCassandraより2倍以上速く、分散環境下においては10倍以上速い結果も確認された。


研究の目的と背景

ウェブサービスにとってデータベースは必須であり、ウェブサービスの規模に比例してデータベースへの負荷も高まる。

データベースの処理能力の高さはそのままウェブサービスの質に繋がるため、データベースのスケーラビリティの確保は重要である。

スケーラビリティ確保の方法としてデータ分散があるが、分散する方法により性能も変わってくる。

スケーラビリティのある分散データベースとしてJungleの実装を行う。

ウェブサービスにおけるデータベースの重要性

ウェブサービスへの負荷が高まることは、データベースへの負荷が高まることでもある。

データベースの性能が低ければ負荷に耐え切れずサービスはダウンする

そのため、データベースにはスケーラビリティが必要

スケーラビリティとは

システムが負荷の増大に対して柔軟に拡張して対応できる性質

主に次の2つの方法によりシステムはスケールされる

分散システムにおいてはスケールアウトによりスケーラビリティを高める

データベースのスケーラビリティ

データベースのスケーラビリティを考えるとき、どういう用途で使用するかを考えるのが重要。

  • 例えば、掲示板システムにおいては、書き込みと読み込みが速いことが求められる。

  • ウェブサービスは、サービスの内容によってスケーラビリティの確保の仕方も変わってくる。

    本研究で開発しているデータベースはコンテンツマネジメントシステム(CMS)を対象としている。

    コンテンツマネジメントシステム(CMS)

    Webコンテンツを構成するテキストや画像などのデジタルコンテンツを管理し配信するシステム。

  • 例:ブログツール、Wiki
  • 分散コンテンツマネジメントシステムに求められること。

  • Webコンテンツを分散して管理
  • スケールアウトするシステム
  • データ全体の整合性に遅延がある、結果整合性でもよい。書き込みや読み込みを優先としたデータベースが必要。

    そこで、非破壊的木構造データベースJungleの提案を行った。

    非破壊的木構造データベースJungle

    JungleはスケーラビリティのあるCMSの設計を目指して当研究室で開発されているデータベース。

    データを木構造で、さらに非破壊で保持する。


    破壊的木構造

    木構造の通常のデータ表現

    破壊的木構造は、木構造により保持しているデータの編集をデータを直接書き換えることで行う

    破壊的木構造

    破壊的木構造ではデータの編集中にそのデータを読むことができない

    編集が完了するまでまたなければならない

    非破壊的木構造

    非破壊的木構造は一度作成したデータは変更しない

    新しい木構造を作成することでデータの編集を行う

    非破壊的木構造におけるデータ編集

    目的とするノード5ををコピーして内容を編集する。ノード100となる

    ルートノードから目的のノード5までに続くルートノードとノード2のコピーとりノード100と繋げる

    非破壊的木構造におけるデータ編集と読み込み

    新しく作成したルートノードに変更を加えていないノードへの参照を持たせる。新しい木構造のデータができる

    最新のルートノードの登録を新しく作成した側のルートノードへと登録する

    非破壊的木構造の利点

    非破壊的木構造は通常の木構造である破壊的木構造に比べ、以下のような利点を持つ

    ロックが少なく、いつでもコピーが可能なことから、非破壊的木構造はスケーラブルなシステムに有用となる

    Jungleの分散設計

    ここまでJungleに実装されている非破壊的木構造の利点について述べた。

    次に、Jungleにおける分散設計について述べる。

    データ分散を行うにあたり、まず考えることはトポロジーの形成と他のノードからデータの伝搬の仕方である。

    Jungleはこの問題に対し、ツリートポロジーを形成し、データ編集の際に発生するcommit logを他のノードに流すことで解決する。

    Jungleの分散設計:トポロジー形成とログによるデータ分散

    ツリートポロジーを形成 commit log伝搬によるデータ分散

    サーバノード同士でツリートポロジーを形成する。データ編集をどのように行ったのかを示すログ commit log を伝搬させデータの分散を行う。

    非破壊的木構造の利点を活かした分散設計

    Jungleで扱うつもりのデータは結果整合性でもよいCMSを想定していることを始めに説明した。

    そこでJungleはMergeを使うことでデータの整合性をとることにした。

    Mergeとは、2つ以上の変更を1つの変更にまとめることである。

    分散システムにおいては、2つ以上のデータの更新が同じデータに対して行われていた場合、 更新を受け取って新しいデータを作ることを指す。

    Mergeは自動で解決出来る場合とそうでない場合がある。

    Mergeによる更新の衝突を自然に解決

    上の図は通常のデータ更新を示す

    下の図は、同じ木に対して2つのデータの更新があったが編集を無事終えるケースを示す

    Mergeによる更新の衝突が自然に解決できない場合

    木の同じノードに対してデータの編集が行われた場合、どのような編集結果にすればよいかわからない。

    どのような木が組まれ、どのようにデータを保存するかはアプリケーション毎に変わってくる。そのため、アプリケーション毎に Mergeアルゴリズムは考えなくてはならない。

    JungleとMergeの相性

    Jungleは非破壊で過去のデータも保持しているため、更新時に過去のデータを参照して自然なMergeを行うことが可能。

    自然にMergeできない場合においても、アプリケーション毎にMergeアルゴリズムを設計することで対応する。

    Mergeが自動で行われるようになれば、Jungleで扱う木構造データは編集を自由に行うことができる。

    木構造データが自由に行えるようになれば、Jungleはデータのリクエストに対して手元のデータを返すことができる。

    古いデータを編集されたものが更新されても、いずれはMergeにより最新のデータと合わせられるから。

    Jungleの分散実装

    以上がJungleにおける分散設計になる。


    この分散設計を元にJungleのサーバノード同士でツリトポロジーを構成し、ログによるデータ分散を実装した。

    また、Mergeの例として掲示板プログラムにおけるMergeの実装も行った。

    Jungleの分散実装:掲示板システムにおけるMerge

    Jungleではアプリケーション毎にMergeアルゴリズムを設計

    後述する性能比較に用いた掲示板システムにおけるMergeの実装を考える

    掲示板システムにおけるデータ構造を以下に示す

    Jungleの分散実装:掲示板システムにおけるMerge

    1

    2

    3

    分散データベースJungleの評価

    分散データベースとしてJungleの性能を評価する。

    分散Key-ValueデーターべースCassandraと比較を行う。

    比較方法は、Jungle, Cassandra をそれぞれバックエンドとした簡易掲示板を作成する。

    掲示板に対してHTTP Requestで並列に読み込みと書き込みの負荷をかけ計測する。

    レスポンスが返る平均時間と標準偏差を求めグラフ化する

    JungleとCassandraの比較方法

    実験は以下の2つを行う

    実験1:サーバ単体への負荷実験2:複数台のサーバに対する負荷

    複数のクライアントから単体のサーバへ負荷をかける

    複数のクライアントから複数のサーバへ負荷をかける

    サーバ単体の性能と, 分散環境下における性能の2つを調べる。

    分散環境下におけるノードは全て繋がっている

    実験に使用するサーバの仕様

    ブレードサーバ
    CPU Intel(R) Xeon(R) CPU X5650@2.67GHz
    コア数 24
    Memory 132GB
    OS Fedora 16
    HyperVisor なし(物理マシン)

    並列環境

    VMWareクラスタKVMクラスタ
    台数4812
    CPU Intel(R) Xeon(R) CPU X5650@2.67GHz Intel(R) Xeon(R) CPU X5650@2.67GHz
    コア数 4 4
    Memory 8GB 8GB
    OS Fedora 16 Fedora 16
    HyperVisor VMWare ESXi KVM (Linux Fedora 16)

    実験1:単体サーバへの負荷

    実験1:単体サーバへの負荷(読み込み)

    ブレードサーバ一台に対して複数のクライアントからの負荷

    読み込みの実験結果

    JungleがCassandraより良い結果を示している

    クライアントが55台のときのJungleの最速とCassandraの最遅は3倍近く離れている

    実験1:単体サーバへの負荷(書き込み)

    ブレードサーバ一台に対して複数のクライアントからの負荷

    書き込みの実験結果

    読み込み同様Jungleのほうが良い結果を示している

    読み込みよりJungleとCassandraの結果が重なる部分が減っている

    実験1の考察

    読み込み、書き込みともにJungleの性能がよく。平均だけみても2倍以上早い部分もある。

    特に書き込みに関してはクライアントの数が増えるにつれ差が開いている。

    これはJungleが全体的にロックが少ないことが要因としてあげられる。

    Jungleは非破壊でデータの保持をするため、読み込みは自由に行える。書き込み時には木のコピーをとりルートノードを入れ替える ときのみロックが発生する。

    実験2:分散環境下における負荷

    実験2:分散環境下における読み込み

    読み込みの実験結果

    CassandraはConsistency Level ONE(赤)とQUORUM(緑)両方を測定

    Jungleは1秒から5秒をキープ

    実験2:分散環境下における書き込み

    書き込みの実験結果

    CassandraはConsistency Level ONE(赤)とQUORUM(緑)両方を測定

    Jungleは5.5秒から7.3秒をキープ

    実験2の考察

    こちらもJungleがCassadraより良い結果を示した。実験1よりも差がでている。

    Jungleのグラフが横ばいになっていることに注目したい。

    Jungleはリクエストに対し手元にあるデータを返す。そのためノードの数が増えてもレスポンスの早さを維持できる。

    Cassandraはデータを持っている数台のノードに読み込みに行くという作業が入るためJungleより遅くなってしまう

    Jungleは同期を取らないためデータ全体の整合性は落ちるが、分散管理システムを参考にした設計の有用性を示すことができた。

    まとめ

    本研究では非破壊的木構造Jungleに分散データベースの実装を行った

    非破壊的木構造における利点を述べ、スケーラビリティの高い分散版管理システムとの類似性を述べた

    Mergeアルゴリズムの1つとして掲示板プログラムにおけるMergeについて設計・実装を行った

    性能比較の実験のためJungle、Cassandraで利用できる簡易掲示板の作成を行った

    実験は単体サーバと分散環境下において行い、どちらともCassandraよりよい結果をえることができた

    今後の課題

    データ分割の実装

    今後の課題

    Mergeアルゴリズムの設計

    今後の課題

    過去のデータの掃除について

    Mergeは必ずできるのか

    Mergeを必ず行うことは難しい

    例えば、更新するデータが画像だった場合、2つの画像のデータから新しい画像を作るわけにはいかない。

    後に更新したものを優先するといった方法をとるか、ユーザの選択に委ねるしかない。

    分散Key-ValueストアCassandraの特徴

    ring型トポロジーを形成。ring上にはHash値があり、書き込むデータのキーのハッシュ値により書き込むノードを決定

    1つのデータの複製を最大何とるかというReplication factorの設定がある。

    Consistency Levelというデータの読み書きの際に何台のノードから読み書きするかを決定できる

    Consistency LevelにはONE,QUORUM,ALLがある。QUORUMはReplication factorの数/2+1 のノードに読み書きする。

    Jungleの分散設計:分散版管理システム

    Jungleは分散設計を行うにあたってGitやMercurialといった分散版管理システムを意識している

    分散版管理システムとは多人数によるソフトウェア開発において変更履歴を管理するシステム

    分散版管理システムは次の特徴とAPIを持つ

    Jungleの分散設計:分散版管理システム

    分散版管理システムAPI

    分版版管理システムはリポジトリが壊れても別のリポジトリよりデータを復旧できることと、push/pullそれとMergeによる整合性 の確保で、高いスケーラビリティを持っている

    Jungleの分散設計:分散版管理システム

    Jungleと分散版管理システムには似通った点がある

  • どちらもデータのコピーが自由
  • データ更新しても過去のデータに影響を与えない

  • 同じAPIを実装することで、分散版管理システムと同じく高いスケーラビリティが期待できる

    具体的には