【C#|.NET】跳出一致性Hash算法 打造更高效的分布式缓存

简介:

背景

  谈到分布式缓存,大家首先想到的是memcached。确实memcached是目前最流行的方案之一。不过很多互联网公司不用memcached,例如新蛋。为什么不选择memcached呢,命中率?热插拔?还是性能。这里先不放结论,用事实来说话。


算法篇 -1.除余法

    如果你手上有老版本的memcache官方文档。你会发现他们用的是除余法来保持节点的一致性。假如你有N台缓存服务器,你需要将某个对象set进某一台节点上。用hash取模这样可以很均匀的保证每台的负载。那么,作为最基本的轮询算法,是否适合分布式缓存我们来看实例。

这里假设有4台缓存节点,先设置除余方案。

自动设置999条键值。

下面来看下除余方案的各种综合结果

  总的来说如果是相对稳定的环境 这种方案还是相当不错,至于性能我会单独开篇幅来说。

但是如果添加一台新节点 192.168.0.5

再来重新获取键值

再随机追加200条键值

注意看数据中的命中率数据 新节点会投入环境 参与新的取模运算 但是之前因为模运算变化的键值就丢失了


算法篇 -2 普通hash算法

既然取模运算没办法保证我们的键值一致性,那么就要考虑新的方案了。不过设计我们自己的方案之前,我们可以继续看看memcache的使用者们进行了哪些改进。

通常的 hash 算法都是将 value 映射到一个 32 位的 key 值,也即是 0~2的32-1 次方的数值空间;

我不喜欢画图,大家就想象一下吧,一个首尾相接的圆。用hash算法将节点分布在圆的不同部位,同样对key值进行hash算法,通过       

public static int BinarySearch<T>(T[] array, T value)方法,匹配到对应位置。

还是找了几张图过来.... 嘴拙 讲不清楚 直接看图吧

在这个环形空间中,如果沿着顺时针方向从对象的 key 值出发,直到遇见一个 cache ,那么就将该对象存储在这个 cache 上,因为对象和 cache 的 hash 值是固定的,因此这个 cache 必然是唯一和确定的。左下表示移除节点的情况,右下表示添加节点的情况

继续看图看结果

在稳定状态下 发现负载不是很平衡 不过还能接受 继续看看添加节点的情况

命中率变70多了 能hold住了 低要求的话 应该还是不错的,再看看新节点的利用情况,随机再生成200条

马马虎虎吧 负载偏差比较大 命中率一般


算法篇 -3 一致性hash算法 _ 虚拟节点 (consistent hashing)

相对普通hash算法 多了一个虚拟节点的概念 这也是目前memcache最主流的算法。

长话短说 就是我把一个节点虚拟成N多个虚节点 这些虚节点指向同一个物理节点 但是key值hash参照虚节点来设置

直接上图

稳定状态下不错 同样我们在新添一个节点

命中率提高了不上 不过负载还不是很平衡 随机再加300条

对比普通hash算法好多了


算法篇 -4 一致性hash算法改进

针对一致性hash算法的虚拟节点 说白了就是一个50大小的坑被拆成 5个10大小的坑而已,不过缝隙小了 对于比较聚集的数据来说还是很有好处的

如何改进 将50大小的坑就变成10大小 对于新增的节点 我们不进虚拟节点化或者个性配置节点化

前面效率和一致性hash比较类似 我们直接看添加节点的情况

98% 有木有 有木有!!! 负载也还不错 你是不是已经被hold住了。

不过作为不良改进者 虫子还是要告诉大家这个改进一个很大的弊端 就是新节点的利用率

我们再随机新建600条键值

对于命中率的提高 是以新节点利用率为代价 至于之间怎么平衡 就看各自把握了


算法篇 -5 完美改进

上一种改进还是基于memcache现有的基础之上,跳出这个圈子为何要用一致性hash。

大家可以猜想一下这个方案的实现办法。关于这个方案的设计会单独开个篇幅来讲。

言归正传直接上图看结果

添加一台新服务器

命中率还是100% hold住 还有更精彩的  我们随机添加500条键值


本篇先到此 希望对大家有帮助

 



本文转自 熬夜的虫子  51CTO博客,原文链接:http://blog.51cto.com/dubing/757518


相关文章
|
14天前
|
存储 缓存 负载均衡
一致性哈希:解决分布式难题的神奇密钥
一致哈希是一种特殊的哈希算法,用于分布式系统中实现数据的高效、均衡分布。它通过将节点和数据映射到一个虚拟环上,确保在节点增减时只需重定位少量数据,从而提供良好的负载均衡、高扩展性和容错性。相比传统取模方法,一致性哈希能显著减少数据迁移成本,广泛应用于分布式缓存、存储、数据库及微服务架构中,有效提升系统的稳定性和性能。
61 1
|
28天前
|
缓存 API C#
C# 一分钟浅谈:GraphQL 中的缓存策略
本文介绍了在现代 Web 应用中,随着数据复杂度的增加,GraphQL 作为一种更灵活的数据查询语言的重要性,以及如何通过缓存策略优化其性能。文章详细探讨了客户端缓存、网络层缓存和服务器端缓存的实现方法,并提供了 C# 示例代码,帮助开发者理解和应用这些技术。同时,文中还讨论了缓存设计中的常见问题及解决方案,如缓存键设计、缓存失效策略等,旨在提升应用的响应速度和稳定性。
42 13
|
5月前
|
算法 Go
[go 面试] 雪花算法与分布式ID生成
[go 面试] 雪花算法与分布式ID生成
|
2月前
|
算法 关系型数据库 MySQL
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
在分布式系统中,确保每个节点生成的 ID 唯一且高效至关重要。Snowflake 算法由 Twitter 开发,通过 64 位 long 型数字生成全局唯一 ID,包括 1 位标识位、41 位时间戳、10 位机器 ID 和 12 位序列号。该算法具备全局唯一性、递增性、高可用性和高性能,适用于高并发场景,如电商促销时的大量订单生成。本文介绍了使用 Go 语言的 `bwmarrin/snowflake` 和 `sony/sonyflake` 库实现 Snowflake 算法的方法。
59 1
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
|
25天前
|
存储 算法 安全
分布式系统架构1:共识算法Paxos
本文介绍了分布式系统中实现数据一致性的重要算法——Paxos及其改进版Multi Paxos。Paxos算法由Leslie Lamport提出,旨在解决分布式环境下的共识问题,通过提案节点、决策节点和记录节点的协作,确保数据在多台机器间的一致性和可用性。Multi Paxos通过引入主节点选举机制,优化了基本Paxos的效率,减少了网络通信次数,提高了系统的性能和可靠性。文中还简要讨论了数据复制的安全性和一致性保障措施。
36 1
|
3月前
|
消息中间件 网络协议 C#
C#使用Socket实现分布式事件总线,不依赖第三方MQ
`CodeWF.EventBus.Socket` 是一个轻量级的、基于Socket的分布式事件总线系统,旨在简化分布式架构中的事件通信。它允许进程之间通过发布/订阅模式进行通信,无需依赖外部消息队列服务。
C#使用Socket实现分布式事件总线,不依赖第三方MQ
|
2月前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
3月前
|
算法
基于粒子群算法的分布式电源配电网重构优化matlab仿真
本研究利用粒子群算法(PSO)优化分布式电源配电网重构,通过Matlab仿真验证优化效果,对比重构前后的节点电压、网损、负荷均衡度、电压偏离及线路传输功率,并记录开关状态变化。PSO算法通过迭代更新粒子位置寻找最优解,旨在最小化网络损耗并提升供电可靠性。仿真结果显示优化后各项指标均有显著改善。
|
3月前
|
存储 开发框架 .NET
C#语言如何搭建分布式文件存储系统
C#语言如何搭建分布式文件存储系统
90 2
|
3月前
|
消息中间件 缓存 算法
分布式系列第一弹:分布式一致性!
分布式系列第一弹:分布式一致性!