两种最小带宽再生码(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】。

继续阅读

伽罗瓦域上的乘法

一、前言

伽罗瓦域上的乘法在包括加/解密编码和存储编码中经常使用,常见的AES 和Reed-Solomon 编码就使用了伽罗瓦域GF(28) 中的运算。以2 或者2w 形式的伽罗瓦域来说,加减法都是异或运算,乘法相对较复杂一些,本文就GF(2w) 上有限域的乘法运算和优化进行分析。现代计算机是为二进制普通运算所设计,对伽罗瓦域计算最多仅有指令集上的优化,而且仅限于某些处理器,因此在更高层次上优化伽罗瓦域上的乘法显得尤为重要。

继续阅读

Explicit Construction of Optimal Exact Regenerating Codes for Distributed Storage

原文地址

从文章字面意思来看讲的是最优再生码的显示结构。文章主要贡献是给出了d = n-1 情况下的精确修复(Exact repair)MBR 一个通用的结构。

在分布式存储系统中,通过传输信息修复失效节点中的数据可以分为两类:精确修复(Exact repair,即修复得到的新数据和原来因节点失效的数据相同)、功能性修复(Functional repair,即修复得到的数据可能和原失效数据不同,但修复保持着数据的冗余度)。精确修复又有一类只对系统码中的原始数据部分进行精确修复,对校验部分进行功能性修复。三者包含范围关系如下:

                                  image

继续阅读