[bind10-dev] Resolver - address database requirements

[Robert Edmonds]

Stephen Morris wrote:
> On 4 Oct 2010, at 10:48, Robert Edmonds wrote:
> > 
> > i think i may not have been clear on the lock-less LRU variant.  the
> > entries in the per-thread expiration lists (at least in my
> > implementation) form completely disjoint sets -- i.e., the thread that
> > allocates the entry and appends it to the expiration list must be the
> > same thread that expires it.  the same entry is never present in more
> > than one of the expiration queues at the same time.
> 
> OK, I understand.  That's quite neat.
> 
> This relies on a frequently-accessed entry being periodically accessed
> by the creating thread to prevent it from expiring.  I guess that it
> will be fairly unlikely for a frequently accessed name not to be
> accessed more or less evenly by all the threads, so that approach does
> avoid an additional mutex (and associated contention), albeit at the
> expense of having thread-specific storage.

actually, i'm mistaken.  i have implementations of caches with FIFO and
LRU expiration policies, and only in the FIFO cache do i make use of the
per-thread expiration lists.  you can do it with FIFO but not with LRU
because the position of an entry doesn't change on a lookup (this also
means you only need a singly linked list).  FIFO is much less useful for
a recursive DNS cache.

-- 
Robert Edmonds
edmonds at isc.org