JFDB.
c. 2016
A better building block for searchable data.
JFDB began with a persistent curiosity about how databases fit together. Existing systems could do the job, but their layers of storage, indexing, and interpretation left an enticing question: could a different foundation make the whole arrangement simpler? Building a database was a way to find out, and to understand the tradeoffs from the inside.
The question grew out of years moving between infrastructure, machine learning, and human interaction. Systems that learn from feedback need ways to remember what has happened and retrieve it from different perspectives. JFDB explored that need at the storage layer, as a compact library written in C and designed for Erlang.
Make indexing part of storage.
Consider a collection of people, each with interests, affiliations, and other properties. The same person might be found by name, profession, a fragment of text, or a combination such as engineers interested in convex optimization. Storing the record is straightforward. Keeping all those ways of finding it correct as the record changes is where the machinery accumulates.
JFDB makes the primary key, value, and index keys a single unit of storage. They are written together atomically. Replacing a record replaces its indexes as well, so searches no longer lead through obsolete associations. The application supplies the value and the ways it should be found; the storage engine maintains their relationship.
jfdb:assign(DB, [people, ada],
#{name => <<"Ada">>},
[[role, engineer],
[interest, <<"convex optimization">>]]).Several ways into the same data.
An index need not correspond to a field inside the record. It can express a classification, a calculated property, or a relationship useful to the application. Search combines those indexes through intersections, alternatives, and exclusions. Their hierarchical paths allow a query to select a whole branch or follow a partial text prefix.
jfdb:search(DB,
{all, [[role, engineer],
{pre, [interest, <<"convex">>]}]}).Primary keys use the same path structure. A branch can be opened as a sub-database and explored through the same interface as the whole. This gives the model something of the familiarity of a filesystem, with the additional freedom to find a value through many independent paths.
Finding the design between the extremes.
Making that interface work efficiently required looking beneath it. A log is easy to extend, but finding a particular item can require substantial searching. An immutable index can be prepared for fast retrieval, but rebuilding it for every change is expensive. Earlier work with DiscoDB provided a concrete example of that second extreme.
JFDB occupies the space between them with a log-structured merge trie. Each update adds a small indexed layer. Layers are merged as they accumulate, balancing the cost of writing against the number of places a read must search. Compaction can consolidate them into a single layer when faster retrieval is worth the upfront work.
The trie compresses shared prefixes and adapts its branches to their contents. Its layout on disk matches its representation in memory, allowing it to be mapped directly and cached by the operating system. The same structure that makes hierarchical queries natural helps keep the physical storage compact.
Curiosity as a method.
JFDB brought the public interface and the internal representation into close agreement. Index maintenance became part of storage; prefixes became both a way to search and a way to compress; merging became a way to trade work now for cheaper reads later. The result was a reusable component, and a deeper understanding of the design space that produced it. That understanding was part of the reason to build it in the first place.