为什么要将文件分块编码?

编码指的是冗余编码或者加密编码等。如果能够将大文件一次性读入内存进行编码的话,为什么要选择将连续的文件分成一块一块(packet)地进行编码呢?个人认为原因有几点:

  1. 节省内存,减少I/O 时间
  2. 利用CPU 缓存局部性,适当的选择packet 大小能够提高编码速度

2

上图给出了RS 码在编码1GB、512MB和256MB 时,不同packet 对编码速度的影响。总体来说,文件越大,编码速度越慢;packet 大小在16KB 和1MB 之间(缓存大小)编码速度最快;packet 超过缓存大小时,编码速度有所下降。packet 大小在RDP 码上的影响参考[1]

 

[1] Plank, James S., et al. “A Performance Evaluation and Examination of Open-Source Erasure Coding Libraries for Storage.” FAST. Vol. 9. 2009.

和NTL(Number Theory Library) 比较有限域上矩阵求秩

下载了NTL(Number Theory Library),简单对正方矩阵(square matrix)求秩和nclib 进行了测试,测试参数如下:

  • 有限域大小为:GF(28)、GF(216)和GF(232)
  • 正方矩阵维度从2 到255(横坐标)

测试方法:随机生成指定大小的矩阵,计算其秩大小,仅计算一次。

测试结果如下(分别是GF(28)、GF(216)和GF(232) 域上的结果):

 

320816

在域大小为GF(28)和GF(216)时差别还不是很大,但为GF(232) 时,计算速度差距就有些大了,主要还是矩阵的表示方法不同,nclib 用uint_8/uint_16/uint_32 类型表示三个域中元素,而NTL 中域中元素全部二进制表示,计算秩更多的使用了单个元素求逆和而不是像nclib 建立域上计算表。比如GF(232) 上进行求秩,方阵很小的时候速度也很慢,是把有限域上计算表(乘法表、对数表)时间给算进去了。nclib 可以对此进行改进。

相关文件

sage:基于云的数学软件系统

Sage is a free open-source mathematics software system licensed under the GPL. It combines the power of many existing open-source packages into a common Python-based interface.

可以在http://www.sagenb.org/home/ 注册并登陆后建立工作清单(worksheets),清单以命令行形式支持多种开源包,比如NTL(Number Theory Library http://sage.math.washington.edu/tmp/sage-2.8.12.alpha0/doc/ref/module-sage.libs.ntl.all.html)。其未来定位应该是将用户本地的Matlab 迁移到云端,以后用户就不用下载、安装那么大的安装文件了~~

求组合数、排列数等

最近写程序一直遇到组合数,排列数等问题。文章介绍程序实现全排列$A_{n}^{n}$、组合$C_{n}^{k}$ 中每个项的列举。

全排列$A_{n}^{n}$ 有顺序的排列n 个数;

组合$C_{n}^{k}$ 从n 个数中选取k 个进行无顺序的组合;

附:一般性的排列$A_{n}^{k}$ 可以通过组合和全排列一起完成。

继续阅读

减少分布式存储系统中基于异或(XOR)冗余编码的修复带宽

背景:分布式存储系统中越来越多地使用冗余编码减少存储开销,保证数据冗余。但存在的问题就是在一个节点发生失效时,需要从网络上的节点下载大量数据修复丢失的数据块,也称修复问题。基于异或(XOR)的冗余编码速度快,易于实现。本文选自FAST12 中Rethinking erasure codes for cloud file systems: Minimizing I/O for recovery and degraded reads ,介绍减少基于异或编码的修复带宽。

问题:通常的修复过程是下载等于原始数据量的数据块,解码得到原始数据,然后经历一个再编码的过程得到丢失的数据块,但这样往往浪费了一些下载的数据,如何为基于XOR 的冗余编码找到最优的修复数据块,使得修复带宽最小呢?

以生成矩阵(Generator Matrix)为下图的编码为例,如果丢失的第一个数据节点,相应地丢失了R0 和R1 对应的数据块,下载任意其他四块数据块可以修复这两块数据块,但显然不是最优的,最优的情况是下载R2、R4 和R7 所对应的数据块,就可以解码得到R0 和R1

gm

定义

  • F 表示为丢失的数据块对应行号的集合;
  • {……} 表示相关数据块对应行号的一个最小集合,且有且仅有一个失效的数据块在其中。比如{R0,R2R4} 满足R0 = R2 +R4,且R2 和R4 都不在F 中,以问题给出的图为例,这样的集合还有{R0,R3R6} 等;
  • {R0,R2R4}  可以表示为10101000,其中对应的位上为1 表示该数据块在集合中;
  • Ei 是所有{……} 中失效节点为i 的集合,即所有相关集合中包含i 的子集,按顺序写作ei,0,ei,1,……;

方法:构造一个有向图(如Figure 5),起点为全零的Z 串(00000000),边为Ei 中的元素ei,j ,边的权重为起点和终点的汉明距离,也就是需要的数据块的个数,每一层代表修复一个数据块。路径中权重最小的路径为最优修复路径(图中粗箭头所指)。

graph

为构建该图,首先将F 中所有节点对应相关集合都计算出来,即E(ei,j 中i 表示节点,j 表示序号):

equations

问题中的例子为例。从Z 开始,首先修复第一个数据块(R0),对应e 的权值为3,3,5,5,接着分别在已有的基础上修复第二个数据块(R1),并得到第二步的权值。使用Dijkstra 可得到最短路径,即最优修复数据块集合。