Re: Escaping the ARC patent

>Tom Lane wrote
> I've been doing a bit of research on $subj, and coming to the
> conclusion
> that the ARC patent is a lot narrower than it might appear. In fact
> most of the parts of the algorithm that we actually want have
> prior art.

Yes, it appears that way to me also.

> The 2Q paper proposes using
> fixed fractions of the total available space for each list --- and it
> includes statistics showing that the algorithm isn't excessively
> sensitive to the exact values used, so ARC's claimed "self tuning"
> advantage isn't all that great after all.

Well, after a few months of watching performance numbers fly by, I have
observed that the ARC algorithm produces a very swift reduction to a
fairly static situation, for a static workload. Looking at the ARC paper
more closely shows IMHO that the ARC algorithm is no better for handling
general workloads, but its swift adaptation to strange workloads is what
gives it the slight edge it has over those earlier techniques.

Later work than ARC by the same authors shows that holding open the T1
list by a fixed amount is actually better for database workloads anyway
(I believe the technique is called CARS, sorry no link). So, the ARC
authors have further shown that ARC is not the ultimate cache management
algorithm for dbms anyway.

Removing the adaptation code will slightly improve performance anyway.

> An advantage of heading in this direction (as opposed to, say, LRU/k
> or other algorithms) is that this represents a direct simplification
> of the ARC code we have now. We can probably implement it almost
> entirely by deletions from freelist.c, with little newly written code.
> That gives me a whole lot more confidence that the result will be
> reliable enough to back-patch into 8.0.*.
>
> Comments?

That sounds like a very good approach.

I'd be inclined to move towards that quickly, so we can return to other
issues which can only be addressed when these code changes occur, such
as BufMgrLock contention and bgwriter tuning - neither of which ARC
addresses anyway,

Best Regards, Simon Riggs