关于一致性哈希算法在游戏服务器端的思考

1. 需求分析

   • 后端有很多逻辑node节点（not-section binded），节点启动后注册到注册中心
     • node本身有状态，有内存cache，有过期时间
   • 客户端登陆，需要从注册中心分配一个node
     • a. 客户端需要在一段时间内连接固定节点（长连接）。因为内存有状态，最好支持客户端断线一段时间再次连接还是之前的节点
     • b. 节点最好是相对负载均匀的
     • 考虑新增/减少节点（宕机），最好保证a/b两点

2. 引入一致性hash算法

   • 算法主要参考：dubbo ConsistentHashSelector 并做部分修改

   • 算法测试

     • a. 初始运营服5个，每个服10w注册，即50w注册。后端一个node承载1w，后端初始50个node

       算法步骤

       1. 初始化50w个rid，rid格式 serverId_id，shuffle
       2. build hash ring，replicaNumber（虚拟节点） = 160
       3. 依次遍历shuffle后的rid list，从hash ring select
       4. 看node整体分布情况（最大、最小、平均、标准差）
       5. 不断调整虚拟节点数目

       统计结果展示

       [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

       结论

       1. 在节点不动态变化的情况，算法可以保证同一个rid每次都select到同一个node
       2. 通过调整replicaNumber，可以让node负载相对均匀
       3. 因为rid样本是可确定的，所以可以这种方式不断调整hash ring的参数，来符合实际的负载情况，即是可预测的
          • 如果一个node负载是1w，那么目前会有node overloaded。实际可以考虑将node负载调整为9k

     • b. 从a的结果上看，看似很美好，比较好的满足我们的需求，but 我们还要考虑新增/减少节点的情况

       假设

       1. 让我们问问题先简化一下 因为我们本身是长连接，所以假设之前的50w个rid全部连接到已知的50个node

       2. 需求：准备开始开第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

       结论

       1. 我们在假设条件成立的情况下，我们期望新增的10w客户端全部负载到新的10个node上。但是从结果上看，其实是负载了整个的60个node上（这个其实也是相对均匀的）。这个和我们预期完全不相符
       2. 从一致性hash的算法实现上看，对于新增/减少节点来说，一定是会有一部分客户端重新分配节点，这个是由算法本身决定的

3. 继续沿着一致性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没有命中的话（增/减），那么对于应用层来是可以重新从数据库加载的。所以其实应用场合并一定特别适合
     • 对于我们的需求，我们手动实现一个基于负载的类似轮询算法，是不是更简单？

4. 再换一个思路 假如我们把连接和数据分开呢？

   • 假如我们让客户端不是直接连接后端的node，而是一个网关呢？
   • 网关负责连接，node负责数据
   • 我们有一组网关，网关的数量是固定的（当然也可以在维护时间调整），先通过客户端rid做hash运算到对应的网关（为保证均匀，可以考虑一致性hash）
   • 然后再通过网关和后端node的映射关系得出客户端该路由到那个node上。这样node节点动态变化时，只需要修改路由表中网关和动态node之前的关系即可
   • TODO
     • Consistent Hashing + Distributed Hash Table （Orleans）

5. 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
   • {技术}某分布式应用实践一致性哈希的一些问题