Lite³: A Serialized, Schemaless, Zero-Copy Datastore

Features

- Schemaless & self-describing

- No (de)serialization step required

- Zero-copy reads + writes of any data size

- Convertable to/from JSON for human readability

- Protocol agnostic

- O(log n) amortized time for all operations

- Built-in pointer validation

- Worst-case latency guarantees for real-time applications

- Low memory profile

- No `malloc()`, caller provides buffer

- A single C11 library with ~1000 LOC

- MIT license

Lite³ explained

JSON comparison

To understand Lite³, let us first look at JSON.

When receiving a JSON-message, it is parsed using JSON.parse() and converted into a 'dictionary object'.

In most cases, the programming language implements a dictionary as a hashmap which supports O(1) constant time lookups, inserts and deletions. In this way, the dictionary acts as the 'intermediate datastructure' to support mutations and lookups.

To send data, the dictionary object must be serialized again using JSON.stringify() back into a JSON string.

In Lite³, lookups, inserts and deletions (get(), set() & delete()) can be directly performed on the serialized form. Since it is already serialialized, it can be sent over the wire at any time.

Think of it as the 'dictionary itself' being sent, thus encoding to a separate string representation becomes unnecessary.

This works because Lite³ structures are always contiguous in memory, unlike most dictionaries which are implemented as hashmaps.

Why B-tree?

Lite³ internally uses a B-tree datastructure.

B-trees are well-known performant datastructures, as evidenced by the many popular databases using them (MySQL, PostgreSQL, MongoDB & DynamoDB).

The reason for their popularity is that they allow for dynamic insertions/deletions while keeping the datastructure balanced and always guaranteeing log(n) operations. Additionally, the nodes sizes can be tuned to disk page sizes, making maximum use of hardware.

However, B-trees are rarely found in a memory or serialization context. For memory-only datastructures, common wisdom rather opts for hashmaps or regular binary trees. B-trees are seen as too 'heavyweight'.

But we can do the same in memory, except that node sizes will be tuned to cache lines, rather than disk pages.

Literature suggests that modern machines have nearly identical latency for 64-byte and 256-byte memory accesses. Currently, Lite³ uses a (configurable) node size of 3 cache lines. Essentially, we create a stripped down micro B-tree specifically adapted for fast memory lookups.

Remember that it is also possible to use Lite³ purely as a memory datastore.

An algorithmic observer will note that B-trees have logarithmic complexity, versus hashmaps' constant time lookups. But typical serialized messages are often small (70% of JSON messages are < 10kB) and only read once. So the difference in logarithmic time vs constant time operations will rarely be noticable except with very frequent updates on large structures (larger than LLC).

More importantly, the Lite³ structure completely eliminates an O(n) parsing and serialization step.

Byte layout

In Lite³, all tree nodes and key-value pairs are serialized inside a single byte buffer.

Tree hierarchies are established using pointers; all parent nodes have pointers to their child nodes:

|----------------|-------|----------------|----------------|-------------|----------------|-------------
|      ROOT      |#DATA##|    CHILD #1    |    CHILD #2    |#####DATA####|    CHILD #3    |####DATA####...
|----------------|-------|----------------|----------------|-------------|----------------|-------------
   | | |___________________|                |                              |
   | |______________________________________|                              |
   |_______________________________________________________________________|
		

Nodes consist of key hashes stored alongside indexes to key-value pairs (data entries), as well as child node pointers:

 NODE
|--------------------------------------------------------------------------------------------|
|      h(key1) h(key2) h(keyN)      *kv1 *kv2 *keyN      *child1 *child2 *child3 *childN     |
|--------------------------------------------------------------------------------------------|
       |                            |                    |
      hashed keys                  kv-pair pointers     child node pointers
      used for key comparison      pointing to data     used for tree traversal
                                   entries
		

The key-value pairs contain the actual data and are stored in between nodes:

 KEY-VALUE PAIR              KEY-VALUE PAIR               KEY-VALUE PAIR
|---------|-----------------|----------|-----------------|----------|-----------------|
|  key 1  |     value 1     |   key 2  |     value 2     |   key N  |     value N     |
|---------|-----------------|----------|-----------------|----------|-----------------|
		

- On insertion: The new nodes or key-value pairs are appended at the end of the buffer.

- On deletion: The key-value pairs are deleted in place.

TODO: freed blocks are added to the GC (garbage collection) index.

Over time, freed blocks cause the contiguous byte buffer to accumulate 'holes'. For a serialization format, this is undesirable as data should be compact to occupy less bandwidth. Lite³ will use a defragmentation system to lazily insert new values into the gaps whenever possible. This way, fragmentation is kept under control without excessive data copying or tree rebuilding (STILL WIP, NOT YET IMPLEMENTED).

While it may seem wasteful to store so much metadata inside a serialized message, remember that all of this reduces the operation required to parse/serialize to a single memcpy(). In effect, a tradeoff is made in favour of CPU-cycles under the assumption of ample bandwidth availability.

Despite being a binary format, Lite³ is schemaless and can be converted to/from JSON for human-readability.