cache replacement proposal

[xoror@infuse.org]

Hi all,

I was having those slowdown behavours discussed before. i've
finally been able to track it down to the real issue.

My test programme was essentially a DoS programme. It uses a so called
looping access pattern. It will flush the lru cache every time.

Here's a short description of a few patterns

1. looping pattern

1,2,3,1,2,3...

if we have a cache of 3 entries, lru will be flush out the entry that will
be used first. (this problem i was experimenting.) lru is failing here.

2. sequence pattern
1....n
where n is a big number. We can't really do much in this case, the only
thing that would help is cache directory of n entries.

3. 'random' pattern
lru performs quite well on these patterns.

I've been studying some cache replacement algoritm and i think ARC
is the best to use in this case. Maby with some domain knowledge processed
inside it as well.

Arc paper can be found here:
http://www.almaden.ibm.com/cs/people/dmodha/#ARC 
it also has implementation details on how to implement it. ARC is a
selftuning adaptive cache replacement algoritm that can adapt to favor
recency (like lru) of frequency (to solve prob 1 , well partially: if the
pattern of the loop > your cache directory there's not much to do about
it). ARC can resist pattern 1 and 2 (if you cacher directory is 1/2
entries of the pattern that will be performed.)

I'm trying to replace the lru algoritm in openldap with ARC to see if i
would gain more cache hits. do you have any tips on what domain knowledge
we could use to even get better cache hit ratios? I'd love to donate
back the code if you are all interested.

regards
Cuong