可伸缩性架构常用技术－－数据切分

1. 简介

本来想写一篇可伸缩性架构方面的文章，发现东西太多了，久久未能下笔，这里首先把大家最关注的数据切分（Partition/Sharding）方面的内容先写完，给大家参考。

我们知道，为了应对不断增长的数据，我们对数据进行切分，存储在不同的数据库里，本文提到的数据库在非特定指明的情况下，均指一个逻辑数据库（是一组数据库，比如Master-Slave），而非单一各个物理数据库。

其主要有两种方式：

    垂直切分（Vertical Partition/Sharding）:就是把不同格式的数据，存储到不同的数据库。

    水平切分（Horizontal Partition/Sharding）:就是把相同的数据格式的数据，存储到不同的数据库，本文将侧重这点进行讲述。

2. 垂直切分（Vertical Partition/Sharding）

对于垂直切分，其实应用非常广泛，主旨是把那些关系依赖非常紧密的数据保存到同一数据库，主要包含如下几种应用方式：

    不同的应用使用不同数据库:这个非常容易理解，即对于一个企业来讲，往往有多个应用，甚至有些应用逐渐演变成两个或者多个应用，这其实就是一种垂直切分应用。

    应用的不同模块使用不同的数据库:为同一应用的不同模块分别使用不同的数据库，之间提供低耦合的API进行访问。
    同一应用相同模块使用不同数据库:在一些应用中，对于适合关系查询的数据，保存在关系数据库，而另外一些适合以NoSQL数据库保存的数据（例如key-value数据库），保存在NoSQL数据库中，方便数据扩展。这里给出一个例子，比如一个论坛应用，可以对个人用户信息保存在关系数据库，例如，其访问次数，个人信息等等，而对于发表的帖子和回帖，则可以保存在一个NoSQL里，方便扩展。注意，这里给出的例子并非真实例子，只是为了易于说明给出一个假设性的例子。

3. 水平切分（Horizontal Partition/Sharding）

水平切分相对比较复杂，我们还是从水平切分的策略谈起。
3.1 水平切分策略主要分为以下几种：

1. Round-Robin（轮询式）算法

顾名思义，就是把数据按照轮流的方式依次存放在的数据库节点上，比如，有2个节点，N0和N1，那么Data0放在N0节点上，Data1放在N1上，Data2放在N0上，依次类推……。

这种方式实现起来非常容易，对于数字键，我们有：n = key mod N。其中，key为数据的键，N为节点的数量，n为存放数据的节点编号；对于那些非数字键，我们可以让其转变为数字键，比如通过某些hash函数，让键值均匀分布，于是有：n = f (key) mod N。

这种方式有个缺点非常明显，不容易应对数据节点的变化，即不易进行二次切分。所谓二次分片是指，当数据的增长超过数据库容量时，需要增加数据库，或者系统故障导致某些数据库不能使用时，这时需要重新切分数据库。例如，有两个节点，N0和N1，现在需要增加一个节点N2，这时候，都需要吧N0上的数据和N1上的数据迁移到N2上，这个工作量是巨大的；并且可能导致上层应用对数据的改变，比如，之前数据Data5存储在N1上面，上层应用访问该数据时，根据key=5知道其存储在数据库N1里，那么便会在N1里查询数据，现在增加另外一个节点N2，那么这条数据被迁移到N2上了，上层应用就应该去N2上查询此数据了，这个看似简单，其实往往导致应用程序的复杂性很高。

2. 虚拟分片技术

为了保证二次分片时，避免对上层应用因为实际物理数据库发生改变而引起对数据访问逻辑的改变，中间加入了一个虚拟片段—物理片段映射表，数据对象存储在虚拟分片上，每个虚拟片段通过这个映射表找到相应的物理片段。这时间，上层应用依赖于虚拟分片，而非物理分片，只要保证虚拟片段足够多，就能避免上层应用的依赖。

3. 一致性Hash算法

为了避免数据库数量发生变化，引起大规模的数据迁移问题，而引入了一致性Hash算法。此算法由David Karger等人发表于1997年，论文题目为《Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web》，这里有一篇文章讲述Java语言简单实现一致性Hash算法http://weblogs.java.net/blog/2007/11/27/consistent-hashing。

一致性Hash算法的主要思想是不改变Hash函数本身，当减少节点时，临近的节点接手该节点，因此，消失节点上的数据迁移只迁移到临近节点上面；而增加节点时，只接手其临近的一个节点的部分数据，因此，只有一部分临近节点的数据被迁移至新加节点。

我们来详细了解一下具体实现：我们的Hash函数生成的数据都有一个值区间[min，max]，我们把该区间用一个环来表示，每个节点的hash值都映射到这个环上，如下图所示：



假设我们的值区间是[1,12]，我们有三个节点，1，4，9，数据的键也映射到这个环上，a的键值介于1~4之间，则存储在节点4上，即按照顺时针方向存储数据，同样b存储于节点9，而c存储于节点1。

假设节点4不可用时，那么数据a就会被迁移至节点9，其他节点的数据不发生迁移，如下图所示：



假设增加节点7，那么将把节点9上的部分数据迁移至节点7，其他节点数据不发生改变，如下图所示：



4. 按照数据的特点进行切分数据

最常见的就是按照地理位置切分数据，那么我们按照用户的注册信息或者用户数据提交的ip地址等来把它们放置于离它们地理位置最近的数据库中。
3.2 实际应用

在真实的应用中，往往会结合这些策略，甚至提供更为抽象的接口让开发人员实现适合自己的切分方法。我们这里讲述Mongodb和Hibernate Shards的分片方式。
3.2.1 Mongodb Sharding

Mongo db是基于文档的NoSQL数据库，查询方式和关系数据库非常接近。

Mongodb把数据存放在称为Chuncks数据结构上面，Chunck的默认大小是64M，每个Chunck上面存储一定切分范围的数据，当数据超过64M时，会自行分裂成两个Chunks，相当于一致性Hash算法添加了一个节点，只是这个节点不是DB。而每台物理db（称为Shard）上含有多个Chunks，为了达到更好的负载均衡，这些物理db上的Chunks会自动迁移，使得db上的Chunks发布均衡。
3.2.2 Hibernate Shards

Hibernate Shards是在Hibernate Core上做的一层扩展，目的是在关系数据库上封装和降低水平切分的复杂性。

Hibernate Shards为开发者提供了抽象接口，开发人员可以实现自己想要的切分策略，为了避免物理数据库发生改变引起应用程序的改变，其采用虚拟分片技术。

Hibernate Shards参考中文文档请参见：http://redhat.iteye.com/blog/328032
3.3 应注意的问题

水平切分数据库之后，会给查询造成一定的困难，特别是Aggregation查询。Mongodb采用Map/Reduce方式，能够比较高效进行Aggregation查询。
4. 总结

对于大规模，可伸缩，海量数据的应用，数据切分是其架构必须考虑的一个重点内容，我们在进行数据切分时，往往采用先垂直，再水平方式对数据分片。