Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
2 added 486 characters in body
source | link

However, unless I'm missing something, all three seem to store a file/block/extent/whatever in cache the first time it is read.

The other option would be to not cache anything the first time it is read, and instead keep a count of the number of times of something is needed, then use some arbitrarily number to decide when something has been "frequently used".

No one would ever implement a system this way, because it means if we say the number is 10 or 20 or 100 times, then once the number is reached, it is obvious the system failed to cache a frequently accessed item the first X number of times. Not so useful!

I'd like the cache to cache those reads I use often.

To sort of re-iterate the previous point, what's "often"? Realistically, it couldn't be a fixed number, since if the system is on long enough, many things could become "often used". It could be a number scaled to a "high score", but in that case, the scale could become very unbalanced if you have a few small items accessed a disproportionate number of times.

In short: no caching mechanism is going to use a minimum count. It's going to cache everything until the cache is full, then it will start evicting things on the basis of some priority algorithm.

Since "frequency" is a factor of "often", it makes sense that every read will cache something, even if it is the first time and the cache is full, since the last file read will be the "most often read file" if we consider a frequency of "the number of times this file was read in the past X reads", where X = 1.

I'm worried that a search over the bodies of all my maildir files or a recursive grep in some large directory might evict large portions of stuff I read far more often.

Probably not, if the cache was full to start with. Each read will be cached, but it will also be evicted sooner than previously cached stuff that has been often accessed.

I guess adaptive replacement might be a term describing what I'm after.

Notice in the "Summary" on that wikipedia page that the discussion is about different strategies (vs. LRU) for ranking things in the cache, not things that have never been in the cache. This follows the logic I've described above: everything goes in the cache, and the efficacy of the caching mechanism is determined by the algorithm for evicting things from the cache. Not putting them in.

However, unless I'm missing something, all three seem to store a file/block/extent/whatever in cache the first time it is read.

The other option would be to not cache anything the first time it is read, and instead keep a count of the number of times of something is needed, then use some arbitrarily number to decide when something has been "frequently used".

No one would ever implement a system this way, because it means if we say the number is 10 or 20 or 100 times, then once the number is reached, it is obvious the system failed to cache a frequently accessed item the first X number of times. Not so useful!

I'd like the cache to cache those reads I use often.

To sort of re-iterate the previous point, what's "often"? Realistically, it couldn't be a fixed number, since if the system is on long enough, many things could become "often used". It could be a number scaled to a "high score", but in that case, the scale could become very unbalanced if you have a few small items accessed a disproportionate number of times.

In short: no caching mechanism is going to use a minimum count. It's going to cache everything until the cache is full, then it will start evicting things on the basis of some priority algorithm.

Since "frequency" is a factor of "often", it makes sense that every read will cache something, even if it is the first time and the cache is full, since the last file read will be the "most often read file" if we consider a frequency of "the number of times this file was read in the past X reads", where X = 1.

I'm worried that a search over the bodies of all my maildir files or a recursive grep in some large directory might evict large portions of stuff I read far more often.

Probably not, if the cache was full to start with. Each read will be cached, but it will also be evicted sooner than previously cached stuff that has been often accessed.

However, unless I'm missing something, all three seem to store a file/block/extent/whatever in cache the first time it is read.

The other option would be to not cache anything the first time it is read, and instead keep a count of the number of times of something is needed, then use some arbitrarily number to decide when something has been "frequently used".

No one would ever implement a system this way, because it means if we say the number is 10 or 20 or 100 times, then once the number is reached, it is obvious the system failed to cache a frequently accessed item the first X number of times. Not so useful!

I'd like the cache to cache those reads I use often.

To sort of re-iterate the previous point, what's "often"? Realistically, it couldn't be a fixed number, since if the system is on long enough, many things could become "often used". It could be a number scaled to a "high score", but in that case, the scale could become very unbalanced if you have a few small items accessed a disproportionate number of times.

In short: no caching mechanism is going to use a minimum count. It's going to cache everything until the cache is full, then it will start evicting things on the basis of some priority algorithm.

Since "frequency" is a factor of "often", it makes sense that every read will cache something, even if it is the first time and the cache is full, since the last file read will be the "most often read file" if we consider a frequency of "the number of times this file was read in the past X reads", where X = 1.

I'm worried that a search over the bodies of all my maildir files or a recursive grep in some large directory might evict large portions of stuff I read far more often.

Probably not, if the cache was full to start with. Each read will be cached, but it will also be evicted sooner than previously cached stuff that has been often accessed.

I guess adaptive replacement might be a term describing what I'm after.

Notice in the "Summary" on that wikipedia page that the discussion is about different strategies (vs. LRU) for ranking things in the cache, not things that have never been in the cache. This follows the logic I've described above: everything goes in the cache, and the efficacy of the caching mechanism is determined by the algorithm for evicting things from the cache. Not putting them in.

1
source | link

However, unless I'm missing something, all three seem to store a file/block/extent/whatever in cache the first time it is read.

The other option would be to not cache anything the first time it is read, and instead keep a count of the number of times of something is needed, then use some arbitrarily number to decide when something has been "frequently used".

No one would ever implement a system this way, because it means if we say the number is 10 or 20 or 100 times, then once the number is reached, it is obvious the system failed to cache a frequently accessed item the first X number of times. Not so useful!

I'd like the cache to cache those reads I use often.

To sort of re-iterate the previous point, what's "often"? Realistically, it couldn't be a fixed number, since if the system is on long enough, many things could become "often used". It could be a number scaled to a "high score", but in that case, the scale could become very unbalanced if you have a few small items accessed a disproportionate number of times.

In short: no caching mechanism is going to use a minimum count. It's going to cache everything until the cache is full, then it will start evicting things on the basis of some priority algorithm.

Since "frequency" is a factor of "often", it makes sense that every read will cache something, even if it is the first time and the cache is full, since the last file read will be the "most often read file" if we consider a frequency of "the number of times this file was read in the past X reads", where X = 1.

I'm worried that a search over the bodies of all my maildir files or a recursive grep in some large directory might evict large portions of stuff I read far more often.

Probably not, if the cache was full to start with. Each read will be cached, but it will also be evicted sooner than previously cached stuff that has been often accessed.