苹果的味道

分布式计算与存储系列(序章):初入门径

二 11 三月 2014

Filed under Distributed System

Tags 分布式系统 Paxos 一致性哈希算法

过年回来之后就发现电脑坏了，一大通鼓捣之后把上学期记录的文档全都丢掉了，包括上学期看过的这本书《大规模分布式存储系统：原理解析与架构实战》,由于文档丢失了，也反而有了一次重温一下这本书的机会;本文基本上以该书为蓝本，对书中某些内容会做进一步的挖掘，对目前我能获得的所有资料综合整理，遂成此文。

概述

无论是云计算、大数据还是互联网公司的各种应用，其后台基础设施的主要目标都是构建低成本、高性能、可扩展、易用的分布式存储系统。(阿里日照)

分布式存储面临的数据需求比较复杂，大致可以分为三类：

  • 非结构化数据 ：包括所有格式的办公文档、文本、图片、图像、音频和视频信息等。
  • 结构化数据：一般存储在关系数据库中，可以用二维关系表结构来表示。结构化数据的模式（Schema，包括属性、数据类型以及数据之间的联系）和内容是分开的，数据的模式需要预先定义。
  • 半结构化数据：介于非结构化数据和结构化数据之间，HTML 文档就属于半结构化数据。它一般是自描述的，与结构化数据最大的区别在于，半结构化数据的模式结构和内容混在一起，没有明显的区分，也不需要预先定义数据的模式结构。

不同的分布式存储系统适合处理不同类型的数据，本书将分布式存储系统分为四类：分布式文件系统、分布式键值（Key-Value）系统、分布式表格系统和分布式数据库。

  • 分布式文件系统

互联网应用需要存储大量的图片、照片、视频等非结构化数据对象，这类数据以对象的形式组织，对象之间没有关联，这样的数据一般称为Blob（Binary Large Object，二进制大对象）数据。分布式文件系统用于存储Blob 对象，典型的系统有Facebook Haystack。另外，分布式文件系统也常作为分布式表格系统以及分布式数据库的底层存储，如谷歌的GFS（Google File System，存储大文件）可以作为分布式表格系统Google Bigtable 的底层存储，Amazon的EBS（Elastic Block Store，弹性块存储）系统可以作为分布式数据库（Amazon RDS）的底层存储。

  • 分布式键值系统

分布式键值系统用于存储关系简单的半结构化数据，它只提供基于主键的CRUD(Create/Read/Update/Delete)功能，即根据主键创建、读取、更新或者删除一条键值记录。典型的系统有Amazon Dynamo。从数据结构的角度看，分布式键值系统与传统的哈希表比较类似，不同的是，分布式键值系统支持将数据分布到集群中的多个存储节点。分布式键值系统是分布式表格系统的一种简化实现，一般用作缓存，比如Memcache。一致性哈希是分布式键值系统中常用的数据分布技术，因其被Amazon DynamoDB 系统使用而变得相当有名。

  • 分布式表格系统

用于存储关系较为复杂的半结构化数据，与分布式键值系统相比,分布式表格系统不仅仅支持简单的CRUD操作，而且支持扫描某个主键范围。分布式表格系统以表格为单位组织数据，每个表格包括很多行，通过主键标识一行，支持根据主键的CRUD 功能以及范围查找功能。典型的系统包括Google Bigtable 以及Megastore，Microsoft Azure Table Storage，Amazon DynamoDB 等。与分布式数据库相比，分布式表格系统主要支持针对单张表格的操作，不支持一些特别复杂的操作，比如多表关联，多表联接，嵌套子查询；另外，在分布式表格系统中，同一个表格的多个数据行也不要求包含相同类型的列，适合半结构化数据。分布式表格系统是一种很好的权衡，这类系统可以做到超大规模，而且支持较多的功能，但实现往往比较复杂，而且有一定的使用门槛。

  • 分布式数据库

分布式数据库一般是从单机关系数据库扩展而来，用于存储结构化数据。分布式数据库采用二维表格组织数据，提供SQL 关系查询语言，支持多表关联，嵌套子查询等复杂操作，并提供数据库事务以及并发控制。典型的系统包括MySQL数据库分片（MySQL Sharding）集群，Amazon RDS 以及Microsoft SQL Azure。分布式数据库支持的功能最为丰富，符合用户使用习惯，但可扩展性往往受到限制。当然，这一点并不是绝对的.Google Spanner系统是一个支持多数据中心的分布式数据库，它不仅支持丰富的关系数据库功能，还能扩展到多个数据中心的成千上万台机器。

NOTE: 传统关系数据库的事务以及二维关系模型很难高效地扩展到多个存储节点上，另外，关系数据库对于要求高并发的应用在性能上优化空间较大。为了解决关系数据库面临的可扩展性、高并发以及性能方面的问题，各种各样的非关系数据库风起云涌，这类系统成为NoSQL1系统，可以理解为“Not Only SQL”系统。NoSQL系统多得让人眼花缭乱，每个系统都有自己的独到之处，适合解决某种特定的问题。(阿里日照)

单机存储系统

单机存储引擎就是哈希表、B 树等数据结构在机械磁盘、SSD等持久化介质上的实现。单机存储系统是单机存储引擎的一种封装,对外提供文件、键值、表格或者关系模型。单机存储系统的理论来源于关系数据库。数据库将一个或多个操作组成一组,称作事务,事务必须满足原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)以及持久性(Durability),简称为 ACID 特性。多个事务并发执行时,数据库的并发控制管理器必须能够保证多个事务的执行结果不能破坏某种约定,如不能出现事务执行到一半的情况,不能读取到未提交的事务,等等。为了保证持久性,对于数据库的每一个变化都要在磁盘上记录日志,当数据库系统突然发生故障,重启后能够恢复到之前一致的状态。

硬件基础

CPU架构

早期的 CPU 为单核芯片,工程师们很快意识到,仅仅提高单核的速度会产生过多的热量且无法带来相应的性能改善。因此,现代服务器基本为多核或多个 CPU。经典的多CPU 架构为对称多处理结构(Symmetric Multi-Processing,SMP),即在一个计算机上汇集了一组处理器,它们之间对称工作,无主次或从属关系,共享相同的物理内存及总线。SMP架构的主要特征是共享,系统中所有资源(CPU、内存、I/O 等)都是共享的,由于多CPU对前端总线的竞争,SMP的扩展能力非常有限。为了提高可扩展性,现在的主流服务器架构一般为 NUMA(Non-Uniform Memory Access,非一致存储访问)架构。它具有多个 NUMA 节点,每个 NUMA 节点是一个 SMP 结构,一般由多个 CPU(如 4 个)组成,并且具有独立的本地内存、IO槽口等。NUMA节点可以直接快速访问本地内存,也可以通过NUMA 互联互通模块访问其他 NUMA 节点的内存,访问本地内存的速度远远高于远程访问的速度。由于这个特点,为了更好地发挥系统性能,开发应用程序时需要尽量减少不同 NUMA 节点之间的信息交互。

存储层次架构

从分布式系统的角度看,整个集群中所有服务器上的存储介质(内存、机械硬盘,SSD)构成一个整体,其他服务器上的存储介质与本机存储介质一样都是可访问的,区别仅仅在于需要额外的网络传输及网络协议栈等访问开销。

存储系统的性能主要包括两个维度:吞吐量以及访问延时,设计系统时要求能够在保证访问延时的基础上,通过最低的成本实现尽可能高的吞吐量。磁盘和 SSD的访问延时差别很大,但带宽差别不大,因此,磁盘适合大块顺序访问的存储系统,SSD适合随机访问较多或者对延时比较敏感的关键系统。二者也常常组合在一起进行混合存储,热数据(访问频繁)存储到SSD中,冷数据(访问不频繁)存储到磁盘中。

单机存储引擎

存储引擎是存储系统的发动机,直接决定了存储系统能够提供的性能和功能。存储系统的基本功能包括:增、删、读、改,其中,读取操作又分为随机读取和顺序扫描。哈希存储引擎是哈希表的持久化实现,支持增、删、改,以及随机读取操作,但不支持顺序扫描,对应的存储系统为键值(Key-Value)存储系统;B树(B-Tree)存储引擎是B树的持久化实现,不仅支持单条记录的增、删、读、改操作,还支持顺序扫描,对应的存储系统是关系数据库。当然,键值系统也可以通过 B 树存储引擎实现;LSM树(Log-Structured Merge Tree)存储引擎和 B 树存储引擎一样,支持增、删、改、随机读取以及顺序扫描。它通过批量转储技术规避磁盘随机写入问题,广泛应用于互联网的后台 存 储 系 统, 例 如 Google Bigtable、Google LevelDB 以 及 Facebook 开 源 的Cassandra系统。本节分别以 Bitcask、MySQL InnoDB 以及 Google LevelDB 系统为例介绍这三种存储引擎。

哈希存储引擎

Bitcask是一个基于哈希表结构的键值存储系统,它仅支持追加操作(Append-only),即所有的写操作只追加而不修改老的数据。在 Bitcask 系统中,每个文件有一定的大小限制,当文件增加到相应的大小时,就会产生一个新的文件,老的文件只读不写。在任意时刻,只有一个文件是可写的,用于数据追加,称为活跃数据文件(active data file)。而其他达到大小限制的文件，称为老数据文件(older data file)。

数据结构

如下图所示，Bitcask 数据文件中的数据是一条一条的写入操作，每一条记录的数据项分别为主键（key）、value 内容（value）、主键长度（key_sz）、value长度（value_sz）、时间戳（timestamp）以及crc 校验值。（数据删除操作也不会删除旧的条目，而是将value设定为一个特殊的值用作标识）。内存中采用基于哈希表的索引数据结构，哈希表的作用是通过主键快速地定位到value的位置。哈希表结构中的每一项包含了三个用于定位数据的信息，分别是文件编号（file id），value 在文件中的位置（value_pos），value 长度（value_sz），通过读取file_id 对应文件的value_pos 开始的value_sz 个字节，这就得到了最终的value值。写入时首先将Key-Value记录追加到活跃数据文件的末尾，接着更新内存哈希表，因此，每个写操作总共需要进行一次顺序的磁盘写入和一次内存操作。

Structure for Bitcask

Bitcask 在内存中存储了主键和value的索引信息，磁盘文件中存储了主键和value的实际内容。系统基于一个假设，value 的长度远大于主键的长度。假如value的平均长度为1KB，每条记录在内存中的索引信息为32 字节，那么，磁盘内存比为32 : 1。这样，32GB 内存索引的数据量为32GB×32 =1TB。

定期合并

Bitcask 系统中的记录删除或者更新后，原来的记录成为垃圾数据。如果这些数据一直保存下去，文件会无限膨胀下去，为了解决这个问题，Bitcask需要定期执行合并（Compaction）操作以实现垃圾回收。所谓合并操作，即将所有老数据文件中的数据扫描一遍并生成新的数据文件，这里的合并其实就是对同一个key 的多个操作以只保留最新一个的原则进行删除，每次合并后，新生成的数据文件就不再有冗余数据了。

快速恢复

Bitcask 系统中的哈希索引存储在内存中，如果不做额外的工作，服务器断电重启重建哈希表需要扫描一遍数据文件，如果数据文件很大，这是一个非常耗时的过程。Bitcask 通过索引文件（hint file）来提高重建哈希表的速度。简单来说，索引文件就是将内存中的哈希索引表转储到磁盘生成的结果文件。Bitcask 对老数据文件进行合并操作时，会产生新的数据文件，这个过程中还会产生一个索引文件，这个索引文件记录每一条记录的哈希索引信息。与数据文件不同的是，索引文件并不存储具体的value 值，只存储value的位置（与内存哈希表一样）。这样，在重建哈希表时，就不需要扫描所有数据文件，而仅仅需要将索引文件中的数据一行行读取并重建即可，大大减少了重启后的恢复时间。

B树存储引擎

相比哈希存储引擎，B 树存储引擎不仅支持随机读取，还支持范围扫描。关系数据库中通过索引访问数据，在Mysql InnoDB 中，有一个称为聚集索引的特殊索引，行的数据存于其中，组织成B+ 树（B 树的一种）数据结构。

数据结构

如下图所示，MySQL InnoDB按照页面（Page）来组织数据，每个页面对应B+树的一个节点。其中，叶子节点保存每行的完整数据，非叶子节点保存索引信息。数据在每个节点中有序存储，数据库查询时需要从根节点开始二分查找直到叶子节点，每次读取一个节点，如果对应的页面不在内存中，需要从磁盘中读取并缓存起来。B+树的根节点是常驻内存的，因此，B+树一次检索最多需要$h-1$次磁盘IO，复杂度为$O(h)=O(logdN)$（$N$为元素个数，$d$为每个节点的出度，$h$为B+树高度）。修改操作首先需要记录提交日志，接着修改内存中的B+树。如果内存中的被修改过的页面超过一定的比率，后台线程会将这些页面刷到磁盘中持久化。当然，InnoDB实现时做了大量的优化，这部分内容我们不再讨论。

Structure of B+

缓冲区管理

缓冲区管理器负责将可用的内存划分成缓冲区，缓冲区是与页面同等大小的区域，磁盘块的内容可以传送到缓冲区中。缓冲区管理器的关键在于替换策略，即选择将哪些页面淘汰出缓冲池。常见的算法有以下两种。

  • LRU

LRU算法淘汰最长时间没有读或者写过的块。这种方法要求缓冲区管理器按照页面最后一次被访问的时间组成一个链表，每次淘汰链表尾部的页面。直觉上，长时间没有读写的页面比那些最近访问过的页面有更小的最近访问的可能性。

  • LIRS(Low Inter-reference Recency Set)

LRU算法在大多数情况下表现是不错的，但有一个问题：假如某一个查询做了一次全表扫描，将导致缓冲池中的大量页面（可能包含很多很快被访问的热点页面）被替换，从而污染缓冲池。现代数据库一般采用LIRS 算法，将缓冲池分为两级，数据首先进入第一级，如果数据在较短的时间内被访问两次或者以上，则成为热点数据进入第二级，每一级内部还是采用LRU替换算法。Oracle数据库中的Touch Count 算法和MySQL InnoDB 中的替换算法都采用了类似的分级思想。以MySQL InnoDB为例，InnoDB 内部的LRU 链表分为两部分：新子链表（new sublist）和老子链表（old sublist），默认情况下，前者占5/8，后者占3/8。页面首先插入到老子链表，InnoDB要求页面在老子链表停留时间超过一定值，比如1秒，才有可能被转移到新子链表。当出现全表扫描时，InnoDB将数据页面载入到老子链表，由于数据页面在老子链表中的停留时间不够，不会被转移到新子链表中，这就避免了新子链表中的页面被替换出去的情况。

LSM树存储引擎

LSM 树（Log Structured Merge Tree）的思想非常朴素，就是将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，读取时需要合并磁盘中的历史数据和内存中最近的修改操作。LSM树的优势在于有效地规避了磁盘随机写入问题，但读取时可能需要访问较多的磁盘文件。本节介绍LevelDB 中的LSM 树存储引擎。

存储结构

如下图所示，LevelDB存储引擎主要包括：内存中的MemTable和不可变MemTable（Immutable MemTable，也称为Frozen MemTable，即冻结MemTable）以及磁盘上的几种主要文件：当前（Current）文件、清单（Manifest）文件、操作日志（Commit Log，也称为提交日志）文件以及SSTable 文件。当应用写入一条记录时，LevelDB 会首先将修改操作写入到操作日志文件，成功后再将修改操作应用到MemTable，这样就完成了写入操作。

Structure of LSM

当MemTable占用的内存达到一个上限值后，需要将内存的数据转储到外存文件中。LevelDB会将原先的MemTable 冻结成为不可变MemTable，并生成一个新的MemTable。新到来的数据被记入新的操作日志文件和新生成的MemTable中。顾名思义，不可变MemTable中的内容是不可更改的，只能读取不能写入或者删除。LevelDB 后台线程会将不可变MemTable的数据排序后转储到磁盘，形成一个新的SSTable 文件，这个操作称为Compaction。SSTable文件是内存中的数据不断进行Compaction操作后形成的，且SSTable 的所有文件是一种层级结构，第0 层为Level 0，第1 层为Level 1，以此类推。

SSTable中的文件是按照记录的主键排序的，每个文件有最小的主键和最大的主键。LevelDB的清单文件记录了这些元数据，包括属于哪个层级、文件名称、最小主键和最大主键。当前文件记录了当前使用的清单文件名。在LevelDB的运行过程中，随着Compaction的进行，SSTable文件会发生变化，新的文件会产生，老的文件被废弃，此时往往会生成新的清单文件来记载这种变化，而当前文件则用来指出哪个清单文件才是当前有效的。

直观上，LevelDB每次查询都需要从老到新读取每个层级的SSTable文件以及内存中的MemTable。LevelDB做了一个优化，由于LevelDB对外只支持随机读取单条记录，查询时LevelDB首先会去查看内存中的MemTable，如果MemTable包含记录的主键及其对应的值，则返回记录即可；如果MemTable没有读到该主键，则接下来到同样处于内存中的不可变Memtable中去读取；类似地，如果还是没有读到，只能依次从新到老读取磁盘中的SSTable 文件。

合并

LevelDB写入操作很简单，但是读取操作比较复杂，需要在内存以及各个层级文件中按照从新到老依次查找，代价很高。为了加快读取速度，LevelDB内部会执行Compaction操作来对已有的记录进行整理压缩，从而删除一些不再有效的记录，减少数据规模和文件数量。

LevelDB的Compaction操作分为两种：minor compaction 和major compaction。Minor compaction 是指当内存中的MemTable 大小到了一定值时，将内存数据转储到SSTable文件中。每个层级下有多个SSTable，当某个层级下的SSTable文件数目超过一定设置后，levelDB会从这个层级中选择SSTable 文件，将其和高一层级的SSTable 文件合并，这就是major compaction。major compaction相当于执行一次多路归并：按照主键顺序依次迭代出所有SSTable文件中的记录，如果没有保存价值，则直接抛弃；否则，将其写入到新生成的SSTable 文件中。

事务与并发控制

写时复制以及多版本控制2

分布式系统

基本概念

一致性

由于异常的存在,分布式存储系统设计时往往会将数据冗余存储多份,每一份称为一个副本(replica/copy)。这样,当某一个节点出现故障时,可以从其他副本上读到数据。可以这么认为,副本是分布式存储系统容错技术的唯一手段。由于多个副本的存在,如何保证副本之间的一致性是整个分布式系统的理论核心。可以从两个角度理解一致性:第一个角度是用户,或者说是客户端,即客户端读写操作是否符合某种特性;第二个角度是存储系统,即存储系统的多个副本之间是否一致,更新的顺序是否相同,等等。

首先定义如下场景,这个场景包含三个组成部分:

  • 存储系统 :存储系统可以理解为一个黑盒子,它为我们提供了可用性和持久性的保证。
  • 客户端A:客户端A主要实现从存储系统write和read操作。
  • 客户端B和客户端C:客户端B和C是独立于A,并且B和C也相互独立的,它们同时也实现对存储系统的write和read 操作。

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

  • 强一致性 :假如A先写入了一个值到存储系统,存储系统保证后续A,B,C的读取操作都将返回最新值。当然,如果写入操作“超时”,那么成功或者失败都是可能的,客户端A不应该做任何假设。
  • 弱一致性 :假如A先写入了一个值到存储系统,存储系统不能保证后续 A,B,C的读取操作是否能够读取到最新值。
  • 最终一致性 :最终一致性是弱一致性的一种特例。假如A首先写入一个值到存储系统,存储系统保证如果后续没有写操作更新同样的值,A,B,C的读取操作“最终”都会读取到A写入的最新值。“最终”一致性有一个不一致窗口的概念,它特指从A写入值,到后续A,B,C 读取到最新值的这段时间。

不一致性窗口”的大小依赖于以下的几个因素 :交互延迟,系统的负载,以及复制协议要求同步的副本数。

最终一致性描述比较粗略,其他常见的变体如下:

  • 读写 (Read-your-writes)一致性 :如果客户端 A 写入了最新的值,那么 A的后续操作都会读取到最新值。但是其他用户(比如 B 或者 C)可能要过一会才能看到。
  • 会话 (Session)一致性:要求客户端和存储系统交互的整个会话期间保证读写一致性。如果原有会话因为某种原因失效而创建了新的会话,原有会话和新会话之间的操作不保证读写一致性。
  • 单调读 (Monotonic read)一致性 :如果客户端 A 已经读取了对象的某个值,那么后续操作将不会读取到更早的值。
  • 单调写 (Monotonic write)一致性:客户端A的写操作按顺序完成,这就意味着,对于同一个客户端的操作,存储系统的多个副本需要按照与客户端相同的顺序完成。

从存储系统的角度看,一致性主要包含如下几个方面:

  • 副本一致性 :存储系统的多个副本之间的数据是否一致,不一致的时间窗口等;
  • 更新顺序一致性 :存储系统的多个副本之间是否按照相同的顺序执行更新操作。

一般来说,存储系统可以支持强一致性,也可以为了性能考虑只支持最终一致性。从客户端的角度看,一般要求存储系统能够支持读写一致性,会话一致性,单调读,单调写等特性,否则,使用比较麻烦,适用的场景也比较有限。

性能指标

评价分布式存储系统有一些常用的指标,下面分别介绍。

  • 性能

常见的性能指标有 :系统的吞吐能力以及系统的响应时间。其中,系统的吞吐能力指系统在某一段时间可以处理的请求总数,通常用每秒处理的读操作数(QPS,Query Per Second)或者写操作数(TPS,Transaction Per Second)来衡量;系统的响应延迟,指从某个请求发出到接收到返回结果消耗的时间,通常用平均延时或者99.9%以上请求的最大延时来衡量。这两个指标往往是矛盾的,追求高吞吐的系统,往往很难做到低延迟;追求低延迟的系统,吞吐量也会受到限制。因此,设计系统时需要权衡这两个指标。

  • 可用性

系统的可用性(availability)是指系统在面对各种异常时可以提供正常服务的能力。系统的可用性可以用系统停服务的时间与正常服务的时间的比例来衡量,例如某系统的可用性为4个9(99.99%),相当于系统一年停服务的时间不能超过 365 × 24 ×60 /10000 = 52.56 分钟。系统可用性往往体现了系统的整体代码质量以及容错能力。

  • 一致性

上面我们说明了系统的一致性。一般来说,越是强的一致性模型,用户使用起来越简单。笔者认为,如果系统部署在同一个数据中心,只要系统设计合理,在保证强一致性的前提下,不会对性能和可用性造成太大的影响。后文中笔者在Alibaba参与开发的OceanBase 系统以及 Google 的分布式存储系统都倾向强一致性。

  • 可扩展性

系统的可扩展性(scalability)指分布式存储系统通过扩展集群服务器规模来提高系统存储容量、计算量和性能的能力。随着业务的发展,对底层存储系统的性能需求不断增加,比较好的方式就是通过自动增加服务器提高系统的能力。理想的分布式存储系统实现了线性可扩展,也就是说,随着集群规模的增加,系统的整体性能与服务器数量呈线性关系。

数据分布

分布式系统区别于传统单机系统在于能够将数据分布到多个节点,并在多个节点之间实现负载均衡。数据分布的方式主要有两种,一种是哈希分布,如一致性哈希,代表系统为Amazon的Dynamo系统;另外一种方法是顺序分布,即每张表格上的数据按照主键整体有序,代表系统为 Google的Bigtable系统。Bigtable将一张大表根据主键切分为有序的范围,每个有序范围是一个子表。将数据分散到多台机器后,需要尽量保证多台机器之间的负载是比较均衡的。衡量机器负载涉及的因素很多,如机器Load值,CPU,内存,磁盘以及网络等资源使用情况,读写请求数及请求量,等等,分布式存储系统需要能够自动识别负载高的节点,当某台机器的负载较高时，将它服务的部分数据迁移到其他机器,实现自动负载均衡。

分布式存储系统的一个基本要求就是透明性,包括数据分布透明性,数据迁移透明性,数据复制透明性,故障处理透明性。本节介绍数据分布以及数据迁移相关的基础知识。

哈希分布

哈希取模的方法很常见,其方法是根据数据的某一种特征计算哈希值,并将哈希值与集群中的服务器建立映射关系,从而将不同哈希值的数据分布到不同的服务器上。所谓数据特征可以是key-value系统中的主键(key),也可以是其他与业务逻辑相关的值。例如,将集群中的服务器按 0 到 N-1 编号(N为服务器的数量),根据数据的主键(hash(key)%N)或者数据所属的用户id(hash(user_id)% N)计算哈希值,来决定将数据映射到哪一台服务器。如果哈希函数的散列特性很好,哈希方式可以将数据比较均匀地分布到集群中去。而且,哈希方式需要记录的元信息也非常简单,每个节点只需要知道哈希函数的计算方式以及模的服务器的个数就可以计算出处理的数据应该属于哪台机器。然而,找出一个散列特性很好的哈希函数是很难的。这是因为,如果按照主键散列,那么同一个用户 id下的数据可能被分散到多台服务器,这会使得一次操作同一个用户id下的多条记录变得困难;如果按照用户id散列,容易出现“数据倾斜”(data skew)问题,即某些大用户的数据量很大,无论集群的规模有多大,这些用户始终由一台服务器处理。处理大用户问题一般有两种方式,一种方式是手动拆分,即线下标记系统中的大用户(例如运行一次MapReduce作业),并根据这些大用户的数据量将其拆分到多台服务器上。这就相当于在哈希分布的基础上针对这些大用户特殊处理;另一种方式是自动拆分,即数据分布算法能够动态调整,自动将大用户的数据拆分到多台服务器上。

传统的哈希分布算法还有一个问题:当服务器上线或者下线时,N值发生变化,数据映射完全被打乱,几乎所有的数据都需要重新分布,这将带来大量的数据迁移。一种思路是不再简单地将哈希值和服务器个数做除法取模映射,而是将哈希值与服务器的对应关系作为元数据,交给专门的元数据服务器来管理。访问数据时,首先计算哈希值,再查询元数据服务器,获得该哈希值对应的服务器。这样,集群扩容时,可以将部分哈希值分配给新加入的机器并迁移对应的数据。另一种思路就是采用一致性哈希(Distributed Hash Table,DHT) 算法。一致性哈希的具体思想如下:3

基本场景

比如你有N个cache 服务（后面简称cache)，那么如何将一个对象object映射到N个cache上呢，你很可能会采用类似下面的通用方法计算object的hash 值，然后均匀的映射到到N个cache:

$$ hash(object) \% N $$

一切都运行正常，再考虑如下的两种情况:

  • 一个cache服务器m宕掉了（在实际应用中必须要考虑这种情况，这样所有映射到 cache m 的对象都会失效，怎么办，需要把 cache m 从cache 中移除，这时候 cache 是 N-1台，映射公式变成了$hash(object)\%(N-1)$；
  • 由于访问加重，需要添加 cache，这时候 cache 是 N+1 台，映射公式变成了$hash(object)\%(N+1)$；

上述两种情况意味着什么？这意味着突然之间几乎所有的cache都失效了。对于服务器而言，这是一场灾难，洪水般的访问都会直接冲向后台服务器；再来考虑第三个问题，由于硬件能力越来越强，你可能想让后面添加的节点多做点活，显然上面的 hash 算法也做不到。

有什么方法可以改变这个状况呢，当当当,于是一致性哈希算法就开始登上历史的舞台。

哈希算法和单调性

Hash 算法的一个衡量指标是单调性（Monotonicity)，定义如下：

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

容易看到，上面的简单hash算法$hash(object)\%N$难以满足单调性要求。

算法原理

consistent hashing是一种hash算法，简单的说,在移除 / 添加一个 cache 时，它能够尽可能小的改变已存在 key的映射关系，尽可能的满足单调性的要求。

下面就来按照5个步骤简单讲讲 consistent hashing 算法的基本原理。

  • 环形hash空间 考虑通常的 hash 算法都是将value映射到一个32位的key值，也即是0~2^32-1次方的数值空间；我们可以将这个空间想象成一个首（0）尾（ 2^32-1 ）相接的圆环，如下图所示:

环形hash空间

  • 把对象映射到hash 空间

接下来考虑4个对象 object1~object4 ，通过 hash 函数计算出的hash值 key在环上的分布如下图所示。 hash(object1) = key1; … … hash(object4) = key4;

对象初始hash分布

  • 把cache映射到hash空间 Consistent hashing 的基本思想就是将对象和cache都映射到同一个hash数值空间中，并且使用相同的 hash 算法。

假设当前有 A,B和C共3台 cache ，那么其映射结果将如下图所示，他们在 hash 空间中，以对应的hash值排列。

hash(cache A) = key A; … … hash(cache C) = key C;

cache分布

NOTE:说到这里，顺便提一下 cache 的 hash 计算，一般的方法可以使用 cache 机器的 IP 地址或者机器名作为 hash 输入。

  • 把对象映射到cache

现在cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了，接下来要考虑的就是如何将对象映射到 cache 上面了。

在这个环形空间中，如果沿着顺时针方向从对象的key值出发，直到遇见一个cache，那么就将该对象存储在这个cache上，因为对象和cache的hash值是固定的，因此这个cache必然是唯一和确定的。这样不就找到了对象和 cache 的映射方法了吗？！

依然继续上面的例子（参见上图），那么根据上面的方法，对象 object1 将被存储到cache A上；object2和object3对应到cache C；object4 对应到cache B ；

  • 考察cache的变动 前面讲过，通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性，当cache有所变动时，cache会失效，进而对后台服务器造成巨大的冲击，现在就来分析分析 consistent hashing算法。

(1)移除 cache

考虑假设cache B挂掉了，根据上面讲到的映射方法，这时受影响的将仅是那些沿 cache B逆时针遍历直到下一个cache（cache C）之间的对象，也即是本来映射到 cache B上的那些对象。

因此这里仅需要变动对象object4,将其重新映射到 cache C 上即可,如下图所示:

移除Cache

(2)添加 cache

再考虑添加一台新的cache D的情况，假设在这个环形hash空间中，cache D被映射在对象object2和object3之间。这时受影响的将仅是那些沿cache D逆时针遍历直到下一个cache（cache B)之间的对象（它们是也本来映射到cache C上对象的一部分),将这些对象重新映射到cache D上即可。因此这里仅需要变动对象 object2,将其重新映射到cache D上,如下图所示:

添加Cache

  • 虚拟节点 考量Hash算法的另一个指标是平衡性 (Balance)，定义如下：

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。

hash算法并不是保证绝对的平衡，如果 cache较少的话，对象并不能被均匀的映射到cache上，比如在上面的例子中，仅部署cache A和cache C的情况下，在4个对象中， cache A 仅存储了object1 ，而cache C则存储了object2、object3和object4；分布是很不均衡的。

为了解决这种情况,consistent hashing 引入了“虚拟节点”的概念，它可以如下定义：

“虚拟节点”（ virtual node ）是实际节点在hash空间的复制品（replica),一实际个节点对应了若干个“虚拟节点”，这个对应> 个数也成为“复制个数”，“虚拟节点”在hash空间中以hash值排列。

仍以仅部署 cache A 和 cache C的情况为例，在上面我们已经看到,cache分布并不均匀。现在我们引入虚拟节点，并设置“复制个数”为 2 ，这就意味着一共会存在 4 个“虚拟节点”， cache A1, cache A2 代表了 cache A ； cache C1, cache C2 代表了 cache C ；假设一种比较理想的情况，如下图所示:

virtual nodes

此时，对象到“虚拟节点”的映射关系为： objec1->cache A2；objec2->cache A1；objec3->cache C1；objec4->cache C2；因此对象 object1 和 object2 都被映射到了 cache A 上，而 object3 和 object4 映射到了 cache C 上；平衡性有了很大提高。引入“虚拟节点”后，映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在cache时的映射关系如下图所示。

Query Cache

“虚拟节点”的hash计算可以采用对应节点的IP地址加数字后缀的方式。例如假设cache A的IP地址为 202.168.14.241。引入“虚拟节点”前，计算 cache A 的 hash 值：

Hash(“202.168.14.241”);

引入“虚拟节点”后，计算“虚拟节”点 cache A1 和 cache A2 的 hash 值：

Hash(“202.168.14.241#1”);  // cache A1
Hash(“202.168.14.241#2”);  // cache A2

顺序分布

哈希散列破坏了数据的有序性,只支持随机读取操作,不能够支持顺序扫描。某些系统可以在应用层做折衷,比如互联网应用经常按照用户来进行数据拆分,并通过哈希方法进行数据分布,同一个用户的数据分布到相同的存储节点,允许对同一个用户的数据执行顺序扫描,由应用层解决跨多个用户的操作问题。另外,这种方式可能出现某些用户的数据量太大的问题,由于用户的数据限定在一个存储节点,无法发挥分布式存储系统的多机并行处理能力。

顺序分布在分布式表格系统中比较常见,一般的做法是将大表顺序划分为连续的范围,每个范围称为一个子表,总控服务器负责将这些子表按照一定的策略分配到存储节点上。如下图所示,用户表(User表)的主键范围为1~7000,在分布式存储系统中划分为多个子表,分别对应数据范围 1 ~ 1000,1001~2000,...6001~7000。Meta表是可选的,某些系统只有根表(Root表)一级索引,在Root表中维护用户表的位置信息,即每个User子表在哪个存储节点上。为了支持更大的集群规模,Bigtable这样的系统将索引分为两级:根表以及元数据表(Meta 表),由 Meta表维护User表的位置信息,而 Root 表用来维护Meta表的位置信息。读User表时,需要通过Meta 表查找相应的 User 子表所在的存储节点,而读取 Meta 表又需要通过 Root 表查找相应的 Meta 子表所在的存储节点。

Sequence Distribution

顺序分布与B+树数据结构比较类似,每个子表相当于叶子节点,随着数据的插入和删除,某些子表可能变得很大,某些变得很小,数据分布不均匀。如果采用顺序分布,系统设计时需要考虑子表的分裂与合并,这将极大地增加系统复杂度。子表分裂指当一个子表太大超过一定阀值时需要分裂为两个子表,从而有机会通过系统的负载均衡机制分散到多个存储节点。子表合并一般由数据删除引起,当相邻的两个子表都很小时,可以合并为一个子表。一般来说,单个服务节点能够服务的子表数量是有限的,比如 4000~10000 个,子表合并的目的是为了防止系统中出现过多太小的子表,减少系统中的元数据。

分布式协议

分布式系统涉及的协议很多,例如租约,复制协议,一致性协议,其中以两阶段提交协议和Paxos协议最具有代表性。两阶段提交协议用于保证跨多个节点操作的原子性,也就是说,跨多个节点的操作要么在所有节点上全部执行成功,要么全部失败。Paxos协议用于确保多个节点对某个投票(例如哪个节点为主节点)达成一致。本节介绍这两个分布式协议。

两阶段提交协议

两阶段提交协议(Two-phase Commit,2PC)经常用来实现分布式事务,在两阶段协议中,系统一般包含两类节点:一类为协调者(coordinator),通常一个系统中只有一个;另一类为事务参与者(participants,cohorts或workers),一般包含多个。协议中假设每个节点都会记录操作日志并持久化到非易失性存储介质,即使节点发生故障日志也不会丢失。顾名思义,两阶段提交协议由两个阶段组成。在正常的执行过程中,这两个阶段的执行过程如下所述:

  • 阶段 1 :请求阶段(Prepare Phase)。

在请求阶段,协调者通知事务参与者准备提交或者取消事务,然后进入表决过程。在表决过程中,参与者将告知协调者自己的决策 :同意(事务参与者本地执行成功)或者取消(事务参与者本地执行失败)。

  • 阶段 2 :提交阶段(Commit Phase)。

在提交阶段,协调者将基于第一个阶段的投票结果进行决策:提交或者取消。当且仅当所有的参与者同意提交事务协调者才通知所有的参与者提交事务,否则协调者通知所有的参与者取消事务。参与者在接收到协调者发来的消息后将执行相应的操作。

例如,A 组织 B、C 和 D 三个人去爬长城:如果所有人都同意去爬长城,那么活动将举行;如果有一人不同意去爬长城,那么活动将取消。用 2PC 算法解决该问题的过程如下:

  1. 首先 A 将成为该活动的协调者,B、C 和 D将成为该活动的参与者。
  2. 准备阶段 :A 发邮件给 B、C和D,提出下周三去爬山,问是否同意。那么此时A需要等待B、C和D的回复。B、C和D分别查看自己的日程安排表。B、C发现自己在当日没有活动安排,则发邮件告诉A他们同意下周三去爬长城。由于某种原因,D白天没有查看邮件。那么此时 A、B 和 C 均需要等待。到晚上的时候,D 发现了A的邮件,然后查看日程安排,发现下周三当天已经有别的安排,那么 D回复A说活动取消吧。
  3. 此时A收到了所有活动参与者的邮件,并且A发现D下周三不能去爬山。那么A将发邮件通知B、C和D,下周三爬长城活动取消。此时 B、C 回复A“太可惜了”,D回复 A“不好意思”。至此该事务终止。

通过该例子可以发现,2PC 协议存在明显的问题。假如D一直不能回复邮件,那么 A、B 和 C 将不得不处于一直等待的状态。并且 B 和 C 所持有的资源一直不能释放,即下周三不能安排其他活动。当然,A可以发邮件告诉D如果晚上六点之前不回复活动就自动取消,通过引入事务的超时机制防止资源一直不能释放的情况。更为严重的是,假如A发完邮件后生病住院了,即使B、C和D都发邮告诉A同意下周三去爬长城,如果A没有备份,事务将被阻塞,B、C和D下周三都不能安排其他活动。

两阶段提交协议可能面临两种故障:

  • 事务参与者发生故障。给每个事务设置一个超时时间,如果某个事务参与者一直不响应,到达超时时间后整个事务失败。
  • 协调者发生故障。协调者需要将事务相关信息记录到操作日志并同步到备用协调者,假如协调者发生故障,备用协调者可以接替它完成后续的工作。如果没有备用协调者,协调者又发生了永久性故障,事务参与者将无法完成事务而一直等待下去。

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

Paxos 协议

Paxos协议用于解决多个节点之间的一致性问题。多个节点之间通过操作日志同步数据,如果只有一个节点为主节点,那么,很容易确保多个节点之间操作日志的一致性。考虑到主节点可能出现故障,系统需要选举出新的主节点。Paxos协议正是用来实现这个需求。只要保证了多个节点之间操作日志的一致性,就能够在这些节点上构建高可用的全局服务,例如分布式锁服务,全局命名和配置服务等。

为了实现高可用性,主节点往往将数据以操作日志的形式同步到备节点。如果主节点发生故障,备节点会提议自己成为主节点。这里存在的问题是网络分区的时候,可能会存在多个备节点提议(Proposer,提议者)自己成为主节点。Paxos协议保证,即使同时存在多个 proposer,也能够保证所有节点最终达成一致,即选举出唯一的主节点。大多数情况下,系统只有一个proposer,他的提议也总是会很快地被大多数节点接受。Paxos 协议执行步骤如下:

  • 批准(accept):Proposer 发送accept消息要求所有其他节点(acceptor,接受者)接受某个提议值,acceptor可以接受或者拒绝。
  • 确认(acknowledge):如果超过一半的acceptor接受,意味着提议值已经生效,proposer发送acknowledge消息通知所有的acceptor提议生效。

当出现网络或者其他异常时,系统中可能存在多个proposer,他们各自发起不同的提议。这里的提议可以是一个修改操作,也可以是提议自己成为主节点。如果 proposer第一次发起的 accept 请求没有被 acceptor 中的多数派批准(例如与其他 proposer 的提议冲突),那么,需要完整地执行一轮Paxos协议。过程如下:(这个过程不靠谱,如果有时间的话会更新,没有解释Paxos协议的实质)

  • 准备(prepare):Proposer 首先选择一个提议序号 n 给其他的 acceptor 节点发送 prepare 消息。Acceptor 收到 prepare 消息后,如果提议的序号大于他已经回复的所有prepare消息,则acceptor将自己上次接受的提议回复给proposer,并承诺不再回复小于n的提议。
  • 批准(accept):Proposer 收到了acceptor中的多数派对prepare的回复后,就进入批准阶段。如果在之前的prepare阶段acceptor回复了上次接受的提议,那么,proposer 选择其中序号最大的提议值发给acceptor批准;否则,proposer生成一个新的提议值发给 acceptor 批准。Acceptor 在不违背他之前在 prepare 阶段的承诺的前提下,接受这个请求。
  • 确认(acknowledge):如果超过一半的 acceptor 接受,提议值生效。Proposer发送 acknowledge 消息通知所有的 acceptor 提议生效。

Paxos协议需要考虑两个问题 :正确性,即只有一个提议值会生效;可终止性,即最后总会有一个提议值生效。Paxos协议中要求每个生效的提议被 acceptor 中的多数派接受,并且每个acceptor不会接受两个不同的提议,因此可以保证正确性。Paxos协议并不能够严格保证可终止性。但是,从 Paxos协议的执行过程可以看出,只要超过一个acceptor接受了提议,proposer很快就会发现,并重新提议其中序号最大的提议值。因此,随着协议不断运行,它会往“某个提议值被多数派接受并生效”这一最终目标 靠拢。

Paxos 与 2PC

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

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

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

  1. 关于NoSQL的详细资料参见NoSQL数据库笔谈 ↩
  2. 该部分未完全弄懂，TODO! ↩
  3. 该部分参考一致性hash算法 ↩

Comments

苹果的味道 © qingyuanxingsi Powered by Pelican and Twitter Bootstrap. Icons by Font Awesome and Font Awesome More