第一幕数据分片与路由

---恢复内容开始---

一、数据分片相关：

数据分片：系统水平扩展。数据分片存的各个机器上

数据复制：保证数据的高可用性，保证读操作的效率，客服端从多个备份数据中选择物理距离较近的读取，提高单次读取效率

数据路由：分片后找到某条记录的存储位置

缺点：数据一致性

二、数据分片和路由的抽象模型

二级映射：

1、key - partation:数据分到数据分片，1对多：一个分片包涵多条数据

2、partation--machine:数据分片到物理机中，1对多：一个物理机包涵多个分片

路由:获得某条记录的值，先通过k-p找到数据分片，再通过p-m找到对应的machine，通过key找到对应的value

数据分片类型：

哈希分片：k-p,支持点查询,大多的KV存储系统支持这种
范围分片：点查询和范围查询

三、哈希分片（Hash Partition）方法

1、Round Robin:

　　H(key) = hash(key)mod(K),表示：物理机k个，以key为主键的某条记录所在的机器。

优点：简单

缺点：缺乏灵活性，新增物理机时，之前的物理机之间的映射关系被打乱。需要重新分配

原因：将k-p,p-m两个映射合为一体，由同一个哈希函数决定；k作为参数，造成机器个数与映射函数造成紧耦合。

2、虚拟桶：两层映射

　　k-p:数据通过哈希函数映射到虚拟桶，1对多，一个虚拟桶存多条记录

　　p-m:虚拟桶通过查表方式映射到物理机，1对多，一个机器存多个桶

优点：扩展灵活。将数据之间映射到机器，解耦成两级映射

新增机器时，p-m的表只需修改个别条目

3、一致性哈希：

　　分布式哈希表（DHT）是一种技术概念，实现有多种，比如Chord(和弦)系统中提出的一致性哈希算法。

　　一致性哈希算法：将哈希数值空间按照大小组成收尾相连的环，每台机器映射到哈希值上，这台机器负责落在一段有序哈希值范围的数据。同时机器记录环中的先驱和后继节点，使之成为有向环。

　路由问题：

低效率的方法：根据key的hash判断是否是本节点管辖范围，若是返回value，不是就转给其他节点继续查找，循环。

　　 2. 高效方法：每个节点配置存储m条路由信息的路由表，第i项表示距离当前节点2^i的哈希空间节点。设计三个节点Np(前驱)、Nc(当前)、Ns(后继)。

该算法有两个步骤：

1、c< j <= s,key在C的范围内，返回值

2、不在，找路由表，找到比j小的最大编号节点Nh,让Nh去找，（j > c + 2^i,i对应的节点h）递归进行这两部.

1）当新增节点情况：

Nnew节点先指向Nx(网络中的节点)，根据路由算法查询Nnew对应的H（Nnew） = new,找到new的后继ns,ns的前驱是np.

第一：改变np,nnew,ns直接的映射关系，构建新网络（需要稳定性检查）

第二：将ns上的小于new的迁移到new上

2）稳定性检查，对Nc进行检查，

假设ns为nc的后继，nc向ns询问ns的前驱np,答复分四部，
如果 s<p<c,则告诉nc,p就是c的后继
条件不满足，设nx为当前的后继节点。nx <-- null 或者 x < c <p,则告诉c，x是c的后继
数据迁移到nc上

3）当nc离开网络时，正常离开和异常离开，都只影响后继节点的数据

正常离开：通知相应的节点，更新前驱和后继，将本身的数据迁出到后继接单，更新其他机器路由表。
异常离开：机器故障，可通过主备份机器获得

一致性哈希算法缺点：机器节点位置随机，导致负载不均衡。将所有机器视为均等，造成低配置高负载。

4、虚拟节点：将物料节虚拟成若干虚拟节点，分别映射到环状结构的不同位置。使得负载更加，兼顾机器异质性问题

四、范围分片:

主键排序，划分分片，保存分片的映射表，记录最小主键和对应的物理机地址。物理机的管理LSM树。

---恢复内容结束---