bind caching algorithm?

[KyoungSoo Park]

Barry Margolin wrote:

>In article <c4sk89$12bh$1 at sf1.isc.org>,
> KyoungSoo Park <kyoungso at cs.princeton.edu> wrote:
>
>  
>
>>Hi,
>>
>>Is there anyone who's familar with bind's caching algorithm?
>>I know it's based on TTLs of the result records, but there should be an 
>>evicting algorthm as well.
>>How does bind do cache eviction? LRU, LFU ... ?
>>    
>>
>
>When it looks up an existing cached record, it checks whether its TTL 
>has expired, and evicts it if so.  Also, there's a periodic "cleaning" 
>that scans the entire cache, evicting all records that have expired; the 
>frequency of this is controlled by the "clean-interval" named.conf 
>option.
>  
>
This seems clearly not a good design. I think the evicting algorithm 
should have a mechanism of
reflecting the past and/or future usage at the very least. What's the 
intuition behind this?

>  
>
>>How does it search for a cached record? Is it using hashing(what kind of)?
>>    
>>
>
>The organization of the cache changed between BIND 8 and 9, and could 
>change again.
>
>  
>
>>I don't think bind is doing very stupid thing like linear search on some 
>>lists or even incur thrashing,
>>but when I do stress test with a lot of requests, usually the memory 
>>size gets bigger and bigger
>>and at some points, the reponse gets very slow. I know I can place a 
>>limit on the caching memory size,
>>but it seems not quite well controlled with that option.
>>    
>>
>
>BIND's cache organization is not very localized.  So if the cache 
>doesn't fit in RAM, it often thrashes and performance goes into the 
>toilet.  This was definitely true in BIND 4 and 8; I don't know whether 
>or not it was improved in BIND 9.
>  
>
Wow. If this is true, that's actually a bad implementation. Now I 
understand why I saw the enormous performance degrade
with lots of requests/sec. I used the latest version of BIND 9, but I 
still see something related with thrashing.
I really wonder how BIND could have survived with this kind of sloppy 
implementation.

Anyway, this is a very good information to me.
Thank you very much.

Regards,
KyoungSoo