《存储秘史》之北斗七星阵（续1）

大家好，我是冬瓜头（QQ122567712）。email: myprotein@sina.com

msn myprotein0007@hotmail.com

我们看一下ppt，看看raid2具体的实现。值得考究的是，七星大侠并没有使用加减法来进行校验，而是用了一种算法复杂的所谓“海明码”来校验，这可不是信手拈来，而是有一定原因的。用加减算法进行校验，并没有对数据纠错的能力，也就是比如1＋0＋1＝10，这段数据在从磁盘被传输给控制器的时候，会一同传输，即数据位101，校验位10，此时经过控制器的校验，他会算1＋0＋1＝10，和一同传过来的校验位进行比对，如果相同，则证明数据都无误。但是此时如果在传输的过程中，电路受到干扰，数据位其中有一位畸变了，比如变成111了，也就是中间那个0变成1了，其他不变，此时控制器进行计算1＋1＋1＝11，和一同传过来的10不同，那么控制器会怎么认为？他可以认为数据位全部正确，而校验位被畸变，也可以认为数据位被畸变，校验位正确。那么他不能判断到低是哪种情况，所以不能修复错误。所以，七星引入了另一种算法，也就是海明码了，这个码使用的校验位和加减法相同，但是却能判断到低是哪一位出错了，能修正一位错误，但是如果有两位都错了，那么就不能修正了。具体请看ppt中的注释部分吧。

   七星大侠现在已经创造了三种阵势了，根据合一刀法所创的raid0，根据独孤掌所创的raid1，根据优雅合一剑法所创的raid2。而七星的郁闷之处，和当年优雅剑侠一样，就是苦于找不到一种一劳永逸的绝妙算法。raid2在传输数据位的同时，也需要将冗余校验位一同传输给控制器，这无疑是一个很大的开销，就为了保证数据不出错，传输大比例无用的码，实在不值得。raid2被创造之后，七星一直是整天昏昏沉沉，郁闷至极。



此秘笈版权所有唯一作者：冬瓜头






raid3阵势

话说到了清末，清政府开展洋务运动，师夷长技以治夷。还别说，真引入了不少好技术，比如布尔逻辑运算式。这话要从布尔说起，布尔有一次在家捣鼓继电器，他将多个继电器时而串联，时而并联，时而串并一同使用，逐渐模索出一些规律，比如两个继电器在串联时候，必须同时闭合两个开关，电路才能接通，灯泡才能亮，如果把开关闭合当作1，开关关闭当作0，灯泡点亮当作1，灯泡不亮当作0，那么这种串联电路得逻辑就可以这样写：1和1＝1，也就是两个开关都闭合，灯泡才能亮（等于1）。然后他还发现一个逻辑，如果在这个串联电路上，增加一个元件，如果两个开关都闭合得时候，电路反而是断开得，有人说不可能，那么就请仔细想一想，闭合开关，电路断开，这有什么难得么？完全可以通过继电器来实现，比如电路闭合之后，电磁铁通电，把铁片吸引下来，而这个铁片是另一个电路得开关，铁片下来了，另一个电路也就断开了，所以通过把这两个电路组合，完全可以得到这种逻辑：1和1＝0。而且还有一种逻辑，就是当两个开关任意一个闭合时，电路就通路，也就是并联电路。这种逻辑可以这么表达：1或1＝1，1或0＝1。经过多种组合，布尔得到1或1＝1，1或0＝1，1和1＝1，1和0＝0。这就是4种基本逻辑电路。这种“和”、“或”得运算，很多人都不理解，人们理解得只是＋－运算，因为＋－很常用。人们不理解得原因就是不知道除了加减算术之外，还有一种叫做“逻辑”得东西，也就是因果得运算。人们往往把1当成数量，代表1个，而在因果率中，1不代表数量，它只代表真假，其实我们完全可以不用1这个符号来代表真，我们就用中文“真”代表真，行否？当然可以，但是因为笔划太多，不方便，还是用1和0代表真假比较方便。其实磁盘上得数据，也不是1就代表1个，而是1代表磁性得取向，因为磁性只有两个取向，仿佛对称就是组成宇宙得基石一样，比如正负，对错等等。当因果率被用数学式子表达出来并赋予电路得物理意义之后，整个世界也就进入了新世纪得黎明，这个世纪是计算机得世纪。从数学到物理意义，我们仿佛看出点什么来，现代量子力学那一大堆数学式，折服了太多得科学家，包括爱因斯坦，到他去世前，爱因斯坦都没有理解量子力学所推演出来得数学式子，在物理上到低代表了什么意义。而且直到21世纪，也没有人给予这些式子以“目前”可理解得物理意义。我们可以想象一下布尔逻辑算式公布得时候，他的物理意义到低是什么？没人知道，甚至布尔自己估计也不知道，就只是一对式子而已。直到有一天一个人在家捣鼓继电器，突然风马牛不相及得想到了，这不就是布尔逻辑么？从此，数字电路，计算机时代，改变了我们得世界。那么我也可以在这里预言：谁能赋予量子力学式以可理解得物理意义，谁就是救世主，谁就能改变世界！！！！！

好，跑题了，我们再回来。七星在学习了布尔逻辑算式之后，也是稀里糊涂得把它用在raid2那一直困扰他的问题上面，看看能否有所突破。
   布尔运算中有一个xor运算，即1 xor 0＝1，1 xor 1＝0，0 xor 0＝0。布尔也总结出了类似加法结合率，加法交换率等等类似得逻辑运算率。并发现一些规律，比如：
1 xor 0 xor 1=0
0 xor 1 xor 0=1
大家看出点什么没有。假如第一个式子中，中间得0被掩盖，让你从结果，推出这个被掩盖得逻辑数字（0或者1，真或假），可否？右边给出了答案，完全可以！太神奇了，不管多少位，进行逻辑运算之后，还是一位，但是仔细一想也是理所当然，逻辑结果只有两个值，不是真，就是假，那么当然只用一位就可以代替了。大家可以自己算算，不管等式左边有多少位进行运算，这个规律都适用。但是在加减法中，如果右边仅有一位，不可能推算出被掩盖得数字，但是逻辑运算中却可以！！就是如此绝妙，有人问为什么，没人能解释为什么，就像问为什么有正电荷，负电荷一样，他们到低是什么东西，除了上帝，谁也说不清。可能上帝创造这个世界之后，发现只有物质是没有意思的，所以又创造了逻辑，有了逻辑的物质，就变得形形色色，千奇百怪。物质靠逻辑来相互作用，逻辑靠物质的相互作用来体现。

  七星大侠开始并不觉得这是真的，他反复演算，想举出一个反例，可是，徒劳无功。七星不得不为布尔得绝学所折服！同时也为西方得发达基础科学所赞叹！
   至此，困扰七星大侠多年得关于算法得问题，终于随着西方科学得涌入，得以顺利解决！解决得是那么完美，那么畅快！
   七星立即决定投入其下一代阵势raid3的创立过程中。他抓狂是的抛弃了那冗余的让人看着就不顺眼的raid2的那几块校验盘，只留下一块。按照raid2的校验思想，数据盘的每一个位之间做xor运算，然后将结果写入校验盘的对应位置。这样，任何一块数据盘损坏，或者任何一个其上的扇区损坏，都可以通过剩余的位和校验位一同xor运算，结果就是这个丢失的位。同样，8位一起校验，也就可以找出一个丢失的字节。七星做到这里，已经算是成功了，但是他还不太满足，因为他还有一庄心事，就是，raid2中，字节中的每个位，都分别分开存放在多个磁盘上，16位raid2，一次可以传2字节，要加大一次传输字节量，只有靠提高数据盘的数量，这种设计真是厌恶至极！所以七星大侠索性把一块磁盘一次可传输的最大单位设成以字节计，而不是位，至于一次具体多少字节，可以让使用者自己设置。但是这个字节数，一般要小于IO块的大小，因为如果大于IO块大小，那么一个IO就只用到一块磁盘了，用不到其他的，这样威力就会变小，所以七星在raid3阵势中，仍旧保持raid2的思想，也就是对一个IO尽量做到能够分割成小块，让每个磁盘都得到存放这些小块的机会，这样多磁盘同时工作，性能高。所以七星在raid3中，把block做的很小。这样每次IO就会牵动所有磁盘并行读写。所以到此我们了解了，raid2和raid3，他们都是每次只能做一次IO（在IO块大于block size的时候），所以不适合于多IO并发的情况，因为会造成IO等待。raid3的并发，只是一次IO的多磁盘并发存取，而不是指多IO的并发。所以和raid2一样，适合IO块大，SPI/IOPS之比大的情况。
  raid3也有缺点，和raid2一样，要达到raid3的最佳性能，需要所有磁盘的主轴同步，也就是说，对于一块数据，所有磁盘最好同时旋转到这个数据所在的位置，然后所有磁盘一股脑同步读出来，不然一旦有磁盘和其他磁盘不同步，那么会造成等待，因为这块数据就缺你的那一份，你还不快点，让大家都等着你，就不好了，所以需要主轴同步才能发挥最大性能。

看ppt

总结一下，raid3相比raid2的提升：校验效率，数据传输效率（因为每次多传一些数据，会提高效率），成本（使用磁盘更少了）。相对raid2缺点是：不支持错误纠正了，因为xor算法无法纠正错误。但是这个缺点已经不重要了，发生错误的机会少之又少，可以完全靠上层来处理错误了。

   正可谓：

与非异或同，

一语解千愁。

今朝有酒醉，

看我数风流！

raid4阵势
   七星自从学习了西方先进的基础科学之后，一发而不可收！以前已经是以钻研为乐，现在成了以钻研为生了。以前饿了还知道去要饭吃，现在七星已经感觉不到饿了，只要有东西让他钻研，就比吃饭了。
   话说某天七星正在闭目思考修炼，他回想起双刀时代的辉煌，回想起独行时代的凄苦，回想起优雅剑时代的中庸之乐。往事历历在目，再看看如今已经是穷困潦倒的自己，他不禁潸然泪下，老泪纵横。
   他给上面的三种思想，分别划分了门派，raid0属于激进派，raid1属于保守派，raid2、3属于中庸派。中庸派的思想一方面吸取了激进派的横分竖割提高威力的做法，一方面适当降底威力，来向保守派吸取了自保的经验，而创立了引以为豪的校验盘的绝妙技术。七星想，激进派似乎已经没有什么可以让中庸派再值得借鉴的地方了，倒是保守派的一个关键技术，中庸派还没有移植过来，那就是－－－－同时应付多个敌人的技术，虽然当年独行侠根本就没有意识到他的独孤影子掌可以同时应付两个敌人，因为独行侠可能一生都没有同时和两个人交过手。鉴于独孤掌的秘笈中也没有提及这门绝招，但是七星凭他多年的知识和经验积累，强烈的感觉到：并发IO早在独孤掌时代，就已经被实现了，只不过没有被他记载而一直被人忽略！要想有所突破，必须突破这一关！想到这里，七星立即再次开始了他的实验，钻研。
   七星分析发现，控制器发过来的指令，一次让磁盘读取或者写入的数据块，几乎很少有大于512K的，一般都是在64k左右。raid2阵法中，我只允许每个磁盘一次存取一个比特，这种设计，确实应该被淘汰了，且不说IO设计合理与否，就先看他的校验盘，就让人气不打一处来。那么再看看raid3，我在raid3的IO设计中，还是思维定势的走了raid2的老路子，也就是一次IO要尽量让每块磁盘都参与，而控制器的一次IO，数据块不会很大，那么想让每块磁盘都参与这个IO，就只能人为的减小block portion的大小。事实证明这种IO设计，在SPI/IOPS（比值，这个值是主讲人自创的）很大的时候，确实管用，但是现实应用中，很多应用的SPI/IOPS都很小，比如数据库查询等等。这种应用每秒产生的IO数目很大，如果所有磁盘同一时刻都被一个IO占用着，那么就不能并发IO，只能一个IO一个IO的来做，这样产生的等待，是不可容忍的。那么要实现并发IO，就需要保证阵中要有空闲的磁盘，未被IO占用的，让其他IO尽量去占有磁盘访问。所以唯一可以实现这个的就是增大block的大小，控制器的一个IO过来，这个IO块小于block大小，所以这个块不用分割，直接就写入一个磁盘上的block中，这个过程只用到了一个磁盘，而与此同时，其他IO可以和这个IO同时进行，前提是其他IO的目标不是这个IO要写入或者读取的磁盘，因为这块磁盘正在被这个IO占用。所以实现IO并发还需要增大数据的随机分布性，而不要连续在一个磁盘上分布，这一点不需但心，因为从raid0开始，竖条带就是跨盘编号的，比如extent0在1号盘，extent1在2号盘，这样就可以保证最大的数据分布随即性，增大IO并发的成功率。（这里七星大侠忽略了一个非常重要的地方，下面我们会看到）。
  在分析了这些的基础上，七星将raid3进行了简单的改造，简单的增大了block size，于是便创立了一个新的阵势，名曰：raid4

殊途同归

先           并

来           肩

后           携

到           手

先           并

进           存

先           并

出           取

天           海

经           誓

地           山

义           盟

！           ！

     raid5阵势

   话说七星大侠正在为创立了raid4阵法而欢喜的时候，麻烦事来了。很多江湖上的朋友都给他捎信说：修炼了raid4阵法之后，好像性能相对于raid3并没有什么提升，不管是SPI/IOPS的值多少。这个奇怪的问题，让七星大侠天天是如坐针毡，茶饭不思，中日思考这个问题的原因。他不停的拿着两块磁盘和一张纸（校验盘）笔划。时间一长，七星有一天突然发现，纸已经被他画的不成样子了，需要换一张。这引起了思维活跃的七星侠的思考，并发IO，并发IO，并发IO，他不停的在嘴里念叨着，突然，他两眼一睁，骂咧了一句之后，奋笔急书。
   七星大侠想到了什么让他恍然大悟呢？原来，七星经过思考之后，发现raid4确实是他的一大败笔，相对raid3没有什么性能提升，反而误人子弟，浪费了很多人的时间用于修炼一个无用的功夫。为什么呢？七星创立raid4的时候，太过大意，竟然忽略了一件事，每个IO每次必须占用校验盘，不管读还是写，校验盘每一时刻总是被一个IO占用，因为读写收据盘的时候，同时也要读写校验盘上的校验码。所以每个IO不管占用了哪块数据盘，校验盘他是必须占用的，这样，校验盘就显得相当的累，没有休息的时候，也叫做“热点盘”，非常容易损坏。虽然数据盘可以被IO并发，但是这已经没有意义了。除非不使用校验盘，那岂不是和raid0无异了？所以七星在raid4上掉进了一个误区。如今他终须醒悟了。

raid4什么也不是，不伦不类。七星郁闷啊，所以为了实现真正的并发IO，他这次是豁出去了，一定要创立新的阵法！！

七星分析，raid4的关键错误在于忽略了校验盘，校验盘，每个IO不管目标在哪个数据盘，但是他一定要读写校验盘，校验盘只有一块，他不读也得读！那么如果我让他有两块校验盘，他能否随即选择一块来读写？不行，这样岂不是乱套了，这两块校验盘之间也要同步起来，类似raid1，这样开销太大，成本太高。有没有其他更好的办法呢？冥思苦想，冥思苦想。不妨作一下演绎，首先，我们的目标是：并发IO，要并发IO，必须校验盘某一时刻可以被多个IO占用，这是必须的，否则就不是并发IO，但是“校验盘某一时刻可以被多个IO占用”，这句话不简直是扯淡么？一块磁盘怎么可以同时被多个IO占用？所以七星下结论，中庸派不可能实现并发IO。结论下了，七星也病了。彻彻底底的病倒了，他郁闷了。他不甘心，在他心中一定有一个完美的阵法，他是唯美主义者。他拿着那张已经快被画烂的纸，气愤至极，将纸撕成了两半。碎片就像七星那快要破碎的心，飘飘洒洒，不偏不倚，正好分别落到了地上的两把剑上，分别盖住了剑的一般。七星看着这情景，一直发愣，仿佛冥冥中一直有个神仙在指引着他似的，每次总是让七星恍然大悟，茅塞顿开。“老天助我啊！！哇哈哈哈哈哈！！”七星疯一般的从炕上滚落下来，他又找来一把剑，把纸撕成三块，分别盖住每把剑的三分之一，同样四把剑，把纸撕成4块，盖住剑的四分之一。。。。。，七星仰天长叹：“完美，太完美了！！！”。七星赶紧静下心来，他深知，必须经过深思熟虑的决定，才是正确的，不能重蹈raid4的覆辙。他花了半个月的时间，用树枝在地上画图演算，并仔细分析。一块磁盘同一时刻不能被多个IO占用，这是绝对真理，不可质疑的真理。那么以前也曾经试问过自己，把校验盘做成多块，可否？也不好，不完美。这次老天助我，让我把校验盘拆开，分割开，组合于数据盘之中，依附于数据盘，这样就完美的避开了那个真理，既然多个IO可以同时刻访问多块数据盘，而校验盘又被打散在各个数据盘上，那么就意味着：多IO可以同时访问校验盘（的“残体”）。这样就大大增加了多IO并发的几率，纵使可能发生多个IO所要用到的校验盘的“残体”可能同一块数据盘上，这样还是要IO排队等待，但是这种情况，根据几率原理，如果数据盘足够多，校验盘打散的“残体”就会分布的足够广泛，所以多IO并发的几率就会显著增大！他根据这个推断做实验，首先两个数据盘，把纸撕成两半，分别盖住两把剑的一半，这样，实际的数据盘容量其实是一把剑的容量，校验盘容量也是一把剑的容量，他们分别占了总容量的二分之一，这样，如果两个IO同时需要访问校验盘，那么他们访问不同残体的几率是三分之一，因为只有两块校验盘残体，第一种情况：可能两个IO同时需要访问1号残体，那么就不能并发，必须等待。第二种情况，两个IO需同时访问2号残体，那么同样也不能并发。第三种情况，第一个IO访问1号残体，第二个IO访问2号残体，可以并发。所以2块盘的系统，IO可并发访问校验盘残体的几率为三分之一。但是这只考虑了多IO访问校验残体的几率，  没有考虑多IO访问数据盘残体的几率，那么同样，我们作分析，也是三分之一，所以最终得出结论是：2块盘的系统中，IO可并发几率为九分之一。我们按照同样的方法分析3块盘的系统，此时校验盘残体占用了整个系统容量的三分之一，可以得出IO可并发几率为：九分之五。再复杂我就没法算了（我的笔没油了，不好意思），大家可以自己算算。可见3块盘的多IO并发率已经超过了一半，那么5块盘，10块盘的并发率一定还有提高。这只是考虑了两个IO并发，没有计算3个，N个的并发率公式。尽管这样，也是一次质的飞跃了。有了数学的支持，七星这次可谓是红星高照，脸色红润，病态全无，他把这个新创立的阵法叫做raid5。

正可谓：

心似剑，剑如心，

剑心合，方不侵。

分久必合合久分，

分分合合天地真！

  
看ppt

raid5也不是那么完美无缺的，可以说raid5是继raid1之后，第一个能实现并发IO的阵法，但是他又比raid1更加划算，raid5浪费的资源，在2块盘系统中，合raid1是一样的，都是二分之一，但是随着磁盘数量的增加，raid5浪费的容量比例越来越小，N分之一，而raid1则永远是二分之一。raid5相比raid0来说，都是利用条带来提升性能，但是又克服了raid0的鲁莽急躁，对数据用校验的方式来保护。但是raid5的设计思想，注定了他的连续读性能不如raid3，raid3由于block很小，每次IO总是能牵动所有磁盘为他服务，这样速度很快，但是raid5的block比较大，每次IO一般只使用了一块数据盘，而且raid5被设计为数据块都是先放满一个segment，再去下一个extent的segment存放，也就是小范围连续，那么如果象大文件