# キャッシュ無効化 ## 定義 キャッシュ無効化(cache invalidation)とは、元データの更新に応じて、キャッシュ済みの複製から古くなったものを取り除く、または使えなくする仕組みである。クエリ結果キャッシュでは、更新がどのクエリ結果に影響するかの判定と、影響を受けるキャッシュへ通知を届ける経路の 2 つが問題になる。(Source: [[@2008__VLDB__Scalable Query Result Caching for Web Applications]]) ## 未解決の問い - 更新の影響を受けるクエリだけへ通知するための、クエリと更新の対応づけ(QUMA)を、範囲述語・結合・集約を含む一般のクエリで自動導出できるか。 - 通知の配送順を保証しない publish/subscribe の上で、動的なシャーディングや障害と両立する無効化の正しさをどう保証するか。 ## 未編纂の観察 - publish/subscribe による無効化は、通知の配送順が保証されないと古い結果を無期限にキャッシュする競合を生む。Ferdinand はマスターグループとノンマスターグループの二段構成でこの競合を避け、[[@2025__HOTOS__Understanding the limitations of pubsub systems]] は動的シャーディングとの競合を同じ系の欠陥として指摘する。前者は競合を設計で避けて証明し、後者は根本的な限界として論じる点で対照的である。(Source: [[@2008__VLDB__Scalable Query Result Caching for Web Applications]], [[@2025__HOTOS__Understanding the limitations of pubsub systems]]) - Quaestor の InvaliDB は、書き込みの後像(after-image)を全登録クエリと照合し、結果集合への出入り(add/remove)と更新(change)を通知する。クエリ集合と更新ストリームの両方を直交に分割するため、処理量はノード数に線形に伸び(16 ノードで約 77M ops/s)、代償として結合が扱えない。Ferdinand が publish/subscribe とクエリテンプレートで無効化対象を絞るのに対し、専用のプロキシ層を持たず標準の HTTP キャッシュへ purge を送る点で異なる。(Source: [[@2017__VLDB__Quaestor - Query Web Caching for Database-as-a-Service Providers]]) ## 関連 - ソース: [[@2008__VLDB__Scalable Query Result Caching for Web Applications]] / [[@2017__VLDB__Quaestor - Query Web Caching for Database-as-a-Service Providers]] - 概念: [[分散キャッシュ]] / [[分散メッセージブローカ]] / [[Webキャッシュ]] / [[有界な陳腐化]] - エンティティ: [[Ferdinand]] ## 出典 - [[@2008__VLDB__Scalable Query Result Caching for Web Applications]]