「探秘」Jerasure那些事

libJerasure

2007 James给出了RS-RAID一个开源实现。officialgithub,目前的版本是2014年发行的2.0版本,是各种纠删码库的开山之作。

Jerasure库包括以下5个模块:

  • galois.h/.c提供伽罗华域的算术运算。
  • jerasure.h/.c提供了绝大部分的核心函数。包括矩阵的编解码,位矩阵变换,矩阵转置和位矩阵转置。
  • reedsol.h/.c支持RS编解码和优化和的RS码。
  • cauchy.h/.c 支持cauchy RS编解码和最优cauchy编码。
  • cauchy_best_r6.h/.c 基于cauchy矩阵的RAID-6优化。
  • liberation.h/.c 支持Liberartion RAID-6编码, Blaum-Roth 编码,和Liber8tion RAID-6编码。 Liberation是一种低密度MDS。这三种编码采用位矩阵来实现,其性能远优于现有的RS和EVENNODD,在某种情况下也优于目前已知的最好的RDP编码。

下标汇总了Jerasure-2.0库常见的参数和其含义:

参数名 数据类型 含义
k int 数据盘个数
m int 校验盘个数
w int 字长
packetsize int 包大小(必须是sizeof(long)的整数倍)
size int 每个设备要编码/解码的字节总数。 这必须是sizeof(long)的倍数。 如果使用位矩阵,则它必须是packetssize * w的倍数。 如果希望对不符合这些限制的数据块进行编码,则必须用零填充数据块,以便满足这些限制。
matrix int * 这是一个具有k * m个元素的数组,表示编码矩阵-即分布矩阵的最后m行。 它的元素必须在0到$2^w -1$之间。第i行和第j列中的元素在`matrix [i * k + j]中。
bitmatrix int * 这是$w \cdot m \cdot w \cdot k$元素的数组,组成二进制分配矩阵BDM的最后$wm$行。 第i行和第j列中的元素位于bitmatrix [i * k * w + j]
dataptrs char ** 这是k个指针数组,指向大小为字节的编码数据。 其中每一个必须是长字对齐的。
coding_ptrs char ** 这是m个指针数组,指向大小为字节的编码数据。 其中每一个必须是长字对齐的。
erasures int * 这是一组ID已删除的设备。 如第4.1节所述,Id是介于0到k + m-1之间的数字。 如果擦除数为$e$,则擦除的元素$0$到$e -1$标识被擦除的设备,并且erasures [e]必须等于-1。
erased int * 这是指定擦除的替代方法。 它是一个$k + m$的元素数组。 数组的元素$i$代表ID为$i$的设备。 如果erased[i]等于0,则设备i正在工作;如果等于1,则其被擦除。
schdule int ** 这是一个5元素整数数组,用于优化位矩阵的编码计算。 如果计划中有o个操作,则计划必须至少包含o + 1个元素,并且schedule [o][0]应当等于-1。
cache int * 三维数组,用于保存一系列缓存地址,用于对RAID6解码进行优化。
row_k_ones bool 布尔类型,用于对满足$m>1$的解码过程进行优化。解码时,如果对应编码矩阵第一行全部为1或者对应的二进制编码矩阵前w行构成k个单位矩阵,则设置此标志位有助于提升解码速度。
decoding_matrix int * 这是用于解码的$k×k$矩阵或$wk×wk$位矩阵。 它是通过使用分布矩阵的相关行并将其求逆而构造的矩阵。
dm_ids int * 一维数组,用于指定仍然正常的磁盘编号,帮助生成解码矩阵。

针对RAID-6,Jerasure作了两类优化:

  • 对乘2运算进行优化

  • 直接对编码矩阵进行改造,得到最小密度RAID6. 这类矩阵很稀疏,计算量较少。目前有三种

    • Liberation: 要求W必须是素数
    • Blaum-Roth: 要求W+1必须是素数
    • Lber8tion: 要求W必须等于8

    这三种编码效率相当。

在安装jerasure库之前,我们得安装GF-Complete库,注意如果根目录下没有./configure,我们可以先运行./configure.ac

关于安装jerasure库的一些步骤和经验可以看这篇非常好的博客

make完成后/usr/local/lib下应该有这些库。

libgf_complete.a   libgf_complete.so.1      libJerasure.so        python3.8
libgf_complete.la  libgf_complete.so.1.0.0  libJerasure.so.2
libgf_complete.so  libJerasure.la           libJerasure.so.2.0.0

自己写的代码在编译时需指定动态链接库:

gcc hello.c -lJerasure -lgf_complete -o hello

库默认安装在/usr/local/lib,否则你需要用-L {path}指定库文件目录。


$\S1.1 $ Galois域算术运算

库:galois.h\galois.c

  • galois_single_multiply(int a, int b, int w) 以及galois_single_divide(int a ,int b, int w)

    在$GF(2^w)$上执行单元素的乘法和除法。

  • galois_region_xor(char *r1, char *r2, char *r3, int nbytes)

    此XOR对字节的两个区域r1r2进行求和,并将总和放入r3。 请注意,如果我们用总和替换区域之一,则r3可能等于r1或r2。
    Nbytes必须是机器长字大小的倍数。

  • galois_w08_region_multiply(char *region, int multby, int nbytes, char *r2, int add):

    这将整个字节区域乘以$GF(2^8)$中的常数multby。 如果r2为NULL,则区域将被覆盖。 否则,如果add为零,则将乘积放在r2中。 如果add不为零,则将乘积与r2中的字节进行异或。

  • galois_w16_region_multiply()galois_w32_region_multiply()与上述函数类似,分别对应$GF(2^{16})$和$GF(2^{32})$.
  • galois_change_technique(gf_t *gf, int w)

    这使您可以从GF-Complete创建自己的Galois Field算术的自定义实现。 为此,请参阅GF-Complete手册中的create_gf_from_argv()gf_init_hard()。 这些过程允许您创建gf_t,然后调用galois_change _technique()实现。

  • galois_init_field()glois_init_composite_field()

    会从GF-Complete创建gf_t指针。我们建议,使用create_gf_from_argv()gf_init_hard()代替。

  • galois_get_field_ptr(int w)

    返回一个目前jerasure使用中的指向gf_t的指针,针对指定的w。

1.1.1 内核操作

库:jerasure.c\jerasure.h

  • void jerasure_do_parity(k,data_ptrs, char *parity_ptr, size)

    这将从数据ptrs访问的k个内存区域中的每个区域计算数据大小字节的奇偶校验。 它将结果放入奇偶校验ptr指向的大小字节中。 像每个数据ptrs一样,奇偶校验ptr必须是长字对齐的,并且大小必须是sizeof(long)的倍数。

  • void jerasure_matrix_encode(k,m,w,bitmatrix,data_ptrs,coding_ptrs,size,packetsize)

    这使用位矩阵进行编码。 现在w可以是1到32之间的任何数字。

  • void jerasure_schedule_encode(k, m, w, schedule, data ptrs, coding ptrs, size, packetsize):

    此编码使用从jerasure_dumb_bitmatrix_to_schedule()jerasure_smart_bitmatrix_schedule()创建的调度进行编码。

1.1.2 解码操作

这些函数中的每一个都返回一个整数,如果成功则返回0,否则返回-1。 如果擦除太多,则解码可能会失败。

  • int jerasure_matrix_decode(k, m, w matrix, row_k_ones, erasures, data ptrs, coding ptrs, size)

此函数使用$GF(2^w)$中的矩阵进行解码。 通过创建解码矩阵并执行矩阵/矢量乘积,然后对所有已擦除的编码设备进行重新编码,可以完成此工作。 完成后,将丢弃解码矩阵。 如果要访问解码矩阵,则应使用下面的jerasure make decoding matrix()

  • int jerasure_bitmatrix_decode(k, m, w bitmatrix, row k ones, erasures, data ptrs, coding ptrs, size, pack)

etsize)

​ 注意,它不做任何调度-它只是创建解码位矩阵,并直接使用它来进行解码。 同样,完成后它会丢弃解码位矩阵。

  • int jerasure_schedule_decode_lazy(k, m, w bitmatrix, erasures, data ptrs, coding ptrs, size, packetsize, int

    smart)

    这是通过根据解码矩阵创建一个schedule并将其解码来进行解码的。 如果smart是1,则使用 bitmatrix来创建计划。 否则,将使用dumb bitmatrix。 请注意,没有使用变量row_k_ones,因为如果smart为1,则创建的schedule无论如何都会找到该优化。 此过程完成后,将释放计划和分配给解码的所有数据结构。

  • int jerasure_schedule_decode_cache(k, m, w cache, erasures, data ptrs, coding ptrs, size, packetsize)

    当m = 2时,使用schedule缓存进行解码。

  • int jerasure_make_decoding_matrix(k, m, w matrix, erased, decoding_matrix, dm_ids):

    创建解码矩阵。 请注意,解码矩阵和dm id均应分配并传递给此过程,以填充它们。解码矩阵应具有$k^2$个整数,而$dm_ids$应具有$k$整数。

  • int jerasure_make_decoding_bitmatrix(k, m, w matrix, erased, decoding_matrix, dm_ids)

​ 创建解码位矩阵。 同样,应同时定位解码矩阵和dm_id,并将其传递给此过程,以填充它们。此时间解码矩阵应具有$k^2w^2$整数,而$dm_id$仍具有$k$个整数。

  • int jerasure_erasures_to_erased(k, m, erasures)

    将上面定义的erasure规范转换为上面定义的erased规范。

1.1.3 点积操作

  • void jerasure_matrix_dotprod(k, w, int matrix_row, int src_ids, int dest_id, data_ptrs, coding_ptrs, size)

这将一行编码/解码矩阵乘以数据/幸存者。 源设备的ID(与矢量元素的ID相对应)位于src_id中。 目标设备的ID在目标ID中。 当矩阵中遇到一个1时,将执行正确的XOR /复制操作。

  • void jerasure bitmatrix dotprod(k, w, int bitmatrix row, int *src ids, int dest id, data ptrs, coding ptrs,size, packetsize)

这是位矩阵的类似过程。 它根据由bitmatrix行指定的矩阵的w行执行w点乘积。

  • void jerasure_do_scheduled_operations(char \ptrs, schedule, packetsize)**:

这将对ptrs指定的指针执行计划。 尽管未指定w,但它以w(packetsize)个字节执行调度。 假定ptrs是与计划匹配的正确大小。 通常,这是k + m。

1.1.4 基础矩阵操作

  • int jerasure_invert_matrix(int\ mat, int inv, int rows, int w)*

这求一个$rows\times rows$矩阵的逆,结果保存在inv中。如果矩阵不可逆,返回-1,否则返回0.

  • int jerasure_invert_bitmatrix(int mat, int inv, int rows):

这是求位矩阵的逆,对应$w=1$,也可以用上面那个函数,不过这个函数明显要快些。它会回收mat。

​ • int jerasure_invertible_matrix(int *mat, int rows, int w):

判断矩阵是否可逆,可逆返回1,否则返回0.

  • void jerasure print matrix(int* matrix, int rows, int cols, int w):

这个函数会打印矩阵。$w$是用来确定间距的。

  • int* jerasure matrix multiply(int m1, int m2, int r1, int c1, int r2, int c2, int w):

此函数执行矩阵乘法,矩阵m1大小为$r1\times c1$,m2为$r2\times c2$。

1.1.5 统计

  • jerasures.c 会记录三种类型的数据
  1. 使用galois_region_xor()中进行XOR操作的字节数;
  2. 在$GF(2^w)$域中乘上常数的字节数,使用galois_w08_region_multiply,galois_w16_region_multiplygalois_w32_region_multiply
  3. 使用memcpy的字节数量。

我们使用函数void jerasure_get_stats(double* fill_in)就可以读到这些数据。在调用这个函数后,用于记录的计数器会被置零。比如 fill_in[0]表示异或的数目。


$\S1.2$ 基础应用教程

例1:构造编码矩阵

\Example\jerasure_01.c

这里输入参数是r,c,w,分别代表矩阵的行数,列数,以及有限域大小。对于$(i,j)$的元素对应于$GF(2^w)$中的$2^{ci+j}$。

例如

./jerasure_01 3 15 8

我们可以得到:

<HTML><TITLE>jerasure_01 3 15 8</TITLE>
<h3>jerasure_01 3 15 8</h3>
<pre>
  1   2   4   8  16  32  64 128  29  58 116 232 205 135  19
 38  76 152  45  90 180 117 234 201 143   3   6  12  24  48
 96 192 157  39  78 156  37  74 148  53 106 212 181 119 238

我们分析一下结果,对于matrix从(0,0)开始,构造$GF(2^8)$上的45个元素(每个都不超过256),至于为什么128后面是29,参考纠删码在存储中的应用关于伽罗华域讲解部分。

例2:构造位编码矩阵

\Example\jerasure_02.c

我们运行

./jerasure_02 3 10 4
1000 0001 0010 0100 1001 0011 0110 1101 1010 0101
0100 1001 0011 0110 1101 1010 0101 1011 0111 1111
0010 0100 1001 0011 0110 1101 1010 0101 1011 0111
0001 0010 0100 1001 0011 0110 1101 1010 0101 1011
 				
1011 0111 1111 1110 1100 1000 0001 0010 0100 1001
1110 1100 1000 0001 0010 0100 1001 0011 0110 1101
1111 1110 1100 1000 0001 0010 0100 1001 0011 0110
0111 1111 1110 1100 1000 0001 0010 0100 1001 0011

0011 0110 1101 1010 0101 1011 0111 1111 1110 1100
1010 0101 1011 0111 1111 1110 1100 1000 0001 0010
1101 1010 0101 1011 0111 1111 1110 1100 1000 0001

整个矩阵的大小为 $rw\times cw$。我们好好看下这个位矩阵是怎么来的。

image-20210126211602293

所以每个$w\times w$子块是不断左移的,。每次移动的距离为1。

例3:构造柯西矩阵以及判断矩阵可逆性

\Example\jerasure_03.c

这会创建一个$k\times k$的柯西矩阵,且$k<2^w$,矩阵$(i,j)$的元素为:$1/\{i\oplus(2^w-j-1)\}$,这儿的减号是普通减法。当$k>2^{w-1}$,存在分母为0 的可能性,这个时候元素被设为0。

我们顺便测试该矩阵是否可逆,如果$k\le 2^{w-1}$就是可逆的,否则不可逆。

运行下列命令

./jerasure_03 4 3

我们得到

<HTML><TITLE>jerasure_03 4 3</TITLE>
<h3>jerasure_03 4 3</h3>
<pre>
The Cauchy Matrix:
4 3 2 7
3 4 7 2
2 7 4 3
7 2 3 4

Invertible: Yes

Inverse:
1 2 5 3
2 1 3 5
5 3 1 2
3 5 2 1

Inverse times matrix (should be identity):
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

例4:构造位柯西矩阵以及判断矩阵可逆性

与例三作用相同,只不过是求位矩阵。

我们得到的结果如下

<HTML><TITLE>jerasure_04 4 3</TITLE>
<h3>jerasure_04 4 3</h3>
<pre>
The Cauchy Bit-Matrix:
010 101 001 111
011 111 101 100
101 011 010 110

101 010 111 001
111 011 100 101
011 101 110 010

001 111 010 101
101 100 011 111
010 110 101 011

111 001 101 010
100 101 111 011
110 010 011 101

Invertible: Yes

...

$k=4,w=3$,这个位矩阵如何理解,

例5:基础RS码构造

\Example\jerasure_05.c

输入参数: k , m, w , size, seed

约束:w必须在8,16,32中取,$k+m\le 2^w$,每个设备的总字节数size必须是sizeof(long)的整数倍,seed是随机数种子。

它首先由jerasure_matrix_encode建立一个$m\times k$柯西编码矩阵:每个元素为$\frac{1}{i\oplus (j+m)}$,接下来,它从数据和编码设备的集合中删除m个随机设备。接下来,它使用jerasure_matrix_decode解码并打印恢复后的矩阵。 该矩阵是分布矩阵的最后k行的逆矩阵。 最后,它使用jerasure_matrix_dotprod()演示了如何在擦除前m个设备后从其他数据显式计算第一个数据设备。
这是w = 8的示例,其中有3个数据设备和4个编码设备,每个设备的大小为8个字节:

输出:十六-十进制(一个字节由两个十六进制位表示)。

./jerasure_05 3 4 8 8 100
<HTML><TITLE>jerasure_05 3 4 8 8 100</TITLE>
<h3>jerasure_05 3 4 8 8 100</h3>
<pre>
The Coding Matrix (the last m rows of the Generator Matrix G^T):

 71 167 122
167  71 186
122 186  71
186 122 167

Encoding Complete:

Data                            Coding
D0 : 8b e3 eb 02 03 5f c5 99    C0 : ab 09 6d 49 24 e2 6e ae
D1 : 14 2f f4 2b e7 72 85 b3    C1 : ee ee bb 70 26 c2 b3 9c
D2 : 85 eb 30 9a ee d4 5d b1    C2 : 69 c0 33 e8 1a d8 c8 e3
                                C3 : 4b b3 6c 32 45 ae 92 5b

Erased 4 random devices:

Data                            Coding
D0 : 8b e3 eb 02 03 5f c5 99    C0 : 00 00 00 00 00 00 00 00
D1 : 00 00 00 00 00 00 00 00    C1 : 00 00 00 00 00 00 00 00
D2 : 85 eb 30 9a ee d4 5d b1    C2 : 69 c0 33 e8 1a d8 c8 e3
                                C3 : 00 00 00 00 00 00 00 00

State of the system after decoding:

Data                            Coding
D0 : 8b e3 eb 02 03 5f c5 99    C0 : ab 09 6d 49 24 e2 6e ae
D1 : 14 2f f4 2b e7 72 85 b3    C1 : ee ee bb 70 26 c2 b3 9c
D2 : 85 eb 30 9a ee d4 5d b1    C2 : 69 c0 33 e8 1a d8 c8 e3
                                C3 : 4b b3 6c 32 45 ae 92 5b

Suppose we erase the first 4 devices.  Here is the decoding matrix:

130  25 182
252 221  25
108 252 130

And dm_ids:

  4   5   6

After calling jerasure_matrix_dotprod, we calculate the value of device #0 to be:

D0 : 8b e3 eb 02 03 5f c5 99

在这个例子中,

第一个编码块的0字节为:

但是,请记住,该实现实际上一次对一组字节执行点积。 因此,在此示例中,每个设备包含8个字节,点积实际上是:

例6:基础位RS码构造

\Example\jerasure_06.c

输入参数:k,m,w,packet_size,seed.

其中packet_size必须是sizeof(long)=4的整数倍。

./jerasure_06 3 4 3 8 100

image-20210127170433218

image-20210127170530595

image-20210127170550129

疑问:为什么RS矩阵的w必须是8,16,32,而位矩阵则只要w在[0,32)以内就行?

在这种编码中,根据编码矩阵第一行中的六个,计算出C0的第一个数据包:

例7:带schedule的位RS码构造

\Example\jerasure_07.C

它执行与jerasure 06中相同的编码/解码,除了它使用位矩阵schedule而不是位矩阵操作。 数据包的大小设置为sizeof(long)个字节。 它创建了一个“dumb”和“smart”的编码时间表,对其进行编码,并打印出每一个进行了多少XOR。
接下来,它擦除m个随机设备,并使用jerasure_schedule_decode_lazy()进行解码。 最后,为了细致化操作,它调用了jerasure_do_scheduled_operations()

./jerasure_07 3 4 3 102

image-20210127165645630

image-20210127165723454

image-20210127165746318

例8:带schedule cache的简单RAID-6构造

它建立一个RAID-6编码矩阵,该矩阵的第一行由1组成,第二行$j$列的元素等于$GF(2^w)$中的$2^j$。 它将其转换为位矩阵,并创建智能编码时间表和用于解码的时间表缓存。
然后将其编码两次: 首先使用smart schedule,然后使用schedule 缓存,方法是将两个编码设备设置为已擦除设备。 接下来,它删除两个随机设备,并使用schedule缓存对其进行解码。 接下来,它删除第一个编码设备,并使用jerasure do parity()对其进行重新计算以演示该过程。 最后,它将释放schedule缓存。


$\S1.3$ 经典RS码

依赖:reed_sol.h, reed_sol.c

1.3.1 Vandermonde分布矩阵

  • int *reed_sol_vandermonde_coding_matrix(k,m,w)

    这将基于扩展的范德蒙德矩阵返回$GF(2^w)$中分布矩阵的最后$m$行。 这是一个$m×k$矩阵,可以与jerasure.c中的矩阵例程一起使用。 此矩阵的第一行保证全为1。 第一列也保证全为1。

  • int *reed sol_extended_vandermonde_matrix(int rows, int cols, w)

    这会创建一个扩展的范德蒙德矩阵。

  • int *reed_sol_big_vandermonde_distribution_matrix(int rows, int cols, w)

    这将扩展矩阵转化为分布矩阵。

1.3.2 针对RAID-6的RS码优化

在RAID-6中,$m=2$,使用奇偶校验从其他编码设备中计算出第一编码设备P,使用以下数据从数据设备Di中计算出第二编码设备Q:

  • int reed_sol_r6_encode(k,w,data_ptr,coding_ptr,size) 编码函数。

  • int *reed_sol_r6_coding_matrix(k,w):为了进行解码,该函数返回分布矩阵的最后两行。第一行全为1,第二行为$2^j$,$j$为列数。

  • reed_sol_galois_w08_region_multby_2(char *region, int nbytes):这会使用Anvin的优化[Anv07]在GF(2^8)中执行快速乘以2。 区域必须是长字对齐的,并且nbytes必须是字长的倍数。
  • reed_sol_galois_w16_region_multby_2(char *region, int nbytes):

  • reed_sol_galois_w32_region_multby_2(char *region, int nbytes)

1.3.3 实例

例8:传统RS编码

\Example\reed_sol_01.c

输入:k,m,w,seed

./reed_sol_01 4 3 8 105
Last m rows of the generator Matrix (G^T):

  1   1   1   1
  1 217  92 172
  1  70 143 200

Encoding Complete:

Data                            Coding
D0 : 6f c1 a7 58 a0 b4 17 74    C0 : 1c 28 9e 71 06 bb 51 22
D1 : 82 13 7f c0 9f 3f db a4    C1 : 7c 0e 9d 11 ee 20 79 ef
D2 : b5 90 6d d0 92 ea ac 98    C2 : 55 0c a8 f2 99 dd 25 e6
D3 : 44 6a 2b 39 ab da 31 6a    

Erased 3 random devices:

Data                            Coding
D0 : 00 00 00 00 00 00 00 00    C0 : 00 00 00 00 00 00 00 00
D1 : 82 13 7f c0 9f 3f db a4    C1 : 7c 0e 9d 11 ee 20 79 ef
D2 : b5 90 6d d0 92 ea ac 98    C2 : 55 0c a8 f2 99 dd 25 e6
D3 : 00 00 00 00 00 00 00 00    

State of the system after decoding:

Data                            Coding
D0 : 6f c1 a7 58 a0 b4 17 74    C0 : 1c 28 9e 71 06 bb 51 22
D1 : 82 13 7f c0 9f 3f db a4    C1 : 7c 0e 9d 11 ee 20 79 ef
D2 : b5 90 6d d0 92 ea ac 98    C2 : 55 0c a8 f2 99 dd 25 e6
D3 : 44 6a 2b 39 ab da 31 6a    

例9:三种重要矩阵

\Example\reed_sol_02.c

输入:k m w

输出:1. $(k+m)\times k $的扩展范德蒙德矩阵;2. 含单位矩阵块的分布矩阵;3. $m\times k$的编码矩阵,通过设置row_k_ones为1,可以进行提速。

注意:w可在1-32取任何值。

./reed_sol_02 4 3 8
Extended Vandermonde Matrix:

  1   0   0   0
  1   1   1   1
  1   2   4   8
  1   3   5  15
  1   4  16  64
  1   5  17  85
  0   0   0   1

Vandermonde Generator Matrix (G^T):

  1   0   0   0
  0   1   0   0
  0   0   1   0
  0   0   0   1
  1   1   1   1
  1 217  92 172
  1  70 143 200

Vandermonde Coding Matrix:

  1   1   1   1
  1 217  92 172
  1  70 143 200

例10:使用Anvin优化的RAID-6矩阵

\Example\reed_sol_03.c

输入参数:k w seed

./reed_sol_03 4 8 100
Last 2 rows of the Generator Matrix:

  1   1   1   1
  1   2   4   8

Encoding Complete:

Data                            Coding
D0 : 8b 03 14 e7 85 ee 42 c5    C0 : a4 24 86 dd f1 ab 31 f6
D1 : 7d 58 3a 05 ea b1 a7 77    C1 : cc c1 fc de b5 61 80 7a
D2 : 44 24 26 69 c3 47 b9 49    
D3 : 16 5b 8e 56 5d b3 6d 0d    

Erased 2 random devices:

Data                            Coding
D0 : 8b 03 14 e7 85 ee 42 c5    C0 : 00 00 00 00 00 00 00 00
D1 : 7d 58 3a 05 ea b1 a7 77    C1 : cc c1 fc de b5 61 80 7a
D2 : 44 24 26 69 c3 47 b9 49    
D3 : 00 00 00 00 00 00 00 00    

State of the system after decoding:

Data                            Coding
D0 : 8b 03 14 e7 85 ee 42 c5    C0 : a4 24 86 dd f1 ab 31 f6
D1 : 7d 58 3a 05 ea b1 a7 77    C1 : cc c1 fc de b5 61 80 7a
D2 : 44 24 26 69 c3 47 b9 49    
D3 : 16 5b 8e 56 5d b3 6d 0d

它主要使用的是reed sol r6 encode(), reed sol r6 coding matrix(), 两个函数。

例11:快速乘法

\Example\reed_sol_04.c

输入参数:w seed

./reed_sol_04 8 100
Char  0: 139 *2 =  11
Char  1:   3 *2 =   6
Char  2:  20 *2 =  40
Char  3: 231 *2 = 211
Char  4: 133 *2 =  23
Char  5: 238 *2 = 193
Char  6:  66 *2 = 132
Char  7: 197 *2 = 151
Char  8: 125 *2 = 250
Char  9:  88 *2 = 176
Char 10:  58 *2 = 116
Char 11:   5 *2 =  10
Char 12: 234 *2 = 201
Char 13: 177 *2 = 127
Char 14: 167 *2 =  83
Char 15: 119 *2 = 238

1.4 柯西编码矩阵

cauchy.h/cauchy.c

  • 构建一个普通的柯西编码矩阵,$M[i,j]=\frac{1}{i\oplus(m+j)}$;
  • 对每一列j,将每一列除以$M[0,j]$,这样的话,行0的每个元素就会变为1.
  • 之后,对于行$i>0$:
    • 计算二进制下,每行1的数目;
    • 除以元素$M [i,j]$的1后,计算二进制下,每行1的数目;
    • 只要j取值使得1的数目增加,就把行i除上$M[i,j]$;

例如$k=m=w=3$下,我们得到如下初始柯西矩阵:

6 7 2
5 2 7
1 3 4

下面我们详细讲解一下包含最少1的cauchy good矩阵是如何得到的。

首先在前提下,我们写出位矩阵和对应的1的个数:

  100 	001 	010		101		011		111		110
  010		101		011		111		110		100		001
  001		010		101		011		111		110		100
>(dec)    1		 2		 4		 3 		 6  	 7 		 5
>(num_1's)3		 4		 5 		 7		 7		 6		 4

>step1:原始矩阵,如果我们对第1行分别除上第一列的元素:

>1 1 1
>4 3 6 -> total 1's = 5 + 7 + 7 = 19 
>3 7 2 

>step2:再对第二行除上每个元素以找到最少1的那个,
>(a) 除上4.
>1 1 1
>1 2 4 -> total 1's = 3 + 4 + 5 = 12 
>3 7 2

>(b) 除上3.
>1 1 1 
>5 1 2 -> total 1's = 4 + 3 + 4 = 11
>3 7 2 

>(c) 除上6.
>1 1 1 
>7 5 1 -> total 1's = 6 + 4 + 3 = 13
>3 7 2 
>可知除上3得到的矩阵1的数目最少。
>step3:对第三行也进行类似于第二步的操作,最终我们得到cauchy good矩阵
>1 1 1 -> 3+3+3=9
>5 1 2 -> 4+3+4=11
>3 7 2 -> 3+5+6=14
>一共是 9+13+14=34个1
>原始矩阵有46个1,而[PX06]给出 的矩阵有39个1,我们的矩阵明显更优秀一些。
  • int *cauchy_original_coding_matrix(k,m,w)

    返回柯西编码矩阵的原始形式。

  • int *cauchy_xy_coding_matrix(k,m,w,int*X, int *Y)

    指定集合X,Y创建柯西矩阵。集合X拥有m个元素,集合Y有k个元素。集合没有重复元素,并且两个集合没有交集。

  • void cauchy_improve_coding_matrix(k,m,w,matrix)

    这个提升在于,先将每一列除上0行元素。

  • int *cauchy_good_general_coding_matrix()

    这会返回一个好矩阵,当$m=2,w\le 11, k\le 1023$,它会返回最优的RAID-6 矩阵。它会引用最前面两个函数。

  • int cauchy_n_ones(int n, int w):

    这将返回$GF(2^w)$中数字n的位矩阵表示形式中的1。 它比生成位矩阵和计数位要有效得多。

例12:计算柯西位矩阵块1的个数

\Example\cauchy_01.c

输入:n,w

输出:位矩阵和1的个数。

./cauchy_01 5 3
<HTML><title>cauchy_01 3 5</title>
<HTML><h3>cauchy_01 3 5</h3>
<pre>
Converted the value 5 (0x5) to the following bitmatrix:

110
001
100

# Ones: 4

例13:柯西位矩阵编解码

\Example\cauchy_02.c

输入:k,m,w,seed

在该例子,packetsize为4. 它首先执行cauchy_original_coding_matrix()来创建一个柯西矩阵,之后转化为位矩阵并编码两次:第一次是jerasure_matrix_encode(),第二次是异或次数更少的jerasure_schedule_encode()。同样它也解码两次,分布调用jerasure_bitmatrix_decode()jerasure_schedule_decode_lazy()

./cauchy_02 3 3 3 100

image-20210131182921044

image-20210131182947015

例14:改进的柯西位矩阵编解码

\Example\cauchy_03.c

功能与例13相同。它使用cauchy_xy_coding_matrix()创建矩阵,并使用cauchy_improve_coding_matrix进行优化。

image-20210131184008267

image-20210131184030092

可以看到异或运算从296次减少到200次,优化效果明显。

例15:最好的柯西编码矩阵

\Example\cauchy_04.c

功能与例13相同。它使用的是cauchy_good_general_coding_matrix()。注意:在$m = 2,w\le11, k\le 1023$这些都是最优的柯西编码矩阵(但不是最优的RAID-6矩阵)。

1.4.1 扩展最优Cauchy RAID-6矩阵的参数空间

很容易证明,只要$k <2^w$,那么第0行中全为1并且第1行中具有不同非零元素的任何矩阵都是有效的MDS RAID-6 矩阵。 因此,对于给定值w的最佳RAID-6矩阵是这样的矩阵,其第1行中的k个元素是在其位矩阵中数量最少的k个元素。 Cauchy.c将这些元素存储在$k≤1023$和$w≤11$的全局变量中。文件cauchy_best_r6.ccauchy.c相同,只不过它包括w≤32的这些值。
这些值不在cauchy.c中的原因仅仅是为了减小目标文件的大小。

1.5 最小密度RAID-6 编码

最小密度RAID-6代码是基于位矩阵的MDS代码,该二进制矩阵满足非零数的下限。 与柯西编码不同,位矩阵元素不对应于GF(2^w)中的元素。 取而代之的是,位矩阵本身具有适当的MDS属性。 对于相同的参数,最小密度RAID-6代码的执行速度比Reed-Solomon和Cauchy Reed-Solomon代码快。 Liberation编码,Liber8tion编码和Blaum-Roth编码是jerasure支持的这种编码的三个示例。
对于这些代码中的每一个,m必须等于2,k必须小于或等于w。 w的值受代码[PBV11]的限制:

​ •对于Liberation编码,w必须是质数。
•对于Blaum-Roth编码,w +1必须是质数。
•对于Liber8tion编码,w必须等于8。

liberation.c\liberation.h实现了如下步骤:

  • int *liberation_coding_bitmatrix(k,w)

这分配并返回用于自由编码的位矩阵。 尽管w必须是大于2的质数,但此过程未强制执行。 如果给它一个非素数w,则将获得一个非MDS编码矩阵。

  • int *liber8tion_coding_bitmatrix(int k)

这会分配并且返回针对libera8tion编码的矩阵。liber8tion中的8表示$w=8$。

  • int *blaum_roth_coding_matrix(int k, int w)

这会分配并且返回针对Blaum Roth的编码矩阵。

例16:liberation编码矩阵

\Example\liberation_01.c

输入参数:k, w, seed .

w是一个大于2的质数,且$k\le w$。

./liberation_01 3 3 100

image-20210201151829328

可以看到同样的参数下,liberation码得到的矩阵明显更稀疏。编码产生的异或数更少,所以计算开销更少。

矩阵大小为$2w\times kw$,该码的特点为,前k+1个块都是单位矩阵,最后k-1个矩阵有些规律。

例 17 文件编码解码

./Example/encode.c

  • encoder.c编码文件:
./encoder 'inputfile' k m 'coding_technique' w (packetsize) (buffersize)

‘inputfile’: 输入文件或负数S:要编码的文件或负数S,指示应使用大小为-S的随机文件而不是现有文件

k:将文件划分的数据块的数量

m:根据数据块生成的校验块的数量

coding_technique:使用的编码算法。

  • “reed_sol_van”:范德蒙德RS码,w=8,16,32
  • “reed_sol_r6_op”:针对RAID-6优化的RS码,m=2,w=8,16,32
  • “cauchy_orig”:原生柯西编码
  • “cauchy_good”:优化的柯西编码
  • “liberation”:最小密度RAID-6中的liberation,k小于等于w,w大于2,且为质数
  • “blaum_roth”:最小密度RAID-6中的blaum roth,k小于等于w,w大于2,且w+1为质数
  • “liber8tion”:最小密度RAID-6中的liber8tion,k小于等于w,w=8,m=2
  • “no_coding”:无编码

w:word size。

packet size:就是packet size 。一般为4的整数倍。

buffer size:每次处理的数据大小,例如1024。

例子:

./encoder /home/durantthorvalds/jerasure-master/test.pdf 6 2 liberation 7 1024 500000
Encoding (MB/sec): 3294.5325077314
En_Total (MB/sec): 372.5363687737
drwxrwxrwx 5 durantthorvalds durantthorvalds    4096  21 16:01 ..
-rw-rw-r-- 1 durantthorvalds durantthorvalds 2637824  21 16:01 test_k1.pdf
-rw-rw-r-- 1 durantthorvalds durantthorvalds 2637824  21 16:01 test_k2.pdf
-rw-rw-r-- 1 durantthorvalds durantthorvalds 2637824  21 16:01 test_k3.pdf
-rw-rw-r-- 1 durantthorvalds durantthorvalds 2637824  21 16:01 test_k4.pdf
-rw-rw-r-- 1 durantthorvalds durantthorvalds 2637824  21 16:01 test_k5.pdf
-rw-rw-r-- 1 durantthorvalds durantthorvalds 2637824  21 16:01 test_k6.pdf
-rw-rw-r-- 1 durantthorvalds durantthorvalds 2637824  21 16:01 test_m1.pdf
-rw-rw-r-- 1 durantthorvalds durantthorvalds 2637824  21 16:01 test_m2.pdf
-rw-rw-r-- 1 durantthorvalds durantthorvalds      90  21 16:01 test_meta.txt

packetsize 为1k。这儿的6个数据文件大小刚好为源文件的大小.注意文件大小既是7的倍数,也是1024的倍数。

按照上述说明执行命令后,我们会发现在Examples文件夹中创建了一个Coding文件夹,顾名思义,这里存放着编码好的数据块和编码块,以及一个meta文件,存放文件的编码信息。每个数据块文件都会被命名为”_k#”(数据块)和”_m#”(校验块)然后跟着源文件的扩展名。例如 40kb-image.jpg 就会生成一个 40kb-image_k1.jpg。

test_meta.txt是这次encoding的相关参数,这些参数将会用于decoding过程。

/home/durantthorvalds/jerasure-master/test.pdf
15431554
6 2 7 1024 688128
liberation
4
23
  • decoder解码文件:
./decoder 'inputfile'

在解码之前,我们假设一种不幸的情况,有两个文件块丢失了。

durantthorvalds@ubuntu:~/jerasure-master/Examples/Coding$ rm test_k1.pdf test_m1.pdf

durantthorvalds@ubuntu:~/jerasure-master/Examples$ ./decoder /home/durantthorvalds/jerasure-master/test.pdf 
Decoding (MB/sec): 3815.5760207509
De_Total (MB/sec): 818.9580808033

durantthorvalds@ubuntu:~/jerasure-master/Examples$ diff Coding/test_decoded.pdf /home/durantthorvalds/jerasure-master/test.pdf

diff没有输出表示两文件完全相同。

另外如果损坏文件数超过m,解码也会失败!

1.6 合理地选择Buffer和Packetsize

在我们的测试中,缓冲区和数据包的大小对性能的影响与所使用的代码一样多。 多位作者(例如[PLS + 09,PGM13])多次对此进行了演示。 以下时序使用Liberation代码对k = 6和w = 2的256MB随机创建的数据进行编码。这些时序于2014年在MacBook Pro上拍摄,并显示了数据包和缓冲区的大小如何影响性能。

UNIX> encoder -268435456 6 2 liberation 7 1024 50000000
Encoding (MB/sec): 1593.9637842733
En_Total (MB/sec): 672.1876668353
UNIX> encoder -268435456 6 2 liberation 7 1024 5000000
Encoding (MB/sec): 2490.9393470499
En_Total (MB/sec): 1383.3866387346
UNIX> encoder -268435456 6 2 liberation 7 10240 5000000
Encoding (MB/sec): 2824.2836957036
En_Total (MB/sec): 1215.1816805228
UNIX> encoder -268435456 6 2 liberation 7 102400 5000000
Encoding (MB/sec): 1969.8973976058
En_Total (MB/sec): 517.6967197425

结论是:

  • 在packetsize相同时,buffer越大,编码速度可能越快;
  • 在buffersize相同时,packetsize越大,编码速度越快。

1.7 改变默认的伽罗华域

当我们需要改变本原多项式,或者其它类似操作就需要改参数。下面两个例子展示了这些。

reed_sol_test_gfreed_sol_time_gf

输入:k,m,w,seed

它至少需要五个命令行参数。 前四个是k,m,w和种子。 接下来是Galois字段的规范,该字段使用从GF-Complete的argv()创建gf的过程。 如果给它一个短横线,它将选择默认值。 然后,程序创建用于Reed-Solomon编码的生成器矩阵,进行编码和解码,并确保解码成功。