raid6 theory summary3

9、分类讨论数据恢复过程

RAID6可以恢复两个磁盘同时失效时的硬盘数据。针对不同的磁盘失效情况，RAID6采取的数据恢复算法有所不同，因此，需要分类讨论数据恢复过程。可以将磁盘数据恢复过程分成如下四种情况进行讨论。

9.1  P盘和Q盘数据损坏

这种情况比较简单，由于原始数据部分是完好无损的，因此P和Q的值可以通过前面讲述的方法进行重新计算。

9.2  Q盘和一个数据盘损坏

这种情况的数据恢复方式和RAID5基本一致。由于P校验码是正确的，因此丢失的数据块可以通过P校验码恢复，这个过程和RAID5是完全相同的。数据块恢复之后，Q校验码就可以根据上述方法重新计算。方法如下：

假设某一条带中的D(0,1)数据丢失。

9.3  P盘和一个数据盘损坏

这种情况的数据恢复较上面两种都复杂。在这种情况下，首先可以采用Q校验码恢复丢失的数据块。待数据块恢复之后，再计算P校验码。整个计算过程如下（假设D(0,2)数据丢失）：

9.4  两个数据盘同时损坏

这种情况是重建过程中遇到的最复杂情况。现在假设数据盘1和数据盘2损坏，那么我们可以通过P、Q校验码得到两个方程，解算这两个方程可以得到损坏的数据信息，如下：

通过矩阵求逆等运算可以直接恢复丢失的数据。当求出一个数据之后，可以通过P校验值来恢复另外一个数据，计算方程如下所示：

D(0,1)和D(0,2)的计算方程：

其中：

通过方程(1)或者(2)得到D(0,1)或者D(0,2)，然后可以通过P校验码恢复另外一个数据，计算方法如下：

点击此处查看原文 >>

系统分类: 软件开发   |    用户分类:    |    来源: 原创

raid6 theory summary2

8、P-Q校验码的生成方法

此处重点讨论采用Reed-Solomon算法生成P、Q校验码。

Reed-Solomon编码的码字格式如下：

RAID6采用P+ Q的二维校验方式，其中P为XOR校验码，而Q校验码采用GF集合，运用线性代数等比较复杂的算法生成。下图为P、Q校验码生成的解算方程式，下面详细介绍P、Q校验码的生成方法。

8.1  P校验码的生成

P校验码的生成和RAID5一样。

下面这两个算式生成条带0和条带2的P校验码：

数据的更新：

假设对D(0,2), D(3,1)的数据进行更新。

8.2  Q校验码的生成

Q校验码的生成过程中用到了伽罗华域变换表，该变换表参见前表。

下面两个算式生成条带0和条带5的Q校验码：

算法举例：

如果存在如下的条带数据，计算编码结果。

Q码计算如下：

条带数据的更新，从而需要更新Q校验码，计算方法如下：

假设D(0,2), D(3,1)数据进行了更新，需要重新计算这两个数据条带的Q校验码。

点击此处查看原文 >>

系统分类: 软件开发   |    用户分类:    |    来源: 原创

raid6 theory summary1

1、RAIDx和RAID6的性能对比

1.1 RAID技术的特点

RAID技术主要有如下三个特点：

u      通过对硬盘上的数据进行条带化，实现对数据成块存取，减少硬盘的机械寻道时间，提高数据存取速度。

u      通过对磁盘阵列中的几块硬盘同时读取，减少硬盘的机械寻道时间，提高数据存取速度。

u      通过镜像或者存储奇偶校验信息的方式，实现对数据的冗余保护。

1.2 RAID6与RAID-X的性能对比

RAID6是RAID5的升级，通过双层校验码来实现高容错性。除了多一层校验码之外，RAID6的数据和RAID5一样被分散地存储到每个硬盘。因为RAID5只有一套校验码，所以如果两个硬盘都坏掉或在重建时发生错误，那么数据就会永远丢失。如果有了RAID6的保护，就算坏掉两个硬盘，数据也可以被复原。RAID6能够提供非常高的数据容错度，并且能够支持多个硬盘同时发生故障。

RAID5在掉一块盘时，不用停机还能保护数据，但是，如果掉两块盘，数据就会丢失。虽然掉两块盘比掉一块盘的可能性要小，但是当涉及到如下一些情况，掉两个盘的可能性还是会增大的。

1、SATA硬盘应用量的增长。SATA硬盘有低成本，大容量的好处，但是，其平均无故障时间比FC和SCSI硬盘的都短。这些硬盘使用率的增大，使同一时间掉两块盘的可能性变大了。

2、容量大，重建时间过长。在一块硬盘中，如果容量过大，意味着如果这块硬盘坏掉，需要重建数据的时间就越长，那么在长时间的重建过程中，掉第二块盘的可能性变大。

3、人为错误。当一块硬盘坏掉时，维护人员会用一块新盘来取代坏盘，但是一旦维护人员不小心拔错了硬盘，就会造成同时掉两块硬盘的状况，RAID数据将丢失。

4、硬盘数量的增加，很大程度上提高了硬盘预期故障发生率。

2、RAID6原理

RAID6是RAID家族中的新技术，是在RAID5基础上扩展出来的，所以同RAID5一样，数据和校验码都是被分成数据块然后分别存储到磁盘阵列的各个硬盘上。RAID6加入了一个独立的校验磁盘，它把分布在各个磁盘上的校验码都被分在一起，这样RAID6磁盘阵列就允许多个磁盘同时出现故障，这对于数据安全要求很高的应用场合是非常必要的。这样搭建一个RAID6磁盘阵列最少需要4块硬盘。但是RAID6并没有改善RAID5写入性能不佳的情况，写入缓存的应用仅仅能对于这个缺点进行一定程度的弥补，但是并不能从根本上解决问题。在实际应用中，RAID6的应用范围并没有其他的RAID模式那么广泛，如果实现这个功能一般需要涉及更加复杂、造价更昂贵的RAID控制器。

RAID6的随机读取性能：很好（当使用大数据块时）

RAID6的随机写入性能：差，因为不但要在每块硬盘上写入校验数据而且要在专门的校验硬盘上写入数据。

RAID6的持续读取性能：好（当使用小数据块时）

RAID6的持续写入性能：一般

RAID6的优点：快速的读取性能，更高的容错能力。

RAID6的缺点：很慢的写入速度，RAID控制器在设计上更加复杂，成本更高。

目前，实现RAID6标准有多种算法：Reed-Solomon P+Q 、 Double Parity和EVEN-ODD编码算法。RAID6是第一个允许掉两块硬盘的RAID标准，在RAID5的基础上大大提高了平均故障时间（MTDL）。

热交换和热冗余

在RAID系统中一般具有热交换和热冗余能力，热交换允许在不关闭系统或者电源的前提下更换故障硬盘，当然更换上的新硬盘也可以被系统动态的石碑出来并且正确的配置和添加，而这些都不需要重新启动计算机。热冗余一般用于不适于热交换的场合。这种设计一般是在故障出现之前就在计算机中配置了额外的硬盘，当有硬盘出现故障的时候，这块冗余的就可以自动替代故障的硬盘位置，对于这样的系统在系统关闭之前是不能把损坏的硬盘拔下来的。

3、双重纠错编码方法

目前，适用于磁盘阵列的双重冗余纠错码主要有三种：2D方案（二维奇偶校验），RS（Reed-Solomon）编码以及EVENODD编码。

3.1  2D方案

二维奇偶校验方法将数据磁盘组织成m*n矩阵，然后分别在水平方向和垂直方向都进行奇偶校验编码的方法，若数据盘是m*n个，则用于存放校验信息的磁盘数为m*n。二维奇偶校验采用简单的异或运算，容易实现。

磁盘校验方法如下：

1.      如果同一行的两个磁盘出现故障，可以通过列校验盘恢复这两个磁盘中的数据；或者在通过列校验盘恢复了其中一个磁盘的数据之后，再通过行校验盘恢复另一个磁盘中的数据。

2.        如果同一列的两个磁盘出现故障，可以通过行校验盘恢复这两个磁盘中的数据；或者在通过行校验盘恢复了其中一个磁盘的数据之后，再通过列校验盘恢复另一个磁盘中的数据。

3.        如果出现故障的两个磁盘分属于不同行和不同列，这时任意选择行校验盘或列校验盘来分别恢复这两个磁盘中的数据。

在这种方案中，冗余率高达 (m+n)/(m*n + m + n)，而存储空间利用率仅为(m*n)/(m*n+m+n)，因此，该方案并不实用。

3.2  EVEN-ODD编码

在二维奇偶校验法中采用了两种类型的冗余：水平冗余和垂直冗余。另一重巧妙的方法是使用水平冗余和对角冗余来设计校验码，这种方法为EVEN-ODD编码。该编码有m+2个磁盘，其中前两个磁盘为数据盘，最后两个为校验盘，当然也可以按照RAID5的方式将校验数据均匀分布在m+2个磁盘上，为了便于描述，下面采用固定校验盘的方式，即相当于RAID4方式。

用EVEN-ODD编码构造双容错磁盘阵列可以看作(m+1)*(m+2)维阵列，矩阵每一列对应一个盘，共m+2个磁盘，前m个磁盘存放数据信息，后两个盘存储冗余校验信息，每个磁盘均含有m-1条带单元。

（一）水平校验

（一）对角线校验

3.3  Reed-Solomon编码

该部分内容将重点讨论，因此独立成节。

3.5  各种纠错编码方法的优缺点

判断双重纠错码的优劣需要从以下几个方面进行考虑：读写性能，冗余磁盘的个数，数据平均修复时间以及小写性能。

各种纠错编码比较

二维奇偶校验码简单，易于实现，但是构造的阵列性价比低，一般不采用此方法，RS码和EVEN-ODD码为最优冗余编码，只需两个冗余信息盘就可以纠双错，其中，RS编码、译码较EVENT-ODD复杂，一般需要用硬件电路实现，但是RS码小写性能好，因此RS码适用于硬件实现的阵列控制器中。EVEN-ODD码编、译过程较RS码简单，只有异或操作，但是小写性能差，因此，EVEN-ODD适用于实时性较强的连续数据存储，如：摄影图像存储等。——摘自冯丹的论文，《电子学报》。

4、条带数据存储方式

RAID6条带数据的存储方式延续了RAID5的方式，与RAID4的条带存储方式不一样。如下图所示，他改变了传统采用两个固定盘做校验的方式，避免了校验盘读写的瓶颈。

点击此处查看原文 >>

系统分类: 软件开发   |    用户分类:    |    来源: 原创

大型软件开发一定要做好设计

最近一个月一直在忙活一个Linux内核软件的稳定、BUG的修改。这个项目的确做的很辛苦，改别人的东西还不如自己开发，这种体会是在是太深了。
从事Linux内核软件的开发已经接近两年了，从对Linux一无所知到内核机制的整体把握，其中经历了很多的故事，完成了3个大中型软件的项目。这一段时间我一直在考虑，如何更加高效的去设计内核程序？如何更加高效地去测试内核程序？总的来说，我认为内核程序的开发，设计阶段实在是太重要了！设计阶段一定要考虑清楚模块的划分（任务的划分），上下文一定要搞清楚，要十分明确那个任务在那个上下文中运行，哪些资源在哪些上下文中用到，只有搞清楚了这些，我们才能很好的设计数据结构，很好的设计锁的机制。如果在设计的前期这些东西不是很明确，那么开发出来的东西不是效率不高，就是漏洞百出。最后导致东补西堵，整个实现乱成一团，实在是太煞风景了。
我是搞硬件出身的，并且现在也一直在搞硬件设计。软件的设计和硬件的设计在某种程度上是一致的。现代软件设计都是多线程设计，并且往往架构在多核平台之上，能够真正实现线程的并发运行（多个硬件线程，本质上是多个异步时钟域），所以软件的设计就必须划分好线程，划分线程的方法很多，简单的方法是任务划分，当然也可以采用数据域的划分方式。不管采用哪种划分方法，我认为线程与线程之间尽量保持弱耦合关系，尽大可能地让线程并行起来，线程之间共享临界区的数据。这样的一个模型和硬件设计是一致的，多个时钟域通过总线共享数据。在这样的一个模型中，最重要的任务是划分时钟域，设计好总线，即设计好仲裁机制，让每个时钟域能够一致的访问数据。
我现在手头这个Linux driver，就是“仲裁机制”没有设计好，在设计之初没有考虑好，经过长时间的补丁，最后就干脆加了若干把大锁，将多个时钟域串行起来，如果不考虑driver底层某些瓶颈的话，这样的机制实在是太滥了，如果底层瓶颈不存在，无论增加多少个CPU，这个driver的性能将无法得以提升。咳，真有冲动，重新将这个东西设计一把。
以后希望和大家一起共同探讨如何高效设计并发软件以及如何高效测试并发软件的话题。yea...再接再厉！！

点击此处查看原文 >>

系统分类: 软件开发   |    用户分类:    |    来源: 原创

不错的logic design study documents

这篇logic design的文章写的不错，正在阅读之中。。。
地址：http://www.cis.upenn.edu/~milom/elements-of-logic-design-style/

点击此处查看原文 >>

系统分类: CPLD/FPGA   |    用户分类:    |    来源: 原创

Linux SCSI中间层分析

点击此处查看原文 >>

系统分类: 软件开发   |    用户分类:    |    来源: 原创

tiloog's blog开场白

祝贺一下，我的中文blog终于在别人强烈的推动下启动了。在大学的时候，曾经建过个人站点，那个年代个人站点风风火火。后来由于免费个人站点的空间没了，所以我的“虚拟仪器研发网”进入了历史的博物馆。再后来建过blog，但是由于工作时间的原因，一直没有很好的管理过:<
tiloog's blog我要坚持下去，主要想在这里记录自己对专业方面的一些体会和认识，主要涉及逻辑电路的设计、内核软件的开发以及嵌入式系统、前端模拟电路设计及测试测量（哇，一大堆，实际上主要围绕“高速互联、网络”这个主题展开:>）。我个人比较喜欢硬件电路的设计，特别是模拟电路和逻辑电路设计这一块，但是，由于我目前的工作主要集中在内核开发这一块。所以，以后有关电子方面的很多内容都可以在tiloog's blog进行交流。多谢大家对我的支持与关注。。。。在此，谢过了！！！！！！

点击此处查看原文 >>

系统分类: 自由话题   |    用户分类:    |    来源: 原创