jerasure纠删

编码引擎评判标准
以下几个关键指标可以对编码引擎性能进行分析：
1、高编/解码速度；
2、参数可配置；
3、编码速度稳定性；
4、代码简洁、稳定；
5、降低修复开销等。
一个可配置参数的编码引擎可以根据数据的冷热程度和数据重要程度选择不同的编码系数而不需要改动引擎本身，这大大降低了后续的开发和维护所需要的精力。比如可靠性要求高的数据可以选择更多冗余。数据恢复和更新代价高，因此常常针对只读数据，或者冷数据。

Erasure Code 参数说明

用法：./encoder ‘data/test.rar’ k m ‘reed_sol_van’ wordsize packetsize buffersize

1.纠删码将一个源文件以若干字节为单位分成k个等长的数据块，通过矩阵运算生成m个与数据块等长的冗余块，用于还原源文件。编码效率R=k/m。

2. RS编解码中涉及到矩阵求逆，若采用高斯消元法，需要进行实数加减乘除四则运算，无法作用于字长为w位的二进制数据。为了解决这个问题，RS采用伽罗华群GF（2^w）中定义的四则运算法则，RS code是基于有限域 的一种编码算法，k+m个数据块就是这个有限域中的元素，因此满足 。RS编码依赖于两张2w-1大小的log表。每个数据块包含若干个字节, 每个字节的长度为w位, w∈{8 , 16 , 32 , 64}, w可在程序设计时自由选择, w值一般选取2的幂，w值越大，纠删码越丰富（可生成更多地数据块和冗余块），但随w值增大，在伽罗瓦域上的计算复杂度提高。通常选择w =8, 因为系统中包含少于28个磁盘, 而且w=8表现性能最好。

3. 以packetsize bytes大小的包为单位进行编码， packetsize个word。决定了packet的大小：
   packet大小=4（int是4位，若是float为8位）wordsizepacketsize 单位B
   第一次编码子过程操作的数据大小是k个packet ,就是一个buffersize。

4.buffersize是源数据在编码分片时设置的缓冲区大小，设置缓冲区的目的是当用户编码的文件过大，读入内存的数据过多会导致编码效率下降，所以选择合适大小的分段缓存可以让编码效率最高。另一个作用是用户节点在下载文件时解码也要用相同的大小buffersize才能正确聚合文件，在一定程度上保护了用户数据的隐私性。这个数值在编码运行时会自动调整，调整到适当的大小，目的是更快地（以最少次数readins）将文件读入内存。

纠删码编码过程验证：
一、 准备
为了方便观察编码过程中源文件的变化，以一个纯数字和少量字母的文本文件为目标文件test.txt，规格如下，共有6段，每段16行64列，（注意：在linux中换行算一个字节，所以一行有63个数字加一个换行字节）：

…
编码工具使用jerasure的reed_sol_van算法；

二、 测试几个典型参数

编码后生成6个数据块、2个冗余块和1个元数据文件test_meta.txt，存放编码相关的参数：
data/test.txt 编码的目标文件
6144 目标文件的大小 单位 B
6 2 8 8 1536 编码参数k m w p b ，其中b参数会自动优化，匹配最优大小。
reed_sol_van 编码算法
0 暂时未知
4 readins表示编码需要读入4次buffersize大小的数据才能完成。

由参数可以计算出编码过程中单次操作的包（packet即数据块中的一个分片）大小为：packet = 4 * wordsize * packetsize = 488 = 256 B
与每个数据块的一个分片大小吻合：4行64字节 = 256 B
所以一个packet就是编码后数据块的一个分片。
buffersize大小为kpacket=6*256 B = 1536 B
与元数据文件中参数一致。向缓冲区写入4次就能把数据块写完，所以图中的数据块有4段。

当数据块分片不足一个包大小时，矩阵运算结果无法保持一致性，所以在每个不足大小的包中补0。

元数据文件：
packet大小为4 * wordsize * packetsize = 488=256 B
buffersize大小为7packet=1792 B


元数据文件为：
data/test.txt
6144
8 2 16 8 4096
reed_sol_van
0
2
packet大小为4168=512 B
buffersize大小为8packet=4096 B
向缓冲区写入2次就能把数据块写完，所以图中的数据块只有2段。

Jerasure库接口
Jerasure库提供Reed-Solomon和Cauchy Reed-Solomon两种编码算法的实现.
①Reed-Solomon矩阵编码接口：

matrix：编码矩阵 （m*k），Jerasure库用的是范德蒙矩阵；
data_ptrs：数据块指针 (长度为k的指针数组)
coding_ptrs：校验块指针(长度为m的指针数组)
size：数据块大小

②Reed-Solomon矩阵解码接口

row_k_ones: 编码的第一行是否全为1，用于优化
erasueres: 记录哪些块丢失了，长度超过m则不能恢复，以-1做为结束标识
erasures[0] = 0; // 第0个块丢失
erasures[1] = 3; // 第3个块丢失
erasures[2] = -1; // -1, 结束标识
size：数据块大小（必须是sizeof(long)的倍数）

③向量点积计算接口：

文件galois.h和galois.c包含用于1≤w≤32的GF（2 w）中的伽罗瓦域算法（可以了解下有限域四则运算）的过程。它们包含用于单个算术运算，对字节区域进行异或，以及用于执行乘法的过程。GF（2 8），GF（2 16）和GF（2 32）中的常量是字节区域。开头提到的wordsize必须∈{8、16、32} 就是在这个接口中需要强制要求。对二进制数据进行矩阵编码运算需要在GF(2w)有限域中运算。
有限域GF(2^w)：
GF§中p必须是一个素数，才能保证集合中的所有元素都有加法和乘法逆元(0除外)。但实际应用中，很多场合需要0到255这256个数字能组成一个域。但256不是素数，小于256的最大素数为251，如果直接把大于等于251的数截断为250，则会丢失一部分数据。
因此引入了GF(p^{w)，其中p为素数，通常取p=2。计算机领域中经常使用的是GF(2}8)，8刚好是一个字节的比特数。为了保证单位元性质，GF(2^w)上的加法运算和乘法运算，不再使用一般的加法和乘法，而是使用多项式运算。

这里对有限域概念有详细介绍。

纠删码在分布式存储的应用
基础概念：

1. 分片上传引入了两个概念：块（block）和片（chunk）。每个块由一到多个片组成，而一个资源则由一到多个块组成。数据分片（segment，fragment， shard， partition），就是按照一定的规则，将数据集划分成相互独立、正交的数据子集，然后将数据子集分布到不同的节点上。注意，这里提到，数据分片需要按照一定的规则，不同的分布式应用有不同的规则，但都遵循同样的原则：按照最主要、最频繁使用的访问方式来分片。通过分片机制得到的每一个文件分片都是由文件不同部分的数据块和校验块组成的 , 分片中文件信息是分散的 ,即单个文件分片不会泄漏用户数据信息。

2. 块是服务端的永久数据存储单位，片则只在分片上传过程中作为临时存储的单位。

3. 在分布式的HDFS集群上，为了便于文件的管理和备份，引入分块（block）概念。这里的“块”是HDFS存储系统当中的最小单位，HDFS默认定义一个块的大小为64MB（从2.7.3版本开始，block size由64 MB变成了128 MB，设计得这么大有两个好处：①减少硬盘寻道时间，②减少需要维护的数据块信息）文件大小大于设置的块大小，则该文件会被切分存储为多个块， Hadoop系统保证一个块存储在一个DataNode上。（如果某文件大小没有到达设置的块大小，则该文件并不会占据整个块空间。）HDFS中的NameNode会记录在上述文件分块中文件的各个块都存放在哪个DataNode上，这些信息一般也称为元信息(MetaInfo),元信息的存储位置由dfs.name.dir指定。DataNode则存有文件的MetaInfo和具体的分块，存储路径由dfs.data.dir指定。

4. 当一个作业提交到Hadoop运行时，其中的核心步骤是MapReduce，在这个过程中传输的数据可能会很多，Hadoop会将MapReduce的输入数据划分为等长的小数据块，称为输入分片或者分片。hadoop为每个分片构建一个map任务,分片的默认实现由InputSplitFormat 类的 getSplits()方法指定：

long splitSize = computeSplitSize(goalSize, minSize, blockSize);
//computeSplitSize方法中省略其他代码，核心计算规则如下
Math.max(minSize, Math.min(goalSize, blockSize));

其中goalSize的值为：(InputFile的大小)/（配置文件中定义的mapred.map.tasks的值），即期望每个Mapper处理多少的数据，仅仅是期望，具体处理的数据数由下面的computeSplitSize决定。
minsize的值为：配置文件mapred.min.split.size的值；
blockSize的值为：64(默认情况)

5. MapReduce是一种分布式计算模型，是Google提出的一种编程模型，主要用于大规模数据集（大于1TB）的并行运算。概念"Map（映射）“和"Reduce（归约）”，是它们的主要思想，都是从函数式编程语言里借来的，还有从矢量编程语言里借来的特性。它极大地方便了编程人员在不会分布式并行编程的情况下，将自己的程序运行在分布式系统上。当前的软件实现是指定一个Map（映射）函数，用来把一组键值对映射成一组新的键值对，指定并发的Reduce（归约）函数，用来保证所有映射的键值对中的每一个都共享相同的键组。

MapReduce原理：

MapReduce的执行步骤：
1、Map任务处理
 读取HDFS中的文件。每一行解析成一个<k,v>。每一个键值对调用一次map函数。 例如：<0,hello you> <10,hello me>
 覆盖map()，接收1.1产生的<k,v>，进行处理，转换为新的<k,v>输出。 例如：<hello,1> <you,1> <hello,1> <me,1>
 对第二步输出的<k,v>进行分区。默认分为一个区。详见《Partitioner》
 对不同分区中的数据进行排序（按照k）、分组。分组指的是相同key的value放到一个集合中。　
排序后：<hello,1> <hello,1> <me,1> <you,1> 分组后：<hello,{1,1}> <me,{1}> <you,{1}>
 （可选）对分组后的数据进行归约。详见《Combiner》

2、Reduce任务处理
 多个map任务的输出，按照不同的分区，通过网络copy到不同的reduce节点上。（shuffle）详见《shuffle过程分析》
 对多个map的输出进行合并、排序。覆盖reduce函数，接收的是分组后的数据，实现自己的业务逻辑，　<hello,2> <me,1> <you,1>处理后，产生新的<k,v>输出。
 对reduce输出的<k,v>写到HDFS中。

附录：
Linux文件分片工具split：可以将一个大文件分割成很多个小文件。
split（选项）（file）PREFIX
-b：值为每一输出档案的大小，单位为 byte。
-C：每一输出档中，单行的最大 byte 数。
-d：使用数字作为后缀。
-l：值为每一输出档的列数大小。
PREFIX:代表前导符，可作为切割文件的前导文件。

分片合并命令：cat xa* > file 其中xa为分片文件前缀。