This page may require house cleaning since the recent migration to a new data model
This page describes the design of the Arrow Space as it takes place in the Entrelacs System prototype.
Source code: https://github.com/miellaby/entrelacs/blob/master/space.c
The Arrow Space prototype aims to map abstract arrows into a single persistence file of the host system during a process called assimilation. This file is operated as a giant hybrid double-hashed-and-coalesced open-addressing hashtable.
The persistence file is divided into individual slots also known as cells and identified by cell addresses.
As stated by the reentrant definition of the Entrelacs Paradigm, a regular arrow is a a pair of arrows. Such an arrow is consequently stored as a pair of addresses within a single cell, in addition with metadata.
RAM is used as a massive direct-mapped cache of cells on top of the persistence file.
When needed, arrows climb up to a level 1 (RAM) memory device. This memory is used as a fine-grained direct-mapped cache of level 0 (disk) cells.
See the page Arrow Cache for further details and https://github.com/miellaby/entrelacs/blob/master/mem1.c for the actual code.
The Arrow Space aims to store atomic arrows, also known as Entrelacs, in addition with regular pair of arrows.
One will distinguish atomic data depending on their sizes.
Despite atoms being binary objects, they are handled like arrow constructs, namely Entrelacs, which are discrete reentrant structures of arrows. Atoms are consequently self-indexed, deduplicated and fully-connected like their arrow counterparts.
One relays on Open Addressing to manage conflicts within the storage space.
When one cannot store an arrow at its expected location because the cell is already occupied, one repeatedly shifts the cell adress by a deterministic offset until a free cell is found.
When looking for a given arrow, one probes the arrow space starting from the expected location and follows the same sequence of shifts until the arrow is found (it’s a hit!) or an empty cell is encountered (it’s a miss!).
The Open Addressing approach to hash conflict has a limitation. Clearing a cell can disrupt one or more sequences of occupied cells, which can result in the loss of information.
The retained solution consists in including a dedicated pebble counter into each cell. It is incremented each time the cell is visited while probing for an available location. Conversely, when removing an arrow from storage, the pebble counter of every cell within the probing sequence is decremented.
With the pebble counters in place, it becomes possible to determine when to continue probing for stored objects —specifically, as long as the pebble counter is greater than zero— even if the cell itself has been emptied.
Every arrow is self indexed, as its definition is hashed to determine an open address within the storage space.
In addition, an arrow is indexed by its tail and head.
For this purpose, back-references are stored at expected locations related to the arrow ends.
These back-references form an index of all child arrows related to a given arrow.
Note these back-references are stored only once the arrow permanently saved to mass storage. A transient arrow may not be indexed.
Arrows back-references are stored in dedicated cells found by shifting the parent address by a children offset. A same “children” cell may actually store unrelated back-references. Wrong back-references are filtered out by checking refered arrows. As there is no need to chain children segments in an unambigous way, there is no “jumper” field involved. Children list also don’t involve “pebble” counters. However a reference counter is stored in the parent arrow definition so that the search will proceed until all children are found.
note one distinguishes outgoing from incoming back-references. Does it actually worth it?
Binary strings, ranging from 12 up to 99 bytes in length, are stored directly into cells. This includes Blob footprints as well.
To facilitate deduplication, binary strings are prefixed with a checksum. This checksum alone doesn’t guarantee identification so the entire string needs to be compared when resolving an atom.
Binary strings are divided into segments and distributed accross multiple cells, each separated by a deterministic offset, similar to the probing process in open addressing. However contrarly to cells visited while probing, string segment cells must be unambigously linked together to prevent unrelated data inclusion.
A collision resolution technique named Coalesced hashing consists in chaining hash-conflicting keys from the original slot thanks to explicit pointers (indices).
The Arrow Space code uses a comparable technique but for cells that need to be unambiguously linked together. These cells are referred to as chained cells and are used for binary strings storage.
Within a cell sequence, chained cells are connected by jumper counters, which allow for jumping over unwanted data from one cell to the next in the chain.
However, a jumper is not a fully qualified address but an offset multiplier, making it much more space-efficient. It indicates the number of shifts required in the probing sequence to reach the next relevant cell.
A jumper as introduced above is a short-sized data. Its maximal value is low. The probability of many repeated consecutive hash-collisions is supposed to be even lower, as explained latter.
If the number of shifts up to the next cell overflows the jumper definition range, one puts a special reattachment point into the next cell. This allows to unambiguously finds latter the location where the chain resumes when retrieving back the list.
For each arrow, one stores in the main space:
In addition, one stores blob bodies as dedicated files next to the main persistence file.
One makes use of an hash function to compute an arrow’s open address out of its definition.
The hash function depends on the arrow type.
In summary:
_h_(Tag) = checksum(Tag)_h_(Pair) = combine(h(tail(Pair)), h(head(Pair)))_h_(Blob) = footprint(Blob)Please note the hash function for a regular arrow is based on its parents’ open addresses rather than their actual cell adresses. It allows to compute the hash of a given arrow without resolving the actual addresses of all its intermediary ancestors.
When storing a new arrow and upon a location conflict, One could decide to look for a free cell immediately following a conflicting cell. But this naive linear probing would rapidly lead to data cluttering.
A better way to probe for a free cell or an existing key is to shift from the default location by a variable offset computed by a second hash function. This reduces the risk of aligning occupied cells together in the same probing sequence. This additional strategy is called double hashing.
When putting an arrow into the storage space, one computes a big hash code h as described above, then one truncates the hash code modulo 2 twin prim numbers P0 and P1.
2012 note: the actual prototype also features triangular grow of the offset as probing goes.
Binary strings divided into segments stored among the arrow space.
One could fill up consecutive cells to store all the segments of the binary string. But this naive approach would lead to data cluttering.
A better approach consists in separating data slices by an offset which differs depending on the data so to minimize cluttering. This is comparable with Double Hashing when probing.
OUTDATED DOCUMENTATION. See actual code.
Address are 4 byte length. So are hash codes.
P0 and P1 are twin prim numbers just above 2^32 (address space size).
The actual memory size is P0. It’s the greatest prime under 2^32.
Here are the hash functions currently used by the prototype.
h(a) = P1 + (tail << 20) + (head << 4) + tail + head (64 bits)checksum(SHA-2(blob)) (the SHA footprint is stored as a tag)h(tag) = checksum(tag) 64 bits checksum à la http://www.cse.yorku.ca/~oz/hash.html((size << 24) + ((buffer[1] ^ buffer[5] ^ buffer[9]) << 16) + ((buffer[2] ^ buffer[6] ^ buffer[10]) << 8) + buffer[3] ^ buffer[7] ^ buffer[11]) with buffer right-padded with size filling bytes
With the 64bits hash result, one deduces the following values.
h & 0xFFFFFFFFU (h truncated to 32bits)h % P0h % P1 (if 0 => 1)invert_bytes(arrow hash) ^ data[0..3] ^ data[4..7]invert_bytes(arrow hash) (or string chaining offset for strings)This is the 24 bytes cell structure and 4 bytes address model used by the actual source code.
* Memory device
*
* -------+------+------+------+-------
* ... | cell | cell | cell | ...
* -------+------+------+------+-------
*
* Cell structure (24 bytes).
*
* +---------------------------------------+---+---+
* | data | T | P |
* +---------------------------------------+---+---+
* 22 1 1
*
* P: Pebble counter (1 byte)
* T: Cell content type (1 byte)
* Data: Cell payload (22 bytes)
*
*
The cell content byte identifies the type of content in a cell:
* +---------------------------------------------------+
* | junk |
* +---------------------------------------------------+
* 22 bytes
* T = 1, 2, 3, 4: arrow definition.
* +--------+----------------------+-----------+----------+----+----+
* | hash | full or partial def | RWC0dWnCn | Child0 | cr | dr |
* +--------+----------------------+-----------+----------+----+----+
* 4 8 4 4 1 1
* where RWC0dWnCn = R|W|C0d|Wn|Cn
*
* R = root flag (1 bit)
* W = weak flag (1 bit)
* C0d = child0 direction (1 bit)
* Wn = Weak children count (14 bits)
* Cn = True children count (15 bits)
*
* child0 = 1st child of this arrow
* cr = children revision
* dr = definition revision
root flag The root flag as a mutable bit
children counters A reference counter is added to every arrow definition. To retrieve all the arrow’s children, one look at all the children cells in the child offset based sequence of cells starting from the parent address.
child0 An arrow definition relates with a list of children. child0 is the younger child (the last assimilated child arrow). The other older children are listed into individual segments stored in separate cells separated by a children offset.
* +--------+--------+--------+-----------+----------+----+----+
* | hash | tail | head | RWC0dWnCn | Child0 | cr | dr |
* +--------+--------+--------+-----------+----------+----+----+
* 4 4 4 4 4 1 1
* +---+-------+-------------------+-----------+----------+----+----+
* | s | hash3 | data | RWC0dWnCn | Child0 | cr | dr |
* +---+-------+-------------------+-----------+----------+----+----+
* 1 3 8
* |<---hash-->|
*
```text
* _size_ (s) : data size, 11 bytes or less.
* _hash3_ = `(data 1st word ^ 2d word ^ 3d word) & 0xFFFFFFu`
* _size_ and _hash3_ forms a 4-bytes hash to filter false candidate when probing
* When size > 8, one retrieve 3 extra bytes of data by computing `(hash ^ 1st word ^ 2d word) & 0xFFFFFFu`
### Tag (T=3) And Blob Footprint (T=4)
```test
* +--------+------------+----+-----------+----------+----+----+
* | hash | slice0 | J0 | RWC0dWnCn | Child0 | cr | dr |
* +--------+------------+----+-----------+----------+----+----+
* 4 7 1
* J = first jumper (1 byte)
jumper The “jumper” is an offset multiplier to jump over unwanted content between two consecutive cells within a chain. Jumpers link segments together without mixing them with unrelated content.
Supposing the offset constant while probing, the next segment of the string is located at (adress + (jumper + 1) * offset) % memory_size. However the actual prototype make the offset grows linearly as the probing process goes. So the actual formula is different.
* +-----------------------------------------+---+
* | data | J |
* +-----------------------------------------+---+
* 21 1
This segment may belong to a blob footprint or a tag.
* T = 6: last segment of a binary string
* +-----------------------------------------+---+
* | data | s |
* +-----------------------------------------+---+
* 21 1
* s = segment size
* +--------+--------+--------------+
* | from | to | ... junk ... |
* +--------+--------+--------------+
* 4 4
This cell content doesn’t contain any definition data. It only reattaches the “from” segment, whom jumper field reached its max value, with the segment at the “to” address.
* +------+------+------+------+------+---+---+
* | C4 | C3 | C2 | C1 | C0 | t | d |
* +------+------+------+------+------+---+---+
* 4 4 4 4 4 1 1
* Ci : Child or list terminator
* (list terminator = parent address with flag)
* t: terminators (1 byte with 5 terminator bits).
* d: directions (1 byte with 5 flags: 0 incoming/1 outgoing)
Note that a children cell can gather children of unrelated arrows.
The AS features a garbage collection process which spares rooted arrows and all their “ancestors” and gets back resources used by unrooted and unreferred arrows.
When an arrow is not rooted and has no rooted descendants, one may recycle the cells used to store its saved definition.
The GC proceeds to-be-deleted arrows in an incremental way. Its job is dispatched on many transactions to avoid CPU overhead. Since arrows are not deleted immediately, they may be saved from deletion by being rooted or linked back. An additional check of deletion criteria is performed just before the actual deletion.
note: In the actual code, the GC is never delayed. It is performed between every micro-transaction and cleans all reclaimable space.
Additional back-references should also be stored for quick retrieval of rooted structured arrows. For example, they may be used to quickly fetch contextualised arrows like (C0 -> (C1 -> (... -> (Cn -> * )))) (all the arrows in the nested hierarchy of context {C0:{C1:...{Cn:{*}}...}}).
A proposal is to index every arrow by its flatten definition, or by some parts of its flatten definition like: