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

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

---

"컴퓨터 과학에는 두 가지 어려운 문제가있다 : 캐시 무효화와 이름 지정 문제."

필 칼튼

캐시 무효화에 대한 일반적인 솔루션이나 방법이 있습니까? 항목이 오래되었을 때를 알고 있으므로 항상 새로운 데이터를 얻을 수 있습니까?

예를 들어 getData()파일에서 데이터를 가져 오는 함수 를 생각해보십시오 . 파일의 마지막 수정 시간을 기반으로 파일을 캐시하며 호출 될 때마다 확인합니다.
그런 다음 transformData()데이터를 변환하고 다음에 함수가 호출 될 때 결과를 캐시 하는 두 번째 함수를 추가합니다 . 파일에 대한 지식이 없습니다. 파일이 변경되면이 캐시가 유효하지 않다는 종속성을 어떻게 추가합니까?

호출 getData()될 때마다 호출 transformData()하여 캐시를 작성하는 데 사용 된 값과 비교할 수 있지만 비용이 많이 듭니다.

---

당신이 말하는 것은 평생 의존 체인이며, 한 가지는 제어 외부에서 수정할 수있는 다른 것에 의존한다는 것입니다.

당신은에서 나무 등의 기능이있는 경우 a, b을 c경우, 어디에서 a와 b동일 한 후 c동일하지만 검사의 비용이 b높 다음입니다 :

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.

그러나 유효성이 완전히 독립적이거나 순환적인 3 개의 입력을 얻을 수 있으므로 레이어링이 불가능합니다. 이는 // 중요로 표시된 줄이 다음으로 변경되어야 함을 의미합니다.

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

---

캐시 무효화의 문제는 우리가 알지 못하고 물건이 변경된다는 것입니다. 따라서 어떤 경우에는 그 사실을 알고 우리에게 알릴 수있는 다른 것이 있으면 해결책이 가능합니다. 주어진 예에서, getData 함수는 파일 시스템에 연결될 수 있습니다. 파일 시스템은 파일을 변경하는 프로세스에 관계없이 파일의 모든 변경 사항을 알고 있으며,이 구성 요소는 데이터를 변환하는 구성 요소를 알릴 수 있습니다.

문제를 해결하기위한 일반적인 마술 수정이 없다고 생각합니다. 그러나 많은 실제 사례에서 "폴링"기반 접근 방식을 "인터럽트"기반 접근 방식으로 변환하여 문제를 간단히 해결할 수있는 기회가있을 수 있습니다.

---

변환을 수행 할 때마다 getData ()를 사용하려는 경우 캐시의 전체 이점을 제거했습니다.

For your example, it seems like a solution would be for when you generate the transformed data, to also store the filename and last modified time of the file the data was generated from (you already stored this in whatever data structure was returned by getData(), so you just copy that record into the data structure returned by transformData()) and then when you call transformData() again, check the last modified time of the file.

---

IMHO, Functional Reactive Programming (FRP) is in a sense a general way to solve cache invalidation.

Here is why: stale data in FRP terminology is called a glitch. One of FRP's goals is to guarantee absence of glitches.

FRP is explained in more detail in this 'Essence of FRP' talk and in this SO answer.

In the talk the Cells represent a cached Object/Entity and a Cell is refreshed if one of it's dependency is refreshed.

FRP hides the plumbing code associated with the dependency graph and makes sure that there are no stale Cells.

---

Another way (different from FRP) that I can think of is wrapping the computed value (of type b) into some kind of a writer Monad Writer (Set (uuid)) b where Set (uuid) (Haskell notation) contains all the identifiers of the mutable values on which the computed value b depends. So, uuid is some kind of a unique identifier that identifies the mutable value/variable (say a row in a database) on which the computed b depends.

Combine this idea with combinators that operate on this kind of writer Monad and that might lead to some kind of a general cache invalidation solution if you only use these combinators to calculate a new b. Such combinators (say a special version of filter) take Writer monads and (uuid, a)-s as inputs, where a is a mutable data/variable, identified by uuid.

So every time you change the "original" data (uuid, a) (say the normalized data in a database from which b was computed) on which the computed value of type b depends then you can invalidate the cache that contains b if you mutate any value a on which the computed b value depends, because based on the Set (uuid) in the Writer Monad you can tell when this happens.

So anytime you mutate something with a given uuid, you broadcast this mutation to all the cache-s and they invalidate the values b that depend on the mutable value identified with said uuid because the Writer monad in which the b is wrapped can tell if that b depends on said uuid or not.

Of course, this only pays off if you read much more often than you write.

---

A third, practical, approach is to use materialized view-s in databases and use them as cache-es. AFAIK they also aim to solve the invalidation problem. This of course limits the operations that connect the mutable data to the derived data.

---

I'm working on an approach right now based on PostSharp and memoizing functions. I've run it past my mentor, and he agrees that it's a good implementation of caching in a content-agnostic way.

Every function can be marked with an attribute that specifies its expiry period. Each function marked in this way is memoized and the result is stored into the cache, with a hash of the function call and parameters used as the key. I'm using Velocity for the backend, which handles distribution of the cache data.

---

Is there a general solution or method to creating a cache, to know when an entry is stale, so you are guaranteed to always get fresh data?

No, because all data is different. Some data may be "stale" after a minute, some after an hour, and some may be fine for days or months.

Regarding your specific example, the simplest solution is to have a 'cache checking' function for files, which you call from both getData and transformData.

---

There is no general solution but:

• You cache can act as a proxy (pull). Assume your cache knows the last origin change's timestamp, when someone call getData(), the cache ask the origin for it's last change's timestamp, if the same, it returns the cache, otherwise it updates its content with the source one and return its content. (A variation is the client to directly send the timestamp on the request, the source would only return content if its timestamp is different.)

• You can still use a notification process (push), the cache observe the source, if the source changes, it sends a notification to the cache which is then flagged as "dirty". If someone calls getData() the cache will first get updated to the source, remove the "dirty" flag; then return its content.

The choice generally speaking depends on:

• The frequency: many calls on getData() would prefer a push so to avoid the source to be flooded by a getTimestamp function
• Your access to the source: Are you owning the source model ? If not, chances are you cannot add any notification process.

Note: As using the timestamp is the traditional way http proxies are working, another approach is sharing a hash of the content stored. The only way I know for 2 entities to get updated together are either I call you (pull) or you call me… (push) that's all.

---

cache is hard because you need to consider: 1)the cache is multiple nodes,need consensus for them 2)invalidation time 3)race condition when multple get/set happen

this is good reading: https://www.confluent.io/blog/turning-the-database-inside-out-with-apache-samza/

---

Perhaps cache-oblivious algorithms would be the most general (Or at least, less hardware configuration dependent), since they'll use the fastest cache first and move on from there. Here's a MIT lecture on it: Cache Oblivious Algorithms

참고URL : https://stackoverflow.com/questions/1188587/cache-invalidation-is-there-a-general-solution