Re: Stale entries in dnscache's cache structure

I disagree with what you said.

If the cache is full, I see no valid reason to delete an entry with  
smaller remaining TTL first.

What matters is to know whether or not this cached entry will be  
reused again before it eventually gets kicked out of the cache.

The "dead on arrival" entries (cached but never requested again)  
should not even get cached in the first place.

LRU seems to be the right policy for that case.

Now, those subjects are very well studied in the area of CPU caches.

For example, to avoid dead on arrival entries to get cached, what one  
can do is:
  1) When a new entry arrives, add it to a cache with a probability of A
  2) Eventually, if the entry is frequently requested, it will get cached
  3) Entries that are request only once have only a small probability  
of (1 - A) to get cached.

I recommend to read the original articles.

Personally, I ran djbdns for a single server only, and I do not run  
any instance of it at the moment.

But if you have this kind of issues it might be fun to collect some  
statistics and see which policy is the most efficient for DNS.

Regards,
  Dinesh Bolkensteyn

Quoting Laurent Bercot <[email protected]>:

>  Let's be a bit technical for a change, shall we?
>
>  Let's assume, for academic purposes, that I am designing a cache
> structure meant to store generic data with an expiration date - for
> instance, DNS entries.
>
>  I studied dnscache's cache structure, and am appalled by its simplicity.
> It's just beautiful that such a simple structure can be used; no wonder
> dnscache is fast.
>  However, this simplicity comes at the cost of a little functionality.
> Entries cannot be directly removed, they remain in the cache until the
> cache is full and oldest entries are overwritten in a round-robin way.
> Expiration time is not a factor in deciding what entry should be removed
> to make room.
>  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.
>
>  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 ?
>
> --
>  Laurent
>