database revision 816e576f77e2c46df3e3d97d65822aa8aded7c4b
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsCopyright (C) 1999, 2000 Internet Software Consortium.
b0e8629055a766d4555a005a283c2889a5974945Mark AndrewsSee COPYRIGHT in the source root or http://isc.org/copyright.html for terms.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrews$Id: database,v 1.7 2000/08/09 04:37:14 tale Exp $
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsBIND 9 DNS database allows named rdatasets to be stored and retrieved.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsDNS databases are used to store two different categories of data:
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsauthoritative zone data and non-authoritative cache data. Unlike
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsprevious versions of BIND which used a monolithic database, BIND 9 has
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsone database per zone or cache. Certain database operations, for
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsexample updates, have differing requirements and actions depending
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsupon whether the database contains zone data or cache data.
d71e2e0c61df16ff37c9934c371a4a60c08974f7Mark AndrewsDatabase Semantics
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsA database instance either has zone semantics or cache semantics. The
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewssemantics are chosen when the database is created and cannot be
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewschanged. The differences between zone databases and cache databases
e21a2904f02a03fa06b6db04d348f65fe9c67b2bMark Andrewswill be discussed further below.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsReference Safety
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsIt is a general principle of the BIND 9 project, and of the database
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsAPI, that all references returned to the caller remain valid until the
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewscaller discards the reference.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsThe database interface also mandates that the rdata in a retrieved
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsrdataset shall remain unaltered while any reference to the rdataset is
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsheld. Some other properties of the rdataset, e.g. its DNSSEC
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsvalidation status, may change.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsDatabase Updates
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsA master zone is updated by a Dynamic Update message. A slave zone is
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsupdated by IXFR or AXFR. AXFR provides the entire contents of the new
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewszone version, and replaces the entire contents of the database. IXFR
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsand Dynamic Update, although completely different protocols, have the
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewssame basic database requirements. They are differential update
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsprotocols, e.g. "add this record to the records at name 'foo'". The
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsupdates are also atomic, i.e. they must either succeed or fail.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsChanges must not become visible to clients until the update has
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewscommitted. In short, zone updates are transactional. This
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewstransaction occurs at a database level; the entire database goes from
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsone version to another.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsCache updates are done by the server in the ordinary course of
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewshandling client requests. Unlike zone databases, there's no need (and
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsindeed, no ability) to ensure that data in the cache is consistent.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsFor example, the cache may hold rdatasets from different versions of a
d71e2e0c61df16ff37c9934c371a4a60c08974f7Mark Andrewsgiven zone. A typical cache update involves looking at the existing
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewscache contents for the given name and type (if any), deciding if the
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsproposed replacement is better, and if so, doing the replacement.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsConcurrent update attempts to the same node and rdataset type must
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsappear to have been executed in some order; there must be no merging
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsof data from multiple updates. Caches are not globally versioned like
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewszones are. There is no need to group changes to multiple rdatasets
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsinto a cache transaction.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsDatabase Concurrency and Locking
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsA principal goal of the BIND 9 project is multiprocessor scalabilty.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsThe amount of concurrency in database accesses is an important factor
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsin achieving scalability. Consider a heavily used database, e.g. the
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewscache database serving some mail hubs, or ".com". If access to these
d71e2e0c61df16ff37c9934c371a4a60c08974f7Mark Andrewsdatabases is not parallalized, then adding another CPU will not help
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsthe server's performance for the portion of the runtime spent in
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsdatabase lookup.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsSupport for multiple concurrent readers certainly helps both cache
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsdatabases and zone databases. Zones are typically read much more than
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsthey are written, though less so than in prior years because dynamic
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsDNS support is now widely available. Caches are frequently read and
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsfrequently written; a non-scientific survey of caching statistics on a
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsfew busy caching nameservers showed the ratio of cache hits to misses
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewswas about 2 to 1.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsAs mentioned above, zone updates must be serialized, but cache updates
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewscan often go in parallel.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsA simple approach to these concurrency goals would be to have a single
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsread-write lock on the database. This would allow for multiple
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsconcurrent readers, and would provide the serialization of updates
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsthat zone updates require. This approach also has significant
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewslimitations. Readers cannot run while an update is running. For a
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsshort-lived transaction like a Dynamic Update, this may be acceptable,
b3cbb2f1ad021349e89807f3492df6e4e679cd56Mark Andrewsbut an IXFR can take a long time (even hours) to complete. Preventing
b3cbb2f1ad021349e89807f3492df6e4e679cd56Mark Andrewsread access for such a long time is unacceptable. Another problem is
b3cbb2f1ad021349e89807f3492df6e4e679cd56Mark Andrewsthat it forces updates to be serialized, even for cache databases.
b3cbb2f1ad021349e89807f3492df6e4e679cd56Mark AndrewsThere are problems on the reader side of the lock too. If the entire
b3cbb2f1ad021349e89807f3492df6e4e679cd56Mark Andrewsdatabase is protected by one lock, then any data retrieved from the
b3cbb2f1ad021349e89807f3492df6e4e679cd56Mark Andrewsdatabase must either be used while the lock is held, or it must be
b3cbb2f1ad021349e89807f3492df6e4e679cd56Mark Andrewscopied, because the data in the database can change when the lock
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsisn't held. Copying is expensive, and the server would like to be
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsable to hold a reference to database data for a long time. The most
d71e2e0c61df16ff37c9934c371a4a60c08974f7Mark Andrewssignificant long-running reader problem is outbound AXFR, which could
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewspotentially block updates for a long time (hours).
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsA finer-grained locking scheme, e.g. one lock per node, helps
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsparallelize cache updates, but doesn't help with the long-lived reader
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsor long-lived writer problems. These problems are solved by zone
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsdatabase versioning, described below.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsThe BIND 9 Database interface does not mandate any particular locking
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsscheme. Database implementations are strongly encouraged to provide
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsas much concurrency as possible without violating the database
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsinterface's rules.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsDatabase Versioning
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsVersioning is not available in cache databases.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsA zone database has a "current version" which is the version most
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsrecently committed. A database has a set of versions open for reading
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrews(the "open versions"). This set is always non-empty, since the
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewscurrent version is always open. The openversion method opens a
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsread-only handle to the current version. All retrievals using the
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewshandle will see the database as it was at the time the version was
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsopened, regardless of subsequent changes to the database. It is not
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewspossible to open a specific version; only the current version may be
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsopened. This helps limit the number of prior versions which must be
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewskept in the database.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsEach zone update transaction is assigned a new version. Only one such
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrews"future version" may be open at any time. It is the caller's
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsresponsibility to serialize and handle the blocking and awakening of
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsmultiple update requests. The future version may be committed or
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsrolled back by the caller. If the future version commits, its version
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsbecomes the current version of the database.