Analysis and Construction of Functional Regenerating Codes with Uncoded Repair for Distributed Storage Systems

原文

本文作者是NCCloud 作者在INFOCOMM13 上发表的短文。作为NCCloud 的理论基础,证明了n = k+2 = d+1 情况下,FMSR 的存在性,并给出了这类编码的一个确定的编码方式。NCCloud 和本文提到的FMSR 具有三点重要性质:

  1. FMSR 码存储效率和容错效率与MDS 相同
  2. FMSR 达到最小修复带宽
  3. FMSR 使用非编码修复(uncoded repair/repair-by-transfer)

继续阅读

Linux 下使用Doxygen

Doxygen 是支持多种语言的文档生成工具。也许在编码前能把设计文档写好,再来编写代码是正确的一件事情,当由于中间编码过程中任务的修改或者代码的优化等原因,会导致开始所写的文档变动非常大,于是在编码前写好文档对于大多数程序员是不太现实的。而在代码写完之后再补上相应的文档则是一件非常常见的做法。Doxygen 就能很好的帮你做好这件事件,在你的代码按照Doxygen 的格式写好注释后,几分钟Doxygen 就能够很快地为你生成文档。最近要使用Doxygen 也是因为代码变多后,之前写的函数往往名字都不记得了,如果能有一份文档查询相应的函数会非常方便。(值得一提的是Hadoop 支持了Doxygen 文档的生成)

继续阅读

一些关于矩阵的基础知识

一、特殊矩阵

正方矩阵/方阵( Square matrix )     大小为n×n 的矩阵

单位矩阵( Identity matrix )             对角线上元素为1,其余元素为0 的方阵,常用I 表示

置换矩阵( Exchange matrix )        反对角线上元素为1,其余元素为0 的方阵,常用J 表示

对角矩阵( Diagonal matrix )          非对角线上元素全为零的方阵

对称矩阵( Symmetric matrix )       满足矩阵中元素eij = eji   的方阵

三角矩阵(Triangle matrix)             分为上三角矩阵(元素eii 以上元素为零)和下三角矩阵

正交矩阵(Orthgonal matrix)          满足MTM = I 的方阵,矩阵和矩阵转置的乘积为单位矩阵

继续阅读

两种最小带宽再生码(MBR)

[1] 和[2] 都是有Rashmi K.V. 提出的精确修复最小带宽再生码。精确修复(exact repair)指的是修复的存储节点数据和节点丢失的数据是完全一致的。RAID 和RS 码都是精确修复,NCCloud 中提出的F-MSR 就不是精确修复。相对于精确修复是功能性修复(functional repair),这种修复只保证了一定的数据冗余性,使得数据可以被恢复出来,并且在下一次丢失一定量数据时可以功能性修复该数据并继续保持数据冗余性。相比精确修复,功能性修复更具不可控性。

早在[1] 中就提出了一种精确修复的再生编码,更重要的是证明了两点:1. 精确修复的最小带宽再生码(exact repair MBR)码率R 大于等于 1/2;2. 精确修复的最小带宽再生码只有一种文中提出的构造方式,所有其他构造的精确修复的最小带宽再生码都是和这种方法同构的。

继续阅读

Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions(FAST 13′)

PDF     Slide     Video

这是FAST13 中一篇关于通过Intel SSE3 指令集加速伽罗瓦域上计算的短文。纠错码广泛用于存储系统中,可分为XOR(异或)码和Reed-solomon(RS) 码。前者(LDPC, RAID5, X-code)在编码时仅进行异或运算,速度快;后者编码运算基于伽罗瓦域/有限域GF(2w),速度相对较慢(XOR 可看做是GF(2) 上的运算)。该文旨在提出基于处理器128 比特指令集加速编码时的乘法运算。

继续阅读

初探GF-Complete(伽罗瓦运算库)

GF-Complete 是一个开源、综合性的伽罗瓦运算库,相应的文章发表在FAST13 中(见参考文献【1】)。作者是大名鼎鼎的Jim Plank 教授,作为开源纠错码库Jerasure 的开发者,在这个伽罗瓦运算库中创新地采用了SSE 指令集来加速纠错码运算的瓶颈—伽罗瓦运算中的乘法运算,并采用了其他运算方法,综合得到GF-Complete。该库可在Plank 主页中下载得到,下面就GF-Complete 库做简要分析,详细可参考文档【2】。

继续阅读