Block placement (Layouts) discussion

[Bulat-Ziganshin]

Continuation of #85 and part of #70 efforts.

If we use ECC with K+M encoding (K data blocks and M parity blocks in each EC group), a dataset contains S*K data blocks and S*M parity blocks. Here we discuss various ways to distribute them over N nodes and currently we support (and discuss here) only the N=K+M case.

Note that the block order of the original data has special meaning - it's the typical retrieval order (in particular, currently we support only sequential download of the entire dataset). For simplicity, we extend dataset with empty blocks to the nearest S*K blocks size. OTOH, parity block order isn't important and we can choose it arbitrarily.

Layout is defined by two functions providing mapping of:

• node number to indexes of data and parity blocks it should store (used by contract to fill slots)
• EC group number to indexes of data and parity blocks it includes (used by uploader to construct ECC, used by downloader to recover data)

We have the following requirements to Layouts, in order of decreasing importance:

• each EC group is distributed over all nodes (in order to maximize reliability)
• (almost) each EC group contains adjacent data blocks, i.e. blocks i+1..., i+K (in order to maximize ECC recovery performance)
• simple calculation of the functions describing Layout

Extra requirement that will allow us to develop extensible contracts:

• Layout functions should still work when extra data blocks (and corresponding parity blocks) are added to the dataset

[Bulat-Ziganshin]

Layout 1 ("horizontal"):

• First S data blocks are placed on the first node, the next S blocks on the second node, and so on. Then, the first S parity blocks are placed on the node K+1 .... last S parity blocks are placed on the node K+M.
• The first EC group includes the first block placed on each node, the second EC group includes the second block placed on each node, and so on.

Layout 2 ("vertical"):

• First K data blocks are distributed over the first K nodes, next K data blocks are distributed again over the same nodes, and so on. Then, the first M parity blocks are distributed over the last M nodes, the next M parity blocks are distributed again over the same nodes, and so on.
• The first EC group includes the first K data blocks and the first M parity blocks, the second EC group contains the next K data blocks and the next M parity blocks, and so on. Actually, it can be described exactly like the first layout - the first EC group is made from first block placed to each node, and so on.

Layout 2R ("vertical rotated"):

• like Layout 2, but nodes in each EC group are rotated in order to spread parity blocks among all nodes (in order to evenly distribute load and improve download performance)

Layout 1R is also possible.