Re: ARC patent

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. A complex 
ARC replacement would receive even less testing than ARC itself has 
received -- which isn't a whole lot, in comparison with LRU.

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 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. In other words, 
I think a more intelligent replacement policy would be nice to have, but 
at this point in the 8.0 development cycle we should go with the 
simplest solution that we know is likely to work -- namely, LRU.

-Neil