Storage implements persistent representation of data held in Ledger. Such data include:
All data and metadata added in storage are persisted using LevelDB. For each page a separate LevelDB instance is created in a dedicated filesystem path of the form: {repo_dir}/{serialization_version}/ledgers/{ledger_dir}/{page_id_base64}/leveldb.
Additionally, metadata about all pages of a single user are persisted in a separate LevelDB instance. This includes information such as the last time a page was used.
The rest of the document describes the key and value representation for each row created in LevelDB to store each data type.
commits/{commit_id}timestamp, generation (i.e. length of the longest path to the first commit created for this page), root_node_id and parent_ids, as serialized by Flatbuffers (see commit.fbs).In storage there is no difference in the representation of value and node objects. Since these two types of objects can be quite big, they might be split in multiple pieces. Each piece is serialized in LevelDB as follows:
objects/{object_digest}{object_content}For value objects, {object_content} is the actual user defined content, while for tree nodes, it is the list of node entries (key, object_id and priority), references to child nodes, and the node level. Tree node content is serialized using Flatbuffers (see tree_node.fbs).
Note that when a Ledger user inserts a key-value pair, the key is stored in a tree node, while the value is stored separately, as described above.
Value or tree node objects might be split into smaller pieces that are stored separately. When processing a large object, its content is fed into a rolling hash which determines how the object should be split into chunks. For each such chunk, whose size is always between 4KiB and 64KiB, an identifier is computed and added in a list. Based on the rolling hash algorithm this list is split into index files, containing references (identifiers) towards either chunks of the original object's content, or other index files. At the end of the algorithm, the data chunks and index files form a tree, where the content of the object is stored on the leaves.
See also split.h and split.cc for more details.
Changes in Page (Put entry, Delete entry, Clear page) that have not yet been committed are organized in journals. A journal can be explicit, when it is part of an explicitly created transaction or part of a merge commit, or implicit, for any other case. On a system crash all explicit journals are considered invalid and once the system restarts they are removed from the storage. Implicit ones on the other hand, are immediately committed on system restart.
A common prefix for all explicit journal entries (journals/E) helps remove them all together when necessary, and an additional metadata row, for implicit journals only, helps retrieve the ids of the not-yet-committed journals.
Journal entry keys (for both implicit and explicit journals) are serialized in LevelDB as:
Row key: journals/{journal_id}/entry/{user_defined_key}
{journal_id} has an E prefix if the journal is explicit or an I prefix if it's implicit.
If the journal entry is about adding a new or updating an existing Ledger key-value pair, then:
Row value: A{priority_byte}{object_identifier}
Where {priority_byte} is either E if the priority is Eager, or L if it's Lazy.
If the journal entry is about removing and existing key-value pair, the value is:
Row value: D
Moreover, if a journal contains a page clear operation, a row with an empty value is added to the journal. If it is present, when the journal is commited, the previous state of the page must be discarded.
journals/{journal_id}/CFor every implicit journal an additional row is kept in LevelDB:
journals/implicit_metadata/{journal-id}{base_commit_id}{base_commit_id} is the parent commit of this journal. Note that implicit journals always have a single parent (merge commits cannot be implicit journals).
The list of head commits is updated and maintained in storage. For each head a separate row is created:
heads/{commit_id}{creation_timestamp}A row is added for each commit that has been created locally, but is not yet synced to the cloud:
unsynced/commits/{commit_id}{generation}Each piece, i.e. part of a value or tree node object, can be in any of the following states:
For each piece, a status row is stored:
{status}/object_digests/{object_piece_identifier}Where status is one of transient, local, or synced.
The cloud sync component persists in storage rows with some metadata.
sync_metadata/{metadata_type}{metadata_value}Currently, cloud sync only stores a single such line, which contains the server-side timestamp of the last commit fetched from the cloud.
Additionally to user-created content and metadata on this content, Ledger persists information on Page usage, such as the timestamp of when each page was last used. This information is used for page eviction, i.e. removing local copies of pages, in order to free up device storage when that is necessary.
Page usage information is stored in a dedicated path: {repo_dir}/page_usage_db using LevelDB.
For each page that is locally stored on the device a row is created in the underlying database:
opened/{ledger_name}{page_id}{timestamp} or {0}{timestamp} is the timestamp from when the given page was last closed. If the page is currently open, the value is a 0 timestamp.
For more information see also: