读书笔记——《大规模分布式存储系统原理解析和架构实战》

---

作者: 康凯森

日期: 2016-04-09

分类: 笔记

---

概述

分布式存储技术

数据分布：均匀，跨机器操作

一致性

容错

负载均衡

事务和并发控制

易用性

压缩/解压缩

数据类型

非结构化数据：图片，音频

结构化数据：二维关系表。 数据模式和内容分开

半结构化数据：模式和内容混在一起。HTML

分布式存储分类：

分布式文件系统：Blob对象，定长块，大文件

分布式键值系统：简单的半结构化数据

分布式表格系统：复杂的半结构化数据

分布式数据库系统：结构化数据

单机存储系统

硬件基础

CPU架构：SMP（共享） NUMA

IO总线：

网络拓扑：

同一数据中心的传输延迟在1ms内 不同地区传输延迟：距离1.52/300000 在几十ms数量级

性能参数

存储层次架构

• 存储系统性能：吞吐量以及访问延时
• 磁盘适合大块顺序访问的存储系统
• SSD适合访问较多或者延时比较敏感的关键系统

单机存储引擎

哈希存储引擎

• 数据结构
• 定期合并 ：标记删除
• 快速恢复 ：索引文件

B树存储引擎

• 数据结构
• 缓冲区管理： LRU LIRS（分为俩级，每一级内部LRU）

LSM树存储引擎

• 存储结构
• 合并

数据模型

文件模型

关系模型

键值模型

SQL和NOSQL

事务和并发控制

事务

• 原子性
• 一致性
• 隔离性
• 持久性

并发控制

数据库锁

解决死锁思路：

• 超时时间
• 死锁检测
• 控制顺序

写时复制

多版本并发控制 MVCC 版本控制

故障恢复

操作日志

重做日志

优化手段

成组提交

• 大小： 数据量超过一定大小则提交
• 时间：距离上次刷入磁盘一定时间则提交

  检查点 checkpoint

数据压缩

压缩算法 ： 压缩比和效率

列式存储：

分布式系统

基本概念

异常

异常类型

• 服务器宕机
• 网络异常： 容错系统的基本原则：网络永远不可靠
• 磁盘故障：磁盘损坏和磁盘数据错误（校验和）

“超时”

RPC结果状态：

• 成功
• 失败
• 超时（未知）

一致性（用户，存储系统）

副本是分布式系统容错的唯一手段 从用户角度：

• 强一致性
• 弱一致性
• 最终一致性

从存储系统角度：

• 副本一致性
• 更新顺序一致性

衡量指标

性能

• 吞吐量： QPS TPS
• 延时

可用性

一致性

可扩展性

性能分析

数据分布

哈希分布

数据倾斜

• 手动拆分
• 自动拆分

一致性哈希（DHT）

顺序分布

顺序分布在分布式表格系统中比较常见

负载均衡

复制

复制的概述

• 强同步协议：一致性好，可用性差
• 异步复制：一致性差，可用性好 同步操作日志（Commit Log)

一致性和可用性：CAP

CAP：一致性，可用性，分区容忍性三者不可同时满足

容错

常见故障

故障检测

• 心跳
• 租约机制：带有超时时间的一种授权

故障恢复

分布式存储系统分为俩级结构： 单层结构和双层结构。

可扩展性

总控节点

数据库扩容

按业务垂直切分，按哈希水平切分

异构系统

分布式协议

俩阶段提交协议

• 协调者 ：一个系统给只有一个
• 事务参与者 ：多个

A邀请B,C,D去爬长城

阶段1：请求阶段

阶段2：提交阶段

• 事务参与者故障 ：设置超时时间
• 协调者发生故障 ： 主备 。 操作日志同步

Paxos 协议

执行步骤：

• 准备： 提议序号N
• 批准：
• 确认

应用：

• 全局锁
• 命名，配置服务
• 将用户数据复制到多个数据中心

跨机房部署

集群整体切换

单个集群跨机房

Paxos 选主副本

用于解决多个节点之间的一致性问题

分布式文件系统

主要功能：

存储Blob类型数据

作为分布式表格系统高的持久化层

GOOGLE 文件系统

系统架构

关键问题

租约机制

• GFS通过租约机制将chunk写操作授权给 ChunkServer.
• 在租约有效期内，对该chunk的写操作都由主 ChunkServer负责，从而减轻Master负载。
• GFS 会对每一个chunk 维护一个版本号来解决上下线数据一致问题。

一致性模型

追加流程

• 流水线：减少延时
• 数据流和控制流分离：优化数据传输

容错机制

master容错

容错机制：操作日志+checkpoit+实时热备

CS容错

容错机制：多副本+校验和

MASTER设计

master内存占用

设每个chunk元数据小于64字节。 则1PB数据的元数据大小：1PB3/64MB64 = 3GB

负载均衡

系统需要创建chunk副本的情况有3种，chunk创建，chunk复制，负载均衡。

垃圾回收

GFS采用延时删除机制

快照

快照只是增加GFS中chunk的引用计数。

chunkserver 设计

磁盘和网络IO密集型应用

讨论

单Master 的设计是可行的

Taobao File System

TFS架构设计时需要考虑如下俩个问题：

• Metadata 信息存储：100亿图片的元数据单机无法提供服务
• 减少图片读取IO次数。

TFS的设计思路：多个逻辑图片共享一个物理文件

系统架构

在TFS中，将大量小文件合并为一个大文件，这个大文件成为block，通过<块ID，文件编号>可以快速确定一个文件。

追加流程

TFS 是写少读多。 系统由需求驱动，用最简单的方式解决用户面临的问题。

nameserver

• 图片去重：用hash算法为图片计算指纹。去重是一个键值系统
• 图片更新：直接写入新图片

Facebook Haystack

系统架构

目录，存储，缓存

写流程

容错处理

目录

存储

内容分发网络

CDN架构

俩级 Cache LVS + Haproxy 方式进行负载均衡

分布式键值系统

只支持对单个 key-value 的增删查改。

Amazon Dynamo

数据分布

采用改进的一致性哈希算法：虚拟节点

同步信息：Gossip 协议。 Gossip协议用于P2P系统中自治节点协调对整个集群的认识。

一致性和复制

NMR：W+R>N N：复制的备份数 W：成功写操作的最少节点数 R：成功读操作的最少节点数

向量时钟来解决冲突

容错

• 数据回传
• Merkle树同步 Merkle:每个非叶子节点对应多个文件，为其所有节点值组合以后的哈希值，叶子节点对应单个数据文件，为文件内容的哈希值。

负载均衡

负载均衡取决于如何给每台机器分配虚拟节点号。

随机分配

数据范围等分 + 随机分配

读写流程

单机实现

存储节点包含3个组件：请求协调，成员和故障检测，存储引擎 请求协调组件采用基于事件驱动的设计

讨论

无中心节点的P2P设计，会有一致性问题。

淘宝 Tair

系统架构

数据分布

根据数据主键计算哈希，分布到Q个桶中，桶是负载均衡和数据迁移的基本单位。 Q取值应该远大于集群的物理机器数，例如Q取值 10240.

容错

数据迁移

config server

config server 存储路由表。

data server

负责数据存储，根据 config server 的要求完成数据的复制和迁移工作。

分布式表格系统

Google bigtable

bigtable 的设计理念是构建在廉价的硬件之上，通过软件层面提供自动化容错和线性可扩展能力。 bigtable 是一个分布式多维映射表。 列族是bigtable访问控制的基本单元。

架构

同HBase

数据分布

为减少访问开销，客户端使用了缓存和预取技术。

复制和一致性

bigtable本质是构建在GFS上的一层分布式索引，通过它解决了GFS的遗留的一致性问题。

容错

同HBase.每条操作日志通过<表格编号，行主键，日志序列号>来唯一标识。

负载均衡

同Hbase.

分裂与合并

顺序分布和哈希分布的区别在于哈希分布往往是静态的，而顺序分布往往是动态的，需要通过分裂和合并操作动态调整。

单机存储

块缓存，行缓存，布隆过滤器。

垃圾回收

标记删除。

Google Megastore

Megastore在bigtable系统之上提供友好的数据库功能支持，增强易用性。 Megastore是介于传统关系型数据库和NoSQL之间的存储技术。

每个用户的所有数据构成一个实体组。

系统架构

组成：

• 客户端库
• 复制服务器
• 协调者

主要功能：

• 映射Megastore数据到bigtable。
• 事务及并发控制
• 跨机房数据复制及读写优化

实体组

• 单个实体组内部支持ACID事务
• 跨实体组事务通过俩阶段提交协议保证
• 通过异步队列支持跨实体组最终一致性

并发控制

读事务

• 最新读取
• 快照读取
• 非一致性读取

写事务

写操作采用 Write-ahead 日志

复制

基于 Paxos 的复制协议机制。

索引

• 局部索引：单个实体组内
• 全局索引：跨多个实体组

协调者

等同于 zookeeper

快速读

利用本地读取实现快速读，减少读取延时和跨机房操作。

协调者的可用性

锁服务

竞争条件

失效操作总是安全的， 生效操作必须谨慎处理。

读取流程

• 本地查询
• 发现位置
• 追赶：获取操作日志，应用操作日志
• 使实体组生效
• 查询数据

  写入流程

• 请求主副本接受
• 准备
• 接受
• 使实体组失效

• 应用操作日志

  讨论

  分布式系统的俩个目标：

• 可扩展性：最终目标是线性可扩展

• 功能：最终目标是支持全功能SQL

Megastore 的主要创新点：

• 提出实体组的数据模型
• 通过 Paxos协议同时保证高可靠性和高可用性

Windows Azure Storage

整体架构

WAS 主要分为俩个部分：

• 定位服务
• 存储区

每个存储区是一个集群。存储区分为三层：

• 文件流层：GFS类似
• 分区层：bigtable 类似
• 前端层

  复制

• 存储区内复制：强同步
• 跨存储区复制：异步

分布式数据库

数据库中间层

架构：MYSQL Sharding

• MYSQL 客户端库
• 中间层 dbproxy：解析客户端SQL请求并转发到后端数据库
• 数据库组 dbgroup
• 元数据服务器：维护 dbgroup 拆分规则并用于dbgroup选主
• 常驻进程 agents

扩容

MYSQL Sharding 一般按照用户id进行哈希分区

Microsoft SQL Azure

数据模型

架构

• SQL Server 实例
• 全局分区管理：维护分区映射信息
• 协议网关：将用户的请求转发到相应主机
• 分布式基础组件

复制和一致性

容错

负载均衡

副本迁移及主备副本切换

多租户

• 操作系统资源限制
• SQL Azure 逻辑数据库容量限制
• SQL Server 物理数据库数据大小限制

Google Spanner

数据模型：和Megastore系统类似

架构

复制与一致性

• Paxos 协议
• 锁表
• 事务管理器

TrueTime

全球时钟同步机制 TrueTime。 实现基础是GPS和原子钟。

并发控制

数据迁移

讨论

分布式技术和关系数据库技术融合的必然性，即底层通过分布式技术实现可扩展性，上层通过关系数据库的模型和接口将系统的功能暴露给用户。

OceanBase架构初探

设计思路

• 单台更新服务器记录最近一段时间的修改增量
• 以前的数据保持不变，以前的数据成为基线数据
• 基线数据以类似分布式文件系统的方式存储于多台基线数据服务器中
• 每次查询都需要把基线数据和增量数据融合后返回给客户端
• 写事务都集中在单台更新服务器中
• 更新服务器的修改增量定期分发到多台基线数据服务器中

系统架构

整体架构

• 客户端
• RootServer：
• UpdateServer：增量更新数据
• ChunkServer:基线数据
• MergeServer:接受并解析用户SQL请求，进过词法分析，语法分析，查询优化等一系列操作后转发给相应的ChunkServer或UpdateServer。结果合并。

客户端

RootServer

• 集群管理
• 数据分布
• 副本管理 每个集群同一时刻只允许一个 UpdateServer提供写服务。 Rootserver与mergeserver和chunkserver之间保持心跳。

  Mergeserver

• 协议解析
• SQL解析
• 请求转发
• 结果合并
• 多表操作

ChunkServer

• 存储多个子表
• 读取服务
• 定期合并
• 数据分发

UpdateServer

集群中唯一能够接受写入的模块，每个集群只有一个主UpdateServer。

定期和并与数据分发

查询结果 = 旧子表 + 冻结内存表 + 新的活跃内存表 = 新子表 + 新的活跃内存表

架构剖析

一致性选择

强一致性会大大简化数据库管理，应用程序也会因此而简化。 修改操作流程如下：

• 将修改操作的操作日志发送到备机
• 将修改操作的操作日志写入主机硬盘
• 将操作日志应用到主机内存表中
• 返回客户端写入成功

数据结构

可靠性和可用性

读写事务

单点性能

SSD支持

SSD写入放大，随机读写性能不好。

数据正确性

• 数据存储校验
• 数据传输校验
• 数据镜像校验
• 数据副本校验

分层结构

• 分布式存储引擎层
• 数据库功能层

分布式存储引擎

公共模块

公共数据结构，内存管理，锁，任务队列，RPC框架，压缩/解压缩。

内存管理

首先注重内存管理的可控性，而不是高效，并防止内存碎片。

全局定长内存池维护了由64KB大小的定长内存块组成的空闲链表。

每个模块实现专用的内存池。

每个线程总是首先尝试从线程局部缓存中申请内存，如果申请不到，再从全局内存池中申请。

基础数据结构

• 哈希表：位锁。 延迟初始化。
• B树：B树支持多线程并发修改。
  • Copy-on-write
  • MVCC存储引擎会在行的末尾追加一个单元记录更新的内容，而不会影响索引结构。
  • 对于删除，MVCC实现为标记删除，即在行的末尾追加一个单元记录行的删除时间，而不会物理删除某行

锁

任务队列

网络框架

压缩和解压缩：LZO。Snappy

rootserver实现机制

数据结构

子表复制和负载均衡

子表分裂和合并

UpdateServer选主

RootServer通过租约机制实现选主。

RootServer主备

主备之间数据强同步。

UpdateServer实现机制

存储引擎

任务模型

主备同步

ChunkServer 实现机制

子表管理

SStable

缓存实现

块缓存，行缓存，块索引缓存。

经典的LRU缓存实现：哈希表+LRU链表 哈希表用于查找，LRU链表用于淘汰。

惊群效应

第一个线程发现行缓存失效时会往缓存中加入一个fake标记，其他线程发现这个标记后会等待一段时间。

缓存预热

IO实现

• 双缓冲区机制实现磁盘预读与CPU处理并行化。
• 双缓冲区广泛应用于生产者和消费者模型，在双缓冲区异步预读的技术中，生产者为磁盘，消费者为CPU。俩个缓冲区，总是一个用于生产者，另一个用于消费者。
• 双缓冲区状态：
  • 双缓冲区都在使用的状态
  • 单个缓冲区空闲
  • 缓冲区的切换

定期合并与数据分发

定期合并限速

消除更新瓶颈

读写优化回顾

• 网络框架优化
• 高性能内存数据结构：内存B树，大部分情况无锁

• 写操作日志优化

  • 成组提交
  • 降低日志缓冲区的锁冲突
  • 日志文件并发写入

• 内存容量优化

  • 精心设计内存数据结构，尽可能节省内存使用
  • 将内存数据很快的分发出去

    数据旁路导入

    数据分区

数据库功能

整体结构

只读事务

只读事务经过词法分析，语法分析，预处理后，转化为逻辑查询计划和物理查询计划。

物理操作符接口

所有的物理运算符构成一个树，每个物理运算的输出结果都可以认为是一个临时的二维表，数中孩子节点的输出总是作为它的父亲节点的输入。

单表操作

• 排序算法 mergegroupby,mergedistinct以及sort都需要使用排序算法。

  • 数据收集
  • 迭代输出
• 哈希算法 hashgroupby,hashdistinct都需要使用哈希算法。

  多表操作

  俩张表实现等值连接方式主要分为俩类：基于哈希的算法，基于排序的算法。

  SQL执行本地化

写事务

写事务执行流程

多版本并发控制

写操作俩个阶段：

• 预提交（多线程执行）
• 提交（单线程）

OLAP业务支持

并发查询

mergeserver将大请求拆分为多个子请求，同时发往每个子请求所在的chunkserver并发执行。

mergeserver会成为性能瓶颈。

列式存储

列式存储的前提是设计好内存数据结构，把CPU操作优化好。

特色功能

大表左连接

• 冗余存储
• 增量修改

质量保证，运维及实践

质量保证

RD开发

• 编码规范
• 代码审核：编码风格审核，实现逻辑审核
• 单元测试
• 快速测试
• RD压力测试

QA测试

• 接口，功能，容灾测试
• 压力测试
• 兼容性测试

试运行

• 业务压力测试
• 线上流量回放
• 灰度上线

使用与运维

系统设计

设计原则

• 容错
• 自动化
• 保持兼容

系统实现

• 重视服务器代码资源管理
• 做好代码审核
• 重视测试

工程现象

• 错误必然出现
• 错误必然复现
• 俩倍数据规模
• 怪异现象的背后总有一个愚蠢的初级bug
• 线上问题自一次出现后，第二次将很快重现

经验法则

• 简单性原则
• 精力投入原则
• 先稳定再优化
• 想清楚，再动手

云存储

分布式技术 + 服务化技术 + 资源隔离 + 虚拟化

SAAS ： 软件即服务

PAAS ： 平台即服务

IAAS ： 基础设施作为服务

云存储技术体系结构：

• 硬件层
• 单机存储层
• 分布式存储层
• 存储访问层

大数据

SQL运算符映射到Mapreduce

如果俩张表很大，且二者的大小比较接近，join字段也没有索引，Sort Merge Join 往往比较高效，然而，如果俩张表格相差很大，hash join往往比较合适。

---

《OLAP 性能优化指南》欢迎 Star&共建

《OLAP 性能优化指南》

欢迎关注微信公众号