1. 概要
本文希望用一杯咖啡的时间，讲明白什么是数据拆分(Partitioning) ，什么是数据复制 (Replica), 一致性哈希算法为何被引入，什么是一致性哈希算法，以及解读amazon 在2007年发表在ACM上，DynamoDB 经典论文 Dynamo: Amazon’s Highly Available Key-value Store 如何应用这些技术。
挑战：
日常生活中，经常会发生，当一台数据库挂了，用户访问不到数据怎么办？以下解决方案可以用来解决这个问题：
1.数据拆分 Sharding or Partitioning
2.数据复制 Replica
2. 数据复制
数据复制 (Replica) 是实时的，每一份数据在写入的同时，会被同时在其他几台机子上面存放几分相同的数据。当某一台机子上的数据丢失的时候，立马能从其他机子获得该数据。数据复制，也能分摊读请求，用户访问一份数据，就不在只能从某一台机子上获取。
数据复制和备份(backup) 有什么区别呢？
数据备份通常是每隔一定时间，进行一次备份。数据丢失的时候，只能恢复到之前某个时间点的数据。数据备份不能分摊读请求。
3. 数据拆分
数据拆分就是把数据分成多块，存在不同的机器上。则挂了一台，不会全挂，也能分摊读写能力。数据复制就是同一份数据存在其他的机器上，多存几份。挂了一台，还可以从其他机器恢复，也能分摊读请求。
数据拆分分为纵向拆分vertical sharding 和纵向拆分 hirizontal sharding。
纵向拆分：
根据工作性质不同，不同类型的表放在不同数据库。例如，订单库，商品库等等。 纵向拆分缺点：如果，表单很大，则访问量就很大。
横向拆分：
将同一个表，分成多部分，存在不同的数据库中。例如将一部分内容存放在机器a, 另一部分内容存放在机器b, 还有一部分内容存放在机器c. 这样用户访问数据时候，可以分散读写，不会仅仅从一台机器里获取数据，导致该机器访问量很大.
那么如何拆分？
方案1：可以把旧的数据存在一起，新的数据用新的机子存，但是这样的缺点是，人们访问最近使用的数据频率比较高，访问就数据频率低，导致各个机子访问量不均匀。 通常将读写访问量不均匀，部分机子访问量异常大的这些机子称之为热点(hot spot)。
方案2：传统的哈希算法，用hash function = key % n 的方式。
例如，n = 3时候，key 0~11, 根据key % 3, 所得的hash值是多少，就代表数据存在哪一台机子。
哈希值为0， 数据存在db0, db0: [0, 3, 6, 9]
哈希值为1， 数据存在db1, db1: [1, 4, 7, 10]
哈希值为2，数据存在db2, db2: [2, 5, 8, 11]
当增加一台机子时候，即n = 4, key 还是0 – 11, 根据key % 4。 新的映射变为：
哈希值为0，数据存在db0, db0:[0, 4, 8]
哈希值为1，数据存在db1, db1:[1, 5, 9]
哈希值为2， 数据存在db2, db2:[2, 6, 10]
哈希值为3, 数据存在db3, db3:[3, 7, 11]
4. 一致性哈希算法
什么是哈希不一致？
根据以上方案二的例子，可见，当增加或删除一台机子的时候，大部分数据都发生了迁移，如果不把相应的数据迁移到新的对应的机器上，那么用户将请求不到该数据，会发生错乱。这就称之为哈希不一致。
根据哈希不一致现象，1997年，麻省理工学院 MIT 提出了一致性哈希算法，一致性哈希算法主要应用在横向拆分，当增加或删除一台机器的时候，会尽量少地减少数据的迁移。
简易的一致性哈希算法
例如，hash function = key % 2^64, 将0 ~ 2^64 – 1 看做是一个很大的圆圈，0 和 2^64 -1 首尾相连。根据hash function, 每个key 都会被计算出一个hash value, 这个hash value对应在这个圆圈里的某个位置。 圆圈上有几台机子，例如，圆环上有A, B, C, D机器，表示四台数据库，那么这个Key，根据hash function找到在圆环的位置 ，往顺时针方向找到的紧挨着的机器A， 就表示A会存储这个key的数据。
如下图所示，（KeyNote绘制）
Note:
这里不详细阐述hash function如何计算，有许多对应的算法，尽量少产生hash colission 的算法较好。在以上例子，根据2^64 取模， 两个不同的key得出相同的hash value的概率就已经足够低了。
缺点：
这种算法有个缺点，无法解决均匀性。每个key计算出来的hash value 都是相对无规律的一个位置，倘若全部落在某一台机子负责的范围内，将导致该机器访问量很大。
改进的一致性哈希算法
改进的一致性哈希算法，为了解决这个问题，讲引入虚拟节点 (Virtual Node)的概念， 虚拟节点的思想就是，每一台实体机器，同时带有数个虚拟节点，较为均匀地分散在这个圆环中。 当一台新的机器加入时， 同时，它附属的多个虚拟节点也将被一并加入，遍布在整个圆环上。引入虚拟节点后的一致性哈希算法，将增加数据分部的均匀性，各台机器以及虚拟节点将被分配到更加均匀的访问量。
如下图所示，（KeyNote绘制）例如，每台机器都带有2个虚拟节点，每增加1台机器，实际上在圆环内相对任意地产生3个位置代表机器A以及它的虚拟节点。那么每需要查询一个key， 由hash(key)算出来它在圆环上的位置，根据落在圆环上的位置，就由紧挨着的下一个node来存储它的数据。
这个算法的引入，能够使数据的存储和查询落在相对均匀的机器上，减少热点(hot spot)机器负载过多的缺陷。在下面一个部分，我们可以看到这款算法的具体应用。
5. 一致性哈希算法和数据复制在Amzon DynamoDB的运用
Amazon DynamoDB 是Amazon给出的存储海量数据的方案，是一款适用于“任何规模的快速灵活的 NoSQL 数据库服务”，是一款去中心化，高可用的分布式 key-value store存储系统。 这一篇论文发表于2007年, 这篇 Dynamo 论文Dynamo: Amazon’s Highly Available Key-value Store 喜获 ACM SIGOPS 名人堂奖（Hall of Fame Award, HoF）。
Amazon DynamoDB 数据拆分的方案
根据Amazon DynamoDB论文所述，Amazon DynamoDB采用的就是如上所示的改进的一致性哈希算法，引入虚拟节点，这样做的好处是：
1）如果某个节点挂了，这台节点上的负载将被均匀地分配到其他可用的，隶属于同一台机器的节点上。
2）如果某个节点恢复状态，那么其他的隶属于同一台机器的节点将各自分配相对均匀的负载到这台刚恢复使用的节点上。
Amazon DynamoDB 数据复制的方案
数据拆分通常和数据复制一同结合使用,根据Amazon DynamoDB论文所述， 每一份数据将被复制并且存放在N台机器上，例如当N = 3, 某个key K按照一致性哈希算法，将由于B负责它的存储，B又把这份数据，按照顺时针的方向，复制到C,和D, 所以，B,C,D都将存有这个key K的数据。 机器D, 将存有自身携带的(C,D] 区间的数据，以及被它的它之前的其他节点复制过来的，来自(A, B], (B, C]的数据。
图片引用自Amazon DynamoDB论文
数据拆分和数据复制是Amazon DynamoDB论文里面重要的2个部分，其论文还包括故障检测，如何处理暂时故障，应对永久性故障如何恢复等等内容，由于本文的话题是数据拆分和数据复制，博主将重新写一篇博客来详细解读。
FAQ
1.使用hash partitioning 能否彻底解决hot spot问题呢？
不能，hash partitioning只能削弱hot spot 的出现。但是，在特定情况下，仍然会出现对同一个Key的write / read 过多，产生hot spot. 例如，某个大v 发了一些热点头条新闻，例如娱乐圈出了某个事件，会导致这个大v的所有followers, 可能有几千万follower 会产生对某一个相同的key的查询， 这个key可能是这个大v的user id, 或者是某一个actin 的id， 用户们对这个action 产生了许多评论， 这也将导致hot spot的出现，而hash partitioning 无法避免这种情况。
那么如何解决这种情景呢？ 可以在这个Key的头部或者结尾，加入一个2位任意十进制数， 这样就可以把对同一个Key的写入，分散到100个不同的key，分散到不同的partition中。那么每一次read 将根据这100个不同的key中读取，并且合并得到结果。 这种方法只适用于对少部分hot spot进行操作， 对于大部分写入少的Key来说，如果也加了这种操作将带来许多不必要的开销。所以，根据不同的情况要进行权衡，选择不同的方案。
2. Primary key 的second part 是用来做什么的，secondary index又是做什么的？
Primary key 可以由于 first part + second part组合而成，first part 用于决定这个数据存在哪个partition， second half 可以用来做排序，可以根据second part 来做一些范围内的查询.
Secondary index 并不是必须的，有的数据库系统禁止secondary index的存在，因为这会增加了不少复杂度。 Secondary index应用的一个例子，例如，有一个关于汽车库存的数据库，你可以用primary key index – unique id来做拆分，比如把0 – 499号 id 分在partition 0, 500 – 999 分在partition 1. 你还可以设置一个secondary key， 例如车子的颜色，或者品牌。 那么你可以根据这个secondary key, 例如汽车的颜色，从不同partition 中筛选出所有颜色为x的汽车， 并把结果合并。 更多内容可以参考 Designing Data-Intensive Applications 这本书，链接放在参考栏目中。
参考
Paper: Dynamo: Amazon’s Highly Available Key-value Store
0 赞 Like
Test comment