Executive Summary

核心观点（金字塔原理）

结论先行: 分布式存储系统通过数据分布、一致性协议和容错机制，实现可扩展、高性能、低成本的海量数据存储能力。

支撑论点:

1. 单机存储引擎（哈希、B树、LSM树）是分布式存储的基石，决定了系统的读写性能特征
2. Paxos与2PC协议相结合，解决了分布式环境下的一致性与原子性问题
3. 不同类型数据（结构化/非结构化/半结构化）需要不同的存储系统架构

SWOT 分析

适用场景

• 大规模Blob数据存储（图片、视频、文档）
• 分布式键值/表格系统的持久化层
• 需要高吞吐量和水平扩展的在线存储服务

第1章 概述

• 分布式存储概念
  1. 分布式存储的几个特性
  2. 可扩展
  3. 低成本
  4. 高性能
  5. 易用
• 分布式系统以及数据库技术
  1. 数据分布
  2. 一致性
  3. 容错
  4. 负载 均衡
  5. 事务与并发控制
  6. 易用性
  7. 压缩/解压缩
• 分布式存储分类
  1. 非结构化数据
  2. 结构化数据
  3. 半结构化数据
• 不同的分布式存储系统适合处理不同类型的数据，共分为四类分布式存储系统：分布式文件系统，分布式键值系统，分布式表格系统，分布式数据库。

第一篇 基础篇

第2章 单机存储系统

• 存储系统的性能主要包括两个维度：吞吐量和访问延时，磁盘和SSD的访问延时差别很大，但带宽差别不大，因此，磁盘适合大块顺序访问的存储系统，SSD适合随机访问较多或者对延时比较敏感的关键系统，二者也常常组合在一起进行混合存储，热数据（访问频繁）存储到SSD中，冷数据（访问不频繁）存储到磁盘中。
• 单机存储引擎
  1. 哈希存储引擎
  2. B树存储引擎
  3. LSM树存储引擎
• 数据模型：文件、关系、键值模型
• 事务与并发控制
  1. 为了提高读事务性能，可以采用写时复制(Copy-On-Write COW)或者多版本并发控制(Multi-Version Concurrency Control MVCC)技术避免写事务阻塞读事务。
  2. ACID
  3. SQL的隔离级别 Read Uncommitted, Read Committed, Repeatable Read, Serializable, Lost Update, Dirty Reads,Non-Repeatable Reads, Second Lost Updates problem, Phantom Reads
  4. 并发控制, 数据库锁
     • 解决死锁的思路主要有两种：1 每个事务设置一个超时时间，超时后自动回滚。2 死锁检测，检测到死锁后可以通过回滚其中某些事务来消除循环依赖。
• 故障恢复
  1. 操作日志
  2. 重做日志
  3. 优化手段
     • 成组提交
     • 检查点
• 数据压缩
  1. 压缩算法
     • Huffman算法，找到一种前缀编码方式使得编码长度最短
     • LZ系列压缩算法，是一种动态创建字典的压缩算法，压缩工程中动态创建字典并保存在压缩信息里面。
     • BMDiff与Zippy
     • 列式存储

第3章 分布式系统

• 分布式系统中有两个重要的协议，包括Paxos选举协议和两个阶段提交协议。Paxos协议用于多个节点之间达成一致， 往往用于实现总控节点选举。两个阶段提交协议用于保证跨多个节点操作的原子性，这些操作要么全部成功，要么全部失败。
• 基本概念
  1. 异常；服务器宕机；网络异常；磁盘故障（磁盘损坏或磁盘数据错误）
  2. 超时，RPC执行结果的三种状态：成功，失败，超时。分布式系统中接口设计为”幂等”，超时时可以不断重试。
  3. 一致性，数据冗余备份时将出现这个问题。从两个角度理解一致性，第一个角度用户，或者称为客户端，即客户端读写 操作是否符合某种特性；第二角度时存储系统，即存储系统的多个副本之间是否一致，更新的顺序是否相同等。 一般要求存储系统能够读写一致性，会话一致性，单调读，单调写等特性。
  4. 衡量指标：性能，每秒处理读操作QPS Query Per Second，每秒写操作 TPS Transaction Per Second。 设计系统时高吞吐量和低延迟需要做个权衡。可用性。一致性。可扩展性。
• 性能分析。
• 数据分布。两种，哈希分布如一致性哈希代表系统Amazon的Dynamo系统；另一个顺序分布，即每张表哥上的数据 按照主键整体有序，代表系统有Google的Bigtable系统。
  1. 哈希分布，只支持随机读取操作不支持顺序扫描。
  2. 顺序分布。
  3. 负载均衡。
• 复制。
• 容错。
  1. 故障检测
  2. 故障恢复
• 可扩展性
  1. 总控节点
  2. 数据库扩容
  3. 异构系统
• 分布式协议
  1. 两个阶段和Paxos协议。两个阶段保证跨多个节点操作的院子性，也就是说跨多个节点的操作要么在所有节点上全部执行成功，要么全部失败。Paxos协议用于确保多个节点对某个投票达成一致。
     • Two-phase Commit 2PC;请求阶段，提交阶段；可能面临的故障，事务参与者发生故障，给每个事务设置一个超时时间，如果某个事务参与者一直不响应，到达超时时间后整个事务失败。协调者发生故障，协调者需要将事务相关信息记录到操作日志并同步到备用协调者，假如协调者发生故障，备用协调者可以接替它完成后续工作，如果没有备用协调者，协调者又发生了永久性故障，事务参与者将无法完成事务而一直等待下去。总而言之，2PC提交协议是阻塞协议，执行过程中需要锁住其他更新，且不能容错，大多数分布式存储系统都敬而远之，放弃对分布式事务的支持。
  2. Paxos协议。准备-》批准-》确认。正确性，可终止性。
  3. Paxos与2PC；Paxos协议一种用法是用它来实现全局的锁服务或者命名的配置服务。另一种用法是用它来将用户数据复制到多个数据中心。2PC协议最大的缺陷在于无法处理协调宕机问题。两者的结合起来，通过2PC保证多个数据分片上操作的原子性，通过Paxos协议实现同一个数据分片的多个副本之间的一致性，另外Paxos解决了2PC的协调者宕机问题，当2PC协调者故障时，通过Paxos协议选举出新的协调者继续提供服务。
     • 跨机房部署
  4. 集群整体切换
  5. 单个集群跨机房
  6. Paxos选主副本。

第二篇 范型篇

第4章 分布式文件系统

• 分布式文件系统的主要功能有两个：一个是存储文档、图像、视频之类的Blob类型数据；另一个作为分布式表格系统的持久化层。
• GFS系统节点分为三种角色：GFS Master(主控服务器)、GFS ChunkServer(CS, 数据块服务器)以及GFS客户端。
• GFS关键问题；
  1. 租约机制
  2. 一致性模型
  3. 追加流程
  4. 容错机制
• Master设计
  1. Master内存占用
  2. 负载均衡
  3. 垃圾回收
  4. 快照
• Taobao File System 读多写基本一次
  1. TFS设计思路：多个逻辑图片文件共享一个物理文件。
  2. NameServer：Block管理，包括创建、删除、复制、重新均衡；DataServer管理，包括心跳、DataServer加入及退出；以及管理Block与所在DataServer之间的映射关系。与GFS Master相比，TFS NameServer最大的不同就是不需要保存文件目录树信息，也不需要维护文件与Block之间的映射关系。
  3. 追加流程
  4. 图片去重是一个键值存储系统。Tair。
• Facebook Haystack
• 内容分发网络
  1. 分级存储
  2. 低功耗服务器定制，考虑是I/O密集型还是CPU密集型。

第5章 分布式键值系统

• Dynamo设计时面临的问题以及解决方案

• 容错
  • Hinted Handoff（数据回传）：当目标节点不可用时，将写操作临时转发到另一个健康节点保存，待原始目标节点恢复后，临时节点将数据回传给它，确保写操作不会因单点故障而丢失。
  • Read Repair（读修复）：在读取操作过程中，协调节点同时从多个副本读取数据并比较，如果发现副本之间存在不一致，则用最新版本的数据修复过期的副本，从而在正常读路径中被动地修复数据不一致问题。
  • Anti-entropy与Merkle Trees（反熵与默克尔哈希树）：每个节点为其管理的数据构建Merkle哈希树，通过逐层比较哈希值可以高效地检测两个副本之间的差异，仅同步不一致的数据块，大幅减少全量同步的开销。
  • 可调一致性（Tunable Consistency）：通过调节N（副本总数）、W（写操作需要确认的副本数）、R（读操作需要确认的副本数）来权衡一致性与可用性。当 W + R > N 时（例如 N=3, W=2, R=2），可以保证强一致性；降低W或R可以提高可用性和性能，但一致性相应减弱。

第6章 分布式表格系统

• Google Bigtable：一个稀疏的、分布式的、持久化的多维有序映射表，数据通过三维键 (row key, column key, timestamp) 进行索引，value为未经解析的字节数组。行按照row key的字典序排列，支持高效的行范围扫描。
• 系统架构：底层使用GFS作为持久化存储层，使用Chubby（分布式锁服务）进行元数据管理、Master选举和服务发现。整体架构由Master Server和多个Tablet Server组成，数据按照row key范围划分为多个Tablet（通常约200MB），每个Tablet由一个Tablet Server负责服务。
• Compaction机制：Minor Compaction将内存中的MemTable冻结并转储为磁盘上的SSTable文件，释放内存空间；Major Compaction将所有SSTable合并为一个新的SSTable，在合并过程中彻底清除已删除的数据和过期版本，回收磁盘空间。
• Schema设计要点：row key的设计对性能至关重要，需要避免热点问题（例如通过反转域名、加盐等手段使请求均匀分布）；Column Family将相关列组织在一起，是访问控制和存储配置的基本单位；合理的row key设计可以使相关数据在物理上相邻存储，提升扫描效率。
• 云端表格存储服务：Microsoft Azure Table Storage和Amazon DynamoDB是基于云平台的分布式表格存储服务，借鉴了Bigtable的设计理念，提供自动扩展、按需付费的托管式表格存储能力。

第7章 分布式数据库

• Google Spanner：全球级分布式数据库，通过TrueTime API（基于GPS和原子钟的高精度时间服务）实现跨数据中心的强一致性。TrueTime提供带有误差边界的全局时间戳，Spanner利用提交等待（commit wait）机制确保事务的时间戳顺序与真实发生顺序一致。
• 外部一致性（External Consistency）：Spanner提供比可串行化隔离级别更强的外部一致性保证——如果事务T1在事务T2开始之前提交完成，则T1的时间戳一定小于T2的时间戳，即事务的全局顺序与它们的实际发生顺序完全一致。
• SQL层与分布式存储的结合：Spanner在分布式存储之上构建了完整的SQL查询引擎，支持SQL查询、分布式事务、在线Schema变更等关系型数据库特性，使开发者可以像使用传统数据库一样使用全球分布式系统。
• OceanBase（阿里巴巴）：采用混合架构设计，UpdateServer负责处理最近的增量更新（存储在内存中，定期转储），ChunkServer存储基线数据（静态数据）。读取时将基线数据与增量更新合并返回，兼顾了写性能和读性能。
• 分布式数据库中的CAP权衡：Spanner选择了CP（一致性+分区容忍性），并通过TrueTime和多副本Paxos复制实现高可用性，接近于”既CP又高可用”；传统分布式数据库如MySQL Cluster和TiDB则使用Raft共识协议实现多副本一致性，在网络分区时优先保证数据一致性。