39 | 哈希表的max_size与bucket_size如何配置

nginx的容器是很多nginx高级功能的实现基础。即使不需要编写第三方模块、查看nginx源代码。但变更nginx配置文件达到最大化的性能，也需要了解nginx的容器是怎样使用的。

nginx 六个容器

数组（和平常理解的数组是不同的，是多块连续内存，其中每一块连续内存汇中可以存放许多元素）
链表（ngx_list_t）
队列（ngx_q_t，很多nginx数据结构中都有相应的这样的数据结构，这些结构体实现的功能是类似的，只是操作方法不同）
哈希表
红黑树
基数树（自平衡排序二叉树的一种，只不过key只能是整型，所以像geo模块在使用基数树，其他使用基数树的场景不多）

哈希表

image.png

nginx的哈希表跟我们正常见到的哈希表有所不同。

image.png

上图的结构跟普通的hash表相同。哪有哪些不同。nginx 哈希表应用场景不同。仅仅应用于静态不变的内容。这个hash表通常不会出现插入和删除。nginx刚启动的时候就能确定这个hash表中一共有多少个元素。使用hash表的这些模块通常会暴露出来一个叫max_size、bucket_size 给我们使用的时候。我们的max_size仅仅控制了最大的hash表bucket的个数而不是实际上bucket的个数。比如：max_size可能配置为100，但是实际上只有十个元素使用了哈希表。与实际上bucket_size不符。它的意义在于可以限制最大化的使用。因为消耗了内存。使用hash表的模块有怎样的特点呢？

比如在stream/http的核心模块里，对所有的变量（variables）使用了hash表，因为变量在我们模块编译进去的时候就已经定义清楚了。还是有像map（stream/http）、反向代理（反向代理中，我们需要对很多header，在配置文件中定义好的header做hash提升性能，后面的referer也是一样的道理，访问复杂度O(1)）。

哈希表中有一个bucket size ，在里面有一些默认值，这个默认值在nginx配置文档中说是cpu cache line 会对齐到这样一个值。有什么意义呢？影响了怎样配置bucket size。现在主流的cpu有L1、L2、L3缓存的，它在去主存的数据时，不是按照大家所想象的那样。按照所谓的64位，32位取。现在主流的cpu一次取主存去的字节数就是cpu cache line 。现在是64字节。

哈希表为什么要向64字节对齐呢？这是因为，假设我们每个哈希表的bucket 是59字节，如果我们是紧密排在一起的，取第一个哈希表元素只需要访问一次，还多取了6个字节。但你去第二个元素的时候需要访问主存两次包括64字节中的最后6个字节，以及第二个单元的58个字节。为了避免这种取两次的问题。nginx在它的代码中自动的向上对齐了。所以在配置bucket_size 的时候需要注意两个问题。第一如果配置的bucket size 不是cpu cache line，而是配置了70字节，就会分配每个元素128字节。第二如果有可能的情况下，我们尽量不要超过64字节。以减少cpu访问每个hash表元素的次数。

实际上还有很多第三方模块使用了hash表，使用hash表需要注意，它只为静态不变的内容服务。第二，hash表的bucket size 需要考虑cpu cache line的对齐问题。

课后问题

两个问题

1、这节课开头的hash表的图用的是书上7-10的图，图上写的是size个ngx_hash_elt_t结构体，我的理解是size个ngx_hash_elt_t结构体指针，然后每个指针指向ngx_hash_elt_t结构体数组，所以这幅图我有点困惑，还希望老师您解惑
2、这节课最后举了个例子，说cacheline是64Byte，bucket size是59Byte，然后取第一个元素老师您讲的是多取了1个字节，这个地方不是多取了5个字节吗？为什么是1个字节，我有点不太理解

 作者回复
1、书中的图，是最终的存储结构，即，每个elt_t指针其实指向的是连续内存中的一个元素，所以，这里的buckets*不是语言上的指向，而是最终真实线性内存的指向。你可以再读读ngx_hash_init这个函数的实现。确实是比较难懂的。

2、我的口误，呵呵，意思就是第1个比cacheline少的话，总有一个会占有2个cacheline。

2.在ngx_hash_t中，buckets是一个二重指针，所以我感觉这个关于书上7-10的ngx_hash_t的基本散列表的结构示意图有点疑问，buckets这个为什么不是先指向一个ngx_hash_elt_t的指针数组，之后再由ngx_hash_elt_t指向ngx_hash_elt_t结构，这个图片我个人感觉更类似于http://www.cnblogs.com/0x2D-0x22/p/4139805.html这个blog上画的图

 作者回复
buckets就是指向的一个指针数组，数组每个成员就是ngx_hash_elt_t*成员。我看了下你给的页面上的图，两幅图意思完全一致啊。