Understanding Bitcask, Part 1: Append-Only Storage, KeyDir, and Safe Compaction

How Bitcask handles active files, fast lookups, and races between normal writes and merging.

https://riak.com/assets/bitcask-intro.pdf

So, I have started reading the research paper for bitcask which implements the database as an append only structure.

The bitCask Implementation is used for storing and retrieving key/value data using log-structured hash tables that provide very fast access.

Check this image below the records are getting appended one by one to the file. If we have to update the records we just have to create a new entry and update the offset.

What is the complexity of each operation ?

Get, PUT and Delete: O(1)

Without keeping the index it would be O(N) since we have to go through each key and check the most recent key Value.

What If the the file on disk gets filled fully ?

We will always have a active file to which we write into so there is one writer thread pointing to the current active file always.

The index does not only store the offset or byte location it has the file Id present too to make sure that it can directly fetch the value from that particular fileId and offset location.

How can we merge and compact the records into a single file so that one file has all the updated information so we always have some useful segments and we merge and compact all the segments into a single segment

But what if there comes a race condition and when the key1: Val is read from the segment1 for merging but at the same time the writer thread too want to update the value then ?

So the list of operations that worked are:

1. Append key/value to data file

2. Receive its file_id, offset and size

3. Call keydir_put_int()

4. Decide whether the keydir should point to it

Call the bitcask_nifs_keydir_put_int() function where it is decided to which fileId and offset the index key will point to.

Get TheDepthStack’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Scenario 1:

Writer updates keydir(Index) first

old_file_id is the id of the latest record present in the immutable file which already has been filled.

f.proxy is the index pointer.

f.proxy_offset is the offset for the index hash table which points to the byte location at specific byte location.

Code: https://github.com/basho/bitcask/blob/d84c8d913713da8f02403431217405f84ee1ba22/c_src/bitcask_nifs.c#L1422

if (old_file_id != 0 &&
    (newest_put || entry.file_id != f.proxy.file_id) &&
    !(old_file_id == f.proxy.file_id &&
      old_offset == f.proxy.offset))
{
    UNLOCK(keydir);
    return ATOM_ALREADY_EXISTS;
}

Merge expects: (file=5, offset=100) Current keydir: (file=6, offset=500) ← new user value

Scenario 2:

This is a simple scenrio when the new write is successful and the Index or keydir points to the file greater or equal.

if ((newest_put &&
     (entry.file_id >= keydir->biggest_file_id)) ||
    ...)

Scenario 3:

bitcask/src/bitcask.erl at d84c8d913713da8f02403431217405f84ee1ba22 · basho/bitcask

case bitcask_nifs:keydir_get(State2#bc_state.keydir, Key) of
    #bitcask_entry{file_id=OldFileId}
      when OldFileId > WriteFileId ->
        State3 = wrap_write_file(State2),
        do_put(Key, Value, State3, Retries - 1, already_exists);

OldFileId = 11 // merged record currently in keydir or index hash table.

WriteFileId = 10 // writer’s existing active file

Therefore it rotates the writer to file 12 before writing. It then appends the new value and calls:

It then appends the new value and calls:

bitcask_nifs:keydir_put(
    KeyDir,
    Key,
    NewFileId,       % 12
    Size,
    NewOffset,
    Tstamp,
    NowTstamp,
    true,            % newest_put
    OldFileId,       % 11
    OldOffset
)

entry = (12, new offset)
expected old location = (11, old offset)
(index pointer)f.proxy = (11, old offset)
newest_put = true

The CASE matches, and this branch accepts the new user entry:

newest_put && entry.file_id >= keydir->biggest_file_id

https://github.com/basho/bitcask/blob/d84c8d913713da8f02403431217405f84ee1ba22/c_src/bitcask_nifs.c#L1446