Pogreb

Pogreb is an embedded key-value store written in Go and designed for read-heavy workloads.

Indexes

Hash Table

Pogreb uses linear hash tables as indexes The hash function is by default, murmur32. Collision is solved by bucket chain which forms a linked list in the data file. The size of the whole hash table can represent as level L, so the total bucket number the hash table can hold is 2^L. Pogreb splits the buckets in the hash table when the items grow to a threshold(load factor) of the whole table size instead of rebuilding the hash table. Pogreb uses 70% as the default load factor. It records the index of bucket to be splited as S and increments S during each split. When S grows up to the max number the hash table can hold, Pogreb will increase L and S will point to bucket 0 again to start a new round.

Checkpoints

Non-Blocking

Pogreb has two options to synchronize the modification in memory to disk. Users can customize the interval duration. Then Pogreb will check automatically and do a synchronization between memory and database at the end of each period if any modification happened during this period. Users can also set the parameter to -1, then Pogreb will do a synchronization at the end of every write, like Put() and Del(). Users can also call Sync() for a manual synchronization anytime to flush the modification in memory to disk. .

Concurrency Control

Deterministic Concurrency Control

Pogreb supports multi-reader and one single writer. It uses a coarse grained lock for each operation. The lock is at the database level. Every read tries to fetch a shared lock and releases the lock when finished. Every write tries to fetch an exclusive lock that blocks other readers and writers while the lock is held.

Storage Architecture

Disk-oriented

Pogreb is a disk-oriented database. All its files are persistently stored on the disk and it will write data into in memory file temporarily. The file in the disk will be mapped to virtual memory first by mmap on a Unix like system and CreateFileMapping on Windows. Users can specify the OS being used or it will extract from the file system.

Storage Model

N-ary Storage Model (Row/Record)

Pogreb uses N-ary storage model. The two main file types for Pogreb are index file and data file. Index file stores the buckets as an array and each bucket is composed of a slot chain. Each slot stores the key information and the offset and size of value in the data file. Data file stores the key and value. Pogreb maintains a free list to record the free space in the data file. It will search the free list to find a suitable block first when doing insertion. If there is not enough space for the new key-value pair, it will extend the data file.

Data Model

Key/Value

Pogreb is a key/value store. There are no particular types for both keys and values in Pogreb. It stores keys and values as byte array. In the example given by the documentation, it converts strings to byte arrays to as the key. Pogreb restricts keys to be no more than 2^16 bytes and values to be no more than 2^31 bytes.

Foreign Keys

Not Supported

Query Interface

Custom API

Pogreb supports API in GO. Users can open or create a database with Open(). Users can also add sync configuration as a parameter when opening the database. It provides basic operations on database such as Put(), Get(), Has(), Delete(). Users can also iterate all the key/value pairs through Items() and Next(). The keys and values for all the interfaces have to in byte array form, and their lengths have to be within the max limit.

System Architecture

Embedded

Pogreb is an embedded database. The database created by Pogreb is represented as files on disk. Users can access it through the custom API and there is no administrator.