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 * 成员. 我看了下你给的页面上的图, 两幅图意思完全一致啊.
40 | Nginx 中最常用的容器: 红黑树
nginx 多个 worker 之间做进程通讯时, 进程在共享内存上使用红黑树来管理许多对象, 实际上在 nginx 的内存中也大量使用红黑树.
nginx 第二个非常常用的容器
红黑树
image.PNG
这样的二叉树有可能退化成右边的链表. 也是一个二叉查找树, 只是没有左子节点, 查找某个元素遍历复杂度 O(N). 而红黑树, 有一个重要的特点, 高度不会差太大, 不会超过两倍.
在 nginx 中描述每个红黑树, 有个数据结构
课后问题
1. 阿里云 cdn 到 Nginx 访问提示 504 错误, The gateway did not receive a timely response from the upstream server or application.
Powered by Tengine, 可能原因有哪些?
作者回复
从上面的 log 来看, 就是上游服务没有在超时范围内发回响应, 要么网络出问题, 要么上游服务出问题了.
2.nginx 的 share_dirt 也是用的红黑树吗
作者回复
你是说 openresty 吗? 是的
来源: http://www.jianshu.com/p/c2b923c6b6e0