数据分片的基本算法介绍，以及数据分片在Redis中是如何运用的。

前言

本文结合了带着问题学习分布式系统之数据分片和翻译了 Partitioning: how to split data among multiple Redis instances.，通过对Redis数据分片的学习，举一反三其他的分布式数据分片的实现。

分片的作用

可能很多人搞不清楚数据分片和数据冗余的区别，下图便很形象的说明了什么是数据分片，什么是数据冗余。

其中，数据集A、B属于数据分片，原始数据被拆分成两个正交子集分布在两个节点上。而数据集C属于数据冗余，同一份完整的数据在两个节点都有存储。当然，在实际的分布式系统中，数据分片和数据冗余一般都是共存的。

何为数据分片（segment，fragment， shard， partition），就是按照一定的规则，将数据集划分成相互独立、正交的数据子集，然后将数据子集分布到不同的节点上。注意，这里提到，数据分片需要按照一定的规则，不同的分布式应用有不同的规则，但都遵循同样的原则：按照最主要、最频繁使用的访问方式来分片。

分片在分布式系统中，主要为了解决两大问题：

1、用多台服务器的内存和磁盘来存储更多的数据。没有分片你的数据需求将受到单机资源的限制。

2、它允许将计算能力扩展到多核和多台计算机，并将网络带宽扩展到多台计算机和网络适配器。

分片基础算法

对于数据分片的任何算法或思想，都需要思考如下几个问题：

• 具体如何划分原始数据集
• 当原问题的规模变大的时候，能否通过增加节点来动态适应？
• 当某个节点故障的时候，能否将该节点上的任务均衡的分摊到其他节点？
• 对于可修改的数据（比如数据库数据），如果其节点数据变大，能否以及如何将部分数据迁移到其他负载较小的节点，及达到动态均衡的效果？
• 元数据的管理（即数据与节点对应关系）规模？元数据更新的频率及复杂度？元数据的一致性保证？

　为了后面分析不同的数据分片方式，假设有三个物理节点，编号为N0， N1， N2；有以下几条记录：

　　R0: {id: 95, name: ‘aa’, tag:’older’}
　　R1: {id: 302, name: ‘bb’,}
　　R2: {id: 759, name: ‘aa’,}
　　R3: {id: 607, name: ‘dd’, age: 18}
　　R4: {id: 904, name: ‘ff’,}
　　R5: {id: 246, name: ‘gg’,}
　　R6: {id: 148, name: ‘ff’,}
　　R7: {id: 533, name: ‘kk’,}

##Range Partitioning

可以指定N0节点负责id在区间[0,333]，N1节点负责id在区间[334,666]，N3节点负责id在区间[667, 1000]。如下示意图所示，数据分布到三个数据节点上。

这种方式的优点是非常的简单，首先选择一个特征键，然后对特征键划分区间，数据只放到满足区间的节点上。但是这种方式的缺点也很多：

• 如果数据的特征键在某一个区间内特别密集，在其他的区间内又特别的稀疏，会导致数据倾斜，使得数据多的节点成为瓶颈，其他数据少的节点又不能发挥其作用。
• 扩容缩容平衡数据（rebalance）成本高，有可能需要移动全部分片的数据。

##Hash Partitioning

Hash分区跟Range Partitioning其实比较相似，只不过把区间，换成了哈希函数取余，hash(key)%mod，mod是节点的数量，取余的值就代表数据要放入到哪个节点中。

Hash分区的优点也是比较简单，缺点同Range Partitioning一致，只不过如果成倍增加节点数量的话，这样概率上来讲至多有50%的数据迁移。

Consistent Hashing

一致性hash是将数据按照特征值映射到一个首尾相接的hash环上，同时也将节点（按照IP地址或者机器名hash）映射到这个环上。对于数据，从数据在环上的位置开始，顺时针找到的第一个节点即为数据的存储节点。这里仍然以上述的数据为例，假设id的范围为［0， 1000］，N0， N1， N2在环上的位置分别是100， 400， 800，那么hash环示意图与数据的分布如下：

可以看到相比于上述的hash方式，一致性hash方式需要维护的元数据额外包含了节点在环上的位置，但这个数据量也是非常小的。

一致性hash在增加或者删除节点的时候，受到影响的数据是比较有限的，比如这里增加一个节点N3，其在环上的位置为600，因此，原来N2负责的范围段（400， 800］现在由N3（400， 600] N2(600, 800]负责，因此只需要将记录R7(id:533) 从N2,迁移到N3:

不难发现一致性hash方式在增删的时候只会影响到hash环上相邻的节点，不会发生大规模的数据迁移。

但是，一致性hash方式在增加节点的时候，只能分摊一个已存在节点的压力；同样，在其中一个节点挂掉的时候，该节点的压力也会被全部转移到下一个节点。我们希望的是“一方有难，八方支援”，因此需要在增删节点的时候，已存在的所有节点都能参与响应，达到新的均衡状态。

因此，在实际工程中，一般会引入虚拟节点（virtual node）的概念。即不是将物理节点映射在hash换上，而是将虚拟节点映射到hash环上。虚拟节点的数目远大于物理节点，因此一个物理节点需要负责多个虚拟节点的真实存储。操作数据的时候，先通过hash环找到对应的虚拟节点，再通过虚拟节点与物理节点的映射关系找到对应的物理节点。

引入虚拟节点后的一致性hash需要维护的元数据也会增加：第一，虚拟节点在hash环上的问题，且虚拟节点的数目又比较多；第二，虚拟节点与物理节点的映射关系。但带来的好处是明显的，当一个物理节点失效时，hash环上多个虚拟节点失效，对应的压力也就会发散到多个其余的虚拟节点，事实上也就是多个其余的物理节点。在增加物理节点的时候同样如此。

工程中，Dynamo、Cassandra都使用了一致性hash算法，且在比较高的版本中都使用了虚拟节点的概念。在这些系统中，需要考虑综合考虑数据分布方式和数据副本，当引入数据副本之后，一致性hash方式也需要做相应的调整， 可以参加cassandra的相关文档。

Hash Slot

虚拟槽就是在物理机的基础上，有虚拟出了远远大于物理机数量的虚拟槽位，数据是保存在虚拟槽位中的。如下图所示。

虚拟槽的好处是当增加节点或者删除节点的时候，数据的压力能分布在多个虚拟槽中，而多个虚拟槽又分布到多个物理机中，这样会把压力均匀的分散到其他物理节点上。

Range base

简单来说，就是按照关键值划分成不同的区间，每个物理节点负责一个或者多个区间。其实这种方式跟一致性hash有点像，可以理解为物理节点在hash环上的位置是动态变化的。

还是以上面的数据举例，三个节点的数据区间分别是N0(0, 200]， N1(200, 500]， N2(500, 1000]。那么数据分布如下：

注意，区间的大小不是固定的，每个数据区间的数据量与区间的大小也是没有关系的。比如说，一部分数据非常集中，那么区间大小应该是比较小的，即以数据量的大小为片段标准。在实际工程中，一个节点往往负责多个区间，每个区间成为一个块（chunk、block），每个块有一个阈值，当达到这个阈值之后就会分裂成两个块。这样做的目的在于当有节点加入的时候，可以快速达到均衡的目的。

不知道读者有没有发现，如果一个节点负责的数据只有一个区间，range based与没有虚拟节点概念的一致性hash很类似；如果一个节点负责多个区间，range based与有虚拟节点概念的一致性hash很类似。

range based的元数据管理相对复杂一些，需要记录每个节点的数据区间范围，特别单个节点对于多个区间的情况。而且，在数据可修改的情况下，如果块进行分裂，那么元数据中的区间信息也需要同步修改。

range based这种数据分片方式应用非常广泛，比如MongoDB, PostgreSQL， HDFS。

##总结

对以上提到的分片方式进行简单总结，主要是针对提出的几个问题：

上面的数据动态均衡，值得是上述问题的第4点，即如果某节点数据量变大，能否以及如何将部分数据迁移到其他负载较小的节点

不同的分片实现

客户端分区(Client side partitioning)

客户端直接选择出正确的节点（node）读或者写。Redis Cluster是客户端分区的一种实现。

代理分区(Proxy assisted partitioning)

客户端发送请求到Proxy服务，由代理服务端负责选择正确的节点并实现数据存储Server端的通信协议，代理把请求发送到数据存储Server端并返回数据给客户端（Client）。twemproxy实现了代理分区这种方式。

##Query routing分区

客户端发送请求到随机的节点B（node）上，接受到请求的实例负责确定正确的存储节点A，并把请求转发到A节点上，A节点处理完毕之后，返回结果到B，B返回结果到客户端。

分片的不利条件

1、事务处理异常的困难

2、多个Key（multiple keys）同时操作讲很难支持。例如Redis Pipline功能，在Cluster模式默认是不支持的，当然如果能够知道每个key属于的具体节点，是可以实现多pipline同时更新的。

3、分区的粒度是基于key的选定，如果这个key下是大数据结构，比如Set，List，Hash表，那么就很难利用分区的优势，数据将产生倾斜。

4、数据处理更加复杂（is more complex）。数据分布到多个节点上，数据的维护工作将变得困难，并且数据恢复（recover）和备份（backup）的算法变得更加复杂，且空间复杂度和时间复杂度都会提升。比如，在Redis集群中，将持有更多的RDB/AOF文件，当备份数据时，需要聚合多个实例的文件。

5、扩容和缩容变得很复杂（can be complex）。例如Redis Cluster支持大多数的增加或减少节点的数据平衡（rebalancing）问题，并对用户透明，但是客户端分区或者代理分区不支持动态透明的数据平衡，可以用Pre-sharding来讨巧的实现数据平衡。

数据存储还是缓存

尽管无论将Redis用作数据存储还是用作缓存，Redis中的分区在概念上都是相同的，但将其用作数据存储时存在很大的限制。 当Redis用作数据存储时，给定的Key必须始终映射到相同的Redis实例。 当Redis用作缓存时，如果给定的节点不可用，则使用不同的节点并不是什么大问题，因为我们希望提高系统的可用性（缓存穿透时系统来响应请求即可）。

如果给定的key首选节点不可用，则一致性哈希实现通常可以切换到其他节点。同样，如果添加新节点，则部分key将开始存储在新节点上。

这里主要的概念如下:

• 如果Redis用作缓存扩容(scaling up)和缩容(scaling down)使用一致性hash是容易实现的
• 如果将Redis用作存储，则使用固定的“key-node”映射(a fixed keys-to-nodes map )，因此节点数必须固定并且不能变化。 否则，需要一个能够在添加或删除节点时在节点之间重新平衡key的系统，并且目前只有Redis Cluster能够做到这一点-Redis Cluster于2015年4月1日全面可用并投入生产。

Redis分片实现方案总结

##Redis集群（Redis Cluster）

Redis集群是最推荐的方式来实现数据分片和高可用。它已经在2015年就具备生产环境的要求。可以阅读官方文档来了解更多信息。一旦Redis Cluster可用，并且如果兼容Redis Cluster的客户端可用于您的语言，则Redis Cluster将成为Redis分区的事实上的标准。

Redis Cluster分片的实现介于query routing 和 client side partitioning.Redis Cluster客户端是直连集群中的节点的（没有通过任何的其他代理，这点比Twemproxy要优），Redis Cluster在客户端的帮助下实现了混合形式的查询路由（请求不会从Redis实例直接转发到另一个实例，而是会将客户端重定向到正确的节点）。这种实现方式，使得Redis Cluster的情况下的性能不亚于单实例Redis。

Twemproxy

Twemproxy是Twitter开源的一款Redis主从代理中间件。在Redis Cluster出现之前，很多人和组织使用这款中间件。它跟Redis Cluster相比，不能满足在线的扩缩容(scaling up & down)，并且每次请求都要经过一层代理，对性能也是有一定损耗的。

客户端一致性Hash

作为Twemproxy的替代方案，可以在客户端实现一致性hash路由算法，实现客户端路由，还可以使用其他的类似于一致性hash的其他算法。已经有很多Redis clients支持一致性hash的客户端路由，比如 Redis-rb 和 Predis.请参考所有的客户端路由来找到适合你的编程语言的选项。

引用

带着问题学习分布式系统之数据分片

Partitioning: how to split data among multiple Redis instances.

Redis Cluster集群知识学习总结