Re: Non-existent zone file

> Has anybody done any formal analysis as to how much performance
> degrades as the cdb file grows?  Or the difference between searching
> the cdb for records that do not exist vs ones that do?

 From http://cr.yp.to/cdb.html :
 Fast lookups: A successful lookup in a large database normally takes just two disk accesses. An unsuccessful lookup takes only one.

 So, searching for nonexistent records should be quick, and searching
for existent records should be fast enough no matter the database size.

 Now, to go a little deeper :

 - on Unix systems, one of the bottlenecks a process may encounter timewise
is the number of system calls. cdb is very light in system call usage;
  * open() on the cdb file
  * mmap() the cdb file to memory
  * all necessary seeks and reads are done using mmapped data
  * munmap() the file
  * close() the file

 Using the patch that maintains the file opened should greatly improve
performance on heavily loaded systems: the open()+mmap() / munmap()+close()
phase is only done once, and every request does only the meat and potatoes,
i.e. operations on the mmapped data, without additional system calls.
 This patch should be the first thing to apply if you're experiencing
poor performance. Of course, the drawback is that changes to the cdb file
won't be seen immediately; adding a SIGALRM handler that makes tinydns
close and reopen the cdb file should solve the problem.

 - the next obvious bottleneck, on modern systems, is cache memory.
No matter how fast your hard drives may be, a read() hitting the cache
will always be faster than a read() causing a page fault in the cache
and a real disk access. With modern hardware multi-layering of cache
memory, the more you access the same addresses, the faster those accesses
become, if the contents you're looking for all fit in the closest and
fastest cache layers.
 This is, of course, also true when accessing disk data through the
mmap() interface. Although the code looks like a simple memory access,
the underlying OS reads tha data on disk as needed.
 This is where cdb does NOT shine.
 cdb hash tables are stored at the end of the file. Records can be
anywhere within the file. A query isn't garanteed *at all* to hit the
same spot as the previous one; quite the contrary.
 So, if your cdb file can fit into the cache, you're good (and the
faster cache it fits into, the better): once the data has been read
once, further access will be fast. If your cdb file is too big, some
queries will cause a real disk access, degrading performance; and if
your cdb file really has a huge number of entries, I suspect that even
the hash table part might not fit into the cache, in which case some
queries would cause *two* real disk accesses.

 Modern hard disks have more than 4 GB integrated cache, which is
enough to hold any entire cdb file; so "real disk accesses" are kind
of a moot point, a dedicated, heavily loaded tinydns server will have
the whole cdb in the disk buffer; nevertheless, access to the disk
buffer is slower than access to RAM, so having 4 GB of RAM should
help too. And soon we'll have CPUs with 4 GB of L1 cache >.>

 This is about as far as I can go with handwaving. Next step is real
numbers coming from real testing with real data by someone who really
has time.

-- 
 Laurent