纠删码和副本策略的定量比较

文章来源:Erasure Coding vs. Replication: A Quatitative Comparison

  • Po      一个块可用的概率
  • n      分片的总数
  • m      需要重建分片的个数
  • N      所有机器的总数目
  • M      当前不可用机器的数目

    $$P_{o} = \displaystyle\sum_{i=0}^{n-m} \frac{\binom{M}{i} \binom{N-M}{n-i}}{\binom{N}{n}}$$

一个数据块可用的概率等于将不可用分片放置在不可达机器上的方法乘以将可用分片放置在可达机器上的方法中能够还原数据块的总方法数,除以将所有分片防止在所有机器上的方法数。以一百万机器为例,如果十分之一的机器不可达,如果采用两个副本的策略,数据块可用率为99%;如果是n=32、R=0.5 的纠删码可以达到9 个九的可用性。

 

  • Sx        存储系统(x in {replica,erasure})的总容量,即:Sx = total bytes stored in system x
  • BWx    存储系统的总带宽,即:BWx = BWx_write + BWx_repair
  • Dx       存储系统需要维持(修复、写和读)率,即Dx = Dx_write + Dx_read  + Dx_repair
  • B        存储系统中数据块总数(假设都是固定大小b)
  • N        所有用户的数目

存储系统中数据块的数目B 可以用用户数目N 与写入速率wBlocks/s 来表示:

    $$B = N \cdot \frac{wBlocks}{s} \cdot total seconds$$

有了以上假设可以得到副本策略和纠删码策略存储系统所需要的容量:

Srepl = b · R · B        (b 是块文件大小,R 是副本个数)

Serase = b · B/r      (r = k/n 为码率)

副本策略和纠删码策略存储系统所需要的带宽:

BWrepl = b · R · N · w·Blocks/s + Srepl /erepl

BWerase = b · 1/r · N · w·Blocks/s + Serase /eerase

其中,ex 是系统的修复周期。进一步计算需要磁盘寻道速度,其中dbsz 是每个磁盘块大小。

    $$D_{repl} = (R \cdot N \cdot \frac{wBlocks}{s} + R \cdot \frac{B}{e_{repl}} + 1) \cdot \frac{b}{db_{sz}}$$

    $$D_{erase} = (n \cdot N \cdot \frac{wBlocks}{s} + n \cdot \frac{B}{e_{erase}} + k) \cdot \frac{b}{m \cdot db_{sz}}$$

有了上面存储容量、带宽和磁盘速率的比较,对比副本策略和纠删码策略存储系统有:

    $$\frac{S_{repl}}{S_{erase}} = R \cdot r$$

    $$\frac{BW_{repl}}{BW_{erase}} = \frac{R \cdot DR_{repl}}{\frac{1}{r} \cdot DR_{erase}} = R \cdot r$$

    $$\frac{D_{repl}}{D_{erase}} = \frac{(R \cdot DR_{repl} + 1) \cdot \frac{b}{db_{sz}}}{(n \cdot DR_{erase} + k) \cdot \frac{b}{k \cdot db_{sz}}} = \approx R \cdot r$$

之前R 可能用来表示码率,这里再重申下,这里表示的是副本策略中的副本数目,r 才是表示的码率。

系统的平均无故障时间可以由磁盘上块的平均无故障时间来计算:

MTTFsystem = MTTFblock / B>>total seconds

文章举了一个极端的例子,假设平均写入速度为35MB/hr ,用户数为224 磁盘块大小(b)和纠删码数据块大小(dbsz )都是8 KB,erepl = eerase =4 months ,且要保证MTTFsystem >1000 年。我们可以计算出共计有B = 1017 个数据块。因此每个数据块的MTTF = 1017+3 = 1020 年。参考了磁盘块的故障率计算出R=22 或者[64,32] 纠删码满足情况,进一步计算出,在这样极端情况下纠删码的存储开销,带宽开销和磁盘速度都要比副本策略存储方案小一个数量级:R · r = 11 。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据