Space-efficient data structure for analytical querying of multiple branching evolutions of a dataset

Question

Problem Description

I have a data state space: a set of data sets, each of which can be modelled as a collection of arbitrary key-value pairs. These data sets are each a branch of evolution of a parent data set, forming a tree (not a lattice; data sets branch but do not merge.) The root of the tree is an empty data set.

I'm not looking at/exploring the entirety of this data state space. Rather, I have a listing of all the leaf-node data sets which exist in use in the real world. I only care about these leaf-node data sets, and (sometimes) their ancestors.

I wish to find (or create!) a persistent (on-disk, distributed/sharded if necessary) data-structure for storing and querying of these in-use data sets. I would also accept a database management system that happens to have such a data-structure (or assemblage of features to simulate such a data structure) as a feature. I just have a practical need to store and query this data!

Requirements

This data structure would need the following operations:

• define a new data set in the store, in terms of a parent data-set identifier/handle; and a set of key-value "writes" which would create this data set if applied to the referenced parent;

• open the store with respect to a particular data-set identifier, returning a data-set handle;

• query the store + data-set handle for a particular key's value;

• query the store + data-set handle for the key-value pairs in a given key range;

• query the store + data-set handle for a dump of all key-value pairs in the data set.

• (optionally) obtain a cursor against a store + data-set handle + initial key, and use it to iterate forward/backward through key-value pairs, with each iteration returning a key-value pair.

Constraints imposed by the data:

• Many leaf-node data sets in the state space will contain billions of key-value pairs.

• Many leaf-node data sets are more than 10 million levels "deep" or "high" away from the root.

• Many data sets are trivial changes from their parent, consisting of one update or even zero updates (but will retain a distinct identity in the zero-update case.)

• Many data sets are non-trivial, consisting of hundreds of thousands of updates to their parent.

• Each branch node in the tree has, on average, 1.5 children (most have only one; some have two; very few have more than two.) The tree mostly consists of long linear segments of nodes, with branch nodes forking between a new "main branch" on one side; and a short, terminal "side branch" on the other.

Operational constraints:

• The read operations must be time-efficient (i.e. soft real-time/bounded latency), as the point of this data store is to serve read-heavy analytical queries.

• Insertion of new data sets into the store must scale into the millions without going exponential; but otherwise inserts can be fairly slow, taking on the order of seconds to commit a new data-set definition into the store.

• Opening a data set within the store can be time-costly (again ~seconds), though again, this overhead must grow slowly-enough to allow one to open a data-set buried "deeply" in the store. This "free" time can be used to unpack the data set from any compression/delta-encoding format, to cache data or required intermediate data-structures from disk into memory, etc.

• The store must be as space-efficient on disk as possible (allowing whatever disk-space overhead is required to satisfy the other constraints.) I don't have petabytes laying around to spread this store onto!

Discussion

The disk-space usage consideration is where things get interesting, IMHO.

Without a requirement of disk-space efficiency, the naive solution is to just have full copies of every distinct data-set stored separately in their own read-indexed storage files, possibly then distributing distinct data-sets onto their own network shards so read queries can be separately routed to them.

But this naive solution would throw the storage requirements for this state-space (recall, ~billions of KV pairs each, ~millions of nodes) into multi-petabyte territory, and I don't have that kind of space.

Intuitively, from experience tuning analytical database systems, I would expect a good on-disk data structure for OLAP backing-storage (including all required indices) to introduce no more than a 10x overhead on top of a change-data-capture representation of the source data. The change-data-capture representation of all these data sets (i.e. the representations that would be fed to the define operation above) currently sums to ~50GB; so I'd intuitively expect this data structure would demand no more than ~500GB of disk. Am I crazy to expect that?

I know I can get some easy wins in terms of storage overhead for general "deduplication" of data sets, by just relying on a filesystem with block-level copy-on-write, where each data-set in the state space becomes its own copy-on-write snapshot, and the snapshots form a tree. But this seems like it wouldn't scale operationally, because either I'd be using a sorted flat-file data set format (in which case inserts "in the middle" of data cause storage-overhead explosion in descendant snapshots) or I'd be using something like an on-disk LSM tree [e.g. LevelDB] or B+-tree [e.g. LMDB] (in which case each snapshot would add another "level" to the tree, causing either an explosion of file inodes in the case of LevelDB, or a fragmentation of each file into tiny per-layer extents in the LMDB case), in the end meaning that reads to a million-branch-deep data set in such a store would have quite a lot of overhead at the filesystem bookkeeping level.

I would guess that a good data-structure for this would involve, at some level:

• tries (HAMTs?)
• a notion of "keyframes" vs "interstitial frames", for representing the trivial change sets
• a notion of "highly-connected routes" through the tree, where "major branches" are repacked (defragmented?) and "minor branches" are re-stored in terms of their difference from a "major branch"

I'm aware of Datomic, which seems to have an architecture and set of operations similar to what I'm looking for; but which supports only a linear timeline, rather than a tree of timeline-branches. I'm unclear on whether its architectural design could be extended to support branching time without fundamental changes.

I'm also aware of what blockchain systems (e.g. Ethereum) are doing with merkle patricia trie-based storage. I've evaluated doing exactly this, but—at least as blockchains themselves implement this approach—the read performance doesn't scale for analytical workloads. (It works for these systems, because their evolution-steps are OLTP workloads, computing almost always against a "main branch" state—the outcome of the previous most-recent computation—which is therefore cached almost-entirely into memory. Everything other than the most-recent "main branch" state is able to be considered "cold." None of this is true for an OLAP use-case; OLAP queries look at arbitrary branches of a state-space at arbitrary times, with no branch or node being "hot.") I would expect that some modification (relaxation?) of this approach might be suitable, though, since the merkle aspect of the merkle patricia tries used here is only relevant for trustless multi-party state sharing, which doesn't come up in this design.

Answer 1

I recommend you use a persistent map data structure. A reasonable choice would be a persistent binary balanced tree or a persistent hash array mapped trie; with these choices, every operation can be done in $O(\log n)$ time or $O(1)$ time. You can store these data structures on disk and the disk overhead should be not too large: $O(n+\log m)$ or $O(n+m)$, where $n$ is the total number of items stored and $m$ is the number of "define" operations used to construct all of the datasets.

Since you have a read-mostly workload, as an optimization you can use your "opening" to load all of the key values in the data structure into memory and construct an in-memory hashmap that serves as a faster index into the data structure, and throw away this hashmap whenever memory gets tight or when you are done with that data structure; or you can build up such an index on the fly as a cache of where certain keys are located. Or, the data structure might perform adequately for your needs even without this.