分布式存储系统（问题, 概念, 及领域语言）面试必考点

定义

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

分类

• 非结构化数据，一般的文档
• 结构化数据， 存储在关系数据库中
• 半结构化数据，HTML文档

不同的分布式存储系统适合处理不同类型的数据：

分布式文件系统

• 非结构化数据，这类数据以对象的形式组织，不同对象之间没有关联，这样的数据一般称为Blob(二进制大对象)数据
• 典型的有Facebook Haystack 以及 Taobao File System
• 另外，分布式文件系统也常作为分布式表格系统以及分布式数据库的底层存储，如谷歌的GFS可以作为分布式表格系统Google Bigtable 的底层存储，Amazon的EBS(弹性存储块)系统可以作为分布式数据库(Amazon RDS)的底层存储
• 总体上看，分布式文件系统存储三种类型的数据：Blob对象、定长块以及大文件

分布式键值系统

• 较简单的半结构化数据，只提供主键的CRUD(创建、读取、更新、删除)
• 典型的有Amazon Dynamo 以及 Taobao Tair

分布式表格系统

• 较复杂的半结构化数据，不仅支持CRUD，而且支持扫描某个主键范围
• 以表格为单位组织数据，每个表格包括很多行，通过主键标识一行，支持根据主键的CRUD功能以及范围查找功能
• 典型的有Google Bigtable 以及 Megastore，Microsoft Azure Table Storage，Amazon DynamoDB等

分布式数据库

• 存储结构化数据，一般是由单机关系数据库扩展而来
• 典型的包括 MySQL 数据库分片集群、Amazon RDS以及Microsoft SQL Azure

问题域

分布式存储解决的是单机存储的性能, 单点故障问题, 容量一开始到还在其次, 但随着应用规模的发展, 要解决容量也得必须分布式了.

• 分布式存储解决容量问题即可扩展性的方式, 就是数据分片. 可扩展性是分布式的已经解决的问题, 任何关于分布式存储的现存问题的讨论, 都不会再涉及可扩展性.
• 数据分片也能部分的解决性能问题. 而解决性能问题的方法还包括数据复制.
• 分布式存储解决单点故障问题的手段, 也许是唯一的手段, 就是复制.
• 而复制会带来一致性问题.

鉴于解决容量问题的手段并没有引入新问题, 因而如果要实现一种分布式存储机制, 需解决或者需平衡的是性能(或者说可用性), 单点故障(或者说分区容忍性), 及一致性

基础结构

分层，一般是两到三层

• 最底层分布式文件系统, 解决数据分块，复制, 读写等需求
• 往上是数据结构层, 解决数据模型, CAP取舍等
• 再往上是更高层API, 解决诸如事物等问题

实现关注点

数据分布策略

考虑因素包括读写场景, 即随机还是顺序, 包括如何保证负载均衡从而提高性能等

• 哈希分布, 一致性哈希等
• 顺序分布

一致性策略

• 强一致性: 强一致性(即时一致性) 假如A先写入了一个值到存储系统，存储系统保证后续A,B,C的读取操作都将返回最新值
• 弱一致性: 假如A先写入了一个值到存储系统，存储系统不能保证后续A,B,C的读取操作能读取到最新值。此种情况下有一个“不一致性窗口”的概念，它特指从A写入值，到后续操作A,B,C读取到最新值这一段时间。
• 最终一致性: 最终一致性是弱一致性的一种特例。假如A首先write了一个值到存储系统，存储系统保证如果在A,B,C后续读取之前没有其它写操作更新同样的值的话，最终所有的读取操作都会读取到最A写入的最新值。此种情况下，如果没有失败发生的话，“不一致性窗口”的大小依赖于以下的几个因素：交互延迟，系统的负载，以及复制技术中replica的个数(这个可以理解为master/salve模式中，salve的个数)，最终一致性方面最出名的系统可以说是DNS系统，当更新一个域名的IP以后，根据配置策略以及缓存控制策略的不同，最终所有的客户都会看到最新的值。

最终一致性变体

• Causal consistency(因果一致性): 如果Process A通知Process B它已经更新了数据，那么Process B的后续读取操作则读取A写入的最新值，而与A没有因果关系的C则可以最终一致性。
• Read-your-writes consistency : 如果Process A写入了最新的值，那么Process A的后续操作都会读取到最新值。但是其它用户可能要过一会才可以看到。
• Session consistency : 此种一致性要求客户端和存储系统交互的整个会话阶段保证Read-your-writes consistency.Hibernate的session提供的一致性保证就属于此种一致性。
• Monotonic read consistency : 此种一致性要求如果Process A已经读取了对象的某个值，那么后续操作将不会读取到更早的值。
• Monotonic write consistency : 此种一致性保证系统会序列化执行一个Process中的所有写操作。

故障监控策略

• 租约
• 心跳

集群管理策略

• 主控, Paxos协议
• 点对点

分布式事务策略

• 两阶段提交协议

数据模型

• 表
• kv
• 文档
• 列族
• 图

列族和文档在某种程度上是存储模型, 而不是对外的接口模型. 列式存储更适合olap，列族则是对存取性能的优化

查询方式

• SQL
• 主键
• path
• 索引
• 聚合

领域语言

CAP理论

当分布式存储网络中有一台机器与其它机器的连接断开了, 但与客户的连接还在, 即依然有读写请求进来, 那么:

• 如果返回本机上存储的结果, 则保证了AP, 牺牲了C, 即依然在有限时间内返回了响应给请求, 依然没有停止服务, 但不保证结果是正确的
• 如果告诉客户无法完成请求, 则保证了AC, 牺牲了P, 即依然在有限时间内返回了响应给请求, 并保证结果要么是正确的, 要么没结果, 但停止了服务
• 如果一直等待网络连接恢复, 则保证了CP, 牺牲了A, 即依然提供服务, 依然保证返回正确的结果, 但不保证读写操作是可终止的.

一致性哈希

在传统的哈希表中，添加或删除一个节点几乎需要对所有关键字进行重新映射(对N取模变成了对N-1或N+1取模, 影响大了)。而Hash算法的一个衡量指标是单调性( Monotonicity )，定义如下：

• 单调性是指如果已经有一些内容通过哈希分派到了相应的节点中，又有新的节点加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的节点中去，而不会被映射到旧的节点集合中的其他节点区。

一致性哈希是一种特殊的哈希算法。在使用一致哈希算法后，哈希表节点数(大小)的改变平均只需要对K/n 个关键字重新映射，其中 K是关键字的数量，n是节点数量。

向量时钟

当系统中存在同一份数据的多份副本时, 如何决定更新顺序, 处理更新冲突成了一个问题, 因为不存在一个全局时钟(存在的话, 我们就可以在每次更新时记录全局时钟值, 这样的话就有明确的先后顺序). 因此我们需要发明一种在分布式环境下有明确顺序定义的机制. 传统的顺序定义通过版本来定义(时钟只是版本的一种实现手段). 将版本的概念扩展到分布式环境下时, 我们便得到了向量时钟: 对于同一份数据的N份副本, 都独立维护自己的一个版本号, 这些版本号合在一起, 组成一个N个元素的vector, 作为该数据的版本. 每个节点都维护这样一个vector, 初值可能都是0, 每次更新数据时, 一起更新vector中对应自己节点的那个版本号, 然后将vector和被更新的数据一起传播给其它节点. 这样每个节点都可以据此来发现更新冲突。

租约协议

租约主要用来解决心跳的误会问题. 在通常的集群系统中，我们采用心跳来检测节点状态。但普通的心跳机制存在误报警的可能. 普通心跳通常是在规定的时限内定期向检测节点发送存活性报告，若超出一段时间未能收到心跳报告，那么检测节点则判断节点可能失效，并采取一系列措施(报警、通知节点的使用者)。这种机制存在的问题是，检测节点单方面判定节点失效，在某些业务集群系统中可能存在风险。节点自身并未认识自己已被认定失效，还在继续提供正常的服务。若该节点在集群中承担唯一 primary 节点的职责，而检测节点的失效判定发起了重新选择新的主节点，会引发“双主”问题。

租约是一种双方协议, 通常定义为：颁发者在一定期限内給予持有者一定权利的协议. 它表达了颁发者在一定期限内的承诺，只要未过期颁发者必须严格遵守 lease 约定的承诺。而 lease 的持有者可以在期限内使用颁发者的承诺，但 lease 一旦过期必须放弃使用或者重新和颁发者续约。

租约过期前必须向颁发者续约才能继续使用, 因此若因为各种原因续约未果, 则使用者必须放弃租约规定的权利, 而颁发者可以将该权利颁发给其它节点.

lease 作为一种协议承诺，其承诺的范围十分宽泛:

• 如果协议内容是确认客户端存活，那么这个租约就相当于心跳。
• 如果协议内容是保证内容不会被修改，那么这个租约就相当于读锁。
• 如果协议内容是保证只能被某个客户端修改，那么这个租约就相当于写锁。

Paxos协议

Paxos是一个分布式选举算法, 最大的用途就是保持多个节点数据的一致性. 基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、垮、重启，消息可能会延迟、丢失、重复，在基础 Paxos 场景中，先不考虑可能出现消息篡改的情况。Paxos 算法解决的问题是在一个可能发生上述异常的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。

一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。这里的问题在于: 为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。Paxos就是这么一种”一致性算法”

为描述 Paxos 算法，其提出者Lamport 虚拟了一个叫做 Paxos 的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题(Byzantine failure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息);只要等待足够的时间，消息就会被传到。另外，Paxos 岛上的议员是不会反对其他议员提出的决议的。

对应于分布式系统，议员对应于各个节点，制定的法律对应于系统的状态。各个节点需要进入一个一致的状态，例如在独立Cache的对称多处理器系统中，各个处理器读内存的某个字节时，必须读到同样的一个值，否则系统就违背了一致性的要求。一致性要求对应于法律条文只能有一个版本。议员和服务员的不确定性对应于节点和消息传递通道的不可靠性。

具体算法, 可参考网络资料

NWR

NWR是一种在分布式存储系统中用于控制一致性级别的策略。其中，N代表同一份数据的Replica的份数，W是更新一个数据对象时需要确保成功更新的份数;R代表读取一个数据需要读取的Replica的份数。

• R = N 或者 W = N, 强一致性, 弱可用性, 即所有副本数据完全一致才认为成功.
• W + R < N, 强可用性, 弱一致性
• W < N, R < N, 但 W + R > N, 比较均衡的可用性和一致性
• W + R > N，保证某个数据不被两个不同的事务同时读和写
• W > N / 2, 保证两个事务不能并发写某一个数据

常用实现技巧

• 将随机读写转化为顺序读写：操作日志+内存修改+定期刷盘 (先写日志再更新内存)
• 批量提交，成组提交：增加了延迟，但提高了吞吐量
• 从A写从B读才会有一致性问题, 总是从一个入口读写，通过复制和自动选举来解决可靠性可用性, 这是传统热备数据库集群的思路. Mongo是主从结构, 但用户只能与主节点打交道, 主节点宕机后自动选举新主偏重CA, 类似传统热备数据库集群
• 实体组, Entity Group, Aggregate Root: Megastore创新点之一是提出了实体组的概念, 用于融合RDBMS(实体组内)和Nosql(实体组间)的优点
• 将更新的记录单独存放: OceanBase通过分离基线和更新使写操作的负担戏剧性的降到单机可以承受的量，从而兼得了一致性和可靠性可用性
• 分离需要加锁和可以并发的操作, 比如写操作并发优化：分离占位和拷贝, 占位加锁，拷贝不需，前提是位置不冲突