DEIM Forum 2013 F4-5

クラウドストレージにおける読み出し性能と書き込み性能のトレードオフ動的調整手法
矢口尭†

首藤一幸 †††, †† 東京工業大学 大学院情報理工学研究科 数理・計算科学専攻〒 152–8552 東京都目黒区大岡山 2–12–1–W8–43
E-mail: †yaguchi.t.ac@m.titech.ac.jp, ††shudo@is.titech.ac.jp
あらまし

既存の永続型クラウドストレージは読み出し性能または書き込み性能のいずれか一方に特化した設計がなされている．これらのクラウドストレージ利用者は，読み出し性能特化または書き込み性能特化のどちらか一方をシステム稼働前に選択することになる．これでは，読み書き要求の比率が時間帯で変化するようなワークロードを効率的に処理することができない．この問題に対処する方法として，同一システム内で読み出しと書き込みの性能特性をシステムの稼働中に切り替える手法を提案する．また，提案手法に基づき設計と実装を行ったクラウドストレージの評価結果を報告する．
キーワード

分散データベース，クラウドストレージ

A Trade-Oﬀ Adjusting Technique between Write and Read Performances
for Cloud Storage
Takashi YAGUCHI† and Kazuyuki SHUDO††† ,††Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology
2-12-1-W8-43 Ookayama, Meguro, Tokyo, 152–8552 Japan
E-mail: †yaguchi.t.ac@m.titech.ac.jp, ††shudo@is.titech.ac.jp
Key words distributed database, cloud storage

1. は じ め にMySQL [4] は読み出し性能に特化している．
この読み書き性能の違いは，ストレージエンジンの設計の違クラウドストレージとは大規模で構造が複雑なデータを効率いに起因する [12] [15]．ストレージエンジンとは，クラウドス良く処理するための分散データベース管理システムである．各

トレージの中で二次記憶装置に対するデータの読み書きを行うマシンに配置されたデータベースノードがクラスタを構成し，構成部分である．このストレージエンジンを設計する上で，読連携して処理を行う．RDBMS 等の従来のデータベース管理シ

み出し性能と書き込み性能はトレードオフの関係にある．

ステムと比べて利用者に提供する機能を制限し，また保証する

書き込み性能を高めるためには，書き込みをなるべくまとめ整合性を緩めることでスケールアウトを容易に，また柔軟に行て行うことが重要である．書き込み性能に特化したストレージ

うことを可能にしている．

エンジンでは，読み出し時にはディスク上の複数箇所からラン様々なクラウドストレージが設計・実装されており，それぞ

ダム I/O でデータを読み出す必要があり，読み出し性能が犠牲れ長所と短所がある．これは，クラウドストレージの設計にトとなる．一方，読み出し性能を求めると書き込み時にランダムレードオフがあり，それぞれに想定するアプリケーションがあI/O が必要となり，書き込み性能が犠牲となる．

るからである．

このようなトレードオフがあるため，ストレージエンジンは本研究では，特に読み出し性能と書き込み性能のトレードオ

読み出し性能と書き込み性能を同時に高めることができない．

フに着目する．従来のクラウドストレージは書き込み性能か

このような背景から，既存のクラウドストレージの多くは，読読み出し性能のどちらかに特化した設計がなされている．例

み出し性能または書き込み性能のどちらかに特化した設計がな

えば，Apache Cassandra [1] [2] や Apache HBase [3] は書き込されている．複数種類のストレージエンジンを差し替えられるみ性能に特化しているが，一方 Yahoo! Sherpa や Sharded

クラウドストレージもあるが，それでもシステム稼働前に一つのストレージエンジンを選択することになる．
このような既存のクラウドストレージでは，読み出し要求との読み書き方式とは多少異なっている点があるが，両者は本質的に同じアイデアを用いている．

書き込み要求の比率が時間帯で変化する場合に，効率的に処理2. 2 定足数を用いた読み書き方式することができない．なぜならば，これらのクラウドストレー定足数を用いた読み書き方式は，複製されたデータに対してジ利用者は，読み出し性能と書き込み性能のどちらに特化する操作を行うためのプロトコルである．この読み書き方式に従うかをシステムの稼働中に変更することができないからである．

ことで，読み出し値がそれ以前の全ての書き込み結果を反映しそこで本研究では，同一クラウドストレージ内で読み出し性たものであることが保証される．また，読み書き操作に関して能と書き込み性能のトレードオフを動的に調整する手法を提案

比較的高い可用性を提供することも特徴の一つである．

する．本手法を用いることでシステムが稼働中でも，読み出し書き込みと読み出しの手順を説明する．以下では，各データ性能と書き込み性能との間で特化する性能を変更することが可にはタイムスタンプやバージョン番号等の，更新順序を決める能になる．

ための情報が付加されていると仮定する．また，複製数を N と

本論文の構成は以下のとおりである．2 章で提案手法のための予備知識を述べる．3 章で提案手法を述べる．4 章で提案手法に基づき設計・実装を行ったクラウドストレージについて述
べ，5 章でそのクラウドストレージの性能評価の結果を示して考察する．6 章で関連研究を述べる．7 章で本研究の貢献と今し，パラメータ R と W は条件式 R + W > N を満たすとする．
まず，書き込みの手順を示す．
（ 1 ） 複製を持つ全てのノードに書き込み要求を行う．
（ 2 ） W 個のノードからの成功応答を待つ．

後の課題をまとめる．
（ 3 ） W 個のノードからの成功応答が確認出来た場合，そ2. 予 備 知 識
本章では，提案手法およびその実装のベースとした MyCas-の書き込みが成功したとみなす．
次に読み出しの手順を示す．

sandra [12] [15] について概要を示す．また，提案手法で用いる定足数を用いた読み書き方式についても述べる．

2. 1 MyCassandra（ 1 ） 複製を持つ全てのノードに読み出し要求を行う．
（ 2 ） R 個のノードからデータを読み出せるまで待つ．

MyCassandra はストレージエンジンを差し替え可能にしたクラウドストレージである．MyCassandra の利用者は，複数のストレージエンジンからアプリケーションに適切なものを選択出来る．しかしながら，システムの稼働中にストレージエンジンを変更することはできないため，クラウドストレージの性能特性をサービスを止めずに変更することはできない．
また，MyCassandra を用いた，読み出し性能と書き込み性能を両立させる手法として MyCassandra Cluster [12] [15] がある．この手法は，種類の異なるストレージエンジンで動作するノード群にデータの複製をとり，読み出し要求と書き込み要求をそれぞれ効率良く処理できるノードに割り振るというものである．しかし，両立のために，一部のノードはデータをメモリ上に保持するストレージエンジンで動作する必要があり，単一マシンで担当するデータ量の上限が小さくなることや，オンメモリストレージエンジン上のデータが障害等で消失した場合，回復処理のため一時的に性能が低下するという課題がある．

MyCassandra は Apache Cassandra というクラウドストレージにストレージエンジンの差し替え機能を追加した拡張である．
以下，Apache Cassandra について概要を示す．

Apache Cassandra は非集中型のアーキテクチャを特徴とするクラウドストレージである．Apache Cassandra で構成するクラスタの全てのノードは同一の機能を持ち，全体を管理するような特別なノードは存在しない．このようなアーキテクチャゆえに単一故障点がなく，高い可用性を達成している．

Apache Cassandra は，読み出し処理と書き込み処理を定足数を用いた方式で行う．提案手法も同様の読み書き方式を用いる．以下にその読み書き方式を説明する．Apache Cassandra（ 3 ） 読み出した R 個のデータの中で最新のものを選択する．
上記のパラメータ R と W をそれぞれ読み出し定足数，書き込み定足数と呼ぶ．
この手順で，読み出し値がそれ以前のすべての書き込み内容を反映したものであることが保証されるのは，R + W > N という条件があり，読み出しを行ったノードの中に，先行の書き込みが行われたノードが少なくとも一つは含まれるためである．
提案手法における，この手順の重要な点は，W 個のノードに書き込みが完了するまでの遅延が，その書き込み全体の遅延となることである．同様に，読み出しも R 個のノードからデータを読み出すまでの遅延が，その読み出し全体の遅延となる．
同じように定足数を用いた読み書き方式で，条件 R + W > Nに加え，条件 W > N/2 を追加したものがある．この方式では，書き込み前にノードへアクセスし，最新のタイムスタンプを取得する．W > N/2 はこの処理のための条件である．しかしながら，書き込み前のノードへのアクセスは書き込み性能を低下させる．そこで Apache Cassandra などで用いられる上記の読み書き方式では，各マシンのシステムクロックが十分同期されていることを前提に，書き込み時のタイムスタンプとして各マシンのシステムクロックを利用することで上記の処理を省略している．よって，このような読み書き方式では W > N/2の条件は必要ない．提案手法もその方式を採用しているが，条件 W > N/2 を満たす方式を採用しても，同様の効果を得られる可能性はある．この検討は今後の課題とする．

3. 提 案 手 法

一方，書き込み時には W 個のノードに対して書き込みが完了するまで待つ．W は書き込み性能特化なノードの数より大

本論文では，読み出し値が以前の書き込み内容を反映したもきいので，書き込みの完了を待つ W 個のノードの中に，少なのであることを保証しつつ，クラウドストレージの読み出し性

くとも 1 つは読み出し性能特化なノードが含まれる．よって，

能と書き込み性能のトレードオフを動的に調整する手法を提案

読み出し性能特化なノードの書き込み遅延が全体の書き込み遅する．

延に影響を与えることになる．つまり，書き込み全体を律速す提案手法では，読み出し性能に特化したストレージエンジンと書き込み性能に特化したストレージエンジンの両方を利用し，読み書き定足数をシステムの稼働中に変更することで，性能を読み出し特化または書き込み特化に切り替える．

るのは，読み出し性能特化なノードの応答速度となる．
以上より，上記の設定をした場合，全体として読み出し性能特化のストレージエンジン性能となる．

3. 2 書き込み性能特化となる定足数の決定方法

以下では，各データベースノードは書き込み特化なストレー

3. 1 節と同様の方法で性能を書き込みに特化させることがでジエンジンまたは読み出し特化なストレージエンジンのどちらきる．書き込みに特化させるためには，次の通りにパラメータか一つを用いて読み書き処理を行うとして議論を進める．一つR,W を定める．のノードが複数のストレージエンジンを用いる構成も考えられるが，そのような構成にも提案手法は同様に適用できる．書き（ 1 ） 書き込み定足数 W を，複製を持つ書き込み性能特化なノードの数以下に定める．

込み特化なストレージエンジンを用いるノードを書き込み特化なノード，また読み出し特化なストレージエンジンを用いる（ 2 ） 読み出し定足数 R を，複製数 N と (1) で定めた書き込み定足数 W に対して，R + W > N を満たすようノードを読み出し特化なノードと呼ぶ．に定める．

本章ではまず，読み書き定足数の設定によってクラウドストレージの性能が読み出し特化または書き込み特化となることを上記の方法で定足数を定める場合，読み出し定足数 R は読み出示す．次に，システムの稼働中に読み書き定足数を変更する手し性能特化なノード数より大きいことに注意する．

順を示す．

3. 1 節と同様の理由で，上記の方法で定足数を定めることで，3. 1 読み出し性能特化となる定足数の決定方法

遅延は書き込み性能特化なストレージエンジンのものとなる．

本手法では，読み出し性能に特化したノードと書き込み性能つまり，書き込み全体を律速するのは書き込み性能特化なノーに特化したノードの両方を用いてデータの更新・参照を行う．

ドの応答速度であり，読み出し全体も書き込み特化なノードのつまり，各データは最低でも 2 つのノード上に複製される．

応答速度に律速される．

読み出しに特化させるためには，次の通りにパラメータ R,Wを定める．
（ 1 ） 読み出し定足数 R を，複製を持つ読み出し性能特化なノードの数以下に定める．

3. 3 動的な定足数の変更手順
3. 1 節，3. 2 節では，読み出し性能特化となるパラメータの定め方と書き込み性能特化となるパラメータの定め方を示した．
それぞれの定め方は，読み出し性能特化なノード上と書き込み性能特化なノード上の両方にデータを複製する点では共通して（ 2 ） 書き込み定足数 W を，複製数 N と (1) で定めた読みいる．異なるのは，読み書き定足数の定め方だけである．つま出し定足数 R に対して，R + W > N を満たすようにり，読み出し性能特化なノードと書き込み性能特化なノードが定める．

ある下で，読み書き性能の偏りは読み書き定足数のみに依存する．従って，システムの稼働中に読み書き定足数を変更するこ

上記の方法で定足数を定める場合，書き込み定足数 W は複製を持つ書き込み特化なノードの数より大きいことに注意する．
読み出し性能特化となる設定の例として，書き込み性能特化なノード 2 つと読み出し性能特化なノード 2 つ，合計 4 つのノード上にデータを複製し，読み書き定足数を R = 2, W = 3とする．これは，条件式 R + W > N を満たす．とで，読み出し性能と書き込み性能との間で特化させる性能をサービスを止めずに変更することができる．
しかしながら，読み書き定足数を動的に変更する際に，単純に変更出来ない場合がある．変更後の読み出し定足数を R，それまで用いてきた書き込み定足数の最小値を Wmin として，条件障害等で読み出し性能特化なノードから読み出しが行えない場合を除き，上記の方法で定足数を定めることで，遅延は読みR + Wmin > N(1)

出し性能特化なストレージエンジンのものとなる．読み出し時を満たしていない場合，書き込み定足数を変更する前の書き込には R 個のノードからデータを読み出せるまで待つ．R が読み結果が，読み出し定足数を変更した後の読み出し時に反映さみ出し性能特化なノード数以下であることから，読み出し特化れていることを保証出来ない．

なノードからのデータ取得に失敗がなければ，書き込み性能特本手法では，同期をとる方法を用いることでこの問題に対処化なノードの読み出し遅延は全体の読み出し遅延に影響を与えする．この方法では，(1) の条件式を満たしていない変更の場ない．つまり，読み出し全体を律速するのは，読み出し性能特合は同期を取る．同期をとっている間も読み書きを可能にする化なノードの応答速度となる．

ため，以下のような手順を踏む．

（ 1 ） 変更後の書き込み定足数 W が現在の書き込み定足数より大きい場合，書き込み定足数のみ変更する．
（ 2 ） R + Wmin を満たしていない場合，複製間の同期をとる．

更新操作を完了できない可能性が高くなる．
本実装では，定足数は対象範囲のデータを担当しているノードだけが保持する．定足数は実際のデータと同様に分散して保持され，また定足数の更新操作は担当ノード間でのみ合意をと（ 3 ） 読み出し定足数を変更後の値に変更する．
同期をとった場合，Wmin は変更後の W に初期化する．
変更前の書き込み定足数で書き込まれた内容は，同期によって整合性が保証されるので，それらの結果が読み出し定足数を変更した後の読み出し時に反映されていることが保証される．
また，同期をとっている間の書き込みは変更後の書き込み定足数で行われるので，それらの結果が読み出し定足数を変更後の読み出し時に反映されていることが保証される．

4. 実

定足数の変更に対して合意をとるノードが多くなり，定足数の装提案手法に基づき，読み出し性能と書き込み性能のトレードオフを動的に調整できるクラウドストレージを MyCassandraベースで設計・実装した．
提案手法を機能させるために，クラウドストレージは以下の機能を持つ必要がある．
（ 1 ） 各ノードが用いるストレージエンジンを選択可能．
（ 2 ） 読み出し定足数と書き込み定足数をシステムの稼働中に変更可能．

れればよい．

4. 3 読み出し手順と書き込み手順の変更
上記の変更に伴い，MyCassandra の元の読み書き手順を変更する．MyCassandra では定足数はクライアントの処理要求に付されるので，サーバに処理要求が届いた時点で定足数を取得できることを前提とした処理手順となっている．
本実装では要求の処理に必要な定足数を別途取得する必要がある．しかしながら，定足数を保持しているノードとデータを保持しているノードが一致していることから，定足数を取得するためだけの別途の通信は必要ない．定足数を用いた読み書き（2. 2 節）を行うノードは，読み書き要求に対する応答と共に定足数を取得できる

4. 4 定足数の動的変更方法
3. 3 節で述べた定足数の変更手順を実装した．この手順に必要な情報である Wmin は定足数と同様にその範囲を担当するノードが保持する．

5. 実

験

本章では，提案手法を次の二つの観点から評価する．まず，

3. 1 節，3. 2 節で述べた読み出し性能特化と書き込み性能特化(1) は MyCassandra が既に備えている機能である．そこで，のパラメータについて，それぞれの読み出し性能と書き込みMyCassandra に機能 (2) を追加実装した．

性能を評価する．次に，読み書き定足数の変更に伴うオーバーそのために既存の設計を一部変更する．MyCassandra は，定足数を利用者が管理することを前提としている．定足数はク
ライアントが処理要求に含めてサーバに送信する．

ヘッドを評価する．評価の対象は，MyCassandra をベースとして実装したクラウドストレージである．
性能評価には，Yahoo! Cloud Serving Benchmark（YCSB）

しかし，定足数をシステムの稼働中に変更するためには，定[7] を用いる．YCSB は，様々なクラウドストレージを公平に評

足数はサーバ側で管理すべきである．そうでなければ，複数の価することを目的として設計・開発されたベンチマークフレー

クライアントが存在する場合，定足数の変更に対するクライアムワークである．YCSB の利用者は読み出し処理と書き込み処ント間の合意をクラウドストレージ利用者に任せることになっ理の比率やデータへのアクセス分布，また 1 秒あたりに発行すてしまうからである．

る処理要求数の目標値を指定できる．その設定に基づき YCSB

よって，本実装ではサーバ側で定足数を管理する．

が対象のクラウドストレージに対して読み出しと書き込みを実4. 1 定足数を管理するデータ単位行し，各処理に要した時間，つまり遅延を集計する．

定足数を各データ毎に持たせれば，読み出し性能と書き込み今回の測定では，書き込み比率が高い Write-Only，Write-性能のトレードオフをデータ単位で細かく調整できる．しかしHeavy，読み出し比率が高い Read-Only，Read-Heavy の 4 つながら，データ毎の管理は現実的ではない．なぜならば，定足のワークロードで実験する．表 1 に，ワークロード毎の読み出数は読み書き処理に用いるメタデータなので，性能のためにはし処理と書き込み処理の割合を示す．データへのアクセス分布

メモリ上に置くことが望ましいが，しかし，全てのデータにつとしては Zipf 分布を用いる．Zipf 分布は，データの新しさとはいて定足数をメモリ上に置くことは難しいからである．

無関係に各データへのアクセス頻度が決まるようなアプリケー

よって，データの適当なグループ毎に定足数を持たせることションのアクセス分布を模す．になる．本実装では，データアクセスに用いるキーの空間を任

本実験では，書き込み性能特化のストレージエンジンとして，意の範囲に分割して，それぞれの範囲毎に定足数を持たせられ

Apache Cassandra 1.1.6 のものを，また読み出し性能特化のるようにした．

ストレージエンジンとして MySQL 5.5.29 の InnoDB を用い

4. 2 定足数を管理するノードある定足数を多くのノードが保持することには様々な問題がある．各ノードがメモリ上に保持する定足数が多くなる上に，る．表 2 に実験マシンの構成を示す．

5. 1 読み出し性能と書き込み性能の評価
読み出し性能特化，書き込み性能特化それぞれのパラメータ

表 1 測定に用いるワークロード

Workload 書き込み割合 読み出し割合 アクセス分布
Write-Only

100%

0%

Zipf 分布Write-Heavy

50%

50%Zipf 分布

Read-Heavy

5%95%

Zipf 分布

Read-Only

0%100%

Zipf 分布

表 2 実験マシンの構成

OSLinux 3.3.4-3

CPU 2.40 GHz Xeon(R) E5620 × 2
メモリ

8GB RAMJava 仮想マシン

Java SE 7 Update 4
図 1 ワークロード毎の読み出し遅延の比較について，読み出し性能と書き込み性能を評価する．3. 1 節，

3. 2 節の方法で読み出し性能特化なクラスタと書き込み性能特化なクラスタを構成し，YCSB を用いて各ワークロードに対する読み出し遅延と書き込み遅延をそれぞれのクラスタについて測定する．また，Apache Cassandra 1.1.6 についても，同様の測定を行う．
実験には 5 台のマシンを用いる．4 台のマシンにそれぞれノードを配置してクラスタを構成し，残りの 1 台で YCSB を実行する．複製数 N は 4 とし，データの件数は 1000 万とした．1 件あたり 1 KB，合計で 40 GB 以上のデータとなる．各マシンの搭載メモリは 8 GB であり，すべてのデータがメモリ
図 2 ワークロード毎の書き込み遅延の比較上に載ることはない．
クラスタは 2 つの書き込み特化なノードと 2 つの読み出し特化なノードで構成する．また，読み出し特化なパラメー(R, W ) = (3, 2) への変更は同期を必要とせず，単純に定足数を

タ は (R, W ) = (2, 3) と し ，書 き 込 み 特 化 な パ ラ メ ー タ は変更するだけで済むからである．

(R, W ) = (3, 2) とした．
図 1, 図 2 に，読み出し処理と書き込み処理の遅延をワークロード毎に示す．クライアント数を調整することで，処理要求定足数の変更完了後は，書き込み性能特化となることからWrite-Only のワークロードをより速く処理していることが確認できる．

を 2500 回/秒とした．読み出し性能特化なクラスタと書き込み

図 4 は Read-Only の ワ ー ク ロ ー ド 実 行 中 に 定 足 数 を性能特化なクラスタを比較すると，どのワークロードでも，読(R, W ) = (3, 2) から (R, W ) = (2, 3) へ変更した時の実験

み出し処理の遅延は読み出し性能特化なクラスタの方が小さく結果である．つまり，書き込み性能特化のクラスタから読み出なっており，書き込み処理の遅延は書き込み性能特化なクラスし性能特化のクラスタに切り替えた．

タの方が小さくなっていることが確認できる．
また，書き込み性能特化のクラスタは Apache Cassandra と同等の書き込み遅延を達成している．

先と同様に，ワークロードを実行開始から 200 秒後に定足数の変更を始めている．この定足数の変更は先の変更よりも長い時間がかかっており，30 分程度かかっている．これは，定足数

5. 2 定足数の動的な変更手法の評価(R, W ) = (2, 3) から (R, W ) = (3, 2) への変更は同期をとる必

次に，定足数の変更に伴うオーバーヘッドを評価する．3. 3

要があるからである．しかしながら，切り替え中も 3 msec 程

節で示した方法を用いて，ワークロードの実行中に読み書き定度の遅延の増加で処理を継続して行えている．

足数を変更し，その間の平均遅延を単位時間毎に測定した．ク

また，定足数の変更完了後は，読み出し性能特化となること

ライアント数は 15 に設定し，それ以外は 5. 1 節と同じ条件でから Read-Only のワークロードをより速く処理していること

実験を行った．

が確認できる．

図 3 は Write-Only の ワ ー ク ロ ー ド 実 行 中 に 定 足 数 を(R, W ) = (2, 3) から (R, W ) = (3, 2) へ変更した際の実験結果である．つまり，読み出し性能特化のクラスタから書き込み性能特化のクラスタに切り替えた．

6. 関 連 研 究Diverget Physical Design [6] は，異なる設定で動作するノード群にデータの複製をとり，種々の読み出し要求をそれぞれ効

この実験では，ワークロードの実行開始から 200 秒後に定率良く処理できるノードに割り振るというデータベースのアー足数の変更を始めている．この定足数の変更は 20 秒程度でキテクチャである．まず，データの複製を持つ各ノードのイン行うことが出来ている．これは，定足数 (R, W ) = (2, 3) からデックスやマテリアライズドビュー等をそれぞれ異なる種類の的に調整する手法を述べ，また提案手法に基づき設計・実装したクラウドストレージを評価した．
実験により，読み出し性能特化なパラメータは読み出し処理を低遅延で行うことができ，書き込み性能特化なパラメータは書き込み処理を低遅延で行えることを確認した．また，読み書
き定足数の変更に伴うオーバーヘッドを測定した．
本論文で提案した読み書き定足数の変更手法では，ブロッキングすることなく継続的に読み書きできるものの，書き込み性能特化から読み出し性能特化への切り替え時は，大量のデータに対して同期を取る必要があるため一時的に性能が下がる．より効率の良い読み書き定足数の調整手法を探ることが，今後の図 3 読み出し特化から書き込み特化への切り替え中のアクセス遅延課題である．

謝辞

本研究は科研費 (24650025) および独立行政法人情報通信機構（NICT）委託研究「新世代ネットワークを支えるネットワー
ク仮想化基盤技術の研究開発」の助成を受けたものである．
文

図 4 書き込み特化から読み出し特化への切り替え中のアクセス遅延

読み出し処理に特化した設定にする．そして，読み出し処理の内容に応じて，その処理が得意なノードに要求を割り振ることで，読み出し性能を高める．ノード間で異なる設定を行う点は本研究と共通しているが，読み出し処理性能と書き込み処理性能のトレードオフは考慮していない．
定足数（もしくはそれを一般化した Quorum System）をシステムの稼働中に変更する手法は，これまでにいくつか提案されている [9] [10] [14]．これらの研究の目的は，いずれも読み書き操作の可用性を高めることである．例えば，定足数を用いた読み書き方式（2. 2 節）で，複製数と読み書き定足数がN = 3, R = 1, W = 3 の場合，一つのノードが故障するだけで書き込み操作を行えなくなる．しかしながら，システムの稼働中に読み書き定足数を R = 2, W = 2 に変更することで，継続して読み書き操作を行うことができる．本研究では，システムの稼働中に定足数を変更するというアイデアを，可用性を高めるためだけでなく，読み出し性能と書き込み性能のトレードオフ動的調整にも応用できることを示した．また，既存研究では言及されていない，処理要求をブロックすることなしで定足数を変更する手順を示した．

7. まとめと今後の課題
本研究では，クラウドストレージにおける読み出し性能と書き込み性能のトレードオフを動的に調整する手法を提案した．
読み出し値が以前の書き込み内容を反映したものであることを保証しつつ，読み出し性能と書き込み性能のトレードオフを動

献[1] The Apache Software Foundation. Apache Cassandra.
http://cassandra.apache.org/.
[2] Lakshman, A. and Malik, P.: Cassandra - A Decentralized
Structured Storage System, Proc. LADIS ’09 (2009).
[3] The Apache Software Foundation. Apache HBase.
http://hadoop.apache.org/hbase/.
[4] Oracle Corporation. MySQL.
http://www.mysql.com/.
[5] Fay Chang, Jeﬀrey Dean, Sanjay Ghemawat, Wilson C.
Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. Bigtable: a distributed storage system for structured data. In Proceedingsof the 7th USENIX Symposium on Operating Systems Design and Implementation - Volume 7, OSDI ’06, pp. 15–15,Berkeley, CA, USA, 2006. USENIX Association.
[6] Mariano P. Consens, Kleoni Ioannidou, Jeﬀ LeFevre, andNeoklis Polyzotis. Divergent physical design tuning for replicated databases. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data,
SIGMOD ’12, pp. 49–60, New York, NY, USA, 2012. ACM.
[7] 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, SoCC ’10, pp. 143–154, New
York, NY, USA, 2010. ACM.
[8] Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin,
Swaminathan Sivasubramanian, Peter Vosshall, and WernerVogels. Dynamo: amazon’s highly available key-value store.
SIGOPS Oper. Syst. Rev., Vol. 41, No. 6, pp. 205–220, October 2007.
[9] Maurice Herlihy. Dynamic quorum adjustment for partitioned data. ACM Trans. Database Syst., Vol. 12, No. 2,pp. 170–194, June 1987.
[10] S. Jajodia and David Mutchler. Dynamic voting algorithms
for maintaining the consistency of a replicated database.
ACM Trans. Database Syst., Vol. 15, No. 2, pp. 230–280,June 1990.
[11] Xing Lin, Yun Mao, Feifei Li, and Robert Ricci. Towards
fair sharing of block storage in a multi-tenant cloud. In Proceedings of the 4th USENIX conference on Hot Topics inCloud Ccomputing, HotCloud’12, pp. 15–15, Berkeley, CA,

USA, 2012. USENIX Association.
[12] Shunsuke Nakamura and Kazuyuki Shudo. Mycassandra: acloud storage supporting both read heavy and write heavy
workloads. In Proceedings of the 5th Annual International
Systems and Storage Conference, SYSTOR ’12, pp. 14:1–14:9, New York, NY, USA, 2012. ACM.
[13] Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil. The log-structured merge-tree (lsm-tree). ActaInf., Vol. 33, No. 4, pp. 351–385, June 1996.
[14] Michael Rabinovich and Edward D. Lazowska. Improving
fault tolerance and supporting partial writes in structured
coterie protocols for replicated objects. SIGMOD Rec.,
Vol. 21, No. 2, pp. 226–235, June 1992.
[15] 中村俊介, 首藤一幸. 読み出し性能と書き込み性能を両立させる
クラウドストレージ. 先進的計算基盤システムシンポジウム論文集, 第 2011 巻, pp. 171–180, may 2011.
[16] 菱沼直子, 竹房あつ子，中田秀基，小口正人. 様々なシステム構
成における Cassandra の処理能力に関する考察. マルチメディ
ア, 分散, 協調とモバイル (DICOMO2012) シンポジウム, pp.
396–402, July 2012.