コラム

CTC教育サービス・ホーム　＞　コラム　＞　グーグルのクラウドを支えるテクノロジー　＞　第142回　CacheSack：数理最適化によるフラッシュディスク・キャッシュの最適化（パート2）

グーグルのクラウドを支えるテクノロジー

CTC 教育サービス

[IT研修]注目キーワード Python UiPath(RPA) 最新技術動向 Microsoft Azure Docker Kubernetes

第142回　CacheSack：数理最適化によるフラッシュディスク・キャッシュの最適化（パート2） (中井悦司) 2022年12月

はじめに

　前回に続いて、2022年に公開された論文「CacheSack: Admission Optimization for Datacenter Flash Caches」を元にして、Googleのデータセンターで使用されている、フラッシュディスクによるファイルキャッシュシステムを紹介します。この論文では、数理最適化を用いてキャッシングポリシーを選択するアルゴリズムが紹介されており、ITシステムにおける数理最適化の応用例としても興味深い内容です。今回は、最適化の対象となるキャッシングポリシーについて説明します。

キャッシングポリシーの種類

　前回の記事で説明したように、Googleのデータセンターには、Colossus Flash Cacheと呼ばれるファイルキャッシュのシステムが用意されており、Colossusのユーザーは、SSDをバックエンドとするフラッシュサーバー上のキャッシュ領域を確保しておき、これを読み込みキャッシュとして利用します。この際、ユーザーが利用するワークロードによって、キャッシュの使用パターンが変わります。したがって、ワークロードの種類に応じてキャッシュ対象のファイルを決定するポリシーを選択する事で、キャッシュの使用効率を最適化できる可能性があります。これを実現するのが、冒頭の論文のメインテーマとなる「CacheSack」の役割になります。CacheSackでは、次の4種類のポリシーを選択の対象として、ワークロードの種類ごとに適切なポリシーを選択することを目指します。

・AdmitOnWrite：新しく書き込まれたファイル、もしくは、キャッシュミスしたファイルは、すべてキャッシュの対象とする
・AdmitOnMiss：キャッシュミスしたファイルは、すべてキャッシュの対象とする
・AdmitOnSecondMiss：2回連続してキャッシュミスしたファイルは、連続の時間間隔が一定以上短い場合、キャッシュの対象とする
・NeverAdmit：すべてのファイルをキャッシュ対象としない

　これらは上から順に、より積極的にキャッシュするものから、そうではないものへと並んでいます。AdmitOnWriteは、初回の書き込み時にあらかじめキャッシュしておきます。AdmitOnMissは、書き込みが行われた後、初回の読み込み時にキャッシュが行われます。一般的なキャッシングシステムでは、AdmitOnMissのポリシーがよく用いられますが、1度しかアクセスされないファイルに対しては、キャッシングの処理が無駄に発生することになります。一方、CacheSackが導入される以前のColossus Flash Cacheでは、AdmitOnSecondMissが固定的に使用されていました。これは、2回目の読み込み時にキャッシュが行われるというものです。しかしながら、これもまた最適と言えるポリシーではありませんでした。図1は、Colossusに対する1週間のアクセス頻度の分布を調査したグラフですが、破線のグラフは、2回以上アクセスされたデータの累積分布を示します。これを見ると、破線のグラフの左端、すなわち、ちょうど2回アクセスされたデータが40%程度あります。（論文によると、正確には39%になります。）これらのデータは、2回目のアクセス時にキャッシュの効果を受けることができず、さらに2回目のアクセス時に発生するキャッシングの処理も無駄になります。

fig01

図1 1週間のアクセス回数の累積分布（論文より抜粋）

　特に、2回目のアクセス時にキャッシュの効果が得られない点は、ワークロードの種類によっては、性能上の大きなボトルネックになることがあり、このような状況をモニタリングで発見して、必要な際は、手動でAdmitOnMissにポリシーを切り替える必要があったそうです。これは、明らかに改善が必要な状況です。

Colossusバッファーキャッシュの影響

　さらに、Colossusの環境では、Colossus自体のバッファーキャッシュの影響も考慮する必要があります。Colossusを構成する個々のディスクサーバーは、メモリー上にデータをキャッシュするバッファーキャッシュの機能を持っており、ディスクから読み出したデータは、その後、数秒間はメモリー上に保持されます。さらに、ディスク上のデータを先行してバッファーキャッシュに読み込んでおくプリフェッチ機能もあります。特に、BigtableやSpannerなど、Colossusをバックエンドとするデータベースでは、バッファーキャッシュを有効活用するように個別のチューニングが行われています。そのため、もともとバッファーキャッシュから読み出されるデータをフラッシュサーバー上のキャッシュから読み出したとしても、ハードディスクへのアクセス数を減らすという本来の目的には寄与しません。図2は、10種類の典型的なワークロードの種類に対して、Colossus Flash Cacheが無かった場合に、バッファーキャッシュに対するキャッシュミスが発生する割合をシミュレーションで見積もった結果を表します。

fig02

図2 バッファーキャッシュに対するキャッシュミスの発生率（論文より抜粋）

　これを見ると、バッファーキャッシュの使用効率はワークロードによってばらつきがあることが分かります。もともとキャッシュミスが少ないワークロードは、フラッシュサーバー上のキャッシュを利用するメリットは小さくなりますので、このような点も考慮した上で、ワークロードごとのキャッシングポリシーを選択する必要があります。

次回予告

　今回は、2022年に公開された論文「CacheSack: Admission Optimization for Datacenter Flash Caches」を元にして、Googleのデータセンターで使用されている、フラッシュディスクによるファイルキャッシュシステムについて、キャッシュ対象のファイルを選択するキャッシングポリシーについて説明しました。次回は、数理最適化を用いてワークロードごとに最適なポリシーを選択するアルゴリズムを解説します。

Disclaimer：この記事は個人的なものです｡ここで述べられていることは私の個人的な意見に基づくものであり、私の雇用者には関係はありません｡