Uncaching the bad guy

Refining my idea a bit...  What if it was structured like this?

Split the DNS cache into two caches:  The primary cache and a secondary, tentative cache.

When a request comes in, check the primary cache.  If it hits, return the response from the
primary cache.

If it misses, check the tentative cache.  If it hits, return the response from the tentative
cache.

If it misses both caches, send a request upstream.  Place the reply in the tentative cache.
If the reply survives in the tentative cache longer than some timeout (say 1-2 minutes), commit
the information from that reply to the primary cache.

If replies arrive for non-existent requests, put "negative entries" for those replies into the
tentative cache.  Give these negative entries a short timeout, perhaps 30 seconds, to prevent
DoS attacks.  Perhaps also put an upper bound on the storage associated with these negative
entries.  Not all information about the replies needs to be stored--rather, just a hash of the
hostname and the corresponding IP address.

If replies arrive for elements already in the tentative cache, and the details disagree,
remove the element from the tentative cache so that it does not get committed to the primary
cache.

If a reply comes back for an outstanding request, and it matches a hostname OR an IP address
with an active negative entry, do not insert it into the tentative cache.


Thus, the tentative cache tracks two things:  Recent bogus replies (factored apart and
simplified), and recent requests that may or may not be bogus.  If a request survives its
quarantine in the tentative cache, then it can be committed to the primary cache.


Hmmm....