This page needs house cleaning since the last migration to a new data model
This page describes the ArrowsSpace design as it takes place in the current Entrelacs System prototype.
The bottom software layer consists in a thread-safe C library (EntrelacsLibrary) which provides:
The Entrelacs server on top of this library allows clients to simultaneously and remotely access the Arrow Space via HTTP.
The prototype also allows to handle several types of complex objects in addition with regular arrows. That is:
Despite blobs, tags and smalls being raw binary objects, they are still handled like their equivalent arrow constructs, namely entrelacs (discrete reentrant structures of arrows). Tuples are also managed as they were arrows structures. So we indifferently use the “arrow” term herein to designate these objects as well.
The persistence file is operated as a bank of storage units called cells.
One cell :
Basically, as a regular arrow is a pair of arrows, it is stored as a pair of addresses within a single cell.
For each arrow a, one also stores 2 back-references attached to its ends -head and tail- definition, that is:
These back-references form an index to browse all children arrows of a given arrow.
See what “next to” expression means hereafter.
One relays on OpenAddressing to manage conflicts within the storage space.
An issue with Open Addressing is that one can’t empty out a cell without breaking one or several sequences of busy cells up to relevant content.
The current prototype chose to manage a dedicated “more” counter attached to every cell. One increments this counter for every cell that one’s visited from the default location up to the actual location of an added object. These counters are comparably decremented upon object removal.
Thanks to “more” counters, one knows when one must keep on probing (“more” counter greater than zero).
Blob signatures and tags are also stored into cells like regular arrows. But such an object definition can’t fit into a single cell. It is taken into slices and dispatched into several cells separated by a predictable offset.
One also stores a checksum previous to the data string to accelerate singleton identification.
Cells used to store data slices needed to be chained together so to avoid mixing them up with unrelated cells. They are called “chained cells”.
Chained cells are also used to store “tuple” definitions and children lists.
Chained cells are chained together by “jumper”s which allows to jump over unwanted data from one cell up to the next in the chain.
One doesn’t need to store a fully qualified address to identify the next cell in a chain. One only needs to keep a short count of shifts until the next relevant cell. So a “jumper” is simply an offset multiplier stored as a short-sized counter in every chained cell but the last.
A jumper as introduced above is a short-sized data. Its max value is very low, but so is the probability of many repeated consecutive collisions with existing cells (see double hashing explanation bellow).
If however the number of shifts up to the next cell in a chain is so high that the jumper reaches its maximal value, one looks for the continuation of the chain by probing a special reattachment cell, that is a cell containing enough data to unambiguously identify the remaining of the interrupted chain.
For each arrow, one needs to store:
As different kinds of data may be found in a cell, one needs to identify a cell content by a few bit length value named “category” hereafter.
One makes use of an hash function to compute an arrow’s open address out of its definition.
The hash function is chosen after the type of arrow:
The overall hash based location function h consequently verifies :
When storing a new arrow and upon a location conflict, One could decide to look for a free cell immediately after a conflicting cell. But this naive approach would lead to data cluttering.
A better approach consists in shifting from the default used location by an offset which is different for each stored content in order to minimize cluttering. In other words, the offset is also computed by an hash function. This particular strategy is called DoubleHashing.
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 p1 and p2.
2012 note: the actual prototype also features quadratic probing. The offset grows as probing goes.
One could decide to reserve and fill up a set of consecutive cells to store several slices of a same arrow definition (blob, tag…). But this naive approach would lead to data cluttering.
A better approach consists in separating data slices by an offset which is different for each stored content in order to minimize cluttering even more. This strategy is a form of DoubleHashing strategy.
One uses different offset functions depending on whether one chains cells for children dispatching to avoid cluttering even more.
Some misc candidate offsets:
where H is the definition hashcode introduced above.
This is a 8 bytes cell proposal.
+---<category>
|
<more> A <--tail@------> <--head@------> <r><child0> : an arrow
<more> I <--data-----------------------> <r><child0> : a small
<more> S <--checksum------> <--jumper--> <r> <child0> : a tag
<more> B <--checksum------> <--jumper--> <r> <child0> : a blob
<more> T <--checksum------> <--jumper--> <r> <child0> : a tuple
<more> C <--end@-------> <--end@-------> <--jumper--> : 2 ends of a tuple
<more> L <--end@-------> <--end@-------> <size = 0/1> : Last ends of a tuple
(size = 0 ==> 1 end only)
<more> C <-----slice-------------------> <--jumper--> : data slice of a blob/tag
<more> L <-----slice-----> <--nothing--> <--size----> : last data slice of blob/tag
(last slice size stored in bytes)
<more> C <--child@-----> <--child@-----> <--jumper--> : 2 children references
<more> L <--child@-----> <--child@-----> <--unused--> : last 2 children references
Note: reference may be null if cell is half-full.
<more> C <--child@-----> <--next@-----> < MAX-JUMP > : Cell chain with overloaded jumper.
One address directly refers to the next cell in the chain.
<more> C ... < MAX-JUMP > : Chained cell with overloaded jumper
<more> X <--previous@--> <--next@-----> <--unused--> : Reattachment cell
The prototype is based upon a 8 bytes cell size.
The “more” counter of the Little Thumbling’s algorithm introduced above.
The category indicates the inner structure of a cell and give information about its content. Note C/L chained cells may store different kinds of data (arrow children, binary slices, tuple ends).
The “jumper” is an offset multiplier to jump over unwanted content between two consecutive cells within a chain. Jumpers link together C, L, S, B or T cells. The next cell in the sequence is located at
@cellR + ( jump + 1) * offsetNext.
2012 note: formula above doesn’t take into consideration quadratic probing in actual prototype
Every cell containing the beginning of an arrow/object definition is also the first cell of a “children cells chain”, a list of cells separated by a dedicated “children offset”. “child0” is is an offset multiplier (like jumpers) to jump over unrelated content up to the first real children cell. The beginning of the children list of an arrow at @parent is located at
@parent + children * offsetChildren(parent). Note that “children” to zero means the arrow has no child.
The root flag as a mutable bit
L cells may be partially full. The size field allows to ignore a stuffing value.
Finally, here is the ideal (no conflict) footprint of an arrow a (its ID and also its address). a goes out a tail arrow and comes into an head arrow (two other addresses). a is also referred by several incoming or outgoing children.
| To be done | |:———–|
When needed, arrows climb up to a level 1 (RAM) memory device. This memory is used as a fine-grained cache of level 0 cells. See ArrowsCache for further details.
The AS features a garbage collection process which spares rooted arrows and all their “ancestors” and gets back resources used by no more rooted nor referred arrows.
When both an arrow is non-rooted and has no child, one can recycle its storage resources.
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.
2012 note: not incremental yet. GC is performed at the beginning of each commit.
P0 and P1 are twin prim numbers just above 2 ^ 24 (address space size).
Here are the hash functions currently used by the prototype.
To be confirmed. See actual code.