有关一致性哈希算法的应用场景 博客分类： 技术 架构 一致性哈希算法负载均衡集群避免震荡
程序员文章站
2024-03-16 15:04:16
...
Tim Yang去年在博客（http://timyang.net）讨论一个有状态服务的场景下如何使用一致性哈希算法的问题。其中主要涉及到增加或删除节点时引起的系统震荡。其中也讨论了是否使用随机选取节点，并使用memcached保持选择的方案。
我们知道一致性哈希算法可以很好的解决增加或删除节点时引起的系统震荡问题。采用虚拟节点后，平均的将增删节点产生的震荡分配到其他节点上。测试证实了一致性哈希算法有很良好的平均性。
我们做一个简单测试：
有50个node，200个虚节点，100000个session。分别测试增加10%的节点和删除10%的节点对系统有多少影响。结果分析如下，
Normal case : nodes count : 50
Added case : nodes count : 55
Reduced case : nodes count : 45
85512 --- 85431
Same percent in added case : 89.218124%
Same percent in reduced case : 89.13361%
（增加或删除10%的节点后，仍有约89%的session被分配给原有节点）
但测试中暴露了两个问题，有待以后研究。
一个是随着节点数的增加，分配给每个节点的session不再是非常平均。特别是在环开始的几个节点分配的较少
第二是当节点数量很多时，比如2^32大小的寻址空间上，如果节点数量很大，超过1000个虚节点，算法性能就开始有比较明显的下降。这可能是由于实现问题，但是还需要调研。
回到原来的问题上，即什么样的场景适合使用一致性哈希算法。
这里有两类场景，我们先来讨论比较简单的情况。
场景一
假设有一种静态资源，例如视频、网页、大型log文件等，只有第一次请求时才加载到系统中。我们希望以后每次对相关资源的请求都送达到同一个节点。这样可以最大限度的利用整个集群的能力，这也是CDN的基本思路。
这类场景的特点是，
1，在高并发情况下，如何使多个并发请求都被发送到同一节点。
2，session实际是无状态的
在该情况下，使用一致性哈希是很合适的。我在构建高性能Java服务器中谈到了使用一致性哈希算法替代多线程上同步锁，从而极大的提高系统性能。就是在这个场景下实现的。
场景二
一个有状态服务，持有大量有状态session，且session不断的被更新和查询。
这种类型的session是不可能被实时更新到数据库的，因此它们只能在分布式内存中被保持。由于session更新频繁，且要特别考虑到场景是多线程同时受理对同一session的多个请求。因此我们的考虑是，不能完全把session保存在一个分布式memory中，因为频繁的更新对CPU和网络都有比较大的压力session异步备份，还是那句话，这次业务可以失败，但是系统不能因为业务无法更新而停止工作
可以有几种解决方案，
buddy replication+一致性哈希
借鉴Jboss Cache buddy replication的思路。为了减少网络和被备份节点的压力，我们不希望把session复制到整个cluster上。但是又希望可以当单点crash后从内存恢复数据。因此我们只把session备份到几个节点上，例如当一致性哈希找到了工作节点后，该工作节点再使用固定后缀找到buddy node进行复制。
例如，sessionID+"buddy1"；sessionID+"buddy2"；
每次更新本地session的同时，节点异步的向buddy中的memcached写一个备份。如果本节点crash，session被分配到其他节点处理，它会试图从buddy的memcached中取回状态。
whole cluster replication
如果你的服务要求一个会话都不能丢失，则只能进行全cluster复制。这样可以保证任何一节点活着就能继续进行业务。我们测试过一些开源产品，比如Jboss InfiniSpan，
在节点数量不大，且网络条件很好的情况，仅用UDP进行whole cluster replication效果就很好。如果参考其实可以发现，通过NIO/TCP进行可序列号对象复制，其速度和可靠性在节点数较多的集群中也可以工作的很好。
以上两种场景在实际运营的系统中都可胜任，当然对于不同客户的不同要求，需要采用不同的架构。另外要考虑到团队的能力，比如团队如果一直基于JBoss开发，且用户对session状态的丢失率有严格要求，则采用Jboss Cache是最简单的方法。尽管它显然没有一致性哈希这么酷：）
本文纯属原创，欢迎转载，请注明原网址；
我们知道一致性哈希算法可以很好的解决增加或删除节点时引起的系统震荡问题。采用虚拟节点后，平均的将增删节点产生的震荡分配到其他节点上。测试证实了一致性哈希算法有很良好的平均性。
我们做一个简单测试：
有50个node，200个虚节点，100000个session。分别测试增加10%的节点和删除10%的节点对系统有多少影响。结果分析如下，
Normal case : nodes count : 50
Added case : nodes count : 55
Reduced case : nodes count : 45
85512 --- 85431
Same percent in added case : 89.218124%
Same percent in reduced case : 89.13361%
（增加或删除10%的节点后，仍有约89%的session被分配给原有节点）
但测试中暴露了两个问题，有待以后研究。
一个是随着节点数的增加，分配给每个节点的session不再是非常平均。特别是在环开始的几个节点分配的较少
第二是当节点数量很多时，比如2^32大小的寻址空间上，如果节点数量很大，超过1000个虚节点，算法性能就开始有比较明显的下降。这可能是由于实现问题，但是还需要调研。
回到原来的问题上，即什么样的场景适合使用一致性哈希算法。
这里有两类场景，我们先来讨论比较简单的情况。
场景一
假设有一种静态资源，例如视频、网页、大型log文件等，只有第一次请求时才加载到系统中。我们希望以后每次对相关资源的请求都送达到同一个节点。这样可以最大限度的利用整个集群的能力，这也是CDN的基本思路。
这类场景的特点是，
1，在高并发情况下，如何使多个并发请求都被发送到同一节点。
2，session实际是无状态的
在该情况下，使用一致性哈希是很合适的。我在构建高性能Java服务器中谈到了使用一致性哈希算法替代多线程上同步锁，从而极大的提高系统性能。就是在这个场景下实现的。
场景二
一个有状态服务，持有大量有状态session，且session不断的被更新和查询。
这种类型的session是不可能被实时更新到数据库的，因此它们只能在分布式内存中被保持。由于session更新频繁，且要特别考虑到场景是多线程同时受理对同一session的多个请求。因此我们的考虑是，不能完全把session保存在一个分布式memory中，因为频繁的更新对CPU和网络都有比较大的压力session异步备份，还是那句话，这次业务可以失败，但是系统不能因为业务无法更新而停止工作
可以有几种解决方案，
buddy replication+一致性哈希
借鉴Jboss Cache buddy replication的思路。为了减少网络和被备份节点的压力，我们不希望把session复制到整个cluster上。但是又希望可以当单点crash后从内存恢复数据。因此我们只把session备份到几个节点上，例如当一致性哈希找到了工作节点后，该工作节点再使用固定后缀找到buddy node进行复制。
例如，sessionID+"buddy1"；sessionID+"buddy2"；
每次更新本地session的同时，节点异步的向buddy中的memcached写一个备份。如果本节点crash，session被分配到其他节点处理，它会试图从buddy的memcached中取回状态。
whole cluster replication
如果你的服务要求一个会话都不能丢失，则只能进行全cluster复制。这样可以保证任何一节点活着就能继续进行业务。我们测试过一些开源产品，比如Jboss InfiniSpan，
在节点数量不大，且网络条件很好的情况，仅用UDP进行whole cluster replication效果就很好。如果参考其实可以发现，通过NIO/TCP进行可序列号对象复制，其速度和可靠性在节点数较多的集群中也可以工作的很好。
以上两种场景在实际运营的系统中都可胜任，当然对于不同客户的不同要求，需要采用不同的架构。另外要考虑到团队的能力，比如团队如果一直基于JBoss开发，且用户对session状态的丢失率有严格要求，则采用Jboss Cache是最简单的方法。尽管它显然没有一致性哈希这么酷：）
本文纯属原创，欢迎转载，请注明原网址；