2008年(8065)
分类: 服务器与存储
2008-05-09 11:04:42
Hamming Code ECC (汉明码错误检测与修正)
现在存储工程师要接触到RAID 系统中最为复杂的等级之一。RAID 2 之所以复杂就是因为它采用了早期的错误检测与修正技术----汉明码(Hamming Code )校验技术。因此在介绍RAID 2 之前有必要讲讲汉明码的原理。
汉明码的原理:
图 1-5 针对4 位数据的汉明码编码示意图
汉明码是一个在原有数据中插入若干校验码来进行错误检查和纠正的编码技术。以典型的4 位数据编码为例,汉明码将加入3 个校验码,从而使实际传输的数据位达到7 个(位),它们的位置如果把上图中的位置横过来就是:
图 1-6 汉明码原理
注:Dx中的x是2的整数幂(下面的幂都是指整数幂)结果,多少幂取决于码位,D1是0次幂,D8是3次幂,想想二进制编码就知道了
现以数据码1101 为例讲讲汉明码的编码原理,此时D8=1、D4=1、D2=0、D1=1,在P1 编码时,先将D8、D4、D1 的二进制码相加,结果为奇数3,汉明码对奇数结果编码为1,偶数结果为0,因此P1 值为1,D8+D2+D1=2 ,为偶数,那么P2 值为0,D4+D2+D1=2 ,为偶数,P3 值为0。这样,参照上文的位置表,汉明码处理的结果就是1010101 。在这个4 位数据码的例子中,存储工程师可以发现每个汉明码都是以三个数据码为基准进行编码的。图示就是它们的对应表(图1-6 ):
从编码形式上,存储工程师可以发现汉明码是一个校验很严谨的编码方式。在这个例子中,通过对4 个数据位的3 个位的3 次组合检测来达到具体码位的校验与修正目的(不过只允许一个位出错,两个出错就无法检查出来了,这从下面的纠错例子中就能体现出来)。在校验时则把每个汉明码与各自对应的数据位值相加,如果结果为偶数(纠错代码为0)就是正确,如果为奇数(纠错代码为1)则说明当前汉明码所对应的三个数据位中有错误,此时再通过其他两个汉明码各自的运算来确定具体是哪个位出了问题。
还是刚才的1101 的例子,正确的编码应该是1010101 ,如果第三个数据位在传输途中因干扰而变成了1,就成了1010111 。检测时,P1+D8+D4+D1 的结果是偶数4,第一位纠错代码为0,正确。P1+D8+D2+D1 的结果是奇数3,第二位纠错代码为1,有错误。P3+D4+D2+D1 的结果是奇数3,第三但纠错代码代码为1,有错误。那么具体是哪个位有错误呢?三个纠错代码从高到低排列为二进制编码110 ,换算成十进制就是6,也就是说第6 位数据错了,而数据第三位在汉明码编码后的位置正好是第6 位。
那么汉明码的数量与数据位的数量之间有何比例呢?上面的例子中数据位是4 位,加上3 位汉明码是7 位,而2 的3 次幂是8。这其中就存在一个规律,即2P≥P+D+1 ,其中P 代表汉明码的个数,D 代表数据位的个数,比如4 位数据,加上1 就是5,而能大于5 的2 的幂数就是3 (23=8,22=4)。这样,存储工程师就能算出任何数据位时所需要的汉明码位数:7 位数据时需要4 位汉明码(24>4+7+1),64 位数据时就需要7 位汉明码(27>64+7+1 ),大家可以依此推算。此时,它们的编码规也与4 位时不一样了。
另外,汉明码加插的位置也是有规律的。以四位数据为例,第一个是汉明码是第一位,第二个是第二位,第三个是第四位,1、2、4 都是2 的整数幂结果,而这个幂次数是从0 开始的整数。这样存储工程师可以推断出来,汉明码的插入位置为1(20)、2(21)、4(22)、8(23)、16(24)、32(25)……
说完汉明码,下面就开始介绍RAID 2 等级。
图 1-7 RAID-2 结构图解
RAID 2 等级介绍:
由于汉明码是位为基础进行校验的,那么在RAID2 中,一个硬盘在一个时间只存取一位的信息。没错,就是这么恐怖。如图中所示,左边的为数据阵列,阵列中的每个硬盘一次只存储一个位的数据。同理,右边的阵列(存储工程师称之为校验阵列)则是存储相应的汉明码,也是一位一个硬盘。所以RAID 2 中的硬盘数量取决于所设定的数据存储宽度。如果是4 位的数据宽度(这由用户决定),那么就需要4 个数据硬盘和3 个汉明码校验硬盘,如果是64 位的位宽呢?从上文介绍的计算方法中,就可以算出来,数据阵列需要64 块硬盘,校验阵列需要7 块硬盘。
在写入时,RAID 2 在写入数据位同时还要计算出它们的汉明码并写入校验阵列,读取时也要对数据即时地进行校验,最后再发向系统。通过上文的介绍,存储工程师知道汉明码只能纠正一个位的错误,所以RAID 2 也只能允许一个硬盘出问题,如果两个或以上的硬盘出问题,RAID 2 的数据就将受到破坏。但由于数据是以位为单位并行传输,所以传输率也相当快。
RAID 2 是早期为了能进行即时的数据校验而研制的一种技术(这在当时的RAID 0、1 等级中是无法做到的),从它的设计上看也是主要为了即时校验以保证数据安全,针对了当时对数据即时安全性非常敏感的领域,如服务器、金融服务等。但由于花费太大(其实,从上面的分析中可以看出如果数据位宽越大,用于校验阵列的相对投资就会越小,就如上面的4:3 与64:7), 成本昂贵,目前已基本不再使用,转而以更高级的即时检验RAID 所代替,如RAID 3、5 等。
图 1-8 RAID 2 特点