TidesDB v0.7.0b

[guycipher]

We are going strong! Onto a new minor TidesDB v0.7.0 BETA. With this new minor we offering greater memory efficiency with merging operations, greater read efficiency with optional block indices and more system stability! Thank you to our awesome open-source crew as well for their meaningful contributions. We have also introduced a new external library xxhash to assist withe our internal sorted binary hash array which is used for block indices.

Features

• ACID transactions are atomic, consistent, isolated, and durable. Transactions are tied to their respective column family.
• Concurrent multiple threads can read and write to the storage engine. Column families use a read-write lock thus allowing multiple readers and a single writer per column family. Transactions on commit and rollback block other threads from reading or writing to the column family until the transaction is completed. A transaction in itself is also is thread safe.
• Column Families store data in separate key-value stores. Each column family has their own memtable and sstables.
• Atomic Transactions commit or rollback multiple operations atomically. When a transaction fails, it rolls back all commited operations.
• Cursor iterate over key-value pairs forward and backward.
• WAL write-ahead logging for durability. Column families replay WAL on startup. This reconstructs memtable if the column family did not reach threshold prior to shutdown.
• Multithreaded Compaction manual multi-threaded paired and merged compaction of sstables. When run for example 10 sstables compacts into 5 as their paired and merged. Each thread is responsible for one pair - you can set the number of threads to use for compaction.
• Background Partial Merge Compaction background merge compaction can be started. If started the system will incrementally merge sstables in the background from oldest to newest. Merges are done every n seconds. Merges are not done in parallel but incrementally.
• Bloom Filters reduce disk reads by reading initial blocks of sstables to check key existence.
• Compression compression is achieved with Snappy, or LZ4, or ZSTD. SStable entries can be compressed as well as WAL entries.
• TTL time-to-live for key-value pairs.
• Configurable column families are configurable with memtable flush threshold, data structure, if skip list max level, if skip list probability, compression, and bloom filters.
• Error Handling API functions return an error code and message.
• Easy API simple and easy to use api.
• Multiple Memtable Data Structures memtable can be a skip list or hash table.
• Multiplatform Linux, MacOS, and Windows support.
• Logging system logs debug messages to log file. This can be disabled. Log file is created in the database directory.
• Block Indices by default TDB_BLOCK_INDICES is set to 1. This means TidesDB for each column family sstable there is a last block containing a sorted binary hash array. This compact data structure gives us the ability to retrieve the specific offset for a key and seek to its containing key value pair block within an sstable without having to scan an entire sstable. If TDB_BLOCK_INDICES is set to 0 then block indices aren't used nor created and reads are slower and consume more IO and CPU having to scan and compare.

Building

Using cmake to build the shared library.

cmake -S . -B build
cmake --build build
cmake --install build

Requirements

You need cmake and a C compiler.
You also require the snappy, lz4, and zstd libraries.

Linux

sudo apt install libzstd-dev
sudo apt install liblz4-dev
sudo apt install libsnappy-dev

MacOS

brew install zstd
brew install lz4
brew install snappy

Windows

Windows using vcpkg

vcpkg install zstd
vcpkg install lz4
vcpkg install snappy

Dependencies

• Snappy
• LZ4
• Zstandard

Include

#include <tidesdb.h>

Usage

Each database method returns a tidesdb_err_t* which returns an error code and message. If no error, TidesDB returns NULL.

Example of error structure

typedef struct
{
    int code;
    char *message;
} tidesdb_err_t;

Opening a database

To open a database you pass the path to the database directory and a pointer to the database.

tidesdb_t *tdb = NULL;
tidesdb_err_t *e = tidesdb_open("your_tdb_directory", &tdb);
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
}

/* close the database */
e = tidesdb_close(tdb);
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
}

Creating a column family

In order to store data in TidesDB you need a column family. This is by design.

You pass

• the database you want to create the column family in. Must be open
• the name of the column family
• memtable flush threshold in bytes. Example below is 128MB
• skip list max level. Example below is 12 ( only if using TDB_MEMTABLE_SKIP_LIST ) pass TDB_USING_HT_MAX_LEVEL if using TDB_MEMTABLE_HASH_TABLE
• skip list probability. Example below is 0.24 ( only if using TDB_MEMTABLE_SKIP_LIST ) pass TDB_USING_HT_PROBABILITY if using TDB_MEMTABLE_HASH_TABLE
• whether column family sstable data is compressed
• the compression algorithm to use [TDB_NO_COMPRESSION, TDB_COMPRESS_SNAPPY, TDB_COMPRESS_LZ4, TDB_COMPRESS_ZSTD]
• whether to use bloom filters
• what data structure to use for the memtable [TDB_MEMTABLE_SKIP_LIST, TDB_MEMTABLE_HASH_TABLE]

/* create a column family with no compression and no bloom filters (slower reads) */
tidesdb_err_t *e = tidesdb_create_column_family(tdb, "your_column_family", (1024 * 1024) * 128, 12, 0.24f, false, TDB_NO_COMPRESSION, false, TDB_MEMTABLE_SKIP_LIST);
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
}

Using Snappy compression, bloom filters and hash table memtable.

/* create a column family with compression and bloom filter (the bloom filter provides fast read speed) */
tidesdb_err_t *e = tidesdb_create_column_family(tdb, "your_column_family", (1024 * 1024) * 128, TDB_USING_HT_MAX_LEVEL, TDB_USING_HT_PROBABILITY, true, TDB_COMPRESS_SNAPPY, true, TDB_MEMTABLE_HASH_TABLE);
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
}

Dropping a column family

/* drop a column family */
tidesdb_err_t *e = tidesdb_drop_column_family(tdb, "your_column_family");
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
}

Listing column families

You can list all column families in the database list as a string. You must free the string when done.

char *column_families = NULL;
tidesdb_err_t *err = tidesdb_list_column_families(tdb, &column_families);
if (err != NULL) {
/* handle error */
}

/* in this example we just print and free the column families */
printf("%s\n", column_families);
free(column_families);

Putting a key-value pair

You pass

• the database you want to put the key-value pair in. Must be open
• the column family name you want to put the key-value pair in
• the key
• the key size
• the value
• the value size
• when the key-value pair should expire. If -1 then it never expires.

/* put a key-value pair */
uint8_t key[] = "key";
uint8_t value[] = "value";

tidesdb_err_t *e = tidesdb_put(tdb, "your_column_family", key, sizeof(key), value, sizeof(value), -1);
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
}

Putting a key-value pair with TTL

/* put a key-value pair with TTL */
uint8_t key[] = "key";
uint8_t value[] = "value";

time_t ttl = time(NULL) + 10; /* 10 seconds */
tidesdb_err_t *e  = tidesdb_put(tdb, "your_column_family", key, sizeof(key), value, sizeof(value), ttl);
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
}

Getting a key-value pair

You pass

• the database you want to get the key-value pair from. Must be open
• the column family name
• the key
• the key size
• a pointer to the value
• a pointer to the value size

size_t value_len = 0;
uint8_t *value_out = NULL;
uint8_t key[] = "key";

tidesdb_err_t *e = tidesdb_get(tdb, "your_column_family", key, sizeof(key), &value_out, &value_len);
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
}

Deleting a key-value pair

You pass

• the database you want to delete the key-value pair from. Must be open
• the column family name
• the key
• the key size

uint8_t key[] = "key";

tidesdb_err_t *e = tidesdb_delete(tdb, "your_column_family", key, sizeof(key));
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
}

Transactions

You can perform a series of operations atomically. This will block other threads from reading or writing to the column family until the transaction is committed or rolled back.

You begin a transaction by calling tidesdb_txn_begin.

You pass

• the database you want to perform the operations in. Must be open
• the transaction pointer
• the column family name you want to perform the operations in

tidesdb_txn_t *transaction;
tidesdb_err_t *e = tidesdb_txn_begin(tdb, &transaction, "your_column_family");
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
}

Now we can add operations to the transaction.

const uint8_t key[] = "example_key";
const uint8_t value[] = "example_value";
tidesdb_err_t *e = tidesdb_txn_put(transaction, key, sizeof(key), value, sizeof(value), -1); /* you can pass a ttl, similar to put */
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
}

/* you can add delete operations as well */
e = tidesdb_txn_delete(transaction, key, sizeof(key));
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
}

/* now we commit */
e = tidesdb_txn_commit(transaction);
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
}

/* before you free, you can rollback */
tidesdb_err_t *e = tidesdb_txn_rollback(transaction);
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
}

/* free the transaction */
tidesdb_txn_free(transaction);

Cursors

You can iterate over key-value pairs in a column family.

tidesdb_cursor_t *c;
tidesdb_err_t *e = tidesdb_cursor_init(tdb, "your_column_family", &c);
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
    return;
}

uint8_t *retrieved_key = NULL;
size_t key_size;
uint8_t *retrieved_value = NULL;
size_t value_size;

/* iterate forward */
while ((e = tidesdb_cursor_next(c)) == NULL)
{
    e = tidesdb_cursor_get(c, &retrieved_key, &key_size, &retrieved_value, &value_size);
    if (e != NULL)
    {
        /* handle error */
        tidesdb_err_free(e);
        break;
    }

    /* use retrieved_key and retrieved_value
     * .. */

    /* free the key and value */
    free(retrieved_key);
    free(retrieved_value);
}

if (e != NULL && e->code != TIDESDB_ERR_AT_END_OF_CURSOR)
{
    /* handle error */
    tidesdb_err_free(e);
}

/* iterate backward */
while ((e = tidesdb_cursor_prev(c)) == NULL)
{
    e = tidesdb_cursor_get(c, &retrieved_key, &key_size, &retrieved_value, &value_size);
    if (e != NULL)
    {
        /* handle error */
        tidesdb_err_free(e);
        break;
    }

    /* use retrieved_key and retrieved_value
     * .. */

    /* free the key and value */
    free(retrieved_key);
    free(retrieved_value);
}

if (e != NULL && e->code != TIDESDB_ERR_AT_START_OF_CURSOR)
{
    /* handle error */
    tidesdb_err_free(e);
}

tidesdb_cursor_free(c);

Compaction

There are 2 ways to compact sstables. Manual multi-threaded paired and merged compaction and automatic background partial merge compaction.
Compaction removes tombstones and expired keys if ttl is set. Because merging merges and older and newer sstables only the newest version of key lives on.

Manual Multi-Threaded Parallel Compaction

You can manually compact sstables. This method pairs and merges column family sstables from oldest to latest. It will remove tombstones and expired keys if ttl is set.
Say you have 100, after compaction you will have 50; Always half the amount you had prior. You can set the number of threads to use for compaction. Each thread handles 1 pair.

tidesdb_err_t *e = tidesdb_compact_sstables(tdb, "your_column_family", 10); /* use 10 threads */
if (e != NULL)
{
    /* handle error */
    tidesdb_err_free(e);
}

Automatic / Background Partial Merge Compaction

You can start a background partial merge compaction. This will incrementally merge sstables in the background from oldest to newest when minimum sstables are reached. Merges are done every n seconds. Merges are not done in parallel but incrementally.
You can set the minimum amount of column family sstables to trigger a background partial merge. Background merging blocks less than manual compaction.

You pass

• the database you want to start the background partial merge compaction in. Must be open
• the column family name
• the number of seconds to wait before going to next pair and merging
• the minimum number of sstables to trigger a merge

tidesdb_err_t *e = tidesdb_start_background_partial_merge(tdb, "your_column_family", 10, 10); /* merge a pair every 10 seconds and if there are a minimum 10 sstables */

What's Changed

• tidesdb: _tidesdb_partial_merge_thread correction to remove null sstables after compaction iteration by @guycipher in tidesdb: _tidesdb_partial_merge_thread correction to remove null sstables after compaction iteration #245
• CI: Add GitHub action pipeline by @evgenykor in CI: Add GitHub action pipeline #246
• fix GH action for building tidesdb by @evgenykor in fix GH action for building tidesdb #247
• windows: Adjustment on skip_list_put to not use VLAs. Additions to compat.h as per @mrfealess by @guycipher in windows: Adjustment on skip_list_put to not use VLAs. Additions to compat.h as per @mrfealess #248
• • win: added mkdir support to compat.h as per issue tidesdb: windows builds, testing (clion, visual studio, visual studio code, more) #241.. by @guycipher in - win: added mkdir support to compat.h as per issue #241.. #250
• fixing as per issue discord invite is invalid or expired #255 on readme by @guycipher in fixing as per issue #255 on readme #256
• compat: windows compatibility adjustments as per issue tidesdb: windows builds, testing (clion, visual studio, visual studio code, more) #241 by @guycipher in compat: windows compatibility adjustments as per issue #241 #257
• tidesdb: tidesdb_list_column_families reformat as per issue tidesdb: tidesdb_list_column_families should return type of tidesdb_err_t * (as any other tidesdb API) but no char* #253 for API consistency by @guycipher in tidesdb: tidesdb_list_column_families reformat as per issue #253 for API consistency #258
• • tidesdb: rename tidesdb_start_partial_merge to tidesdb_start_backgr… by @guycipher in - tidesdb: rename tidesdb_start_partial_merge to tidesdb_start_backgr… #259
• readme: more information on compaction strategies in TidesDB. by @guycipher in readme: more information on compaction strategies in TidesDB. #260
• logging: tidesdb debug logging implementation. by @guycipher in logging: tidesdb debug logging implementation. #265
• readme & log: minor consistency corrections and read me update by @guycipher in readme & log: minor consistency corrections and read me update #266
• tidesdb: reformat so column family has a pointer to tdb instance. This allows us to write to tidesdb log say from column family methods. by @guycipher in tidesdb: reformat so column family has a pointer to tdb instance. This allows us to write to tidesdb log say from column family methods. #267
• • _tidesdb_flush_memtable on error memory corrections.... by @guycipher in - _tidesdb_flush_memtable on error memory corrections.... #268
• _tidesdb_get_available_mem on system start up we get available memory for system. On write operations like tidesdb_put we check the size of the key and value combined if exceeds available memory. by @guycipher in _tidesdb_get_available_mem on system start up we get available memory for system. On write operations like tidesdb_put we check the size of the key and value combined if exceeds available memory. #269
• logical correction with available_mem check on tidesdb_put and tidesd… by @guycipher in logical correction with available_mem check on tidesdb_put and tidesd… #270
• • TDB_AVAILABLE_MEMORY_THRESHOLD implementation. Limit key value pai… by @guycipher in - TDB_AVAILABLE_MEMORY_THRESHOLD implementation. Limit key value pai… #273
• tidesdb: _tidesdb_merge_sort corrections regards to memory and minor enhancements to avoid missing keys by @guycipher in tidesdb: _tidesdb_merge_sort corrections regards to memory and minor enhancements to avoid missing keys #274
• tidesdb: memory efficient blocked sstable sort merge optimization. issue tidesdb: pair merge memory optimizations #271 by @guycipher in tidesdb: memory efficient blocked sstable sort merge optimization. issue #271 #275
• bug: handle memtable pointers properly by @evgenykor in bug: handle memtable pointers properly #276
• Addition of binary hash array which soon will be replacing bloom filt… by @guycipher in Addition of binary hash array which soon will be replacing bloom filt… #277
• • tidesdb: _tidesdb_merge_sort corrections... by @guycipher in - tidesdb: _tidesdb_merge_sort corrections... #278
• bloom_filter__tests.c and binary_hash_array__tests.c to print seriali… by @guycipher in bloom_filter__tests.c and binary_hash_array__tests.c to print seriali… #279
• tidesdb: block indices implementation using sorted binary hash array at end of each sstable to assist retrieval methods seek to blocks in rather constant times and consistent times. issue tidesdb: block indices(offsets) optimization #249. by @guycipher in tidesdb: block indices implementation using sorted binary hash array at end of each sstable to assist retrieval methods seek to blocks in rather constant times and consistent times. issue #249. #280
• tidesdb: bump to beta version 0.7.0b by @guycipher in tidesdb: bump to beta version 0.7.0b #281

Full Changelog: v0.6.0b...v0.7.0b

---

This discussion was created from the release v0.7.0b.