owned this note
owned this note
Published
Linked with GitHub
## Overview
Let $F$ be a file with $b$ blocks. For given parameters $k$ and $m$, erasure coding proceeds as follows.
We begin by computing, from $b$ and $k$, the number $s = \lceil \frac{b}{k} \rceil$ of _encoding steps_. We then split the $b$ blocks of $F$ into $k$ buckets of $s$ blocks each (Figure 1). Since $b$ may not in general be divisible by $k$, we _pad_ $F$ with $b_e$ empty blocks such that $b_e + b$ is. We refer to this padded file as $F_r$, and its block count $b_r = b_e + b = s \times k$.
<center>
<image src="https://hackmd.io/_uploads/BydvPukI0.png" width="70%"/>
</center>
**Figure 1.** Splitting of blocks into step buckets.
The file is then extended with $m \times s$ parity blocks, where the input for each parity block depends on the indexing strategy.
## Code
Encoding parameters are computed from a Manifest as follows:
```nim=
proc init*(
_: type EncodingParams,
manifest: Manifest,
ecK: Natural, ecM: Natural,
strategy: StrategyType): ?!EncodingParams =
if ecK > manifest.blocksCount:
return failure(
"Unable to encode manifest, not enough blocks, ecK = " &
$ecK &
", blocksCount = " &
$manifest.blocksCount)
let
rounded = roundUp(manifest.blocksCount, ecK)
steps = divUp(rounded, ecK)
blocksCount = rounded + (steps * ecM)
success EncodingParams(
ecK: ecK,
ecM: ecM,
rounded: rounded,
steps: steps,
blocksCount: blocksCount,
strategy: strategy
)
```
this uses somewhat funny math to compute $\lceil b/k \rceil$:
```nim=
func divUp*[T: SomeInteger](a, b : T): T =
## Division with result rounded up (rather than truncated as in 'div')
assert(b != T(0))
if a == T(0): T(0) else: ((a - T(1)) div b) + T(1)
func roundUp*[T](a, b : T): T =
## Round up 'a' to the next value divisible by 'b'
divUp(a, b) * b
```
it basically says that, for $a \neq 0$, we have that:
$$
\left\lfloor \frac{a - 1}{b} \right\rfloor + 1 = \left\lceil \frac{a}{b}\right\rceil
$$
this can be seen to hold if $a$ is divisible by $b$: if $q = a/b$, then $\left\lfloor \frac{a - 1}{b} \right\rfloor = q - 1$ and $q - 1 + 1 = q = \left\lfloor \frac{a}{b}\right\rfloor = \left\lceil \frac{a}{b}\right\rceil$. If $0 < a < b$ it is also trivially true. If $0 < b < a$ and $a$ is not divisible by $b$, on the other hand:
$$
\left\lfloor \frac{a - 1}{b} \right\rfloor + 1 = \left\lfloor \frac{(qb + r)- 1}{b} \right\rfloor + 1
$$
where $1 \leq r < b$ and $\lceil a/b \rceil = q + 1$. Taking the expression above, we see that:
$$
\left\lfloor \frac{qb + (r - 1)}{b} \right\rfloor + 1= \left\lfloor q + \frac{(r - 1)}{b} \right\rfloor + 1= q + 1
$$
since $1 \leq r < b$ and hence $(r - 1) / b < 1$. $_{\blacksquare}$
In the code above, we have the following mapping for the `EncodingParams`:
* ecK $= k$;
* ecM $= m$;
* steps $= s = \lceil \frac{b}{k} \rceil$;
* rounded $= b_r = s \times k$;
* blocksCount $= b_r + b_p$ (includes empty and parity blocks).
Note that this can be confusing, as `Manifest` also has a `blocksCount` attribute, but in the non-encoded manifest this refers to $b$ and not $b_r + b_p$. This is because `blocksCount` is calculated from `datasetSize`:
```nim=
func blocksCount*(self: Manifest): int =
divUp(self.datasetSize.int, self.blockSize.int)
```
and `datasetSize` does get updated when we create the encoded `Manifest`:
```nim=
let encodedManifest = Manifest.new(
manifest = manifest,
treeCid = treeCid,
datasetSize = (manifest.blockSize.int * params.blocksCount).NBytes,
ecK = params.ecK,
ecM = params.ecM,
strategy = params.strategy
)
```
The encoded manifest does keep track of the original dataset size under the `originalDatasetSize` attribute. I would argue that for consistency and to avoid confusion, having an `originalBlocksCount` akin to `blocksCount` but which operates on `originalDatasetSize` would go a long way.
**Mapping from API requests.** API requests specify parameters `nodes` and `tolerance`. Nodes is the total number of `nodes`, and `tolerance` the maximum number of nodes we are willing to see failing before we lose any data. Considering the above, it should be clear that:
* $k$ = `nodes` $-$ `tolerance`;
* $m$ = `tolerance`.
## Explaining the Numbers in The EC Decoding Test
For the EC decoding test I am using [Eric's integration test]() with a version of the King James' Bible truncated to $262\,144$ bytes. Using a plain text file helps distinguish actual content from gibberish in output, and it makes it easy to search, say, for the end of the file and visually checking that all the content is there.
I am getting a file with $786\,432$ bytes back from the API, or about $3$ times the size of the original file. This contains the original text plus gibberish which amounts to $2$ times the original file.
We make an API call with settings `nodes = 3` and `tolerance = 1`, which means $k = 2$ and $m = 1$.
We are using the default block size, which is set to:
```nim=
DefaultBlockSize* = NBytes 1024*64 # 65536
```
This means our file has _exactly_ 4 blocks. Since $k = 2$, this means we should have:
* $2$ encoding steps;
* no padding (no extra empty blocks);
* $2$ parity blocks of size $65\,536$.
The total expected size for the encoded file, therefore, is $6$ blocks.
The fact that we get an output of size $786\,432$ is therefore rather puzzling: this amounts to $12$ blocks, of which the first $4$ are the content of the file -- which we can confirm by inspecting the output -- and the next $8$ are jumbled gibberish.
Since Leopard will not even allow coding rates below $0.5$, we know those cannot be all parity bits, unless padding is broken.
### Encoding
Analysing instrumentation output from Codex, we get:
```text=
-------------------- ENCODING ------------------------
* ecM is: 1
* ecK is: 2
* Steps are: 2
* Original blocks are: 4
* Rounded blocks are: 4
* Total blocks are: 6
INTERLEAVING STEP (0)
* Blocks resolved: 2
* Padding blocks added: 0
DONE INTERLEAVING STEP (0)
TRC 2024-06-19 11:26:18.327-03:00 Erasure coding data
TRC 2024-06-19 11:26:18.336-03:00 Adding parity block
INTERLEAVING STEP (1)
* Blocks resolved: 2
* Padding blocks added: 0
DONE INTERLEAVING STEP (1)
TRC 2024-06-19 11:26:18.343-03:00 Erasure coding data
TRC 2024-06-19 11:26:18.344-03:00 Adding parity block
* added a total of parity blocks: 2
* treeCid is: zDzSvJTfAh9dU5pnpYpULXAzfsonLZ9iJMNzEBXT2Uw25g6JVbwP
* original manifest blocksCount is: 4
* manifest blocksCount is: 6
* manifest blockSize is:65536'NByte
* manifest datasetSize is: 393216'NByte
* manifest original dataset size is: 262144'NByte
TRC 2024-06-19 11:26:18.351-03:00 Encoded data successfully topics="codex erasure" tid=107940 treeCid=zDz*6JVbwP blocksCount=6 steps=2 ecK=2 rounded_blocks=4 ecM=1
-------------------- ENCODING DONE ------------------------
```
These top-level numbers seem roughly correct - the size of the new dataset is correct, as is $b_r$ (4), the number of steps (2), parity blocks (2), and empty padding blocks (0).
### Decoding
Decoding has a similar yet slightly more complex structure than encoding. `prepareDecodingData` shows the code for a decoding step, which fetches blocks and arranges their content into an array of arrays. Each inner array should contain the contents of a block, or be empty if the block is missing. Missing arrays will be later interpreted as erasures by Leopard.
Since this produces the input for a single decoding interleaved step, output arrays have size $k$ (`data`) and $m$ (`parity`), and the total number of non-empty inner arrays for decoding to succeed should be $\geq k$. In case it is not, decoding will fail and an error will be generated at a later step.
```nim=
proc prepareDecodingData(
self: Erasure,
encoded: Manifest,
step: Natural,
data: ref seq[seq[byte]],
parityData: ref seq[seq[byte]],
cids: ref seq[Cid],
emptyBlock: seq[byte]): Future[?!(Natural, Natural)] {.async.} =
## Prepare data for decoding
## `encoded` - the encoded manifest
## `step` - the current step
## `data` - the data to be prepared
## `parityData` - the parityData to be prepared
## `cids` - cids of prepared data
## `emptyBlock` - the empty block to be used for padding
##
let
strategy = encoded.protectedStrategy.init(
firstIndex = 0,
lastIndex = encoded.blocksCount - 1,
iterations = encoded.steps
)
indicies = toSeq(strategy.getIndicies(step))
pendingBlocksIter = self.getPendingBlocks(encoded, indicies)
var
dataPieces = 0
parityPieces = 0
resolved = 0
for fut in pendingBlocksIter:
# Continue to receive blocks until we have just enough for decoding
# or no more blocks can arrive
if resolved >= encoded.ecK:
break
let (blkOrErr, idx) = await fut
without blk =? blkOrErr, err:
trace "Failed retreiving a block", idx, treeCid = encoded.treeCid, msg = err.msg
continue
let
pos = indexToPos(encoded.steps, idx, step)
logScope:
cid = blk.cid
idx = idx
pos = pos
step = step
empty = blk.isEmpty
cids[idx] = blk.cid
if idx >= encoded.rounded and pos >= encoded.ecK:
trace "Retrieved parity block"
shallowCopy(parityData[pos - encoded.ecK], if blk.isEmpty: emptyBlock else: blk.data)
parityPieces.inc
else:
trace "Retrieved data block"
shallowCopy(data[pos], if blk.isEmpty: emptyBlock else: blk.data)
dataPieces.inc
resolved.inc
return success (dataPieces.Natural, parityPieces.Natural)
```
The code above initializes the indexing strategy with `blocksCount` and `steps`, which we know to be computed correctly in encoding: this will provide us with the block mapping for this interleaving step.
It then issues an async fetch for all required blocks, and processes those as they arrive in the main for loop (lines $31$ - $62$). It will stop immediately once enough ($k$) blocks have been fetched (line $34$), effectively trading IO for CPU.
Line $37$ processes a block retrieval. `idx` represents the position of the block into the overall file, and should be a number between $0$ and $b_r + b_e + b_p$. In the case of our file, this should be a value between $0$ and $5$.
Line $43$ then performs a key transformation which is extracting the reverse mapping for the interleaving. One key aspect of this transformation is that it _does not work for any interleaving strategy_.
The stepping strategy maps index $0 \leq j < s$ at step $0 \leq i < k$ into the $i^{th}$ element of the $j^{th}$ $s$-sized bucket (Figure 1). If we let $l$ be the mapped index, we get:
$$
\begin{equation}
i + j\times s = l \iff j = \frac{l - i}{s} \label{eq:stepped} \tag{1}
\end{equation}
$$
where the equation for $j$ is the reverse mapping. Not surprisingly, the mapping strategy in `indexToPos` is defined as:
```nim=
func indexToPos(steps, idx, step: int): int {.inline.} =
## Convert an index to a position in the encoded
## dataset
## `idx` - the index to convert
## `step` - the current step
## `pos` - the position in the encoded dataset
##
(idx - step) div steps
```
One implication of this is that the only interleaving strategy that currently will work with the EC module is the stepped strategy.
In that same vein, the `decode` function also has one bit which will only work with the stepped strategy:
```nim=
for i in 0..<encoded.ecK:
let idx = i * encoded.steps + step
if data[i].len <= 0 and not cids[idx].isEmpty:
without blk =? bt.Block.new(recovered[i]), error:
trace "Unable to create block!", exc = error.msg
return failure(error)
trace "Recovered block", cid = blk.cid, index = i
if isErr (await self.store.putBlock(blk)):
trace "Unable to store block!", cid = blk.cid
return failure("Unable to store block!")
cids[idx] = blk.cid
recoveredIndices.add(idx)
```
This scans through the data blocks fed into the current step and checks that there are matching recovery blocks in the `recovered` array. Note that the index mapping that is used in line $2$ to pick the blocks that took part in step $i$ is exactly the same formula we had deduced in Eq. $\eqref{eq:stepped}$.
Google Drive
Gist
Clipboard
Sign in with Wallet
