[bind10-dev] more about cache (Re: cache effectiveness)

[Michal 'vorner' Vaner]

Hello

I noticed you kind of implicitly assume threads. I guess nothing would change
too much in this stage of design if we consider separate processes, but we
should probably answer that question. In my understanding, we wanted to avoid
threads if at all possible.

On Wed, Feb 27, 2013 at 07:47:17PM -0800, JINMEI Tatuya / 神明達哉 wrote:
> I tried this idea in the jinmei-l1cache branch.  It's a hash table
> keyed with a tuple of query name and type whose entry stores fully
> rendered, wire-format response image (answer section only, assuming
> the "minimal-responses" option).  It also maintains offsets to each
> RR, so it can easily update TTLs when necessary or rotate RRs if
> optionally requested.  If neither TTL adjustment nor RR rotation is
> required, query handling is just to lookup the hash table and copy the
> pre-rendered data.  Experimental benchmark showed it ran vary fast;
> more than 4 times faster than BIND 9, and even much faster than other
> implementations that have full response cache (although, as usual, the
> comparison is not entirely fair).
> 
> Also, the cache size is quite small; the run time memory footprint of
> this server process was just about 5MB.  So, I think it's reasonable
> to have each process/thread have their own copy of this cache to
> completely eliminate contention.  Also, if we can keep the cache size
> this small, it would be easier to dump it to a file on shutdown and
> reuse it on restart.  This will be quite effective (if the downtime is
> reasonably short) because the cached data are expected to be highly
> popular.

We might want to tune this size and try what is best, we may (or may not) get
better results if we fit the whole cache into L2 of processor, or something.

I agree we probably want to have a separate cache of this kind for each
process/thread, to avoid lock contention.

> For the normal record cache, I don't have a particular idea beyond
> something obvious, like a hash table to map from query parameters to
> corresponding RRset (or negative information).  But I guess this cache
> should be shared by multiple threads.  That will help reconstruct the
> full response cache data on TTL expiration more efficiently.  And, if
> shared, the data structure should be chosen so that contention
> overhead can be minimized.  In general, I guess something like hash
> tables is more suitable than tree-like structure in that sense.

Just a crazy idea. If we had some reasonably fast IPC mechanims, we could
outsource the cache to separate process. We actually could have several such
single-threaded caches. Then the process asking the cache would compute some
hash, and pick which cache to ask based on than. The caches could be lock-less
too (though, the locking would be probably delegated onto the IPC mechanims).

The IPC could be asynchronous, so the resolver would act as if it was upstream
query to the remote server mostly (eg. proceed to other queries before the
answer arrives).

I have no idea if that would work.

With regards

-- 
Einstein argued that there must be simplified explanations of nature, because
God is not capricious or arbitrary.  No such faith comforts the software
engineer.
                -- Fred Brooks

Michal 'vorner' Vaner
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20130228/cd41953a/attachment.bin>