Hierarchical Documents

Python Java

Goal

Create a representation for hierarchical documents.

Challenge

Support efficient storage and retrieval of documents, both as a whole and by subdocuments specified by paths.

Explanation

A hierarchical document has a tree-like structure, with the document ID as the root. We’ll map the hierarchy to a list of tuples in which each tuple corresponds to a path from the root to a leaf. These tuples will form keys, so each leaf is indexed by the path leading to it.

Ordering

Because each tuple represents a path from the document root to a leaf, the lexicographic ordering of tuples guarantees that adjacent paths will be stored in adjacent keys. Each tuple prefix will correspond to a subdocument that can be retrieved using a prefix range read. Likewise, a range read using the root as a prefix will retrieve the entire document.

Pattern

A document will consist of a dictionary whose values may be simple data types (e.g., integers or strings), lists, or (nested) dictionaries. Each document will be stored under a unique ID. If a document ID has not already been supplied, we randomly generate one.

We convert the document to a list of tuples representing each path from the root to a leaf. Each tuple is used to construct a composite key within a subspace. The document ID becomes the first element after the subspace prefix, followed by the remainder of the path. We store the leaf (the last element of the tuple) as the value, which enables storage of larger data sizes (see Key and value sizes).

If we’re given a serialized JSON object to start with, we just deserialize it before converting it to tuples. To distinguish the list elements in the document (a.k.a. JSON arrays) from dictionary elements and preserve the order of the lists, we include the index of each list element before it in the tuple.

We can retrieve any subdocument based on the partial path to its root. The partial path will just be a tuple that the query function uses as a key prefix for a range read. The retrieved data will be a list of tuples. The final step before returning the data is to convert it back to a document.

Extensions

Indexing

We could extend the document model to allow selective indexing of keys or values at specified locations with a document.

Query language

We could extend the document to support more powerful query capabilities, either with query functions or a full query language. Either would be designed to take advantage of existing indexes.

Code

Here’s a basic implementation of the recipe.

import itertools
import json
import random

doc_space = fdb.Subspace(('D',))

EMPTY_OBJECT = -2
EMPTY_ARRAY = -1

def to_tuples(item):
    if item == {}:
        return [(EMPTY_OBJECT, None)]
    elif item == []:
        return [(EMPTY_ARRAY, None)]
    elif type(item) == dict:
        return [(k,) + sub for k, v in item.iteritems() for sub in to_tuples(v)]
    elif type(item) == list:
        return [(k,) + sub for k, v in enumerate(item) for sub in to_tuples(v)]
    else:
        return [(item,)]

def from_tuples(tuples):
    if not tuples: return {}
    first = tuples[0]  # Determine kind of object from first tuple
    if len(first) == 1: return first[0]  # Primitive value
    if first == (EMPTY_OBJECT,None): return {}
    if first == (EMPTY_ARRAY, None): return []
    # For an object or array, we need to group the tuples by their first element
    groups = [list(g) for k, g in itertools.groupby(tuples, lambda t:t[0])]
    if first[0] == 0:   # array
        return [from_tuples([t[1:] for t in g]) for g in groups]
    else:    # object
        return dict((g[0][0], from_tuples([t[1:] for t in g])) for g in groups)

@fdb.transactional
def insert_doc(tr, doc):
    if type(doc) == str:
        doc = json.loads(doc)
    if not 'doc_id' in doc:
        new_id = _get_new_id(tr)
        doc['doc_id'] = new_id
    for tup in to_tuples( doc ):
        tr[doc_space.pack((doc['doc_id'],) + tup[:-1])] = fdb.tuple.pack((tup[-1],))
    return doc['doc_id']

@fdb.transactional
def _get_new_id(tr):
    found = False
    while (not found):
        new_id = random.randint(0, 100000000)
        found = True
        for _ in tr[doc_space[new_id].range()]:
            found = False
            break
    return new_id

@fdb.transactional
def get_doc(tr, doc_id, prefix=()):
    v = tr[doc_space.pack((doc_id,) + prefix)]
    if v.present():
        return from_tuples([prefix + fdb.tuple.unpack(v)])
    else:
        return from_tuples([doc_space.unpack(k)[1:] + fdb.tuple.unpack(v)
                            for k, v in tr[doc_space.range((doc_id,)+prefix)]])