Designing a single-file mmap-backed read-only hashed multi-table database -- Volution Notes

Warning!

This is a work-in-progress, brainstorming document, which is not yet implemented.

Feedback is extremely welcome, see the comments section.

It is written with a bullet-style because it's easier to follow as a specification or for future reference.

Purpose

The goal is to have a persistent multi-namespace key-value database that is written once and read multiple times afterward.

Think something similar to CDB or Sparkey.

Where would I like to use this? Kawipiko!

What sets this apart from CDB (or other key-value stores)?

multiple keys can be mapped to the same value; (think of redirects, full HTTP header-sets common amongst multiple resources, pages that have the same content, etc.)
some values are small (redirects, icons, images, etc.) meanwhile some values are very large (media files);
some values share common parts (think headers, footers, common JS/CSS snippets, etc.;) (this aspect is not yet accounted for in the design;)
one doesn't actually need to store the keys (i.e. URIs / URLs / paths), just enough information to find the matching values (i.e. HTTP headers and HTTP body);

Requirements, constraints, assumptions

The database has the following characteristics:

it is stored as a single self-contained read-only file; (storing it on a raw block device is also a possibility;)
the maximum file-size is (at least) 16 TiB (i.e. 2^32 * 4096), depending on the chosen page size; (typical file-sizes are in the hundreds of MiB up to a few GiB;)
the format is portable across architectures and operating systems; (the main operating systems considered are POSIX-like, especially Linux;) (the main architectures considered are 64 bit Intel/AMD and ARM;)
it allows having multiple independent namespaces (tables); (no more than 64 Ki tables, i.e. 2^16;) (each table is identified by a 128 bit identifier;) (the 128 bit identifier is opaque and user-chosen;)
each table is an association of key-value pairs; (no duplicate keys are allowed in the same table;)
the maximum number of key-value pairs per table is (at least) 4 Gi (i.e. 2^32);
keys are arbitrary byte arrays of no more than 4096 bytes (i.e. 2^12); (empty keys are allowed;)
values are arbitrary byte arrays of no more than 64 GiB each (i.e. 2^32 * 16); (empty values are allowed;)
after creation, during the "access", the database is read-only; (accessible by any number of processes, without any synchronization or locking mechanisms;)
during the "access" phase, the only required functionality is (given table) retrieving the value associated with a given key; (there is no need to list the keys, range queries, deletions, updates, etc.);
compression is not a concern of the database;
verifying the integrity of the data file should be supported;

Main considerations and constraints during access:

during the "access", the database can be mmap-ed and shared by multiple processes;
value size distribution is multi-modal; (many small values, many few KiB values, some MiB values, and rarely over a few tens of MiB values;)
looking for a key (in a given table) should require on average 2.5 page faults; (excluding the reading of the value data, and excluding the lookup of the table;) (if the key comparison is required for the lookup, then this must be accounted for in the page faults;) (the page faults should apply for both looking-up existing and non-existing keys;)
lookups for a key that was not seen during the creation (i.e. non-existing keys) is allowed to return values for other existing keys; (i.e. false positives are allowed;) the probability of such wrong returns should should be low; however lookups for existing keys should always return the value associated to that key during the creation; (i.e. no false negatives are allowed;)
the overwhelming majority of the lookups are for keys that have been seen during the creation;
the lookup shouldn't require dynamic memory allocation;
the lookup should be efficient in terms of CPU cycles, CPU cache misses, and memory page faults;
if any error, precondition, or assertion, is encountered during the access, the entire process can be aborted;

Main considerations and constraints during the creation:

the file creation should be append-only; (using large in-memory buffers is allowed, but once the data is written to the underlying file, it should be in an append only maner;)
the creation process shouldn't be concerned with interruptions, crashes, recovery, etc.;
if any error, precondition, or assertion, is encountered during the creation, the entire process can be aborted;

Main assumptions:

the CPU cache line is 64 bytes, thus important fields should be clustered together within the 64 bytes;
the expected page size is 4 KiB; one can use smaller sizes if padding is a concern; one can use larger sizes if alignment is a concern;

High level overall design

the underlaying data structure is a hash-map with linear probing; (Robin-Hood hashing is an alternative;)
the keys are not stored; (only their fingerprints are used to allow look-ups);
a single 128 bit non-cryptographic but strong hash function is used for the keys;
each table is stored as an independent hash-map;
the data for each independent hash-map is stored as a contiguous, page aligned, memory region;
the data for each value is stored as contiguous bytes; (depending on the size, it might be page aligned, or padded to another alignment;)
the values can be mixed and shared between the indenpendent tables;
whenever a header is required, this is stored at the end of the data, thus being a trailer, so that the underlying data can be page-aligned;
integers are sorted as unsigned values in little-endian;
although checksums are stored, they are optional during normal operation, and are meant to verify against corrupted storage or retrieval;

Single-file byte-level format

Database header and trailer

header -- starting from the beginning of the file, going forwards:
- 128 bits (16 bytes) -- the magic number that identifies the file format;
  - one of these bytes should represent the major version of the file format; (odd values imply stable formats, even values imply experimental formats;)
  - one of these bytes is the log2 - 6 of the page size; (i.e. 0 means 64 bytes, 1 means 128 bytes, etc.;)
- 128 bits (16 bytes) -- a random nonce; (no cryptographic properties are required;)
- 256 bits (32 bytes) -- a public key used to sign the database; (all zeroes means no signature was created;)
- 128 bits (16 bytes) -- a user chosen database identifier; (used for example to identify the application, perhaps the version of the application, etc.;)
- (if needed) padding until the end of the current page;
- (at least 80 bytes are required for the header;)
trailer -- starting from the end of the file, going backwards:
- 128 bits (16 bytes) -- the same magic number as in the header;
- 128 bits (16 bytes) -- the same random nonce as in the header;
- 512 bits (64 bytes) -- a signature of the database; (all zeroes means no signature was created;)
- 256 bits (32 bytes) -- a checksum of the entire database;
- 32 bits (4 bytes) -- the page index where the tables descriptor ends;
- (if needed) padding until the beginning of the current page;
- (at least 132 bytes are required for the trailer;)
(the header has at least one page, and spans the smallest number of pages that can contain the header;) (the trailer follows the same rules as the header;)
(the file size must be a multiple of the page size;)
the file should not contain any pages that are not part of the header, trailer, or any of the descriptors below; it is allowed however to contain such unused pages (for example if writing on a raw block device), in which case such pages unused pages are not covered by any checksum, and should contain only zeroes, but might contain arbitrary values;

All tables descriptor

it ends with the page identified in the trailer of the database;
reading from the end of that page backwards:
- 256 bits (32 bytes) -- the checksum of the tables descriptor;
- 16 bits (2 bytes) -- the number of tables present in the database; (zero tables is acceptable;)
- (if needed) the minimum amount of padding to have the tables descriptor fit an integer number of pages;
- (at least 34 bytes are required for the tables descriptor trailer;)
starting from the beginning of the tables descriptor first page, going forwards:
- for each table present in the database a record with:
  - 128 bits (16 bytes) -- the identifier of the table; (unique;)
  - 32 bits (4 bytes) -- the page index where the table descriptor ends;
  - (exactly 20 bytes are required for each record;)
- (this array must be sorted by the identifier;)
- (it is allowed for two tables to point to the same page index, in which case the two tables are "aliases" of eachother;)
(it is allowed for the tables descriptor trailer to share the same page with the records, but these should not overlap;)
(at least 54 bytes are required for the whole tables descriptor that contains exactly one table;)

Individual table descriptor

it ends with the page identified in the tables descriptor record for the matching table;
reading from the end of that page backwards:
- 256 bits (32 bytes) -- the checksum of the table descriptor;
- 64 bits (8 bytes) -- the number of table entries (i.e. all hash-map buckets); (zero entries is acceptable;)
- 64 bits (8 bytes) -- the number of table key-value pairs (i.e. used hash-map buckets);
- 128 bits (16 bytes) -- key hash seed; (no cryptographic properties are required;)
- (if needed) the minimum amount of padding to have the table descriptor fit an integer number of pages;
- (at least 64 bytes are required for the table descriptor trailer;)
starting from the beginning of the table descriptor first page, going forwards:
- for each table hash-map entry:
  - 32 bits (4 bytes) -- part of the key hash; (part B)
  - 32 bits (4 bytes) -- the page index where the value descriptor ends; (as a special case, the 0x00000000 page index means that the value is empty, i.e. an empty byte array;) (as another special case, the 0xffffffff page index means that the entry is unused, and thus the key hash must also be 0xffffffff;)
  - (exactly 8 bytes are required for each hash-map entry;) (thus 8 records per single CPU cache-line;)
(it is allowed for the table descriptor trailer to share the same page with the hash-map entries, but these should not overlap;)
(how the hash-map is constructed or used is described in a later section;)
(at least 72 bytes are required for the whole table descriptor that contains exactly one key;)

Individual value descriptor

it ends with the page identified in the table key record;
reading from the end of the page backwards:
- 256 bits (32 bytes) -- the checksum of the value descriptor;
- 32 bits (4 bytes) -- the number of pages that represent this value descriptor; (i.e. the extent of pages;)
- 32 bits (4 bytes) -- the number of values stored within the current page (or extent of pages);
if the number of values stored is one, it means we have a large value, which is stored as follows:
- continuing to read from the end backwards:
  - 128 bits (8 bytes) -- the hash of the key to which the value belongs; (this includes part A, B, C, and the rest of the original hash;)
  - 64 bits (4 bytes) -- the size of the value;
  - (if needed) the minimum amount of padding to have the value descriptor fit an integer number of pages;
- starting from the beginning of the value descriptor first page, going forwards:
  - the actual data belonging to the value; (the actual data starts at a page boundary, thus it is page aligned;)
- (at least 52 bytes are required for a single-value descriptor;)
if the number of values stored is more than one, it means we have smaller values that are packed within the same page (or extent of pages), which are stored as follows:
- continuing to read from the end backwards:
  - 128 bits (8 bytes) -- key hash seed; (no cryptographic properties are required;)
  - 64 bits (4 bytes) -- padding;
- continuing to read from the end backwards:
  - for each value present in the value descriptor:
    - 32 bits (4 bytes) -- part of the key hash; (part C) (unique within the same value descriptor;)
    - 16 bits (2 bytes) -- the size of the value; (thus at most 64 KiB for each value in a multi-value value descriptor;)
    - 16 bits (2 bytes) -- the offset (after the multiplication by 16) (from the start of the first page of the value descriptor) of the value; (thus at most 1 MiB for all the values concatenated in a multi-value value descriptor; excluding the array describing the values;) (it is allowed for multiple values to share the same offset;)
    - (if needed) the minimum amount of padding to have the value descriptor fit an integer number of pages;
    - (exactly 8 bytes are required for each value record;) (thus 8 records per single CPU cache-line;)
  - (this array should be sorted by the key hash (part C);)
- starting from the beginning of the value descriptor first page, going forwards:
  - (usually) the concatenated values as identified by the length and offsets in the previous array;
  - (it is allowed for multiple values datas to overlap one another;)
- (at least 52 bytes are required for a multi-value descriptor;)
(it is allowed for the value descriptor trailer to share the same page with the actual value data, but these should not overlap;)

Overhead analysis

The total overhead of storing an empty database:

assuming a 64 byte page size;
128 bytes -- database header (with padding);
64 bytes -- tables descriptor (with padding);
192 bytes -- database trailer (with padding);
(384 bytes in total;)

The total overhead of storing a database with one table with one value of 1 byte:

assuming a 64 byte page size;
128 bytes -- database header (with padding);
64 bytes -- tables descriptor (with padding), containing one table;
128 bytes -- table descriptor (with padding), containing one key-value pair;
64 bytes -- value descriptor (with padding), containing one byte;
192 bytes -- database trailer (with padding);
(576 bytes in total;)

The total overhead of storing a key-value pair:

ignoring the actual value data;
ignoring the amortized global structures;
4 + 4 bytes in the table descriptor;
4 + 4 bytes in the value descriptor;
plus at most 16 bytes of padding;
16 bytes at least, 32 bytes at most, 20 bytes on average;
(all this assuming a multi-value descriptor, that can hold values of up to 64 KiB; for larger values the overhead is minimal relative to the data size;)

High-level algorithms

Hash-map algorithm

each hash map uses linear probing; (possibly created with Robin-Hood hashing, but the chain lengths are not stored;)
each hash map targets a 90% load factor;
the key is hashed into 128 bits using XXH3;
the first 64 bits (part A) are used to compute the first hash-map bucket;
the next 32 bits (part B) are used to find the proper hash-map bucket in a linear-probing fashion;
the next 32 bits (part C) are used to identify the proper value in a multi-value value descriptor;
if during the creation, the length of the linear probe is longer than 16 tries, another per-table seed is generated, and the table is re-created; (perhaps the load factor can be decreased;)
if during the creation, during linear probing (within the 16 tries), we find another key that has the same 32 bits (part B) with the current to-be-inserted key, another per-table seed is generated, and the table is re-created; (this is to ensure that when looking-up keys, we always access at most one value descriptor;)
during the creation, the creation algorithm must make sure that in a multi-value value descriptor, all keys have unique (part C) hashes; (this can be achieved by grouping the keys in another way, or by choosing another hashing seed;)

Checksumming

the value descriptor checksum is obtained by computing the Blake3 hash over the pages that hold the data, with the 256 bits of the checksum set to zero;
the table descriptor checksum is obtained by computing the Blake3 hash over the pages that hold the data, with the 256 bits of the checksum set to zero, followed by the 256 bits checksums of all the value descriptors ordered (uniquely) by their last page index;
the tables descriptor checksum is obtained by computing the Blake3 hash over the pages that hold the data, with the 256 bits of the checksum set to zero, followed by the 256 bits checksums of all the tables descriptors ordered by their identifier;
the database checksum is obtained by computing the Blake3 hash over the pages that hold the header data, followed by the pages that hold the footer data, with the checksum and signature set to zero, followed by the 256 bits checksum of the tables descriptor;

Signing

the public key is an Ed25519 public key;
the signature is an Ed25519 signature, computed over the database checksum;

Observations

the first and last pages of the database (where the header / trailer lives) can never be used as value descriptors; (thus their use as sentinel values;)
the nonce in the header / trailer is to detect truncated databases that happen to contain the magic number as values;
the nonce in the header / trailer can also be used as an extra seed for computing the key hashes;
page extents used for the database header / trailer, tables descriptor, each table descriptor, and each value descriptor can never overlap;
the values can be shared between tables by just sharing the value descriptor page indices;
if the data is highly compressible, the application can compress each data independently; (losing the possibility of long window compression;)
if the application wants to remove false positives, it could store the key as a suffix to the value, and compare it after the lookup to decide the rejection;