最近看了《大规模分布式存储系统：原理解析与架构实践》，主要介绍了OceanBase数据库的原理和实现，是一本难得的好书。本文介绍书中的关键内容以及自己的想法。如果你有充足的时间，建议直接读原书，没必要花时间阅读本文，如果没有的话，可以阅读本文了解OceanBase的整体架构和关键内容。另外书中的内容是基于OceanBase 0.4版本的，0.4发布于2012年，距今已经8年，一些内容上可能有点陈旧，但是不影响整本书的价值。
1. 背景
OceanBase开发背景是为了解决海量数据的读写问题。举个例子，淘宝有个收藏夹功能，每个用户可以收藏自己感兴趣的商品方便自己访问。收藏夹可以有多个商品，用户可以添加或者删除收藏夹的商品。
- 数据库设计了商品表item和收藏信息表info
- 商品表item有数十亿条记录，收藏信息表info有数百亿条记录
- 每个用户可以收藏几千个商品，热门商品可能被数十万用户收藏
- 商品的价格等信息随时变化
对于这个问题，传统的方案有两种。
一种方案是info表只保存item表的索引，每次按用户ID找到info列表后，再根据索引找到每个item详情返回给用户。这种方案的问题在于，如果info表中的记录比较多，那么关联查询item的时间会很长，尤其是分库分表后，查询item可能需要到很多台机器上查询。这种方案对读不够友好。
另一种方案是info表冗余存储item详情，查询的时候只需要查info表，不需要关联查询item表。但这种方案的问题在于，如果商品item的信息变化了，比如价格修改了，需要修改所有几十万收藏了这个商品的info信息，分库分表后，可能需要到很多台机器上更新。这种方案对写不够友好。
这个问题是OceanBase面临的主要挑战之一。
2. OceanBase架构
大部分互联网业务有个特点就是读多写少，读的次数可能是写的几倍，几十倍，甚至更多。比如游戏业务，读写比可能是5:1，热门视频读写比可能是一百万比一。针对这个特点，OceanBase设计时采用单台更新服务器保存最近一段时间的增量数据。历史数据也叫基线数据保存在基线服务器中。每次查询的时候，从基线服务器取到基线数据，从更新服务器取到增量数据，合并后返回给客户端。更新服务器上的数据会定期同步给基线服务器，这样可以保证更新服务器上的数据不会太大。整体架构如下：
- 客户端：兼容MySQL客户端，支持JDBC，C客户端访问。
- RootServer：管理服务器，管理集群中所有服务器，子表数据分布和副本管理。一主一备强同步。
- UpdateServer：更新服务器，一主一备，可以配置不同的同步模式。一般是强同步模式，异步模式主要用来做异地容灾。异步模式下，有可能会造成一段时间的数据丢失，但因为跨城的延时比较大，一般是30ms ～ 100ms，如果采用强同步方式，性能可能会慢得让你怀疑人生。 另外UpdateServer和RootServer一般部署在同一台物理服务器上。因为两台服务器都是单点，这样可以提升进程间通信的开销。
- ChunkServer：基线服务器，基线数据一般存储三副本，相当于是存储系统的数据存储节点。
- MergeServer：接收并解析客户端SQL请求，将请求转化成物理查询计划后发给ChunkServer或者UpdateServer，合并多个服务器返回的结果，将最终结果发给客户端。MergeServer无状态，相当于是存储系统的计算节点。
2.1 客户端
客户端访问OceanBase流程：
1）请求RootServer获取MergeServer地址列表。
2）选择某台MergeServer发送SQL请求。选择的策略有随机和一致性哈希两种。
3）如果请求MergeServer失败，从MergeServer列表中重新选择一台重试，如果某台MergeServer失败超过一定次数，将这台MergeServer加入黑名单并从列表中删除。客户端还会定期从RootServer更新MergeServer列表。
2.2 RootServer
RootServer主要功能包括集群管理，数据分布和副本管理。
集群管理：RootServer通过租约机制选择主UpdateServer。另外通过和MergeServer以及ChunkServer建立心跳来感知服务器的健康状态。
数据分布：存储数据时，OceanBase使用主键对数据排序后存储。基线数据按照主键划分子表，每个子表默认256MB，默认三副本，分布在多台ChunkServer中。每个子表负责的主键范围保存在RootServer中。一个子表划分例子：
副本管理：当某台ChunkServer故障时，RootServer检测后触发对这台ChunkServer上的子表增加副本的操作。如果某台ChunkServer的负载比较高，RootServer会定期执行负载均衡操作，将某些子表迁移到负载较低的机器上。
2.3 MergeServer
MergeServer主要功能包括协议解析，SQL解析，请求转发，结果合并，多表操作等。
MergeServer缓存了子表分布信息，根据请求设计的子表将请求转发给子表所在的ChunkServer。如果是写操作，还会转发给UpdateServer。如果请求跨多个子表，MergeServer将请求拆分后并发发给多台ChunkServer，合并这些ChunkServer返回的结果。如果某个ChunkServer故障，MergeServer将请求转发给该子表其他副本所在的ChunkServer。
2.4 ChunkServer
ChunkServer主要功能包括存储多个子表，提供读取服务，执行定期合并和数据分发。
OceanBase将大表划分成256MB的子表，每个子表一般由一个SSTable组成，每个SSTable由多个Block组成，每个Block 4KB ～ 64KB之间。子表不能太大也不能太小，太大的话导致子表迁移以及负载均衡成本较高，也不能太小，太小导致元数据会比较大，增加RootServer负担。查找数据时，先根据子表数据分布定位到子表，然后在SSTable中执行二分查找，找到基线数据后，ChunkServer请求UpdateServer获取增量数据，合并基线数据和增量数据的结果。
一般在凌晨的时候，OceanBase会触发UpdateServer的数据分发和合并，这时ChunkServer向UpdateServer请求某段时间的更新操作，和本地数据合并。
2.5 UpdateServer
UpdateServer更新数据流程：
1）同步操作日志到备机
2）写主机操作日志
3）更新内存
4）当内存数量超过一定值，生成快照文件，也即SSTable，存储到SSD中。
如果UpdateServer宕机，RootServer上的租约将失效，然后将备UpdateServer切换为主UpdateServer。宕机的UpdateServer重启后需要先加载快照文件，然后回放快照点之后的操作日志。注意第一步和第二部的顺序不能调换，书中8.3.6节这里的顺序写反了，书中先写本机再同步备机，如果主机在这之间宕机，数据还没有同步到备机，这时备机变成主机，之前宕机的主机重启后，回放快照，包含之前的最后一次更新，但是这时的新主机上没有这次更新，那就冲突了，书中8.4.1中的描述是对的。
注意第一步日志同步到备机，备机只要接收到日志写到内存就可以回复主机，不需要写盘后才回复，这样提高同步性能。而主机是需要写盘后才能回复客户端的。
UpdateServer的租约一般3 ～ 5秒，正常情况下RootServer定期给UpdateServer发送延长租期命令。如果RootServer需要升级，升级过程中，UpdateServer租约过期后系统就停止服务了。书中给出的方案是RootServer在退出前，会给UpdateServer发送一个超长时间的租约，承诺这段时间不进行主UpdateServer选举。但是这里有个隐患，如果这时主UpdateServer宕机了，就无法选择新的UpdateServer了，系统还是无法服务。而且因为RootServer主备强同步，即使RootServer有备机，也不能先升级备RootServer，再升级主RootServer。
因为集群中只有一台主UpdateServer，所以很容易实现事务，相当于是单机事务，而不是分布式事务，都不需要用到两阶段协议。然后通过每日数据合并和分发可以使UpdateServer的内存消耗不至于太大。
UpdateServer的数据结构是一个内存B+树，结构如下：
树中每个叶子节点对应一行数据，key为主键，value为每行按照时间的顺序操作链表。
比如：对主键为1的商品有3个修改操作，分别是：将商品购买人数修改为100，删除该商品，将商品名称修改为“女鞋”，那么，该商品的行操作链中将保存三个Cell，分别为：＜update，购买人数，100＞、＜delete，*＞以及＜update，商品名，“女鞋”＞。
注意这里保存的是操作列表，而不是最终值，这样做有什么好处呢？好处就是在进行事务回滚操作时，只需要把这个操作记录删除就行了。
OceanBase相当于GFS + MemSQL，ChunkServer相当于GFS，UpdateServer相当于MemSQL。
3 关键设计
下面介绍OceanBase关键点的设计方案。
3.1 定期合并和数据分发
定期合并和数据分发都是将UpdateServer中的增量数据分发到ChunkServer的手段，两者有相同的地方，也有不同的地方。相同的地方在于：
1）UpdateServer先冻结当前活跃的内存表，变成冻结的内存表，并开启新的活跃内存表用于保存后续的更新操作。
2）UpdateServer通知RootServer数据版本发生了变化，RootServer通过心跳通知ChunkServer。
3）ChunkServer从UpdateServer获取冻结的更新数据保存到本地。
不同的地方在于：数据分发只是将数据保存到内存，而定期合并会将本地SSTable的基线数据与增量更新数据执行多路归并，生成新的基线数据保存在新的SSTable中。定期合并是一个比较耗性能的操作，为了避免影响正常服务，定期合并会进行限速，而且RootServer通知所有ChunServer数据版本变化时，每个ChunkServer会等待随机一段时间后再开始定期合并，防止所有ChunkServer同时请求UpdateServer。
3.2 顺序写磁盘
不管是机械硬盘还是SSD，随机写磁盘都是一个耗时间的操作。对于机械硬盘，寻道时间比较长。对于SSD存在写入放大效应。所以OceanBase摒弃随机写，采用批量顺序写，提高写盘时的性能。对于随机读，SSD可以轻松应对。
3.3 子表复制与负载均衡
RootServer有一个线程专门执行子表复制和负载均衡任务。
子表复制是指当某个ChunkServer宕机后，为了防止数据丢失，需要增加副本数小于阈值的子表数量。增加副本时，RootServer选择这个子表副本所在的ChunkServer作为源，选择另一台负载较低的ChunkServer作为目的服务器，生成一个子表复制任务，加到任务队列中。
负载均衡是指当某台ChunkServer上的子表个数超过了阈值，把这台ChunkServer上的子表迁移到负载较低的ChunkServer上。
子表复制和负载均衡操作时，RootServer还会限制每个ChunkServer同时执行的任务数量，防止任务太多压垮ChunkServer。
3.4 子表自动分裂与合并
随着数据的增加和减少，每个子表的大小可能会差距非常大，有的几GB，有的几MB。为了维护每个子表的大小差距不至于太大，OceanBase会自动对子表的进行分裂与合并操作。
分裂操作由ChunkServer在定期合并时执行。如果当前子表大于256MB，找到当前子表的中间点作为分裂点，将子表分裂成大小差不多的两个子表。虽然每个子表的副本有多个，但只要所有子表都采用同样的分裂规则，就可以保证分裂后的子表是相同的。
合并操作流程如下：
1）合并准备：RootServer选择若干个主键范围连续的小子表
2）子表迁移：将待合并的若干个小子表迁移到相同的ChunkServer
3）子表合并：往ChunkServer发送子表合并命令，生成合并后的子表范围
因为每个子表有多个副本，只要某一个副本合并成功就行，失败的子表通过垃圾回收机制删除。副本数小于阈值的子表将会在子表复制过程中恢复副本数量。
3.5 SSTable文件结构
SSTable的文件结构如下：
1）第一列下部框图是整个SSTable的结构。每行数据按照主键排序后存放在多个Block中，Block之间也是按照顺序排列。接着存放的是Block Index，把每个Block最后一行的主键作为Block Index。接着是布隆过滤器和表Schema。最后是Trailer和Trailer Offset。Trailer是保存的是各个区域的偏移信息，比如每个Block在哪个位置，Block Index在哪个位置，有了这些位置信息可以快速读取到某个Block的数据，而不需要把整个文件加载到内存。Trailer Offset保存到是Trailer本身的偏移位置。
2）第二列下部框图是Block Index的结构。上部框图是Block结构，先是两个Header信息，接着是每行数据，最后是Row Index，也就是每行的偏移信息，可以快速定位到行。
从SSTable查找数据时，首先读取Trailer Offset信息，根据这个读取Trailer信息，从Trailer中获取到Block Index位置，把Block Index读到内存，通过二分查找找到这个主键属于哪个Block。接着读取Block到内存，再用二分查找找到对应行。
从上面流程看到，整个ChunkServer是一个三级索引结构：子表索引，块索引以及行索引。通过这些索引可以快速读取到行数据。为了进一步加速读取，ChunkServer使用了缓存功能，包含三种：块缓存，行缓存以及块索引缓存。块缓存和行缓存存储访问频繁的数据块和数据行。块索引缓存一般常驻内存，因为块索引一般不会太大。
3.6 UpdateServer瓶颈
UpdateServer的一些性能数据：
千兆网卡每秒收发包超过50万个，万兆网卡每秒收发包超过100万个；
16核机器上B+树每秒单行修改操作查过150万次。
经过网络，内存结构，IO读取，多线程操作等多种优化，UpdateServer的性能已经很卓越了，但是随着应用的场景越来越多，还是有可能成为瓶颈。一种可能的扩展方式是采用数据分片的方式，把所有数据按Hash分片，这样同一个用户的数据会分到同一个UpdateServer。但是这样带来的问题是如果要修改多个用户的数据，就会带来分布式事务的挑战，可以通过两阶段提交或者最终一致性方式实现。
3.7 事务和MVCC
OceanBase支持多线程并发修改，写操作拆分为两个阶段：
1）预提交（多线程执行）：事务执行线程首先锁住待更新数据行，接着，将事务中针对数据行的操作追加到该行的未提交行操作链表中，最后，往提交任务队列中加入一个提交任务。
2）提交（单线程执行）：提交线程不断地扫描并取出提交任务队列中的提交任务，将这些任务的操作日志追加到日志缓冲区中。如果日志缓冲区到达一定大小，将日志缓冲区中的数据同步到备机，同时写入主机的磁盘日志文件。操作日志写成功后，将未提交行操作链表中的cell操作追加到已提交行操作链表的末尾，释放锁并回复客户端写操作成功。
为什么要拆分成两阶段？多个线程同时提交会有什么问题？我能想到的一种解释是提交阶段的写日志缓冲，同步备机和写磁盘这三个操作是没办法多线程执行的，所以把提交阶段设置为单线程执行，而预提交多线程执行，既保证了正确性又兼顾了性能。
另外每个写事务会根据提交时的系统时间生成一个事务版本，读事务只会读取在它之前提交的写事务的修改操作。其中写事务需要加锁，版本号是在提交时生成，而读事务不需要加锁，版本号在预提交时生成。对于读写事务，需要加锁，版本号在提交时生成。举个例子：
对主键为1的商品有2个写事务：
- 事务T1（提交版本号为2）将商品购买人数修改为100，事务T2（提交版本号为4）将商品购买人数修改为50。
- 事务T2预提交时，T1已经提交，该商品的已提交行操作链包含一个cell：＜update，购买人数，100＞，未提交操作链包含一个cell：＜update，购买人数，50＞。事务T2成功提交后，该商品的已提交行操作链将包含两个cell：＜update，购买人数，100＞以及＜update，购买人数，50＞，未提交行操作链为空。
对于读事务：
T3：事务版本号为1，T1和T2均未提交，该行数据为空。
T4：事务版本号为3，T1已提交，T2未提交，读取到＜update，购买人数，100＞。尽管T2在T4执行过程中将购买人数修改为50，T4第二次读取时会过滤掉T2的修改操作，因而两次读取将得到相同的结果。
T5：事务版本号为5，T1和T2均已提交，读取到＜update，购买人数，100＞以及＜update，购买人数，50＞，购买人数最终值为50。
OceanBase锁定粒度为行锁，默认隔离级别是读取已提交（read committed)。read commited会遇到不可重复读和幻读问题，使用MVCC功能，可以解决不可重复读问题。读操作读取某个版本的数据快照，不需要加锁。
- 只写事务：事务预提交时加锁，事务提交时释放锁。如果修改多行数据，使用两阶段锁2PL。
- 读写事务：读操作读取某个版本快照，写操作加锁方式和只写事务相同。
OceanBase处理死锁的方式为事务执行时超过一段时间无法获取锁，回滚事务。
3.8 淘宝收藏夹实现
回到文章开头的问题，如何实现收藏夹？
根据前面的OceanBase的特性，可以采取这样的方案：info表中冗余存储item的信息，用户查询收藏夹时，MergeServer先发请求给ChunkServer请求基线数据，然后ChunkServer再发请求给UpdateServer，获取用户info记录和各个item的增量信息，因为UpdateServer的数据都在内存，即使这个用户收藏了几千个item，获取增量信息也会很快。合并基线和增量信息后，返回给MergeServer，再返回给客户端。
在每日定期合并时，info和item表的增量信息需要合并进ChunkServer的info表中，生成新的基线数据，这样可以减少查询时在UpdateServer上处理的数据量。
4 后续迭代
《大规模分布式存储系统：原理解析与架构实践》书中介绍的OceanBase是0.4版本，发布于2012年，后面几年OceanBase又经过了一系列的迭代改进。
1.0版本
2016年发布1.0版本，主要的变化有两点：
引入Paxos实现真正的高可用和强一致性。
改进架构，将UpdateServer、ChunkServer、MergeServer和RootServer合并为一个ObServer。这样可以减少运维和部署成本。 而ObProxy主要是反向代理的作用，对用户的SQL进行解析，将请求发给对应的ObServer。新的架构如下：
实现多租户功能SQL-VM，隔离不同用户之间资源，包括CPU，内存和IO。
2.0版本
2018年发布2.0版本，和1.0相比架构没有太大变化，主要对扩展性，高可用，一致性，低成本和易用性做了提升，提供了全局一致性快照功能。
看完整本书，个人最大的感受就是如果可能的话，一切都应该自动化，减少人工参与。包括但不限于自动合并分裂子表，自动负载均衡，自动切换主备等。而且系统设计阶段就应该考虑自动化的方式，否则等系统上线运营后再引入自动化可能成本就会比较大。
参考
