Nginx 散列表设计

  • 不支持动态增删改元素，初始化的时候就固定了整个哈希表的结构，只支持查找
  • 以字符串作为关键字，键值可以是任意类型
  • 有一种支持通配符的散列表变体，支持前缀和后缀通配符形式的关键字
  • 解决散列冲突的方式本质上是分离链接法，但是由于不用支持动态增删，就不需要链表的动态插入特性，直接使用数组，可以增加访问的效率
  • 字符串关键字在哈希表中是转换为小写字母存放的（重要）

Nginx 散列表数据结构

散列表结构

  • 桶的数量为 size
  • 每个桶可能含有多个槽数组，遍历槽类似于遍历链表，以一个 NULL 作为结尾
    typedef struct {
    ngx_hash_elt_t  **buckets;
    ngx_uint_t        size;
} ngx_hash_t;

散列表槽结构

  • 键值用 value 指向
  • 关键字的长度用 len 表示
  • 关键字用 name 保存，这里用到了柔性数组（flexible array），这里长度为 1 而不是 0 是出于可移植性的问题，有些编译器不支持零长度数组，好处就是少一次动态内存分配
    typedef struct {
    void             *value;
    u_short           len;
    u_char            name[1];
} ngx_hash_elt_t;

散列表初始化结构

  • 为了初始化一个散列表，Nginx 专门设计了一个结构体

  • 散列表实体为 hash ，如果传入 NULL 则由初始化函数负责分配内存

  • 散列函数用一个函数指针变量 key 表示，只要满足要求，用户可以使用自定义的散列函数，Nginx 默认支持两种散列函数

  • 桶的最大数量用 max_size 表示

  • 单个桶的最大大小用 bucket_size 表示

  • 哈希表的名称用 name 表示

  • 用于分配散列表的内存池用 pool 表示

  • 在初始化支持通配符的散列表时，需要使用 temp_pool 为临时动态数组分配空间

    typedef struct {
    ngx_hash_t       *hash;
    ngx_hash_key_pt   key;

    ngx_uint_t        max_size;
    ngx_uint_t        bucket_size;

    char             *name;
    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);

  • Nginx 支持两种散列函数，一种是直接通过 BKDR 算法将指定长度的字节流数据映射为整型，另一种是先将字节流数据中的字母全部转为小写，再使用 BKDR 算法（注意这里的 data 不一定是 c 风格字符串）

    #define ngx_hash(key, c)   ((ngx_uint_t) key * 31 + c)

ngx_uint_t
ngx_hash_key(u_char *data, size_t len)
{
    ngx_uint_t  i, key;

    key = 0;

    for (i = 0; i < len; i++) {
        key = ngx_hash(key, data[i]);
    }

    return key;
}

ngx_uint_t
ngx_hash_key_lc(u_char *data, size_t len)
{
    ngx_uint_t  i, key;

    key = 0;

    for (i = 0; i < len; i++) {
        key = ngx_hash(key, ngx_tolower(data[i]));
    }

    return key;
}

散列表键值结构体

  • 散列表初始化函数需要通过一个 ngx_hash_key_t 结构的数组来向哈希表添加数据
  • 结构包含了关键字通过散列函数得到的 key_hash ，以及关键字本身 key ，最后是关键字对应的键值
    typedef struct {
    ngx_str_t         key;
    ngx_uint_t        key_hash;
    void             *value;
} ngx_hash_key_t;

Nginx 散列表初始化

  • 首先做合法性校验，桶数量不能为 0，单个桶的大小不能超过 u_short 的最大值减去按 ngx_cacheline_size 对齐的大小

  • 遍历散列键值结构体数组，键为空的跳过，不为空的就判断设置的桶大小是否能够放下这对键值的大小再加上一个指针的大小（因为每个桶中的槽都以一个 NULL 结尾），NGX_HASH_ELE_SIZE 的实现如下，键值所需槽的大小为一个 value 指针的大小，加上关键字长度和 u_short所占的两个字节，按照指针大小对齐

    #define NGX_HASH_ELT_SIZE(name)                                               \
    (sizeof(void *) + ngx_align((name)->key.len + 2, sizeof(void *)))

  • 为了计算哈希表所需的桶数量，使用一个 test 数组，分配的总内存大小为设定的桶数量最大值

  • 然后使用特定的计算方法，求出一个初始探测值 start ，从这个值开始探测合适的桶数量 size ，本质上就是将键散列到 size 大小的桶数组中，并累计使用的桶的长度，如果超过了 bucket_size 则尝试下一个 size

    • 如果全部都超过了，size 就直接使用 hinit->max_size 并通过日志进行提示
    • 如果中途找到了合适的 size ，就进入下一阶段

  • 将 test 初始化为单个指针的大小（即每个桶结尾的 NULL 所占的大小）

  • 然后再重新进行一次散列操作，判断单个桶的大小不得超过 65536 - ngx_cacheline_size

  • 对于非空的桶，将其大小调整为按 ngx_cacheline_size 对齐后的大小，并用 len 记录所有桶大小的和，用于之后一次性分配所有槽的内存

  • 如果传入的散列表为空，则重新分配，注意大小为 sizeof(ngx_hash_wildcard_t) + size * sizeof(ngx_hash_elt_t *) ，即头部还包含一个通配符散列表结构体，所以实际的散列表首地址需要偏移一个通配符散列表结构体的大小，若传入的散列表不为空，则只分配 size * sizeof(ngx_hash_elt_t *) 大小的内存

  • 为所有槽分配内存，用 elts 指向这块内存（注意需要进行地址对齐）

  • 为桶数组的每个元素赋值，指向其对应的槽数组的第一个元素

  • 将键值数据放到槽中，之前只是用 test 探测，现在需要将实际的数据放进去了，存放关键字 name 的时候将字符串都转为小写了

  • 为每个槽数组的最后一个元素赋值，这里比较巧妙，由于最后剩余一个指针的大小，就将这块地址转换为 ngx_hash_elt_t 指针，由于结构体的第一个成员 value 正好占一个指针的大小，因此可以通过设置它的值为 NULL 来表示槽数组的结尾

    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;

    if (hinit->max_size == 0) {
        ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
                      "could not build %s, you should "
                      "increase %s_max_size: %i",
                      hinit->name, hinit->name, hinit->max_size);
        return NGX_ERROR;
    }

    if (hinit->bucket_size > 65536 - ngx_cacheline_size) {
        ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
                      "could not build %s, too large "
                      "%s_bucket_size: %i",
                      hinit->name, hinit->name, hinit->bucket_size);
        return NGX_ERROR;
    }

    for (n = 0; n < nelts; n++) {
        if (names[n].key.data == NULL) {
            continue;
        }

        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 %s, you should "
                          "increase %s_bucket_size: %i",
                          hinit->name, hinit->name, hinit->bucket_size);
            return NGX_ERROR;
        }
    }

    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));

        for (n = 0; n < nelts; n++) {
            if (names[n].key.data == NULL) {
                continue;
            }

            key = names[n].key_hash % size;
            len = test[key] + NGX_HASH_ELT_SIZE(&names[n]);

#if 0
            ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
                          "%ui: %ui %uz \"%V\"",
                          size, key, len, &names[n].key);
#endif

            if (len > bucket_size) {
                goto next;
            }

            test[key] = (u_short) len;
        }

        goto found;

    next:

        continue;
    }

    size = hinit->max_size;

    ngx_log_error(NGX_LOG_WARN, hinit->pool->log, 0,
                  "could not build optimal %s, you should increase "
                  "either %s_max_size: %i or %s_bucket_size: %i; "
                  "ignoring %s_bucket_size",
                  hinit->name, hinit->name, hinit->max_size,
                  hinit->name, hinit->bucket_size, hinit->name);

found:

    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;
        len = test[key] + NGX_HASH_ELT_SIZE(&names[n]);

        if (len > 65536 - ngx_cacheline_size) {
            ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
                          "could not build %s, you should "
                          "increase %s_max_size: %i",
                          hinit->name, hinit->name, hinit->max_size);
            ngx_free(test);
            return NGX_ERROR;
        }

        test[key] = (u_short) len;
    }

    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));

        len += test[i];
    }

    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;
        }
    }

    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;
    }

    for (n = 0; n < nelts; n++) {
        if (names[n].key.data == NULL) {
            continue;
        }

        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);

        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;

#if 0

    for (i = 0; i < size; i++) {
        ngx_str_t   val;
        ngx_uint_t  key;

        elt = buckets[i];

        if (elt == NULL) {
            ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
                          "%ui: NULL", i);
            continue;
        }

        while (elt->value) {
            val.len = elt->len;
            val.data = &elt->name[0];

            key = hinit->key(val.data, val.len);

            ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
                          "%ui: %p \"%V\" %ui", i, elt, &val, key);

            elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
                                                   sizeof(void *));
        }
    }

#endif

    return NGX_OK;
}

    Nginx 散列表查找

  • 调用方需要传入关键字，根据散列函数计算出对应的 key ，注意如果你的关键字含大写且使用的散列函数的 ngx_hash_key ，则你需要在查找前将关键字转为小写

  • 关键字对应的桶为 key % hash->size ，遍历槽数组即可

    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];

    if (elt == NULL) {
        return NULL;
    }

    while (elt->value) {
        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;
}