BIND 10 #445: Review Recursor cache design
BIND 10 Development
do-not-reply at isc.org
Thu Feb 17 09:41:38 UTC 2011
#445: Review Recursor cache design
-------------------------------------+-------------------------------------
Reporter: | Owner: zhanglikun
zhanglikun | Status: reviewing
Type: task | Milestone: R-Team-
Priority: major | Sprint-20110222
Component: | Resolution:
resolver | Sensitive: 0
Keywords: | Add Hours to Ticket: 0
Estimated Number of Hours: 5.0 | Total Hours: 0
Billable?: 1 |
Internal?: 0 |
-------------------------------------+-------------------------------------
Comment (by zhanglikun):
= Resolver Cache - Design =
[[PageOutline(2-5,,inline)]]
== Introduction ==
This document outlines the design of resolver cache. For the requirement
of resolver cache, please refer to this
[http://bind10.isc.org/wiki/RecursorCacheRequirements "link"].
== About RR Class ==
In the resolver side, most of the queries belong to class 'IN', so class-
specific message/rrset cache objects are considered here for saving the
16-bit class processing time when querying in the cache. When getting a
lookup, dispatch it to a proper message/rrset object based on class.
There will be two rrset caches for each class: C1 and C2. C1 includes the
rrsets from the root hints or local zones, the rrset in C1 will never
expire. C2 includes the rrsets parsed from received messages (also known
as the transient cache).
Others:
* The supported classes are configurable, user can add or remove the
class in supported class list.
* Resolver will reject the query with the class not configured.
* Create the cache for each class if there are some hints or localZones
provided for that class when resolver starting, or else, romove the class
from the supported class list.
== Main Data Structures ==
=== Resolver Cache ===
The cache is represented by the !ResolverCache object. It holds the
Message/RRset caches for all configured classes. The interfaces(The only
interfaces provided to the user of resolver cache) it will provide are:
* Lookup(): Lookup a message/rrset in the cache.
* Input: query name, query type, query class.
* Output: lookup result and the message if it can be looked up.
* LookupClosestRRset(): Lookup the closest enclosing name.
* Input: same with Lookup().
* Output: the shared_ptr of rrset.
* Update(): Update one message/rrset in the cache.
* Input: message/rrset needs to be updated.
* Output: update result(true or false).
* !ResizeCache(): Resize a message/rrset cache.
* Input: new cache size.
* Output: operation result(true or false)
* !DumpCache(): Dump a message/rrset cache to one file or database.
* Input: the file/database name.
* Output: none.
* !LoadCache(): Load message/rrset cache content from one file or
database.
* Input & Output: same with !DumpCache().
=== Message Cache ===
Message cache is represented by one class-specific !MessageCache object,
it's the manager of message entries(see below section 'Message Entry')
which are held in one hash table. The key for the message entry is
"query_name + query_type". The interfaces it will provide are(same with
the interfaces of !ResolverCache except the difference of parameters):
* Lookup(): Lookup one message from the message cache.
* Update(): Update one message to message cache, if the message already
exists, it will be overwritten.
* !ResizeCache(): Resize message cache size.
* !DumpCache(): Dump the cache to one file or database.
* !LoadCache(): Load the cache content from one file or database.
One or more LRU lists are used to track the cached message entries, each
list holds a list of shared pointers to message entries. When a message
entry is created or accessed, it will be moved to the end of the LRU list.
Once the message cache is resized smaller or reachs its size, the message
entries at the head of the list will be removed.
The main attributes of message cache include:
* Size of message cache.
* Class of the message cache.
=== Message Entry ===
One cached message is represented by one message entry(!MessageEntry)
object, it holds the information of one message, which will be used to
regenerate the replied message. Its main attributes include:
* Expiration time of the message(The lowerest expiration time of the
rrset in the message.).
* Query information(information in question section of the message).
* Flags in message header(AA/AD/TC bits).
* DNSSEC validation result.
* Count of rrsets in answer/authority/additional section. (Note: it
doesn't include the rrsig records, since they are saved together with the
original rrset as one of its attributes)
* rrsets information for each sections(answer + authority + additional).
It's a vector of rrset reference to the proper rrset entry objects.
Note: Once the message entry, or some rrset in the message has expired or
can't be found in rrset cache, it will be removed from the message cache,
or moved to the head of LRU list, make sure it is removed first. In the
future, the cache will be smart enough to refetch the messages be about to
expire.
=== RRset Cache ===
RRset cache is represented by one class-specific RRsetCache object, it
manages rrset entries in one hash table. The key for one rrset entry is
"rrset_name + rrset_type". The interfaces it provides are(same with the
interfaces of !MessageCache):
* Lookup(): Lookup one rrset.
* Update(): Update one rrset in the cache.
* !ResizeCache(): Resize rrset cache size.
* !DumpCache(): Dump the cache to one file or database.
* !LoadCache(): Load the cache content from one file or database.
There will also be one or more LRU lists to track rrset entries, which are
same with the LRU lists of message entries.
Different with rrset cache for caching rrsets parsed from cached message,
the cache for localZones is much simple, a map is used for caching the
rrsets in one localZone. The rrsets in localZones will never expires, so
there is no LRU list provided for it.
=== RRset Entry ===
RRsets are represented by the rrset entry(RRsetEntry) object, it holds the
information of one rrset, its main attributes include:
* Expiration time of the rrset.
* Number of rrs.
* Number of the rrsig records.
* Security status of the rrset.
* Rdatas for each rr and rrsig.
The ttl of rrset generated from rrset entry is a dynamic value(TTL =
!ExpireTime(rrset) - !TimeofNow). Once the rrset has expired, it will be
removed from the cache, or moved to the head of LRU list in rrset cache,
so that the expired rrsets always are removed first.
=== Relationship Between Objects ===
The relationship between the objects mentioned above.
[[Image(RecursorCacheUML_V2.png)]]
== Miscellaneous Consideration ==
=== Update operation ===
* The not-expired rrset entry only can be updated by the more
authoritative rrset. Authoritative level will follow the algorithm
mentioned in rfc2181 section 5.4.1
== Resolver Cache Query Algorithm ==
1. When resolver cache gets a query, if the queried class isn't
supported, return empty to query client, or else, lookup cache C1(for
localZone) of quired class with the key "query_name + query_type", if one
rrset is found, generate the reply message with only the found rrset in
answer section and return, if not found, go to next step.
2. Find the message cache of the queried class. If it can't be found,
return empty, or else, go to next step.
2. Find the message entry in the message cache according the key
"query_name + query_type". If it can't be found, return empty, or else, go
to next step.
3. Check whether the message entry has expired. If it has expired, return
emptry, or else, go to next step.
4. Find all rrset entries in the class-specific rrset cache C2 according
rrsets information recorded in message entry. If any rrset has expired,
return empty, or else go to next step.
5. Generate the replied message according the message/rrset entry
information.(Note: If the query doesn't request dnssec records, all the
rrsig records, if they were cached, will be removed from the generated
message.)
TODO, it's better to add a diagram for the algorithm here.
== Questions ==
Since the recursive query mode used by NSAS now, it might makes the
resolver "deadlock"(for more information, please check the page
[wiki:NSASReqIdeas "Using resolver and cache for NSAS needs"] provided by
vorner) once some glue records expired or evicted from the cache. Need to
think more about it.
--
Ticket URL: <http://bind10.isc.org/ticket/445#comment:12>
BIND 10 Development <http://bind10.isc.org>
BIND 10 Development
More information about the bind10-tickets
mailing list