Re: [PATCHES] ARC Memory Usage analysis

On Tue, 2004-10-26 at 09:49, Simon Riggs wrote:
> On Mon, 2004-10-25 at 16:34, Jan Wieck wrote:
> > The problem is, with a too small directory ARC cannot guesstimate what
> > might be in the kernel buffers. Nor can it guesstimate what recently was
> > in the kernel buffers and got pushed out from there. That results in a
> > way too small B1 list, and therefore we don't get B1 hits when in fact
> > the data was found in memory. B1 hits is what increases the T1target,
> > and since we are missing them with a too small directory size, our
> > implementation of ARC is propably using a T2 size larger than the
> > working set. That is not optimal.
>
> I think I have seen that the T1 list shrinks "too much", but need more
> tests...with some good test results
>
> > If we would replace the dynamic T1 buffers with a max_backends*2 area of
> > shared buffers, use a C value representing the effective cache size and
> > limit the T1target on the lower bound to effective cache size - shared
> > buffers, then we basically moved the T1 cache into the OS buffers.
>
> Limiting the minimum size of T1len to be 2* maxbackends sounds like an
> easy way to prevent overbalancing of T2, but I would like to follow up
> on ways to have T1 naturally stay larger. I'll do a patch with this idea
> in, for testing. I'll call this "T1 minimum size" so we can discuss it.
>

Don't know whether you've seen this latest update on the ARC idea:
Sorav Bansal and Dharmendra S. Modha,
CAR: Clock with Adaptive Replacement,
    in Proceedings of the USENIX Conference on File and Storage Technologies
    (FAST), pages 187--200, March 2004.
[I picked up the .pdf here http://citeseer.ist.psu.edu/bansal04car.html]

In that paper Bansal and Modha introduce an update to ARC called CART
which they say is more appropriate for databases. Their idea is to
introduce a "temporal locality window" as a way of making sure that
blocks called twice within a short period don't fall out of T1, though
don't make it into T2 either. Strangely enough the "temporal locality
window" is made by increasing the size of T1... in an adpative way, of
course.

If we were going to put a limit on the minimum size of T1, then this
would put a minimal "temporal locality window" in place....rather than
the increased complexity they go to in order to make T1 larger. I note
test results from both the ARC and CAR papers that show that T2 usually
represents most of C, so the observations that T1 is very small is not
atypical. That implies that the cost of managing the temporal locality
window in CART is usually wasted, even though it does cut in as an
overall benefit: The results show that CART is better than ARC over the
whole range of cache sizes tested (16MB to 4GB) and workloads (apart
from 1 out 22).

If we were to implement a minimum size of T1, related as suggested to
number of users, then this would provide a reasonable approximation of
the temporal locality window. This wouldn't prevent the adaptation of T1
to be higher than this when required.

Jan has already optimised ARC for PostgreSQL by the addition of a
special lookup on transactionId required to optimise for the double
cache lookup of select/update that occurs on a T1 hit. That seems likely
to be able to be removed as a result of having a larger T1.

I'd suggest limiting T1 to be a value of:
shared_buffers <= 1000        T1limit = max_backends *0.75
shared_buffers <= 2000        T1limit = max_backends
shared_buffers <= 5000        T1limit = max_backends *1.5
shared_buffers > 5000        T1limit = max_backends *2

I'll try some tests with both
- minimum size of T1
- update optimisation removed

Thoughts?

--
Best Regards, Simon Riggs