Data Model

Key/Value

At its core, OlegDB is simply a concurrent key/value hash table. It uses the open-source MurmurHash3 hash function (32 bits option). Collisions are handled using separate chaining with linked list.

In addition to the hash table, OlegDB keeps track of inserted nodes using a splay tree (self-balancing binary search tree) data structure. It enable users to iterate through inserted keys in a chosen order. In order to save space, the user can chose to get rid of this optional structure through a toggleable parameter.

Logging

Logical Logging

OlegDB uses an append-only log file (nicknamed AOL) to record the high level operations executed by transactions on the database.

Storage Architecture

Disk-oriented

OlegDB uses disk storage. The system keeps track of its state through two different types of data:

• the Value file: contains all the inserted values, aligned in a four megabytes block (by default). On startup, this file is loaded in RAM using the mmap() system call.
• the AOL file: contains transaction logs. It is regularly cleaned to remove expired data.

In the original release of OlegDB, this AOL file was the only persistent data of the system and all the values were kept in memory while the database was running. The Value file was added in later versions of the implementation.

Compression

Dictionary Encoding

OlegDB uses the LZ4 lossless data compression algorithm for storing values on disk. The user has the possibility to disable this feature if they want to accelerate data operations.