cdb (software)
From Wikipedia, the free encyclopedia
cdb, short for "constant database", refers to both a library and data format created by Daniel J. Bernstein. cdb acts as an on-disk associative array, mapping keys to values, and allows multiple values to be stored for a single key. A constant database allows for only two operations: creation and reading. Both operations are designed to be very fast and highly reliable. Since the database does not change while it is in use, multiple processes can access a single database without locking. Additionally, since all modifications are actually the creation of a replacement database, it can take advantage of UNIX filesystem semantics to provide a guarantee of reliability.
Keys, values, and total database size have no arbitrary limits, though the use of 4-byte offsets restricts it to 4 gigabytes or smaller. cdb is used by djbdns, fastforward, mess822, qmail and ucspi-tcp to provide highly efficient, reliable, and simple data access.
Contents |
[edit] Structure
A database contains an entire data set (e.g. a single associative array) in a single computer file. It consists of three parts: a fixed-size header, data, and a set of hash tables. Lookups are designed for exact keys only, though other types of searches could be performed by scanning the entire database. Lookups are performed using the following algorithm:
- Hash the key.
- Determine which hash table and slot this record should be located at.
- Test the indicated slot in the hash table.
- If the slot is empty, the record does not exist. Abort the search.
- If the slot's hash matches the key's hash, seek to the record. Read and compare the key. If it matches, the data has been found, so abort the search.
- The record is not in this slot. Proceed to the next slot, wrapping around to the beginning of the hash table if necessary.
For lookups of keys multiple values, additional values may be found by simply resuming the search at the next slot.
[edit] Format
All numbers -- offsets, lengths, and hash values -- are unsigned 32-bit integers, stored in little endian format. Keys and data are considered to be opaque byte strings, and have no special treatment.
The fixed-size header at the beginning of the database describes 256 hash tables by listing their position within the file and their length in slots. Data is stored as a series of records, each storing key length, data length, key, and data. There are no alignment or sorting rules. The records are followed by a set of 256 hash tables of varying lengths. Since zero is a valid length, there may be fewer than 256 hash tables physically stored in the database, but there are nonetheless considered to be 256 tables. Hash tables contain a series of slots, each of which contains a hash value and a record offset. "Empty slots" have an offset of zero.
Hashes are unsigned 32 bit integers, and start with a value of 5381. For each byte of the key, the current hash is shifted five bits up, summed with itself, then XOR'ed with the current byte of the key. Overflow bits are discarded. Slots and tables are trivially computed from hashes. The target table is simply the lowest eight bits of the hash (e.g. hash modulo 256), and the slot within the table is the remaining bits of the hash modulo the table length (e.g. hash divided by 256 modulo table length).
[edit] Library
The official cdb library is publicly available, but not under an OSI-approved license. The license allows for verbatim distribution of the library source and inclusion into downstream software packages, but not of modified versions of the code. The unusual licensing and simplicity of the format has prompted others to re-implement the library and release it under more common terms, such as Michael Tokarev's TinyCDB library, available under the public domain.
Notably, the creator of cdb does not intend for cdb to be used as a shared library. This differs from virtually all similar databases, such as Berkeley DB.
