To build the software:
$ make
To install it:
$ sudo make install
This will put the executables in /usr/local/bin
To initialize or re-create the database files:
$ sudo /usr/local/bin/dbr_ctl initdb [force]
To start the db:
$ sudo /usr/local/bin/dbr_ctl start
Look at the top of the dbr_ctl script for some initialization variables you
might want to change.
--------------
Precis
--------------
Roxanne is a very simple database server that allows a client to store and
retrieve values by key. Keys are stored in a hash map of 64K buckets. Hash
collisions are resolved by separate chaining onto linked lists at the end
of the index file. The default location for the index file is in
/var/roxanne/idx
In addition to value lookups by key, the database provides a way to group
keys in a hierarchical directory structure. See Composite Keys below.
The values for the given keys are stored in contiguous 4KB blocks in the
database file (/var/roxanne/db). A file called block_bitmap tracks the
free/busy blocks in the db file. The dbr processes memory-map this file for
very fast access. The db file starts out with zero blocks. Blocks are only
added to the db file as needed to accomodate new records. As typically
built, the database can accomodate about a billion blocks.
--------------
Composite Keys
--------------
The database supports the notion of a composite key. That is, a key
that is subdivided into a hierarchy that all keys participate in. The key-
space is similar to a typical Unix filesystem organized into directories.
To work with hierarchical keys, divide them with spaces ' '. The last
element becomes the value. The 'value' does not participate in the
key-space.
The commands
create finance accounting payroll employees 50
create finance accounting receivables employees 70
Creates a 4-level hierarchy:
1 2 3 4
finance
accounting
payroll
employees
receivables
employees
The key-space then becomes a kind of database on its own. A client
can query the database for all the subkeys of a path. This gives clients
building blocks for range queries and ordered (sorted) results.
Nodes in the key-space are reference-counted so that repeating groups
in the hierarchy don't waste space.
All lookups of values are still done via hashmap of the entire key. In
other words, values can only be fetched by providing THE ENTIRE KEY.
In this case, the hash-lookup key is 'finance accounting payroll employees'.
It points to a starting block in the db that contains '50'.
This means that point-lookups of records will always be very fast, but that
the operator can use the key-space to organize and sort results.
Results from the keys command return in ascending sort order (strcmp).
--------------
Usage Example
--------------
madison:Roxanne rothrock$ sudo dbr_ctl start
Started listening.
carp:Roxanne rothrock$ telnet localhost 4080
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
create alpha record_1
STATUS: OK
SIZE: 9
Write OK.
create alpha beta record_2
STATUS: OK
SIZE: 9
Write OK.
read alpha
STATUS: OK
SIZE: 8
record_1
read alpha beta
STATUS: OK
SIZE: 8
record_2
...Now a demonstration of the 'keys' command:
create alpha gamma record_3
STATUS: OK
SIZE: 9
Write OK.
create alpha delta record_4
STATUS: OK
SIZE: 9
Write OK.
keys alpha
STATUS: OK
SIZE: 16
beta delta gamma
--------------
Protocol
--------------
Data manipulation commands:
create key [key]...value<newline>
read key [key]...<newline>
delete key [key]...<newline>
keys [key] [key]....<newline>
Other commands:
quit
Response:
"STATUS: <status string>\nSIZE: <integer>\n<integer> long string of bytes\n\n"
--------------
On Disk
--------------
The initial and maximum sizes are hard-coded in the application along
with the units of growth and storage. Eventually, these will become
configurable options. For now, it's just simpler this way.
Roxanne's persistent storage lives in /var/roxanne by default.
$ du -skh /var/roxanne/*
128M /var/roxanne/block_bitmap
64K /var/roxanne/db
64M /var/roxanne/idx
24K /var/roxanne/keydb
0B /var/roxanne/keydb_freelist
### The Block Bitmap (/var/roxanne/block_bitmap)
Each _bit_ in this file corresponds to a 4 KB block in the 'db' file.
Roxanne processes memory-map this file and use it keep track of used
and free blocks. Only one process may update the block bitmap at any
time. The block bitmap file provides a way to very quickly find and
reserve a contiguous set of blocks to store values.The block_bitmap
file is regularly flushed to disk with msync() after each reservation
request. The size of the block bitmap file is fixed at 128MB which is
enough space to keep track of 1,073,741,824 blocks.
### The database (/var/roxanne/db)
All values are stored in the db file. The unit of storage in the 'db'
file is the block, and all blocks are 4KB.
The db file starts out small and grows as more values are added to the
the database. All values inserted into the database are stored in
contiguous blocks. This simplifies the code, and provides for fast access,
but some fragmentation will occur over time if the database serves lots
of reads and writes of varying size.
#### The hash index (/var/roxanne/idx)
Initially sized at 64 megabytes, the hash index stores the full, composite
keys for values in the db file. An entry in the index is comprised of a
key stored as a string, an integer that represents a byte-offset in the
db file, an integer representing the length in bytes of the value, and
a third integer that represents a byte-offset in the idx file for
chaining additional keys.
Hash collisions are resolved by the separate chaining method. Each
index entry is 1024 bytes, so the hash table has 65,536 slots. When a
collision occurs, the colliding key is appended to the end if the index
file and the key in the slot where the collision occurred has its
'next' pointer updated to be the byte-offest in the index file where
the append occurred.
#### The keydb (/var/roxanne/keydb)
Initially sized at 0 bytes, the keydb stores the composite key hierarchy.
Each level of the hierarchy is stored as a binary tree.
Each node in the hierarchy has: a key-part, a left pointer (less-than),
a right pointer (greater-than), and a next pointer that points to the
next level in the hierarchy.
Nodes have a reference count so that duplicate key-parts don't require
additional space. Unfortunately, the database does not yet support
reclamation of keydb nodes with a reference count of 0.
##### Example
Consider the following two composite keys (values left off):
foo bar toast
foo bar jam
This set of two composite keys comprises 4 nodes in the keydb, stored
like so:
key refcount next-pointer left-pointer right-pointer
------------------------------------------------------------
foo 2 bar NULL NULL
bar 2 toast NULL NULL
toast 1 NULL jam NULL
jam 1 NULL NULL NULL
Next, add these composite keys (again, values left off).
foo bar whiskey
zen
zoo
egg
The table now looks like this:
key refcount next-pointer left-pointer right-pointer
------------------------------------------------------------
foo 3 bar egg zen
bar 3 toast NULL NULL
toast 1 NULL jam whiskey
jam 1 NULL NULL NULL
whiskey 1 NULL NULL NULL
zen 1 NULL NULL zoo
zoo 1 NULL NULL NULL
egg 1 NULL NULL NULL
Here is the composite-key space represented graphically:
+---+foo+----+
| + |
| | |
| | |
v v v
egg bar zen+--+
+ |
| v
| v
v zoo
+--+toast+--+
| |
| |
| |
v v
jam whiskey
459134f146