In ZFS RAID 6 implementation, why certain shifts are ⊕, but not the others?

Question

ZFS is a computer filesystem, which has an implementation of the RAID 6. I understand the simplified example of the RAID 6 implementation in Wikipedia, which each data chunk D is bit-shifted by a different amount.

In ZFS RAID 6 (aka RAID-Z2) implementation (summarised in a developer blog post, the algorithm is based on H. Peter Anvin's paper, as well as the comment in source code), y₀ through y₇, which are multiplications by 2, means shifting of bits in binary.

However what I do not understand is, why y₂, y₃, and y₄ are particularly ⊕ (exclusive-or) by x₇, while the rest five do not?

Answer 1

After study for a few more times, I understand a bit more. Simply say, why certain shifts are exclusive-or while the rest do not? This is the carefully chosen linear feedback shift register algorithm.

Quote from the Wikipedia:

General parity system

It is possible to support a far greater number of drives by choosing the parity function more carefully. ...

The effect of g i {\displaystyle g^{i}} g^{i} can be thought of as the action of a carefully chosen linear feedback shift register on the data chunk.[30] Unlike the bit shift in the simplified example, which could only be applied k {\displaystyle k} k times before the encoding began to repeat, applying the operator g {\displaystyle g} g multiple times is guaranteed to produce m = 2 k − 1 {\displaystyle m=2^{k}-1} {\displaystyle m=2^{k}-1} unique invertible functions, which will allow a chunk length of k {\displaystyle k} k to support up to 2 k − 1 {\displaystyle 2^{k}-1} 2^{k}-1 data pieces.

With a carefully chosen LFSR algorithm, among k-bits, it allows us to produce far more than k unique deviations.

Back to the H. Peter Anvin's paper, the x's in the paper are bits (of a byte) while shifting and XOR 0001 1100 (of x₇) produces the next shifted byte. From point 6 through point 12 should be proving that this shifting and XOR 0001 1100 algorithm would produce 255 unique deviations. (For this part I do not understand well about its proof as Mathematics is not my expertise. Should anyone could explain this would compose a better answer than mine.)

This is cross verified by the ZFS RAID source code.

In C, multiplying by 2 is therefore ((a << 1) ^ ((a & 0x80) ? 0x1d : 0)).

a is a byte. It is shifted and XOR 0001 1100, i.e. 0x1d (of x₇), to produce the next byte.

We provide a mechanism to perform the field multiplication operation on a * 64-bit value all at once rather than a byte at a time. This works by * creating a mask from the top bit in each byte and using that to * conditionally apply the XOR of 0x1d.

However neither VDEV_RAIDZ_MUL_2(x) nor VDEV_RAIDZ_MUL_4(x) is used in the source code. Instead it uses a less trivial VDEV_RAIDZ_64MUL_2. This would require further calculation to prove and understand this part. Yet this might be a scope of programming more than mathematics.