驻马店市网站建设_网站建设公司_数据统计_seo优化

一、普通 hash 算法 (取模算法)：

在了解一致性哈希算法之前，我们先了解一下缓存中的一个应用场景，了解了这个应用场景之后，再来理解一致性哈希算法，就容易多了，也更能体现出一致性哈希算法的优点，那么，我们先来描述一下这个经典的分布式缓存的应用场景。

1、普通 hash算法 与 使用场景描述：

假设我们有三台缓存服务器，用于缓存图片，我们为这三台缓存服务器编号为 0号、1号、2号，现在有3万张图片需要缓存，我们希望这些图片被均匀的缓存到这3台服务器上，以便它们能够分摊缓存的压力。也就是说，我们希望每台服务器能够缓存1万张左右的图片，那么我们应该怎样做呢？常见的做法是对缓存项的键进行哈希，将hash后的结果对缓存服务器的数量进行取模操作，通过取模后的结果，决定缓存项将会缓存在哪一台服务器上

我们举例说明，以刚才描述的场景为例，假设图片名称是不重复的，那我们就可以使用图片名称作为访问图片的key，使用如下公式，计算出图片应该存放在哪台服务器上。

hash（图片名称）% N

当我们对同一个图片名称做相同的哈希计算时，得出的结果应该是不变的，

如果我们有3台服务器，使用哈希后的结果对3求余，那么余数一定是0、1或者2；如果求余的结果为0， 就把当前图片缓存在0号服务器上，如果余数为1，就缓存在1号服务器上，以此类推；

同理，当我们访问任意图片时，只要再次对图片名称进行上述运算，即可得出图片应该存放在哪一台缓存服务器上，我们只要在这一台服务器上查找图片即可，如果图片在对应的服务器上不存在，则证明对应的图片没有被缓存，也不用再去遍历其他缓存服务器了，通过这样的方法，即可将3万张图片随机的分布到3台缓存服务器上了，而且下次访问某张图片时，直接能够判断出该图片应该存在于哪台缓存服务器上，我们暂时称上述算法为 HASH 算法或者取模算法，取模算法的过程可以用下图表示：

2、普通 hash 算法的缺陷：

上述HASH算法时，会出现一些缺陷：如果服务器已经不能满足缓存需求，就需要增加服务器数量，假设我们增加了一台缓存服务器，此时如果仍然使用上述方法对同一张图片进行缓存，那么这张图片所在的服务器编号必定与原来3台服务器时所在的服务器编号不同，因为除数由3变为了4，最终导致所有缓存的位置都要发生改变，也就是说，当服务器数量发生改变时，所有缓存在一定时间内是失效的，当应用无法从缓存中获取数据时，则会向后端服务器请求数据；同理，假设突然有一台缓存服务器出现了故障，那么我们则需要将故障机器移除，那么缓存服务器数量从3台变为2台，同样会导致大量缓存在同一时间失效，造成了缓存的雪崩，后端服务器将会承受巨大的压力，整个系统很有可能被压垮。为了解决这种情况，就有了一致性哈希算法。

二、一致性哈希算法：

1、什么是一致性 hash 算法：

一致性哈希算法也是使用取模的方法，但是取模算法是对服务器的数量进行取模，而一致性哈希算法是对 2^32 取模，具体步骤如下：

步骤一：一致性哈希算法将整个哈希值空间按照顺时针方向组织成一个虚拟的圆环，称为 Hash 环；
步骤二：接着将各个服务器使用 Hash 函数进行哈希，具体可以选择服务器的IP或主机名作为关键字进行哈希，从而确定每台机器在哈希环上的位置
步骤三：最后使用算法定位数据访问到相应服务器：将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针寻找，第一台遇到的服务器就是其应该定位到的服务器
下面我们使用具体案例说明一下一致性哈希算法的具体流程：

（1）步骤一：哈希环的组织：

我们将 2^32 想象成一个圆，像钟表一样，钟表的圆可以理解成由60个点组成的圆，而此处我们把这个圆想象成由2^32个点组成的圆，示意图如下：

圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32-1,也就是说0点左侧的第一个点代表2^32-1，我们把这个由 2^32 个点组成的圆环称为hash环。

（2）步骤二：确定服务器在哈希环的位置：

哈希算法：hash（服务器的IP） % 2^32

上述公式的计算结果一定是 0 到 2^32-1 之间的整数，那么上图中的 hash 环上必定有一个点与这个整数对应，所以我们可以使用这个整数代表服务器，也就是服务器就可以映射到这个环上，假设我们有 ABC 三台服务器，那么它们在哈希环上的示意图如下：

（3）步骤三：将数据映射到哈希环上：

我们还是使用图片的名称作为 key，所以我们使用下面算法将图片映射在哈希环上：hash（图片名称） % 2^32，假设我们有4张图片，映射后的示意图如下，其中橘黄色的点表示图片：

那么，怎么算出上图中的图片应该被缓存到哪一台服务上面呢？我们只要从图片的位置开始，沿顺时针方向遇到的第一个服务器就是图片存放的服务器了。最终，1号、2号图片将会被缓存到服务器A上，3号图片将会被缓存到服务器B上，4号图片将会被缓存到服务器C上。

2、一致性 hash 算法的优点：

前面提到，如果简单对服务器数量进行取模，那么当服务器数量发生变化时，会产生缓存的雪崩，从而很有可能导致系统崩溃，而使用一致性哈希算法就可以很好的解决这个问题，

因为一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，只有部分缓存会失效，不至于将所有压力都在同一时间集中到后端服务器上，具有较好的容错性和可扩展性。

假设服务器B出现了故障，需要将服务器B移除，那么移除前后的示意图如下图所示：

在服务器B未移除时，图片3应该被缓存到服务器B中，可是当服务器B移除以后，按照之前描述的一致性哈希算法的规则，图片3应该被缓存到服务器C中，因为从图片3的位置出发，沿顺时针方向遇到的第一个缓存服务器节点就是服务器C，也就是说，如果服务器B出现故障被移除时，图片3的缓存位置会发生改变，但是，图片4仍然会被缓存到服务器C中，图片1与图片2仍然会被缓存到服务器A中，这与服务器B移除之前并没有任何区别，这就是一致性哈希算法的优点。

3、hash 环的倾斜与虚拟节点：

一致性哈希算法在服务节点太少的情况下，容易因为节点分部不均匀而造成数据倾斜问题，也就是被缓存的对象大部分集中缓存在某一台服务器上，从而出现数据分布不均匀的情况，这种情况就称为 hash 环的倾斜。

如下图所示：

hash 环的倾斜在极端情况下，仍然有可能引起系统的崩溃，为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点，一个实际物理节点可以对应多个虚拟节点，虚拟节点越多，hash环上的节点就越多，缓存被均匀分布的概率就越大，hash环倾斜所带来的影响就越小，同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射。具体做法可以在服务器ip或主机名的后面增加编号来实现，加入虚拟节点以后的hash环如下：

实现 一致性哈希

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdint.h> #include <assert.h> // 哈希环的范围（通常为2^32） #define HASH_RING_SIZE 4294967296U // 2^32 #define INITIAL_CAPACITY 16 // 环上的节点 typedef struct RingNode { uint32_t hash_value; // 在环上的位置 char* server_name; // 服务器名称或标识 void* data; // 节点关联的数据 struct RingNode* next; // 链表下一个节点 } RingNode; // 一致性哈希环 typedef struct ConsistentHashRing { RingNode** nodes; // 节点数组（按hash_value排序） int node_count; // 当前节点数量 int capacity; // 数组容量 uint32_t(*hash_func)(const char*); // 哈希函数 } ConsistentHashRing; // 哈希函数选择 // 通用的字符串哈希函数（MurmurHash3简化版） uint32_t murmur_hash(const char* key) { const uint32_t c1 = 0xcc9e2d51; const uint32_t c2 = 0x1b873593; const uint32_t seed = 0x9747b28c; uint32_t h = seed; const uint8_t* data = (const uint8_t*)key; size_t len = strlen(key); // 处理4字节块 const int nblocks = len / 4; const uint32_t* blocks = (const uint32_t*)data; for (int i = 0; i < nblocks; i++) { uint32_t k = blocks[i]; k *= c1; k = (k << 15) | (k >> 17); // ROTL32(k, 15) k *= c2; h ^= k; h = (h << 13) | (h >> 19); // ROTL32(h, 13) h = h * 5 + 0xe6546b64; } // 处理剩余字节 const uint8_t* tail = data + nblocks * 4; uint32_t k1 = 0; switch (len & 3) { case 3: k1 ^= tail[2] << 16; case 2: k1 ^= tail[1] << 8; case 1: k1 ^= tail[0]; k1 *= c1; k1 = (k1 << 15) | (k1 >> 17); k1 *= c2; h ^= k1; } // 最终混合 h ^= len; h ^= h >> 16; h *= 0x85ebca6b; h ^= h >> 13; h *= 0xc2b2ae35; h ^= h >> 16; return h; } // 简单的FNV哈希（备用） uint32_t fnv_hash(const char* str) { const uint32_t FNV_prime = 16777619U; const uint32_t offset_basis = 2166136261U; uint32_t hash = offset_basis; while (*str) { hash ^= (uint32_t)(*str++); hash *= FNV_prime; } return hash; } //创建哈希环 // 创建一致性哈希环 ConsistentHashRing * create_consistent_hash_ring( uint32_t(*hash_func)(const char*)) { ConsistentHashRing* ring = (ConsistentHashRing*)malloc(sizeof(ConsistentHashRing)); if (!ring) return NULL; ring->nodes = (RingNode**)calloc(INITIAL_CAPACITY, sizeof(RingNode*)); if (!ring->nodes) { free(ring); return NULL; } ring->node_count = 0; ring->capacity = INITIAL_CAPACITY; ring->hash_func = hash_func ? hash_func : murmur_hash; return ring; } //添加节点 // 添加节点到哈希环 int add_node_to_ring(ConsistentHashRing * ring, const char* server_name) { assert(ring && server_name); // 1. 计算节点的哈希值 uint32_t hash = ring->hash_func(server_name); hash = hash % HASH_RING_SIZE; // 确保在环范围内 // 2. 检查节点是否已存在 for (int i = 0; i < ring->node_count; i++) { if (ring->nodes[i]->hash_value == hash) { printf("节点 %s 已存在于环上 (hash: %u)\n", server_name, hash); return 0; } } // 3. 创建新节点 RingNode* new_node = (RingNode*)malloc(sizeof(RingNode)); if (!new_node) return 0; new_node->hash_value = hash; new_node->server_name = strdup(server_name); new_node->data = NULL; new_node->next = NULL; // 4. 扩展数组容量（如果需要） if (ring->node_count >= ring->capacity) { int new_capacity = ring->capacity * 2; RingNode** new_array = (RingNode**)realloc(ring->nodes, new_capacity * sizeof(RingNode*)); if (!new_array) { free(new_node->server_name); free(new_node); return 0; } ring->nodes = new_array; ring->capacity = new_capacity; } // 5. 找到插入位置（保持有序） int insert_pos = 0; while (insert_pos < ring->node_count && ring->nodes[insert_pos]->hash_value < hash) { insert_pos++; } // 6. 移动元素，插入新节点 for (int i = ring->node_count; i > insert_pos; i--) { ring->nodes[i] = ring->nodes[i - 1]; } ring->nodes[insert_pos] = new_node; ring->node_count++; printf("添加节点: %s (hash: %u, 位置: %d)\n", server_name, hash, insert_pos); return 1; } // 查找数据位置 // 查找数据应该存储的节点 RingNode * find_node_for_key(ConsistentHashRing * ring, const char* key) { if (!ring || !key || ring->node_count == 0) { return NULL; } // 1. 计算数据的哈希值 uint32_t key_hash = ring->hash_func(key); key_hash = key_hash % HASH_RING_SIZE; printf("查找键: %s (hash: %u)\n", key, key_hash); // 2. 二分查找第一个大于等于key_hash的节点 int left = 0; int right = ring->node_count - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (ring->nodes[mid]->hash_value >= key_hash) { result = mid; right = mid - 1; // 继续向左查找更小的 } else { left = mid + 1; } } // 3. 处理查找结果 if (result != -1) { // 找到大于等于的节点 return ring->nodes[result]; } else { // 绕回环的起点（第一个节点） return ring->nodes[0]; } } // 删除节点 // 从哈希环删除节点 int remove_node_from_ring(ConsistentHashRing * ring, const char* server_name) { if (!ring || !server_name) return 0; // 1. 查找节点 int node_index = -1; for (int i = 0; i < ring->node_count; i++) { if (strcmp(ring->nodes[i]->server_name, server_name) == 0) { node_index = i; break; } } if (node_index == -1) { printf("节点 %s 不存在\n", server_name); return 0; } // 2. 记录被删除的节点信息 RingNode* removed_node = ring->nodes[node_index]; printf("删除节点: %s (hash: %u)\n", removed_node->server_name, removed_node->hash_value); // 3. 确定需要迁移的数据范围 // 被删除节点负责的数据需要迁移到顺时针下一个节点 uint32_t start_hash = (node_index > 0) ? ring->nodes[node_index - 1]->hash_value : ring->nodes[ring->node_count - 1]->hash_value; uint32_t end_hash = removed_node->hash_value; printf("需要迁移的数据范围: (%u, %u]\n", start_hash, end_hash); // 4. 从数组中移除节点 for (int i = node_index; i < ring->node_count - 1; i++) { ring->nodes[i] = ring->nodes[i + 1]; } ring->node_count--; // 5. 清理节点资源 free(removed_node->server_name); free(removed_node); return 1; } // 打印哈希环 // 打印哈希环的状态 void print_hash_ring(ConsistentHashRing * ring) { if (!ring) { printf("哈希环为空指针\n"); return; } printf("\n========== 一致性哈希环状态 ==========\n"); printf("节点数量: %d\n", ring->node_count); printf("环大小: 0 ~ %u (2^32)\n", HASH_RING_SIZE - 1); printf("--------------------------------------\n"); if (ring->node_count == 0) { printf("环为空，无节点\n"); printf("======================================\n\n"); return; } // 打印所有节点及其负责的范围 for (int i = 0; i < ring->node_count; i++) { RingNode* current = ring->nodes[i]; RingNode* previous = (i > 0) ? ring->nodes[i - 1] : ring->nodes[ring->node_count - 1]; printf("节点[%2d]: %s\n", i, current->server_name); printf(" 哈希值: %u\n", current->hash_value); printf(" 负责范围: (%u, %u]\n", previous->hash_value, current->hash_value); printf(" 范围大小: %u\n", (current->hash_value - previous->hash_value + HASH_RING_SIZE) % HASH_RING_SIZE); printf(" 相对位置: %.2f%%\n", (float)current->hash_value / HASH_RING_SIZE * 100); if (i < ring->node_count - 1) { printf(" --------------------\n"); } } printf("======================================\n\n"); }

实现虚拟节点

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdint.h> #include <assert.h> // 物理节点 typedef struct PhysicalNode { char* server_name; // 服务器名称 int weight; // 权重（性能因子） int virtual_node_count; // 虚拟节点数量 uint32_t* virtual_hashes; // 虚拟节点哈希值数组 int data_count; // 存储的数据量 double load_factor; // 当前负载 } PhysicalNode; // 虚拟节点 typedef struct VirtualNode { uint32_t hash_value; // 在环上的位置 PhysicalNode* physical_node; // 所属的物理节点 int replica_id; // 副本ID } VirtualNode; // 带虚拟节点的一致性哈希环 typedef struct VirtualConsistentHashRing { VirtualNode** virtual_nodes; // 虚拟节点数组（排序） int vnode_count; // 虚拟节点总数 PhysicalNode** physical_nodes; // 物理节点数组 int pnode_count; // 物理节点数量 int vnodes_per_physical; // 每个物理节点的默认虚拟节点数 } VirtualConsistentHashRing; //虚拟节点创建 // 为物理节点创建虚拟节点 void create_virtual_nodes_for_physical(PhysicalNode * pnode, int base_vnode_count, uint32_t(*hash_func)(const char*)) { // 根据权重计算虚拟节点数量 int vnode_count = base_vnode_count * pnode->weight; pnode->virtual_node_count = vnode_count; // 分配内存 pnode->virtual_hashes = (uint32_t*)malloc(vnode_count * sizeof(uint32_t)); printf("为物理节点 %s 创建 %d 个虚拟节点 (权重: %d)\n", pnode->server_name, vnode_count, pnode->weight); // 创建每个虚拟节点 for (int i = 0; i < vnode_count; i++) { // 生成虚拟节点标识：server_name + "#" + replica_id char vnode_id[256]; sprintf(vnode_id, "%s#%d", pnode->server_name, i); // 计算哈希值 uint32_t hash = hash_func(vnode_id) % HASH_RING_SIZE; pnode->virtual_hashes[i] = hash; printf(" 虚拟节点[%d]: %s (hash: %u)\n", i, vnode_id, hash); } } //带虚拟节点的数据定位 // 使用虚拟节点的数据定位 PhysicalNode * find_physical_node_for_key( VirtualConsistentHashRing * vring, const char* key) { if (!vring || !key || vring->vnode_count == 0) { return NULL; } // 1. 计算键的哈希值 uint32_t key_hash = murmur_hash(key) % HASH_RING_SIZE; // 2. 在虚拟节点环上查找 int left = 0; int right = vring->vnode_count - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (vring->virtual_nodes[mid]->hash_value >= key_hash) { result = mid; right = mid - 1; } else { left = mid + 1; } } // 3. 获取目标虚拟节点 VirtualNode* target_vnode = NULL; if (result != -1) { target_vnode = vring->virtual_nodes[result]; } else { target_vnode = vring->virtual_nodes[0]; // 绕回起点 } // 4. 返回对应的物理节点 return target_vnode->physical_node; } // 数据倾斜检测和修复 void detect_and_fix_data_skew(VirtualConsistentHashRing * vring) { printf("\n=== 数据倾斜检测 ===\n"); // 计算每个物理节点的数据量 for (int i = 0; i < vring->pnode_count; i++) { PhysicalNode* pnode = vring->physical_nodes[i]; printf("物理节点 %s: 数据量 = %d\n", pnode->server_name, pnode->data_count); } // 计算标准差 double mean = 0; for (int i = 0; i < vring->pnode_count; i++) { mean += vring->physical_nodes[i]->data_count; } mean /= vring->pnode_count; double variance = 0; for (int i = 0; i < vring->pnode_count; i++) { double diff = vring->physical_nodes[i]->data_count - mean; variance += diff * diff; } variance /= vring->pnode_count; double std_dev = sqrt(variance); printf("平均值: %.2f, 标准差: %.2f\n", mean, std_dev); // 如果标准差过大，调整虚拟节点 double cv = std_dev / mean; // 变异系数 if (cv > 0.3) { // 阈值30% printf("检测到数据倾斜（变异系数: %.2f），需要调整虚拟节点\n", cv); rebalance_virtual_nodes(vring); } } // 热点数据检测和迁移 typedef struct Hotspot { uint32_t hash_range_start; uint32_t hash_range_end; int access_count; int data_size; } Hotspot; void handle_hotspots(VirtualConsistentHashRing* vring) { // 1. 检测热点数据范围 Hotspot* hotspots = detect_hotspot_ranges(vring); // 2. 为热点数据创建副本 for (int i = 0; hotspots[i].access_count > 0; i++) { if (hotspots[i].access_count > HOTSPOT_THRESHOLD) { printf("发现热点数据范围: [%u, %u], 访问次数: %d\n", hotspots[i].hash_range_start, hotspots[i].hash_range_end, hotspots[i].access_count); // 创建副本到其他节点 replicate_hotspot_data(vring, &hotspots[i]); } } free(hotspots); } // 节点故障处理 void handle_node_failure(VirtualConsistentHashRing * vring, const char* failed_node_name) { printf("\n=== 处理节点故障: %s ===\n", failed_node_name); // 1. 找到故障节点 int failed_index = -1; PhysicalNode* failed_node = NULL; for (int i = 0; i < vring->pnode_count; i++) { if (strcmp(vring->physical_nodes[i]->server_name, failed_node_name) == 0) { failed_index = i; failed_node = vring->physical_nodes[i]; break; } } if (!failed_node) { printf("节点 %s 未找到\n", failed_node_name); return; } // 2. 将故障节点的数据迁移到备份节点 printf("故障节点数据量: %d\n", failed_node->data_count); printf("开始数据迁移...\n"); // 为每个虚拟节点找到顺时针下一个正常节点 for (int i = 0; i < failed_node->virtual_node_count; i++) { uint32_t vnode_hash = failed_node->virtual_hashes[i]; // 找到下一个正常的虚拟节点 VirtualNode* next_vnode = find_next_available_vnode(vring, vnode_hash); if (next_vnode) { printf("迁移虚拟节点 %u 的数据到 %s\n", vnode_hash, next_vnode->physical_node->server_name); // 实际的数据迁移操作 migrate_virtual_node_data(vring, vnode_hash, next_vnode); } } // 3. 标记节点为故障状态 printf("节点 %s 已标记为故障\n", failed_node_name); failed_node->status = NODE_STATUS_FAILED; }

一致性哈希的核心优势

1. 最小化数据迁移：节点变化时只影响相邻数据

2. 负载相对均衡：通过虚拟节点优化

3. 可扩展性：支持动态添加/删除节点

4. 容错性：节点故障时自动迁移数据

实现注意事项

1. 哈希函数选择：需要良好的均匀分布性

2. 虚拟节点数量：太少不均衡，太多开销大（通常100-200个）

3. 数据结构的优化：使用排序数组+二分查找

4. 并发控制：多线程环境需要加锁

实际应用建议

1. 监控负载：定期检查节点负载均衡情况

2. 动态调整：根据实际负载动态调整虚拟节点

3. 故障预案：实现自动故障