wiki:RecursorCacheDesign

Resolver Cache - Design

  1. Introduction
  2. About RR Class
  3. Main Data Structures
    1. Resolver Cache
    2. Message Cache
    3. Message Entry
    4. RRset Cache
    5. RRset Entry
    6. Relationship Between Objects
  4. Miscellaneous Consideration
    1. Update operation
  5. Resolver Cache Query Algorithm
  6. Questions

Introduction

This document outlines the design of resolver cache. For the requirement of resolver cache, please refer to this 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.

Recursor cache design: relationship between classes.

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.
  3. 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.
  4. Check whether the message entry has expired. If it has expired, return emptry, or else, go to next step.
  5. 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.
  6. 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 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.

Last modified 7 years ago Last modified on Feb 17, 2011, 9:44:52 AM

Attachments (2)

Download all attachments as: .zip