大数据，从打好分布式系统的基础开始

分布式系统是大数据的基础，大数据是分布式系统的最佳实践。本文将介绍分布式系统对数据的基本处理方法，包括数据的分布方式和对数据副本进行控制的协议和算法。这些算法也是大数据各类组件技术的基础。

分布式系统定义

分布式系统是若干独立计算机的集合，但这些计算机系统集合从用户的使用角度来说，则是一个单一的应用系统。组建一个分布式系统具备五个关键目标：

1. 资源的可访问性：用户能够方便的访问远程资源，并且可以以一种受控的方式与其他用户共享资源；
2. 透明性：资源在网络上的分布对用户不可见，用户的使用体验就是在一个入口做操作；
3. 开放性：系统通过一整套标准化的接口来提供服务，任何第三方系统都可以通过该标准接口接入该系统，并使用其提供的服务；
4. 可扩展性：系统在规模上可以扩展，可以方便的增加资源来为更多的用户提供服务。
5. 容错性：系统可以从部分失效中自动恢复，而且不会严重的影响整体性能。特别是，当故障发生时，分布式系统应该在进行故障恢复的同时依然可以提供基本的操作能力。也就是说，它应该能容忍错误，在发生错误时某种程度上可以继续操作。

整个系统由分布在不同位置或者服务器上的节点和进程组成，这二者是分布式系统的基本元素，而节点/进程间的通信是分布式系统的核心。节点/进程间通过命名服务和同步来相互协作。

一致性和复制是分布式系统要解决的二个重要问题，对数据进行复制是为了增强系统的可靠性或提高性能。而实现数据复制的主要难题是保证各个副本的一致性。

分布式系统体系结构

把分布式系统的逻辑组织结构看作软件组件来分析其体系结构，则通常分布式系统可以划分为：

基于分层的体系架构：组件组成不同的层，各层的请求自顶向下依次调用，而请求结果则从下往上。如下图“基于分层的体系架构”所示，TCP/IP协议的模型是这种体系架构的经典。

基于分层的体系架构

基于对象的体系架构：这是一种很松散的组织结构，每个对象是一个组件，组件间通过远程过程调用机制来交互。如下图“基于对象的体系架构”所示，大型软件多采用本架构。

基于对象的体系架构

基于数据的体系架构：组件间的通信通过一个公用的数据仓库。如下图“基于数据的体系架构”所示，基于WEB的分布式系统大多数是以数据为中心的。

基于数据的体系架构

基于事件的体系架构：组件间的通信是通过事件来传播的，进程间是松耦合的。如下图“基于事件的体系架构”所示，通常的发布/订阅系统都属于这类。

基于事件的体系架构

分布式系统演进

最出名的分布式计算模型就是Internet，它是所有分布式技术的基础，从电子商务到云计算到面向服务到虚拟化到大数据。所有的分布式计算模型都有一个相同的特性：他们是一群协同工作的网络计算机。

总体上说，整体分布式系统的演进是从封闭到开放的过程，是一个不断标准化的过程。

早期是美国国防部先进研究项目局（DARPA）的内部网络和一些私企的远程过程调用（RPC）系统，慢慢的TCP/IP协议的发展和被广泛应用。最终夯实了分布式系统的基础。

每个厂商和标准组织都在发展自己的远程过程调用（RPC）系统，这使得任何一家公司都无法创建一个通用的分布式计算标准。1990年代中期，Internet协议替代了这些早期的尝试，并成为今天分布式计算的基础。整个演进过程如下图所示。

分布式计算演进过程

典型的分布式系统案例如下：

电信通讯网络：

• 电话网络和蜂窝网络
• 计算机网络，诸如Internet
• 无线传感器网络

网络应用：

• 广域网和点对点网络
• 在线游戏和虚拟现实社区
• 分布式数据库
• 网络文件系统

实时控制系统：

• 飞机控制系统
• 工业控制系统

并行计算：

• 科学计算，包括集群计算和网格计算
• 计算机图形的分布式渲染

分布式系统关键协议和算法

在分布式系统中计算节点和存储节点可以在同一台物理机器上，也可以位于不同的物理机器。如果计算节点和存储节点位于不同的物理机器则计算的数据需要通过网络传输，此种方式的开销很大，甚至网络带宽会成为系统的总体瓶颈。另一种思路是，将计算尽量调度到与存储节点在同一台物理机器上的计算节点上进行，这称之为本地化计算。本地化计算是计算调度的一种重要优化，其体现了一种重要的分布式调度思想：“移动数据不如移动计算”，通俗说就是计算跟着数据走。

当数据分布到多个节点后，为了保证数据的安全和可靠性，必须对每份数据都有备份，也就是数据的副本。对分布式系统来说，副本数据的复制（维持多副本）和保证副本的一致性是其重点要解决的两个问题。进行数据复制主要是为了提升系统的可靠性和性能。如果一个文件系统已实现数据复制，则当一个副本被破坏后，文件系统只需要转换到另一个数据副本就可继续运转，从而使得系统更加可靠。同样，当分布式系统需要在服务器数量和地理区域上进行扩展时，复制对于提高性能也是非常重要的，通过对服务器进行复制，让他们分担工作负荷，就可以提高性能。虽然复制能提升系统可靠性和性能，但是复制是有代价的。首先，维持多副本需要更多的存储空间，所有副本的更新需要更多的网络带宽，另外，多个副本可能导致一致性方面的问题，一旦某个副本被修改了，那么它将不同于其他所有的副本。因此，必须对所有副本进行同样的修改以确保一致性。

综上，一个分布式系统的关键协议和算法主要有两类：

1. 如何拆解分布式系统的输入数据，即数据的分布方式；
2. 数据的副本是如何创建的，并且如何保证其一致性。

数据分布方式

对系统的输入数据进行分解并分布到不同的节点的方式就是数据的分布方式，通常用下面的方法：

a） 哈希方式

哈希方式是最常见的数据分布方式，其方法是按照数据的某一特征计算哈希值，并将哈希值与机器中的机器建立映射关系，从而将不同哈希值的数据分布到不同的机器上。所谓数据特征可以是key-value 系统中的 key，也可以是其他与应用业务逻辑相关的值。下图“哈希算法数据分布示意图”给出了哈希方式分数据的一个例子，将数据按哈希值分配到3个节点上。

哈希算法数据分布示意图

b） 按数据范围分布

按数据范围分布是另一个常见的数据分布式，将数据按特征值的值域范围划分为不同的区间，使得集群中每台（组）服务器处理不同区间的数据。下图“按数据范围分布的示意图”展示了这种数据发布方式。

按数据范围分布的示意图

c） 按数据量分布

按数据量分布数据与具体的数据特征无关，而是将数据视为一个顺序增长的文件，并将这个文件按照某一较为固定的大小划分为若干数据块（chunk），不同的数据块分布到不同的服务器上。下图“按数据量分布的示意图”就是一个简单的样例。

按数据量分布的示意图

d） 一致性哈希

使用一个哈希函数计算数据或数据特征的哈希值，令该哈希函数的输出值域为一个封闭的环，即哈希函数输出的最大值是最小值的前序。将节点随机分布到这个环上，每个节点负责处理从自己开始顺时针至下一个节点的全部哈希值域上的数据。下图“一致性哈希分布示意图”是一个简单的示例。

一致性哈希分布示意图

数据副本控制协议

副本控制协议指按一定的协议流程控制副本数据的读写行为，使得副本满足一定的可用性和一致性要求的分布式协议。副本控制协议要具有一定的容错能力，从而保证系统具有一定的可用性。在分布式系统中通常有两种方法：

a） 中心化副本控制协议

中心化副本控制协议的基本思路是由一个中心节点协调副本数据的更新、维护副本之间的一致性。中心化副本控制协议的优点是协议相对较为简单，所有的副本相关的控制由中心节点完成，并发控制由中心节点完成，从而使得一个分布式并发控制问题，简化为一个单机并发控制问题。中心化副本控制协议通用架构如下图“中心化副本控制协议示意图”：这类协议优点是设计简单，但是存在中心节点使得有一定的中心节点异常造成的不可用问题。

中心化副本控制协议示意图

最常用的中心化副本控制协议就是primary-secondary协议。类似通常的Master-Slave协议，Primary是主节点，Secondary是若干副节点。这种协议中，副本被分为两种：Primary的副本，通常只有一个；除Primary 以外的副本都作为Secondary 副本。维护Primary副本的节点作为中心节点，中心节点负责维护数据的更新、并发控制、协调副本的一致性等控制管理工作。

b） 去中心化副本控制协议

去中心化副本控制协议没有中心节点，协议中所有的节点都是完全对等的，节点之间通过平等协商达到一致。从而去中心化协议没有因为中心化节点异常而带来的停服务等问题。去中心化协议的最大的缺点是协议过程通常比较复杂。不再就去中心化副本控制协议做进一步详细分析。去中心化副本控制协议通用架构如下图“去中心化副本控制协议示意图”：这类协议的优点是个别节点异常不影响整个系统，缺点是协议流程复杂，实现和处理效率均降低。

去中心化副本控制协议示意图

Paxos是唯一在工程中得到应用的强一致性去中心化副本控制协议。Paxos协议算法是Lamport于1990年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视。06年Google的三篇论文中的chubby锁服务使用paxos作为chubby cell中的一致性算法，Paxos的人气从此一路狂飙。Paxos 协议是少数在工程实践中证实的强一致性、高可用的去中心化分布式协议。

Paxos 协议算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致，是分布式计算中的重要问题。

基于Paxos 协议中，有一组完全对等的参与节点（称为 accpetor），这组节点各自就某一事件做出决议，如果某个决议获得了超过半数节点的同意则生效。Paxos 协议中只要有超过一半的节点正常，就可以工作，能很好对抗宕机、网络分化等异常情况。

分布式系统和大数据

大数据作为分布式系统的最佳实践，其核心是利用多台计算机组成的分布式系统来协同解决单台计算机所不能解决的大数据的计算、存储等问题。大数据和传统数据分析的最大的区别就在于问题的规模，即计算、存储的数据量的区别。大数据将传统的单机数据分析问题使用分布式来解决，首先要解决的就是如何将问题拆解为可以使用多机分布式解决，使得分布式系统中的每台机器负责原问题的一个子集。由于无论是计算还是存储，其问题输入对象都是数据，所以如何拆解大数据依然是大数据系统的基本问题。

大数据系统采用的数据处理方式如下图所示：

大数据系统的数据处理方式

对于开源大数据系统Hadoop的各个组件来说，其普遍采用中心化副本控制协议来简化系统的设计和实现，但是为了保证系统的可靠性，又在其分布式协调系统ZooKeeper中采用类似Paxos的去中心化协议选出Primary节点。在完成Primary节点的选举后，系统就转为中心化的副本控制协议，即由Primary节点负责同步更新操作到Secondary。这样就保证了Primary节点的可靠性。

综合起来，我们可以看到，无论是分布式系统还是大数据系统，其本质都是如何对数据做合理和高效的处理。本文介绍了作为大数据基础的分布式系统对数据的基本处理方法，包括数据的分布方式和对数据副本进行控制的协议和算法。这些算法也是大数据各类组件技术的基础。