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 个行向量,达到了最小修复开销。

基于FPGA SoC 的内存系统中的纠错码

原文地址:https://www.altera.com/en_US/pdfs/literature/wp/wp-01179-ecc-embedded.pdf

原文名称:Error Correction Code in SoC FPGA-Based Memory Systems

下载地址wp-01179-ecc-embedded

备注:本文是Altera 和Micron 科技的共同编写的技术白皮书。

 

 

本文分析了1. 软错误的潜在原因和影响;2. Altera 和Micron 提出的一种错误检测和纠错方法,能够使得嵌入式系统能够容忍这类软差错。

 

引言

不断进步的半导体工艺技术使得嵌入式系统集成度、功能和性能都在增加。然而,性能的增长也带了巨大的开销,高性能系统的一个负面影响就是必须花费更多精力去处理软差错。随着集成电路供应电压的下降,使得它更容易受到电磁和颗粒辐射的影响。随着嵌入式系统内存大小增大到百兆量级,自然界alpha 粒子导致的软差错可能会超出可接受的限度。另外,现代接口速度超过Gb 每秒,大量的噪声和抖动会造成数据在传输线上写入/读出外部内存时发生错误。

 

内存比特错误来源

1. 比特单元软错误

通常,被写入数据的比特单位都以电荷值表示其编程值。当向某比特单位写入新值时,将重新编程和强制电荷值变为新值。一般来说,只要基本要求满足,如供电正常,对于动态内存刷新方法有效,内存比特单元内的编程值总是确定的。

但是,存储的电荷值会受到射入内存系统外部电荷的负面影响。宇宙粒子和大气中的原子碰撞产生能量射线可能会影响到存储的电荷值。要使得内存比特单元值跳变,必须向其注入足够多的电荷才能使得其表示为一个错误的逻辑值。

宇宙射线中百分之十以上由高能alpha 粒子组成,它们能够穿透几米厚的混凝土。芯片封装材料在衰减过程中会释放出低能alpha 粒子,因为能量小,其传播的距离和影响也小。类似地,gamma 射线也是表现为宇宙射线的一种高能粒子,由自然界衰减造成。地球的大气环境对于宇宙射线和粒子是一个天然、有重要意义的屏障,但绝不是天衣无缝的。结果就是,在高海拔,如山顶上、航空系统,大气环境能够提供的保护更少,发生软错误的几率更高。

这类因为外来能量注入无意地修改内存比特单位中数值叫做单粒子翻转(single event upset, SEU)。这类错误是软错误,这类错误的原因不是因为设备的缺陷造成的,而是由于设备所在环境的外部干扰造成。一旦正确的数据因此发生重写,几乎不可能再次经历SEU而翻转回来。这类事件的可能性极小,并且随着内存容量增加而增大。

2. 硬件错误

硬件错误被被归类为功能性错误。这类错误往往是可重复的、持续性的。一个包含了内存设备的系统被制造出后,应该是没有故障的,但随着系统寿命的增加,这种状况可能发生改变。各种因素,如频繁的温度变化、电压、高湿度和物理压力,都可能会引起系统中部件的失效。这类错误可能会表现为一个内存单元或一个印制线缺陷导致的比特卡顿(bit stuck,某位比特单位读出、传输结果总是1或0)。

3. 传输错误

传输错误发生在内存比特单位和功能性单元之间的读写数据路径上。这类错误一般是因为系统中短暂地超过系统设计余量的抖动和噪声造成,因此它们与设计余量、使用系统部件质量和系统对所在环境的电能敏感度有关。

物理连接到外部内存的电感、电容数量和导线长度比片上系统(System-on-Chip,SoC)或者内存系统中的内部布线要高出几个数量级。不过,部件内部还是可能发生传输错误。Alpha 粒子和gamma 射线能够影响感应放大器和内存比特线,导致获取到错误的数据值。

图一:传输错误

4. 数据错误的影响

内存数据的损坏对于嵌入式系统的运行通常是致命的。在基于处理器的系统中,内存错误会导致指令或数据流中的值不正确。现代处理器会检测到非法指令,通常会迫使系统重新启动。数据流中的错误可能会导致程序流出轨,往往会导致非法访问受保护的内存。这些事件在桌面系统中表现为“死亡蓝屏”或“core dump”。

尽管在嵌入式系统中崩溃是令人讨厌的,但是想要有个替代方法也不是那么简单。没有立即检测出的错误可能会长时间滞留在系统中。由于错误的数据用于计算新数据,未检测到的内存错误可能会倍增。而一旦检测到错误的数据,错误的起点以及造成的后续影响将很难确定。

嵌入式系统通常运行时间较长,并不像在台式计算机那样频繁地重新启动。这给嵌入式系统带来了额外的缺点:错误将随着时间推移而累积。数据错误和系统崩溃的负面影响很多:异常行为的系统会令用户烦恼,让顾客感到不快;维护成本可能会增加,因为客户的投诉会触发对不可重现错误来源进行昂贵的调查;突然的系统故障可能会造成重型机器周围的不安全环境,而且安全系统中的错误可能会导致意外的系统访问后门。

5. 嵌入式系统中错误的可能性

硬错误率和传输错误率是许多变量的函数。在较大系统中对于这类错误的研究比较成熟,但研究结果并不能直接将应用于其他系统。另一方面,已有很多研究发布了软错误率(Soft Error Rate,SER)结果。举一个实际例子,一个有1GB 内存的嵌入式系统的平均故障间隔时间的范围在一年几次和几年一次。

MTBF 还应该考虑到该领域系统数量。系统供应商则应该考虑一个给定时间段内可能发生失效设备的总数。假设10000 台设备的MTBF 是十年,那么意味着平均每年都将有1000 台设备遭受一次单比特错误。

这种错误率的可接受性取决于应用领域。在高海拔使用的应用开发人员将关注由于宇宙射线造成的较高的SER。军事,汽车,高性能计算,通信和工业客户将更关注错误率导致的安全性和可靠性的下降。在消费领域,一年的MTBF 则有时可以被接受。然而在许多情况下,错误率造成增加维护成本和不满意的客户数量是推动解决方案的关键因素。

 

提高容错能力

1. 传输错误

Altera®SoC FPGA 支持高达533 MHz(1066 Gbps)的DDR3。 DDR3 接口规范以及SoC FPGA 与外部存储器器件中实现的方式保证了错误率可以忽略不计,因为于DDR 规范所限定的范围内具有可靠的电路板设计和抖动和噪声控制。

谷歌与多伦多大学合作进行的大规模研究以及斯坦福大学的另一项研究表明,被分析的所有系统中大部分错误仅是由系统的一个设备子集造成。这些错误很可能是由过度的抖动或噪声引起的,或可能与系统及其组件的质量不合格有关。

传输错误发生的概率会随着接口速度的增加而增大,比如DDR4 或更高。随着功耗降低和接口速度提高,电源层面的电压和信号电平也随之缩小,抖动和噪声越来越难以控制。

随着更高的接口速度而增加,例如为DDR4及更高版本所定义。随着功耗降低和接口速度提高,电源层面的电压和信号电平也随之缩小,抖动和噪声越来越难以控制。 JEDEC 指出,对于DDR4 和GDDR5 的下一代存储器规范,抖动和噪声的影响已经促使该规范允许在一定的误码率和简化设计,特性和鉴定之间权衡。任何需要容忍的误码率都将用一种有效的方法来纠正发生的错误。

2. 软错误

因为软错误是不可避免的,所以已研发出了一些方法能够使得系统对这些错误具有抵抗力。也就是说,当一个错误发生时,它能够被检测、校正并传输校正后的值,因此系统可不中断地运行。这个壮举是通过向内存数据段中添加字节实现的,那么加宽的数据段携带了足够的信息来检测和校正错误。数据字段中增加的比特越多,能够被校正的错误也就越多。这使得纠错成为成本和期望可靠性的函数。能够修正一个错误和检验出两个错误的纠错方法即具有成本效益,又被证明在嵌入式系统中提供了出色的错误恢复能力。这种在工业界被广泛应用的技术叫做纠错码(Error Correction Code,ECC)。

3. ECC 的基本实现

通过增加内存容量,并在进出额外的外部内存的通道上增加有限的组合逻辑可以实现ECC。逻辑部分用于ECC 编码,采用非常成熟的多项式汉明(Hamming)算法。一个ECC 比特产生器可以为正在存储的数据生成ECC 数据,并将ECC 数据和普通数据一起存储。ECC 检测和校正逻辑函数被插入在内存的输出端,当从内存读取数据,这个函数将检验ECC 数据和普通数据的组合。如果没有检测到错误,则直接传输普通数据而不做任何改变。如果检测到一个错误,它将纠正普通数据内的错误比特位,并返回纠正后的数据,可选择性地抛出一个异常标志。当检测到两个错误时,则抛出一个异常标识,让系统因地制宜地去响应这个事件。

图2:ECC 内存容量更大且增加额外的逻辑部件

4. ECC 优势

能够纠单错和检测出双错具有很多好处。虽然ECC 是由大内存的SER 问题推动的,但它也增加了抵御其他类型错误的能力。一个硬件单错,比如内存中的比特卡顿或印刷电路板上的不稳定连接,都能够被ECC 完全掩盖,同样单比特传输错误也同样能被解决。核心是ECC 可以校正一个数据段中的错误比特。也就是说,ECC 可以正确地处理系统中的多个错误,只要任意一个数据段中发生不超过一个比特的错误。

另一个好处ECC 逻辑能够指出系统的健康状态。当ECC 逻辑纠正了一个数据段中的单错,它还可以向处理器发送一个故障状态信号,以利于处理器采去与系统所需的可靠性相关的措施。这一手段将系统降级转化为可调度的维护任务,而不是响应意外的、致命的系统错误状况。基于启发式概率,附表分析了有ECC 和没有ECC 的系统的估计软错误模型,表明ECC 有效地增加了MBTF,使其从短于系统寿命增加到比宇宙寿命更长。

表1:ECC 使得容单错能力大大提高

 

图3:外部DDR 内存没有错误校正的软错误MTBF

Altera 和Micron ECC 解决方案

1. 外部DRAM 的ECC

为Altera SoC FPGA 的外部内存添加ECC 功能只需要增加内存数据带宽。生成ECC 比特、错误检测和校正的功能都已经内置到SoC FPGA 的内存控制器中,这样的话,虽然带宽变大,但内存具备了ECC 功能。此外,在SoC FPGA 和外部内存之间的数据通道上已经布置了ECC,因此在数据通道上也可以恢复某些传输错误。

具有16-bit 或32-bit 宽的数据通道的外部内存系统在SoC FPGA 和外存之间分别需要存储额外的6 或7 个ECC 存储位。 对于这两种情况,Altera 架构简化为定义一个额外的1 字节的ECC 内存存储位。

2. ECC DRAM 的典型架构

一个由SoC FPGA 和外部存储器组成的现代嵌入式系统可能需要包含1 GB 的DRAM。 为了实现这种系统的高性价比的32 位宽内存接口,一个典型的DRAM 可以包括并行配置的一个8位宽器件和两个16位宽器件的组合。

图4:典型的外部DDR 内存架构

3. ECC NAND 闪存

外部的NAND 闪存可以连接到SoC FPGA 器件,既可以作为一个存储引导配置的内存,也可以作为存储应用程序的文件系统。NAND 闪存对软错误非常敏感,并且经常需要ECC 保护。不同于外部DDR 内存将数据段带宽变宽,NAND 闪存提供额外的存储缓冲区来保存ECC 数据。ECC 所编码的数据块也更大,如512 或1024 字节,那么SoC FPGA 设备则能够校正高达24 比特的错误。尽管实现方式被调整为更适应NAND 闪存的一般错误模式,但恢复方法还是类似于常规的SRAM 和DRAM。

4. Altera SoC FPGA 的错误恢复

ECC功能内置于SoC FPGA器件中,用于大量片上内存实例。L2 缓存,临时RAM,FPGA 结构内部的内存和外围上作为数据缓存的内存都带宽加宽并装备上了ECC 产生器和逻辑校正器件。由于这些是内置的,使用ECC 功能不需要额外的成本。 同样地,外部内存和NAND 闪存的ECC 也内置在SoC FPGA 中。数据和指令缓存在物理大小上相对较小,因此不容易发生软错误。因为它们需要高速运行,也为了读取L1 缓存时避免额外的延迟,系统使用更简单的奇偶校验方法。

FPGA 架构内的配置数据不是以增宽的数据段来组织的,因此也没有用ECC 校验。FPGA 架构内部有一个内置的硬件引擎,允许循环地检查配置数据的正确性,当检测到一个错误时会抛出一个异常标志。这种错误校正方法称作“擦洗(scrubbing)”,也是这类设备的一种工业标准方法。Altera SoC FPGA 具有支持系统级的错误恢复所需要的逻辑器件,并集成到设备中。通过仅扩展外部DDR 内存,可以获得对软错误和传输错误具有恢复能力的通用综合系统级方法。

图5:SoC FPGA 系统级的容错能力

 

总结

嵌入式系统中的内存可能受到宇宙射线的注入而导致比特位翻转,而过度的噪声和抖动也会导致传输错误,从而使得传输的数据不正确。虽然这种错误可能性很小,但随着内存容量、接口频率和带宽的增大,这类事件的可能性越来越成为挑战。系统级错误恢复能力日益成为高性能嵌入系统设计的考虑因素。Altera SoC FPGA 设备通过擦除(scrubbing)、奇偶校验和ECC 技术实现高容错能力。它能够很方便地为外部内存增加ECC 功能,特别是兼容了高性能系统中32-bit 位宽的外部DRAM 内存。增加ECC 实际上消除了内存对这些错误的敏感性,为系统级别的容错做出了重要贡献。

 

扩展阅读

“A Second Look at Jitter: Calculating Bit Error Rates,” Justin Redd, Maxim Integrated Products:
www.eetimes.com/electronics-news/4164171/A-second-look-at-jitter-Calculating-bit-error-rates
■ “Understanding the New Bit Error Rate DRAM Timing Specifications,” Perry Kelly, Agilent Technologies:
www.jedec.org/sites/default/files/Understanding%20BER%20based%20timing%20specifications%20Agilent%202011_1101.pdf
■ “DRAM Errors in the Wild: A Large-Scale Field Study,” Bianca Schroeder, University of Toronto, Eduardo Pinheiro and Wolf-Dietrich Weber, Google Inc.:
www.cs.toronto.edu/~bianca/papers/sigmetrics09.pdf
■ “Hard Data on Soft Errors: A Large-Scale Assessment of Real-World Error Rates in GPGPU,” Imran S. Haque, Vijay S. Pande, Stanford University:
http://cs.stanford.edu/people/ihaque/papers/gpuser.pdf
■ White Paper: Enhancing Robust SEU Mitigation with 28-nm FPGAs , Altera Corporation:
www.altera.com/literature/wp/wp-01135-stxv-seu-mitigation.pdf
■ On the Need to Use Error-correcting Memory,” Berke Durak:
http://lambda-diode.com/opinion/ecc-memory

存储系统中的纠删码(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

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

继续阅读

存储系统中的纠删码(Erasure Codes)—XOR 码和RS 码(二)

纠删码(Erasure Codes)能够总体上分为XOR 码和RS 码两类,XOR 码基于有限域GF(2),编、解码只需要按位异或(bit-wise exclusive-OR)即可完成,速度较快;RS 码基于有限域GF(2w),编、解码需要有限域上(后面的文章将详细介绍)的运算,速度慢于XOR码。常见的XOR码有:

  • 低密度奇偶校验码(Low Density Parity Code, LDPC)
  • 柯西-里德所罗门码(Cauchy-Reed-Solomon Codes,CRS)
  • RAID码(如RAID5、RAID6)
  • 奇偶码(EVENODD)
  • X-码(X-code)

按照编码理论来说,RS码是一个字长为n,维度为k,码字间距为n-k+1 的最小距离可分码(MDS codes),但为了能够让读者能够更容易接受,我们这里的RS 码是基于有限域上GF(2w)编解码运算的编码。

继续阅读

存储系统中的纠删码(Erasure Codes)—综述(一)

一、背景与挑战

数据的爆炸式增长使得存储系统的规模不断增加,存储设备的可靠性却一直没有得到显著提高(SSD 从SLC 到MLC 和TLC 可靠性不断下降,磁盘随着单位面积写入数据更多导致可靠性无法提升),从而给数据的持久化存储带来巨大挑战。另外随着存储系统规模的增大,存储系统中的冷数据的增加将远超过热数据的增加,如何安全保存冷数据,在需要的时候能够获取冷数据也成为存储系统中的重要挑战。下面是近年全球估计的数据量增长情况(GB,TB,PB,EB,ZB,YB…)。

2007    281 EB
2010     1.2 ZB
2011     1.8 ZB
2020      35 ZB

继续阅读

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

编码指的是冗余编码或者加密编码等。如果能够将大文件一次性读入内存进行编码的话,为什么要选择将连续的文件分成一块一块(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.