nginx hash结构存储

作者:djjsindy 和c/c++相关  

    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是不能存下一个元素的。

  1. ngx_int_t
  2. ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts)
  3. {
  4.     u_char *elts;
  5.     size_t len;
  6.     u_short *test;
  7.     ngx_uint_t i, n, key, size, start, bucket_size;
  8.     ngx_hash_elt_t *elt, **buckets;
  9.     //遍历每一个元素,看下bucket是否能存储下每一个元素,这里 NGX_HASH_ELT_SIZE是每一个元素的大小
  10.     //#define NGX_HASH_ELT_SIZE(name)
  11.     //(sizeof(void *) + ngx_align((name)->key.len + 2, sizeof(void *)))
  12.     //这里面每个name的value指向ngx_http_core_srv_conf_t,后面的key的大小就是key.len,再存储这个len,是个short类型,需要两个2字节的空间
  13.     for (n = 0; n < nelts; n++) {
  14.         if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *)) //每个bucket的size 再加上sizeof(void *)的目的是每个bucket有个结束元素,         这个元素的value是个指针,指向null。
  15.         {
  16.             ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
  17.                           "could not build the %s, you should "
  18.                           "increase %s_bucket_size: %i",
  19.                           hinit->name, hinit->name, hinit->bucket_size);
  20.             return NGX_ERROR;
  21.         }
  22.     }

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


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

  6.    //每个bucket的size需要去掉最后一个元素所占的空间,这个元素是个哑元素,用来判断当前bucket是否还有元素
  7.     bucket_size = hinit->bucket_size - sizeof(void *);
  8.    //start是最少的bucket的数目,因为每个元素占有的空间是value的指针和后面len和name按照字节对齐的总和
  9.     start = nelts / (bucket_size / (2 * sizeof(void *)));
  10.     start = start ? start : 1;
  11.    //经验值
  12.     if (hinit->max_size > 10000 && nelts && hinit->max_size / nelts < 100) {
  13.         start = hinit->max_size - 1000;
  14.     }
  15.    //size从start开始,逐渐加大bucket的个数,直到恰好满足所有具有相同hash%size的元素都在同一个bucket,这样hash的size就能确定了
  16.     for (size = start; size < hinit->max_size; size++) {
  17.       //每次递归新的size的时候需要将旧test的数据清空
  18.         ngx_memzero(test, size * sizeof(u_short));
  19.          //新size的开始,遍历每一个元素
  20.         for (n = 0; n < nelts; n++) {
  21.             if (names[n].key.data == NULL) {
  22.                 continue;
  23.             }
  24.             key = names[n].key_hash % size;
  25.             //开始叠加每个bucket的size
  26.             test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
  27.             //如果某个bucket的size超过了bucket_size,那么加大bucket的个数,使得元素分布更分散一些
  28.             if (test[key] > (u_short) bucket_size) {
  29.                 goto next;
  30.             }
  31.         }

  32.         goto found;

  33.     next:

  34.         continue;
  35.     }
  36.      //最终如果size超过了max size,就报错
  37.     ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
  38.                   "could not build the %s, you should increase "
  39.                   "either %s_max_size: %i or %s_bucket_size: %i",
  40.                   hinit->name, hinit->name, hinit->max_size,
  41.                   hinit->name, hinit->bucket_size);

  42.     ngx_free(test);

  43.     return NGX_ERROR;

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


  1. found:
  2.     //每个bucket都有一个哑元素
  3.     for (i = 0; i < size; i++) {
  4.         test[i] = sizeof(void *);
  5.     }
  6.    //遍历每个bucket计算每个bucket的大小
  7.     for (n = 0; n < nelts; n++) {
  8.         if (names[n].key.data == NULL) {
  9.             continue;
  10.         }

  11.         key = names[n].key_hash % size;
  12.         test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
  13.     }

  14.     len = 0;
  15.     //叠加每个bucket 的大小,sum是len
  16.     for (i = 0; i < size; i++) {
  17.         if (test[i] == sizeof(void *)) {
  18.             continue;
  19.         }

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

  21.         len += test[i];
  22.     }
  23.     //初始化hinit的hash结构空间
  24.     if (hinit->hash == NULL) {
  25.         hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t)
  26.                                              + size * sizeof(ngx_hash_elt_t *));
  27.         if (hinit->hash == NULL) {
  28.             ngx_free(test);
  29.             return NGX_ERROR;
  30.         }

  31.         buckets = (ngx_hash_elt_t **)
  32.                       ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t));

  33.     } else {
  34.         buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));
  35.         if (buckets == NULL) {
  36.             ngx_free(test);
  37.             return NGX_ERROR;
  38.         }
  39.     }
  40.     //malloc bucket的空间,根据那个上面计算出来的len
  41.     elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size);
  42.     if (elts == NULL) {
  43.         ngx_free(test);
  44.         return NGX_ERROR;
  45.     }

  46.     elts = ngx_align_ptr(elts, ngx_cacheline_size);
  47.     //把elts地址空间分发到每个bucket中
  48.     for (i = 0; i < size; i++) {
  49.         if (test[i] == sizeof(void *)) {
  50.             continue;
  51.         }

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

  54.     }

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

  1. for (i = 0; i < size; i++) {
  2.         test[i] = 0;
  3.     }

  4.     for (n = 0; n < nelts; n++) {
  5.         if (names[n].key.data == NULL) {
  6.             continue;
  7.         }
  8.         //这里test数组纪录每个bucket当前组后一个元素的位移,为了计算下一个元素的位置
  9.         key = names[n].key_hash % size;
  10.         elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]);

  11.         elt->value = names[n].value;
  12.         elt->len = (u_short) names[n].key.len;

  13.         ngx_strlow(elt->name, names[n].key.data, names[n].key.len);
  14.         //更新bucket中下一个元素的位置
  15.         test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
  16.     }
  17.     //最后填充结束节点
  18.     for (i = 0; i < size; i++) {
  19.         if (buckets[i] == NULL) {
  20.             continue;
  21.         }
  22.         //强转不会出现问题,虽然只有一个指针的空间
  23.         elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);
  24.         
  25.         elt->value = NULL;
  26.     }

  27.     ngx_free(test);

  28.     hinit->hash->buckets = buckets;
  29.     hinit->hash->size = size;



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


相关资料:

nginx hash结构存储来源网络,如有侵权请告知,即处理!

编程Tags: