65 Legacy Seid encoding
Status: historical. This chapter records the legacy base-255 Seid encoding.
The Recoverable Packet Map (RPM) is a persistent 8 level hierarchical map used to locate the latest versions of recoverable packets given the Seid. These 8 levels correspond to the 8 bytes in a 64 bit Seid. There is one RPM for the LSS.
Each RPM-node in the search tree stores an array of 255 LogRecordPosition, using an index in the range [1,255]. The storage space required is at most 255 x 8 ~ 2k bytes. The levels are labelled from 0 to 7 where 0 is at the "bottom" and 7 is at the "top" of the search tree. There is exactly one RPM-node at level 7. This node is stored in the root block of the LSS. All the other RPM-nodes are stored in the log as indivisible (packet) log records (indivisible means that the RPM-node can't be broken up into a chain of packets, as done for serial elements).
The level 7 RPM-node in the root block stores the current locations of the RPM-nodes at level 6. The RPM-nodes at level 6 store the current locations of the RPM-nodes at level 5. This continues until we get to the RPM-nodes at level 0. These store the current locations of the packets that contain actual data.
Seid allocations involve incrementing the next Seidlow or Seidhigh, so that RPM-nodes are filled in an ordered manner at level 0 (for Seidlow) or level 4 (for Seidhigh). When a level 0 RPM-node is filled, we create a new level 0 RPM-node under the parent (level 1) RPM-node. If this level 1 RPM-node is full then we create a new level 1 RPM-node under the parent (level 2) RPM-node. This "create RPM-node on overflow" concept continues up through the levels, and relates to counting in base 255. Therefore the fan-out at a given node will often be much less than 255. When an RPM-node is serialised to disk, only the portion of the array of LogRecordPosition that is in use is written to the archive.
There are two types of packets
- Data packets
- RPM packets
Seids to identity RPM packets
Let b3.b2.b1.b0 represent a 32 bit value made of bytes bi, where b3 is the most significant byte. On little endian (such as x86) architectures, b3 has the highest memory address.
Let a Seid have Seidhigh = c6.c5.c4.c3 and Seidlow = c2.c1.c0.p. Let p > 0, c0 > 0, ... c6 > 0
The Seid space is reserved as follows
SeidHigh SeidLow
------------------------------------------------------
Null Seid 0 . 0. 0. 0 0. 0. 0. 0
Level 6 RPM packet c6. 0. 0. 0 0. 0. 0. 0
Level 5 RPM packet c6.c5. 0. 0 0. 0. 0. 0
Level 4 RPM packet c6.c5.c4. 0 0. 0. 0. 0
Level 3 RPM packet c6.c5.c4.c3 0 .0. 0. 0
Level 2 RPM packet c6.c5.c4.c3 c2. 0. 0. 0
Level 1 RPM packet c6.c5.c4.c3 c2.c1. 0. 0
Level 0 RPM packet c6.c5.c4.c3 c2.c1.c0. 0
Data packet c6.c5.c4.c3 c2.c1.c0. p
<----------------------- increasing memory addresses
Number data packets supported = 255^8 ~ 1.788e+19
Note that we don't have the option of reversing the meaning of the bytes because incrementing SeidLow needs to step through p values first.
Accessing the bytes in the required order
Let a 32 bit integer be written as a.b.c.d where a is the most significant byte and d is the least significant byte.
The following code can be used to extract the bytes from 32 bit integer v
d = v & 0xFF;
v >>= 8;
c = v & 0xFF;
v >>= 8;
b = v & 0xFF;
v >>= 8;
a = v & 0xFF;
Note that the bytes are obtained in the order from least significant to most significant. Unfortunately for the purposes of traversing down the RPM, we actually want to extract the most significant byte first.
The following retrieves the bytes in the required order:-
a = v >> 24;
b = (v >> 16) & 0xFF;
c = (v >> 8) & 0xFF;
d = v & 0xFF;
OR
c = v >> 8;
b = c >> 8;
a = b >> 8;
< use a >
b &= 0xFF;
< use b >
c &= 0xFF;
< use c >
d = v & 0xFF;
< use d >
OR
octet_t* p = ((octet_t*) &seid) + 7;
for (int i=0 ; i < 8 ; ++i)
{
int index = *p--;
}