nginx hash结构存储

    nginx在存储server_name和ngx_http_core_srv_conf_t的映射的时候用到了hash结构，nginx中的非通配符server_name存储hash结构类似如下形式

   配置server_names_hash_max_size控制bucket的最大数量，server_names_hash_bucket_size控制每个bucket的大小，每个bucket可以盛放一定数量的ngx_hash_elt_t，每个bucket存放的ngx_hash_elt_t都拥有相同的hash％size。这里就要求拥有相同hash％size的元素全都放在一个bucket中，因为每个元素的hash值是确定的，size是不确定的。所以有必要从一定的size开始测试，看能不能保证拥有相同hash％size的元素放在同一个bucket中，如果不能，那么就继续加大size，因为加大size有利于元素分布的更分散一些。所以测试size的大小直到server_names_hash_max_size，如果到达了max size也不能使得相同的hash％size的元素同时分布在一个bucket中，那么就会报错了，提示server_names_hash_max_size和server_names_hash_bucket_size设置的不合理。

   每个bucket的布局如图

   看下代码的实现:

   构建hash的过程分为4步

  第一步，检验bucket是否能存储每一个元素，如果设置的bucket_size过小，server_name又比较长，那么bucket是不能存下一个元素的。

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;
    //遍历每一个元素，看下bucket是否能存储下每一个元素,这里 NGX_HASH_ELT_SIZE是每一个元素的大小
    //#define NGX_HASH_ELT_SIZE(name)
    //(sizeof(void *) + ngx_align((name)->key.len + 2, sizeof(void *)))
    //这里面每个name的value指向ngx_http_core_srv_conf_t，后面的key的大小就是key.len,再存储这个len，是个short类型，需要两个2字节的空间
    for (n = 0; n < nelts; n++) {
        if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *)) //每个bucket的size 再加上sizeof(void *)的目的是每个bucket有个结束元素，         这个元素的value是个指针，指向null。
        {
            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;
        }
    }

  第二步 要确定hash 的size，size尽可能的小，同时要保证具有相同hash％size的元素都再一个bucket中

   //test数组中存放每个bucket的当前容量，如果某一个key的容量大于了bucket size就意味着需要加大hash桶的个数了
    test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log);
    if (test == NULL) {
        return NGX_ERROR;
    }

   //每个bucket的size需要去掉最后一个元素所占的空间，这个元素是个哑元素，用来判断当前bucket是否还有元素
    bucket_size = hinit->bucket_size - sizeof(void *);
   //start是最少的bucket的数目，因为每个元素占有的空间是value的指针和后面len和name按照字节对齐的总和
    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;
    }
   //size从start开始，逐渐加大bucket的个数，直到恰好满足所有具有相同hash％size的元素都在同一个bucket，这样hash的size就能确定了
    for (size = start; size < hinit->max_size; size++) {
      //每次递归新的size的时候需要将旧test的数据清空
        ngx_memzero(test, size * sizeof(u_short));
         //新size的开始，遍历每一个元素
        for (n = 0; n < nelts; n++) {
            if (names[n].key.data == NULL) {
                continue;
            }
            key = names[n].key_hash % size;
            //开始叠加每个bucket的size
            test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
            //如果某个bucket的size超过了bucket_size，那么加大bucket的个数，使得元素分布更分散一些
            if (test[key] > (u_short) bucket_size) {
                goto next;
            }
        }

        goto found;

    next:

        continue;
    }
     //最终如果size超过了max size，就报错
    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;

  第三步：表示找到了合适的bucket个数，使得所有具有相同的hash％size的元素都在同一个bucket中，需要根据元素具体数量，分配地址空间

found:
    //每个bucket都有一个哑元素
    for (i = 0; i < size; i++) {
        test[i] = sizeof(void *);
    }
   //遍历每个bucket计算每个bucket的大小
    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]));
    }

    len = 0;
    //叠加每个bucket 的大小，sum是len
    for (i = 0; i < size; i++) {
        if (test[i] == sizeof(void *)) {
            continue;
        }

        test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size));

        len += test[i];
    }
    //初始化hinit的hash结构空间
    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;
        }

        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;
        }
    }
    //malloc bucket的空间，根据那个上面计算出来的len
    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);
    //把elts地址空间分发到每个bucket中
    for (i = 0; i < size; i++) {
        if (test[i] == sizeof(void *)) {
            continue;
        }

        buckets[i] = (ngx_hash_elt_t *) elts;
        elts += test[i];

    }

   第四步，hash结构已经有了，开始填充数据，填充每一个bucket

for (i = 0; i < size; i++) {
        test[i] = 0;
    }

    for (n = 0; n < nelts; n++) {
        if (names[n].key.data == NULL) {
            continue;
        }
        //这里test数组纪录每个bucket当前组后一个元素的位移，为了计算下一个元素的位置
        key = names[n].key_hash % size;
        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);
        //更新bucket中下一个元素的位置
        test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
    }
    //最后填充结束节点
    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);

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

总结：
      nginx的hash结构是静态的，也就是不需要插入删除元素，这里选择合适的bucket个数是这个init过程的关键，要保证bucket个数最小，同时要保证具有相同hash％size的元素都能存放在一个bucket当中。