背景

一致性hash算法是为了解决分布式缓存数据变动和映射问题，某个机器坏了，分母的数量改变了，自然取于数就不行了

目的

提出一致性hash解决方案目的是：当服务器个数发生变动时候，尽量减少影响客户端到服务器的映射关系

3大步骤

算法构建一致性hash环

哈希环
在这里插入图片描述

我们之前是对机器（节点）数量进行取余，而现在一致性hash通过对2^32取模
我们把全量集设置成了分母,将整个哈希值空间组织成了一个虚拟的圆环，无论什么值都不会大过这个值

服务器ip节点映射

将集群中的每个ip节点映射到环上的某个位置
将每个服务器使用hash进行一个哈希，具体可以使用服务器的ip或者主机名作为关键字进行hash，这样每台机器就能确定的落在哈希环上的位置，假如有3个服务器节点n1,n2,n3，使用ip地址进行哈希后在环空间的位置如下

在这里插入图片描述

key落到服务器的落键规则

我们的每个key和服务器节点使用相同的hash函数，将该key落在环上
然后在哈希环上的key顺时针走，第一个遇到的服务器就是其应该定位到的服务器，并将该key存储在该服务器上

在这里插入图片描述

keyn6存储在noden3
keyn3存储在noden2
依次类推，存储在顺时针的第一个节点上

使用虚拟节点来解决hash不均匀问题

如果按照顺序延续，一个节点坏了，另一个节点承当前一个节点的数据，这样可能导致自身的负载上升，导致自己也挂掉了
在这里插入图片描述

为了引入了一个虚拟节点的概念
想象在环中有很多个“虚拟节点”，数据的存储会沿着环找到相对应的一个虚拟节点，而每个虚拟节点会关联到一个真实节点
在这里插入图片描述
图中A1 A2,B1,B2,C1,C2...都是虚拟节点，A1,A2的数据存储在机器A上，机器B负载B1,B2的数据 …，这些虚拟节点的数量很多，分布均匀，所以不会造成一个"雪崩"现象

优点

容错性

如果上图中的n2节点挂掉了，那么keyn3按照顺时针旋转应该到达的就是n1节点
容错性很好,这样其他机器也不会受到影响，如果n2挂了这些数据就会转移到n1进行存储

扩展性

如果机器增加，在n2和n3之间再加上一个n4,那么keyn3把数据顺延到n4即可（只影响hash环中的相邻节点)
不会导致hash取余全部数据重新洗牌

缺点

容易头重脚轻，可能会导致多个key被缓存到了一台机器上,数据分配不均匀

如果按照顺序延续，一个节点坏了，另一个节点承当前一个节点的数据，这样可能导致自身的负载上升，导致自己也挂掉了

代码

/*step1：插入存储节点，也就是虚拟节点（上图中A1,A2，B1,B2）这里需要记录两个信息1. 每个虚拟节点对应的哪个真实节点2. 哈希环上每个哈希值对应哪个虚拟节点step2:给每个数据分配存储的节点，先通过哈希函数计算出hash值，然后可以找到对应的虚拟节点，再映射到正式的节点上*/#include 
#include 
#include 
#include 
#include 
using namespace std;class ConsistentHash
{
private:map serverNodes; // 虚拟节点，key是虚拟节点的哈希值，value就是机器的真实ipset physicalNodes;         // 真实的节点IPint virtualNOdeNum;                // 每个机器关联的虚拟节点个数
public:ConsistentHash(const int _virtualNOdeNum): virtualNOdeNum(_virtualNOdeNum){physicalNodes.insert("192.168.1.101"); // 给他初始化一些物理机器physicalNodes.insert("192.168.1.102");physicalNodes.insert("192.168.1.103");physicalNodes.insert("192.168.1.104");}~ConsistentHash(){serverNodes.clear();}// 32位的Flower-Noll-Vo哈希算法,根据key获得一个hash值static uint32_t FNVHash(string key)//也可以放在类外面就行{const int p = 16777619;uint32_t hash = 2166136261;for (int idx = 0; idx < key.size(); idx++){hash = (hash ^ key[idx]) * p;}hash += hash << 13;hash ^= hash >> 7;hash += hash << 3;hash ^= hash >> 17;hash += hash << 5;if (hash < 0)hash = -hash;return hash;}void initialize() // 对这里的一致性hash函数进行一个初始化{for (auto &ip : physicalNodes){for (int j = 0; j < virtualNOdeNum; j++) // 这里每个物理机关联上virtualnode个虚拟节点{// stringstream是C++的一个流对象，方便的读写字符串和数字等各个数据类型<<就是流输入，>>就是流输出stringstream nodekey;nodekey << ip << "#" << j;uint32_t partition = FNVHash(nodekey.str());serverNodes[partition] = ip; // 这里我们先绑定好}}}// 插入一个物理节点时，同时插入其关联的所有虚拟节点void AddNewPhysicalNode(const string nodeip){// 如果该物理机器不存在就可以添加if (physicalNodes.find(nodeip) == physicalNodes.end()){physicalNodes.insert(nodeip);for (int j = 0; j < virtualNOdeNum; j++){stringstream nodekey;nodekey << nodeip << "#" << j;uint32_t partition = FNVHash(nodekey.str());serverNodes[partition] = nodeip; // 这里把新的物理节点也要生成相应的虚拟节点，进行映射}}// 如果该物理机器存在，就需要进行添加}// 删除一个物理节点,同时他对应的虚拟节点也要删除void DeletePhysicalNode(const string nodeip){// 如果该物理机器存在，才能进行删除if (physicalNodes.find(nodeip) != physicalNodes.end()){for (int j = 0; j < virtualNOdeNum; j++){stringstream nodekey;nodekey << nodeip << "#" << j;uint32_t partition = FNVHash(nodekey.str());auto it = serverNodes.find(partition); // 找到了对应的虚拟节点的hash值的keyif (it != serverNodes.end()){serverNodes.erase(it);}}physicalNodes.erase(nodeip); // 这里直接再实际物理机上删除对应的机器}//如果该机器不存在就不能够进行删除}// 根据某个数据key，获得对应的虚拟节点的ip再获得对应的物理节点的ipstring GetserverIndex(const string key){uint32_t partition = FNVHash(key);// lower_bound时一个获得>=target的第一个元素// vector v{ 1, 3, 5, 7, 9 };// int target = 6;// auto it = std::lower_bound(v.begin(), v.end(), target);，这个地方返回的就是7,7是>=6的第一个元素// 所以这个地方因为顺时针往下走，所以就能够获得这个key对应的最接近的一个虚拟节点auto it = serverNodes.lower_bound(partition);// 言环顺时针找到第一个大于等于partition的虚拟节点if (it == serverNodes.end()) // 这个地方发现没有找到一个比该节点大的值{if (serverNodes.empty()) // 一个节点都没有{cout << "no available servers node" << endl;}return serverNodes.begin()->second; // 所以就把第一个节点给行了，因为这是一个环}return it->second;}// 给区间[objmin,objmax] 上的数据寻找合适的存储节点void statisticpref(string label, int objmin, int objmax){map cnt;for (int i = objmin; i <= objmax; i++){string nodeip = GetserverIndex(to_string(i));cnt[nodeip]++;}int total = objmax - objmin + 1;cout << "----" << label << "-----" << endl;for (auto &p : cnt){cout << "nodeip:" << p.first << " rate: " << 100 * p.second / (total * 1.0) << "%" << endl;}}//获得在线机器的个数size_t size(){return physicalNodes.size();}//判断在线机器是否有机器bool empty(){return physicalNodes.empty();}
};

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：JS逆向系列之猿人学爬虫第3题-访问逻辑-推心置腹

下一篇：2023年3月20日学习总结

一致性hash

文章目录

背景

目的

3大步骤

算法构建一致性hash环

服务器ip节点映射

key落到服务器的落键规则

使用虚拟节点来解决hash不均匀问题

优点

缺点

代码

相关内容

热门资讯