Re: [HACKERS] Clock with Adaptive Replacement

On Sat, May 5, 2018 at 2:16 AM, Andrey Borodin <x4mmm(at)yandex-team(dot)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. 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). 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.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company