第一章 数据分片和路由
面对大数据，首先应该处理的是数据的存储问题，单台机器无法存储海量的数据，传统数据库系统是通过纵向扩展，即通过改善机器的性能来提升，但是对于目前的大数据存储和处理，一般是采用横向扩展，即增加机器的数量来存储数据。如何把数据存储到不同的机器上，又如何迅速找到某条记录，这两个问题的解决方法就是数据分片和路由。第一章主要讲述了就是这两个问题的解决方案。
上图就是数据分片与路由的抽象模型，数据通过key进行分片的映射，之后再通过分片与机器的映射将数据分片存储到不同的物理机器上。
数据分片一般有哈希分片和范围分片
哈希分片，和我们学习的哈希算法是一样的，通过哈希函数建立key-partition，然后根据key获取记录，这种方式的缺点就是只能支持点查询。范围分片既支持点查询，也支持范围查询。
哈希分片
哈希分片方式主要有三种，分别是Round Robin，虚拟桶及一致性哈希方法。
Round Robin
该方法就是Java中HashMap中方法，num = Hash(key) % K
num是对应的物理机编号，K是机器数量，key是记录的键值。
该方法的优点是实现比较简单，缺点是如果新增加了机器，所有的数据都会重新进行分片，缺乏扩展的灵活性。
虚拟桶
虚拟桶把上面的问题解决掉了，虚拟桶引入后，先预设好集群的最大机器个数(假设是1024台)，这样在集群慢慢扩大时，mod的值不会发生改变，加入一开始只有两台机器，物理机1对应0-500的桶，物理机2对应501-1024的桶，当要引入第三台物理机的时候，如果第三台物理机承担400-600的桶，key-partition无须更改，只需要把原先两台物理机上400-600的桶的数据移动至新的机器上，并修改下虚拟桶上的partition-machine映射关系即可。
一致性哈希
上图是长度为5的的二进制数值的“一致性哈希算法“的大致图，因为长度为5，因此hash值的范围是0-31，上图的集群中有五台物理机，分别用N+编号标志，每台机器管理着hash值在自身编号到上一个节点编号之间的记录，如N14管理着hash值在6-14之间的记录，当要查询记录时，根据hash值依次查询每台机器的管理范围即可获取。
由于每次都要查询所有机器，效率比较低，因此在每台机器上维护一个路由表，路由表存储着m条(m指的是物理机台数)
该图是上面N14节点的路由表
第三项表示距离N14节点距离为4(即20)的hash值落在N20机器上。
一致性哈希算法有两个明显的缺陷，就是节点映射到环中的位置是随机的(位置是由机器IP通过hash得到)，会导致负载均衡问题，此外，集群中机器的性能可能是存在较大差异的，将所有机器平等看待，也会存在负载均衡问题。解决的方法就是引入“虚拟节点”,将每台机器根据性能虚拟成若干节点，再把节点映射到环上即可。
范围分片
顾名思义，就是会对数据的主键进行排序，同时维护着一个数据分片的索引表，索引表的每一项记录着该分片的最小记录的key和对应的物理机，具体的数据存储与管理方式采用的是LSM树。
