分布式系统数据分布方案

数据分布方式

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

几种方案可以组合使用

普通哈希

按照数据的某一特征计算哈希值，并将哈希值与机器中的机器建立映射关系，从而将不同哈希值的数据分布到不同的机器上

优点:
哈希函数的散列特性较好时数据分布均匀。
元信息非常简单

缺点:

可扩展性不高:一旦集群规模需要扩展，则几乎所有的数据需要被迁移并重新分布。
解决方案：
维护额外的元数据：哈希值不与机器做除法取模映射，将对应关系作为元数据由专门的元数据服务器管理。
访问数据时：
1.1 计算哈希值
1.2. 哈希值取模个数大于机器个数，使同一台机器上负责多个哈希取模的余数
1.3. 查询元数据服务器，获得哈希值对应的机器。
1.4. 扩容时，将部分余数分配到新加入的机器并迁移对应的数据到新机器上
分布不均:一旦某数据特征值的数据严重不均，容易出现“数据倾斜”(data skew)问题
解决方案：使用多个特征值计算哈希值，工程实践不容易落地

工程实践
1.Mola(developer.baidu.com/platform/s6…)
2.Armor(分布式Key-Value系统)
3.Big Pipe(百度的消息传输系统)分布不均：一旦某数据特征值的数据严重不均，容易出现“数据倾斜”(data skew)问题

按范围

将数据按特征值的值域范围划分为不同的区间，使得集群中每台(组)服务器处理不同区间的数据。如id、时间、区域
使用元数据服务器管理数据分布信息

优点:可以灵活的根据数据量的具体情况拆分原有数据区间，拆分后的数据区间可以迁移到其他机器。
缺点:当集群规模较大时，元信息的数据量也变得很大
解决方案：
1.利用动态划分区间的技术，使得每个区间中服务的数据量尽量的一样多。
2.当某个区间的数据量较大时，通过将区间“分裂”的方式拆分为两个区间，使得每个数据区间中的数据量都尽量维持在一个较为固定的阈值之下。

工程实践
1.Big Table(cloud.google.com/bigtable/)
2.Hbase(hbase.apache.org/)
3.PNUTS(timyang.net/architectur…)

按数据量

将数据视为一个顺序增长的文件，并将数据按照某一较为固定的大小划分为若干数据块(chunk)，不同的数据块分布到不同的服务器上
使用元数据服务器管理数据分布信息

优点:数据分布均匀
缺点:数据分布均匀集群规模较大时，元信息的数据量很大;维护元数据逻辑复杂

实践中比较好的数据分布方案
按哈希值分段
1.按照用户ID的哈希值分数据，如果某个用户ID的数据量特别大时，统计用户的数据量，并按某一阈值将用户的数据切分为多个均匀的数据段
2.将数据段分布到集群中去。大部分用户的数据量不会超过阈值
3.元数据中仅仅保存超过阈值的用户的数据段分布信息。

工程实践:
1.GFS(pdos.csail.mit.edu/6.824/paper…)
2.HDFS(hadoop.apache.org/docs/r1.0.4…)

一致性哈希

使用一个哈希函数计算数据或数据特征的哈希值，令哈希函数的输出值域为一个封闭的环，将节点随机分布在这个环上，每个节点负责处理从自己开始顺时针到下一个节点的全部哈希值域上的数据。
元数据维护虚拟节点与真实节点的映射

优点:可以任意动态添加、删除节点，每次仅影响一致性哈希环上相邻的节点。
缺点:很难均匀分布
解决方案：
1.引入虚节点(virtual node)，虚节点的个数远大于未来集群中机器的个数，将虚节点均匀分布到一致性哈希环上。
2.操作数据时，首先找到对应的虚节点，进而查找元数据找到对应的真实节点。

工程实践
1.Dynamo(aws.amazon.com/cn/dynamodb…)
2.Cassandra(cassandra.apache.org/)

基本副本协议

中心化副本控制协议

由一个中心节点协调副本数据的更新、维护副本之间的一致性

优点:
1.协议相对较为简单，所有的副本相关的控制交由中心节点完成。
2.并发控制将由中心节点完成，从而使得一个分布式并发控制问题，简化为一个单机并发控制问题

缺点:系统的可用性依赖于中心化节点

primary-secondary协议

1.副本分为两大类，其中有且仅有一个副本作为 primary 副本，除 primary 以外的副本都作为 secondary 副本。
2.维护 primary 副本的节点作为中心节点，中心节点负责维护数据的更新、并发控制、协调副本的一致性。

优点:兼顾了复杂、一致性与可用性
缺点:牺牲一定的可用性
工程实践:
1.GFS
2.PNUTS
3.Niobe

去中心化副本控制协议

没有中心节点，协议中所有的节点都是完全对等的，节点之间通过平等协商达到一致

优点:没有因为中心化节点异常而带来的停服务等问题
缺点:
1.协议过程通常比较复杂。尤其当需要实现强一致性时，协议流程变得复杂且不容易理解。
2.由于流程的复杂，去中心化协议的效率或者性能一般也较中心化协议低。
3.一个不恰当的比方就是，中心化副本控制协议类似专制制度，系统效率高但高度依赖于中心节点，一旦中心节点异常，系统受到的影响较大;去中心化副本控制协议类似民主制度，节点集体协商，效率低下，但个别节点的异常不会对系统总体造成太大影响。

工程实践
基于paxos协议:
1.Dynamo/Cassandra
2.Chubby/Zookeeper

primary-secondary协议

解决四大类问题:数据更新流程、数据读取方式、Primary 副本的确定和切换、数据同步(reconcile)

数据更新流程

数据更新都由 primary 节点协调完成。
外部节点将更新操作发给 primary 节点
primary 节点进行并发控制即确定并发更新操作的先后顺序
primary 节点将更新操作发送给 secondary 节点
primary 根据 secondary 节点的完成情况决定更新是否成功并将结果返回外部节点

数据读取方式

保障强一致性的几种方法：

始终读取primary副本
由 primary 控制节点 secondary 节点的可用性。当 primary 更新某个 secondary 副本不成功时，primary 将该 secondary 副本标记为不可用，从而用户不再读取该不可用的副本。不可用的 secondary 副本可以继续尝试与 primary 同步数据，当与 primary 完成数据同步后，primary 可以副本标记为可用。
Quorum方式读取
即 primary 成功更新 W 个副本(含 primary 本身)后向用户返回成功。读取数据时依照一致性要求的不同可以有不同的做法:

如果需要强一致性的立刻读取到最新的成功提交的数据，则可以简单的只读取 primary 副本上的数据即可，也可以通过强一致的方式读取;
如果需要会话一致性，则可以根据之前已经读到的数据版本号在各个副本上进行选择性读取;
如果只需要弱一致性，则可以选择任意副本读取。

Primary 副本的确定和切换

primary副本的确定：属于元信息，由专门的元数据服务器维护
primary的切换：
1.如何确定primary副本异常：lease机制
2.切换primary副本时如何保障数据一致性：quorum机制

数据同步

数据不一致原因	解决方案
网络分化异常，secondary落后primary	使用日志技术，回放primary上的操作日志(通常是redo日志)，追上进度
某些协议下，secondary的数据是脏数据。（如primary没有更新，secondary更新了）	1. 设计协议不产生脏数据 2. 丢弃脏数据 3. 使用undo日志删除脏数据
secondary为新增副本，完全没有数据	1. 直接拷贝 primary 副本的数据，回放日志追更新进度的方法快很多 2. 但拷贝数据时 primary 副本需要能够继续提供更新服务，要求 primary 副本支持快照(snapshot)功能。即对某一刻的副本数据形成快照，然后拷贝快照，拷贝完成后使用回放日志的方式追快照形成后的更新操作