超强的储存方法：即使连续128个扇区全部损坏也能恢复原数据

不知大家有过硬盘坏道没，反正有一次我是遇上了，珍贵的collection顷刻间化为乌有。信息时代，每个人都面临着一个新的问题：如何储存你的重要文件最为安全？大多数人会选择多弄它几个备份，虽然这种办法的效率和“性价比”都不高。有没有什么高效而又节省空间的办法来保证数据安全呢？最近，ttsiod(http://ttsiodras.googlepages.com/rsbep.html)写了一篇关于Linux小软件Rsbep(http://www.s.netic.de/gfiala/dvbackup.html)的文章，里面提到的算法可以保证大段数据丢失以后仍然能复原原来的数据。算法基于一种叫做Reed-Solomon(http://en.wikipedia.org/wiki/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个扇区全部损坏，我们也能完整地恢复出原数据。