[解決済み] キャッシュの無効化 - 一般的な解決策はありますか？

質問

コンピュータサイエンスには、キャッシュの無効化と名前の付け方という2つの難しい問題しかありません。

フィル カールトン

キャッシュを無効にする一般的な解決策や方法はありますか？エントリが古くなったときにそれを知ることで、常に新鮮なデータを得られることが保証されますか？

たとえば、ある関数 getData() で、ファイルからデータを取得するとします。 これはファイルの最終更新時刻に基づいてデータをキャッシュし、呼び出されるたびにそれをチェックします。

次に、2番目の関数 transformData() を追加します。この関数はデータを変換し、次にこの関数が呼ばれたときのためにその結果をキャッシュします。 ファイルが変更された場合、このキャッシュは無効になるという依存関係をどのように追加するのでしょうか？

あなたは getData() 毎回 transformData() が呼び出されるたびに、キャッシュを構築するために使用された値と比較しますが、これは非常にコストがかかることになります。

どのように解決するのか？

あるものが別のものに依存し、その依存したものが自分のコントロール外で変更される可能性がある、ということです。

からのべき乗関数がある場合、それは a , b から c ここで、もし a と b が同じであれば c は同じですが、チェックのコストは b が高いのであれば、どちらかです。

1. 古い情報を使って操作することがあり、常に b
2. チェックするように最善を尽くす b をできるだけ速くする

ケーキを食べることはできない...

に基づいて追加のキャッシュを重ねることができるのであれば、そのキャッシュは a に基づいて追加のキャッシュを重ねることができるなら、これは最初の問題に少しも影響しません。もし 1 を選んだのであれば、自分自身に与えた自由があるので、より多くのキャッシュを行うことができますが、キャッシュされた b . 2 を選んだ場合は b を毎回チェックしなければなりませんが、キャッシュを利用することで a もし b がチェックアウトします。

キャッシュを重ねる場合、組み合わせた動作の結果、システムの「ルール」に違反したかどうかを検討する必要があります。

もし、あなたが a が常に有効であるならば b が有効であれば、以下のようにキャッシュを配置することができます（擬似コード）。

private map<b,map<a,c>> cache // 
private func realFunction    // (a,b) -> c

get(a, b) 
{
    c result;
    map<a,c> endCache;
    if (cache[b] expired or not present)
    {
        remove all b -> * entries in cache;   
        endCache = new map<a,c>();      
        add to cache b -> endCache;
    }
    else
    {
        endCache = cache[b];     
    }
    if (endCache[a] not present)     // important line
    {
        result = realFunction(a,b); 
        endCache[a] = result;
    }
    else   
    {
        result = endCache[a];
    }
    return result;
}

明らかに連続したレイヤー（例えば x ) は、各段階で新しく追加された入力の妥当性が a : b の関係 x : b と x : a .

しかし、有効性が完全に独立している（あるいは循環している）3つの入力を得ることは十分に可能であり、レイヤリングは不可能でしょう。この場合、「//重要」とマークされた行は次のように変更する必要があります。

if (endCache[a]) が期限切れか が存在しない場合)