DEIM Forum 2014 D8-3

読み出しデータの新鮮度を考慮するキャッシュ機構
高塚康成†

長尾 洋也††矢口尭††

華井 雅俊††

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

メモリ等を用いたキャッシュはデータベースのアクセス性能向上に有効である．しかし一方で， データベー

スへの書き込み時にキャッシュ上のデータを無効化または更新しない限りは，キャッシュ上のデータがデータベース上のものと異なる可能性が時間の経過とともに高くなっていく．つまりデータの新鮮度が下がっていくというトレード
オフがある．そこで，データベースの負荷やアクセス性能に応じてキャッシュの使用/不使用を切り替えることで，ア
クセス性能とデータ新鮮度のトレードオフを調整すること，および，その切り替え方を提案する．また，既存のデータベース管理システムを用いて，提案手法に基づき設計，および実装を行ったキャッシュ機構の性能を評価する．
キーワード

データ新鮮度，キャッシュ，データベース

A Caching Mechanism Considering Data Freshness
Yasunari TAKATSUKA† , Hiroya NAGAO†† , Takashi YAGUCHI†† , Masatoshi HANAI†† , andKazuyuki SHUDO††† Dept. of Information Science, Tokyo Institute of Technology†† Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology
2–12–1–W8–43 Ookayama, Meguro, Tokyo, 152–8552 Japan
E-mail: takatsuka.y.aa@m.titech.ac.jp, hiroya.nagao@is.titech.ac.jp, yaguchi.t.ac@m.titech.ac.jp,
hanai.aa@m.titech.ac.jp, shudo@is.titech.ac.jp

Key words data freshness, cache, database

1. は じ め に出してしまう可能性が高まる．
我々は，時間経過による，オリジナルデータと複製の整合性

データベースのアクセス性能を向上させる方法の一つに，ク

欠如，およびその可能性が高まることをデータ新鮮度の低下

ライアントからのアクセスを高速に行える場所にデータを複製と位置づけ，メモリを用いたキャッシュのデータ新鮮度に注目するという手法がある．その代表例がキャッシュである．一度する．

アクセスされたデータをクライアントから高速にアクセスでき

サービス運営の継続を優先する場合，キャッシュの使用が必る場所に複製し，次回以降の読み出しアクセスではその複製を要な時と不要な時が存在する．例えば，過度のアクセスにより利用する．具体的には，クライアントから地理的に近いサーバ

データベースからの読み出し遅延が一時的に増大する時，サーにデータを複製することで通信遅延を削減する手法や，メモリ

ビス運営を継続させるためには遅延を一定値以下に維持する必

上にデータを複製することでディスクアクセスを削減し，読み要があり，そのためにキャッシュを使用する必要がある．しか出し処理の遅延を小さくする手法などが存在する．

し，それ以外の遅延が小さい時は，キャッシュを使用せずとも

しかし，これらの手法には，複製とオリジナルデータとの整合性をどの程度担保するかという問題がある．キャッシュ上のサービス運営の継続に支障はない．つまり，データ新鮮度を低下させる可能性のあるキャッシュを使用する必要はない．

データを無効化または更新しない限り，時間の経過とともにそ

そこで，本研究はデータベースの負荷やアクセス性能に応じのデータは古くなり，オリジナルデータと異なるデータを読みてキャッシュの使用/不使用を切り替えることで，アクセス性能

と新鮮度のトレードオフを調整すること，および，その切り替た場合は，データに付加されている保存時刻情報と読み出したえ方を提案する．また，提案手法はリバースプロキシに実装す

時刻の差により，そのデータの未更新時間を計算し保存する．

る．これにより，データベース管理システムには手を入れずに同じデータの未更新時間に関しては，その値がより大きい方を提案手法を機能させることができる．我々は既存のデータベー保存する．これにより，キャッシュがどれほどの時間，更新せス管理システムを使用し，提案手法の評価を行う．

ずに古いデータを保持し続けるのかを調べることが出来る．

本論文の構成は以下のとおりである．2 章でデータ新鮮度に

2. 4 データ新鮮度低下を抑えるキャッシュ方式

ついて述べ，3 章で我々の提案手法を述べる．4 章で提案手法

キャッシュからデータの読み出しを行う場合にデータ新鮮度に基づき設計・実装を行ったキャッシュ機構について述べ，5 章を損なわない単純な方法は，そのキャッシュ上のデータが最新でそのキャッシュ機構の性能評価を行う．6 章で関連研究を述であるかどうかをデータベースに確認することである．しかしべ，7 章で本研究の貢献と今後の課題をまとめる．

これは，データベースへのアクセスを省くことが出来ないた

2. データ新鮮度
2. 1 データ新鮮度とはデータベースに対して書き込みと読み出しが同時に行われる

め，キャッシュとしての意味をなさない．そのような手法以外
で，データ新鮮度の低下を抑えるようなキャッシュ方式の例としては以下の二つが挙げられる．

•

キャッシュ上のデータに有効期限を設ける

場合，キャッシュ上のデータは，無効化や更新をしない限り，時この手法では，キャッシュ上の有効期限を過ぎた古いデータ間とともにデータベース上のオリジナルデータと異なる可能性

は無効化され，次にそのデータを読み出す場合はデータベースが高まっていく．本論文では，そのような読み出しデータに関から直接読み出し，その新しいデータを再びキャッシュに保存する整合性の欠如，およびその可能性が高まることをデータのする．しかし，有効期限を長く設けた場合，キャッシュ上に古新鮮度低下と捉える．キャッシュに存在するデータの新しさ，まいデータが存在する時間が増え，データ新鮮度が低下する．またはキャッシュから最新のデータが読み出される度合いをデー

た，有効期限を短く設けた場合，キャッシュ上のデータがすぐ

タ新鮮度と呼ぶ．

に無効化されデータベースへのアクセスが増加し，キャッシュ

2. 2 データ新鮮度の低下

としての効果が薄れる．有効期限の長さによっては最新のデー

データ新鮮度が低下するのは，キャッシュ上のデータとオリタにも関わらず無効化しなければならない場合がある．どれほ

ジナルデータの間に違いが生じた時である．そして，その違い

どの時間でデータが更新されるか不明であり，また，データ毎が生じるのはデータベース上のオリジナルデータが更新されるに更新される頻度も異なるため，適切な有効期限の決め方がこ時である．オリジナルデータの更新時に，更新される対象デーの手法の課題である．

タの複製がキャッシュ上に存在し，かつ，そのキャッシュ上の•複製データが更新または無効化されない場合に，複製とオリジ

これは，データベースへデータを書き込む際に，そのデータ

ナルデータの間に違いが生じる．また，オリジナルデータの更によりキャッシュを更新する手法である．この手法では，まず新時にキャッシュを更新したとしても，複製されたデータベー

データベースへの書き込みを行い，続けて，キャッシュを更新

ス間の同期処理など，更新が内部的に起こった場合に古いデーすることで書き込み完了とする．この手法を用いると，キャッ

タがキャッシュ上に残ってしまう．したがって，データベース

シュ上にあるデータが最新である可能性が高まる．しかしながを構成するノードが一台の場合など，全ての更新処理時に必ずら，依然としてデータ新鮮度を完全に保つことはできない．例

キャッシュを更新できる場合以外は，キャッシュを使用するとえば，複製されたデータベース間の同期処理などにより，更新

必ずデータ新鮮度の低下が生じる．

が内部的に起こった場合，古いデータがキャッシュ上に残って

2. 3 データ新鮮度を表す指標
データ新鮮度を表す指標としては，以下の二つが例として挙
げられる．

•

最新のデータを読み出す割合

ライトスルー・キャッシング

しまう．

3. 提 案 手 法
通常のデータベースシステムは過度のアクセスにより遅延が読み出し処理全体に対して，最新のデータを読み出した件数

予想外に大きくなってしまうことがある．しかし，アプリケーの割合が高いほどデータ新鮮度は高い．例えば，クライアント

ションによっては，サービス運営上，遅延をある一定値以下に側に書き込みデータを保存し，読み出しデータとの比較を行う

維持することが望ましい場合がある．つまり，データベースのことで，最新のデータを読み出した件数を測定することがで負荷が増えた際に，ある上限を超えて遅延が大きくなることを

きる．

防ぎたい．

•

キャッシュ上データの未更新時間

キャッシュ上データの未更新時間が長いほどデータ新鮮度はそこで，我々は，データ新鮮度を調整することで遅延を維持する手法を提案する．

低い．これを測定する方法の例としては，データをキャッシュキャッシュを使用すると 2 章で述べたようなデータ新鮮度のに保存する際，保存した時刻の情報をそのデータに付加してお低下が生じるが，読み出し遅延を小さくすることができる．しく．キャッシュからデータを読み出した際，そのデータが最新

たがって，キャッシュの使用/不使用を切り替えることでデータのデータであるか否かを確認する．古いデータを読み出してい新鮮度を調整し，読み出し遅延を維持する．具体的には，データの一部をキャッシュしながら，常にデータベースへの負荷を

FARP のコアなアルゴリズムに依存しないため，任意のものを監視する．そして，データベースへの負荷が，あらかじめ設定

用いることが可能である．キャッシュのデータ置換ポリシーのした限界を超えた時にのみキャッシュを使用する．例えば，読例としては以下のものが挙げられる．

み出し遅延を監視する．読み出し遅延にしきい値を設け，測定•した遅延がそのしきい値を超えた時にのみキャッシュを使用す

未使用の時間が最も長いデータを破棄する．

る．そうすることで，読み出し遅延がしきい値より小さいとき•はデータ新鮮度を保ち，しきい値より大きいときは，データ新

最も最近使われたデータを破棄する．

鮮度を犠牲にして読み出し遅延を維持する．

•

読み出し遅延以外に，データベースへの負荷を表す指標としては以下のものが挙げられる．

Least Recently Used（LRU）
Most Recently Used（MRU）
Least Frequently Used（LFU）

使用頻度が一番低いデータを破棄する．
また，本論文では 2.4 節で紹介したライトスルー・キャッシ•

書き込みの遅延

ングは未実装である．したがって，書き込み時に FARP が行う•

単位時間あたりの読み書き処理数

操作はクライアントから受け取ったデータをデータベースへ受•同時接続クライアント数

け渡すことのみである．

•

データベースサーバ側の CPU 使用率

これらの指標を用いてキャッシュの使用/不使用を切り替えるこ

読み出し遅延を測定し，その値が設定されたしきい値を超えた場合にのみキャッシュからデータを読み出すようにキャッシュ

とも可能である．

4. 実

4. 2. 2 キャッシュ使用/不使用の切り替え

装使用/不使用の切り替えを行う．
キャッシュ使用/不使用切り替えの判断には，FARP とオリジ提案手法に基づき，読み出しデータの新鮮度を考慮するキャッナルデータベース間で測定された読み出し遅延を用いる．そのシュ機構を設計・実装した．本論文では，我々の提案するキャッため，切り替え判断に FARP とクライアント間の通信遅延はシュ機構を Freshness–aware Reverse Proxy（以下，FARP と考慮されない．しかし，オリジナルデータベースのディスクア

略す）と呼ぶ．

クセスによる遅延はネットワーク通信による遅延に比べ大きい

4. 1 設計

我々は，FARP をリバースプロキシ向けに実装した．つまり，

FARP の実装はデータベース管理システムから独立している．
この設計には以下の利点がある．

ため，FARP とオリジナルデータベース間の読み出し遅延のみを測定することは，クライアントとデータベース間のおおよその読み出し遅延を知るのに十分である．
また，読み出したいデータがオリジナルデータベースのメモ•

様々なデータベース管理システムに対応できる

リに存在する場合と存在しない場合など，オリジナルデータ•

データベース管理システムに手を加えないため，開発・ベースの状況により個々の読み出し遅延は多少変動し，突発的改良が容易である•

FARP が故障したとしても，元々のデータベースには影響を与えないに読み出し遅延が大きくなることがある．そのため，読み出し要求が発行されるたびにキャッシュ使用/不使用の判断を行うと遅延制御の精度が落ちてしまう可能性がある．そこで，キャッFARP を利用するには，クライアントからの読み出し・書き

シュ使用/不使用の判断には読み出しの平均遅延を用いる．平

込み要求の送信先を FARP の稼働するサーバに設定するだけで均遅延を計算するまでの読み出し回数を指定することにより，よい．元々のデータベースからの読み出し遅延の監視，キャッキャッシュ使用/不使用の判断を行う間隔を設定する．

シュへのデータ保存，およびキャッシュの使用/不使用の切り替
えは全て FARP が行う．
クライアントからは FARP と元々のデータベースを合わせた

FARP は以下のようなアルゴリズムでキャッシュ使用/不使用の切り替えを行う．キャッシュの使用/不使用を示すマーカ
を cacheSwitch と呼ぶ．cacheSwitch の値が true の場合キャッものが一つのデータベースとして認識される．つまり，FARP

シュを使用し．cacheSwitch の値が false の場合キャッシュをはデータベースの機能拡張と位置づけられる．以下では区別の使用しない．また，平均遅延を計算するまでの読み出し回数をために，オリジナルデータを保存する元々のデータベースをオ

readCount と呼ぶ．

リジナルデータベース，FARP とオリジナルデータベースを合わせたものをデータベースと呼ぶ．

4. 2 Freshness–aware Reverse Proxy

FARP はクライアントから読み出し処理の要求を受け取ると，まず cacheSwitch の値を確認し，その値により異なる処理を行う．

4. 2. 1 キャッシュアーキテクチャ•

FARP のキャッシュサイズは，FARP の起動時に，キャッシュ（ 1 ） キャッシュに目的のデータが保存されているか調べる．

に保存するレコード数の上限値により設定する．

cacheSwitch が true の場合– 保存されている場合はその値を返す．

キャッシュサイズは指定されているため，キャッシュが満杯– 保存されていない場合はオリジナルデータベースから目になった際は，キャッシュ上のデータを破棄することで新しく的のデータを読み出し，そのデータによりキャッシュを更新す

データを保存するための空きを作らなければならない．そのる．その際に読み出し遅延を測定し，readCount を１増やす．

データ置換ポリシーは，キャッシュの使用/不使用を切り替える（ 2 ） readCount が設定値に達した場合はそれまでの読み出し遅延の平均を計算する．その値がしきい値以下であった場合
は cacheSwitch を false とする．また，readCount を０に戻す．

•

cacheSwitch が false の場合

5. 実

験

本章では，4.2 節で述べた各種パラメータを調整し，提案手（ 1 ） オリジナルデータベースから目的のデータを読み出し，法を次の二つの観点から評価する．まず，単位時間あたりの読読み出したデータによりキャッシュを更新する．その際に読みみ書き処理の量を増やすことによりデータベースへの負荷を高出しの遅延を測定し，readCount を１増やす．

めることで，FARP を使用した場合に読み出し遅延をどれほど（ 2 ） readCount が設定値に達した場合はそれまでの読み出制御・維持できるかを評価する．次に，読み出しの負荷を高め

し遅延の平均を計算する．その値がしきい値以上であった場合た場合の新鮮度の変化を評価する．データベース管理システム

は cacheSwitch を true とする．また，readCount を０に戻す．

には Apache Cassandra [1] [5] を使用する．

4. 2. 3 チューニングのポイント

性能評価には，Yahoo! Cloud Serving Benchmark（YCSB）

FARP には，読み出し遅延のしきい値以外に，性能に影響す[2] を用いる．YCSB は NoSQL 向けのベンチマークツールでるパラメータが二つ存在する．どちらも FARP の起動時に設あり，読み出しおよび更新処理の比率や，データベースへのア

定できる．

•

キャッシュ容量FARP のキャッシュ容量が多いほど，キャッシュ使用時にオリジナルデータベースへのアクセスを削減できるため，より大きな負荷に対応できる．

•

キャッシュ使用/不使用の切り替え判断の間隔

これは読み出し遅延制御の精度に影響する．4.2.2 節で述べた通り，我々の実装ではキャッシュ使用/不使用の切り替えを判断する間隔は平均遅延を計算する間隔と等価である．そして，

クセス分布，また 1 秒あたりに発行する処理要求数の目標値を指定できる．ただし，YCSB には遅延の集計を行う機能はある
ものの，データ新鮮度を測定する機能はない．そこで，データ
新鮮度を測定できるよう YCSB に改良を施した．

5. 1 データ新鮮度の測定方法
本実験では，2.3 節で述べた，最新のデータを読み出した割合をデータ新鮮度として測定した．以下の式により計算する．
データ新鮮度 =最新のデータを読み出した件数
読み出し処理の総数

平均遅延を計算する間隔は，平均遅延を計算するまでの読み出

全体の読み出し件数は YCSB により指定する事ができる．しし回数（readCount）を指定することにより設定する．

たがって，上式のデータ新鮮度を計算するためには最新のデー

readCount が大きいほど平均遅延の計算に用いる標本数がタを読み出した件数を測定する必要がある．そこで，その値を多くなり，より正確な平均遅延を測定できる．しかし一方で，測定できるよう YCSB に改良を施した．最新のデータを読みreadCount が大きすぎるとキャッシュ使用/不使用の切り替え

出した件数を測定する手法としては以下の二つが考えられる．

判断までの間隔が大きくなり，切り替えを行いたい時にうまく•全ての書き込みと読み出し内容のログを書き出し，後に切り替えを行えない．また逆に，readCount が小さい場合はそのログを調査する事で正しく最新のデータを読み出しているキャッシュ使用/不使用の切り替えの判断を細かく行うことがで箇所を確認する．

きるが，平均遅延の計算に用いる標本数が少なくなり正確な平均遅延を計算することが出来ないため，本来切り替える必要のない場面で誤って切り替えを行ってしまう可能性が高まる．

•

書き込み内容を YCSB 側で保存し，読み出したデータと保存されているデータに不整合が無いか逐次確認する．
一つ目の手法は全ての書き込みと読み出しを網羅的に調査す

そこで，測定した平均遅延により readCount を動的に変更る事ができるため，誤差のない新鮮度測定が可能である．しかするように実装した．平均遅延を計算するたびに，FARP が維

し，ログのディスクへの書き出しには時間がかかるため，実験持したい遅延のしきい値と平均遅延の差を計算し，その差が大結果に影響を与えないようにこの手法を実装することは難しい．

きいほど readCount を大きく変更する．また，readCount にそのため，本論文では二つ目の手法を採用した．

上限値を設けることで，readCount が過度に大きくなることを防ぐ．

我々が採用した新鮮度測定の手法には考慮すべき点が二つ存在する．一つ目は，データ保存や整合性確認のための余分な負変更は以下の式により行う．readCount の初期値と上限値は荷が YCSB 側にかかるという点である．その負荷を軽減する

キャッシュ使用時と不使用時で別々に設定することができる．

ために，書き込みデータの保存と整合性の確認を高速に行うこキャッシュ使用時における初期値を cacheLoopCount，不使用とができるよう，データは YCSB を稼働させるマシンのメモリ時における初期値を direct readLoopCount とする．

に保存する．また，本研究では，全ての実験に改良した YCSB

– キャッシュ使用時を用いているため，全ての実験結果に整合性確認のオーバヘッ

readCount = cacheLoopCount × (平均遅延 / しきい値)

ドが含まれている．したがって，改良した YCSB を用いて得た– キャッシュ不使用時

実験結果により，提案手法を比較・評価する事に問題はない．

readCount = direct readLoopCount /(平均遅延 / しきい値)

二つ目は，上述した理由で書き込みデータ全てをメモリに保また，キャッシュ使用時はキャッシュ不使用時より，キャッシュ

存した場合，メモリ容量が不足する可能性があるという点でからの読み出し回数分だけ平均遅延を計算するまでの間隔が長ある．全ての書き込みデータを YCSB 側で保存しておく場合，

くなる．そのため，キャッシュ使用時の readCount やその上限

データベースのディスク容量に比べてメモリの容量はかなり小値はキャッシュ不使用時より小さく設定することを推奨する．

さいため，大量の書き込みを行った際は容易にメモリの容量不足に陥る．それに対処する方法としては，書き込み対象のキー

5. 4 Freshness–aware Reverse Proxy の設定を整数値に変換し，その値をあらかじめ指定した整数値 n で割

データベースノード一台につき一台の FARP を稼働させる．

り，余りが 0 になるデータのみを保存するという手法が考えら

FARP のキャッシュアルゴリズムには LRU を使用し，4.2.3 節

れる．結果として得られた，古いデータを読み出した回数を nで述べた二種のパラメータは以下のような設定で実験を行う．

倍すれば本来の値に近い値が得られるはずである．しかし，こ•の手法は保存する書き込みデータ件数の増加速度を n 分の 1 に100 万レコードを保存する．

抑える効果しかないため，書き込み件数が推定できない場合に•有効な手法であるとは言えない．本研究では書き込むデータ件
数があらかじめ判明しているため，この手法を採用できるのでキャッシュ容量キャッシュ使用/不使用の切り替え判断の間隔

4.2.3 節で説明した，キャッシュ使用時/不使用時の readCountの初期値とその上限値は表 3 のように設定した．

ある．

表 3 readCount 各種設定

5. 2 ベンチマーク環境

readCount 初期値 上限値

表 1 に利用したマシンの構成を示す．ストレージデバイスには SSD を使用する．

キャッシュ使用時

101000

キャッシュ不使用時

100

10000

1 ノードに保存するデータ件数は 1000 万件で実験を行う．今
回，一つのレコードは 10 個のカラムを持ち，一カラムの容量を 100 バイトとしたため，一レコードの容量は 1KB となる．
つまり，データ全体のサイズは 10GB となり，これにさらにス
キーマの情報が加わるため，8 GB のメモリに全データが乗る
事はない．

5. 5 実 験 結 果
目標スループットを上げていき，実スループットが追いつかなくなった時点で終了とする．
データベースノードは 1 ノードと 3 ノードで実験を行った．

FARP が制御する遅延のしきい値は，1 ノードでの実験では 5
ms, 10 ms, 15 ms の三つを設定し，3 ノードでの実験では 10

表 1 ベンチマーク環境

Ubuntu 12.04.3 LTS

ms を設定した．また，比較のため，FARP を使用せずに直接CPU 2.40 GHz Xeon(R) E5620 × 2

アクセスする場合と遅延に関係なくキャッシュを常に使用した

メモリ

8 GB RAM

場合の実験結果も示す．

Java

Java SE 7 Update 4

OS

5. 5. 1 データベースノード一台による実験
図 1 は Update–Heavy ワークロードを課し，スループット

5. 3 ワークロードを変更することでデータベースへの負荷を変えた時の読み出し

書き込み比率が高い Update—Heavy と，読み出し比率が高遅延を示したものである．その際のデータ新鮮度を図 2 に示す．

い Read–Heavy の二つのワークロードで実験を行う．表 2 にしきい値ごとに遅延が維持されていることが確認できる．また，ワークロード毎の書き込み処理と読み出し処理の割合を示す．

図 3，4 は Read–Heavy ワークロードを課した際の結果である

データベースへのアクセス分布としては Zipf 分布を用いる．

Update–Heavy ワークロードと Read–Heavy ワークロード

Zipf 分布は，データの新しさとは無関係に各データへのアクセ

ともに，しきい値が低いほどデータ新鮮度の低下は大きいが，ス頻度が決まるようなアプリケーションのアクセス分布を模す．

実スループットが目標スループットに追いつかなくなった時のデータベースにかかる負荷が変わっても読み出し遅延を制御

データ新鮮度はどのしきい値も同じ値であった．

できることを確認するたに，データベースにかかる負荷の大き5. 5. 2 データベースノード三台による実験

さを変える必要がある．今回は，一秒あたりに発行する処理要

図 5 は Update–Heavy ワークロードを課し，スループット

求数の目標値（以下，スループットと呼ぶ）を増加させることを変更することでデータベースへの負荷を変えた時の読み出しでデータベースにかかる負荷を増やす．一回のワークロードに遅延を示したものである．その際のデータ新鮮度を図 6 に示す．

おける処理命令数は 100 万件とし，それぞれのスループットに設定したしきい値に従い遅延が維持されていることが確認できおける読み出し遅延の平均，およびデータ新鮮度を測定する．

る．また，図 7，8 は Read–Heavy ワークロードを課した際のまた，今回の実験では，書き込みデータの総量がマシン搭載結果である．

メモリに比べて小さい．そのため，新鮮度測定のために，YCSB．

側で書き込みデータの全てを保存する．

5. 6 考察

図 1 から図 8 より，直接アクセスの遅延がしきい値を超えた

表 2 実験に用いるワークロード

Workload 書き込み割合 読み出し割合 アクセス分布あたりを境としてデータ新鮮度は低下し始め，負荷をより大きUpdate–Heavy

50%

50%

Zipf 分布

くした場合は，さらにデータ新鮮度を犠牲にして遅延を維持しRead–Heavy

5%

95%

Zipf 分布ている．したがって，遅延を維持できるスループットには限界があるものの，FARP により読み出し性能とデータ新鮮度のト
レードオフが調整されていることがわかる.
以下では各種実験データについての考察を行う．

図 1 Update–Heavy ワークロードでの読み出しアクセスの遅延比較

図 2 Update–Heavy ワークロードでのデータ新鮮度

図 3 Read–Heavy ワークロードでの読み出しアクセスの遅延

図 4 Read–Heavy ワークロードでのデータ新鮮度

図 5 3 ノードクラスタにおける読み出しアクセスの遅延（Update–

Heavy）

図 6 3 ノードクラスタにおけるデータ新鮮度（Update–Heavy）

はデータの保存にメモリを用いているため，FARP が保持できるデータ量はデータベースに保存されているデータ量に比べて小さい．また，FARP はキャッシュにヒットしなかった場合，クライアントへ返すデータを取得するためにオリジナルデータ
ベースへアクセスする．そのため，スループットを増加させると単位時間あたりのキャッシュヒットミス率が高くなり，単位時間あたりのオリジナルデータベースへのアクセスも増加する．
つまり，負荷が高まりメモリによるキャッシュを常に使用している状態でも，オリジナルデータベースへの読み出しアクセスの削減には限界がある．FARP により限界まで削減した，オリジナルデータベースへの読み出しアクセス量がその処理能力限界に達した時，遅延を維持できなくなり，遅延が大きく増加している．
より高い負荷に対応するための手法
さらに高い負荷に対して低遅延を維持するためには，オリジ
図 7 3 ノードクラスタにおける読み出しアクセスの遅延（Read–

Heavy）

ナルデータベースへのアクセスをさらに削減する必要があり，そのためには FARP のキャッシュ容量を増やす必要がある．その単純な方法は，FARP が使用できるメモリ容量を増やすことである．例えば，複数サーバのメモリを使用することが考えられる．それを実現する設計の具体案としては，Memcached [6] [9]など，既存の分散型メモリキャッシュシステムを複数のサーバで稼働させ，FARP が自身のメモリに加え，Memcached にもデータを保存する設計が考えられる．
しかし，メモリの容量を増やすことでキャッシュヒット率を上げることは出来るが，データベースへのアクセスを完全に削減することはできない．したがって，メモリ容量を増やすだけ
では，やはり FARP による遅延維持には限界がある．そこで，キャッシュにディスクを使用することを考える．
データベース管理システムは書き込み性能か読み出し性能のどちらかに特化した設計がなされている．我々の実験で使用している Apache Cassandra は書き込み性能に特化しているが，
一方，MySQL [7] などは読み出し性能に特化している．オリジ
ナルデータベースのデータベース管理システムとして書き込

図 8 3 ノードクラスタにおけるデータ新鮮度（Read–Heavy）

み性能に特化したものを使用している場合，FARP で読み出
し性能に特化したデータベース管理システムを使用すること

5. 6. 1 読み出しアクセスの遅延

で，ディスクを使用したキャッシュを行うことが出来る．例え直接アクセスの遅延がしきい値を超えるまでは，Read–

ば，オリジナルデータベースのデータを，MySQL を使用してHeavy ワークロードと Update–Heavy ワークロードのどちら

FARP のディスクに複製する．メモリ上のデータ同様，FARP

も，FARP を使用した遅延が直接アクセスの遅延を上回っていはディスク上のデータが古いデータであることを許容し，負荷る．これは，読み出し処理全てが FARP を経由して行われてに余裕があるときのみ更新を行う．オリジナルデータベースへいることで，サーバ間の通信遅延が余分に加わっているためとの負荷が増加し，メモリによるキャッシュのみでは遅延を維持考えられる．

できなくなった時，FARP のディスクからデータを読み出す．

スループットが一定の値を超えるまで，FARP はしきい値にすると，古いデータを読み出す可能性は高まるが，オリジナル

従い遅延を維持している．維持された遅延がしきい値を少しだ

データベースにアクセスするより早く読み出しを行うことがけ超えているのは，FARP がデータベースからの読み出し遅延

でき，また，オリジナルデータベースへのアクセスを完全に削のみを監視し，キャッシュ使用/不使用の切り替え判断にクライ減することができる．したがって，維持できる遅延の下限値はアントと FARP 間の通信遅延を考慮していないためと考えら

FARP で使用するデータベース管理システムの性能によるもの

れる．

の，FARP による遅延維持の限界を無くすことが出来ると予想

Update–Heavy ワークロードと Read–Heavy ワークロード
ともに，遅延を維持できるスループットには限界がある．FARP

される．

5. 6. 2 データ新鮮度

データベースの保証するサービスレベルを変更するシステムは

Update–Heavy ワークロードと Read–Heavy ワークロード

研究されている．Terry らの手法 [4] はその一例である．データのどちらも，スループットを大きくするほどデータ新鮮度が低ベースが担保する整合性にレベルを設け，データベースからの下している．これは，データベースへの負荷が増えた際に，遅読み出し遅延に応じて担保する整合性レベルを変更する．デー

延を維持するためにキャッシュをより頻繁に使用する必要があ

タ新鮮度の向上は整合性の向上と捉えることができるため，整るためである．また，遅延をより低く維持するためには，より合性と遅延のトレードオフを考慮する点は本研究と共通してい頻繁にキャッシュを使用する必要があるため，しきい値が低い

る．しかし，データベース管理システムの機能としてシステム

ほどデータ新鮮度の低下が大きい．

が組み込まれており，strong consisntency を担保するために単

直接アクセスの遅延がしきい値を超えた時を境として，デー

一障害点が存在するなど，本研究とはその設計方針が異なる．

タ新鮮度の低下が始まっている．特に Update–Heavy ワーク

また，整合性のベンチマーク方法も研究されており，Rahman

ロードは，その境におけるデータ新鮮度の低下が顕著に現れてらの手法 [8] はその一つである．この研究も，ベースとなるベ

いる．Update–Heavy ワークロードはオリジナルデータの更新

ンチマークツールとして YCSB を用いている．

頻度が高いため，キャッシュ上のデータが古くなる可能性が高く，そのため，キャッシュの使用が少量でもデータ新鮮度が急激

7. まとめと今後の課題に低下していると考えられる．逆に，Read–Heavy ワークロー

キャッシュの使用量を調整することでデータ新鮮度とデータ

ドはオリジナルデータの更新頻度が低く，キャッシュ上のデー

ベースのアクセス性能のトレードオフを調整する手法を提案し，タが最新である可能性が高いため，キャッシュ使用が少ないう

提案手法に基づき設計・実装したキャッシュ機構を評価した．

ちはデータ新鮮度の低下が小さい．

実験により，我々の設計したキャッシュ機構を用いることで，スループットを限界まで大きくしたときに，異なるしきい値対応できる負荷の大きさに限界はあるものの，読み出し性能とにおけるデータ新鮮度が同じ値に収束しているのは，しきい値

データ新鮮度のトレードオフを調整できることを確認した．

に関係無くキャッシュをほぼ常に使用しているためである．

5. 6. 3 複数ノード

5.6.1 節で述べた手法を実装することで FARP のキャッシュ
容量を増やし，その性能評価を行いたい．

データベースの構成ノードを三台にし，FARP を三台稼働しまた，今回の実装では，読み出し遅延の平均を維持することた場合も，1 ノードの場合と同様の結果が得られた．したがっは出来るが，個々の読み出し遅延をすべてしきい値以下に維持て，データベースノードが増えた数だけ FARP を稼働する台することは出来ない．したがって，キャッシュ使用の調整によ数を増やすことで，Update–Heavy ワークロードなら約 30 %，り 99 パーセンタイルの遅延を維持することは課題である．

Read–Heavy ワークロードなら約 20 % 程度までは，スルー

謝辞

プットが上昇しても遅延を目標値に維持できると予想される．

本研究は JSPS 科研費 25700008，24650025 の助成を受けた

今回，データベースノード一台につき一台の FARP を稼働させたのは，メモリ容量に制限され，FARP がキャッシュできるデータ件数がオリジナルデータベースの扱うデータ件数に比べて少ないからである．データベースノードが増え，オリジナ
ルデータベースが扱うデータ件数が数倍に増えたにも関わらずキャッシュ容量が変わらない場合，キャッシュヒットミス率の増加に伴いオリジナルデータベースへのアクセスも増加し，

FARP により遅延を維持できるスループットの限界値が減少すると考えられる．5.6.1 節で述べた手法により，FARP のキャッシュ容量を大幅に増やすことが出来れば，データベースノードが増えた場合も FARP を稼働させる台数を増やすことなく，高スループットに対応できると予想される．

6. 関 連 研 究
Bolt–on causal consistency [3] は我々と同じ設計方針で，データベースが担保する整合性のレベルを，最も弱い eventual con-sistency から一段階上の causal consisntency へ向上させるシ
ステムの研究である．我々と同じ設計方針であるため，コアなアルゴリズム部分はデータベース管理システムから独立している．そのため，そのアルゴリズムを我々の提案手法に取り入れる事も可能である．
データベースの負荷やアクセス性能を監視し，それに従いものである．
文

献[1] The Apache Software Foundation: Apache Cassandra,
http://cassandra.apache.org/.
[2] 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.
[3] Peter Bailis, Ali Ghodsi, Joseph M. Hellerstein, and Ion Stoica.: Bolt-on Causal Consistency, Proc. SIGMOD ’13, pp.
761–772, 2013.
[4] Douglas Terry, Vijayan Prabhakaran, Rama Kotla,
Mahesh Balakrishnan, Marcos K. Aguilera, and Hussam
Abu-Libdeh.: Consistency-based Service Level Agreements
for Cloud Strage, Proc. SOSP ’13, pp. 309–324, 2013.
[5] Avinash Lakshman, and Prashant Malik.: Cassandra - A
Decentralized Structured Storage System, Proc. LADIS ’09,
2009.
[6] Brad Fitzpatrick.: Distributed Caching with Memcached,Linux Journal, vol. 2004, no. 124, p. 5, 2004.
[7] Oracle Corporation: MySQL, http://www.mysql.com/.
[8] Muntasir R. Rahman, Wojciech Golab, Alvin AuYoung,
Kimberly Keeton, Jay J. Wylie.: Toward a Principled
Framework for Benchmarking Consistency, Proc. Workshop
on Hot Topics in System Dependability, 2012.
[9] Jure Petrovic.: Using Memcached for Data Distribution in
Industrial Environment, Proc. IEEE Computer Society, pp.
368–372, 2008.