关于一致性哈希算法在游戏服务器端的思考
需求分析
后端有很多逻辑node节点（not-section binded），节点启动后注册到注册中心
node本身有状态，有内存cache，有过期时间
客户端登陆，需要从注册中心分配一个node
a. 客户端需要在一段时间内连接固定节点（长连接）。因为内存有状态，最好支持客户端断线一段时间再次连接还是之前的节点
b. 节点最好是相对负载均匀的
考虑新增/减少节点（宕机），最好保证a/b两点
引入一致性hash算法
算法主要参考：dubbo ConsistentHashSelector 并做部分修改
算法测试
a. 初始运营服5个，每个服10w注册，即50w注册。后端一个node承载1w，后端初始50个node
算法步骤
初始化50w个rid，rid格式 serverId_id，shuffle
build hash ring，replicaNumber（虚拟节点） = 160
依次遍历shuffle后的rid list，从hash ring select
看node整体分布情况（最大、最小、平均、标准差）
不断调整虚拟节点数目
统计结果展示
[7743, 8777, 8847, 8932, 8985, 9100, 9185, 9229, 9274, 9308, 9330, 9478, 9625, 9638, 9660, 9697, 9699, 9728, 9748, 9791, 9794, 9847, 9904, 10021, 10053, 10055, 10063, 10073, 10257, 10258, 10263, 10291, 10356, 10374, 10376, 10486, 10519, 10521, 10581, 10620, 10628, 10678, 10719, 10783, 10790, 10837, 10859, 11001, 11120, 12099]
replica:160 |max:12099|min:7743|mean:10000.0|std:750.9|median:10054.0
[9142, 9393, 9518, 9525, 9549, 9578, 9626, 9659, 9667, 9690, 9765, 9777, 9811, 9831, 9848, 9850, 9886, 9889, 9909, 9933, 9940, 9958, 9998, 10002, 10007, 10029, 10030, 10050, 10052, 10129, 10152, 10158, 10182, 10184, 10202, 10212, 10213, 10215, 10247, 10265, 10273, 10279, 10297, 10321, 10322, 10342, 10358, 10420, 10456, 10861]
replica:1280 |max:10861|min:9142|mean:10000.0|std:317.2|median:10018.0
结论
在节点不动态变化的情况，算法可以保证同一个rid每次都select到同一个node
通过调整replicaNumber，可以让node负载相对均匀
因为rid样本是可确定的，所以可以这种方式不断调整hash ring的参数，来符合实际的负载情况，即是可预测的
如果一个node负载是1w，那么目前会有node overloaded。实际可以考虑将node负载调整为9k
b. 从a的结果上看，看似很美好，比较好的满足我们的需求，but 我们还要考虑新增/减少节点的情况
假设
让我们问问题先简化一下 因为我们本身是长连接，所以假设之前的50w个rid全部连接到已知的50个node
需求：准备开始开第6个服，在新增10个node，用来承载10w人，并重建hash ring
测试输出
// 这个是已经连接的50个node的数据分布情况，和a的结果一致，也验证了本身一致性hash算法的正确性
[9142, 9393, 9518, 9525, 9549, 9578, 9626, 9659, 9667, 9690, 9765, 9777, 9811, 9831, 9848, 9850, 9886, 9889, 9909, 9933, 9940, 9958, 9998, 10002, 10007, 10029, 10030, 10050, 10052, 10129, 10152, 10158, 10182, 10184, 10202, 10212, 10213, 10215, 10247, 10265, 10273, 10279, 10297, 10321, 10322, 10342, 10358, 10420, 10456, 10861]
replica:1280 |max:10861|min:9142|mean:10000.0|std:317.2|median:10018.0
// 这个是新增10个node后的数据分布情况
[1499, 1534, 1569, 1652, 1673, 1675, 1684, 1712, 1713, 1723, 10585, 10948, 11119, 11162, 11173, 11177, 11223, 11267, 11270, 11324, 11348, 11404, 11504, 11511, 11530, 11546, 11547, 11569, 11570, 11610, 11631, 11635, 11674, 11681, 11684, 11706, 11742, 11750, 11758, 11769, 11796, 11815, 11842, 11855, 11878, 11908, 11912, 11921, 11933, 11952, 11991, 11996, 12019, 12068, 12068, 12077, 12089, 12157, 12215, 12657]
replica:1280 |max:12657|min:1499|mean:10000.0|std:3783.8|median:11620.5
结论
我们在假设条件成立的情况下，我们期望新增的10w客户端全部负载到新的10个node上。但是从结果上看，其实是负载了整个的60个node上（这个其实也是相对均匀的）。这个和我们预期完全不相符
从一致性hash的算法实现上看，对于新增/减少节点来说，一定是会有一部分客户端重新分配节点，这个是由算法本身决定的
继续沿着一致性hash的思路走
主要问题
a. 如何解决新增/减少节点，部分客户端select节点变化的问题？
b. 如何解决新增节点，整体的负载均匀问题（甚至分配过程中的相对均匀，即不会出现分配过程中某一个node先达到上限，而是整体均衡）？
一些扩展思路
对于a
可以在客户端select到一个节点后，将客户端和节点的映射关系保存下来。客户端断线再连接还是同一个节点。当内存数据过期后，下次再连接，可以再次重新映射
可以在每次客户端断线时，强制刷新一下对应的node内存数据到外部缓存。这样当客户端再次连接时，如果切到了其他的node也没有关系，只不过额外走一次加载流程。不过如果是频繁断线重连的情况下则需要额外注意
对于b
可以引入有限负载一致性哈希，即node有负载的概念。首选还是按照正常的一致性hash算法选择某一个node。不过区别是会判断此node是否overloaded，如果overloaded，则继续从hash ring寻找下一个node，直到未超过负载。引入该算法后，对于2b中的测试来说，新的10w人会被主要分流到新增的10个node上
我目前实现的一个版本是可以设置一个node的负载上限比如9000
不过引入负载后，就需要额外维护负载这个指标。比如客户端内存数据过期后，将客户端所属的node的负载-1
思考
如果我们按照一致性hash的思路实现需求，是可以做的，只不过有不少额外成本。那这样的必要性大吗？
一致性hash最早的例子是用在如memcache，根据key hash到对应的node。而这个应用场合是缓存，即使key没有命中的话（增/减），那么对于应用层来是可以重新从数据库加载的。所以其实应用场合并一定特别适合
对于我们的需求，我们手动实现一个基于负载的类似轮询算法，是不是更简单？
再换一个思路 假如我们把连接和数据分开呢？
假如我们让客户端不是直接连接后端的node，而是一个网关呢？
网关负责连接，node负责数据
我们有一组网关，网关的数量是固定的（当然也可以在维护时间调整），先通过客户端rid做hash运算到对应的网关（为保证均匀，可以考虑一致性hash）
然后再通过网关和后端node的映射关系得出客户端该路由到那个node上。这样node节点动态变化时，只需要修改路由表中网关和动态node之前的关系即可
TODO
Consistent Hashing + Distributed Hash Table （Orleans）
ref
Improve consistent hashing load balancing with a new algorithm(patch for 3.0)
蚂蚁金服服务注册中心如何实现 DataServer 平滑扩缩容
Dubbo 一致性Hash负载均衡实现剖析
Making The Case For Building Scalable Stateful Services In The Modern Era
{技术}某分布式应用实践一致性哈希的一些问题
