[Consistent Hashing] Go 实现基于虚拟节点的一致性哈希

一致性哈希 (Consistent Hashing) 算法, 主要应用在分布式系统中, 尤其是缓存, 解决负载均衡、热点、数据倾斜等问题.

将服务器节点 Node, 映射到一个较长的环上, 当查找数据时, 在环上顺时针查找, 该数据的 Key 所临近的服务器节点 Node, 最后再到服务器节点上去查找源数据.

1.取一个环, 作为哈希环.

长度一般是 2 的 32 次方 ( 4,294,967,296 ), 即 int32 的数值范围.

2.定一个哈希规则, 哈希结果的值范围在要跟哈希环的长度适配. 比如环长度为 2 的 32 次方, 则选用 CRC32 规则 Redis-Cluster Slots 的个数是 2 的 14 次方 (16384), 使用的规则是 CRC16 .

3.使用哈希规则对服务器节点 Node 进行哈希运算. 比如对服务器节点的 IP、HostName 等, 进行 CRC32 哈希运算.

4.将哈希运算的结果, 对哈希环的长度进行取余运算, 然后将余数映射到哈希环上.

5.对查找数据的 Key 进行 CRC32 哈希运算, 并对哈希环的长度进行哈希取余操作, 然后 顺时针 查找临近的 Node. (Key 比如 user 表的 user id)

如果节点个数比较少, 极端假设有两个节点, 一个节点 A 的 Hash 值为 0, 另一个节点 B 的 Hash 值为 10, 而一般哈希环的长度一般都相当长 (如 int32 范围), 导致的结果是 A 负载 11 ~ int32最大数值, 而仅仅负载 1~10.

如果新增一个节点 C, Hash 值为 3,000,000,000 , 那么 11 ~ 3,000,000,000 对应的这么大量的数据, 会从 A 迁移到 C 来.

新增的节点, 只为一个节点分摊压力, 并不是都为其他节点分摊一部分的负载压力.

节点越多, 分布越均匀.

负载越近似均衡, 数据倾斜越少.

如果没有实际节点, 那就通过新增虚拟节点.

于是, 基于虚拟节点的一致性哈希诞生.

根据迪米勒原则, 抽象以下接口

真实节点 Node, 作为值类型.

虚拟节点, 将用 map 来与真实节点的关联, RingIndexs 切片的索引就是虚拟节点的 ID.

基于虚拟节点的一致性哈希.

因为算法 hash 范围正是环的长度范围, 所以不对 math.MaxInt32 取余.

快排算法, 时间复杂度: O(NlogN) , N 为虚拟节点的个数

在新增节点时, 自动创建虚拟节点, 在删除节点时, 将节点对应的所有虚拟节点进行拔除.

并在修改节点后, 重新对所有虚拟节点的 Hash 值进行排序.

使用折半算法, 对节点进行查找

主要验证获取的节点是否正确, 以及对新增和删除节点的操作是否正确.

排序、新增节点、删除节点、获取节点, 貌似都 Okay.

理解 Consistent Hashing

无服务器架构（Serverless）是一种将应用与基础设施彻底分离的架构理念，开发人员无需关心基础设施的运维工作，只需专注于应用逻辑的开发，真正实现了弹性伸缩与按需付费。当前各大云服务商和头部互联网企业的内部业务 Serverless 化升级改造已经开始小范围试水；中小企业基于 Serverless 的业务应用也初见端倪，已然可见初具规模的企业级应用，未来可期。Serverless 生态已初具规模，可以预见，Serverless 将成为下一代云计算服务形态的趋势。

在此背景下， 云函数（SCF）、弹性微服务（TEM）和弹性容器服务（EKS）联合其他相关产品，在 2021 年 Serverless 平台技术能力评估中，共同获得国内首批 Serverless 平台技术能力最高先进级认证。

今年 7 月，在中国信息通信研究院、中国通信标准化协会联合主办的 “2021 可信云大会” 上， 腾讯云拿下了 5 项大奖和 10 项可信云认证，在云存储、Serverless 等各细分领域评测中，获得 54 项可信云认证，数量位居中国云厂商第一 。腾讯云云函数（SCF）、弹性微服务（TEM）和弹性容器服务（EKS）深度参与了此次 Serverless 标准制定和实施过程，腾讯云的 Serverless 产品矩阵所提供的平台技术能力也得到了同行的一致认可。

通过本次 Serverless 标准，为大家带来以下几方面关于 Serverless 发展趋势的解读：

当我们把 Serverless 理念和这些产品结合时，Serverless 化的文件系统（CFS）、数据库（TDSQL-C）、网关（API Gatgeway）和中间件（TDMQ）等可大幅度降低 Serverless 应用的开发和运维成本，让开发者真正聚焦于业务的核心能力，把核心的研发力量和IT投资最大化企业的核心差异化竞争力。通过最终的需求驱动，我们可以预见到，各个云服务产品的 Serverless 化或许是未来云计算发展的必经之路。

过去场景化的 FaaS 是 Serverless 较为主流的应用形态，落地案例也以轻量级的站点、SSR 和云上“云上粘合剂”居多。在本次 Serverless 标准制定过程中，对于如何评估企业实际的 Serverless 落地形式大家展开了丰富的讨论和交流。我们认为 Serverless 的应用形态可以是 FaaS、微服务甚至是单体应用；运行环境可以是原生的运行时，也可以是容器镜像；具体落地时，可以用来对外提供 API 接口，也可以用来运行 音视频转码、直播推流 等计算任务，还可以用来完成 站点压测、AI 推理 等任务。

但是现有存量系统的 Serverless 化无法一蹴而就，这是一个不断设计和矫正的过程，应用 Serverless 化也需要经历迁移、优化和云原生架构改造的几个阶段，不同阶段之间需要有一个较为平滑的切换过程，借助于云函数的 Web Function 的功能可以让迁移过程更加平滑，只有实际负载运行在 Serverless 上之后，才能基于生产环境的实际运行结果、采集定量的指标持续进行 Serverless 应用的优化和云原生改造，进一步发挥出 Serverless 的价值。

当构建应用所依赖的服务逐渐向云上迁移的时候，开发环境也进一步“云”化，和本地开发相比也面临一些新的挑战，比如代码生效时间、本地测试、远程调试和离线开发等等，这些都是影响开发者效率的关键环节。在本次的 「Serverless 平台技术能力」标准中，单独把对于工具链的支持作为衡量 Serverless 平台技术能力的重要维度之一。一个成熟的 Serverless 开发者平台需要能够提供比较友好的IDE支持，让开发者使用熟悉的开发工具进行 Serverless 应用的开发，降低开发者的切换成本；除此之外从本地或者远程测试的时候，需要有良好的工具支持，可以方便地发起调用，触发应用执行并快速返回结果，当结果不符合预期的时候也需要有一系列监控、日志等排障手段帮助开发者快速定位问题。

作为 Serverless 社区最流行的一站式开发者工具， Serverless Framework 拥有百万级别的活跃应用程序以及 50000+ 的日下载量。Serverless Framework 早在 2019 年就已经和腾讯达成了大中华区独家的战略合作，和腾讯云的云函数等 Serverless 产品深度集成，同时社区也有大量开箱即用的插件和模板，帮助开发者快速上手 Serverless 应用开发。除此之外，云开发也是国内最大的微信小程序应用开发平台， 四川天府 健康 通、深圳机场智慧航旅服务等小程序应用都是运行在腾讯云的 Serverless 平台之上。

云函数（Serverless Cloud Function，SCF）是腾讯云为企业和开发者们提供的无服务器执行环境，帮助您在无需购买和管理服务器的情况下运行代码。只需编写核心代码并设置代码运行的条件，即可在腾讯云基础设施上弹性、安全地运行代码。

只需简单修改监听端口，即可将目前流行的 Node.js 框架直接部署上云，享受 Serverless 技术带来的免运维、低成本、按需扩缩容的众多优势。

突破传统 FaaS 形态产品的执行时长的限制， 首家支持运行长达 24 小时的长时任务的 FaaS 产品 ，支持体积较大的音视频文件处理、直播推流、数据分析等多种场景。

业界首发支持分配 120GB(122,880MB) 大内存环境，可以更加轻松地处理具有更高内存或更密集计算需求的工作负载，如音视频处理、大数据分析等。

通过 Web Function、容器化镜像等方式平滑把应用迁移至云函数之上，支持托管 H5 页面、API、SSR 应用、小程序等多种形态的应用形式，缩短研发周期，快速收集市场反馈从而加速产品迭代。

无需运维虚拟机或者其他计算集群，利用云函数提供的极致弹性、按量计费等特性，高效、低成本地进行音视频的录制、转码、混流、剪辑和推流等操作，让企业聚焦于音视频处理逻辑本身，从而不断提升内容质量，优化视听体验。

可以通过触发器连接其他的云服务，如对象存储（COS）、日志服务（CLS）等其他服务，当上游的数据发送变化的时候自动触发函数执行计算逻辑，典型的使用场景包括：CDN 刷新和预热、中间件消息转存、文件备份等。

支持定时、消息队列等多种形式触发函数执行输出处理逻辑，进行数据采集、数据清洗、ETL 等数据处理操作，处理之后的数据可以直接存储至下游的数据仓库、业务数据库或者 BI 分析系统等。

腾讯云弹性微服务 (Tencent Cloud Elastic Microservice, TEM) 是面向微服务应用的 Serverless PaaS 平台，实现 Serverless 与微服务的完美结合，应用零改造上云，按量付费，免运维，提供开箱即用的微服务应用托管服务。

弹性微服务拥抱开源，支持 Spring Cloud 等微服务应用零改造上云，提供应用运行托管、服务注册发现、微服务治理、多维度监控等能力，满足 Consul、Eureka 等多种注册中心需求。弹性微服务帮助您创建和管理云资源，并提供秒级弹性伸缩，您可按需使用、按量付费，极大降低资源和运维成本，让您充分聚焦企业核心业务逻辑，助力业务成功。

弹性微服务通过应用托管、服务注册与发现、服务治理、调用链与多维度监控等功能力，为客户提供开箱即用的微服务解决方案。帮助企业用户快速构建微服务应用，大幅提升运维效率，降低服务治理的复杂度与技术门槛，让企业聚焦核心业务本身，助力客户成功。

在业务呈现潮汐特性、突发流量等场景下，容易出现访问响应超时、错误率提升等问题。腾讯云弹性微服务提供秒级弹性伸缩能力，帮助企业客户轻松应对流量高峰。

腾讯云弹性微服务帮助客户持续集成与交付，实现微服务应用快速迭代。从代码开发到应用交付，弹性微服务提供 IDE 插件、灰度发布等多发布策略的能力，助力企业客户快速验证业务价值。

弹性容器服务 EKS（Elastic Kubernetes Service）是腾讯云容器团队的推出的 Serverless 化 Kubernetes 服务 ，无须用户购买节点，直接部署工作负载。其完全兼容原生 Kubernetes，支持使用原生方式购买及管理资源，按照容器真实使用的资源量计费。

无论是自建 K8s 集群，还是腾讯云 TKE 托管集群，只要网络互通，即可通过部署 EKS 虚拟节点的方式，几乎无成本扩展集群资源池。在扩容 Pod 时可自动或手动快速将 Pod 调度到「虚拟节点」对应的腾讯云公有云资源上。

相比传统的通过扩缩服务器去调度资源（流程重，耗时久），虚拟节点提供一种直接调度 Pod 的能力，可以更快、更高效的弹性。

使用弹性容器服务 EKS 来运行微服务，免除用户对计算节点的运维工作。服务可根据负载情况自动伸缩，使用最合理的资源量来承载应用，降低资源使用成本。

使用弹性容器服务 EKS 运行离线计算任务，只需准备容器镜像，即可快速部署任务负载。另外，弹性容器服务 EKS 仅收取任务真实运行时间所使用算力的费用，任务结束 Pod 自动释放即结束计费。

弹性容器服务 EKS 支持使用 CPU、GPU 以及 vGPU 来运行在线推理服务，丰富的资源规格和弹性伸缩的负载，使运行服务更高效、更经济。

立即体验腾讯云 Serverless Demo，领取 Serverless 新用户礼包 腾讯云 Serverless 新手体验

先说一下hash算法，hash算法是将任意长度的二进制值映射为固定长度的二进制值。

在分布式系统中， 可以通过该算法计算哈希值

Hash是一个字符串到正整数的hash映射函数， key是键值（例如服务器ip地址/唯一主机名）， n是键的个数。每当改变服务器数量时， 都会使hash值改变，容错性和扩展性会极差。

一致性hash算法将2的32次方的hash空间组成一个首尾相连的圆环，然后把服务器ip地址/唯一主机名作为键进行hash得到一个唯一的hash值，该值就是该服务器在圆环上的位置。数据也通过hash得到一个唯一的hash值，然后把数据放进最近的服务器中（顺时针），如下图。

假如服务器C宕机了， 数据B就会被放在服务器A，其他服务器和数据都不会受到影响。

假如新增服务器D， 数据C会放在服务器D中，其他的都不变。

在服务器节点太少时， 会有数据倾斜问题，即大部分数据在一个节点上。

为了解决这个问题，引入了虚拟节点。可以在ip地址/唯一主机名后面加上编号，使一台服务器算出多个hash值，在hash环上增加同一服务器节点，该节点就是虚拟节点；在服务器节点较少时也能实现数据均匀分布。

---