一致性hash算法原理及golang实现

社区订阅号:Golang语言社区 社区服务号:Golang技术社区 如有问题或建议,请公众号留言

概述

这里存在一种场景, 当一个缓存服务由多个服务器组共同提供时, key应该路由到哪一个服务.这里假如采用最通用的方式key%N(N为服务器数目), 这里乍一看没什么问题, 但是当服务器数目发送增加或减少时, 分配方式则变为key%(N+1)或key%(N-1).这里将会有大量的key失效迁移,如果后端key对应的是有状态的存储数据,那么毫无疑问,这种做法将导致服务器间大量的数据迁移,从而照成服务的不稳定. 为了解决类问题,一致性hash算法应运而生.

1. 一致性hash算法特点

在分布式缓存中, 一个好的hash算法应该要满足以下几个条件:

  • 均衡性(Balance)

均衡性主要指,通过算法分配, 集群中各节点应该要尽可能均衡.

  • 单调性(Monotonicity)

单调性主要指当集群发生变化时, 已经分配到老节点的key, 尽可能的任然分配到之前节点,以防止大量数据迁移, 这里一般的hash取模就很难满足这点,而一致性hash算法能够将发生迁移的key数量控制在较低的水平.

  • 分散性(Spread)

分散性主要针对同一个key, 当在不同客户端操作时,可能存在客户端获取到的缓存集群的数量不一致,从而导致将key映射到不同节点的问题,这会引发数据的不一致性.好的hash算法应该要尽可能避免分散性.

  • 负载(Load)

负载主要是针对一个缓存而言, 同一缓存有可能会被用户映射到不同的key上,从而导致该缓存的状态不一致.

从原理来看,一致性hash算法针对以上问题均有一个合理的解决.

2. 一致性hash详解

一致性hash的核心思想为将key作hash运算, 并按一定规律取整得出0-2^32-1之间的值, 环的大小为2^32,key计算出来的整数值则为key在hash环上的位置,如何将一个key,映射到一个节点, 这里分为两步.

第一步, 将服务的key按该hash算法计算,得到在服务在一致性hash环上的位置.

第二步, 将缓存的key,用同样的方法计算出hash环上的位置,按顺时针方向,找到第一个大于等于该hash环位置的服务key,从而得到该key需要分配的服务器。

如图, 各key根据hash算法分配到各节点,当某一节点失效实效时, 如NODE 2失败, 则NODE 2 上的key将分配到hash环上相邻的节点,而其他key所在位置不变。

虚拟节点提高均衡性

如上图可看到, 由于节点只有3个,存在某些节点所在位置周围有大量的hash点从而导致分配到这些节点到key要比其他节点多的多,这样会导致集群中各节点负载不均衡,为解决这个问题,引入虚拟节点, 即一个实节点对应多个虚拟节点。缓存的key作映射时,先找到对应的虚拟节点,再对应到实节点。如下图所示, 每个节点虚拟出两个虚拟节点,从而提高均衡性。

3. 一致性hash算法与其他算法对比

对于集群中缓存类数据key的节点分配问题,有这几种解决方法,简单的hash取模,槽映射,一致性hash。

  • hash取模

对于hash取模,均衡性没有什么问题,但是如果集群中新增一个节点时,将会有N/(N+1)的数据实效,当N值越大,失效率越高。这显然是不可接受的。

  • 槽映射

其思想是将key值做一定运算(如crc16, crc32,hash), 获得一个整数值,再将该值与固定的槽数取模(slots), 每个节点处理固定的slots。获取key所在的节点时,先要计算出key与槽的对应关系,再通过槽与节点的对应关系找到节点,这里每次新增节点时,只需要迁移一定槽对应的key即可,而不迁移的槽点key值则不会实效,这种方式将实效率降低到了 N/(N+1)。不过这种方式有个缺点就是所有节点都需要知道槽与节点对应关系,如果client端不保存槽与节点的对应关系的话,它需要实现重定向的逻辑。

  • 一致性hash

一致性hash如上文所言,其新增一个节点的实效率仅为N/(N+1),通过一致性hash最大程度的降低了实效率。同时相比于槽映射的方式,不需要引人槽来做中间对应,最大限度的简化了实现。

4. 基于golang的一致性hash算法实现

这里讲采用golang实现一致性hash,考虑到实际使用场景中,存在服务节点之间机器配置可能不一样,因此提供了基于节点权重进行虚拟节点再分配的逻辑,从而尽可能让权重高的节点多承担一些key,而权重低的节点少承担一些key,当然这里权重的计算也涉及到较多东西,代码见:

https://github.com/g4zhuj/hashring

5. 总结

本文分析了一致性性hash的原理,并与其它的分布式集群分配算法进行了对比,从分布式缓存的角度来说,两大出名的分布存储系统redis, memcached分别采用了槽映射,及一致性hash来实现,由于采用的算法不同,集群中节点变更时所触发的一系列动作也不尽相同,各有各的考虑。

版权申明:内容来源网络,版权归原创者所有。除非无法确认,我们都会标明作者及出处,如有侵权烦请告知,我们会立即删除并表示歉意。谢谢。

原文发布于微信公众号 - Golang语言社区(Golangweb)

原文发表时间:2018-05-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云计算教程系列

如何在Ubuntu 14.04第1部分上查询Prometheus

Prometheus是一个开源监控系统和时间序列数据库。Prometheus最重要的一个方面是它的多维数据模型以及随附的查询语言。此查询语言允许您对维度数据进行...

1220
来自专栏祝威廉

TensorFlowOnSpark 源码解析

这两天琢磨了下spark-deep-learning和spark-sklearn两个项目,但是感觉都不尽人如意。在training时,都需要把数据broadca...

1432
来自专栏人工智能LeadAI

用python编写一个本地论文管理器

介绍和引入 最近初学NLP相关的深度学习,下了很多论文,数量一多,发现论文管理是个问题。 首先论文数目一多,必须要按类别放到子文件夹下。但是某一篇论文,往往有...

3859
来自专栏PaddlePaddle

【进阶篇】安装与编译C-API预测库

编写|PaddlePaddle 排版|wangp 1 概述 使用 C-API 进行预测依赖于将 PaddlePaddle 核心代码编译成链接库,只需在编译时...

37610
来自专栏磨磨谈

预估ceph的迁移数据量

我们在进行 ceph 的 osd 的增加和减少的维护的时候,会碰到迁移数据,但是我们平时会怎么去回答关于迁移数据量的问题,一般来说,都是说很多,或者说根据环境来...

1312
来自专栏AI科技评论

开发 | GitHub项目推荐 : 用于对机器学习模型进行对抗性攻击、防御和基准测试的Python库

此资料库包含CleverHans的源代码,CleverHans是一个Python库,用于将机器学习系统中的漏洞与对抗性示例进行对比。 您可以在随附的博客上了解有...

1302
来自专栏AI研习社

GitHub项目推荐 | 用于对机器学习模型进行对抗性攻击、防御和基准测试的Python库:CleverHans 3.0.0

项目地址:https://github.com/tensorflow/cleverhans

4496
来自专栏TensorFlow从0到N

TensorFlow从0到1 - 18 - TensorFlow 1.3.0安装手记

《TensorFlow从0到1》写到现在,TensorFlow的版本也从当时的1.1.0迭代到了8月初发布的1.3.0。可以预见在未来很长一段时间里,它仍会持...

3566
来自专栏MixLab科技+设计实验室

建筑师编程指南之SketchUp插件开发 1

本系列指南使用的是 SketchUp2018 最新版本,基于 ruby 语言进行插件开发。 1 环境准备 先下载一个扩展,用于方便调试代码: https:/...

4106
来自专栏一枝花算不算浪漫

集群扩容的常规解决:一致性hash算法

1792

扫码关注云+社区

领取腾讯云代金券