skunk

A collection of tools for dealing with skunk databases: a library, support tools, and an on-disk format for high-speed data retrieval. The database is a static key → value mapping — it can't be inserted into or deleted from once built, only created once and queried many times. Small enough to statically link: querying a skunk db takes 511 bytes of code on i386, creating one takes 1426.

After the last release below it grew into a full OLAP query engine — a different project in substance, even if the name stuck around for a while.

Notes on scalability

The 32-bit (default) build supports databases up to 4GB. Records can be any size up to that. sdb_make needs about 20 bytes of RAM per record, though the record data itself doesn't need to fit in memory. On 32-bit CPUs you're limited to 2GB databases, since the whole thing needs to fit in the address space.

Performance

sdb_make creates a million-record database in about 2.7s from a warm cache (excluding fsync()). Querying that same database: 1,000,000 unique queries in about 0.425s — roughly 2.35M queries/second, mostly bottlenecked on making sure the queries themselves were all distinct.

Features

Doesn't need the data to fit in memory while creating a database
Buffered output during database creation
Databases up to 4GB (limited by virtual address space)
A successful lookup needs only 2 reads from the file
Lookups require no system calls
Fowler/Noll/Vo hash function
Linear-probed open addressing for collision resolution
Databases are demand-loaded
Portable (POSIX/ANSI C99)

Possible applications

A fast webserver that can update its webroot atomically — scripts precompiled to machine code when the webroot database is built
A document retrieval system: RFC number in, RFC text out; patent number in, patent application out
A DNS server that scales easily to millions of records
A FreeRADIUS module for RADIUS authentication against a skunk db

Downloads

The latest version is 0.0.5 (ChangeLog).

Version 0.0.5 — source — binary-tree indexing, renamed to skunkdb
Version 0.0.4 — source — autoconfiscated, much more memory-efficient database creation, nicer API
Version 0.0.3 — source — experimental Python bindings
Version 0.0.2 — source — added the skunk library, sdb_tar, much more robust
Version 0.0.1 — source — first release, Fowler/Noll/Vo hash

TODO

Cursor API
Ordered database format supporting ranges and prefix searches
Index library for ordered and non-ordered keys
sdb_fsck to repair or recover data from corrupt databases