Stale entries in dnscache's cache structure

 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