Re: [HACKERS] Clock with Adaptive Replacement

пт, 4 мая 2018 г., 12:27 Andrey Borodin <x4mmm(at)yandex-team(dot)ru>:

>
> > 4 мая 2018 г., в 0:37, Robert Haas <robertmhaas(at)gmail(dot)com> написал(а):
> >
> > On Wed, May 2, 2018 at 3:06 PM, Vladimir Sitnikov
> > <sitnikov(dot)vladimir(at)gmail(dot)com> wrote:
> >> Sample output can be seen here:
> >> https://github.com/vlsi/pgsqlstat/tree/pgsqlio#pgsqlio
> >
> > Neat. Not sure what generated this trace, but note this part:
> >
> > 3271838881374 88205 0 0 1663 16385 16604
> 0
> > 3271840973321 4368 0 0 1663 16385 16604
> 1
> > 3271842680626 4502 0 0 1663 16385 16604
> 1
> > 3271846077927 4173 0 0 1663 16385 16604
> 1
> >
> > If we want to avoid artificial inflation of usage counts, that kind of
> > thing would be a good place to start -- obviously 4 consecutive
> > accesses to the same buffer by the same backend doesn't justify a
> > separate usage count bump each time.
>
> Upper in this thread Yura suggested that usages should not create equal
> bump each time. He effectively suggested log scale of usages, thus many
> consecutive usages will be taken into account but not dramatically more
> important than just few recent usages.
>

I didn't suggest log scale of usages, but rather "replacement-period based"
increment: usage count could be incremented at most once in NBlocks/32
replaced items. Once it is incremented, its "replacement time" is
remembered, and next NBlocks/32 replacements usage count of this buffer
doesn't increment.
This way, increment is synchronized with replacement activity.

Digging further, I suggest as improvement of GClock algorithm:
- placing new buffer with usage count = 0 (and next NBlock/32 replacements
its usage count doesn't increased)
- increment not by 1, but by 8 (it simulates "hot queue" of popular
algorithms) with limit 32.
- scan at most 25 buffers for eviction. If no buffer with zero usage count
found, the least used buffer (among scanned 25) is evicted.
(new buffers are not evicted during their first NBlock/32 replacements).

Regards,
Yura Sokolov.