`
ScotTina
  • 浏览: 9714 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

一致性哈希算法的优化----关于如何保正在环中增加新节点时,命中率不受影响

阅读更多

 

背景

 

09年初,我们做了一个memcached的智能客户端库,业务只要将这个库链上,就能跟memcached服务器通信。并且实现了一致性哈希的分布式算法,后端memcached服务器可以无限制扩展,而且客户端能对memcached做自动故障转移以及恢复。

我们知道,在没有对数据做冗余存储的情况下,无论是一致性哈希还是求余数分布式算法,在新增或删除memcached节点时,命中率都会不同程度的降低。本文旨在解决当新增memcached节点时,如何保证命中率不变。

 

 

基本原理

 

新增一个memcached节点时,将该新节点的下一个节点的且属于该新节点的数据迁移过来。

 

上面的这个基本原理读起来可能会比较拗口,容我下面详细说明。

 

 

原理描述

 

如图1所示,假设当前哈希环上有nmemcached节点,记为M1~Mn,存储到这些节点上的数据的有效期都是一致的,记为Te。因此从图1可以看出,从M1Mk区间的数据均从Mk上存取。比如数据K1K2Kn

         
                  
    

                                                                            图1

当新增节点Mx时,如图2所示。

                  
                     
                   

                                                                              图2

此时数据K1K2从新节点Mx读取不到的,但节点Mk存储了这些数据,我们需要做的就是将这些数据迁移到新节点Mx

 

具体做法是:将新加入的节点Mx标记为NNew)状态,表示该节点是新增的。在N状态下读取数据K1的步骤为:

1)Mx读取数据,如果读取得到,则返回,否则进行2);

2)Mk读取数据,如果读取不到,则返回,否则进行3);

3)将读取到的数据K1写入Mx

4)K1Mk删除;

 

N状态下,不断进行上面的4个步骤

 

因为数据的有效期是Te,所以在经过Te时间后,Mk上的数据随之自动失效了,此时将Mx标记为OOld)状态,在O状态下,如果读取不到数据也立即返回,无需再次到它下一个节点尝试读取。

  • 大小: 12.9 KB
  • 大小: 11.9 KB
4
3
分享到:
评论
4 楼 hellwhj 2018-03-29  
所以说,其实完全可以专门做一个迁移服务来做这个事的,不需要改变正常客户端取数据的逻辑。
迁移服务:先初始化并且分配新的虚拟节点给新库和表,然后计算每个新虚拟节点hash在旧虚拟节点列表中的位置,找到迁移数据,将其复制过来,然后将新节点加入列表,然后将列表推送给各客户端,然后将被复制的数据从旧节点中删掉。
3 楼 hellwhj 2018-03-28  
感觉在实践中,本方案应用面比较窄,仅适用于不用虚拟节点的情况,此时只增加一个新节点,则该新节点与下一个节点之间的数据就会落到新节点里。这种可以使用本方案。

而一般分布式缓存都是用虚拟节点,每次增加新节点时,都是要迁移虚拟节点,一个数据落到哪个虚拟节点里,这个是不变的。所以扩容时的关键就在于如何调整虚拟节点在实体节点里的分布了。
2 楼 lanceyan 2013-05-12  
scott怎么没有继续写文章了
1 楼 biankai008 2011-11-03  
最近正准备做memcache集群,受益良多啊。

相关推荐

    一致性Hash(Consistent Hashing)原理剖析1

    总的来说,一致性哈希算法通过环形空间和虚拟节点的设计,实现了在动态调整系统规模时,尽可能少地改变已分配的对象,提高了系统的扩展性和可用性。随着节点数量的增加,一致性哈希能够保持较高的缓存命中率,减轻对...

    一种改进的分布式存储系统节点动态扩展策略.pdf

    通过对现有一致性哈希算法的改进,该策略不仅解决了扩容带来的问题,还能够迅速适应节点故障的情况,确保数据能够在各个存储节点之间重新均衡分布。 在实际应用中,一致性哈希已经被广泛应用于分布式存储系统,如...

    Memcache缓存

    - **更好的缓存命中率:** 当服务器集群发生变化时,一致性哈希算法可以最小化缓存数据失效的数量,从而保持较高的缓存命中率。 - **动态扩展:** 支持动态地添加或移除服务器,而不会对现有的缓存数据造成太大影响...

    memcached-笔记资料

    1. "一致性哈希对缓存命中率的影响实验报告.doc":这份文档可能详细介绍了如何使用一致性哈希算法来分配和检索数据在Memcached中的存储,以及该算法如何影响缓存的命中率。一致性哈希是解决分布式缓存中数据分布不均...

    Memcached集群搭建

    在Memcached中,没有内置的集群管理机制,但可以通过一致性哈希算法实现数据分布。一致性哈希允许我们根据键的哈希值将数据分配到不同的节点上,即使有节点加入或离开,也只需要重新映射少量数据。 #### 1. 使用...

    边缘计算数据库优化.pptx

    - **分片策略**:采用一致性哈希算法或范围分片等方式,有效分配数据负载,避免热点问题。 **2.3 冷热数据分离** - **热数据处理**:对经常访问的热数据进行快速访问优化。 - **冷数据迁移**:将不常访问的冷数据...

    基于区块链的去中心化缓存.pptx

    - 索引和检索算法的优化减少了查询时间,提高了缓存命中率。 4. **安全保障**: - 区块链的加密技术确保了缓存数据的机密性和完整性。 - 数据加密有效阻止了未经授权的访问和篡改,增强了缓存服务的安全性。 - ...

    基于云计算的分布式缓存.pptx

    - 典型的分布式缓存采用客户端-服务器架构,客户端负责与缓存服务器进行交互,而服务器则根据特定算法(如一致性哈希算法)将数据分散到多个缓存节点上。 - 为了保障数据的一致性和高可用性,分布式缓存系统还包含...

    代码优化与高性能计算.pptx

    - **代码剖析**:深入了解函数调用、缓存命中率等细节。 - **针对性优化**:根据分析结果调整代码逻辑,持续改进性能。 #### 三、性能分析与优化工具 **1. 性能分析工具** - **性能配置文件**:提供详尽的性能...

    高可用分布式架构设计与实践-内训方案.pdf

    架构的高可用性是指在系统发生故障时,能够保证业务不受影响或者影响最小化的能力。具体而言,高可用性的目标是确保系统在遇到单点或多个点故障的情况下仍然能够正常运行,提供稳定的服务。 - **CAP理论** CAP...

    高性能离线缓存存储引擎.pptx

    - **分布式架构**:采用分布式架构和一致性哈希算法,将数据均匀分配到多个节点上。 - **请求分流**:根据请求类型和负载情况动态分配请求到不同的节点上,优化资源的利用。 #### 四、键值存储与数据模型 **4.1 ...

    Ehcache 3(ehcache-clustered-3.8.1-kit.zip)

    1. **数据分布**:数据可以在集群中的多个节点上分布,通过一致性哈希算法确定数据存储位置,实现负载均衡。 2. **复制策略**:支持全副本复制或主-从复制,确保数据的高可用性。全副本复制意味着所有节点都持有...

    memcached面试26题和答案

    - **负载均衡器**: 使用一致性哈希算法平衡负载,最小化节点故障带来的影响。 **2. 特殊说明** - **数据分布**: 每台Memcached服务器仅存储部分数据,所有服务器的数据总和才构成完整的数据集。 - **一致性哈希...

    29道memcached面试题含答案(很全)

    通过一致性哈希算法,可以将数据均匀分布到各个节点,当某个节点故障时,其他节点能继续提供服务。 - 高可用性与容错性:即使有节点失败,系统仍能保持服务,确保数据的连续访问。 - 缓存策略:Memcached支持预热...

    Go-Golang无锁线程安全的HashMap为最快的读取访问进行了优化

    在多线程环境中,为了保证数据的一致性和正确性,通常需要引入锁机制,但这会增加额外的开销,降低并发性能。Go语言提供了通道(Channel)和原子操作(Atomic Operations)等原生并发工具,使得无锁实现成为可能。 ...

    20-Memcached面试题(24题).pdf

    Memcached 的分布式集群实现主要依靠一致性哈希算法,它将数据分散在多台服务器上,当节点增加或减少时,数据迁移的影响最小。程序端或负载均衡器都可以实现这一算法,确保数据的正确分发。 Memcached 的特点包括:...

    缓存优化在边缘计算中的应用.pptx

    - **基于预测的动态缓存管理**:利用机器学习算法预测未来的请求模式,提前预取和缓存数据,提高缓存命中率。 - **协作式动态缓存分配**:在多个边缘节点之间进行缓存资源的协作分配,共同优化缓存策略,提高整体...

    缓存竞争缓解机制在边缘计算中的应用.pptx

    综上所述,针对边缘计算场景下的缓存竞争问题,不仅可以从缓存替换算法本身进行优化,还可以探索新的缓存管理机制和技术手段,如分布式一致性协议、虚拟化技术等,来进一步减轻缓存竞争带来的负面影响,提高系统的...

    MySQL查询优化

    该算法通过将Memcached服务器和键值哈希到一个虚拟的环(continuum)上,然后顺时针查找第一个服务器节点,从而最小化了服务器变动对缓存命中率的影响。 在实际应用中,使用Memcached提高MySQL查询优化时,需要先...

    大数据环境下字符串指针的处理策略.pptx

    - **问题描述**:在分布式环境中,数据可能分布在不同的节点上,导致指针解引用需要跨节点访问,增加了延迟和开销。 - **解决方案**: - 使用全局唯一标识符(UUID)。 - 采用非引用计数的垃圾收集器。 ##### 5.2 ...

Global site tag (gtag.js) - Google Analytics