一、概述

1. 分布式存储概念

定义：分布式存储系统是大量普通PC服务器通过Internet互联，对外作为一个整体提供存储服务。

特性：可扩展、低成本、高性能、易用

挑战：数据、状态信息的持久化，要求在自动迁移、自动容错、并发读写的过程中保证数据的一致性。

技术：分布式系统和数据库。
数据分布、一致性、容错、负载均衡、事务与并发控制、易用性、压缩/解压缩。

2. 分布式存储分类

数据需求：非结构化数据、结构化数据、半结构化数据

分类：分布式文件系统、分布式键值系统、分布式表格系统、分布式数据库。

二、单机存储系统

1. 硬件基础

CPU架构：

IO总线：

网络拓扑：

性能参数：

存储层次架构：

2. 单机存储引擎

哈希存储引擎：

B树存储引擎：

LSM树存储引擎：
LSM树（Log Structured Merge Tree）的思想非常朴素，就是将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，读取时需要合并磁盘中的历史数据和内存中最近的修改操作。LSM树的优势在于有效地规避了磁盘随机写入问题，但读取时可能需要访问较多的磁盘文件。
合并：Minor compaction是指当内存中的MemTable大小到了一定值时，将内存数据转储到SSTable文件中。Major compaction相当于执行一次多路归并：按照主键顺序依次迭代出所有SSTable文件中的记录，如果没有保存价值，则直接抛弃；否则，将其写入到新生成的SSTable文件中。

3. 数据模型

存储系统的数据模型主要包括三类：文件、关系以及随着NoSQL技术流行起来的键值模型。

4. 事务与并发控制

事务：数据库事务具有原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）以及持久性（Durability），即ACID属性。事务的原子性首先体现在事务对数据的修改，即要么全都执行，要么全都不执行。

并发控制：数据库锁、写时复制、多版本并发控制。

5. 故障恢复

操作日志：

重做日志：

优化手段：成组提交、checkpoint

6. 数据压缩

压缩算法：

列式存储：

三、分布式系统

分布式系统中有两个重要的协议，包括Paxos选举协议以及两阶段提交协议。Paxos协议用于多个节点之间达成一致，往往用于实现总控节点选举。两阶段提交协议用于保证跨多个节点操作的原子性，这些操作要么全部成功，要么全部失败。

1. 基本概念

在分布式存储系统中，往往将一台服务器或者服务器上运行的一个进程称为一个节点，节点与节点之间通过网络互联。

异常：大规模分布式存储系统的一个核心问题在于自动容错。然而，服务器节点是不可靠的，网络也是不可靠的，本节介绍系统运行过程中可能会遇到的各种异常。

• 异常类型：服务器宕机、网络异常、磁盘故障
• 超时：在分布式系统中，如果某个节点向另外一个节点发起RPC（Remote Procedure Call）调用，这个RPC执行的结果有三种状态：“成功”、“失败”、“超时”（未知状态），也称为分布式存储系统的三态。

一致性：副本是分布式存储系统容错技术的唯一手段。由于多个副本的存在，如何保证副本之间的一致性是整个分布式系统的理论核心。

从客户端的角度来看，一致性包含如下三种情况：

• 强一致性：假如A先写入了一个值到存储系统，存储系统保证后续A，B，C的读取操作都将返回最新值。当然，如果写入操作“超时”，那么成功或者失败都是可能的，客户端A不应该做任何假设。
• 弱一致性：假如A先写入了一个值到存储系统，存储系统不能保证后续A，B，C的读取操作是否能够读取到最新值。
• 最终一致性：最终一致性是弱一致性的一种特例。假如A首先写入一个值到存储系统，存储系统保证如果后续没有写操作更新同样的值，A，B，C的读取操作“最终”都会读取到A写入的最新值。“最终”一致性有一个“不一致窗口”的概念，它特指从A写入值，到后续A，B，C读取到最新值的这段时间。“不一致性窗口”的大小依赖于以下的几个因素：交互延迟，系统的负载，以及复制协议要求同步的副本数。

衡量指标：性能、可用性、一致性、可扩展性（scalability）

2. 性能分析

3. 数据分布

数据分布的方式主要有两种，一种是哈希分布，如一致性哈希，代表系统为Amazon的Dynamo系统；另外一种方法是顺序分布，即每张表格上的数据按照主键整体有序，代表系统为Google的Bigtable系统。

哈希分布：

顺序分布：

负载均衡：工作节点通过心跳包（Heartbeat，定时发送）将节点负载相关的信息，如CPU，内存，磁盘，网络等资源使用率，读写次数及读写数据量等发送给主控节点。

4. 复制

复制的概述：复制协议分为两种，强同步复制以及异步复制，二者的区别在于用户的写请求是否需要同步到备副本才可以返回成功。

一致性与可用性：
CAP理论：一致性（Consistency），可用性（Availability）以及分区可容忍性（Tolerance of network Partition）三者不能同时满足。

5. 容错

容错是分布式存储系统设计的重要目标，只有实现了自动化容错，才能减少人工运维成本，实现分布式存储的规模效应。在分布式系统中，故障检测往往通过租约（Lease）协议实现。

6. 可扩展性

7. 分布式协议

两阶段提交协议用于保证跨多个节点操作的原子性，也就是说，跨多个节点的操作要么在所有节点上全部执行成功，要么全部失败。Paxos协议用于确保多个节点对某个投票（例如哪个节点为主节点）达成一致。

两阶段提交协议：

• 阶段1：请求阶段（Prepare Phase）。在请求阶段，协调者通知事务参与者准备提交或者取消事务，然后进入表决过程。在表决过程中，参与者将告知协调者自己的决策：同意（事务参与者本地执行成功）或者取消（事务参与者本地执行失败）。
• 阶段2：提交阶段（Commit Phase）。在提交阶段，协调者将基于第一个阶段的投票结果进行决策：提交或者取消。当且仅当所有的参与者同意提交事务协调者才通知所有的参与者提交事务，否则协调者通知所有的参与者取消事务。参与者在接收到协调者发来的消息后将执行相应的操作。

例如，A组织B、C和D三个人去爬长城：如果所有人都同意去爬长城，那么活动将举行；如果有一人不同意去爬长城，那么活动将取消。

两阶段提交协议是阻塞协议，执行过程中需要锁住其他更新，且不能容错，大多数分布式存储系统都采用敬而远之的做法，放弃对分布式事务的支持。

Paxos协议：为了实现高可用性，主节点往往将数据以操作日志的形式同步到备节点。这里存在的问题是网络分区的时候，可能会存在多个备节点提议（Proposer，提议者）自己成为主节点。Paxos协议保证，即使同时存在多个proposer，也能够保证所有节点最终达成一致，即选举出唯一的主节点。

常见的做法是将2PC和Paxos协议结合起来，通过2PC保证多个数据分片上的操作的原子性，通过Paxos协议实现同一个数据分片的多个副本之间的一致性。

8. 跨机房部署

跨机房问题主要包含两个方面：数据同步以及服务切换。

跨机房部署方案有三个：集群整体切换、单个集群跨机房、Paxos选主副本。

参考资料
[1] 《 大规模分布式存储系统：原理解析与架构实战 》 杨传辉 著