Consistent Hashing

• 简单的一致性hash就是，用key mod一个很大的数，例如360。
• 将360分配给n台机器，每个机器负责一段区间。
• 将区间分配信息记录着一张表上存在web server上，
• 新加一台机器的时候，在表中选择一个位置插入，匀走相邻的两台机器的一部分数据。
  • 找最大的相邻的两个区间（加起来最大的）

缺陷

• 数据分部不均匀
• 迁移压力过大，新的机器数据只从老的机器获取，不能从别的机器获取

把整个Hash区间看做环

• 将环的大小从0-359变为 0-2^64-1
• 将机器和数据都看成环上的点
  • 数据点放在环上顺时针遇到的第一个机器位置，这样就可以看到环上的机器负责的区域为从他前一个机器顺时针到他的这个范围
• 引入Micro shards/virtual nodes
  • 每一台实体机器对应1000个分身，映射到环上，
  • 计算某个key所在服务器时候，计算hash，获得在环上的位置，顺时针找到第一个virtual node，就可以把数据存到这个node所在的机器，这样可以有效的解决环上可能存在的分部不均的问题
  • 数据结构用treemap
• 加入新的机器的时候，要进行数据迁移
  • 新的这些virtual node要顺时针的找到他的下一个node，找她要数据

http://www.lintcode.com/problem/consistent-hashing-ii/

Replica

• Backup
  • 一般是周期性的
  • 当数据丢失的时候，通常只能恢复到之前的某个时间点
  • backup不用做在线的数据服务，不分摊读
• Replica
  • 是实时的，在数据写入的时候，就会以复制品的形式存为多分
  • 数据丢失的时候，可以马上通过其他的replica恢复
  • Replica用做在线的数据服务，分摊读

SQL Replica

• Master Slave的replica
  • master负责写
  • slave负责读
• Write Ahead Log (WAL)
  • SQL数据库的任何操作，都会以log的形式做一份记录
  • 比如数据A在B时刻，从C改到了D
  • Slave被激活以后，告诉master我在了
  • master每次有任何操作就通知slave来读log
  • 因此slave上的数据是有『延迟』的，例如master已经完成了写操作，slave才刚刚获取log，需要一段时间才能同步
• Master挂了怎么办
  • 将一台slave promote为master，接受读写
  • 可能会造成一定程度的数据丢失和不一致

NoSQL Replica

• 顺时针找到下面连续三个不同的机器(virtual node) 存三分