2008-08-06 2:37| 
26 Comments | 本文内容遵从不知大家有过硬盘坏道没，反正有一次我是遇上了，珍贵的collection顷刻间化为乌有。信息时代，每个人都面临着一个新的问题：如何储存你的重要文件最为安全？大多数人会选择多弄它几个备份，虽然这种办法的效率和“性价比”都不高。有没有什么高效而又节省空间的办法来保证数据安全呢？最近，ttsiod写了一篇关于Linux小软件Rsbep的文章，里面提到的算法可以保证大段数据丢失以后仍然能复原原来的数据。算法基于一种叫做Reed-Solomon的编码方式。
Reed-Solomon编码的核心思想非常有趣：任意k个点都惟一地确定了一个最高次数为k-1次的多项式，如果我们把要传送的信息用一个多项式函数上的点来表示，那么我们可以用更多的点来描述这一信息，这样即使某些点的位置在传输过程中发生了错误，接收者也能根据其它的点来复原全部信息。考虑一个大小为n的有限域（由于一个字节有2^8=256种可能的值，n通常取256），其元素分别为x_0, x_1, x_2, ..., x_n；而我们要传输的数据长度为k。首先我们把这k个字节的数据当作有限域的前k个非0元素所对应的函数值，确定出它们所对应的k-1次多项式函数f；然后计算出n-1个非0元素的函数值f(x_1), f(x_2), ..., f(x_n)，作为最终的编码发送出去。注意我们的元素是一个有限域，因此多项式的值仍然在这个域里面（范围仍然是0到255）。在实际应用中，我们通常取k=223，这样的话223个字节的数据将加强为一段255字节长的数据，其中有32个字节是附加的信息。这种编码的纠错能力很强，即使有16个字节在传输中发生错误，我们也能通过剩余的信息复原出原始数据。
对于现今常用的数据储存方式，这样的算法仍然有它的局限性：数据丢失往往是一个扇区一个扇区地丢，而一个扇区就有512个字节，普通的存储方式将导致整段编码全部丢失。我们必需要避免把同一段自校对编码放在一个扇区里。rsbep强就强在：它把本该储存在同一个扇区的自校对编码分散存储到各个扇区去。得到整个数据编码后所需要的扇区数之后，我们重新排列整个编码中的所有字节，先顺序填满每个扇区的第一个字节，再依次填充每个扇区的第二个字节（就像栅栏密码一样）。如此一来，每一段（255字节长的）自校对编码都横贯255个扇区，倘若有一个扇区不能读了，那么我们丢失的就是512段编码各自在该扇区中的那一个字节。事实上，一个更强的储存方法是，在遍历扇区时也跳着进行存取，先填满第1, N+1, 2N+1, ...个扇区，再填充第2, N+2, 2N+2, ...个扇区。在ttsiod修改后的rsbep中，常数N=8，因此每第8个扇区中同一位置上的字节合在一起才组成一段编码。由于Reed-Solomon编码可以自我校对多达16个字节的错误，因此只有第i个、第i+8个、第i+8*2个、……、第i+8*16个扇区同时损坏才能造成真正的损失。这样的话，即使连续的128个扇区全部损坏，我们也能完整地恢复出原数据。
真的假的？
没有沙发了
第一个反应就是全息摄影技术应用到硬盘上面来了～
结果发现离全息还差那么一点点
后面那个分散的步骤跟IBM的内存技术完全一样
IBM可是在至少5年前就提出来了
现在好像叫Chipkill吧
那现在问题就到了磁盘读写效率上来了
如果没记错，Reed-Solomon编码是光盘使用的编码方式。好像有一部是散列交织（光盘肯定有，但是不是Reed-Solomon的一部分就不记得了），把连续存出的数据分散到一段存储空间中，这样如果存储空间有连续的损坏，对应到原数据就只是零散的损坏，可以分块纠错。
如果开发了多线程的cpu应该很快的
网络游戏都可以加速了...这样寄出去n个packet...丢了几个都没有关系...
backup full every month,
backup incremental every day.
很有含量很有趣。
哥伦比亚号上掉下的硬盘可以恢复出99%的数据，应该不用怕把。不过SSD还有IBM最近的赛道硬盘安全性还是挺高的，似乎不需要这种方法
半月前坏了分区表＝ ＝飘过
哥伦比亚号上掉下的硬盘可以恢复出99%的数据，应该不用怕把。不过SSD还有IBM最近的赛道硬盘安全性还是挺高的，似乎不需要这种方法
==============================================
那件事情RP度很高……而且用了好几年……
相信你珍藏的A如果丢失了不能快速恢复的话你会选择新的……不会去等几年的……
你的硬盘如果坏了, 估计你交钱NASA也不会给你恢复数据的..
没有13楼也应该没有14楼啊, 现在的楼都这样了.
有14楼啊。。。
Chipkill内存子系统的设计原理是这样的：在Chipkill技术支持下，单一内存芯片无论数据宽度是多少，只有一个给定的ECC识别码，它的影响最多为一比特。举个例子来说明，如果使用4比特宽的SDRAM，4比特中的每一位的奇偶性将分别组成不同的ECC识别码，每个ECC单元可单独用一个数据位来保存，也就是说这些识别码分别保存在不同的内存空间中。因此，即使整个内存芯片出了故障，每个ECC单元也将最多出现一比特坏数据。出现这种情况完全可以通过ECC进行逻辑修复，从而保证了内存子系统的容错性，保证了服务器在出现故障时，有强大的自我恢复能力。
Chipkill内存控制器所提供的存储保护在概念上和具有校验功能的磁盘阵列类似。在写数据的时候，把数据写到多个DIMM内存芯片上。这样，每个DIMM所起的作用和存储阵列相同。如果其中任何一个芯片失效了，它只影响到一个数据字节的某一比特，因为其他比特存储在另外的芯片上。出现错误后，内存控制器能够从失效的芯片重新构造“失去”的数据，使得服务器可以继续正常工作。采用这种Chipkill内存技术的内存可以同时检查并修复4个错误数据位，进一步提高了服务器的实用性。
与ECC技术相比，Chipkill内存技术更加有效，提高效率几乎达100倍，它提供对每个DIMM内存芯片纠正4比特错误的能力。如果内存发生错误，Chipkill将自动平稳地让出错的内存芯片离线，而服务器继续保持正常工作。
Chipkill内存技术与ECC技术一样，不仅原来的SD内存可以支持，现在主流的DDR内存也对它提供了支持。由于Chipkill内存技术是通过内存控制器提供的，所以可以在标准的ECC DIMM内存上实现，并且对于操作系统是透明的。在IBM x系列中的x445（如图3-9所示）和最新的x365（如图3-10所示）等子系列服务器中，都采用了Chipkill内存技术。
呵呵，您说大量的collection化为乌有，什么珍贵的collection？
估计大家猜的到。
光储存+网络服务器储存+一个盘 = 安全
光储存+网络服务器储存+一个盘 = 安全
mark
究竟是什么collection呢？
现在新出的A很多啊，没有了就看新的嘛。。
[...] 在密码学中，我们有一些更精妙的方案。最巧妙的方法是，把秘密文件编码为三维空间中的一个点，然后生成5个过该点的平面，每个特工持有其中一个平面方程。显然，两个特工在一起是无法获得原文件的，因为两个平面的公共点有无穷多个；但三个平面的交点是唯一的，因此任意三个人在一起都能解开原文件。 另一个有趣的办法利用了下面这个事实：知道m-1次多项式函数上的任意m个点就能恢复出整个多项式。因此，我们可以把文件编码为一个二次多项式f，然后把f(1)、f(2)、f(3)、f(4)和f(5)的值告诉对应的特工。任意三个特工碰头之后，只需要解一个三元线性方程即可恢复原文件。多项式的这一性质还曾用于数据备份当中。 利用数论知识我们还能得到一个简单的协议。中国剩余定理告诉我们，给出m个两两互质的整数，它们的乘积为P；假设有一个大整数M，如果我们已知M分别除以这m个数所得的余数，那么在0到P-1的范围内可以唯一地确定这个M。我们可以想办法构造这样一种情况，n个数之中任意m个的乘积都比M大，但是任意m-1个数的乘积就比M小。这样，任意m个模数就能唯一地确定M，但m-1个数就不足以求出M来。 Mignotte门限方案就用到了这样一个思路。我们选取n个两两互质的数，使得最小的m个数的乘积比最大的m-1个数的乘积还大。例如，在(3,5)门限方案中，我们可以取53、59、64、67、71这五个数，前面三个数乘起来得200128，而后面两个数相乘才4757。我们把秘密文件编码为一个4757和200128之间的整数，比如123456。分别算出123456模上面那五个数的结果，得到19、28、0、42、58。显然，知道任意三个同余方程就可以唯一地确定出123456，但仅知道两个方程只能得到成百上千个不定解。例如，假设我们知道了x模59等于28，也知道了x模67得42，那么我们只能确定在0到59*67-1内的解913，并且只能断定M是一个形如59 * 67 * k + 913的数，其中k的数量级和当初选的那五个数一样大。 Posted in Brain Storm Tags: 算法, 组合数学, 质数, 密码, 数论Trackback: http://www.matrix67.com/blog/archives/1261/trackback 我猜您可能还喜欢： 身份验证、中间人攻击和数字签名：浅谈密码学（上） [...]
半个月前因为因为硬盘坏轨无法重装系统而重买硬盘的飘过。
那么是不是就是说
假如不考虑需要恢复的话，那么那128个扇区的信息是冗余的
而可以不需要储存呢？
这128个扇区就浪费了。