Re: bind caching algorithm?

Barry Margolin wrote:

>In article <c4sk89$12bh$1@sf1.isc.org>,
> KyoungSoo Park <kyoungso@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