# Proposal for a high-performance storage system for OSMIC branching histories

The storage system consists of a binary ledger, an append-only concatext, a
reverse index of hashes of large chunks of text (organized…

* * *

### Proposal for a high-performance storage system for OSMIC branching
histories

#### Introduction:

OSMIC is a tree versioning system proposed & used as part of Project Xanadu®.
This document proposes an alternative, compacted, high-speed storage system
for OSMIC ledgers. For an introduction to OSMIC & the Enfilade, see [my
introduction to Xanadu technologies](https://hackernoon.com/an-engineers-
guide-to-the-docuverse-d080cdbb73a6). Alternatively, you may look at my proof
of concept implementations of
[OSMIC](https://github.com/enkiv2/misc/blob/master/ds-lib/osmic.py) and the
[Enfilade](https://github.com/enkiv2/misc/blob/master/ds-lib/Enfilade.py).

#### Abstract:

The storage system consists of a binary ledger, an append-only permascroll, a
reverse index of hashes of large chunks of text (organized first by length),
and an index & reverse index for translating OSMIC numbers into offsets into
the ledger.

#### Binary ledger:

The binary ledger consists of three fixed-length integers: a length, an
insertion offset into the versioned blob (concatext), and a start offset into
the permascroll.

The length is a signed 16-bit integer — negative for a delete operation; the
other two are unsigned 64-bit integers.

#### Permascroll:

The permascroll contains all historically-inserted text concatenated together
in insertion order.

#### Reverse hash index:

For long chunks of text (where length is more than some _n_ times the length
of the output of some fast hashing algorithm), we avoid double-inserting
strings into the permascroll by checking them against a reverse hash index.
This index consists of _k_ buckets organized by size. Each bucket associates a
hashed string to its position in the concatext. For long strings, the maximum
prefix for each bucket size will be filed into those buckets.

The value of _n_ must be calculated based on the cost of hashing  & index
lookup. I would start with _n_ =3 as a potentially-reasonable value.

The value of _k_ must be calculated based on the likelihood of collision for a
given number of hashes. The hashing algorithm should be fast and produce
relatively small output, in order to ensure performance, so collision is
possible at smaller sizes. (Cryptographic hashes are not reasonable in this
context.)

#### OSMIC number to ledger offset index:

This index should be an enfilade with 32-bit integer indices.

Lookup produces a structure consisting of:

  1. a signed 64-bit integer row number in the ledger, which must be multiplied by 18 (2 bytes length + 8 bytes for each offset) to get a byte offset. If the row number is positive, then the next row is contiguous (i.e., the next OSMIC number is the next row).
  2. a pointer to the previous & next OSMIC number entries in the enfilade.

#### OSMIC number to ledger offset reverse index:

An array of null-padded fixed-length string representations of OSMIC numbers,
in hexadecimal. Their ordering is the same as the corresponding rows in the
ledger. They are capped at 100 levels — in other words, 100 hex-encoded 32-bit
integers, or 800 bytes.

#### Insert behavior:

If an inserted string is smaller than _n_ , then it is added to the
permascroll and a row is added to the end of the ledger.

If an inserted string is larger than n, then it is hashed & looked for in the
reverse hash index. If it is not found, successive prefixes sized for each
buckets are tried. If a prefix is found, that prefix is used in a ledger row &
the remaining suffix is passed to regular insert. Any string larger than n
that is not found at all will be put into the permascroll & reverse hash
index.

All new ledger rows correspond to new OSMIC numbers, and these numbers are
added to both the forward and reverse OSMIC number indexes.

As with regular OSMIC, delete behavior is the same as insert behavior, with
the delete indicator (in this case, the sign of the length) inverted.

#### Single lookup behavior:

To reconstruct an action, we first look up the row number in the forward OSMIC
number index. We fetch the row. We then perform general lookup behavior.

#### General lookup behavior:

If we are in ‘rewind’ or ‘undo’ mode, we invert the sign on the ledger row’s
length value.

If this new sign is negative, we are in ‘delete’ mode: we do not fetch the
value of the string from the permascroll, but instead merely remove the
corresponding number of bytes from the concatext, beginning at the index
provided.

Otherwise, we fetch that number of bytes from the permascroll starting at the
permascroll index provided, and insert it into the concatext.

#### Bulk lookup (fast-forward / rewind) behavior:

To reconstruct a series of actions, we fetch the entire range from the OSMIC
number forward lookup enfilade, then break it into sets of contiguous ledger
rows. We fetch those sets of rows with single seek+read operations, creating a
single and fully-contiguous virtual ledger row list.

If we are in rewind mode, we reverse the order of these rows.

After that, we perform general lookup behavior.

By [John Ohno](https://medium.com/@enkiv2) on [January 7,
2019](https://medium.com/p/7cb324c7df2d).

[Canonical link](https://medium.com/@enkiv2/proposal-for-a-high-performance-
storage-system-for-osmic-branching-histories-7cb324c7df2d)

Exported from [Medium](https://medium.com) on September 18, 2020.