Fetching latest commit…
Cannot retrieve the latest commit at this time.
|Failed to load latest commit information.|
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