知识卡片
LRC不能按校验数估容错
书中10数据块、4个RS校验再加2个局部校验形成16块的例子,局部性可降到5,最小码距为5,因此保证任意4块损坏可恢复,并非任意6块。相对14块RS增加约14.3%存储;省略第三个局部校验依赖事先设计的线性关系,不能任意删一个校验仍保留全部性质。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 分布式文件系统 · 查看原书依据
上述情形下LRC的最小码距是5,也即对于所有16个数据块来说,最多允许任意4块数据同时发生损毁而数据可恢复。关于最多允许同时损毁4块数据,这一点比较容易看出:假设损毁的4块数据中不包含LRC生成的局部校验数据块,那么RS编码即可做到这一点。如果损毁的数据块中包含S 1 和S 2 ,则可以通过RS编码首先恢复损毁的原始数据块,而由这些恢复好的原始数据块生成S 1 和S 2 。另外一个值得思考的问题是:既然增加了校验数据,那么最小码距可否达到6?即最多允许同时损毁5块数据呢?这在有些情形下可以,但是存在反例。比如如果第1组数据块中损失4块,第2组数据块中损失1块,可以根据局部校验码S 2 和第2组其他数据块首先恢复第2组损失的那个数据块,然后根据RS编码可以恢复第1组中损失的4块。但是如果数据损失的情形是第1组损失2块,第2组损失3块,那么明显是无法恢复的,读者可以思考其原因。由此反例可见,这个例子中LRC的最小码距只能是5。
参考来源
- 位置:《大数据日知录:架构与算法》第8章《分布式文件系统》,原文段落262(OEBPS/text00013.html)。
- 结论依据:本卡说明书中机制及其适用条件;出版时版本、目标数字与架构状态不作为当前普遍保证。
- 原始内容:上述情形下LRC的最小码距是5,也即对于所有16个数据块来说,最多允许任意4块数据同时发生损毁而数据可恢复。关于最多允许同时损毁4块数据,这一点比较容易看出:假设损毁的4块数据中不包含LRC生成的局部校验数据块,那么RS编码即可做到这一点。如果损毁的数据块中包含S 1 和S 2 ,则可以通过RS编码首先恢复损毁的原始数据块,而由这些恢复好的原始数据块生成S 1 和S 2 。另外一个值得思考的问题是:既然增加了校验数据,那么最小码距可否达到6?即最多允许同时损毁5块数据呢?这在有些情形下可以,但是存在反例。比如如果第1组数据块中损失4块,第2组数据块中损失1块,可以根据局部校验码S 2 和第2组其他数据块首先恢复第2组损失的那个数据块,然后根据RS编码可以恢复第1组中损失的4块。但是如果数据损失的情形是第1组损失2块,第2组损失3块,那么明显是无法恢复的,读者可以思考其原因。由此反例可见,这个例子中LRC的最小码距只能是5。