Technology

Google、データの保持時間を予測してキャッシュの総コストを削減

この記事のポイント

  1. 実現したこと

    データベースのキャッシュサイズを、メモリーの占有費用と再取得の費用を考慮して動的に調整できるようにした。

  2. 実現の仕組み

    浅い決定木がデータサイズやキャッシュミスの費用から保持時間を予測し、期限まで再アクセスされないデータを退避する。

  3. 得られた結果

    GoogleのSpanner本番環境での評価では、固定容量キャッシュに比べて総保有コストが約5%減少した。

  4. 従来との違い

    Spannerの本番サーバーに可変制御を組み込み、固定容量キャッシュとの比較でメモリー使用量が15.5%減った。

サーバーのキャッシュ棚に色分けされたデータページが並び、異なるタイマーで保持時間を分け、期限切れや満杯時に一部を退避トレーへ移す。右側のストレージ棚からページが戻る流れも描かれている。
AI生成画像

キャッシュ内のデータをいつまで保持するか予測し、メモリーの占有費用と再取得の費用を合わせて抑える。Googleは、この制御を分散データベースSpannerの本番サーバーに組み込み、固定容量方式より総保有コストを約5%削減したと報告した。

データの保持をサイズと時間で費用に換算する

Googleが開発したキャッシュ制御方式linear elastic cachingは、メモリーの費用を、保持するデータのサイズと保持時間に比例する量として扱う。キャッシュサイズは固定せず、実際の負荷に応じて調整する。

データを保持し続ければメモリーの費用がかかり、退避すれば再び必要になった際にキャッシュミスの費用がかかる。この選択を、利用期間が分からないままレンタルを続けるか購入するかを決める「スキーレンタル問題」に対応させ、保持期間の判断に使う。

保持期限と満杯時の退避を別々に決める

保持期間をページごとに決める場合も、キャッシュ全体には容量上限がある。Googleは、この制約の下でも、保持時間と退避方針を別々に最適化できることを理論的に示したとしている。

実装では、ページに保持期限であるTTLを設定し、期限まで再アクセスされなければ退避する。期限を待たずにキャッシュが満杯になった場合は、最近使われていないデータから退避するLRUなどの方針で空きを確保する。

浅い決定木が要求ごとに保持時間を予測する

Spanner向けの実装では、ページへの要求が来るたびに浅い決定木がTTLを予測する。入力にはデータサイズ、キャッシュミスの費用、データベース操作の種類などを使い、ページごとの条件を保持時間に反映する。

この決定木は数行のC++コードに変換できる。Googleは、こうした軽量な予測を使うキャッシュ制御を、Spannerの本番サーバーに数カ月にわたって組み込んだ。

メモリー15.5%減と再取得費用を合わせて評価する

Googleの本番環境での評価では、標準的な固定容量キャッシュに比べ、メモリー使用量が15.5%減少した。一方でキャッシュミスは5.5%増加し、データを保持する量と再取得する回数の間で変化が生じた。

費用を考慮した制御により、増加したキャッシュミスはストレージから安く取得できるデータに集中したとGoogleは説明している。実際のI/O費用への影響は0.5%で、総保有コストは約5%減少した。