Making Cache Monotonic and Consistent

Resources

https://www.vldb.org/pvldb/vol16/p891-cao.pdf

Summary

単調性（観測された書き込みを失わない）と一貫性（DBのある時点の一貫したビューを提供する）を保証するキャッシュポリシMCCを提案．バッチモデルに対して有界なstalenessを許容する最適なMCCポリシを，オンラインモデルに対してMLベースのMCCポリシを提案．HBase上のRedisにMCCを適用することでDB読み取りを39%削減し，スループットを77%改善した．

Memo

既存の研究: 書き込みをトラックして inconsistent なキャッシュヒットをアプリケーションに通知する．
- アプリケーションのセマンティクスを満たさないキャッシュを invalidate するロジックは既存の LRU などのキャッシュ置換ポリシーに干渉し，性能低下の原因となっている．
- Monotonicity を考慮していない．
キャッシュの Properties
- Consistency
  - アプリケーションがデータベースのある時点の一貫したビューを常に見ることができること
- Monotonicity
  - 観測された書き込みがロストしないこと
コントリビューション
- 従来のキャッシュオーバーフローと，monotonicity あるいは consistency 違反による invalid なキャッシュヒットの両方を扱うキャッシュポリシー MCC (monotonic consistent caching) を提案．
- Redis や Memcached で上記のポリシーを利用する MCCache を開発．HBase 上で MCCache を適用することで平均 77.15% のスループット改善．
MCC (monotonic consistent caching) ポリシー
- 入力モデルとして 3 つを考慮
- バッチ: 大量のリクエストがバッチ化されたもの
- セミオンライン: 読み取りリクエストのみがバッチ化されたもの
- オンライン:
- 従来のキャッシュポリシーの計算量は Poly-time
  - キャッシュミス時にどのキャッシュを evict するかを決めるだけ
- MCC ポリシーの計算量は NP-complete
  - MCC は non-monotonic あるいは inconsistent なキャッシュヒットに対処するために，どのバージョンのアイテムをキャッシュするかを決定する必要がある．
- バージョン選択戦略
  - Eager: 最新のアイテムをキャッシュする
  - Lazy: 有界な staleness でアイテムをキャッシュする
- MCC w/ Eager = NP-complete, MCC w/ Lazy = Poly-time
- 最適なポリシー
- バッチモデル用 MCC ポリシーは Lazy 戦略を用いると optimal である．
- セミオンラインとオンラインモデル用の MCC ポリシーは，obsolate アイテムを分類する ML 分類器を組み込むことで
  - オンラインの場合: competitive
  - セミオンラインの場合: optimal
  - ML-robust，すなわち ML 分類器が攻撃的あるいは悪い予測を出力したとしても competitive

stonewhitener / readingss

Making Cache Monotonic and Consistent #211

Resources

Summary

Memo