Clay Codes — 从生成矩阵的角度来看

Clay Codes ( Clay Codes: Moulding MDS Codes to Yield an MSR Code ) 是FAST18 上提出的一种编码方法,文章地址,Clay 码能够将一般的MDS 码(最优容错)转化为具有最优修复的编码方法,具有以下性质:

  • Minimum Storage (最小存储开销,同经典RS码和最小存储再生码,MSR)
  • Maximum Failure Tolerance(最大容错,即 (n,k)-Clay 码可以容任意n-k 失效)
  • Optimal Repair Bandwidth (最优修复开销,能够达到理论最优值)
  • All-Node Optimal Repair (最小开销修复所有节点的数据,包括原始数据和校验数据)
  • Disk Read Optimal (最优磁盘读)
  • Low Sub-packetization (低分包数,即码字长度短)

首先介绍下Clay 码的设计思想,第二部分从生成矩阵的角度来看看Clay 码如何实现。

一 Clay 码的设计思想

1.1 术语

首先文章介绍了一些基础概念:

纠删码:纠删码将一段原始数据等分为k 份,进而编码为m 份,共计n=k+m 份,通过将这n 份数据分别存储在n 个不同的存储节点上,达到抵御数据丢失的风险。

标量码/向量码(Scalar code/Vector code):标量码每个码字在每个节点上包含一个字节,向量码在每个节点上包含若干个字节,共同组合为一个超字节(superbyte),不同节点上超字节共同组成一个码字。

   上图表示标量码,下图表示向量码。在磁盘阵列中,每个条带(stripe)也是横跨n 个节点,对应的一个码字,而码字中一个字节(标量码)或者超字节(向量码)则对应着条带中的一个数据块。一个(n,k) 标量码和向量码在生成矩阵中对应的是一个n×k 和nw×kw 矩阵,其中一个超字节包含w 个字节。

MDS 码:最大距离可分(Maximum Distance )码是一种最优容错编码方法,即编码后的n 份数据最大可容忍任意m 份数据失效,原始数据也不会丢失。常见的RS、CRS、Evenodd、RDP 码都是MDS 码。

修复开销:修复开销指的是重建一个节点数据或单个数据块所需要的数据量(从磁盘读取、从网络传输的数据量)。在存储系统中,单点失效是常态,因此研究更注意单点失效的修复开销。

MSR 码:最小存储再生码(Minimum Storage Regenerating codes,MSR 码)是一类具有最小存储开销下的再生码。再生码是一类能够减少修复开销的纠删码。

原始数据量为M,再生码在每个节点存储的数据量为α。如果每个节点存储量最小,即α=M/k,那么这个再生码是MSR 码,和其他经典(n,k)-MDS 码存储开销相同。当一个节点失效,需要从剩余d<(n-1) 个节点中每个取β<α 数据完成修复,修复开销为dβ。当n-1 时,修复开销最小,为(n-1)α/m。

磁盘开销:再生码是网络编码研究者提出的,在数据修复时在网络上传输的数据量能够达到理论最小,但需要在磁盘上读取大量数据,进而计算得到少量修复数据进行数据修复,因此需要额外的磁盘访问和计算。Clay 码能够减少磁盘开销,即在网络上传输的数据就是从磁盘哦读取的数据。

系统码:系统码编码后保留了原始数据,非系统码编码后只有校验数据。实际存储系统中常见的是系统码,这样数据读取不用解码。

1.2 编码方法

下面以(n=4,k=2) 来介绍Clay 码,一种将一般MDS 码转化为MSR 码的方法。

Clay 是Coupled Layer 的结合,包含了Clay 码的两个特点:1 将MDS 码分层处理;2 分层之间耦合数据。

一个(4,2)-MDS 码编码后的数据有4 份,可以摆放成一个正方形。

四个(4,2)-MDS 码编码后的数据可以形成一个四层的棱柱,四棱柱的四个边对应着四个存储节点,边上的四个点所代表的数据存储于同一个节点。(下图a_0/b_0/c_o/d_0 都存在同一个节点)

耦合是将分层中不同数据进行线性组合,以实现最小修复开销。

图中被耦合的数据块用黄色表示,没有参与耦合的数据块用红色表示,两两耦合对应的数据块如上右图所示。如何选择耦合的数据块对文章中有也介绍,但为什么这样选择文章未提及。

下面谈谈什么是耦合,耦合即通过线性组合两个数据块,不管这两个数据块是原始数据块还是校验数据块。然后再将两个线性组合后的数据块(Coupled)取代两个原来未耦合的数据块(Uncoupled)。下图中(a_0, b_0),[a_0,b_0] 表示的就是数据块a_0 和b_0 的线性组合。注意:实际中Clay 码在节点上存储的是耦合后的数据,这样才能保证Clay 码的最优修复。

两个数据块的线性组合可以表示为数据块的乘法,解耦同理,如果用C(p) C*(p)表示两个耦合的数据块,解耦即乘以解耦矩阵,

γ 为不等于0的值,使得矩阵(在对应的有限域)满秩即可,比如2。

1.3 最优修复单点失效

下面以一个节点的修复来展示Clay 的最小修复开销,(4,2) 编码最小修复开销为(n-1)α/m = 3α/2 = 6,这也是其他MSR 的最小理论修复开销。下图给出了原a_2 数据块所在节点的修复过程。

Clay 修复该节点失效只需要第二层和第三层的剩余数据块(如上图(中)所示),修复步骤如下:

  1. 两个耦合的数据块(b_3,d_1) 和[b_3, d_1] 解耦得到b3 和d1,如上图(右)
  2. 第二层通过b1,b3 的MDS 解码得到b_0, b_2,第四层MDS 解码得到d_0,d_2
  3. 利用第二层中[a_2, b_0] 和步骤2 得到的b_0 得到a_2,同理得到c_2;

简单推导可以发现其他三个节点也可以以最小开销完成数据修复。

1.4 系统码

需要注意的是Clay 码这时虽然满足了所有节点的最优修复,但耦合的过程中某些数据已经不再是系统码,因为某些原始数据已经线性组合为校验数据。作者因此提出了一种“耦合-编码-再解耦”的方式来保证Clay 码的系统性(systematic),如下图所示。

首先对原始数据进行耦合,经过MDS 编码后再解耦,这样原始数据还是原始数据,但校验数据不再是MDS 编码后的校验数据了。

但如果是这样理解的话,会存在一个问题:MDS 编码前,耦合的校验数据为空,导致一个原始数据和空数据耦合,那么解耦后的数据能延续刚才的最优修复么?

换个角度,如果耦合的两个数据块中有一个是原始数据,是不是可以选课合适的耦合方程来保证原始数据不发生变化,即数据块a,b 耦合后可以是a,xa+yb(a 是原始数据)或xa+yb,b(b是原始数据)的形式么?但如果需耦合数据都是校验数据块呢?

这几个问题可以通过生成矩阵的方法来解释。

二 Clay 码的生成矩阵

本节用生成矩阵这个工具来展示如何实现Clay 码,即生成(4,2)-Clay 码的生成矩阵并验证其最优修复性质。

首先利用Clay 码“耦合 – MDS编码 – 解耦” 的变换过程构建其生成矩阵。因为三个变换都是线性变换,所以可以用三个矩阵来代替。

注意:前面我们提到解耦矩阵和耦合矩阵是互逆的,这是针对两个需要耦合/解耦数据块而言的,本节所讲的耦合、解耦矩阵是针对所有数据块,且需要在中建添加MDS 编码过程,所以本节耦合、结构矩阵大小不同,更不互逆。

|G| 是Clay 码的生成矩阵,那么

|G| = |U|×|GM|×|C|

|U|是解耦矩阵,|GM| 是MDS编码的生成矩阵,|C| 是耦合矩阵。

首先从最简单的MDS 编码矩阵 |GM| 开始,一层MDS 编码生成矩阵是一个2×2 单位矩阵和2×2 校验矩阵组合得到的4×2 的生成矩阵(如下左图所示)。四层的MDS 编码矩阵如下右图(在生成矩阵右边标出了该行向量对应的数据块)。

为了使得一个码字中原始数据部分放在一起,可以进行一个对齐操作,即将单位矩阵放在上面,新的生成矩阵为|GM|。

根据所对应数据块位置和耦合规则,可以得到解耦矩阵 |U|,如下图所示。

因为MDS 编码后,有16个数据块,所以解耦矩阵|U| 大小为16×16。

耦合矩阵是一个8×8 大小的矩阵(因为四层MDS码有8 个原始数据块,|GM| 大小是16×8)。那么利用|G| 矩阵上半部分是单位矩阵可解出耦合矩阵|C|

|G| = [I P] = |U|×|GM|×|C|  →    |C| = |I+L×GP|^{-1}

耦合矩阵|C| 是 |I+L×GP| 的逆矩阵,L 是解耦矩阵|U| 右上分块矩阵,GP是MDS 编码生成矩阵|GM| 下半部分的校验部分。

下面介绍程序验证过程。首先是测试当λ=2 时,两个数据块的耦合和解耦矩阵。

当λ=2 时,计算得到的耦合矩阵|C| = |I+L×GP|^{-1} 为

MDS 码采用RS码,|GM| 为

耦合矩阵乘积为 |GM|×|C| 为

最终(4,2)-Clay 码生成矩阵|G|为

最后,用程序验证了这个矩阵的最优修复性质,具体而言,首先将该矩阵等分为4×8 的4个子矩阵,依次失效每个子矩阵,从失效子矩阵以外的矩阵中选取行向量重建该失效子矩阵,所需要选取的子矩阵的行向量个数即需要重建数据块的数量,验证发现所有子矩阵修复都只需要6 个行向量,达到了最小修复开销。

计算某一点到连接两点的直线距离(矢量方法)

方法一:计算两点形成直线的斜率,斜率的负倒数是某点到该直线的斜率,通过计算垂足到该点距离得到某点到两点形成的直线距离。

方法二:矢量方法,好处是对于任意斜率都可以计算。

问题:已知点A (ax, ay),求到连接点B(bx, by)  和C(cx, cy) 的直线距离。

假设:建立坐标系,向量\vec{a}\vec{b} \vec{c}  分别对应三点的向量,如下图:

绘图1

图中C到直线AB 的垂线是紫色那根(假设垂足为D,图中未标注)。分别求得A 到B 的向量和C 到B的向量:

\vec{AB} = \vec{b}-\vec{a}    \vec{CB} = \vec{b}-\vec{c}

通过计算\vec{AB} \times \vec{CB} 可以推导出红色线段长度为$\mid\vec{CB}\mid \cos\theta $,因为

\vec{AB} \times \vec{CB}  = \mid\vec{AB}\mid \cdot \mid\vec{CB}\mid $ \cos\theta $

再通过勾股定理得到垂线距离:

$\mid CD\mid = \sqrt{\mid\vec{CB}\mid ^2 - (\frac{\vec{AB} \times \vec{CB})^2}{\mid\vec{AB}\mid}}$

$ = \sqrt{(cy-by)^2+(cx-bx)^2-\frac{((bx-ax)(bx-cx)+(by-ay)(by-cy))^2}{(ay-by)^2+(ax-bx)^2}}$

 

存储系统中的纠删码(Erasure Codes)—有限域(三)

有限域是纠删码中运算的基础域,所有的编解码和重建运算都是基于某个有限域的。在讲讲为什么纠删码不能基于一般常见的域(自然数域,实数域)之前,需要讲讲域的概念和有限域与其他域的区别。文章将以尽量简单的语言使得更多的读者能够看懂。

一、有限域的基本概念

1. 什么是域?

首先回顾下我们学习数学的历史:从刚开始接触数学时,我们首先学会一些符号(比如从1开始数到100,初中开始学习未知数x, y, z 等),接着开始学习基于这些符号的运算(加减乘除等),这些符号和运算就可以构成一个“域”。比如我们最早接触的是整数域,接着有理数域,然后在高中和大学还接触了虚数域,只不过当时老师没有告诉你这些是域而已。还有一些常见的数不构成域,比如自然数、素数、整数。

 

2. 域具有哪些性质?

在抽象代数中,域是一个非零的可交换环。在域上可以进行我们常见的加减乘除算法,一个域具有以下性质:

  • 加法和乘法的封闭性,加法和乘法结果还在域内
  • 加法和乘法的交换律;a + b = b + a  和  a · b = b · a.
  • 加法和乘法的分配律:a + (b + c) = (a + b) + c  和  a · (b · c) = (a · b) · c.
  • 加法和乘法的分配律:a · (b + c) = (a · b) + (a · c).
  • 存在加法和乘法的单位元素:a+0 = a 和 a·1 = 1(这里的0,1 不是自然数的0,1,代表着域上的加法单位元素和乘法单位元素)
  • 每个域上的元素都存在其负元和逆元: a+(-a) = 0, a·(a-1) = 1

这些性质和我们平时遇到的许多运算性质相同,这是因为我们很多运算就是在域上进行的。

继续阅读

和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 可以对此进行改进。

相关文件

求组合数、排列数等

最近写程序一直遇到组合数,排列数等问题。文章介绍程序实现全排列$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 可得到最短路径,即最优修复数据块集合。