大规模分布式存储系统: 原理解析与架构实战

Reference: 杨传辉. 大规模分布式存储系统: 原理解析与架构实战. 机械工业出版社, 2013.

1. 概述

分布式存储系统概念

  • 定义: 大量普通PC服务器通过Internet互联,对外作为一个整体提供存储服务
  • 特性: (1) 可扩展; (2) 低成本; (3) 高性能; (4) 易用
  • 涉及技术: (1) 数据分布; (2) 一致性; (3) 容错; (4) 负载均衡; (5) 事务与并发控制; (6) 易用性; (7) 压缩/解压缩

分布式存储分类

  • 数据需求分类: (1) 非结构化; (2) 半结构化; (3) 结构化
  • 系统分类: (1) 分布式文件系统: 存储非结构化数据对象,比如Facebook Haystack、Taobao File System、Google File System、Amazon Elastic Block Store; (2) 分布式键值系统: 存储关系简单的半结构化数据,只支持基于主键的CRUD功能,比如Amazon Dynamo、Taobao Tair、Memcache; (3) 分布式表格系统: 存储关系较为复杂的半结构化数据,不仅支持简单的CRUD操作,而且支持扫描某个主键范围,支持某种程度上的事务(比如单行事务),主要支持针对单张表格的操作,一般不会有schema的强约束(比如要求包含相同类型的数据),比如Google Bigtable、Google Megastore、Microsoft Azure Table Storage、Amazon DynamoDB; (4) 分布式数据库: 一般是从单机关系数据库扩展而来,用于存储结构化数据,支持关系数据库的大多数功能,比如MySQL数据库分片(MySQL Sharding)集群、Amazon RDS、Microsoft SQL Azure、Google Spanner、OceanBase。

2. 单机存储系统

硬件基础

  • 经典的多CPU架构: Symmetric Multi-Processing(SMP)
  • 为了提高可扩展性,现在的主流服务器架构一般为NUMA(Non-Uniform Memory Access)
  • 常见硬件的大致性能参数
性能参数

单机存储引擎

  • 哈希存储引擎: Bitcask
  • B树存储引擎: InnoDB
  • LSM(Log Structured Merge Tree)树存储引擎: LevelDB

数据模型

  • 文件模型
  • 关系模型
  • 键值模型

事务与并发控制

  • 事务
  • 并发控制: (1) 数据库锁; (2) 写时复制; (3) 多版本并发控制

故障恢复

  • UNDO/REDO日志
  • 优化手段: (1) 成组提交(Group Commit); (2) 检查点(Checkpoint)

数据压缩

  • 压缩算法: (1) Huffman编码; (2) LZ系列压缩算法: LZ77(Gzip)、LZW、LZO; (3) BMDiff与Zippy(Snappy): 被用于Google Bigtable中,也属于LZ系列,但相比传统的LZW或者Gzip,这两种算法的压缩比不算高,但是处理速度非常快
  • 列式存储: 比较适用于OLAP

3. 分布式系统

基本概念

  • 异常: (1) 服务器宕机; (2) 网络异常; (3) 磁盘故障;
  • 一致性: (1) 强一致性; (2) 弱一致性; (3) 最终一致性
  • 衡量指标: (1) 性能: 吞吐量(Throughput)、响应时间(Latency); (2) 可用性; (3) 一致性; (4) 可扩展性

性能分析

性能分析

数据分布

  • 哈希分布(一致性哈希): 为了查找集群中的服务器,需要维护每台机器在哈希环中的位置信息,可以存储O(1)位置信息(前一个、后一个节点信息),或者O(logN)位置信息,或者O(N)位置信息。Dyanmo系统通过牺牲空间换时间,在每台服务器维护整个集群中所有服务器的位置信息,将查找服务器的时间复杂度降为O(1),工程上一般都采用这种做法
  • 顺序分布
  • 负载均衡

复制

  • 复制协议: (1) 强同步复制; (2) 异步复制。二者的区别在于用户的写请求是否需要同步到备副本才可以返回成功
  • 强同步复制和异步复制都是将主副本的数据以某种形式发送到其他副本,这种复制协议称为基于主副本的复制协议(Primary-based Protocol)。除了基于主副本的复制协议,还可能使用基于写多个存储节点的复制协议(Replicated-write Protocol),比如Dynamo系统中的NWR复制协议,但是这种方式在实际系统中比较少见,不建议使用
  • 一致性与可用性: CAP协议

容错

  • 故障检测: 在分布式系统中,故障检测往往通过租约(Lease)协议实现
  • 故障恢复

可扩展性

  • 总控节点: (1) 减少总控节点负载; (2) 采用两级结构
  • 数据库扩容
  • 异构系统

分布式协议

  • 两阶段提交协议(Two-phase Commit, 2PC): 保证属于多个数据分片上的操作的原子性
  • Paxos协议: 保证同一个数据分片的多个副本之间的数据一致性

跨机房部署

  • 集群整体切换
  • 单个集群跨机房
  • Paxos选主副本

4. 分布式文件系统

4.1 Google文件系统

  • 系统架构
  • 租约机制: GFS通过租约(lease)将chunk写操作授权给ChunkServer
  • 一致性模型: GFS主要是为了追加(append)而不是改写(overwrite)设计的
  • 追加流程: (1) 找到持有租约的ChunkServer; (2) 将要追加的记录发送到每一个副本; (3) 当所有副本都确认收到了数据,客户端发起写请求控制命令给主副本,由主副本确认操作顺序; (4) 主副本把写请求提交给所有的备副本,每个备副本会根据主副本确定的顺序执行写操作; (5) 所有备副本成功后,主副本应答客户端

容错

  • Master上保存三种元数据信息: (1) 命令空间(Name Space),也就是整个文件系统的目录结构以及chunk基本信息; (2) 文件到chunk之间的映射; (3) chunk副本的位置信息,每个chunk通常有三个副本。
  • Master容错: (1) 操作日志、checkpoint; (2) 实时热备: Shadow Master; (3) 持久化: master需要持久化前两种元数据,即命名空间及文件到chunk之间的映射
  • ChunkServer容错: (1) 复制多个副本; (2) checksum

Master设计

  • 内存占用: 1PB数据的chunk元信息大小不超过3GB(估计),因此Master内存容量不会成为GFS的系统瓶颈
  • 负载均衡: 选择chunk副本的初始位置策略: (1) 新副本所在的ChunkServer的磁盘利用率低于平均水平; (2) 限制每个ChunkServer”最近”创建的数量; (3) 每个chunk的所有副本不能在同一个机架
  • 垃圾回收: 延迟删除
  • 快照

4.2 Taobao File System

  • 设计思路: 多个逻辑图片文件共享一个物理文件
  • 系统架构: NameServer、DataServer、追加流程
  • 图片去重: 使用键值系统,比如Taobao Tair

4.3 Facebook Haystack

  • 系统架构: 存储(Store,物理存储节点,以物理卷轴的形式组织空间,一般一个物理卷轴很大,比如100GB; 多个物理存储节点上的物理卷轴组成一个逻辑卷轴,用于备份)、目录(Directory, 存放逻辑卷轴和物理卷轴的对应关系,以及照片id到逻辑卷轴之间的映射关系)、缓存(Cache,主要用于解决对CDN提供商过于依赖的问题,提供最近增加的照片的缓存服务)
  • 写流程
  • 容错处理
  • 目录: (1) 提供逻辑卷轴到物理卷轴的映射,维护照片id到逻辑卷轴的映射; (2) 提供负载均衡,为写操作选择逻辑卷轴,为读操作选择物理卷轴; (3) 屏蔽CDN服务,可以选择某些图片请求直接走Haystack缓存; (4) 标记某些逻辑卷轴为只读
  • 存储: 每个物理卷轴对应文件系统中的一个物理文件,基于追加的Index文件,延迟删除

4.4 内存分发网络(CDN)

CDN
  • CDN架构: 两级Cache(L1, L2),每个CDN节点内部通过LVS+Haproxy的方式进行负载均衡,使用Squid服务器缓存Blob图片数据
  • 分级存储: 最热门数据存储到SSD,中等热度的存储到SAS,轻热度的存储到SATA

5. 分布式键值系统

5.1 Amazon Dynamo

Dynamo
  • 一致性哈希
  • 数据回传
  • Merkle树同步
  • 向量时钟(Vector Clock)
  • 读写流程: (1) 选取协调者; (2) 根据NWR协议。读取过程中如果发现某些副本上的数据版本太旧,Dynamo内部会异步发起一次读取修复操作,使用冲突解决后的结果修正错误的版本
  • P2P架构

5.2 Taobao Tair

  • 系统架构: Config Server(Master)、Data Server

6. 分布式表格系统

6.1 Google Bigtable

  • 分布式多维映射表: (row: string, column: string, timestamp: int64) -> string
  • 系统架构: Client、Master、Tablet Server
  • Chubby服务部署在多个数据中心,典型的部署为两地三数据中心五副本。同城的两个数据中心分别部署两个副本,异地的数据中心部署一个副本
  • Bigtable包含三种类型的表格: 用户表(User Table)、元数据表(Meta Table)、根表(Root Table)

  • 客户端查询时,首先从Chubby中读取根表的位置,接着从根表读取所需的元数据子表的位置,然后就可以从元数据子表中找到待查询的用户子表的位置。为了减少访问开销,客户端使用缓存(Cache)和预取(Prefetch)技术
  • Bigtable系统保证强一致性,同一个时刻同一个子表只能被一台Tablet Server服务,这是通过Chubby的互斥锁机制保证的
  • Bigtable本质上是构建在GFS之上的一层分布式索引,通过它解决了GFS遗留的一致性问题

  • 所有的Tablet Server基本信息被保存在Chubby中一个被称为服务器目录(Server Directory)的特殊目录中
  • 为了提高性能,Tablet Server没有为它服务的每个子表写一个操作日志文件,而是把所有它服务的子表的操作日志混在一起写入GFS,每条日志通过<表格编号, 行主键, 日志序列号>来唯一标识。
  • 当某个Tablet Servre宕机后,Master将该Tablet Server服务的子表分配给其他Tablet Server,为了减少Tablet Server从GFS读取的日志数据量,Master将选择一些Tablet Server对日志进行分段排序。排好序后,同一个子表的操作日志连续存放,Tablet Server恢复某个子表时只需要读取该子表对应的操作日志即可

  • 负载均衡: 子表迁移(两次Minor Compaction操作)
  • 子表的分裂与合并

  • Bigtable采用Merge-dump存储引擎。数据写入时需要先写操作日志,成功后应用到内存中的MemTable中。当内存中的MemTable达到一定大小,需要将MemTable转储(dump)到磁盘中生成SSTable文件
  • Compaction: Minor、Merging、Major

  • 缺点: (1) 单副本服务; (2) SSD使用; (3) 架构的复杂性导致Bug定位很难
  • 总体上,Bigtable架构把可扩展性和成本做到了极致,但在线实时服务能力有一定的改进空间,适合通用的离线和半线上应用场合

6.2 Google Megastore

  • Megastore在Bigtable系统上提供友好的数据库功能支持,增强易用性,介于传统的关系型数据库和NoSQL之间的存储技术
  • 系统架构: 客户端(大部分功能集中在客户端,包括映射Megastore操作到Bigtable,事务及并发控制,基于Paxos的复制,将请求分送给复制服务器,通过协调者实现快速读等)、复制服务器(接受客户端的用户请求并转发到所在机房的Bigtable实例,用于解决跨机房连接数过多的问题)、协调者(存储每个机房本地的实体组是否处于最新状态的信息,用于实现快速读)

  • 数据拆分为不同的实体组,每个实体组内的操作日志采用基于Paxos的方式同步到多个机房,保证强一致性。实体组之间通过分布式队列的方式保证最终一致性或者两阶段提交协议的方式实现分布式事务
  • 并发控制: 读事务、写事务
  • 复制: 基于Paxos的复制协议
  • 索引: 局部索引(单个实体组内部)、全局索引

  • 读取流程: (1) 本地查询,通过协调者确认本地数据是否是最新的; (2) 发现位置: 本地读取/多数派读取; (3) 追赶: 利用Paxos协议发起一次无操作的写(Paxos中的no-op); (4) 使实体组生效; (5) 查询数据
  • 写入流程: (1) 请求主副本接受; (2) 准备/接受(Paxos协议): 如果主副本已经接受,可以跳过准备阶段; (3) 使实体组失效; (4) 应用操作日志

6.3 Windows Azure Storage

  • 系统架构: Location Service(Stream Layer、Partition Layer、Front-End Layer)、Storage stamp
  • 整体架构借鉴GFS+Bigtable

7. 分布式数据库

7.1 数据库中间层

  • 为了扩展关系数据库,最简单也是最常见的方法就是应用层按照规则将数据拆分为多个分片,分布到多个数据库节点,并引入一个中间层来对应用屏蔽后端的数据库拆分细节
  • 系统架构: (1) 客户端; (2) 中间层dbproxy: 解析客户端MySQL请求并转发到后端的数据库; (3) 数据库组dbgroup: 由N台数据库机器组成,其中一台是主机(Master),另外N-1台是备机(Slave)。主机负责所有的写事务及強一致读事务,并将操作以binlog的形式复制到备机,备机可以支持有一定延迟的读事务; (4) 元数据服务器: 主要负责维护dbgroup拆分规则并用于dbgroup选主; (5) 常驻进程agents: 部署在每台数据库服务器上的常驻进程,用于实现监控、单点切换、安装、卸载程序等
  • 缺点: (1) 数据库复制; (2) 扩容问题; (3) 动态数据迁移问题

7.2 Microsoft SQL Azure

  • 逻辑模型: 云SQL Server将数据划分为多个分区,通过限制事务只能在一个分区执行来规避分布式事务,通过主备复制(Primary-Copy)协议将数据复制到多个副本,保证高可用性
  • 物理模型: 每个有主键的表格组根据划分主键列有序地分成多个数据分区,分区是云SQL Server复制、迁移、负载均衡的基本单位
  • 系统架构: SQL Server实例、全局分区管理器(Global Partition Manager)、协议网关(Protocol Gateway, 负责将用户的数据库连接请求转发到相应的主分区上)、分布式基础部件(Distributed Fabric, 守护进程)

  • 云SQL Server采用”Quorum Commit”的复制协议
  • 某些备副本可能出现故障,恢复后将往主副本发送本地已经提交的最后一个事务的提交顺序号。如果两者相差不多,主副本将直接发送操作日志给副本;如果两者相差太多,主副本将首先把数据库快照传给备副本,再把快照点之后的操作日志传给备副本

7.3 Google Spanner

  • Spanner构建在Google下一代分布式文件系统Colossus之上。Colossus是GFS的延续,相比GFS,Colossus的主要改进点在于实时性,并且支持海量小文件
  • Universe: 一个Spanner部署实例称为一个Universe
  • Zones: 每个Zone属于一个数据中心,而一个数据中心可能有多个Zone。一般来说,Zone内部的网络通信代价比较低,而Zone与Zone之间通信代价很高
  • 系统架构: Universe Master(监控这个Universe里Zone级别的状态信息)、Placement Driver(提供跨Zone数据迁移的功能)、Location Proxy(提供获取数据的位置信息服务,客户端通过它知道数据由哪台Spanserver服务)、Spanserver(提供存储服务,功能上相当于Bigtable系统中的Tablet Server)

  • 通过Paxos协议,实现跨数据中心的多个副本之间的一致性
  • 锁表实现单个Paxos组内的单机事务,事务管理器实现跨多个Paxos组的分布式事务。为了实现分布式事务,使用两阶段提交协议

  • 为了实现并发控制,数据库需要给每个事务分配全局唯一的事务id。然而,在分布式系统中,很难生成全局唯一id。一种方式是采用Google Percolator中的做法,即专门部署一套Oracle数据库用于生成全局唯一id,虽然逻辑上是一个单点,但是实现的功能单一,因而能够做得很高效。Spanner选择了另外一种做法,即全球时钟同步机制TrueTime
  • TrueTime API返回(时间戳(t), 误差(e)),基于GPS和原子钟实现
  • 延迟提交(Commit Wait): 如果事务T1的提交版本为时间戳,那么事务T1会在$$t_{commit} + e$之后才能提交。这意味着每个写事务的延时至少为2e

8. OceanBase架构初探

  • 基线数据+增量数据
  • 系统架构: 客户端(支持JDBC、C客户端访问)、RootServer(管理集群中的所有服务器,一主一备)、UpdateServer(存储增量更新数据,一主一备,部署时和RootServer往往共用物理服务器)、ChunkServer(存储基线数据)、MergeServer(接受并解析用户的SQL请求,并转发给ChunkServer(如果是写操作,还会转发给UpdateServer),随后对返回结果进行合并)

  • MergeServer将每个子表的读取请求发送到子表所在的ChunkServer,ChunkServer首先读取SSTable中包含的基线数据,接着请求UpdateServer获取相应的增量更新数据,并将基线数据与增量更新数据融合后得到最终结果
  • UpdateServer是集群中唯一能够接受写入的模块,由于集群中只有一台主UpdateServer提供写服务,因此OceanBase很容易地实现了跨行跨表事务,不需要采用传统的两阶段提交协议。
  • OceanBase集群通过定期合并和数据分发这两种机制将UpdateServer一段时间之前的增量更新不断地分散到ChunkServer,而UpdateServer只需要服务最新一小段时间新增的数据,这部分数据往往可以全部放到内存中

  • UpdateServer单点性能优化: (1) 配置较大的内存; (2) 当内存达到一定大小,可以转储到SSD中,同时通过定期合并和数据分发把数据分散到ChunkServer中; (3) 配置千兆甚至万兆网卡,同时针对收发的网络包一般比较小的特点,对UpdateServer的网络框架做了专门的优化,大大提高了每秒收发网络包的个数,使得网络不会成为瓶颈; (4) 配置了带有缓存模块的RAID卡,还实现了写事务的成组提交机制,进一步减少磁盘IO次数
  • SSD的随机读性能非常好,但是随机写性能并不理想,OceanBase整个系统设计时完全摒弃了随机写

  • 数据正确性: (1) 数据存储校验; (2) 数据传输校验; (3) 数据镜像校验; (4) 数据副本校验
  • OceanBase相当于GFS+MemSQL(MemSQL是基于内存的分布式数据库)

9. 分布式存储引擎

9.1 公共模块

  • 内存管理: OceanBase系统有一个全局的定长内存池,这个内存池维护了由64kb大小的定长内存块组成的空闲链表,若用户申请内存不超过64kb,则从其中获取一个64kb的内存块; 否则调用glibc的malloc函数,释放时直接调用free函数。每个模块内部有自己专用的内存池
  • 全局内存池可以统计每个模块的内存使用情况,如果出现内存泄漏,可以很快定位到发生问题的模块;也可以用于辅助调试
  • 哈希表: 位锁(BitLock)、延迟初始化(Lazy Initialization)
  • B树: 写时复制(copy on write),使得读操作永远不会被阻塞
  • LightyQueue: 用于解决全局任务队列锁冲突问题,每个工作线程在不同的槽位上等待

9.2 RootServer实现机制

  • RootTable存储子表数据分布,实现时采用支持写时复制的有序数组
  • 子表复制以及负载均衡生成的子表迁移任务并不会立即执行,而是会加入到迁移源的迁移任务列表中,RootServer中有一个后台线程负责处理
  • UpdateServer选主: Lease机制
  • RootServer主备: 数据强同步,通过Linux HA实现心跳检测,并用VIP(Virtual IP)实现切换

9.3 UpdateServer实现机制

  • 操作日志: DirectIO方式写入以避免污染操作系统的缓存、成组提交(批量写入缓冲区,随后一次性写入)
  • MemTable: 高性能B树、存储对某一行各个列的修改操作、缓存预热(在丢弃冻结MemTable之前的一段时间,每隔一段时间,将一定比率的请求发送给SSTable,而不是冻结MemTable)
  • 网络模型: 为了解决收发小数据包带来的上下文切换问题,OceanBase目前采用Libeasy任务模型,采用多个线程收发包监听一个套接字集合
  • 主备同步: 主UpdateServer往备机推送操作日志,备UpdateServer只要接收到日志就可以回复主UpdateServer同步成功,主UpdateServer接着更新本地内存并将日志刷到磁盘文件中,最后回复客户端写入操作成功

9.4 ChunkServer实现机制

  • ChunkServer内部通过ObMultiVersionTabletImage来存储每个子表的索引信息

SSTable

  • SSTable格式
SSTable格式
  • 查找SSTable时,首先从子表的索引信息中读取SSTable Trailer的偏移位置,接着获取Trailer信息。根据Trailer中记录的信息,可以获取块索引的大小和偏移,从而将整个块索引加载到内存中。根据块索引记录的每个Block最后一行的主键,可以通过二分查找定位到查找的Block。最后将Block加载到内存中,通过二分查找Block中记录的行索引(Row Index)查找到具体某一行。
  • 本质上看,SSTable是一个两级索引结构:块索引以及行索引;而整个ChunkServer是一个三级索引:子表索引、块索引以及行索引
  • SSTable分为两种格式:稀疏格式和稠密格式。ChunkServer中的SSTable是稠密格式,UpdateServer中的SSTable是稀疏格式
  • SSTable支持列组(Column Group),将同一个列组下的多个列的内容存储在一块。列组是一种行列混合存储格式,将每一行的所有列分成多个组(称为列组),每个列组内部按行存储。
  • SSTable支持以Block为单位的压缩功能

缓存实现

  • 快缓存、行缓存、块索引缓存
  • 惊群效应: 假设N个工作线程同时发现一行的缓存失效,所有线程同时读取这行数据并更新行缓存,因而N-1线程不仅做了无用功,还增加了锁冲突。为了解决这个问题,第一个线程发现行缓存失效时会往缓存中加入一个fake标记,其他线程发现后会等待一段时间,直到第一个线程从SSTable中读取这行数据并加入到行缓存后,再进行读取
  • 缓存预热: 由于定期合并在凌晨业务低峰期,因此实际上并不需要进行主动缓存预热,而采取被动缓存预热即可

IO实现

  • ChunkServer采用Linux的libaio实现异步IO,并通过双缓冲区机制实现磁盘预读与CPU处理并行化
  • 写操作日志优化: (1) 成组提交; (2) 降低日志缓冲区的锁冲突(先占位再拷贝); (3) 日志文件并发写入
  • 目前看来,单UpdateServer对于OLTP类数据库业务的性能是足够的

10. 数据库功能

  • MergeServer的MySQL协议模块解析SQL语句,并进行词法分析(采用GNU Flex实现)、语法分析(采用GNU Bison实现)、预处理、并生成逻辑计划和物理执行计划
  • 多版本并发控制: 使用行操作链表记录不同版本的修改操作
  • 大表左连接: 在基线数据中冗余信息(融合两张表),在增量数据中分开存储

11. 质量保证、运维及实践

  • OceanBase借鉴了Oracle数据库中的”系统表”机制,将表格Schema、监控数据、系统内部状态等信息保存到内部系统表中,从而能够基于系统表构建监控界面、运维管理界面以及运维工具

质量保证

OceanBase质量保证体系
  • RD开发: 编码规范、代码审核、单元测试(google test、google mock)、快速测试(quicktest)、RD压力测试(分布式存储引擎压力测试、数据库功能压力测试)
  • QA测试: 接口、功能、容灾测试; 压力测试; Benchmark测试; 兼容性测试
  • 试运行: 业务压力测试、线上流量回放、灰度上线

12. 云存储

  • 云存储技术体系
云存储技术体系

13. 大数据

PASS

Written on July 1, 2017