背景

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中，成为存储后端的单点。今天我们来解决这个单点问题。如下图所示，为了提升集群拓扑信息的安全和可用性，有两种方案：

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

方案2
方案2实际上是方案1的简化版本
不再依赖于etcd，而是使用braft实现一个简单的KV结构。也拥有三副本，由braft完成3副本之间的数据复制。
在leader节点上集成集群管理逻辑，由这个管理逻辑对集群进行管理。(每个节点都有相同的逻辑，但只有处于leader状态时，才开始工作)
路由信息缓存层和方案一类似，区别在于:

• 使用round robin的方式从元数据服务节点(Metaserver)同步数据。
• 同步的时候，利用raft log index只增不减的特性，作为拓扑信息的版本，避免同步到旧的信息。
• 即使metaserver2个节点宕机，拓扑信息也能正常获取到。

元数据
集群中(metaserver中)需要存储的元数据主要包括：
表相关(shard, replica等)
存储节点相关(IP、磁盘、可用区、资源池等)

表相关元数据
表的元数据主要包括：
表的基本属性(创建时间，shard数量，每个shard的replica数量)。
shard的属性：有哪些replica，该shard在这张表中属于第几个partition(即取mod后的下标)。
replica的属性：需要描述其对应存储节点的信息，以及位于对应节点的具体哪块磁盘上
我们采用如下的proto文件进行描述，通过id和uuid可以建立起对应的关联信息

存储节点相关元数据
存储节点的元数据主要包括：
resource pool的基础信息
每个resource pool有几个可用区
每个可用区由哪些节点组成
每个节点有几块磁盘构成
使用如下proto文件进行描述，构建后端集群的分布情况

image.png

table和存储节点间的关联关系(拓扑信息)
通过这些信息，我们可以建立如下映射关系

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

新的架构

image.png

Day8

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

元数据量级：
假设在S3元数据侧，每个对象需要100Byte进行描述(文件名、objectId等)
假设单个object大小为100KB，总存储规模为100PB，则对应的元数据空间为100T级别 (100PB/100KB * 100Byte)
假设单个object大小为10MB，总存储规模为1000PB，则对应的元数据空间为T级别 (1000PB/10MB * 100Byte = 10TB)
可见，对于一个大规模存储集群，通过元数据的提取和压缩，元数据完全可以使用一个小规模的NewSQL或者分布式KV进行存储。

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

image.png

Day9

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

image.png
方案一
进度信息持久化在MySQL中
接入层

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

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

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

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

新架构
新的架构如下所示：

image.png

Day10

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

EC的基础功能
将原始数据切分为等长的数据块
通过对数据块进行矩阵计算，生成编码块(也称校验块)
数据块的数量用k表示，编码块的数量用m表示
所有的数据块和编码块的长度相等(先忽略数据块的padding问题)
从这(k+m)个块中，任意取出其中的k个，可以通过矩阵运算的方式还原出(k+m)个
eg：

• 假设原始数据为(a,b,c,d,e,f), 使用k=6，m=3的方式，生成3个编码块(g,h,j)，总共9个块
• 任意取其中的 b,c,e,f,h,j 则可以还原出a,d,g

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

  
  image.png

纠删码空间占用
副本数 = (k+m)/m, 以k=6, m=3为例，则副本数为 1.5副本
3副本模式，可以理解为k=1,m=2的特殊场景

读写过程

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

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

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

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

EC模式的读取过程
IO服务收到读请求后，计算出key对应的shard
检查shard对应的k+m个replica的信息，得到前k个replica(由sn_in_shard描述)，优先将请求发送个给这k个replica。当这k个replica返回结果时，直接拼接原始数据返回即可(读取的时候，尽可能避免走EC解码，EC解码对CPU消耗很大)。
同时，新建若干个定时器，构造对应批次的backup request，对应剩余的m个replica

• 如果第一批次返回，则取消这些定时器，避免浪费后端IO
• 如果第一批次的返回值有部分报不存在或者出错，则立即启动上面的定时器
• 由于写入的时候，任意k个以上成功就返回，所以有可能写入的时候失败了
• 或者此时后端部分节点异常
  k+m中有任意k个成功后，即可通过矩阵计算还原出原始数据块并返回

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

k和m的选择
根据上文的计算k越大, m越小，则副本数(k+m)/k=1+m/k越小。那么我们是不是可以把k设置成100，m设置成1呢？这里的k和m 一般受如下几个条件制约
一个shard的replica数量等于k+m，而这些replica是位于不同的node中，这些node是位于不同的可用区中。k=100,m=1要求有101个可用区，一般公司的故障隔离域没有这么多，规模也没有这么大。
原始数据输入后，会切割成k个数据块，如果原始数据长度为1MB的话，那么切割后到后端存储节点只有10KB了，会造成后端节点的IOPS上升(相当于放大了101倍)。
读取的时候，需要并行读取100个数据块，长尾和IOPS都会上升。
那么是不是可以在约束k的情况下，降低m的值呢？这里又引入了另外一个话题。

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

可靠性相关因数
磁盘故障概率：直观解释，假设在某鱼购入一批硬盘，某天中午都同时发生了故障，那么一定会丢数据。
坏盘后的修复速度：假设磁盘故障不是同时发生的，那么只要在连续故障导致数据丢失之前，将数据修复回来，也就是修复速度大于故障速度的话，就不会发生数据丢失。假设有个神器，无论磁盘多大，都能在1秒内修复，那也不会发生数据丢失。
能够容忍发生连续损坏的盘的数量：假设修复时间恒定(比如1小时修复一块盘)，那么此时3副本(可以容忍连续损坏2块盘)的数据可靠性小于10副本的情况(可以连续损坏9块盘)
回顾上文，EC使用k+m的策略，任意k个块就可以恢复原始数据，也就是允许m个损坏。所以从数据可靠性考虑，m越多越好。实际环境中k+m的策略，需要根据资源(机器数、故障隔离域数)、业务IO特点(比如文件大小)进行具体调整。

Day11

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

优化目标

在讨论这些引擎的差别之前，我们先看下存储层的目标。所有的存储的目标都是为了最终数据的读取操作，如果没有读取的话，也就没有存储的动力。如何有效的满足读取目标是各个存储引擎的优化目标。注意，这里我们使用有效的满足而不是高效的满足，区别在于，不是所有的读需求都要求高性能，有些场景，只要能满足就行了。
假设我们采用最简单的策略：
收到一个写请求的时候，在文件系统中的某个指定的目录中(比如"/"下)，以收到的key(blockid, int64 类型)为文件名，创建一个新的文件，并将文件内容写入. 收到读请求的时候，以key文件名，打开文件并读取内容返回。文件不存在，则返回not found。
这种方案如果简单进行测试，发现可以工作，但是是否可以完成目标，该如何进行评估呢？回顾文件系统的实现，我们会发现，本地文件系统，通常也分为元数据存储和数据存储两块。其中元数据主要包括目录树(文件名相关信息)、inode(用于描述文件由哪些数据块组成)、数据块。如下图所示

image.png
本地文件系统的读取过程如下(以读取"/image"文件为例)：
由"/"找到对应的inode(每个文件系统的根inode id通常固定，比如ext2为2，不需要查找过程)
根据inode 2，找到对应的datablock id列表(比如上图中的block id 7) 将数据块(block id7)的内容读出，转换为目录项(可能是一个有序数组，也可能是个B+树)
在目录项中查找"image"，得到对应的inode id(如上图例子为88) 根据inode id(88)，读取对应的inode信息(一段128 byte左右大小的数据，视不同的文件系统而有所区别)
解析inode的内容，得到对应的block id列表(例子中为block id 10,11,15) 由block id查找到对应的磁盘块，进行读取操作
对比下我们系统的架构和读取流程，可以发现和我们的系统的工作过程非常相似。我们的系统也有目录树和inode的概念。目录树就是S3元数据中的name表，而inode则是object表。
在单机文件系统上，通常每个目录是存放在一个B树中。当一个目录下的文件特别多的时候，这个B树就会成为瓶颈。同时一个文件对应一个inode，如何缓存inode避免频繁的读取磁盘，也会成为一个重要的目标。
假设每块磁盘大小为 10TB
每次写入的数据长度为10KB(即一个文件10KB)，此时B树的entry数量为10TB/10KB = 10亿条。
如果单次写入的数据条数为1MB, 则entry数量为 10TB/1MB = 1千万条。
假设每条记录需要 20 + 8 + 8 + 128 = 164byte(假设每个int64由字符串表示时占用20Byte, inode需要128Byte, inode number 8 byte，不考虑其他开销)
1000万条约1.6GB内存，可以全量cache。
10亿条约160GB内存，无法全量cache
通过上面的计算，我们发现当每次写入后端的数据长度较大(比较理想)的时候，可以直接将数据写在文件系统上，不用做其他优化。这里我们实际上是在利用文件系统的设计，在磁盘之上实现了一个meta和data分离的存储。但是，生产环境中往往没有这么理想，后端接受到的value长度往往长短不一(考虑上文的erasecode的编码过程，会将数据切割成等长的k个块，然后发送给后端节点，一个5MB的文件，k=10的话，切割完成之后发送给后端的数据长度只有500KB了)。为了应对复杂场景保证读写性能，必须进行优化。
观察上面的写入过程，核心问题在于文件数量太多，导致B树的条目数和inode数量过多，而通用文件系统很难进行定制性的优化(比如把B树创建在指定的nvme ssd盘上)。为了降低文件的数量，我们可以将不同的数据写入到相同的文件中(比如每1GB 数据使用一个文件，则此时文件数量为 10TB/1GB = 1万条记录，文件系统的meta部分的内存占用降低到可以忽略的程度)。此时我们面临的问题转变为如何有效的根据key(blockid)在一堆文件中，找到对应的数据。
回想在内存里面，我们优化读取性能的时候，通常两种套路：
方法1：k和v放到一个hash中，o(1)的方式进行定位，然后读取
方法2：放在一个有序集合(比如有序数组)，进行折半查找。
其他：其他优化折半查找次数的方法、提升索引效率的方法
在磁盘上，其实我们可用的的优化方法也类似：
方法1：对这些文件内容进行排序，查找时进行折半查找即可。
方法2：建立key(blockid, int64类型)到文件名和文件内部offset的索引，从索引中查找到文件名和位置信息之后，进行读取即可。此索引必须高效，可以放在内存或者nvme ssd中。
根据对文件内容进行排序的时机，可以分为离线排序和在线排序(写入的同时)。最直观的区别在于，在线排序会导致写入性能下降(有点废话，关键路径上做了更多的事情)。

常见存储引擎
根据上文提及的优化手段，目前常见的存储引擎有如下几种
bitcask
b/b+树
LSM tree
上述各种引擎的优化和变种(组合)版本

B/B+树

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

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

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

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

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

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

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

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

优缺点
bitcask类型的引擎，由于meta的定位耗时低(位于内存或者nvme ssd中)，读延迟低。通常只需要一次磁盘IO
写入操作，都是追加写，写吞吐高
所有的读取都是随机读操作，没有顺序遍历能力
空间回收效率低，假设一个文件中的20%的数据已经被删除，则需要读取80%的数据，并写入到新文件后，才能释放20%的空间。

常见优化手段
bitcask的常见优化手段主要集中在优化索引的内存占用，通常内存中需要存储(k, file_name, offset, length)等信息, 因此各种优化手段集中在压缩这些信息(当然也可以不用内存，而使用nvme ssd，比如将索引放到位于nvme ssd上的rocksdb中)
对key的压缩，通常基于一些业务相关的先验知识，或者对于string 类型的key，可以使用trie-tree
假定一个文件大小为2GB，一块磁盘10TB，则其上的文件数量为10TB/2GB = 5*1024, 12bit的文件编号即可表示
将文件内部划分为128byte的block，一个2GB的文件有2GB/128byte =16,777,216 个块，24个bit即可表示
length信息，可以不用存储，比如可以根据先验知识进行读取(比如4K)，实际长度可以通过数据的头部进行描述。保证99%的情况下，只有一次读取过程即可(读出的结果中，有多余的数据进行剔除，不足的话，根据头部中的描述信息，再读一次，也可以对先验知识进行动态学习)。

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

Day12

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

简单实现
删除功能的基本实现如下：
网关接受到Del请求后，通过s3元数据服务，获取到当前对象的object id和对应的block id 列表
通过s3元数据服务，从name表中，删除相应的文件
从object表中，将对应的object id删除
通过IO服务，将对应的block id进行删除

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

修正
删除逻辑和修复逻辑做如下修正：
删除逻辑给后端发送标记删除请求(而非删除请求)
修复逻辑发现标记删除之后，将所有的副本设置为标记删除状态
只有当所有的副本都处于不存在或者标记删除状态时，才进行真正的删除操作
Del功能实现完成，收工回家。

Day13

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

副本修复功能

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

水平扩容

修复工作流程

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

扩容工作流程

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

异常处理
副本之间的copy可能会失败，又回归到原始的3副本状态。因此在copy过程中，所有的数据仍然需要写入到旧的副本上(源副本)
由于copy过程中，旧的副本人仍然在写入，在旧副本退出之前需要做额外的检查工作，确保旧副本上的所有数据都已经进行迁移(优雅退出)
3->4->3后，API侧需要及时感知分布的变化，将请求发送给新副本。我们可以在每个读写response中返回当前shard的最新分布信息(由存储层返回，而非metaserver)。当API对比发现分布发生变化时，及时去metaserver中进行更新即可。
需要注意，EC模式时每个副本上的数据不一样(key相同)，因此源端和目的端必须一一对应(与3副本模式有所区别)

总结

回顾整个实现过程，我们从一张简单的MySQL表开始，通过13天时间，逐步构建出整个对象存储系统，并论述了各个模块的设计取舍，实现了除分段上传以外的其他功能。分段上传的具体实现不再赘述，读者可以自己思考并实践。
此外，还可以思考下面的问题：
如果将一张表的shard数量设定为1(而不是上文的2233)，并且对外提供建表API接口(假设每次调用平均延迟100ms)，此时存储后端读写逻辑与HDFS的异同(注意key只需要table内部唯一即可)。