十十一一资料夹,永不丢失的信息库

资料基本来源于网络,用于归档.

最近看完了杨传辉老师写的《大规模分布式存储系统》一书,发现里面很多知识点和之前看的《大型网站系统与 Java 中间件》有很多相通之处,也渐渐加深了我对分布式技术的兴趣。但无奈分布式涵盖范围太广了,分布式存储、分布式计算、CAP 理论、Paxos 算法、什么 GFS、Hadoop、Dynamo、BigTable、Spanner 等等,不下点功夫还真不能理顺它们之间的内在关系。所以结合两书以及一些优秀博文,总结了分布式存储的知识体系,为以后打下基础而努力。由于初入泥潭,必然有些理解不当的地方,若有大神路过还望不吝指教。

本文更像是读书笔记,是对知识点的一个梳理,无奈越写越多,部分知识只能点到为止,具体内容可以查看原书或维基百科。

单机存储引擎

哈希

哈希存储引擎是哈希表的持久化实现,支持增、删、改,以及随机读取操作,但不支持顺序扫描,对应的存储系统为键值 (Key-Value) 存储系统,如 Bitcask。它仅支持追加操作,删除也只是通过标识 value 为特殊值,通过定期合并(Compaction)实现垃圾回收。

B 树

B 树存储引擎是 B 树的持久化实现,不仅支持单条记录的增、删、读、改操作,还支持顺序扫描,对应的存储系统是关系数据库。关系数据库中通过索引访问数据,在 Mysql InnoDB 中,有一个称为聚集索引的东西,行的数据存于其中,组织成 B+ 树的结构。更多 B 系树的内容可以参考 这里

LSM 树

LSM 树 (Log Structure Merge Tree) 存储引擎采用批量转储技术来避免磁盘随机写入。其思想很朴素,就是将对数据的修改增量保持在内存中,达到指定的大小限制后将这些修改操作批量写入磁盘。它广泛应用于互联网的后台存储系统, 例如 Google BigTable、 以及 Facebook 开源的 Cassandra 系统。

分布式存储的出现

单机存储随着业务的增长会遇到性能单点故障问题。通常有两种解决方案:

  1. 数据分布:就是把数据分块存在不同的服务器上(分库分表)。
  2. 数据复制:让所有的服务器都有相同的数据,提供相当的服务。

这两种方法都能解决性能上的问题,一般结合使用。而对于数据丢失的问题,我们只能通过第二种方法来完成——数据的冗余存储。但是加入更多的机器,会导致事情变得复杂起来,尤其是分布式事务处理,也就是多台服务器之间的数据如何保持一致性,因为原先单机的 ACID 特性在分布式环境下都用不了了。

数据分布

数据分布主要有两种方式:一种是哈希分布,如一致性哈希(Dynamo);另一种是顺序分布(BigTable)。考虑因素包括读写场景, 即随机还是顺序, 包括如何保证负载均衡从而提高性能等

传统的哈希分布算法简单的将哈希值与服务器个数做除法取模映射。但是当服务器上下线时,数据的重新分布会带来大量的数据迁移。

因此有了 一致性哈希算法 。算法思想如下 : 给系统中每个节点分配一个随机 token,这些 token 构成一个哈希环。执行数据存放操作时,先计算 Key(主键) 的哈希值,然后存放到顺时针方向第一个大于或者等于该哈希值的 token 所在的节点。一致性哈希的优点在于节点加入 / 删除时只会影响到在哈希环中相邻的节点,而对其他节点没影响。增加节点后能很大程度上避免了数据迁移。为了考虑负载均衡,一般还会引入虚拟节点的技术,即一个物理节点会对应着多个虚拟节点(如 Dynamo)。

数据复制

复制协议有两种:强同步复制异步复制。 区别在于用户的写请求是否需要同步到备副本才可以返回成功。

一致性和可用性是矛盾的。强同步复制协议保证主备副本之间的一致性,但是当备副本出现故障时会影响系统可用性。异步复制协议的可用性较好,但是一致性得不到保障,主副本出现故障时还有数据丢失的可能。

这两种协议都是将主副本的数据以某种形式(多为操作日志)发送到其他副本,这种复制协议称为基于主副本的复制协议。当然还有基于多个存储节点的复制协议。比如下面会介绍的 Dynamo 系统的 NWR 复制协议。

故障检测

设计分布式系统的前提就是假定服务器时刻肯能发生故障。故障检测主要有心跳和租约两种机制。

  • 心跳:假设总控机 A 需要确认工作机 B 是否发生故障,那么总控机 A 每隔一段时间,比如 1 秒,向工作机 B 发送一个心跳包。不足之处是若 A 到 B 网络发生故障,则不能确定是否是 B 不再提供服务。
  • 租约:租约机制就是带有超时时间的一种授权。假设机器 A 需要检测机器 B 是否发生故障,机器 A 可以给机器 B 发放租约,机器 B 持有的租约在有效期内才允许提供服务,否则主动停止服务。机器 B 的租约快要到期的时候向机器 A 重新申请租约。租约机制可以解决上述心跳问题的不足。

一致性模型

说起数据一致性,简单说有三种类型(细分会有很多,此处不展开):

  1. 弱一致性(Weak):当你写入一个新值后,读操作在各个数据副本上不保证能读出最新值。比如:某些 cache 系统,网络游戏其它玩家的数据和你没什么关系。
  2. 最终一致性(Eventually):Eventually 是 Weak 的一种特殊情况。当你写入一个新值后,有可能读不出来,但在某个时间窗口之后保证最终能读出来。比如:DNS,电子邮件、Amazon S3,Google 搜索引擎这样的系统。
  3. 强一致性(Strong):新的数据一旦写入,在任意副本任意时刻都能读到新值。比如:文件系统,RDBMS,Azure Table 都是强一致性的。

从这三种一致型的模型上来说,我们可以看到,Weak 和 Eventually 一般来说是异步冗余的,而 Strong 一般来说是同步冗余的,异步的通常意味着更好的性能,但也意味着更复杂的状态控制。同步意味着简单,但也意味着性能下降。

分布式事务

事务的支持对于业务是非常重要的特性,数据库在单机下的 ACID 事务特性是比较到位的,而一旦进行分库分表后就要面对一致性和可用性的问题了,这就是分布式事务了。

CAP 原理

在分布式环境下需要考虑数据的一致性和性能的问题,我们要了解下 CAP 理论

  • 一致性:所有节点在同一时间具有相同的数据。
  • 可用性:保证每个请求不管成功或者失败都有响应。我理解的是系统的性能。
  • 分区容忍性:系统中任意信息的丢失或失败不会影响系统的继续运作。我理解的是系统的抗故障能力。

在分布式系统中,对于这三者不能同时满足。这就是 CAP 理论。

简单地说就是:
1)要想让数据避免单点故障,就得写多份数据。
2)写多份的问题会导致数据一致性的问题。
3)数据一致性的问题又会引发性能问题

NWR 模型

NWR 是一种在分布式存储系统中用于控制一致性级别的策略,应用于 Amazon Dynamo。NWR 模型将 CAP 的选择权交给了用户,由用户自己选择 CAP 中的哪两个。其中,N 代表 N 个备份,W 代表至少写 W 份才认为成功,R 代表至少要读 R 份才认为成功。

  • 如果 W+R>N ,是可以保证强一致性的。因为 W+R > N, 所以 R > N-W,什么意思呢?就是读取的份数必须要大于未成功写的份数,这样至少能读到一份最新值。
  • 如果 W+R<=N,则能够保证最终一致性。
  • 如果我们要高可写的环境,我们可以配置 W=1 R=N。这个时候只要写任何节点成功就认为成功,但是读的时候必须从所有的节点都读出数据。
  • 如果我们要求读的高效率,我们可以配置 W=N R=1。这个时候任何一个节点读成功就认为成功,但是写的时候必须写所有三个节点成功才认为成功。

两阶段提交

英文 Two Phase Commit,也叫 2PC。两阶段提交经常用于分布式事务,是强一致性算法。简要的说就是分两阶段:

第一阶段,主控节点(协调者)询问所有节点(参与者)是否可以提交操作,参与者回应 yes or no。
第二阶段,协调者根据收到的响应,如果所有参与者都回应 yes,则向所有参与者发送 “正式提交” 的命令。参与者完成后恢复 “完成” 消息,协调者收集齐各节点的回应后结束这个 Global Transaction。如果有一个拒绝则给所有参与者发送 “回滚操作”。参与者回滚成功后回应“回滚完成”,协调者收集各结点的“回滚” 回应后,取消这个 Global Transaction。

2PC 说白了就是第一阶段做 Vote,第二阶段做决定的一个算法,相对于单库事务来说就是在提交之前多了准备的阶段。但是也存在着问题,其中一个是同步阻塞操作,这个事情必然会非常大地影响性能。另一个主要的问题是在 TimeOut 上。因此出现了 3PC,主要是将提交过程分为两步,更多描述见 Wikipedia

Paxos 算法

Google Chubby 的作者 Mike Burrows 说过,“世上只有一种一致性算法,那就是 Paxos”,所有其他一致性算法都是 Paxos 算法的残次版本。

Paxos 是一个分布式选举算法, 最大的用途就是保持多个节点数据的一致性。看了好久的 Paxos 算法还是有些迷糊,这里就不给出具体算法了。感兴趣的可以参看 WikiPedia 以及里面给出的示例。

实际上对于一般的开发人员,我们并不需要了解 Paxos 所有细节及如何实现,只需要知道 Paxos 是一个分布式选举算法就够了。当我们以后遇到相似的问题,知道有这样一个技术,可以正确及优雅地解决技术架构上一些难题就够了。

小结

Paxos 协议和 2PC 协议在分布式系统中所起的作用并不相同。Paxos 协议用于保证同一个数据分片的多个副本之间的数据一致性。当这些副本分布到不同的数据中心时,这个需求尤其强烈。2PC 协议用于保证属于多个数据分片上的操作的原子性。这些数据分片可能分布在不同的服务器上,2PC 协议保证多台服务器上的操作要么全部成功,要么全部失败。可见 Paxos 的学术地位不一般。

Paxos 协议有两种用法: 一种用法是用它来实现全局的锁服务或者命名和配置服务,例如 Google Chubby 以及 Apache Zookeeper 还有全局 ID。另外一种用法是用它来将用户数据复制到多个数据中心,例如 Google Megastore 以及 Google Spanner。

2PC 协议最大的缺陷在于无法处理协调者宕机问题。如果协调者宕机,那么,2PC 协议中的每个参与者可能都不知道事务应该提交还是回滚,整个协议被阻塞,执行过程中申请的资源都无法释放。因此,常见的做法是将 2PC 和 Paxos 协议结合起来,通过 2PC 保证多个数据分片上的操作的原子性,通过 Paxos 协议实现同一个数据分片的多个副本之间的一致性。另外,通过 Paxos 协议解决 2PC 协议中协调者宕机问题。当 2PC 协议中的协调者出现故障时,通过 Paxos 协议选举出新的协调者继续提供服务。

下图是几种策略原理的比较,来源于:Google App Engine 的 co-founder Ryan Barrett 在 2009 年的 google i/o 上的演讲《Transaction Across DataCenter》(视频

图中 M/S 是 Master-Slave) 结构,实现简单,但是存在单点故障和数据丢失的问题。M/M 即 Multi-Master,解决了单点故障但是一致性的实现较复杂且存在冲突合并的问题(Vector Clock 解决)。从上图我们可以看到,我们基本上来说不可以让所有的项都绿起来,也就是之前说到的著名的 CAP 理论:一致性,可用性,分区容忍性,你只可能要其中的两个。

分布式系统分类

分布式文件系统

分布式文件系统用于存储 Blob 对象,典型的系统有 Facebook Haystack 以及 Taobao File System(TFS)。分布式文件系统是分布式的基石,通常作为上层系统的底层存储。

总体上看,分布式文件系统存储三种类型的数据 :Blob 对象、定长块以及大文件。在系统实现层面,分布式文件系统内部按照数据块 (chunk) 来组织数据,每个 chunk 的大小大致相同,每个 chunk 可以包含多个 Blob 对象或者定长块,一个大文件也可以拆分为多个 chunk 。

分布式键值系统

分布式键值系统用于存储关系简单的半结构化数据,它只提供基于主键的 CRUD(Create/Read/Update/Delete) 功能。

典型的系统有 Amazon Dynamo 以及 Taobao Tair。从数据结构的角度看,分布式键值系统与传统的哈希表比较类似,不同的是,分布式键值系统支持将数据分布到集群中的多个存储节点。分布式键值系统是分布式表格系统的一种简化实现,一般用作缓存,比如淘宝 Tair 以及 Memcache。一致性哈希是分布式键值系统中常用的数据分布技术。

分布式表格系统

分布式表格系统用于存储关系较为复杂的半结构化数据。分布式表格系统以表格为单位组织数据,每个表格包括很多行,通过主键标识一行,支持根据主键的 CRUD 功能以及范围查找功能。

典型的系统包括 Google Bigtable 以及 Megastore,Microsoft Azure Table Storage,Amazon DynamoDB 等。在分布式表格系统中,同一个表格的多个数据行也不要求包含相同类型的列,适合半结构化数据。

分布式数据库

分布式数据库一般是从单机关系数据库扩展而来,用于存储结构化数据。分布式数据库采用二维表格组织数据,提供 SQL 关系查询语言,支持多表关联,嵌套子查询等复杂操作,并提供数据库事务以及并发控制。

典型的系统包括 MySQL 数据库分片 (MySQL Sharding) 集群,Amazon RDS 以及 Microsoft SQL Azure。分布式数据库支持的功能最为丰富,符合用户使用习惯,但可扩展性往往受到限制。当然,这一点并不是绝对的。Google Spanner 的扩展性就达到了全球级,它不仅支持丰富的关系数据库功能,还能扩展到多个数据中心的成千上万台机器。除此之外,阿里巴巴 OceanBase 也是一个支持自动扩展的分布式关系数据库。

摘录

书中有很多对于分布式的观点对我启发很大,将之引用如下。

  • “Google 的分布式存储系统一步步地从 Bigtable 到 Megastore,再到 Spanner,这也验证了分布式技术和传统关系数据库技术融合的必然性,即底层通过分布式技术实现可扩展性,上层通过关系数据库的模型和接口将系统的功能暴露给用户。” OceanBase 正是看准了这两种技术融合的必然性,才走向了可扩展的关系数据库道路。   
  • “简单就是美。系统开发过程中,如果某个方案很复杂,一般是实践者没有想清楚。”。关于这一点其实很早就听说过,就像贯穿 UNIX 哲学的 KISS 原则(Keep It Simple,Stupid),而作者通过开发复杂的分布式存储系统过程中得出这么宝贵经验,是 “简单就是美” 最好的注解。
  • 中心化 VS 去中心。“主流的分布式系统一般都带有中心节点,这样能够简化设计,而且中心节点只维护少量元数据,一般不会成为性能瓶颈。在实践中 Dynamo 及其开源实现 Cassandra 受到的关注逐渐减少,去中心的设计短期内难以成为主流。”

参考资料

原文地址 http://wuchong.me/blog/2014/08/07/distributed-storage-system-knowledge/
分布式, CAP, 事务, Paxos, 存储