vsdb

VSDB

VSDB is an experimental database based on atomic updates of constant databases. Unlike other lightweight databases, VSDB supports full transactional semantics when reading and writing to the database. A VSDB database consists of several hash tables (with plans for other data structures). Transaction conflicts are detected and rolled back and the system maintains full ACID semantics. VSDB may be used across distributed filesystems such as NFS without problems.

The interesting this about VSDB is that it does this with no locking whatsoever, not even file locks. This means that the system is very robust against errors and portable across filesystems and even across different computers accessing the database via NFS or other shared filesystems. Any app accessing the database may die uncleanly or become disconnected from the file store at any point and the database cannot become corrupted. Moreso, a client may always trust the return code of a transaction commit to know definitively whether an update succeeded or failed. VSDB will even work over NFS and distributed filesystems which support its atomicity requirements (which are easier to meet than what UNIX generally provides) without requiring problematic locking daemons or services.

The price paid for this ability is more expensive updates of the database, to offset this, since we are building constant databases they are usually smaller than mutable ones containing only the raw data and minimal hash information. This also allows optimizations which are not possible in mutable databases which can be exploited for faster reading than mutable databases. There are several areas where this set of trade offs would be appropriate where traditionally other embedded databases such as Berkeley DB and GDBM have been used, but the added robustness and true guaranteed ACID transaction updates or the maximal speed when reading the database are needed.

Features

Data Format

The current database format will be changed, but the underlying ideas and update mechanism will remain the same. A database is a directory, in which various files and subdirectories exist. all objects whose names beginning with 'db' are parts of the database machinery. files beginning with two underscores are temporary files and may be deleted at any time (including when concurrent database access is going on) without affecting the correctness of the database.

file format

all values are encoded in bigendian format and are of unsigned integral types. 
        |"JWM\001" |generation | number of entries |raw record/key data| hash entries   |
        |--- 4 ----|--- 4 ---- | -------- 4 -------|  ...variable...   | ---20*num ---- |
each hash entry looks like this and is 20 bytes long. 
        struct vsdb_hashentry {
                uint32_t hash;         //hash of key
                uint32_t offset;       //offset (in bytes) of key/data pair in file
                uint32_t keysize;     
                uint32_t datasize;
                uint32_t overflow;     //index in hash table for hash collisions
        };
to look up a key, hash it. and take hash % num_entries as an index into the hash table. check if that entry matches. if it doesn't then 'overflow' may contain a link to an overflow spot in the same table. keep following the overflow links until you run out of them or find the entry wanted.

database structure

although all files in the directory have the same format, they have different roles depending on their name

update process

to update the database you create your new database in a temporary file and link(2) to dbd.[num]/db.[num + 1] where num is the generation number of the database you are updating.
This link succeeds if and only if your commit succeeds. all these further operations are optimizations and need not be successful for the algorithm to work. you then may delete your temporary file or rename it to 'db.cache' if your commit succeeded. and rename dbd.[num] to dbd.[num + 1]. Any client that notices your directory has the wrong name may promote it by renaming. They also cooperate on keeping a link to the most recent database available for quick lookup and deleting any database files numbering less than the directory name in the directory.
The reason for this odd update procedure is to keep the database in a consistent state even in the face of system crashes while at the same time guaranteeing that a client knows equivocally whether its transactions failed or succeeded.

See the API documentation. for the current interface. This is very alpha software at the moment, beware.

the Changelog has information on recent changes.

The Future

Download

** Here is the download directory **

My homepage -> computer stuff -> vsdb