USTCReadingGroup——On-the-Optimal-Repair-Scaling-Trade-off-in-Locally-Repairable-Codes

Step 1

题目摘要引言

题目

对 Locally Repairable Codes（本地可修复码）的最佳 Repair-Scaling Trade-off 的探究

摘要

LRC 是针对 erasure coded storage（可擦除码存储方案）提升修复性能的可行编码方式的一种。可以减少修复带宽并可用于实践。文章分析了均衡 repair 和 scaling 的最佳 trade-off，设计了更优的分布策略，并在 LAN 环境下测试优于传统的布局方案。

引言

存储系统扩容与容错需求，Erasure coding 技术相较于传统备份，达到相同容错能力时所需代价更小（低冗余）。Erasure code 已经被应用很多商业存储系统，如微软 Azure 等。

Erasure code 以 original data blocks 为输入，可以产生一些附加的冗余块，它们与原始数据块子集可共同作用于恢复全部原始数据，这些冗余块被称为parity blocks。

Erasure coding 解决方案存在的问题就是修复过程中的 I/O 放大问题。LRC 时 Erasure codes 家族的新成员，设计的主要目的就是以进一步增加冗余存储的代价减小修复过程中的网路贷款与磁盘 I/O 消耗（Local）。

trade-off 探寻方式，以 coding 参数为变量平衡系统 performance 与 storage efficiency 的关系。

贡献

  • 第三节阐述 trade-off 的正是分析。先推导出单集群容错性限制下的放置策略，拓展到其他数据放置策略更贴近最优曲线。
  • 极端放置策略，最优 scaling 与最优 repair。在 LAN 上的试验结果表明两种极端情况下的优化性能。

基本理论概况

结论部分

Numerical Studies 和 Testbed Experiments 都证明了该放置策略的有效性。

实验室源码下载地址

GitHub 源码下载地址

回答基本问题

  1. 类别

对现有系统分析 Trade-off 并进行改进

  1. 内容

和 Erasure Code 相关，RS-Paxos，CRaft。

  1. 正确性
  1. 创新点
  1. 清晰度

分析优化，较为清晰

阅读选择

继续阅读

Step 2

细读笔记

集群存储系统体系结构

  • 两层体系结构
  • 一个集群划分成多个存储结点。
  • 一个集群内的多个节点通过同一台交换机进行通信，集群间通信通过一个网路核心。
  • 一个 Cluster 可以参考成一个机架或者一个数据中心。
  • 数据组织状态是 fixed-size 的，作为基本 r/w 单元。
  • 跨集群带宽比内部集群带宽要稀缺得多（more scarce）

Locally Repairable Codes

  • 4 parameters (k,l,g,c)
    • k 表示 data node 数量
    • l 表示 local parity 数量
    • g 表示 global parity 数量
    • c 表示 集群数

在实践中，发生多个集群同时挂掉的情况不常见，故障情况更多为 node failures 而非 cluster failures，采用 Azure Local Reconstruction Code 的形式。将 k 个 data node 划分为 l 份（ \(l \mid k\)），每\(b = \frac{k}{l}\)个划分出来的子块通过异或（XOR）产生一个 local 块。这 b+1 个成为一个 local group。

修复过程：

代价，代价平均值

Scaling 过程：

  • fast LRC： （相同 k）l 更小，更多的 local parity，修复表现增强
  • compact LRC： （相同 k）l 更大，更少的 local parity，提高存储效率
  • upcoding： fast 转向 compact 增大 l，减少 local parity 的过程
  • downcoding： compact LRC

问题记录

未读（且值得读）文献记录

  • Erasure Coding 技术
  • LRC 本地修复码

Step 3

思路复现

证明与推理复现

实验验证复现

ReadingGroup 笔记

BackGround

符合自己学习的内容

Motivation

再 repair 和 scaling cost 间进行一个 Trade-off

设计

引理 1 (k,l,g) LRC 可以用人任意 g+i 个 block failures（不等式证明）

一个简单结论，不能把 g+i 块放置在一个集群中

举例

  • upcoding cost 产生于 local parity 之间
  • repair cost 产生于 data 块与 local parity 之间

分析过程

就是一个单元变量，每次将 Local Parity 集中集群中分配一个 LP 块到其对应的 local group 中，一次函数。

验证过程

  • flat 放置
  • 改变块大小的一系列对比试验

总结

  • 优点
    • 关于 LRC 放置的优化
    • 建模 strictly derived
  • 缺点

绿色： b = g+1 （想把分配出来的 Local Parity 分配到 Local Group 所在机架上），恰好是边界条件

如果要实现一个 OPTr

不同的的 LRC 布置策略是不同的