Re: [HACKERS] Clock with Adaptive Replacement

2018-05-08 16:21 GMT+03:00 Robert Haas <robertmhaas(at)gmail(dot)com>:
>
> On Mon, May 7, 2018 at 12:54 PM, Юрий Соколов <funny(dot)falcon(at)gmail(dot)com>
wrote:
> >> 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.
>
> I don't agree that the information is almost irrelevant. If we have a
> working set that starts out fitting within shared_buffers and then
> grows larger, we want to know which parts of the data were being
> accessed frequently just prior to the point where we started evicting
> things.

"just prior to the point" means we have to have machinery for information
expiration without eviction. For example, same "clock hand" should walk
over all buffers continiously, and decrement "usage count", but without
eviction performed. Right?

As alternative, some approximation of Working Set algorithm could be used:
- on every access "access time" should be written to item,
- items accessed before some "expiration interval" are considered for
expiration.
This way, there is also fresh information about usage even without any
expiration performed yet.

"usage count" still have to be used to track access frequency, but it
should not be just incremented:
- there should be formula for "corrected count", that depends on
last access time, written usage count and over-all system access rate.
- increment should look like:
usage_count = corrected_count(cur_time, access_time, usage_count,
access_rate) + increment(cur_time, access_time, access_rate)
- probably, expiration should rely on "corrected_count" either,
ie evict if "corrected_count" == 0

To smooth access spikes, new values for "usage count" and "access time"
should be written not on every access, but once in some period.

Oh, looks like I'm inventing another kind of bicycle :-(
and this one is unlikely to be good.

With regards,
Sokolov Yura