Re: Stale entries in dnscache's cache structure

On Wed, Mar 10, 2010 at 10:39:18PM +0100, Laurent Bercot wrote:

>  As a result, a cache might be full of stale entries, and entries that
> might still be valid will be deleted before entries that have been
> written afterwards, but with a smaller TTL, and that have become stale.
> 
>  Since dnscache seems to work well, it seems like a minor inconvenience;
> I don't think it's causing enough superfluous DNS traffic to be an issue.
> But still, the architect in me frowns. It would be better design to
> remove stale entries *first* when the cache is full; and then, if it's
> still full, remove the oldest valid entries.
>
> I can do this; it's not even very complex (store indices in a binary
> search tree ordered by expiration time as well as by key hash).
> Still, compared to dnscache's absolute simplicity, this is adding
> quite a lot of code, and probably a bit of CPU usage and a loss of RAM
> efficiency for a likely minor benefit.

I've never looked at the cache code in detail, but presumably an
alternative solution would be to do an O(n) traversal through the cache
when there is cache pressure and expire anything stale or perhaps even
close to stale. That would presumably free up several entries in one
traversal, and you wouldn't need to traverse again until you filled up
all of the available slots. Of course, there are worst-case scenarios
where you expire just one stale entry, and end up doing the O(n)
traversal for each query. You would probably want to limit it to
garbage-collecting once per some unit of wall-clock time. This bounds
the amount of time you spend on it, and doesn't negatively impact the
result since you will likely not have very many stale entries on the
second of two runs in quick succession (because you didn't give much
time for the wall-clock TTLs to expire).

That gets rid of the complexity of a separate index, but you'd have to
measure the performance impact. My gut feeling tells me that if you
are only running the garbage collection infrequently (by wall clock
time), the O(n) runtime would be acceptably amortized over many queries
for a busy cache (and for a non-busy cache, you simply wouldn't garbage
collect very often, since you wouldn't have constant cache pressure).

But that is vague and handwaving. I would need a real analysis or some
experimental evidence to be convinced.

All of that being said...

> What do you think ? Should I go for the theoretically better solution,
> or does usage show that this flaw in dnscache is never a problem in
> practice and simplicity wins ?

I don't know that this is a problem in practice.  If you are throwing
out a lot of entries before their TTLs are up, your best bet is probably
to increase your cache size.

-Peff