[导语] EC(Erasure Coding, 纠删码) 是现代分布式存储系统一个重要的能力。它可以保证在相同数据持久度的基础上大幅提高存储空间利用率，对降低存储成本有极为重要的意义。腾讯大数据存储团队全程参与了 Ozone 社区 EC 的设计与开发，并先于社区在内部完成了 EC offline recovery 的开发和测试。本文主要讲解 EC 在 Ozone 中的设计与实现，并讨论其中的利弊权衡。
0.引言
Apache Ozone 做为 Hadoop 生态的下一代分布式存储系统，是 Hadoop 生态目前最活跃的项目之一。Ozone 具有高度可扩展性，非常适合数据分析，大数据及云原生的应用。同时，Ozone 是一个 hadoop 兼容的文件系统，所有基于 Apache Spark，YARN 和 Hive 的应用可以无需任何修改直接切换到 Ozone 上。在设计上，Ozone 以 container 为汇报和复制的单元，将部分元数据管理的职责下沉到 datanode，解决了 HDFS namenode 的扩展性和块汇报风暴等长期以来困扰用户的问题。同时，Ozone 的元数据节点 OM 和SCM 基于 raft 实现了 HA，完全不依赖于外部组件，解决了 HDFS namenode HA 架构的复杂性问题。
1. 技术背景
1.1 EC 的原理
EC 的数学原理如下图所示，非本文重点，就不展开讲了。
具体到应用上，简单来说就是有 n 个大小相同的 data block，通过 EC 的算法可以计算出 m 个大小相同的 parity block，使得在所有 n m 个块中丢失任意不超过 m 个块，都可以通过 EC 的算法恢复出来。需要说明的是，这里的 EC 算法可以是多种，比如 Reed-Solomon(RS)、异或(XOR)等，并不局限于某种特定的算法。EC 存储的优势如何体现呢？这就要引出存储策略的两个衡量指标：
- 持久度：在保证数据块中内容不丢失的情况下，最大可以丢失块的数量。比如，hdfs 中三副本策略，我们最多可以在丢失2个块的情况下保持数据内容不丢失，因此 hdfs 中三副本的存储策略持久度为2。该指标关乎数据的安全性。
- 存储利用率：这个概念其实等同于空间放大，也即是数据大小和系统存储该数据实际占用的空间大小之比。比如，hdfs 中三副本策略，一个数据块是128M，我们实际存储时需要3*128M=384M，存储利用率就是1/3=33%。该指标关乎存储成本。
图1比较了单副本，三副本，以及两种 EC 策略的持久度和存储利用率。可以看出，使用 EC 算法能够同时将持久度和存储利用率保持在一个较高的水平，且不同的 EC 配置策略能达到的效果也不同，可以根据用户的实际需求进行选择。
图1
既然 EC 有这么大的优势，为何不全部采用 EC 策略？任何事情都有两面性，EC一般适用于存储较冷的大文件，而热数据或小文件并不适合采用 EC 策略。
- 如果文件太小，比如小于一个 block 的长度，那么 EC 策略生成的 parity block 有可能远大于2个 block 副本。比如 RS-10-4 的场景中，如果文件仅有1个 block 大小，但EC仍然需要生成4个 parity block，这大大低于三副本的存储利用率。图2对比了不同 block 大小的情况下 EC 和三副本策略实际产生的数据量。由图可见，只有在大文件的场景下 EC 才有相应的存储利用率优势。
图2
- EC 中的 block 会均匀的分布在不同的 rack 上，当需要读取数据时也要从不同的 rack 上来读，这就意味着以 EC 策略存储的数据丧失了数据的本地性。在大数据的场景下，yarn 等资源管理器往往会把计算调度到数据所在的节点运行，这就是为了利用节点上数据的本地性。而如果节点丧失了数据的本地性，则任务调度也无法做到最优。
1.3 完备的EC功能
一般来说，一个分布式存储系统支持完备的 EC 功能需要做到如下几点：
- EC 写：在数据写入时对数据计算校验块，并分别写入到不同的 datanode中。
- 在线恢复：在读数据块出错的时侯，客户端需要自动读取校验块并通过 EC 算法计算出丢失的数据块，并返回给上层，整个恢复过程对用户透明。正常情况下的 EC 读相对比较简单，不再赘述。
- 离线恢复：在数据没有被读取的时候，系统能自动探测到数据块的损坏，并进行数据恢复。这样用户在读取该数据时就可以避免在线恢复的过程，提升读取性能。
- 用户通知系统进行恢复：当客户端读取数据块出错的时候，除了在线恢复，客户端还可以及时通知系统该数据块已经损坏，让系统及时进行修复，避免下次读取该数据时仍然需要进行在线恢复。
- EC 和多副本的互转：一般对于热数据会采用三副本的方式来存储，从而保证iops和吞吐。当数据降温时，系统应能检测到相应的情况，自动将冷数据从三副本存储转为 EC 存储，从而节省存储成本。与之相对应，当数据升温时，需要将存储模式自动从 EC 转换为三副本。
目前我们内部 Ozone 已经实现了 EC 写，在线恢复和离线恢复，社区的 EC 离线恢复还在开发中。
2 Ozone EC的整体设计
2.1 Ozone中的数据存储方式
总得来说，Ozone 的存储层被称为HDDS(Hadoop Distributed Data Storage)，由元数据节点 SCM 和数据节点 DataNode 组成。Ozone 管理数据的粒度是大小为 5G 的 container。container 存储在 datanode 上，并定期向 SCM 汇报 container 的情况。而数据块则存储在 container 内部，由 datanode 自行管理。在三副本的策略中，Ozone 会选择3个 datanode 组成一个 pipeline(raft group)，通过 raft 来保证一个 container 在三个 datanode上的副本一致性。在 SCM 中，container 是一个逻辑概念，其实体是存在于 datanode 上的 container replica。一个三副本的逻辑 container 对应了三个存在于不同 datanode 上的 container replica 实体。Ozone 的 EC 也是针对 HDDS 进行设计和实现的。
2.2 EC的参数
EC 的参数主要包括三个方面，EC 算法，data(数据部)，parity(校验部), 用户可以根据自己对数据持久度和存储利用率的不同需求来调节 data 与 parity 的比例。例如 EC-RS-3-2，代表使用 RS 算法，3个 data，2个 parity，如图3所示。
图3
在 Ozone 中，既支持在写文件的时候指定 EC 的参数，也支持创建一个 EC 的目录，该目录中所有的文件都以相同的 EC 参数存储。在以 EC 的方式写入数据时，Ozone 首先会选择 data parity（比如上面例子中的3 2 = 5）个 datanode 组成 EC pipeline，选取 datanode 的时候会根据集群的网络拓扑结构尽量选择处于不同机架上的节点，最大化数据的容灾能力。然后在这个 pipeline 中的每个 datanode 上创建一个 container，来组成一个 container group（逻辑container）。这个 container group 中的所有 container replica 都有相同的 containerID，因为他们都属于同一个逻辑 container。每个 container replica 都有其单独的 index，从1开始向后逐个增加编号，前面连续的若干编号为 data container的index，后面连续的若干编号为 parity container的 index。对于上例来说，所有 container replica index 的编号为1，2，3，4，5。前面的1，2，3是 data container 的 index，后面的4，5是 parity container 的 index。一个 container group 中所有的 replica 上虽然有相同的container ID，但却存储着不同的数据，这点和三副本的存储方式完全不同。
2.2 EC的粒度选择
在 Ozone 中，一个 container(默认大小为5G)由若干 block(默认大小为256M)组成，一个 block 由若干 chunk(默认大小为4M)组成。对于一个 EC container group 来说，EC 可以选择在 container，block 以及 chunk 的粒度上做 EC，那么如何选择呢?
2.2.1 Container级EC
从实现的难易程度来讲，在 container 级别实现 EC 最容易，当前的数据写入路径完全不需要修改。data 以三副本的方式写入，等待 container 写满并成功 close 之后通过后台任务计算出所有的 parity container，并将每个 container index 的副本数减少至1，过程如图4所示，这样我们就能得到一个最终的 EC container group。
图4
该方案看似最少修改且实现最简单，但却有三个重要缺陷：
- 存储利用率的提升不能即时体现：在 container 写满并 close 之前，数据一直是以三副本的方式存储。假如 container 一直没有写满，EC 就一直无法进行，存储利用率也一直无法提升。
- 数据删除收到极大制约：当 EC container group 中某个 container 丢失时，我们需要完整的 container 来计算丢失的 container，因此，即使某个 container 中的 block 被 scm 删除了，它也不能从 datanode 上对应 container 的目录中删除，否则在恢复丢失的 container 时便会计算错误。这会导致被删除的数据长久的留在 datanode 上，无效数据会占用大量硬盘空间。
- 计算 Parity container 需要占用大量内存：假设 EC 的参数为 EC-RS-10-4，计算4个 parity container 需要将10个 data container 读入内存才能进行 RS 计算。Ozone 中 container 得默认大小为5G，10个 data container 就要占用 50G 的内存，并且计算过程还会占用大量的 cpu 资源。
上述三个缺陷中的每一个都是无法接受的，因此 container 粒度的 EC 不可行。
2.2.2 Block级EC
block 级的 EC 的实现方法简单来说就是先写 data container 上的 block，当 data container 上的 block 写满后，根据所有的 data block 计算出相应的 parity block。block 级 EC 的写入流程如图5所示：
图5
客户端会将数据切分为若干个 data block，并写入到 container group 中的 data container 上，之后再计算出这个 EC block 对应的 parity block 并写入 parity container 中。一个 EC block 对应的所有 data block 和 parity blcok 称为一个 block group。这种方案虽然相比于 container 级的 EC 有了很大改善：
- 在一个 block group 写完时就可以进行即时 EC。
- block 可以正常删除，不影响 container 中其他的 block。
但 block 级的 EC 在内存占用仍然不够理想，主要问题是 parity 的计算是在客户端进行的，那么客户端在写完一个 data block 后不能立即将该 data block 占用的缓存释放，必须缓存所有的 data block 的数据才能在其写完后计算对应的 parity block。Ozone 中一个 block 的默认大小是 256M，若 EC配置中的 data 部分比较大，例如 EC-RS-10-4（data部分为10），就需要缓存住10个 block，在写的过程中大概会占用客户端 2G 的内存，还有可能引发客户端的频繁 GC，这对用户来说是非常不友好的。
2.2.3 Chunk级EC——EC stripe
整个逻辑和 block 级的 EC 相似，Ozone 中 chunk 的默认大小为 4M，这样即使是 EC 配置中 data 值较大，也不会占用客户端过多的内存。例如 EC-RS-10-4为了计算 parity 只需占用 40M 内存来缓存相应的 data 数据。与 block group 相似，一个 EC stripe 本质上也就是一个 chunk group。EC stripe 是我们选择的最终方案，相应的写入流程如图6：
图6
3 Ozone EC的实现细节
3.1 EC写
Ozone EC 写的整体流程如图7所示：
图7
当以 EC 的方式向 Ozone 集群写入一个文件时，详细的流程如下：
- 客户端向 OM 申请创建一个 key，并同时申请能够承载文件数据的 block。
- OM 创建 key 的元数据之后向 SCM 申请 block。
- SCM 先查找有无符合条件(data parity)的 EC pipeline, 如果有则申请在该 pipeline 上分配一个 block 并返回给 OM，如果没有则根据条件创建一个新的 EC pipeline，然后在新创建的 pipeline 上分配一个 block 并返回给 om。
- OM 将申请成功的 block 信息返回给客户端。block 信息中包含了 pipeline 的信息和 container 的信息，因此客户端可以根据这些信息向指定 datanode 上指定的 container 写入数据。
- 在写每个 stripe 的时候，如果出现错误，则客户端会立刻放弃对应 block的写入，重新向 OM 申请新的 block 重写失败的数据。
- 客户端以 EC stripe 的方式向 datanode 写入数据，写完之后会向 om 发送commit key 请求，表示写入完成。
EC 写入的时候会遇到 padding 的情况。比如在 EC-RS-3-2中，如果一个 chunk 默认为 4M，那么一个 EC stripe 理论上应该能写 4M*3=12M 的 data，外加 4M*2=8M 的 parity。但有可能我需要写的数据只有 2M，小于一个 chunk。此时为了 EC 校验算法的完整性就需要用 padding 的方式来将 stripe 上空余的 data 部分填空，然后进行 parity 的计算。在实现上，Ozone的并不会真正的将 padding 数据写入到 datanode，而只是在 block group 中那些需要 padding 的 block 的元数据中写入 padding 数据的大小从而创建一个不存在的虚拟 chunk，从而避免了无效数据的传输。如图8所示，node2 和node3 上虽然有 block 和相应的 chunk，但实际的 chunk length 却为0.
图8
3.2 EC读
EC 读流程相对简单，就是向 OM 查询对应 key 的 block group 的位置，然后以 stripe 的方式将数据读取，整体流程如图9所示：
图9
在读的时候可能会遇到某个存放 data 数据的 datanode 丢失造成数据不可用的情况，这时客户端会启动 online recovery 的过程进行在线恢复，读取相应的 parity 数据并在客户端将 data 数据通过 EC 的算法反向计算出来，并跟据之前读到的数据进行拼接后返回给上层应用，全程对用户透明。相应的流程如图10所示：
图10
整个 online recovery 过程虽然对上层应用是透明的，但是由于多了读 data 数据失败，读 parity 及数据反向计算三个过程，读的延迟必定比正常的读要长，因此需要通过 EC offline recovery 对出错的数据进行及时修复，避免再次读到缺失的数据。
3.3 EC offline recovery
SCM 通过接受 datanode 的汇报心跳来判断各个 EC 的 contain group 是否是处于健康的状态。这里的健康状态有两层意思：一是整个 container group 中所有 index 对应的 container replica 是否都是健康存活的，二是所有的 container replica 所处的位置时是否满足 EC 的副本放置策略。比如，如果一个 container group 的所有 index 对应的 container 都位于同一个 datanode 上，那么一旦这个 datanode 挂了，整个 container group 的数据就丢失。对于仅仅不满足副本放置策略的情况，SCM 只需要按照副本放置策略的要求寻找一些新的 datanode，并发送相应的 replication 命令将这些 container replica 复制过去，然后删除原来的 container replica 就行了，相对比较简单。EC offline recovery主要是对于某些 index 的 container replica 丢失的情况，需要启动 container 的重建流程来进行数据恢复，具体如图11所示：
图11
- 确定所有丢失的 replica index。如果丢失的 replica index 大于 parity 的数量，比如 EC-RS-3-2 中丢失超过2个不同 index 的 container replica，那么改 EC container group 就处于不可恢复的状态。
- 对于可恢复的 EC container group，按照 EC 的副本放置策略选择和丢失的replica index数量相同的datanode作为重建container replica的目标datanode。
- 在目标 datanode 中选择一个作为 coordinator datanode。coordinator 会首先在所有目标 datanode（包括其自身）上创建空的 contaner replica，然后按照顺序读取所有健康 container replica 上 chunk，并根据 EC 算法反向计算出丢失的 container replica 上对应位置的 chunk，并将 chunk 数据写入之前创建好的空 container replica 中。通过逐个重建 EC stripe 的方式来重建每个 block，最终实现重建丢失 container replica 的目标。
这个地方为何要选择一个 coordinator datanode 来完成重建工作，而不是将重建命令分别发送给各个目标 datanode 来让他们自行读取健康的 container replica 进行重建？主要原因是为了避免一个健康的 container replica 上的数据被读取和传输多次，产生不必要的磁盘及网络 IO。采用 coordinator datanode 方案使得健康 container replica 上的数据仅仅会被读取和传输一次。
4 后记
腾讯大数据存储团队作为 Apache Ozone 社区的主要推动和参与方，一直致力于社区的发展及代码的贡献和 review，主导设计并实现了Network Topology Awareness， SCM HA，Container Balancer，Merge rocksDB，Streaming Write，EC 等多个重要 feature，目前已经晋升了3位社区 Committer。未来，我们会持续跟进，助力 Ozone 走向更好的未来！
