Three-Dimensional Data Storage

The difficult part in storing any kind of data is to enable efficient access and manipulation. The patterns of data access that a Willow implementation needs to support are primarily determined by two factors: how do applications access the data, and how do several data stores sync their contents?

The bare minimum functionality that a Willow database has to provide to applications is the creation of new Entries, and retrieval of Payloads by Entry. The three-dimensionality of Willow suggests a natural way for applications to access data in bulk: by querying for all Entries in an Area11Queries for 3dRanges are not particularly meaningful in the face of end-to-end encrypted data; we recommend to always use Areas in human-facing components such as programming APIs..

As for the requirements of syncing, we shall use the Willow Transport Protocol (WTP) as a baseline. The WTP needs to compute Fingerprints for arbitrary AreaSlices, to split arbitrary AreaSlices into multiple, roughly equally-sized subranges, and to constrain Areas to a number of newest Entries (to work with AreasOfInterest).

This gives us a fairly compact feature set, revolving around spatially constrained access to a three-dimensional arrangement of Entries.

There are two general approaches to working with AreaSlices. One is to convert each AreaSlice into a small number (at most five) of 3dRanges and to then employ standard three-dimensional data structures; we give a brief introduction to such datastructures below.

Alternatively, a database can use denormalisation to maintain a bounded number of one-dimensional indexes that together suffice to serve arbitrary AreaSlice queries. The denormalisation is explained in  [?], and is the main reason for why the Willow protocols favour AreaSlices over 3dRange in its region-based set reconciliation. Another alternative might be to denormalise subspaces and to then use a two-dimensional search tree for handling Paths and Timestamps.

Multidimensional search data structures have been studied for decades, whether in database research, computer graphics, geoinformatics, or several other fields of computer science. The bad news is that — unlike one-dimensional search data structures such as self-balancing search trees — no one-size-fits-all data structures with acceptable worst-case complexity profiles are known. The good news, however, is that this has not stopped decades worth of engineering power to develop systems that easily satisfy all practical requirements.

Unfortunately, Willow requires some features not found in off-the-shelf solutions. While there exist several solutions for managing and querying multidimensional data indexed by fixed-width integers or floating point numbers, lexicographically sorted strings of strings (i.e., Paths) are a different beast. Fingerprint aggregation is another feature you will not find in SQLite.

Hence, we now give pointers to some standard implementation techniques for multi-dimensional data structures. For more in-depth introductory coverage, we recommend part four of the Handbook of Data Structures and Applications (Mehta & Sahni, 2004).

• Octrees recursively split three-dimensional volumes into eight equally-sized sub-volumes, until every leaf volume contains at most one data point. This can lead to deep tree structures for points that lie close together but whose coordinates take many bits to represent. Paths are fairly likely to trigger these cases, so octrees (and any other space-partitioning techniques) should be enjoyed with caution.
• K-D trees are search-trees where each node splits items along a single dimension, cycling through the different dimensions based on the depth of the nodes. Unlike one-dimensional search trees, balancing and space utilisation of K-D trees tend to degrade over time. Practically useful variations, such as Bkd-trees (Procopiuc et al., 2003) can quickly become rather complicated.
• R-trees arrange data in a containment hierarchy of minimum bounding boxes. Their performance hinges on heuristic choices in maintaining the containment hierarchy under insertions and deletions, with R*-trees being a popular, efficient choice.
• A more simplistic option is to maintain three one-dimensional search trees of the same Entry set, each using different linearisations of the three dimensions: one sorts by subspace_id first, using paths as tiebreakers, and using timestamps as final tiebreaker; the next tree has paths first, timestamps second, subspace_id third; the final tree has timestamps first, subspace_id second, paths third. This technique is often used by RDF triple stores, for example by the Rya store (Punnoose et al., 2012).
• UB-trees linearise multidimensional data according to its Z-order (or, alternatively, its Hilbert order, and then store it in a one-dimensional search tree. The theoretical worst-case behavior is subpar, but in practise, these data structures perform well on reasonably distributed data.

All of these data structures are tree-based, so they can readily be adapted to store the Fingerprints of the items of each subtree in every tree node, hence allowing for efficient Fingerprint computation. Similarly, storing the total number of items in each node allows for efficiently working with AreasOfInterest, and can guide the splitting of 3dRanges for region-based set reconciliation.

Three-dimensional storage lies at the heart of a performant Willow database, but any implementation effort must ask several further questions. How do applications interface with the data store? Can they subscribe to updates in real time? Or even request replays of changes after reconnecting to the database after a longer time span? Who controls which payloads should be requested, persisted, deleted? Can applications issue atomic transactions? Should there be indexes for efficient access beyond the three-dimensional data model, based on payload contents?

Each of these questions is an exciting project on its own, and we are committed to exploring them further.