Boosting Full-Node Repair in Erasure-Coded Storage
0.Abstract
RepairBoost
调度框架
提高全节点修复性能
修复抽象
修复流量平衡
传输调度
提高35%-97.1%
1.Introduction
减少修复过程中I/O放大的问题方法
新的编码理论
高效的修复算法，修复过程并行化
利用机器学习的预测技术，故障发生前，利用修复算法主动修复数据
现有关注单块修复，全节点修复必须同时操作多个块的修复。
存在差距导致了一些问题
没有用全双工运输来饱和可用带宽
没有仔细安排块的传输来充分利用带宽
忽略了不同修复算法间的弹性合作
增加了实现的复杂性
如何无缝地部署现有的修复方法以有效地解决全节点修复问题，是擦除编码存储中一个具有挑战性而又至关重要的问题
通过RepairBoost来弥补这个差距，是一个调度框架，主要思想是通过修复有向无环图（RDAG），来形成一个单块修复，描述了网络上数据路由以及需要修复的请求块之间的依赖关系。
将RDAG分解为多个修复任务每个任务执行数据上传和下载，以促进修复
平衡全节点修复中的修复流量和带宽利用率
将多个RDAGs的修复任务小心地分配到相应的节点上，平衡整体的上传下载修复流量
协调修复任务的执行顺序，使可用上传和下载带宽的利用率达到饱和
2.Background
2.1Basics
介绍了纠删码的概念
本文讨论RS（k+m）也适用于其他编码
2.2 Repair
修复
full-node repair
degraded reads
本文关注full-node repair
修复代价比较高，研究减小修复代价
Repair-efficient erasure codes
LRC和再生码
Repair algorithms
利用未占用的带宽来加速修复
举了个例子，减小修复时间段
Proactive repair with erasure coding
有效修复的纠删码和修复算法，发生故障后才启动修复工作
可以通过机器学习预测，提前预测到要发生故障的节点，提前修复，本文主要研究后一种办法
2.3 Limitations
Limitation 1 (L1): Failing to utilize the full duplex transmission
上传和下载是独立的
图3
Limitation 2 (L2): Failing to fully utilize the bandwidth at each timeslot.
现有的修复算法可以在单个块修复中缓解下载瓶颈
全节点修复可能无意中再次导致链路拥塞
图4
Limitation 3 (L3): Inflexibility
很多修复算法平等地对待每个块，并使用相同地修复算法修复所有的块
没有考虑到不同的可靠性要求和热度倾斜问题
Limitation 4 (L4): Lack of a general framework for the full-node repair
没有通用的框架，同时支持不同类型的修复算法
3.RepairBoost Design
提高全节点修复性能
Assumptions
首先关注单节点故障，然后扩展到多节点故障
Overview
通过RDAG抽象出一个单块修复方案，通过支持多个RDAG的调度，实现灵活性，支持不同修复算法的协作，通用性（L3 和L4的情况）
3.1 Repair Abstraction
RDAG construction
抽象出了一个RDAG图
Repair process guided by RDAG
从叶子节点开始修复
Example
图五
Advantages of an RDAG
使用这个图的好处
适用于各种编码方案
描述了各种依赖关系
表示了每个顶点的修复任务
Discussion
RDAG和ECDAG的区别
3.2 Repair Traffic Balancing
整个系统的上传和下载流量应尽可能均衡
Retaining fault tolerance degree
保证容错
Balancing repair traffic
三种节点
叶子节点
根节点
中间节点
先映射中间节点和根节点，平衡下载流量
最后分配叶子节点，平衡上传流量
3.3 Transmission Scheduling
平衡整体上传和下载修复流量后，不一定能达到修复时间的下限。因为在修复期间，带宽可能不会在每个时间段被利用
最大流问题，图7
时间复杂度O(n2e)
3.4 Extensions
Multi-node repair
两种选择
逐个修复每个失败的节点
优先修复包含较多故障块或较多访问块的条带
Heterogeneous environments
可以根据环境改变
在轮询模式下采用以下方式进行传输调度
定位上传和下载数据时间最短的节点
根据可用带宽 进行排序
从拥有最大上传或下载带宽的链接中选择数据传输
Adaptation to network conditions
可以适应网络条件
4. Implementation
System architecture
图8
coordinator
位于元数据服务器
agents
存在节点上
Operating flow
向元数据服务器报告故障事件，协调块确定丢失块的id以及关联条带的身份，选择修复方案，发送给代理
代理收到后
读取本地存储的幸存块请求
将他们发送到指定的中继节点
解码（修复）丢失的块
repairboost将一个块分割成许多更小的包，使用多线程，做pipeline
Integration with Hadoop HDFS
在NameNode上部署coordinator
在DataNode上部署agent
5.Performance Evaluation
实验总结
吞吐量提高35.0-97.1%
可以协调多种EC
在低网络带宽的环境中更有优势
在异构和多故障修复种仍能保持其有效性
5.1Setup
EC2
17 virtual machine instances
m5.large
Ubuntu 16.04.7 LTS
two vCPUs with 2.5 GHz Intel Xeon Platinum
8 GB RAM
40 GB of EBS storage
先写数据，warm up
用擦除来模拟节点故障
从报告故障事件到修复和持久化所有丢失数据的时延
修复吞吐量
较高的修复吞吐量意味着较短的漏洞窗口
Erasure codes and repair algorithms
RS,LRC,MSR
CR,PPR,ECPipe
Selection of baseline
random selection(RAN),LRU-based selection approach
Default configurations
chunk size 64MB
packet 1MB
5.2 Experiments on Sensitivity
图9实验结果
5.3 Experiments onRepairBoostProperty
5.4 Experiments on Practicality
6.Related Work
Repair-efficient codes
Repair algorithms
Proactive repair with erasure coding
7.Conclusion
RepairBoost
一个调度框架