[bind10-dev] Resolver - address database requirements

[Robert Edmonds]

Michal 'vorner' Vaner wrote:
> Furthermore, if there's a situation:
> • Request 'a' about example.net. The database does not have it. So it is asked
>   to add/fetch it.
> • Request 'b' about example.net in the time between 'a' got answer „no data in DB“
>   and 'a' asked to add it there. So it asks to fetch it again.
> 
> I think this should be atomic operation so we do not have these race conditions.
> Not that they would be bad, because we will have something like „This is not in
> the DB yet, but it is already requested“, so it could be solved here as well.

resolvers should definitely avoid sending multiple queries with the same
qname/qtype/qclass, as not doing so weakens the protections against DNS
spoofing.  see:

    http://www.kb.cert.org/vuls/id/457875

> > 7) If the address information associated with a nameserver reaches its TTL, the information should be fetched again the next time address information is required.
> > 
> > 15) To limit memory usage, it should be possible to limit the number of names in the database.
> > * If a new name is added and takes the count over the limit, another name should be dropped.
> 
> These look like expensive operations (with the TTL, we could wait until someone
> asks for it or is dropped due to 15), but it seems to lack elegance). Would it
> be possible to have them in „not exact“ manner ‒ if there are too many items in
> the DB, run a background task that clears the DB of outdated and not much used
> items and drop something like 10% of the database?

it is fairly easy to avoid having to implement a "background task" and
the associated concurrency problems if you're willing to add two extra
pointers to each node in the address database to implement a doubly
linked list for the purpose of LRU expiration.

basically, this linked list threads its way through all the nodes in the
database, with least recently used nodes near the head and most recently
used nodes near the tail.  on inserts new nodes are appended at the end
of the list and on lookups existing nodes are detached from the middle
of the list and appended to the tail.  when the memory limit is reached
you remove nodes from the head of the list.  this check can be performed
immediately after insertion and since you would typically only remove
one or two entries at a time the cost of expiration is amortized.

naturally, when the TTL for an entry expires and the entry isn't looked
up again, that entry will gravitate towards the head of the list and
eventually be expired.  it's possible to also implement a TTL expiration
policy that frees entries as soon as they expire but this requires more
bookkeeping and more overhead.

additionally, you can make the above lock-free by using a separate LRU
list per thread, assuming that the number of threads is constant during
runtime.

of course, all of the above are implementation details but it shows that
the requirements are reasonable :)

-- 
Robert Edmonds
edmonds at isc.org