浅谈B站对象存储

司春峰

哔哩哔哩技术专家

负责B站对象存储、NoSQL、数据传输、数据库代理等方向的研发工作，致力于提供稳定可靠高性能的存储服务。

背景

BLOB(binary large object)存储，通常也被称为对象存储(OSS, object storage service)。一般用来存储文件，如视频文件、音频文件等。目前，各个云计算厂商都对外提供对象存储服务，其中以亚马逊的S3系统最著名，S3系统也成为行业的事实标准。各个云计算厂商推出的对象存储服务，也纷纷兼容S3标准。

B站由于其内容的独特性(视频网站)，对象存储也有着非常多的需求。下面我们会介绍B站的对象存储的设计与实现。为了便于大家理解，会采用由简单到复杂的过程进行。我们称这个对象存储系统为BOSS(Bilibili Object Storage Service)。目标13天精通超大规模分布式对象存储系统的架构与设计。

Day1

先研读S3协议，我们会发现S3其实提供的接口非常简单，主要有PUT/GET/DEL/LIST等几种类型的接口(这里先忽略分段上传等接口)。各个接口对应的语义和term定义如下：

看到这里，假设我们有一个性能非常强大的SQL服务(比如Mysql ORZ), 那么我们可以建一张表(比如表名为data_and_meta)，然后将数据存入即可。

表结构

系统架构

此时我们的系统架构如下图所示

其中协议网关可以采用golang编写，解析S3协议，并转换为后端对MySQL服务的操作即可。至此，Day1的工作完成， 收工回家。

Day2

第一天在设计表结构的时候，数据和元数据都堆在一起，相互有影响。今天我们将元数据和数据拆开来。新建两张表，meta表和data表。

meta和data分离的表结构

如上图所示，通过object_id将meta表和数据进行关联，object id为一个int64类型(先不考虑object_id哪里来的)

优点

1. 元数据和数据进行了分离存储
2. 可以实现数据和元数据的分别更新(可以预见，后面需要新增字段，满足不同需求)
3. 甚至可是实现rename操作(当然S3没有这个需求)

问题

引入Block表

针对单个data字段中的数据太长的问题，我们继续拆分，改成3张表，如下图所示

变化

写入流程

1. 接入层接受到数据之后，将数据切割为若干个block，每个block分配一个id(先不管哪里来的)。以blockid为主键，将数据写入到data表中
2. 分配一个object_id(先忽略从哪里分配)，将步骤1中的blockid和数据表的表名压缩到一段pb中，然后以object_id为主键，将这段pb写入到object表中
3. 以bucketName和s3文件名组成主键，将object_id写入到name表中

读取流程

1. 读取流程和写入流程相反
2. 以bucketName和s3文件名为key，从name表中查找到对应的objectid
3. 以objectid为key，从object表中查找到对应的block列表
4. 根据block列表中的长度信息，根据用户读请求的区间，计算出需要读取哪些blockid
5. 以blockid为key，从data表中读取对应的数据，并进行截断和拼装，返回结果。(假设上传一个10MB的文件，1MB一个block，指定读取区间 [1MB+1B, 2M+100KB], 则需要读取第1和第2个block，并进行截断)

新的架构

如上图所示，我们实现了数据存储和元数据存储的分离，并将元数据分为两块，用于处理大文件的场景。

objectId和blockID 哪里来?

回顾上文对objectId和blockID的使用，我们发现这两个ID的用途在于"唯一标识一段数据，不能有重复"。我们可以有几种产生ID的方法:

1. mysql的自增ID
2. value的CRC
3. 其他外部的ID分配器

这里我们先使用mysql的自增ID作为object id。使用CRC的问题在于，同一个文件两次上传(使用不同的文件名)，以block的CRC和整个的CRC分别作为blockid和objectid，会导致在data表和object表中，只有一条记录(CRC相同)，删除的时候会导致实际的数据被删除(当然我们可以使用CRC做去重，这里先不讨论)。Day2工作完成，我们已经实现了元数据和数据分离存储。

Day3

目前我们接入层直接访问MySQL来进行数据和元数据的读写操作，和MySQL耦合比较严重。今天我们在MySQL和网关之间加一层，用于屏蔽存储层的具体实现。

新架构

网关与S3元数据服务和IO服务之间走RPC进行通信(比如gprc/brpc)，S3元数据服务和IO服务通过SQL访问后端MySQL, 用于屏蔽后端具体的存储实现。

Day4

回顾过去两天的工作，我们已经实现了元数据和数据的分离存储。但是作为一个分布式存储系统，我们离高可用、高可靠、水平扩展能力，差距很大，需要继续改进。数据存储部分通常采用sharding的方式进行集群化(也就是进行分片)。而sharding的方式， 又分为一次映射和二次映射的方式。

一次映射过程

1. 当路由层收到PUT请求时， 此时输入为(key, value)，其中key为int64类型(blockid)。
2. 假设后端有4台MySQL服务器， key % 4, 得到对应MySQL服务器的下标。
3. 将请求发送给对应的MySQL服务器即可。

一次映射的缺点

1. 没有办法做扩容和缩容操作(比如4台MySQL变成5台之后，按照5进行取模操作，MySQL server对应的下标会发生变化)
2. 替换节点(比如MySQL所在物理机坏了)，必须做一一对应，否则下标无法对应。

一个简单的改进

1. 路由层收到请求之后，查询MySQL(某种元数据服务，这里简化成MySQL), 来确定与后端的哪台服务器进行通信。
2. 根据MySQL返回的地址信息，与数据层的服务节点(data-1...data-4)进行同行。

缺点

1. 存储路由信息MySQL会成为瓶颈，性能和空间都会有问题。
2. 后端进行扩缩容的时候，需要对路由MySQL进行大量的变更操作(需要修改每条key所对应的存储层服务器的地址信息)。

问题关键

上面的方案的主要的问题在于，路由元数据的压缩不够明显，每条记录的元数据都进行了存储。常识告诉我们，计算和存储之间可以进行转换，即通过计算来降低存储空间。

改进方案

1. 引入虚拟的sharding层
2. 将key通过计算的方式得到一个虚拟的shard
3. 路由MySQL中只存放虚拟的shard到存储层服务器地址的映射信息
4. 虚拟的sharding的数量可以先拍脑袋决定，比如2233个。

新写入过程

1. 路由层收到key之后， hash(key) % 2233 得到一个[0, 2232]之间的数字，比如X， 即shardX。
2. 查询路由MySQL，得到shardX所对应后端的数据存储层MySQL服务器的地址。
3. 与数据存储层MySQL进行通信，获取数据。

优点

1. 这里路由层MySQL只需要存储2233条记录即可，每条为(shardID, 数据存储层MySQL的IP)，shardID为主键。
2. 由于这些数据变动的概率非常小，变动的内容有限，完全可以在路由层的内存中缓存。
3. 存储层进行扩容(缩容操作)的时候，只需要在路由MySQL中修改一条记录即可。即shardID到数据层MySQL新的地址信息。
4. 路由层在感知(主动/被动)到变化后，只需要在更新本地的路由表即可。
5. key(blockid)到shard的映射信息，由计算得到，无需存储(eg: md5sum(blockid) % shard的数量)。

对存储层的影响

假设水平扩容的实现过程如下：

1. 从存储节点A上，将隶属于shardX的所有数据copy到存储节点B上
2. 更新路由表中shardX的地址信息(从节点A的IP变更为节点B的IP)
3. 由于在copy的同时，仍然有数据继续写入，因此需要一些容错逻辑，这里不展开。

写入流程如下：

data表schema更新

为了便于迁移属于同一个shard的所有数据(快速扫描出来，该shard的所有数据)，存储层表的schema更新如下(新增shard_id字段)：

block_idvalueshard_idblockID实际数据shardID

迁移数据时，根据shard_id字段进行过滤即可。至此，Day4工作完成，今天我们完成了数据层的sharding过程，并为水平扩容打下了基础。

Day5

到目前后端的数据均存在MySQL中，MySQL的好处在于稳定易用，但是功能过于复杂，性能也不能满足要求。今天我们对MySQL进行替换。

数据存储节点语义

1. 对外提供PUT/GET 接口(先忽略Del接口)。
2. 相应的参数为shardID, key(int64), value。

根据这些需求，可以将存储节点进行如下两种设计：

存储节点设计简介

1. 从上至下分为 RPC 层、shard层和引擎层
2. RPC层负责通信
3. shard层将RPC请求转换为对具体的某个shard的读写操作
4. engine层则负责将请求转换为对磁盘的读写操作

方案对比

方案1

1. 请求进入RPC层之后， 根据shardid 进行分发，获取到对应的shard实例(句柄)
2. shard使用key和value操作engine层
3. 一个节点(或者一块磁盘)公用一个engine，使用shardID作为key前缀，用于区分不同的shard(在迁移的时候，可以使用shardID为前缀扫描属于该shard的所有的key和value)

方案2

1. 方案2作为方案1的简化版本
2. 区别在于，一个shard实例(句柄)对应一个engine实例(而非方案1的全局公用)
3. 优点在于：
4. 实现更简洁
5. 进行数据搬迁的时候，可以对整个engine进行snapshot拷贝即可(无需逐条扫描)

引擎的实现

今天我们直接使用RocksDB作为我们的单机引擎，不做其他优化。

新架构

数据存储节点替换了原有的MySQL服务，今天的目标达成，收工。

Day6

前面几天已经实现了数据存储层的sharding。但是sharding只能解决水平扩展问题，容灾仍然有问题。今天我们对数据存储集群的资源重新进行整理。

1. 引入资源池和可用区(故障隔离域)的概念。同一个资源池内的机型同构(简化资源调度逻辑，比如相同的磁盘数量和磁盘大小)。不同的业务可以使用不同的资源池，做到存储层资源隔离。
2. 将不同交换机下的节点定义为不同的可用区(故障隔离域)。可用区之间实现交换机级别的隔离。
3. 每个存储集群由一个或者多个资源池组成。资源池之间IO隔离，资源池内部机型同构。
4. 每个资源池内部，由多个可用区组成。每个可用区由若干台服务器(存储节点)组成。
5. 修改路由表中shard到IP的映射关系。
6. 一个shard对应到多个Replica(比如3副本)
7. 路由表中存放每个Replica所在存储节点的地址信息。
8. 一个shard对应的Replica被放置于不同的可用区中(比如3个Replica放在不同的可用区)。
9. 3副本模式的时候，任何一个交换机下的节点宕机，都不会影响读写操作。

新架构

下图为一个资源池+4可用区的模式，每个shard拥有3个副本(Replica)。

路由层的MySQL中存储的信息如下：

集群拓扑信息(路由规则)

如何将一张表对应的shard(Replica)分配到这些存储节点上的呢？

1. 假设一张表(table1)，有2233个shard，每个shard 3个副本。
2. 资源池A有4个可用区，每个可用区3个节点。
3. 则每个节点拥有约558个Replica( (2233 * 3) / (4可用区 * 3节点) = 558.25)。
4. 假设每个节点有30块磁盘，则每个磁盘上有18个replica(558.25/30).
5. 后端集群在创建表(table1)的时候，可以对每个shard逐个处理
6. 为该shard对应的3个replica(也可以是多个)，从4个可用区中，挑选出合适的节点
7. 在从这些节点上挑选出合适的磁盘
8. 将这些映射信息，固话到路由层的MySQL数据库中即可
9. 挑选策略可以采用负载最低(Replica数量最少)、随机挑选等多种方式
10. 通过这些策略，最终确保每个存储节点的每块磁盘上的Replica数量大致相同，保证读写压力能够均匀的分摊到后端的所有节点上。

读写模型

回顾上文，在引入多副本之前，一条(K,V)请求到达路由层之后，经过sharding和路由表查找之后，请求会转发给存储层的某一个节点，由该节点进行实际的读写操作。在引入多副本的概念之后，引入了副本间的一致性问题。

一致性问题

1. 假设一个shard 有3个副本，R1，R2，R3
2. 两个client对同一条Key，分别进行了写入(key, value1) 和 (key, value2)
3. 根据请求到达的先后顺序，3副本上最终存储的数据可能状态有2x2x2=8种

如上图所示，只有状态1和状态8的3副本处于一致性状态

对于这种一致性问题，通常我们采取选一个主节点(主角色)，由leader来进行冲突的解决(比如RAFT协议) 如下图所示，对于有主系统，常见的复制模型如下

1. HDFS的pipepine方式
2. RAFT协议的Quoram方式

有主系统(有主角色)的主要问题在于，主节点不可避免的会遇到一些抖动(CPU/磁盘IO)问题，从而带来用户请求的抖动。回顾上文，我们这个系统里面的key(blockid)由MySQL的递增ID生成，全局唯一。一条key只会被写入一次，不存在写冲突问题。因此我们可以采用最简单星型写入模型。如下图所示，一条记录由IO服务直接并行写入到多个存储节点，多数成功即可。

优点

1. 可用性高：没有选主过程(异常宕机后，RAFT的选主周期在秒级别，比如5s左右)
2. 长尾小
1. 写入时，任意2个节点ack即可
2. 读取时，任意节点返回即可。同时由于没有更新(覆盖)操作，可以使用backup request规避长尾

副本间的一致性

由于采用大多数成功即可的写入模型， 运行一段时间后，同一个shard的各个副本之间的数据分布如下图所示：

可以看到，不同的Replica之间key的数量有差别， 比如key2在Replica2上不存在，key3在Replica3上不存在。为了解决这些差别，我们引入修复模块(先不考虑Delete的情况)，用来修复不同副本之间的差异。

修复工作流程：

1. 修复模块定期的扫描集群中的所有的shard
2. 对每个shard，获取shard的所有的replica的key列表
3. 计算这些Replica间的diff，将缺失的key读取出来，并进行回填

新的架构

今天的架构演化到如下状态：

总结一下今天的工作：

1. 对后端的存储节点重新进行了划分，引入资源池和可用区的概念
2. 引入副本的概念， 一个shard由多个副本组成，这些副本分布在不同的可用区。
3. 对一个shard的写入，实际上转化为对多个副本的写入，这些副本只需要写入到大多数成功即可。
4. 加入离线修复模块，用于修复一个shard多个副本间的数据不一致问题。

BLOB(binary large object)存储，通常也被称为对象存储(OSS, object storage service)。一般用来存储文件，如视频文件、音频文件等。目前，各个云计算厂商都对外提供对象存储服务，其中以亚马逊的S3系统最著名，S3系统也成为行业的事实标准。各个云计算厂商推出的对象存储服务，也纷纷兼容S3标准。

B站由于其内容的独特性(视频网站)，对象存储也有着非常多的需求。下面我们会介绍B站的对象存储的设计与实现。为了便于大家理解，会采用由简单到复杂的过程进行。我们称这个对象存储系统为BOSS(Bilibili Object Storage Service)。目标13天精通超大规模分布式对象存储系统的架构与设计。前6天的内容详见：十三天精通超大规模分布式存储系统架构设计——浅谈B站对象存储(BOSS)实现（上）。

Day7

拓扑信息(路由信息)单点问题

经过前几天的努力，目前后端存储已经具有多副本，sharding的功能。观察我们的系统，路由数据存放于MySQL中，成为存储后端的单点。今天我们来解决这个单点问题。如下图所示，为了提升集群拓扑信息的安全和可用性，有两种方案：

方案1

1. 将数据存储于etcd中，通过etcd的3副本来保证数据安全
2. 在etcd之前，加入路由信息缓存层，将路由信息全部镜像到内存中
3. 新加入管理节点，负责拓扑信息的变更操作

方案2

1. 方案2实际上是方案1的简化版本
2. 不再依赖于etcd，而是使用braft实现一个简单的KV结构。也拥有三副本，由braft完成3副本之间的数据复制。
3. 在leader节点上集成集群管理逻辑，由这个管理逻辑对集群进行管理。(每个节点都有相同的逻辑，但只有处于leader状态时，才开始工作)
4. 路由信息缓存层和方案一类似，区别在于:
5. 使用round robin的方式从元数据服务节点(Metaserver)同步数据。
6. 同步的时候，利用raft log index只增不减的特性，作为拓扑信息的版本，避免同步到旧的信息。
7. 即使metaserver2个节点宕机，拓扑信息也能正常获取到。

元数据

集群中(metaserver中)需要存储的元数据主要包括：

表相关元数据

表的元数据主要包括：

1. 表的基本属性(创建时间，shard数量，每个shard的replica数量)。
2. shard的属性：有哪些replica，该shard在这张表中属于第几个partition(即取mod后的下标)。
3. replica的属性：需要描述其对应存储节点的信息，以及位于对应节点的具体哪块磁盘上

我们采用如下的proto文件进行描述，通过id和uuid可以建立起对应的关联信息

存储节点相关元数据

存储节点的元数据主要包括：

1. resource pool的基础信息
2. 每个resource pool有几个可用区
3. 每个可用区由哪些节点组成
4. 每个节点有几块磁盘构成

使用如下proto文件进行描述，构建后端集群的分布情况

table和存储节点间的关联关系(拓扑信息)

通过这些信息，我们可以建立如下映射关系

1. 在逻辑层，我们可以做这样的映射: (table_name, key) -> shard -> [replica0, replica1, replica2]->[addr0, addr1, addr2]
2. 在物理层，集群由多个资源池组成，每个资源池由多个可用区构成，每个可用区由若干台服务节点(DataNode)构成。每个服务节点管理若干块磁盘
3. replica最终对应到某个服务节点(DataNode)上的某个磁盘上的一个存储单位

新的架构

Day8

回顾整个存储系统，可以发现目前S3元数据存储和object_id的生成还是单点，今天我们来解决这个问题。

元数据量级：

1. 假设在S3元数据侧，每个对象需要100Byte进行描述(文件名、objectId等)
2. 假设单个object大小为100KB，总存储规模为100PB，则对应的元数据空间为100T级别 (100PB/100KB * 100Byte)
3. 假设单个object大小为10MB，总存储规模为1000PB，则对应的元数据空间为T级别 (1000PB/10MB * 100Byte = 10TB)

可见，对于一个大规模存储集群，通过元数据的提取和压缩，元数据完全可以使用一个小规模的NewSQL或者分布式KV进行存储。

新架构

在S3元数据侧引入新的元数据存储，修改后的架构如下图所示。

Day9

目前object_id的使用MySQL的自增ID生成，存在单点。对于object_id的需求，我们只需要全局唯一，不需要递增。可以使用如下两种方案：

方案一

1. 进度信息持久化在MySQL中
2. 接入层
3. 对外提供RPC接口
4. 由后端线程去MySQL中进行预分配(incr操作)。再从分配后的空间，对外提供ID分配操作。
5. 每次重启后，先去MySQL中进行预分配，再对外提供服务
6. 所有的接入层均对外提供分配操作(即上图中的取号器0、取号器1、取号器2都对外提供服务)

问题

方案一的缺点在于，MySQL仍然是单点。

方案二

1. 方案二可以认为是方案一的改进版, 使用RAFT实现一个简单的KV
2. 此KV对外提供INCR 操作。每次操作返回incr前后的值，作为接入层的安全分配区间
3. 这样实现简单，也避免了MySQL的单点。
4. 以braft单个raft group约5000 QPS的性能计算，每次预分配10000作为分配空间，分配性能足够。

问题

RAFT异常宕机时，约有5s左右的不可写入时间，因此需要计算(评估)合理的预分配范围，确保这段时间有足够的key可用。

新架构

新的架构如下所示：

Day10

对象存储系统，由于整体规模庞大，存储成本会有比较大的压力，这点与计算型系统有较大差别。到目前这个系统还是使用3副本的方式来保证数据的可靠性和服务的可用性。今天我们来降低副本数。Erase code(纠删码/EC)是目前比较常见的降副本的方式。其具体原理的细节这里不再赘述，一言以蔽之就是"时间换空间/CPU换存储"。

EC的基础功能

1. 将原始数据切分为等长的数据块
2. 通过对数据块进行矩阵计算，生成编码块(也称校验块)
3. 数据块的数量用k表示，编码块的数量用m表示
4. 所有的数据块和编码块的长度相等(先忽略数据块的padding问题)
5. 从这(k+m)个块中，任意取出其中的k个，可以通过矩阵运算的方式还原出(k+m)个
6. eg：
7. 假设原始数据为(a,b,c,d,e,f), 使用k=6，m=3的方式，生成3个编码块(g,h,j)，总共9个块
8. 任意取其中的 b,c,e,f,h,j 则可以还原出a,d,g

如下图所示，编码的具体过程，由6个数据块生成3个编码块。

纠删码空间占用

1. 副本数 = (k+m)/m, 以k=6, m=3为例，则副本数为 1.5副本
2. 3副本模式，可以理解为k=1,m=2的特殊场景

读写过程

如上图所示，我们可以对比下EC模式和3副本模式的写入过程。

副本模式时写入过程

1. 根据key进行计算，得到数据应该存放到哪个shard上
2. 由shard的信息，定位到对应的3个Replica的地址信息
3. 将请求发送给Replica所在的节点进行写入即可(这3个节点位于不同的可用区中)

EC模式时写入过程

1. 与副本模式的差别在于不再将原始数据发送给后端存储节点
2. 而是先进行编码，然后将编码后的k+m个块，发送给后端的节点
3. 此时要求后端的Replica的数量等于 k+m，而不是原来的3副本
4. 这k+m个Replica位于k+m个节点，并且这些节点处于不同的可用区中
5. 理论有k个实际写入成功即可(实际上会根据k和m的数量进行处理)

数据块和编码块间的顺序关系

1. 由于这k+m个Replica之间的数据是不一样的(可以观察图上数据块的颜色)，而且数据块和编码块的之间也有顺序关系(比如返回给用户的时候，一定是按照(数据块0数据块1数据块2)的顺序)，因此需要有地方来描述这些数据块之间的关系。
2. 我们希望在读取之前就能确定这些块的关系，否则需要读取k个以上的块进行解码才能得知
3. 这里我们在Replica的元数据中加入sn_in_shard 用来标识对应的k+m个replica的先后关系(可以再查阅Day7时ReplicaModel的定义)

EC模式的读取过程

1. IO服务收到读请求后，计算出key对应的shard
2. 检查shard对应的k+m个replica的信息，得到前k个replica(由sn_in_shard描述)，优先将请求发送个给这k个replica。当这k个replica返回结果时，直接拼接原始数据返回即可(读取的时候，尽可能避免走EC解码，EC解码对CPU消耗很大)。
3. 同时，新建若干个定时器，构造对应批次的backup request，对应剩余的m个replica
4. 如果第一批次返回，则取消这些定时器，避免浪费后端IO
5. 如果第一批次的返回值有部分报不存在或者出错，则立即启动上面的定时器
6. 由于写入的时候，任意k个以上成功就返回，所以有可能写入的时候失败了
7. 或者此时后端部分节点异常
8. k+m中有任意k个成功后，即可通过矩阵计算还原出原始数据块并返回

对其他模块的影响

修复模块会受影响。3副本模式的修复过程，只需要读取任意一个replica上的数据，就可以进行修复。现在需要读取k个数据，并重新进行EC计算，然后才可以进行修复。

k和m的选择

根据上文的计算k越大, m越小，则副本数(k+m)/k=1+m/k越小。那么我们是不是可以把k设置成100，m设置成1呢？这里的k和m 一般受如下几个条件制约

1. 一个shard的replica数量等于k+m，而这些replica是位于不同的node中，这些node是位于不同的可用区中。k=100,m=1要求有101个可用区，一般公司的故障隔离域没有这么多，规模也没有这么大。
2. 原始数据输入后，会切割成k个数据块，如果原始数据长度为1MB的话，那么切割后到后端存储节点只有10KB了，会造成后端节点的IOPS上升(相当于放大了101倍)。
3. 读取的时候，需要并行读取100个数据块，长尾和IOPS都会上升。

那么是不是可以在约束k的情况下，降低m的值呢？这里又引入了另外一个话题。

数据可靠性(安全性/持久性)计算

数据可靠性讨论一般指在给定的磁盘故障概率情况下，不发生数据丢失的概率。先不考虑原始写入的时候只写入部分成功的情况。

可靠性相关因数

1. 磁盘故障概率：直观解释，假设在某鱼购入一批硬盘，某天中午都同时发生了故障，那么一定会丢数据。
2. 坏盘后的修复速度：假设磁盘故障不是同时发生的，那么只要在连续故障导致数据丢失之前，将数据修复回来，也就是修复速度大于故障速度的话，就不会发生数据丢失。假设有个神器，无论磁盘多大，都能在1秒内修复，那也不会发生数据丢失。
3. 能够容忍发生连续损坏的盘的数量：假设修复时间恒定(比如1小时修复一块盘)，那么此时3副本(可以容忍连续损坏2块盘)的数据可靠性小于10副本的情况(可以连续损坏9块盘)

回顾上文，EC使用k+m的策略，任意k个块就可以恢复原始数据，也就是允许m个损坏。所以从数据可靠性考虑，m越多越好。实际环境中k+m的策略，需要根据资源(机器数、故障隔离域数)、业务IO特点(比如文件大小)进行具体调整。

Day11

目前从架构层看，我们基本完成了S3的大部分功能(不考虑分段上传和Delete操作)。目前engine层还是使用的Rocksdb，而rocksdb在面对长度比较长的value时(1K以上)，会有比较大的写性能问题(compaction导致)。今天我们足够解决这个问题。

优化目标

在讨论这些引擎的差别之前，我们先看下存储层的目标。所有的存储的目标都是为了最终数据的读取操作，如果没有读取的话，也就没有存储的动力。如何有效的满足读取目标是各个存储引擎的优化目标。注意，这里我们使用有效的满足而不是高效的满足，区别在于，不是所有的读需求都要求高性能，有些场景，只要能满足就行了。

假设我们采用最简单的策略：

这种方案如果简单进行测试，发现可以工作，但是是否可以完成目标，该如何进行评估呢？回顾文件系统的实现，我们会发现，本地文件系统，通常也分为元数据存储和数据存储两块。其中元数据主要包括目录树(文件名相关信息)、inode(用于描述文件由哪些数据块组成)、数据块。如下图所示

本地文件系统的读取过程如下(以读取"/image"文件为例)：

1. 由"/"找到对应的inode(每个文件系统的根inode id通常固定，比如ext2为2，不需要查找过程)
2. 根据inode 2，找到对应的datablock id列表(比如上图中的block id 7)
3. 将数据块(block id7)的内容读出，转换为目录项(可能是一个有序数组，也可能是个B+树)
4. 在目录项中查找"image"，得到对应的inode id(如上图例子为88)
5. 根据inode id(88)，读取对应的inode信息(一段128 byte左右大小的数据，视不同的文件系统而有所区别)
6. 解析inode的内容，得到对应的block id列表(例子中为block id 10,11,15)
7. 由block id查找到对应的磁盘块，进行读取操作

对比下我们系统的架构和读取流程，可以发现和我们的系统的工作过程非常相似。我们的系统也有目录树和inode的概念。目录树就是S3元数据中的name表，而inode则是object表。在单机文件系统上，通常每个目录是存放在一个B树中。当一个目录下的文件特别多的时候，这个B树就会成为瓶颈。同时一个文件对应一个inode，如何缓存inode避免频繁的读取磁盘，也会成为一个重要的目标。

通过上面的计算，我们发现当每次写入后端的数据长度较大(比较理想)的时候，可以直接将数据写在文件系统上，不用做其他优化。这里我们实际上是在利用文件系统的设计，在磁盘之上实现了一个meta和data分离的存储。但是，生产环境中往往没有这么理想，后端接受到的value长度往往长短不一(考虑上文的erasecode的编码过程，会将数据切割成等长的k个块，然后发送给后端节点，一个5MB的文件，k=10的话，切割完成之后发送给后端的数据长度只有500KB了)。为了应对复杂场景保证读写性能，必须进行优化。

观察上面的写入过程，核心问题在于文件数量太多，导致B树的条目数和inode数量过多，而通用文件系统很难进行定制性的优化(比如把B树创建在指定的nvme ssd盘上)。为了降低文件的数量，我们可以将不同的数据写入到相同的文件中(比如每1GB 数据使用一个文件，则此时文件数量为 10TB/1GB = 1万条记录，文件系统的meta部分的内存占用降低到可以忽略的程度)。此时我们面临的问题转变为如何有效的根据key(blockid)在一堆文件中，找到对应的数据。

回想在内存里面，我们优化读取性能的时候，通常两种套路：

在磁盘上，其实我们可用的的优化方法也类似：

根据对文件内容进行排序的时机，可以分为离线排序和在线排序(写入的同时)。最直观的区别在于，在线排序会导致写入性能下降(有点废话，关键路径上做了更多的事情)。

常见存储引擎

根据上文提及的优化手段，目前常见的存储引擎有如下几种

1. bitcask
2. b/b+树
3. LSM tree
4. 上述各种引擎的优化和变种(组合)版本

B/B+树

B/B+树的本质在于写入的时候，构造一个全局有序的数据集合，然后在这个有序集合上进行折半查找。由于磁盘进行折半的开销太大(有多次IO操作)，因此建立多个层次的索引，并尽可能的将这些索引load到内存中，减少查找的代价， 如下图所示：

优缺点

对于连续key访问，相应的数据都在一起，因此可以利用磁盘的顺序IO获得比较大的吞吐。由于对象存储系统通常都是离散的IO，而且上层做了key打散，因此不能发挥顺序IO的优势。同时，由于为了构造全局有序的集合，需要不停的进行分裂和调整，磁盘上的随机写IO也会非常明显。

LSM tree

LSM tree 本质上是在多个有序文件之间进行查找。

如上图所示，LSM tree的工作流程如下：

1. 在内存中构建一个排序的数据集合(通常使用skip list)
2. 攒到一定规模后(比如16MB)，将排序后的结果dump到磁盘。为了在内存中进行排序，同时又保证数据不丢失，需要把写入操作先LOG。这样如果重启的话，可以从LOG重放，重建内存数据集合。
3. 从内存中直接dump出的有序文件，放到称之为L0的层的集合中。这里可以想象，如果写入速度非常高，那么会有相当数量的有序文件堆积在L0层中。这些文件之间只有时间上的先后顺序，每个文件内部有序。此时如果需要查找一个key的话，本质上需要按照时间的先后顺序，对每个文件进行折半查找。当L0文件的数量堆积到一定程度之后，读取的效率可想而知。为了缓解这种情况，通常LSM写给的方案是阻塞写入，由后台线程对已经存在的数据先进行排序(嗯，先别写入数据了，等我排好序再来)。排序时，采用读取多个有序文件，merge后写到新文件中的方式(非原地修改)。
4. L0的这些文件，经过排序之后，就可以生成一个L1有序文件集合了。如上图所示，L1的文件之间和内部都是有顺序关系的。
5. 不考虑层间的排序情况，如果步骤3的情况再发生一次，此时的L1变成L2，L0的文件进行排序后生成L1的文件列表。
6. 如上图所示，经过多次dump之后，不考虑各种优化手段(bloomfilter)，如果需要查找key=4.5，需要在L0的3个文件、L1、L2、L3等多个文件内部进行查找。

优缺点

LSM tree在写入的关键路径上，不对key进行排序，而是由后端线程进行离线排序，因此读取的性能依赖于排序的状态。如果都排序完成，不考虑优化手段的区别，读取性能可以类比与B树。排序跟不上写入时，读取性能则退化为在多个文件间进行顺序折半查找。

bitcask

bitcask类型的引擎，可以类比与内存中的hash结构，放弃了对有序的需求，通过内存中的全索引，快速定位到磁盘上的绝对位置，然后转换为对磁盘的一次读取操作。

如上图所示，读写工作流程如下：

1. 每个engine，维持一个正在写入的文件，新的写入都写入到此文件中。
2. 写入文件成功后，在索引中记录key->(file_name, offset，len)信息(索引可以是内存hash或者位于nvme ssd上的其他engine) 。
3. 读取时，从索引中获取到(file_name, offset，len)信息，然后打开相应的文件，seek到指定的位置，进行读取即可。
4. 删除时, 在新的文件中写入删除标记，并在索引中删除对应的key 即可。
5. 覆盖写的逻辑和删除逻辑类似，如上图的key=1，写入两次后，索引中的位置指向后一次写入的位置信息

数据回收流程

1. 从最早写入的文件开始遍历磁盘数据(k,v)
2. 判断索引是否还指向当前记录，如果不再指向，则说明有新的写入或者被删除，跳过当前记录即可。如果指向，则将当前记录重新进行写入即可。此写入和普通的写入一样，会追加写到最新文件的末尾。
3. 这里需要注意，判断索引是否指向当前记录到真正执行写入，有时间差(race condition)。因此需要注意锁的使用以及锁的区间。

优缺点

常见优化手段

回顾我们的场景，对后端的所有读取均为随机读取，没有顺序遍历需求。虽然bitcask的空间回收效率低，但实现简单，并且可以方便的获取key 列表(用于修复模块)。因此实现一个bitcask类型的引擎，提供put/get/del等接口即可。至此，今天任务完工，收工回家。

Day12

到现在，该分布式存储系统除了删除功能和分段上传功能外，从协议接入层到engine层，功能基本完备。今天我们来实现del功能。

简单实现

删除功能的基本实现如下：

问题

回顾上文，我们的修复模块，会将一个shard不同的replica上缺失的key(block id)进行补回，删除逻辑和修复模块会存在竞争。会出现一个刚刚被删除的key，被修复模块又重新补回的情况。

修正

删除逻辑和修复逻辑做如下修正：

1. 删除逻辑给后端发送标记删除请求(而非删除请求)
2. 修复逻辑发现标记删除之后，将所有的副本设置为标记删除状态
3. 只有当所有的副本都处于不存在或者标记删除状态时，才进行真正的删除操作

Del功能实现完成，收工回家。

Day13

今天我们来实现水平扩容和副本修复功能。

副本修复功能

副本缺失通常出现在磁盘损坏的情况。磁盘损坏后，其上的replica也会相应损坏。此时对于存储系统而言，我们需要及时从系统中摘除这块盘，这时某些shard都出现缺失一个replica的情况(这些replica都位于刚刚被摘除的那块盘上)。系统需要在可用的磁盘(需要考虑可用区)上创建出相应的空replica，然后由修复模块自动修复数据即可。

水平扩容

修复工作流程

以3副本为例，修复功能实际工作流程为：

1. 系统处于3副本状态
2. 由于坏盘或者其他故障，系统降低为2副本状态
3. 系统感知到副本缺失，自动创建出1个空副本，回到3副本状态
4. 即3副本->2副本->3副本的过程
5. 修复逻辑开始比较3个副本间的数据diff，将缺失的数据补回

扩容工作流程

扩容过程，与此类似：

1. 假设系统处于3副本状态
2. 开始水平扩容
3. 系统自动新建一个副本，并与之前的副本建立任务关系(源和目标)，此时进入4副本状态
4. 建立任务关系的两个副本之间自行进行数据copy(比如创建snapshot后，copy snapshot或者逐条copy key)
5. 删除源副本，又回归到3副本状态
6. 即3副本->4副本->3副本的过程

异常处理

总结

回顾整个实现过程，我们从一张简单的MySQL表开始，通过13天时间，逐步构建出整个对象存储系统，并论述了各个模块的设计取舍，实现了除分段上传以外的其他功能。分段上传的具体实现不再赘述，读者可以自己思考并实践。此外，还可以思考下面的问题：

免责声明：本网信息来自于互联网，目的在于传递更多信息，并不代表本网赞同其观点。其内容真实性、完整性不作任何保证或承诺。如若本网有任何内容侵犯您的权益，请及时联系我们，本站将会在24小时内处理完毕。