See also the refactoring RBTDB discussion
What are the requirements for DNS data structures (what BIND calls a database), if they are tuned for particular purposes? Thinking in the abstract, without worrying about the constraints of RBTDB.
There's a basic distinction between authoritative data and cached data; it is likely that a cache will benefit from splitting the bulk read-mostly data from active and recently-completed queries.
alternatives
If we want the cache to share code with auth zones, that pushes the design towards transactional updates and ordered lookups, as assumed by the points below.
Or the cache could be built from a big hash table. This would need the separate authority cache suggested under active queries below, and it would push NSEC NXDOMAIN synthesis to another separate data structure. But then it might support more fine-grained locking so it would not need a separate active queries table.
In any case, it's desirable to separate the lookup index structures (trees or hash tables, however they are implemented) from the tricky DNS details, so we have freedom to pick and choose data structures.
common issues
-
additional and authority sections
a glue cache helps root zone performance; what about fast lookups for additional data too? is it useful in a cache as well as an auth server?
-
case preservation
authoritative
-
read-mostly
-
longest-match lookups to find enclosing zone
-
NSEC denial requires ordered lookups
-
NSEC3 denial requires another data structure
-
transactional updates
-
multi-version concurrency between updates and zone transfers
-
scheduler for signing
tricky details
-
occluded data (under DNAME or zone cut)
-
wildcards
-
zone cuts and DS
-
EDNS client subnet - in the main database or as a stunt extension?
bulk cache
-
read-mostly
-
updated from active queries table
-
scheduler for TTL cleaning
-
memory usage limit
(perhaps TTL cleaning and folding in results from recursion can be done with a transactional update so the fast read path can have simpler locking)
-
NSEC NXDOMAIN synthesis requires ordered lookups
(NSEC3 synthesis does not seem worth worrying about, because NSEC3 is mostly useful for opt-out which does not provide NXDOMAIN proofs)
tricky details
-
query time, to handle TTLs after expiry before cleaning
-
RFC 2181 trust levels
-
unvalidated records, +CD queries
-
prefetch
-
serve stale
-
EDNS client subnet
-
records present on both sides of a zone cut: NSEC, NS and their signatures (#3031)
negative cache
-
mostly the same issues as the positive cache, but no need for ordered lookups
(Note NSEC NXDOMAIN synthesis uses the positive cache, because the necessary NSEC records exist).
-
is it useful for the negative and positive caches to be the same data structure or separate?
active queries
-
supports frequent small updates
-
only needs exact-match lookups
-
query coalescing
-
NSEC3PARAM database
Is it worth having an authority database separate from the main cache, that is just for infrastructure records? SOA, NS, DS, DNSKEY, NSEC3PARAM (as well as the ADB for nameserver addresses)
BIND contains a separate rbt instance used for DNSSEC validation trust
anchors, called a keytable. Should it be part of a more general
authority database? But there are some parts of the keytable that are
special (RFC 5011 processing and saving trust anchor updates).