Nginx模块开发（17）—HASH模型
1、百科知识
hash一般翻译为“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。
ngx_hash.h实现了nginx里面比较重要的一个hash结构，这个在模块配置解析中经常被用到。该hash结构是只读的，即仅在初始创建时可以给出保存在其中的key-value对，其后就只能查询而不能进行增删改操作了，在这里只介绍常用的结构体和函数。
2、数据结构
ngx_hash_init_t;
typedef struct {
ngx_hash_t *hash; //指向我们实际的hash结构体
ngx_hash_key_pt key; //hash函数指针
ngx_uint_t max_size; //最大元素个数，一般用指令来配置
ngx_uint_t bucket_size; //桶的大小，一般用指令来配置
char *name; //log中会用到
ngx_pool_t *pool; //内存池
ngx_pool_t *temp_pool; //用于分配临时数据空间的内存池
} ngx_hash_init_t;
typedef ngx_uint_t (*ngx_hash_key_pt) (u_char *data, size_t len);
ngx_hash_key_t
typedef struct {
ngx_str_t key; // key
ngx_uint_t key_hash; //key经过算法变成的uint
void *value; //key对应的value
} ngx_hash_key_t;
主要功能：Key-Value对，包含hash值；
ngx_hash_t;
typedef struct {
ngx_hash_elt_t **buckets; //指向桶的实际空间
ngx_uint_t size; //桶的个数
} ngx_hash_t;
主要功能：hash结构体；
ngx_hash_elt_t
typedef struct {
void *value; //具体存放的值，对应于value
u_short len; //name的长度
u_char name[1]; //对应于小写的key
} ngx_hash_elt_t;
主要功能：存放在桶中的每个元素；
3、数据操作
ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,ngx_uint_t nelts);
ngx_int_t
ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts)
{
u_char *elts;
size_t len;
u_short *test;
ngx_uint_t i, n, key, size, start, bucket_size;
ngx_hash_elt_t *elt, **buckets;
//判断桶的最大容量是否能容纳ngx_hash_key_t
for (n = 0; n < nelts; n++) {
if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names;[n]) + sizeof(void *))
{
ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
"could not build the %s, you should "
"increase %s_bucket_size: %i",
hinit->name, hinit->name, hinit->bucket_size);
return NGX_ERROR;
}
}
//分配max_size个数组空间，用来存储每个桶的占用空间
test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log);
if (test == NULL) {
return NGX_ERROR;
}
bucket_size = hinit->bucket_size - sizeof(void *);
//初步算出哈希表中需要多少个桶
start = nelts / (bucket_size / (2 * sizeof(void *)));
start = start ? start : 1;
if (hinit->max_size > 10000 && hinit->max_size / nelts < 100) {
start = hinit->max_size - 1000;
}
//计算哈希表需要多少个桶
for (size = start; size < hinit->max_size; size++) {
ngx_memzero(test, size * sizeof(u_short));
for (n = 0; n < nelts; n++) {
if (names[n].key.data == NULL) {
continue;
}
//计算names[n]应该存放在哪个桶中
key = names[n].key_hash % size;
//计算key桶占用空间
test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names;[n]));
#if 0
ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
"%ui: %ui %ui \"%V\"",
size, key, test[key], &names;[n].key);
#endif
//若key桶的容量大于桶的最大容量，则跳转到next，增加hash表中桶的数量
if (test[key] > (u_short) bucket_size) {
goto next;
}
}
//找到合适的桶数量
goto found;
next:
continue;
}
//max_size和bucket_size设置不合理，nginx也启动不了
ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
"could not build the %s, you should increase "
"either %s_max_size: %i or %s_bucket_size: %i",
hinit->name, hinit->name, hinit->max_size,
hinit->name, hinit->bucket_size);
ngx_free(test);
return NGX_ERROR;
found:
//初始化每个桶的初始容量为4个字节，size为桶数
for (i = 0; i < size; i++) {
test[i] = sizeof(void *);
}
//计算每个桶的实际容量
for (n = 0; n < nelts; n++) {
if (names[n].key.data == NULL) {
continue;
}
key = names[n].key_hash % size;
test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names;[n])); //4+20
}
//把每个桶的实际占用空间大小对齐到ngx_cacheline_size边界上
//计算所有桶占用的空间长度
len = 0;
for (i = 0; i < size; i++) {
if (test[i] == sizeof(void *)) {
continue;
}
test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size)); //64
len += test[i];
}
//若hash没初始化，分配ngx_hash_wildcard_t空间和size个桶的ngx_hash_elt_t 管理成员。
if (hinit->hash == NULL) {
hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t)
+ size * sizeof(ngx_hash_elt_t *));
if (hinit->hash == NULL) {
ngx_free(test);
return NGX_ERROR;
}
//第一个桶的管理成员ngx_hash_elt_t
buckets = (ngx_hash_elt_t **)
((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t));
} else {
buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));
if (buckets == NULL) {
ngx_free(test);
return NGX_ERROR;
}
}
//分配桶的实际占用空间，并对齐到ngx_cacheline_size边界上
elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size);
if (elts == NULL) {
ngx_free(test);
return NGX_ERROR;
}
elts = ngx_align_ptr(elts, ngx_cacheline_size);
//计算每个桶的起始地址
for (i = 0; i < size; i++) {
if (test[i] == sizeof(void *)) {
continue;
}
buckets[i] = (ngx_hash_elt_t *) elts;
elts += test[i];
}
for (i = 0; i < size; i++) {
test[i] = 0;
}
//初始化每个桶的成员。桶的成员保存key字符串，value值地址,key字符串的长度。
//同时计算每个桶所有成员占用的空间
for (n = 0; n < nelts; n++) {
if (names[n].key.data == NULL) {
continue;
}
key = names[n].key_hash % size;
//第一次test[key]=0
elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]);
elt->value = names[n].value;
elt->len = (u_short) names[n].key.len;
ngx_strlow(elt->name, names[n].key.data, names[n].key.len);
//下一个test[key]值已经变了，主要为了解决hash冲突
test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names;[n])); //20
}
//在每个桶末成员后添加NULL结束字符，以标示每个桶的结束标志。
for (i = 0; i < size; i++) {
if (buckets[i] == NULL) {
continue;
}
elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);
elt->value = NULL;
}
ngx_free(test);
//赋值桶的管理成员buckets开始地址
hinit->hash->buckets = buckets;
hinit->hash->size = size;
。。。
return NGX_OK;
}
实例分析
| Key | key = names[n].key_hash % size |
| 10.253.70.106 | 2 |
| 10.253.70.107 | 0 |
| 10.253.70.108 | 1 |
| 10.253.70.109 | 2 |
| 10.253.70.110 | 0 |
| 10.253.70.111 | 1 |
| 10.253.70.112 | 2 |
备注：对于ngx_hash_init来说，nelts=7，通过计算后，桶数只需要3就OK了。
（1）存在key-value有一致的，如果重复性数据较少，max_size较大，bucket_size较大，有可能成功；
（2）存在key-value有一致的，如果重复性数据很多，则有可能重启不成功，会出现以下错误；
ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len);
使用实例：
key = ngx_hash_key_lc(address, strlen(address));
ngx_hash_find(hash_init->hash, key, address, strlen(address));
备注：nginx的hash在查找时使用的是分桶后线性查找法，因此当分桶数确定时查找效率同其中的总key-value对数量成反比。
void *
ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len)
{
ngx_uint_t i;
ngx_hash_elt_t *elt;
#if 0
ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "hf:\"%*s\"", len, name);
#endif
elt = hash->buckets[key % hash->size]; //ngx_hash_t
if (elt == NULL) {
return NULL;
}
while (elt->value) { //最后一个value被置为了NULL
if (len != (size_t) elt->len) {
goto next;
}
for (i = 0; i < len; i++) {
if (name[i] != elt->name[i]) {
goto next;
}
}
return elt->value;
next:
elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt-;>name[0] + elt->len,
sizeof(void *)); //对齐
continue;
}
return NULL;
}
4、常见操作
对于hash结构的操作，主要有创建hash和查找hash。其中创建hash过程分为以下三个步骤：
（1）构造一个ngx_hash_key_t为成员的数组；
（2）向ngx_hash_key_t中填充数据：key、value和使用key计算出来的一个hash值；
（2）构造一个ngx_hash_init_t结构体的变量，其中包含了ngx_hash_t的成员，为hash的结构体，还包括了一些其他初始设置，如bucket大小、内存等；
（3）调用ngx_hash_init传入ngx_hash_init_t结构，ngx_hash_key_t的数组，和数组的长度，进行初始化，这样ngx_hash_init_t的hash成员就是我们想要的hash结构；
//构建一个ngx_hash_key_t为成员的数组
datas = ngx_array_create(pool, NGX_BARRIER_RULE_NUM, sizeof(ngx_hash_key_t));
if (datas == NULL){
fclose(fp);
return NGX_ERROR;
}
//填充数据
while(1)
{
node = (ngx_hash_key_t *)ngx_array_push(datas);
node->key.len = strlen(key);
node->key.data = ngx_pcalloc(pool, NGX_BARRIER_BUF_LEN);
strncpy(node->key.data, key, node->key.len);
node->key.data[node->key.len] = '\0';
node->key_hash = ngx_hash_key_lc(node->key.data, node->key.len);
node->value = (char *)ngx_pcalloc(pool, NGX_BARRIER_BUF_LEN);
if (node->value == NULL){
fclose(fp);
return NGX_ERROR;
}
strncpy((char * )node->value, value, strlen(value));
}//while ends
//构造ngx_hash_init_t数组
ngx_hash_init_t *hash_init = &ctx-;>BWlist; //已分配空间
hash = (ngx_hash_t *)ngx_pcalloc(pool, sizeof(ngx_hash_t));
if (hash == NULL){
fclose(fp);
return NGX_ERROR;
}
hash_init->hash = hash; //hash结构
hash_init->key = &ngx;_hash_key_lc; //hash算法函数
hash_init->max_size = ctx->hash_max_size; //最好通过指令来设置
hash_init->bucket_size = ctx->hash_bucket_size; //最好通过指令来设置
hash_init->name = "barrier_rule_hash";
hash_init->pool = pool;
hash_init->temp_pool = NULL;
if (ngx_hash_init(hash_init, (ngx_hash_key_t *)datas->elts, datas->nelts) != NGX_OK){
fclose(fp);
return NGX_ERROR;
}
5、参考资料
http://blog.csdn.net/livelylittlefish/article/details/6636229