Nginx源码研究(4)——hash结构ngx_hash_t

本文 http://blog.codeg.cn/2015/01/03/ngx_hash_t/ 是作者zieckey在研究和学习相关内容时所做的笔记,欢迎广大朋友指正和交流! 版权所有,欢迎转载和分享,但请保留此段声明。

简介

本文主要介绍Nginx的hash结构ngx_hash_t这一重要的数据结构的使用方法和具体实现。nginx实现的hash表特点是构建一次, 初始化后无法动态的增删,之后就只用于查找。之所以这么设计是为了使用最少的内存同时得到最快的查找速度。

冲突解决

Nginx的ngx_hash_t采用开放地址法来解决冲突问题,即:插入的时候发现自己的位置f(key)已经被占了,就向后遍历,查看f(key)+1的位置是否被占用,如果没被占用,就占用它,否则继续相后,查询的时候,同样也如果f(key)不是需要的值,也依次向后遍历,一直找到需要的元素。

源代码位置

src/core/ngx_hash.{h,c}

数据结构

//hash结构
typedef struct {
    ngx_hash_elt_t  **buckets; //hash桶(有size个桶)
    ngx_uint_t        size;    //hash桶个数
} ngx_hash_t;


// <key,value> 结构,初始化时候使用
typedef struct {
    ngx_str_t         key;      //key,为nginx的字符串结构
    ngx_uint_t        key_hash; //由该key计算出的hash值(通过hash函数如ngx_hash_key_lc())
    void             *value;    //该key对应的值,组成一个键-值对<key,value>
} ngx_hash_key_t;

//hash元素结构
typedef struct {
    void             *value;    //value,即某个key对应的值,即<key,value>中的value
    u_short           len;      //name长度
    u_char            name[1];  //某个要hash的数据(在nginx中表现为字符串),即<key,value>中的key
    // 这里数组长度为1,是一个小技巧。实现时,在具体分配ngx_hash_elt_t的大小时使用宏NGX_HASH_ELT_SIZE来确定(并且是内存对齐的):
    // #define NGX_HASH_ELT_SIZE(name) (sizeof(void *) + ngx_align((name)->key.len + 2, sizeof(void *)))
} ngx_hash_elt_t;

//hash初始化结构,用来将其相关数据封装起来作为参数传递给ngx_hash_init()或ngx_hash_wildcard_init()函数
typedef struct {
    ngx_hash_t       *hash;         //指向待初始化的hash结构。
    ngx_hash_key_pt   key;          //hash函数指针

    // 散列表中槽的最大数目
    ngx_uint_t        max_size;     //bucket的最大个数

    // 散列表中一个槽的空间大小,它限制了每个散列表元素关键字的最大长度,通过NGX_HASH_ELT_SIZE(name)计算每个element的大小。
    // 如果这个bucket_size设置较大,那么他就能够容纳多个element,这样一个bucket里存放多个element,进而导致查找速度下降。
    // 为了更好的查找速度,请将bucket_size设置为所有element长度最大的那个。
    ngx_uint_t        bucket_size;

    // 散列表的名称
    char             *name;         //该hash结构的名字(仅在错误日志中使用)
    // 内存池,它分配散列表(最多3个,包括1个普通散列表,1个前置通配符散列表,1个后置通配符散列表)中的所有槽
    ngx_pool_t       *pool;         //该hash结构从pool指向的内存池中分配
    // 临时内存池,它仅存在于初始化散列表之前。它主要用于分配一些临时的动态数组,带通配符的元素在初始化时需要用到这些数组。
    ngx_pool_t       *temp_pool;    //分配临时数据空间的内存池
} ngx_hash_init_t;

内存结构图

备注:从参考文档7摘录

备注:从参考博客6摘录

初始化函数

直接上增加了注释的代码,这个需要结合上面两个图片来看。


// 第一个参数hinit是初始化的一些参数的一个集合。 names是初始化一个ngx_hash_t所需要的所有<key,value>对的一个数组,而nelts是该数组的个数。
// 备注:我倒是觉得可以直接使用一个ngx_array_t*作为参数呢?
//
//初始化步骤
//1. 遍历待初始化的ngx_hash_key_t数组, 保证占用空间最大的ngx_hash_elt_t元素可以装进bucket_size大小空间
//2. 预估一个可以装入所有元素的hash表长度start, 判断是否可以将所有元素装进这个size大小的hash表
//3. 装不下, 增加size, 如果size达到max_size仍然不能创建这个hash表, 则失败. 否则确定了要构建的hash表长度(buckets个数)
//4. found:处开始,, 计算所有元素占用总空间, 为hash表的各个bucket分配各自的空间
//5. 将ngx_hash_key_t数组元素分别放入对应的bucket中
//
//其中第2步中怎么计算初始的可能hash表的大小start?
//start = nelts / (bucket_size / (2 * sizeof(void *)));
//也即认为一个bucket最多放入的元素个数为bucket_size / (2 * sizeof(void *));
//64位机器上, sizeof(void *) 为8 Bytes,  sizeof(unsigned short)为2Bytes, sizeof(name)为1 Byte, sizeof(ngx_hash_elt_t)为16Bytes, 正好与2 * sizeof(void *)相等.
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;

    //检查names数组的每一个元素,判断桶的大小是否够存放key
    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;
        }
    }

    //分配 sizeof(u_short)*max_size 个字节的空间保存hash数据
    //(该内存分配操作不在nginx的内存池中进行,因为test只是临时的)
    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 && nelts && 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));
        //标记1:此块代码是检查bucket大小是否够分配hash数据
        for (n = 0; n < nelts; n++) {
            if (names[n].key.data == NULL) {
                continue;
            }

            //计算key和names中所有name长度,并保存在test[key]中
            key = names[n].key_hash % size; //若size=1,则key一直为0
            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

            //若超过了桶的大小,则到下一个桶重新计算
            if (test[key] > (u_short) bucket_size) {
                goto next;
            }
        }

        goto found;

    next:

        continue;
    }

    //若没有找到合适的bucket,退出
    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: //找到合适的bucket

	//将test数组前size个元素初始化为sizeof(void *)
    for (i = 0; i < size; i++) {
        test[i] = sizeof(void *);
    }

    /** 标记2:与标记1代码基本相同,但此块代码是再次计算所有hash数据的总长度(标记1的检查已通过)
        但此处的test[i]已被初始化为sizeof(void *),即相当于后续的计算再加上一个void指针的大小。
     */
    for (n = 0; n < nelts; n++) {
        if (names[n].key.data == NULL) {
            continue;
        }

        //计算key和names中所有name长度,并保存在test[key]中
        key = names[n].key_hash % size;//若size=1,则key一直为0
        test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
    }

    //计算hash数据的总长度
    len = 0;

    for (i = 0; i < size; i++) {
        if (test[i] == sizeof(void *)) {
        	//若test[i]仍为初始化的值为sizeof(void *),即没有变化,则继续
            continue;
        }

        //对test[i]按ngx_cacheline_size对齐(32位平台,ngx_cacheline_size=32)
        test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size));

        len += test[i];
    }

    if (hinit->hash == NULL) {
    	//在内存池中分配hash头及buckets数组(size个ngx_hash_elt_t*结构)
        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;
        }

        //计算buckets的启示位置(在ngx_hash_wildcard_t结构之后)
        buckets = (ngx_hash_elt_t **)
                      ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t));

    } else {
    	//在内存池中分配buckets数组(size个ngx_hash_elt_t*结构)
        buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));
        if (buckets == NULL) {
            ngx_free(test);
            return NGX_ERROR;
        }
    }

    //接着分配elts,大小为len+ngx_cacheline_size,此处为什么+ngx_cacheline_size?——下面要按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);

    //将buckets数组与相应elts对应起来
    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;
    }

    //将传进来的每一个hash数据存入hash表
    for (n = 0; n < nelts; n++) {
        if (names[n].key.data == NULL) {
            continue;
        }

        //计算key,即将被hash的数据在第几个bucket,并计算其对应的elts位置
        key = names[n].key_hash % size;
        elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]);

        //对ngx_hash_elt_t结构赋值
        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);

        //计算下一个要被hash的数据的长度偏移
        test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
    }

    for (i = 0; i < size; i++) {
        if (buckets[i] == NULL) {
            continue;
        }

        //test[i]相当于所有被hash的数据总长度
        elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);

        //将每个bucket的最后一个指针大小区域置NULL
        elt->value = NULL;
    }

    ngx_free(test);//释放该临时空间

    hinit->hash->buckets = buckets;
    hinit->hash->size = size;

    return NGX_OK;
}

测试代码

该测试代码的完整工程的编译和运行方式请参考 https://github.com/zieckey/nginx-research项目。Linux&Windows都测试通过。

static ngx_str_t names[] = {
    ngx_string("zieckey"),
    ngx_string("codeg"),
    ngx_string("jane") };

static char* descs[] = { "zieckey's id is 0", "codeg's id is 1", "jane's id is 2" };

// hash table的一些基本操作
TEST_UNIT(ngx_hash)
{
    ngx_uint_t          k;
    ngx_pool_t*         pool = g_pool;
    ngx_hash_init_t     hash_init;
    ngx_array_t*        elements;
    ngx_hash_key_t*     arr_node;
    char*               find;
    int                 i;

    ngx_cacheline_size = NGX_CPU_CACHE_LINE;

    hash_init.hash = NULL;                      // 置为NULL,让ngx_hash_init来初始化
    hash_init.key = &ngx_hash_key_lc;          // hash算法函数
    hash_init.max_size = 1024;                   // max_size
    hash_init.bucket_size = 64; // ngx_align(64, ngx_cacheline_size);
    hash_init.name = "codeg_hash";          // 在log里会用到
    hash_init.pool = pool;                 // 内存池
    hash_init.temp_pool = NULL;

    // 创建数组
    elements = ngx_array_create(pool, H_ARRAYSIZE(names), sizeof(ngx_hash_key_t));
    for (i = 0; i < H_ARRAYSIZE(names); i++) {
        arr_node = (ngx_hash_key_t*)ngx_array_push(elements);
        arr_node->key = (names[i]);
        arr_node->key_hash = ngx_hash_key_lc(arr_node->key.data, arr_node->key.len);
        arr_node->value = (void*)descs[i];
        printf("key: %s , key_hash: %u\n", arr_node->key.data, arr_node->key_hash);
    }

    H_TEST_ASSERT(ngx_hash_init(&hash_init, (ngx_hash_key_t*)elements->elts, elements->nelts) == NGX_OK);

    // 查找
    k = ngx_hash_key_lc(names[0].data, names[0].len);
    printf("%s key is %u\n", names[0].data, k);
    find = (char*)ngx_hash_find(hash_init.hash, k, (u_char*)names[0].data, names[0].len);
    H_TEST_ASSERT(find);
    if (find) {
        printf("get desc of %s : %s\n", (char*)names[0].data, (char*)find);
    }

    ngx_array_destroy(elements);
}

参考:

  1. 淘宝:Nginx开发从入门到精通 http://tengine.taobao.org/book/chapter_02.html#ngx-hash-t-100
  2. nginx源码注释 https://github.com/zieckey/nginx-1.0.14_comment/blob/master/src/core/ngx_hash.h
  3. nginx源码注释 https://github.com/zieckey/nginx-1.0.14_comment/blob/master/src/core/ngx_hash.c
  4. nginx源码分析—hash结构ngx_hash_t(v1.0.4) http://blog.csdn.net/livelylittlefish/article/details/6636229
  5. 菜鸟nginx源码剖析数据结构篇(六) 哈希表 ngx_hash_t(上) http://blog.csdn.net/chen19870707/article/details/40794285
  6. nginx代码分析-基本结构-哈希表ngx_hash_t http://my.oschina.net/chenzhuo/blog/177866
  7. nginx源码研究 https://code.google.com/p/nginxsrp/wiki/NginxCodeReview