存档

文章标签 ‘vandermonde’

Reed Solomon Erasure Codes

2014年7月12日 没有评论

[latexpage]
上一篇文章《Finite Field Arithmetic》介绍了有限域上的运算,理解有限域上的运算,是理解erasure编码的基础。今天这篇文章就来介绍一下erasure编码。在分布式存储系统中,通常会通过多副本的方式来保证数据的可靠性,但是多副本带来的成本问题也是显而易见的。在类HDFS这样的系统中,通常数据都会保留三副本,三副本可以容有两副本故障的场景,但同时成本也是一副本的三倍。如何在保证同等的数据可靠性的前提下,减少副本数,降低成本,是分布式存储系统中很重要的一个课题。Erasure编码正是用来解决这个问题的,它能将副本降到1.x的同时,保证同等的数据可靠性保证。本文会以最常用的Reed Solomon erasure编码为例来介绍。

基本思想

erasure-codes
如上图所示,我们总共有$n$块盘,其中$k$块用来存放数据,m块用来存储erasure编码($k+m=n$),在上面的$n$块盘中,任意坏$m$块,都可以通过erasure编码将其余的恢复出来。也就是说,通常$k+m$的erasure编码,能容$m$块盘故障的场景,这时候的存储成本是$1+m/k$, 通常$m 阅读全文…