Overview ¶

What is OlegDB ¶

OlegDB is a concurrent, pretty fast K/V hashtable with an Erlang frontend. It uses the Murmur3 hashing algorithm to hash and index keys. We chose Erlang for the server because it is functional, uses the actor model and the pattern matching is ridiculous.

In addition to this, liboleg is a C library that powers everything. liboleg exports a relatively simplistic API for use in other applications. We build the main database off of this library.

Installation ¶

Installing OlegDB is pretty simple, you only need a POSIX compliant system, make, gcc/clang (thats all we test) and Erlang. You'll also need the source code for OlegDB.

Once you have your fanciful medley of computer science tools, you're ready to dive into a lengthy and complex process of program compilation. Sound foreboding? Have no fear, people have been doing this for at least a quarter of a century.

I'm going to assume you've extracted the source tarball into a folder called ~/src/olegdb and that you haven't cd'd into it yet. Lets smash some electrons together:

$ cd ~/src/olegdb
$ make
$ sudo make install

If you really wanted to, you could specify a different installation directory. The default is /usr/local. You can do this by setting the PREFIX variable before compilation:

$ sudo make PREFIX=/usr/ install

Actually running OlegDB and getting it do stuff after this point is trivial, if your installation prefix is in your PATH variable you should just be able to run something like the following:

$ olegdb [data_directory]

...where [data_directory] is the place you want OlegDB to store persistent data. Make it /dev/null if you want, I don't care. You can also specify IP/port information from the commandline:

$ olegdb /tmp 1978 #Starts OlegDB listening on port 1978
$ olegdb /tmp 0.0.0.0 1337 #Starts OlegDB listening on the 0.0.0.0 IP, with port 1337
$ olegdb /tmp data.shithouse.tv 666 #Hostnames work too

Getting Started ¶

Communicating with OlegDB is done via a pretty simple REST interface. You POST to create/update records, GET to retrieve them, DELETE to delete, and HEAD to get back some information about them. Probably.

For example, to store the value Raphael into the named database turtles under the key red you could use something like the following:

$ curl -X POST -d 'Raphael' http://localhost:8080/turtles/red

Retrieving data is just as simple:

$ curl http://localhost:8080/turtles/red

Deleting keys can be done by using DELETE:

$ curl -X DELETE http://localhost:8080/turtles/red

You can also tell Oleg what the Content-Type of that key's value is:

$ curl -X POST -H "Content-Type: text/html" -d '<p>Raphael</p>' http://localhost:8080/turtles/red

OlegDB supports lazy key expiration. You can specify an expiration date by setting the X-OlegDB-use-by header to a *UTC* POSIX timestamp .

$ curl -X POST \
-H "X-OlegDB-use-by: $(date +%s)" \
-H "Content-Type: application/json" \
-d '{turtle: "Johnny", age: 34}' http://localhost:8080/turtles/Johnny
> POST /turtles/Johnny HTTP/1.1
> User-Agent: curl/7.22.0 (x86_64-pc-linux-gnu) libcurl/7.22.0
> Host: localhost:8080
> Accept: */*
> X-OlegDB-use-by: 1394323192
> Content-Type: application/json
> Content-Length: 27
>
\* upload completely sent off: 27out of 27 bytes
< HTTP/1.1 200 OK
< Server: OlegDB/fresh_cuts_n_jams
< Content-Type: text/plain
< Connection: close
< Content-Length: 7
<
無駄

And then when we try to get it back out again:

$ curl -v http://localhost:8080/turtles/Johnny
> GET /turtles/Johnny HTTP/1.1
> User-Agent: curl/7.22.0 (x86_64-pc-linux-gnu) libcurl/7.22.0
> Host: localhost:8080
> Accept: */*
>
< HTTP/1.1 404 Not Found
< Status: 404 Not Found
< Server: OlegDB/fresh_cuts_n_jams
< Content-Length: 26
< Connection: close
< Content-Type: text/plain
<
These aren't your ghosts.

As you can hopefully tell, the POST succeeds and a 200 OK is returned. We used the bash command date +%s which returns a timestamp. Then, immediately trying to access the key again results in a 404, because the key expired.

If you want to retrieve the expiration date of a key, you can do so by sending HEAD:

$ curl -v -X HEAD http://localhost:8080/turtles/Johnny
> HEAD /turtles/Johnny HTTP/1.1
> User-Agent: curl/7.35.0
> Host: localhost:8080
> Accept: */*
>
< HTTP/1.1 200 OK
\* Server OlegDB/fresh_cuts_n_jams is not blacklisted
< Server: OlegDB/fresh_cuts_n_jams
< Content-Length: 0
< Content-Type: application/json
< Expires: 1395368972
<

Cursor Iteration ¶

In 0.1.2, we added the ability to iterate through keys inserted into the database via the frontend. It's a pretty simple interface and follows the rest of the current URL idioms.

Each cursor operand is of the form /database/key/operand. In some operands (_last and _first) the key option is ignored. Using them is trivial.

Using any of the operands will return both the value of the key you requested (_next will return the next value, _prev will return the previous value, etc.) and the HTTP header X-OlegDB-Key followed by the key paired to the value you just retrieved. For example, say we have two keys in the database, aaa and bbb. To begin with, I can request the first key in the database:

$ curl -v localhost:8080/oleg//_first
> GET /oleg//_first HTTP/1.1
> User-Agent: curl/7.22.0 (x86_64-pc-linux-gnu) libcurl/7.22.0 OpenSSL/1.0.1
> zlib/1.2.3.4 libidn/1.23 librtmp/2.3
> Host: localhost:8080
> Accept: */*
>
< HTTP/1.1 200 OK
< Server: OlegDB/fresh_cuts_n_jams
< Content-Type: application/x-www-form-urlencoded
< Content-Length: 22
< Connection: close
< X-OlegDB-Key: aaa
<
I am the value of aaa.

As you can see, the key aaa is the first one in the tree of ordered keys. If you're paying attention, you've also noticed that I've omitted the parameter between the database specifier and the cursor operand _first. This is because the key is not used in this command. It will, however, be used in the next:

$ curl -v localhost:8080/oleg/aaa/_next
> GET /oleg/aaa/_next HTTP/1.1
> User-Agent: curl/7.22.0 (x86_64-pc-linux-gnu) libcurl/7.22.0 OpenSSL/1.0.1
> zlib/1.2.3.4 libidn/1.23 librtmp/2.3
> Host: localhost:8080
> Accept: */*
>
< HTTP/1.1 200 OK
< Server: OlegDB/fresh_cuts_n_jams
< Content-Type: application/x-www-form-urlencoded
< Content-Length: 22
< Connection: close
< X-OlegDB-Key: bbb
<
I am the value of bbb.

Logically, the key bbb follows the key aaa. Nice. In our request, we asked Oleg for the key after (_next) the key aaa. The value of the next key was returned, and we can see the header X-OlegDB-Key is set to the key that corresponds to that value. Lets see what happens if we try to get the next key, knowing that we only have two keys (aaa and bbb) in our database:

$ curl -v localhost:8080/oleg/bbb/_next
> GET /oleg/bbb/_next HTTP/1.1
> User-Agent: curl/7.22.0 (x86_64-pc-linux-gnu) libcurl/7.22.0 OpenSSL/1.0.1
> zlib/1.2.3.4 libidn/1.23 librtmp/2.3
> Host: localhost:8080
> Accept: */*
>
< HTTP/1.1 404 Not Found
< Status: 404 Not Found
< Server: OlegDB/fresh_cuts_n_jams
< Content-Length: 26
< Connection: close
< Content-Type: text/plain
<
These aren't your ghosts.

We get a 404 statuscode and a message to match. This informs us that we cannot iterate any farther and that we have reached the end of the list.

In addition to these to commands, you can use _last to find the last key in the database and _prev to iterate backwards. The usage of these commands is identical to those above:

$ curl -v localhost:8080/oleg//_last
> GET /oleg//_last HTTP/1.1
> User-Agent: curl/7.22.0 (x86_64-pc-linux-gnu) libcurl/7.22.0 OpenSSL/1.0.1
> zlib/1.2.3.4 libidn/1.23 librtmp/2.3
> Host: localhost:8080
> Accept: */*
>
< HTTP/1.1 200 OK
< Server: OlegDB/fresh_cuts_n_jams
< Content-Type: application/x-www-form-urlencoded
< Content-Length: 22
< Connection: close
< X-OlegDB-Key: bbb
<
I am the value of bbb.
$ curl -v localhost:8080/oleg/bbb/_prev
> GET /oleg/bbb/_prev HTTP/1.1
> User-Agent: curl/7.22.0 (x86_64-pc-linux-gnu) libcurl/7.22.0 OpenSSL/1.0.1
> zlib/1.2.3.4 libidn/1.23 librtmp/2.3
> Host: localhost:8080
> Accept: */*
>
< HTTP/1.1 200 OK
< Server: OlegDB/fresh_cuts_n_jams
< Content-Type: application/x-www-form-urlencoded
< Content-Length: 22
< Connection: close
< X-OlegDB-Key: aaa
<
I am the value of aaa.
$ curl -v localhost:8080/oleg/aaa/_prev
> GET /oleg/aaa/_prev HTTP/1.1
> User-Agent: curl/7.22.0 (x86_64-pc-linux-gnu) libcurl/7.22.0 OpenSSL/1.0.1
> zlib/1.2.3.4 libidn/1.23 librtmp/2.3
> Host: localhost:8080
> Accept: */*
>
< HTTP/1.1 404 Not Found
< Status: 404 Not Found
< Server: OlegDB/fresh_cuts_n_jams
< Content-Length: 26
< Connection: close
< Content-Type: text/plain
<
These aren't your ghosts.

Prefix Matching ¶

In addition to cursor iteration 0.1.2 added the ability to return the values of keys that match a given prefix. Use of this feature follows the same URL layout as it's predeccesors, mainly via the use of the _match qualifier.

For example, say I have three keys in the database, test_a, test_b and test_c. I can easily find the values of all of these keys in one operation by using the _match operand. To demonstrate:

$ curl -v localhost:8080/oleg/test/_match
> GET /oleg/test/_match HTTP/1.1
> User-Agent: curl/7.22.0 (x86_64-pc-linux-gnu) libcurl/7.22.0 OpenSSL/1.0.1
> zlib/1.2.3.4 libidn/1.23 librtmp/2.3
> Host: localhost:8080
> Accept: */*
>
< HTTP/1.1 200 OK
< Server: OlegDB/fresh_cuts_n_jams
< Content-Type: application/json
< Content-Length: 25
< Connection: close
< X-OlegDB-Num-Matches: 3
<
["test3","test2","test1"]

This returns a JSON-encoded list of all of your values. Also of note is the X-OlegDB-Num-Matches header which specifies the number of keys that matched the given prefix.

If no matches are present, a 404 is returned.

Technical Internals ¶

Hash Table ¶

At it's core, OlegDB is just a hashtable. On a good day, this means operations are O(1). Since we use linked lists to handle collisions see here the worst-case scenario for operations is O(n). This usually doesn't happen.

Rehashing happens when we run out of space. To handle this, we currently allocate a new block of memory, rehash all keys and move everything over. This is a blocking operation. If you know you're going to have a lot of keys and want to avoid this, you can tweak the HASH_MALLOC parameter before compilation. This controls the default amount of space that OlegDB will allocate.

Splay Trees ¶

In addition to the hash table, OlegDB also keeps track of currently inserted nodes via a splay tree. Going over the intricacies of splay trees is a little outside the scope of this documentation, but we do use it for several things and for several reasons.

In their simplified form, splay trees are just a specialized form of a self-balancing binary search tree. This means that searching for any given key in the tree is an O(log n) operation and can be done relatively quickly.

In addition to be a binary tree, a splay tree has the property of moving recently inserted keys to the top of the tree. This is known as a splaying operation. While some splay tree implementations splay on read, write and deletion, OlegDB only splays keys to the top of the tree upon insertion and deletion. We figured that, since the splay tree is at most a secondary structure in the Oleg ecosystem, we wanted it's impact to be minimal.

With splay trees installed, we can now iterate through the tree in a timely and efficient manor, and whats more, in a user-decided order.

Binary trees have several modes of traversal that can be useful in a database context. Traversing the tree in-order gives the user the ability to retrieve keys alphabetically, while traversing in a pre-ordered fashion will show the user when the keys were inserted.

Besides key-traversal, splay trees are used for prefix matching. Since binary trees are inherently sorted, we can iterate through one much faster than we could a list.

Splay trees can be turned on/off by changing how you open a database. See ol_feature_flags for a complete list of toggleable parameters.

LZ4 Compression ¶

OlegDB uses the super-fast LZ4 compression algorithm for keeping values on disk in a smaller size while maintaining a low-impact on insertion/deletion.

This is a toggleable feature. See ol_feature_flags for more detail.

AOL File ¶

The Append Only Log file is how Oleg keeps track of state outside of it's values files. Everytime a change occurs to OlegDB, that command is written to the AOL file. This is what allows OlegDB to be persistent.

Every now and then the AOL file needs to be squished (compacted) to remove old and expired data. The AOL file is designed to be human readable (mostly) so you can tell at a glance whats going on with your database.

Values File ¶

The values file augments the AOL file in persisting state to the disk. The values file is basically all of your data, more or less aligned in four megabyte blocks.

Starting in 0.1.2, this is how we store data on disk. Previously all values were stored in the AOL file. Instead, the values file is mmap()'d into RAM on database startup, allowing you to hold datasets bigger than memory.