一致性哈希模型如何优雅扩容

[ma6174]

如果不清楚一致性哈希的原理，先移步这里： http://blog.codinglabs.org/articles/consistent-hashing.html

项目初期，为了节省成本，可能只用3台机器做缓存，通过一致性哈希方式将请求分摊到3台机器上面。后面随着业务量扩大，3台机器遇到性能瓶颈就需要扩容。假设我们扩容一倍到6台机器，如果直接将三个新节点加入一致性哈希环里面，就意味着一半的缓存会失效，这无疑会给后端服务造成巨大冲击。为了减小冲击，可以每次新增一个节点，第一次有25%的缓存失效，为了减小对后端的冲击可能需要在凌晨操作，过一段时间，等缓存新节点里面有足够多数据之后，再增加第二个节点，理想情况下第二次添加节点只有20%的缓存失效。同样的方式再增加第三个节点，16.7%的缓存失效。后面再新增节点失效的缓存会逐渐减少。

回顾一下上面的的扩容方式，有几个地方不太优雅：

1. 扩容导致缓存失效。如果服务器压力已经很大，25%的缓存失效意味着对后端服务会有较大冲击。
2. 每次新增一个节点，不能立即增加下一个节点，需要等缓存填充，这个时间不可控，有可能导致扩容的周期非常长，增加运维人员负担。

有没有什么方式可能一次性扩容多个节点，并且缓存不失效呢？这个想法很美好，其实也是可以做到的。

对应原先三台机器A,B,C组成一个哈希环H1，三台新机器D,E,F和A,B,C组成一个新的哈希环H2，我们需要实现一个特殊的读逻辑：先去H2读，当H2不存在的时候去H1读，两个都不存在意味着缓存不存在。写操作全部在H2，一段时间后当D,E,F三台机器缓存被填充之后移除哈希环H1，只保留H2，也就是我们希望的扩容的最终结果。

再来分析一下上面扩容方式的优缺点

• 优点： 一次性扩容，可扩容任意多机器数，扩容期间缓存不失效，对后端无冲击。
• 缺点：读逻辑变复杂，3台扩6台之后，有一半的缓存需要读两次才能读到，并且所有缓存不存在的情况都需要读两次才能最终确认。

大部分情况下，读缓存的时间远小于读后端的时间，可以推测，两次读缓存的时间也是远小于读后端的时间的，这种情况下读两次带来的额外开销可以忽略。

新的扩容方式还有优化的空间，当在H2读不到的时候，会再去H1读，因为我们H2集群里面已经包含了H1集群，如果在H2读的是A,B,C三台机器，那么就不需要再去H1集群读，因为即使去H1读，也是同一台机器，结果是一样的。优化之后每台机器的读写请求数不会比扩容前高。

对于简单哈希，也可以使用上面的方法进行优雅扩容。

[kuangchanglang]

补充一点，只写H2+双读H2H1的方式，过程中会有脏数据。
举个例子：key1哈希到H1的A和H2的D，删除key1时只删了H2，下一次读H2未命中再读H1拿到老数据。

[jl2005]

删除的时候同时删除H1和H2，是否可以避免这种脏数据的产生？

[firefeifei]

这个是理论还是已有具体实现了