========================================================================
SkunkDB - A fast constant database library
Copyright (c) 2001-2002 Gianni Tedesco <gianni@ecsc.co.uk>
SkunkDB is released under the terms of the GNU GPL version 2
========================================================================

Introduction
============
Skunk creates constant databases (ie: not designed to be modified after
creation). It supports databases up to 4GB in size. It is extremely
fast. The main aims are blistering high speed and very small footprint
so you can statically link it if you want.

Maybe one day I will extend it in to something that you can insert into
and delete from. The ability to run purely 'in memory' would be nice
too. Probably berkeley db is best for that kind of thing though.


Caveats
=======
 Skunk databases are not portable. Skunk databases are much larger than
 the data inside them. This makes skunk NOT a suitable transmission
 format. You should transmit data in its original form and then create
 the databases on the endpoint where they are to be used.

 Skunk databases are not safe if someone else truncates the file while
 you are using it. This can cause skunk to crash with SIGSEGV or SIGBUS.


Making a database
=================
 sdb_make takes a plain text file as input. The text file is formatted
 with ':' as a field delimiter and LF ('\n') as record delimiter. There
 can be only two fields per record, field 1 is the key and field 2 is
 the value.

 There are some tools for building database source files in the scripts
 directory. sv.py creates database source files from /etc/protocols or
 /etc/services. mkmillion creates a million record database.


Querying a database
===================
 o sdb_query: queries for a key in a DB file and returns the result.
 o sdb_dump: dumps ALL the data in the DB in a reusable format.


Why is skunk DB so fast?
========================

sdb_make:
 o No data is ever copied, the input file is mmapped
 o The process does very little dynamic allocation
 o Output is buffered in 8KB blocks
 o For reliability we fsync() the database, this slows us right down
   but there is no way to avoid this. Any DB which doesn't fsync the
   file cannot guarantee your data is written to disk!

sdb_query:
 o DB file is shared mmap (zero-copy reads direct from page cache)
 o Lookups never perform system calls
 o Fowler/Noll/Vo hash, very fast
 o Database structure has good locality of reference
 o All arithmetic is 32bit integer math
 o No dynamic allocation is needed
 o Successful lookups require an 8 byte and a 16 byte read on to
   the file (usually on two sequential blocks/pages)
 o All metadata is stored in the hash table avoiding furher seeks on
   successful lookups.
 o Hash tables are never created with a load factor greater than 66%
   to prevent excessive primary clustering.
 o Hash tables are never powers of two in size.

sdb_dump:
 It isn't amazingly fast at all, its only there to help me
 debug databases... That said sdb_dump > /dev/null on a million
 record database takes only 1 second.


Speed Examples
==============

Preliminary benchmarks on my laptop.
 CPU: powerpc 7455 667MHz
 RAM: 512Mb RAM
 HD: IBM-IC25N040ATCS04-0 ATA33 laptop harddisk
 OS: Linux 2.4.19.
 FS: reiserfs 3.6.25

 o On a million record database, all records can be successfully
   queried in around 0.480 seconds. Thats around 2.15 million queries
   a second. Thats less than half a microsecond per query.

 o around 3.7 seconds to create a million record DB, reading data from
   the disk at the same time as writing it. About 25% of the time is
   spent parsing the input. Collision resolution absolutely murders
   performance here.

 o Dumping the database to /dev/null takes 1 second.


Quick explanation of the format
===============================
 SkunkDB is a hash table with 2048 entries in the initial hash table and
 variable sized secondary hash tables. The hash-function used is 32bit
 FNV1a. The two on-disk structures are described in skunk.h as the
 skunk_table and skunk_bucket structures.

 H(K) % 2048 finds the offset in the 2048 element array of skunk_table
 structures located at the beginning of the file.

 ( H(K) xor len(K) ) % len finds the first element in the N element
 array of skunk_bucket structures at the location pointed to by the
 skunk_table ofs field. If the element is not in that location try the
 next. Try no more than N times, where N is equal to the len field of
 the skunk_table structure).
