分布式存储中常见的容错机制:多副本、纠删码(RS、LRC、SHEC)

2024-02-08 12:20

本文主要是介绍分布式存储中常见的容错机制:多副本、纠删码(RS、LRC、SHEC),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 分布式存储中常见的容错机制
    • 浴缸原理
    • 多副本
    • 纠删码
      • RS
      • LRC
      • SHEC
    • 总结


分布式存储中常见的容错机制

浴缸原理

在存储领域中,通常我们会使用浴缸曲线来描述硬盘的故障率,如下图。
在这里插入图片描述

浴缸曲线

故障率随着时间变化,主要分为三个阶段:

  • 早期适配型故障:早期在引入新设备时,会出现系统、软/硬件、驱动等适配型原因的故障。当完成设备适配后,这一类型的故障会急剧下降。
  • 中期偶发型故障:中期设备正常运转时,故障率较低且运行稳定,偶尔可能会因为操作失误、次品设备等原因出现小概率故障。
  • 末期损耗型故障:在设备长期运转后,硬盘由于老化出现各种各样的问题,例如扇区错误/磁盘坏块(HDD)、闪存磨耗/LFT映射表损坏(SSD)等,此时会大规模出现硬件故障。

在分布式存储中,通常采用增加存储节点来扩充系统的容量,这就导致随着系统中的硬盘设备增加,维护的难度越来越大,故障的风险也随之增加,因此需要通过某种容错策略来确保数据安全。


多副本

在传统的分布式存储中,通常会采用多副本的容错策略,常见的用例如 HDFS 中就采用了三副本的策略 。
在这里插入图片描述

多副本

多副本顾名思义,采用了数据冗余的方式,将同样的数据拷贝到存储系统中的 N 个节点上。当某个节点的数据丢失时,只要系统中还有任意一个存活的副本,就可以将数据恢复。

其实现简单,数据恢复速度快,可靠性高(只要有一个副本存活,数据就不会丢失)。但也因此导致了严重的空间浪费,因此通常在存储小文件、热点文件时,才会使用多副本。


纠删码

纠删码(Erasure Code)是一种用于纠正数据丢失的校验编码。如下图,通常我们会讲输入数据拆分为多个数据块,再根据某种算法在数据块的基础上编码出校验块。当出现数据块丢失时,可以通过剩余的数据块和校验块进行解码,将丢失数据恢复回来。
http://img.orekilee.top//imgbed/store/store4.png

纠删码

由于编码、解码的计算流程复杂,开销过大,所以通常只有大文件和冷数据才会使用纠错码进行容错。


RS

RS(Reed-Solomon)是当前最为主流的纠删码算法,例如 Google GFS、Facebook HDFS、Dell EMC ECS、CEPH 就采用了这种算法。

由于 RS 算法应用较广,有许多比较出名的开源实现如:

  • Jerasure
  • ISA-L

RS 算法的核心思路在于将原始数据分为 K 份大小相同的数据块,并根据这些数据块计算出 M 份大小相同的校验块。 将所有的数据块和校验块分别存储在不同的节点中,当有任意块丢失时,只要保证有任意 K 块存在,则可以将数据计算恢复。

  • 编码流程
    在这里插入图片描述
    RS 编码流程

以 RS(5,3) 为例。如上图,首先会生成一个 n * (n + m) 大小的编码矩阵。矩阵有两部分组成,上半部分是一个 n * n 的单位矩阵,下半部份是一个 m * n 大小的校验矩阵(通常使用范德蒙矩阵或柯西矩阵)。通过将数据块和编码矩阵相乘,即得到一个 (n + m) * 1 的结果矩阵。其中数据块不变,生成 m 个校验块。

下面以范德蒙矩阵为例,这里简单描述一下解码流程,不涉及矩阵计算和代数原理。(感兴趣的可以研究下线性代数)

  • 解码流程

在这里插入图片描述

RS 解码流程1

以之前的数据距离,假设同时丢失了 m 个块——D1、D4、C2。
在这里插入图片描述
RS 解码流程2

此时需要从编码矩阵中删除掉丢失块对应的行,生成新的编码矩阵与结果矩阵。
在这里插入图片描述
RS 解码流程3

紧接着计算出编码矩阵的逆矩阵。
在这里插入图片描述

RS 解码流程4

同时对等式两边乘以逆矩阵。

在这里插入图片描述

RS 解码流程5

编码矩阵与逆矩阵相乘后得到单位矩阵。
在这里插入图片描述

RS 解码流程6

经过化简,此时得到原始数据 D,完成数据恢复。从上面的编解码流程可以看出,若要保证数据恢复,至多可丢失 M 个块(即删除 M 列不会影响矩阵计算)。


LRC

RS 虽然带来了大量的空间节省,但数据恢复的开销也急剧增大。当单数据块出现故障时,需要从 N 个节点上读取数据进行计算恢复。为了进一步降低恢复开销,Microsoft Azure 牺牲了部分空间,在 RS 的基础上封装出新的纠错算法 LRC(Locally Repairable Codes)。

LRC 算法的核心思路是将校验块拆分为全局校验块和局部校验块。 根据 K 个数据块计算出 M 个全局校验块,再将数据块平均分为 L 组,每组计算出一个局部数据块。

具体的原理这里不进行介绍,如果感兴趣可以去看看论文 Locally Repairable Codes

根据块类型的不同,数据恢复的开销也不一样:

  • 数据块
    • 单数据块丢失时,需要同组其他数据块和局部校验块进行恢复。
    • 多数据块丢失时
      • 同组:如果丢失的是同组的数据块,则需要根据所有剩余的数据块和全局校验块进行恢复。
      • 不同组:假设丢失的 N 个数据块处于不同组,则与单数据块流程一样,每组分别进行恢复。
  • 全局校验块:需要根据所有的数据块进行恢复。
  • 局部校验块:局部校验块丢失时,需要读取对应组的所有数据块进行恢复。

根据丢失的块类型,容错如下:

  • 允许所有的校验块同时丢失。
  • 允许 M 个块同时丢失。


SHEC

与 LRC 不同,CEPH 团队选择通过牺牲部分可靠性,近一步提高空间利用率,在 LRC 的基础上再次封装出新的纠错算法 SHEC(Shingled Erasure Code)。

SHEC 算法的核心思路是利用类似于滑动窗口的机制,每个校验块不仅包含对应数据块的信息,还包含上一个校验块的部分信息,因此某个校验块丢失时,也可以通过其他校验块进行恢复。 根据 K 个数据块,生成 M 个校验块,每个校验块中包含 C 个数据块。

具体的原理这里不进行介绍,如果感兴趣可以去看看论文 Erasure Code with Shingled Local Parity Groups for Efficient Recovery from Multiple Disk Failures

在这里插入图片描述

SHEC 算法图例

以上图 SHEC(10,6,3) 为例,即有 10 个数据块,6个滑动窗口,每个滑动窗口长度为 5。假设 D1 丢失时,我们可以通过读取 D2 ~ D5、P1 来进行数据恢复。而当 D6 和 D9 丢失时,可以通过读取同时包含这两个数据块的 P3、P4 校验块,以及 D5、D7、D8、D10 数据块,即可将数据恢复。

因此当一个数据块丢失时,仅需要读取 C 个数据块即可将数据恢复,并且同时支持丢失 (M * C) / K 个数据块丢。


总结

算法多副本RS(K,M)LRC(K,M,L)SHEC(K,M,C)
恢复开销(单数据块)1KLC
空间开销N(K + M) / K(K + M + M / L ) / KK + M
容错上限N - 1MMM * C / K
适用场景小文件、热点文件大文件、冷数据
  • 应用场景
    • 多副本保证了高可靠性以及低恢复开销,牺牲了空间。因此通常适用于高频访问的热点文件和小文件。
    • 纠错码降低了空间开销,但是带来了容错损耗和编解码开销。因此通常适用于大文件及冷数据。
  • 对比
    • 空间利用率:RS > SHEC > LRC > 多副本
    • 恢复速度:多副本 > LRC ≈ SHEC > RS
    • 可靠性:多副本 > RS ≈ LRC > SHEC

这篇关于分布式存储中常见的容错机制:多副本、纠删码(RS、LRC、SHEC)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/691018

相关文章

MySQL 中的 CAST 函数详解及常见用法

《MySQL中的CAST函数详解及常见用法》CAST函数是MySQL中用于数据类型转换的重要函数,它允许你将一个值从一种数据类型转换为另一种数据类型,本文给大家介绍MySQL中的CAST... 目录mysql 中的 CAST 函数详解一、基本语法二、支持的数据类型三、常见用法示例1. 字符串转数字2. 数字

Spring事务传播机制最佳实践

《Spring事务传播机制最佳实践》Spring的事务传播机制为我们提供了优雅的解决方案,本文将带您深入理解这一机制,掌握不同场景下的最佳实践,感兴趣的朋友一起看看吧... 目录1. 什么是事务传播行为2. Spring支持的七种事务传播行为2.1 REQUIRED(默认)2.2 SUPPORTS2

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os

Python中win32包的安装及常见用途介绍

《Python中win32包的安装及常见用途介绍》在Windows环境下,PythonWin32模块通常随Python安装包一起安装,:本文主要介绍Python中win32包的安装及常见用途的相关... 目录前言主要组件安装方法常见用途1. 操作Windows注册表2. 操作Windows服务3. 窗口操作

MySQL中的锁机制详解之全局锁,表级锁,行级锁

《MySQL中的锁机制详解之全局锁,表级锁,行级锁》MySQL锁机制通过全局、表级、行级锁控制并发,保障数据一致性与隔离性,全局锁适用于全库备份,表级锁适合读多写少场景,行级锁(InnoDB)实现高并... 目录一、锁机制基础:从并发问题到锁分类1.1 并发访问的三大问题1.2 锁的核心作用1.3 锁粒度分

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

MySQL之InnoDB存储引擎中的索引用法及说明

《MySQL之InnoDB存储引擎中的索引用法及说明》:本文主要介绍MySQL之InnoDB存储引擎中的索引用法及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录1、背景2、准备3、正篇【1】存储用户记录的数据页【2】存储目录项记录的数据页【3】聚簇索引【4】二

ModelMapper基本使用和常见场景示例详解

《ModelMapper基本使用和常见场景示例详解》ModelMapper是Java对象映射库,支持自动映射、自定义规则、集合转换及高级配置(如匹配策略、转换器),可集成SpringBoot,减少样板... 目录1. 添加依赖2. 基本用法示例:简单对象映射3. 自定义映射规则4. 集合映射5. 高级配置匹

MySQL之InnoDB存储页的独立表空间解读

《MySQL之InnoDB存储页的独立表空间解读》:本文主要介绍MySQL之InnoDB存储页的独立表空间,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、独立表空间【1】表空间大小【2】区【3】组【4】段【5】区的类型【6】XDES Entry区结构【

SQLite3 在嵌入式C环境中存储音频/视频文件的最优方案

《SQLite3在嵌入式C环境中存储音频/视频文件的最优方案》本文探讨了SQLite3在嵌入式C环境中存储音视频文件的优化方案,推荐采用文件路径存储结合元数据管理,兼顾效率与资源限制,小文件可使用B... 目录SQLite3 在嵌入式C环境中存储音频/视频文件的专业方案一、存储策略选择1. 直接存储 vs