Re: ARC patent

Ühel kenal päeval (neljapäev, 20. jaanuar 2005, 23:17+1100), kirjutas
Neil Conway:
> Simon Riggs wrote:
> >>However, I think the ARC replacement should *not* be a fundamental
> >>change in behavior: the algorithm should still attempt to balance
> >>recency and frequency, to adjust dynamically to changes in workload, to
> >>avoid "sequential flooding", and to allow constant-time page
> >>replacement.
> >
> > Agreed: Those are the requirements. It must also scale better as well.
>
> On thinking about this more, I'm not sure these are the right goals for
> an 8.0.x replacement algorithm. For 8.1 we should definitely Do The
> Right Thing and develop a complete ARC replacement. For 8.0.x, I wonder
> if it would be better to just replace ARC with LRU. The primary
> advantage to doing this is LRU's simplicity -- if we're concerned about
> introducing regressions in stability into 8.0, this is likely the best
> way to reduce the chance of that happening. Furthermore, LRU's behavior
> with PostgreSQL is well-known and has been extensively tested.

If we are going the "simple" way, i have two simple suggestions:

1) We should do something about seqscans polluting LRU - perhaps insert
pages brought into memory by seqscan near the end of LRU list. Or just
swich off postgresqls internal cachin alltogether when doing seqscans
and rely on underlying systems caching entirely (as we cant switch it
off anyway)

2) Another simple, but nondeterministic, hack would be using randomness,
i.e.
 2.1) select a random buffer in LR side half (or 30% or 60%) of       for replacement.
 2.2) dont last accessed pages to top of LRU list immediately,       just push them uphill some amount, either random,
or      perhaps 1/2 the way to top at each access. 

This should be quite qood strategy for avoiding disastrous failings on
specific pathological workloads, at the cost of less than optimal
behaviour in easily analysed standard cases.

> Of course, the downside is that we lose the benefits of ARC or an
> ARC-like algorithm in 8.0. That would be unfortunate, but I don't think
> it is a catastrophe.

The only case this would be a catastrophe, is for production OLTP
workloads that did fine with ARC but get overloaded when using LRU.

> The other bufmgr-related changes (vacuum hints,
> bgwriter and vacuum delay) should ensure that VACUUM still has a much
> reduced impact on system performance. Sequential scans will still flood
> the cache, but I don't view that as an enormous problem.

Has anobody some insight, how does linux kernel level disk cache solve
this "sequencial scan/read pollutes cache" problem ?


--
Hannu Krosing <hannu@tm.ee>