2018-05-07 17:15 GMT+03:00 Robert Haas <robertmh...@gmail.com>: > > On Sat, May 5, 2018 at 2:16 AM, Andrey Borodin <x4...@yandex-team.ru> wrote: > > But you loose difference between "touched once" and "actively used". Log > > scale of usage solves this: usage count grows logarithmically, but drains > > linearly. > > Even if we have that, or something with similar effects, it's still > desirable to avoid bumping the usage count multiple times for accesses > that happen close together in time. I don't really agree with Yura > Sokolov's proposal for how to prevent that problem, because during > periods when no buffer eviction is happening it basically throws out > all of the data: no items are replaced, and the usage count can't be > bumped again until NBlocks/32 items are replaced. That's bad.
That is not as bad as it seems on first glance: during period when no buffer eviction is happenning, all information is almost irrelevant, because it is naturally outdated. And due to choose of "batch" size (25), there is always window between "NBlocks/32 items replaced" and "this item is considered for replacement": even if all items in 25/32*NBlocks had non-zero usage count, then there are at least 7/32*NBlocks to consider before this item could be replaced, during which usage count can be incremented. Note: "1/32 replacements" really means "1/32 new buffers", so while shared_buffers are not full yet (so no evictions happend), all blocks, except last 1/32, could have increment of usage count. > > We want an algorithm that, if there's no buffer eviction for a while and > then we start having to evict buffers, has good information on which > things should be evicted and which should resist eviction. But I > think that he's right that preventing the usage count from rising > artificially when there are correlated accesses is important. If we > have a page with usage count 0 which incurs 4 correlated accesses, as > shown in Vladimir Sitnikov's results upthread, then reducing the usage > count linearly requires 4 sweeps through the buffer ring to get the > usage count back down to 0 (4->3->2->1->0); reducing it by dividing by > two still requires 3 sweeps (4->2->1->0). Yes, that is why log-scale doesn't help much. > A good solution for that > case should, like Yura Sokolov's proposed algorithm, avoid pushing the > usage count higher than 1. So he has the right idea, I think, even if > the method's not quite what we want. Well, I proposed increment by 8 , because simulation (on traces, I found) shows, it really improves quality of algorithm. Looks like, if item had a hit after not-so-short period there is great chance this item is hot, so it should be "protected" from eviction. I used traces from https://github.com/djblue/caching/tree/master/traces (and code in that repository to develop algorithm). That is really important thing to have real-world traces. Because it is not so obvious how algorithm should perform. Mental conclusions could be wrong and doesn't match production load behavior. For example, all good algorithm tracks recently evicted items, and it is not so obvious that already evicted item that get a hit is a "hot" item, and should be placed in separate "hot" queue. (My algo doesn't track evicted items, so it could not be as good in term of hit-rate.) (Personally, I vote more for Clock-Pro than for my algo. But it has three "clock-hands", and if implemented as described, still demands double-linked lists. So, it should be modified/adapted, imho.) With regards, Yura Sokolov.
