[algorithm] 캐시 무효화 — 일반적인 해결책이 있습니까?

당신이 말하는 것은 평생 의존성 체인입니다. 그것은 하나의 것이 다른 것에 의존하며 그것의 통제 밖에서 수정할 수 있습니다.

에서 멱등 함수가있는 경우 a, bto cwhere, if aand bare the same then cis same but the cost of check the cost bis high then you either :

1. 언젠가 오래된 정보로 작업하고 항상 확인하지는 않는다는 것을 인정하십시오. b
2. b가능한 한 빨리 확인하기 위해 최선을 다 하십시오.

케이크를 먹고 먹을 수는 없습니다 …

a맨 위에 기반으로 추가 캐시를 계층화 할 수 있다면 이는 초기 문제에 1 비트가 아닌 영향을 미칩니다. 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.

그러나 유효성이 완전히 독립적 (또는 순환 적) 인 세 개의 입력을 얻을 수 있으므로 계층화가 불가능합니다. 이것은 // 중요로 표시된 줄이 다음으로 변경되어야 함을 의미합니다.

(endCache [a]가 만료되었거나 존재하지 않는 경우)

답변