Nginx学习 – ip_hash的hash算法

414次阅读

共计 2991 个字符，预计需要花费 8 分钟才能阅读完成。

直接看代码：

162 for (;;) {
163
164 for (i = 0; i < 3; i++) {
165 hash = (hash * 113 + iphp->addr[i]) % 6271; //iphp->addr[i]为 ip 的点分十进制法的第 i 段
166 }
167
168 p = hash % iphp->rrp.peers->number;
169
170 n = p / (8 * sizeof(uintptr_t));
171 m = (uintptr_t) 1 << p % (8 * sizeof(uintptr_t));
172
173 if (!(iphp->rrp.tried[n] & m)) {
174
175 ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
176 “get ip hash peer, hash: %ui %04XA“, p, m);
177
178 peer = &iphp->rrp.peers->peer[p];
179
180 /* ngx_lock_mutex(iphp->rrp.peers->mutex); */
181
182 if (!peer->down) {
183
184 if (peer->max_fails == 0 || peer->fails < peer->max_fails) {
185 break;
186 }
187
188 if (now – peer->accessed > peer->fail_timeout) {
189 peer->fails = 0;
190 break;
191 }
192 }
193
194 iphp->rrp.tried[n] |= m;
195
196 /* ngx_unlock_mutex(iphp->rrp.peers->mutex); */
197
198 pc->tries–;
199 }
200
201 if (++iphp->tries >= 20) {
202 return iphp->get_rr_peer(pc, &iphp->rrp);
203 }
204 }

主要代码在红色三行。

1、for 循环 i 取 012 三个值，而 ip 的点分十进制表示方法将 ip 分成四段（如：192.168.1.1），但是这里循环时只是将 ip 的前三个端作为参数加入 hash 函数。这样做的目的是保证 ip 地址前三位相同的用户经过 hash 计算将分配到相同的后端 server。

作者的这个考虑是极为可取的，因此 ip 地址前三位相同通常意味着来着同一个局域网或者相邻区域，使用相同的后端服务让 nginx 在一定程度上更具有一致性。

2、哈希函数：hash = (hash * 113 + iphp->addr[i]) % 6271

作者使用了这样一个极为简单的 hash 函数，当然目的是为了性能。而这样一个 hash 函数的效果如何呢？我们来测试一下。

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

const double per = 0.5; // 阈值，后端 server 命中个数与平均值偏离超过该比例则输出相关信息

int main() {
srand((unsigned)time(NULL));
int peer_number; //后端 server 节点数
peer_number= rand() % 6271 + 1; // 随机产生
int* result = new int[peer_number]; // 存放每个后端 server 命中次数
for(int i = 0; i < peer_number; i++) {// 初始化
result[i] = 0;
}

int total_num = 1000000; //进行 hash 的总次数
int total_num_temp = total_num;
while(total_num_temp–>0) {
int rand_num[3];
for(int i = 0; i < 3; i++) {
rand_num[i]= rand()%255; // 随机生成三个数作为 ip 地址前三段
// cout << i << “: ” << rand_num[i] <<endl;
}
int hash = 89;
for(int i = 0; i < 3; i++) {
hash = (hash * 113 + rand_num[i]) % 6271; //hash 运算
}
hash = hash % peer_number;
result[hash]++; // 统计 hash 值命中
}

// 设定一个阈值 per，当每个 server 命中次数与平均值偏差超过该比例时记录。
int avg = total_num/peer_number;
int max =(int) ((double)avg * (1 + per));
int min =(int) ((double)avg * (1 – per));
for(int i = 0; i < peer_number; i++) {
//cout<<i<<“: “<<result[i]<< endl;
if (result[i] > max || result[i] < min){
for(int j = 0; j < peer_number; j++) {
cout<<j<<“: “<<result[j]<< endl;
}
cout << “avg: “ << avg << “, max: “ << max << “, min: “ <<
min << “, i: “ << i << “, result[i]: “ << result[i] <<endl;
cout << peer_number << endl;
return 1;
}
}
delete []result;
}