纠删码与尾部延迟

主要观点:Jeff Dean 和 Luiz Barroso 的论文提出的对冲(hedging)技术及其优缺点,介绍了擦除编码(erasure coding)用于降低延迟、提高可用性和控制负载等方面的优势,强调擦除编码在系统中未得到充分重视和利用。
关键信息:

  • 对冲技术:简单地将相同请求发送到多个地方并使用第一个返回,可立即或延迟发送二次请求,缺点是要么发送两次要么一次,对低百分位延迟帮助不大。
  • 擦除编码:将数据分成 M 部分,可从其中任意 k 部分重建,在存储系统等中很常见,用于提高可用性和降低延迟等。
  • 擦除编码用于延迟:将数据分成 5 份,取 4 份可重构,请求开销 5 倍,带宽最差 20%,存储 20%,对尾延迟影响大,中位数延迟也降低约 20%。
  • 擦除编码用于可用性:单节点故障不影响可用性,随 k 增加可用性呈指数提升。
  • 擦除编码用于负载和扩展:具有灵活性,可控制负载分布,如 k = 2,M = 10 的方案,负载均衡效果好。
    重要细节:
  • 对冲技术在正常情况下可将二次请求数限制在约 5%,但系统相关延迟增加时可能会增加流量和取消流量,应结合令牌桶等限制额外请求。
  • 擦除编码中的最大距离可分码可从任意 k 部分重建数据,还有其他非 MDS 码具有不同特性。
  • 前向纠错(FEC)从噪声中提取有用数据的能力很惊人。
阅读 15
0 条评论