1. 概念介绍
数据分片与数据路由
在大数据背景下，数据规模已经由GB级别跨越到PB级别。单机明显无法存储如此规模的数据量，只能依靠大规模集群来对这些数据进行存储和处理，所以系统可扩展性成为衡量系统优劣的重要指标。
传统并行数据库为了支持更多的数据，往往采用纵向拓展的方式，即不增加机器数量，而是通过改善单机硬件资源配置来解决问题。
而目前主流的大数据存储与计算系统通常采用横向拓展的方式支持系统可拓展性，即通过增加机器数目来获得水平拓展能力。
与此对应，对于存储待处理的海量数据，需要通过数据分片（share/patition）来将数据进行切分合并到各个机器中去。数据分片后，如何能够找到某条记录的存储位置就成为必然 要解决的问题，这一般被称为数据路由(routing).
数据分片与数据复制
数据分片与数据复制是紧密联系的两个概念，对于海量数据，通过数据分片实现系统的水平扩展能力，通过数据复制保证数据的高可用性。
由于机器可能存在隐患，为了保证数据不丢失，可将数据备份起来，客户端可从多个备份数据中选择物理距离较近的进行读取，增加了读操作的并发性又可以提高单次读的读取效率。
数据复制虽然带来了很多好处，但是也引入了相应的问题：
每份数据都存在多个副本，在并发对数据进行更新时如何保证数据的一致性就成为关键问题。
今天主要关注的问题是数据分片与路由的相关技术。
分片方式
常见的数据分片方式包括哈希分片与范围分片。
１．抽象模型
数据分片与路由的抽象模型，可以看成一个二级映射关系。
- 第一级key-partition映射是将数据记录映射到数据分片，一个数据分片可以包含多条数据记录；
- 第二级partition-machine映射是将数据分片映射到物理机器中，一个物理机器可以包含多个数据分片。
- 数据分片时，根据key-partition映射关系将数据水平分割成数据分片，再根据partition-machine映射关系将分片存入对应的物理机器中；
- 数据路由时，根据key-partition映射关系查找到对应的数据分片，然后根据partition-machine得出具体存储该数据的物理机器，之后从该物理机器读取值。
- 哈希分片
数据分片的常见手段是采取哈希函数，常见的哈希分片方式分别是：
-
哈希取模法
假设有K台机器，对其编号从0到K-1。对于key关键字的记录，根据H(key)哈希函数求出存储该数据的机器编号，从而实现数据分片。数据路由也使用相同的哈希函数。H(key)=hash(key) mod KRound Robin的优点是实现非常简单。
缺点是缺乏灵活性，因为每台物理机器对应一个数据分片，抽象模型中两个映射关系都采取了同一个哈希函数，造成了集群中机器个数和哈希函数的紧耦合，因此只要机器个数发生变化，哈希函数发生变化，需要重新进行数据分片。 虚拟桶
所有记录通过哈希函数映射到虚拟桶，一个虚拟桶可以包含多条记录，这是第一层映射关系，虚拟桶其实就是数据分片；第二层映射通过查表实现，一个物理机器可容纳多个虚拟桶。
- 一致性哈希
一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法.
一致性哈希是在分布式环境下，每台机器负责存储部分数据，通过哈希方式对数据进行操作的方法。
侧重一致性哈希原理
http://blog.csdn.net/cywosp/article/details/23397179
把数据通过一定的hash算法处理后映射到环上
现在我们将object1、object2、object3、object4四个对象通过特定的Hash函数计算出对应的key值，然后散列到Hash环上。如下图：
Hash(object1) = key1；
Hash(object2) = key2；
Hash(object3) = key3；
Hash(object4) = key4；
侧重一致性哈希在分布式系统中应用的实际情况 。
http://blog.csdn.net/bzhxuexi/article/details/46422027
(1) 环形Hash空间
-
范围分片
所有记录根据主键进行排序，再从排序好的记录中划分数据分片，每个分片存储的是一段记录。一般会保存一个数据分片的映射表，表记录数据分片中记录的最小主键值以及对应的机器地址。
范围分片
内容来源
