hash表冲突太多如何平滑地进行rehash操作_hash rehash

Linux内核中大量使用了hash表，然而我们知道，hash表这个数据结构的查找效率和数据的规模是强相关的：

• hash表总是处在链表和完美hash的某种中间状态。

其中，hash冲突是我们必然要面对的，hash冲突过多，意味着：

• 数据insert/delete的时候需要lock整个冲突链表，同步开销增大。
• 冲突链表过长，造成遍历开销过大。

解决冲突的有效办法，就是用更大的hash表，对数据进行rehash。

大概4，5年前的事了，当时遇到了一个技术问题，我大致描述一下：

我在开发一个转发网关，需要监控过路的TCP连接，注意，这是一个转发网关，类似路由器，因此对于任何连接，均没有本地socket与之对应，所以本地TCP ehash表中没有任何有用信息。

于是，我在Linux内核的PREROUTING处部署了一个管理TCP四元组的hash表，类似TCP协议栈的ehash，通过解析TCP skb中的SYN，FIN，RST等标志来判断TCP连接的状态，进而决定该hash表的insert/delete操作。类似nf_conntrack那样，但是要轻量的多。

然而随着短连接的不断SYN和FIN，TCP连接不断在hash中被insert随后被delete，perf观察看来hash bucket的spinlock非常高。

…

最终的解决方案很简单，只要将hash bucket的数量扩大一倍即可，在我的代码中，我只需要改一下BUCKETS这个宏定义即可，从1024改到2048.

然而更加优雅的方案似乎是做一个动态rehash机制。动手就能写的逻辑如下：

void rehash(...)
{
       int old_size = ...
       int new_size = old_size*2;
       int i;

       old_htable = htable;
       new_htable = kmalloc(new_size*info_size, GFP_KERNEL);
       for (i = 0; i < new_size; i++) {
               init_one_bucket(&new_htable[i], ...);
       }

       spin_lock(&something_cover_all);
       for (i = 0; i < old_size; i++) {
               head = old_htable[i].hlist;
               spin_lock(&old_htable[i].lock);
               hlist_for_each...(...) {
                       hlist_del(&node);
                       new_hash = hashfn(node_info, new_size);
                       hlist_add_head(&node, &head);
               }
               spin_unlock(&old_htable[i].lock);

       }
       htable = new_htable;
       ...
       spin_unlock(&something_cover_all);
       ...
}

非常简单且直接的一个rehash逻辑。

但是，不够平滑。

下面进入正文。

如果你试过就会知道，当整个hash表的元素已经非常多，上述的rehash操作将会将CPU冲高很久。这很容易理解：

• 需要rehash了，说明bucket的hlist冲突链表已经很长。
• 很长的hlist链表需要很久的遍历时间。
• 在old_htable的元素清空之前，要防止新的元素再insert进入，因此需要很重的lock。

这个rehash操作在现象上将会造成 卡顿 的观感。

这对于我而言是不可接受的，特别是2014年初处于膨胀期的我。所以，我必须设计一种 平滑 的rehash方法，并实现它。

是的，我花了一个周末设计并实现了它。

故事就讲完了。之所以今天又一次提到这个，是因为如今我又遇到了相似的问题，不过这一次，似乎要对TCP socket的ehash和nf_conntrack的hash动手了。

说说我的设计。

参考 两阶段RCU 的实现方式，当我需要对一个hash表进行rehash的时候，我实际上只需要重新申请一个更大的hash表就好了，并记录当前时间点为T：

• 在T之后，所有的insert操作仅针对新的hash表进行操作。
• 在T之后，旧的hash表中的元素完全清空后，旧hash表释放。
• 对于查询，若同时两个hash表的元素个数均不为0，则依次查询两个hash表。

换句话说， 在T之后，old表只能delete，new表可以insert，也可以delete，当old表清空，进入下一个稳定状态。

在实现上，你可以实现地相当巧妙。

首先，我们定义两张hash表：

struct hlist_info {
        struct hlist_head hlist;
        spinlock_t lock;
};

struct hash_table {
    unsigned char *addr;
    unsigned int size;
    atomic_t in_use;
}

struct hash_table htable[2];

static int version = 0;
static int curr_index = 0;

我们的rehash只需要如下这么做：

void rehash(...)
{
    version++;
    htable[curr_index + 1].addr = kzalloc(new_size*info_size, GFP_KERNEL);
    htable[curr_index + 1].size = new_size;

    for (i = 0; i < new_size; i++) {
        init_one_bucket(htable[curr_index + 1].addr + i*info_size, ...);
    }
    curr_index = version%2;
}

与之配套的，我们也需要对inser操作进行定义：

void insert(...)
{
    table = htable[curr_index];
    hash = hashfn(info, table.size);
    head = (... *)(table.addr + hash*info_size).hlist;
    lock = (... *)(table.addr + hash*info_size).lock;
    spin_lock(&lock);
    hlist_add_head(&info->hnode, &head);
    info->hlist = &head //下面的delete操作要用到。
    spin_unlock(&lock);
}

对于delete，稍微麻烦一点，因为一个元素自己并不知道自己是处在新旧哪个table里，所以为了避免遍历，做好的办法就是对info数据结构进行改造，以浪费一个指针为代价，保存该info元素所在的hlist地址：

struct info {
        struct hlist_node hnode;
        struct hlist_head *hlist; // 把hlist信息保存下来
        unsigned int hash;
        void *value;
        ...
};

这样delete操作就及其简单了：

void delete(...)
{
    head = info->hlist;
    // 类似list_entry那样的container_of技巧取出lock
    lock = entry_t(head, struct hlist_info)->lock;
    spin_lock(&lock);
    hlist_del(&info->hnode);
    spin_unlock(&lock);
}

最后就是查找了，这里也存在一些技巧，但是最朴素的做法就是按部就班：

... search(...)
{
    int idx = curr_index;
    table = htable[idx];
again:
    hash = item_hashfn(..., table.size);
    head = (... *)(table.addr + hash*info_size).hlist;
    lock = (... *)(table.addr + hash*info_size).lock;
    spin_lock(&lock);
    hlist_for_each(...) {
        ...
        if (match(...)) {
            spin_unlock(&lock);
            return info;
        }
    }
    spin_unlock(&lock);
    idx++;
    idx = idx%2
    table = htable[idx];
    if (unlikely(table.in_use != 0) && idx != curr_index) {
        goto again;
    }
    return NULL;
}

好了，这就是我所谓的平滑rehash的一个解法。

当然了，我这里的实现是采用了2阶段的实现，也可以是3阶段，甚至n阶段，这就相当于对hash表进行了zone的划分，通常可以用这种方法来隔离业务，nf_conntrack的zone化，表达了这一思想。

事实上，我觉得Linux内核的很多hash表均可以采用这个。

以TCP socket的ehash为例，目前迄至5.3版本内核，ehash的hash bucket在内核运行生命周期中是不可以发生变化的，这很难应对一些突发的流量上升或者下降：

• 在连接过多时，适当增加ehash bucket的大小，以减少hash冲突，降低spinlock和遍历的开销。
• 在连接异常少且持续少时，适当减小ehash bucket的大小，以节约内存。

我想TCP socket查找在经历了lockless Listener之后，有必要去支持类似的动态rehash。

关于TCP的lockless Listener，参见：
https://lwn.net/Articles/659199/
其意义在于取消了per listner的request队列，进而取消了该队列的lock，统一于ehash。

此外，nf_conntrack虽然支持rehash，但是同样存在抖动卡顿，在我的转发网关中，同样基于上述的算法进行了修改。

– 初始记录于2020/03/08下午，于03/12午饭间补齐。也不知道什么时候才能进公司复工，这段时间，一个人，总是回忆，总是乏味，技术的，生活的，哲学的，或者其它别的…

浙江温州皮鞋湿，下雨进水不会胖。