上周有个做内核扩展的朋友问我想在自己的PostgreSQL插件里加一个缓存表记录会话级的状态用什么数据结构最省事我直接告诉他去翻src/backend/utils/hash/dynahash.c用现成的PostgreSQL动态哈希表。这不是我敷衍而是动态哈希表确实是PG内核里用得最广、最皮实的基础结构之一——共享缓冲区映射、锁管理器的主锁表、订阅关系的映射几乎凡是需要“按key快速查value”的地方底层都是它。但“会用”和“操作明白”完全是两回事。动态哈希表这六个字看着简单真到初始化参数、扩容机制、遍历游标、共享内存分配这些环节坑一个接一个。我这些年读源码加写扩展在它身上踩过的雷不在少数也见过不少同事在扩容时撞上莫名其妙的死循环。这篇文章就把“操作动态哈希表”这件事彻底拆开从它为什么设计成动态的到核心结构长什么样再到初始化、增查删改、遍历清理的完整代码路径最后附上我实际排查问题的经验。适合三类人写PostgreSQL扩展的C开发者、想入门数据库内核源码的读者、以及做性能问题定位时总在哈希表附近打转的运维朋友。1. 动态哈希表到底“动态”在哪1.1 一句话解释它的定位PostgreSQL里的动态哈希表通常叫dynahash是一套带自动扩容能力的哈希表实现。注意“自动扩容”这四个字——它不是创建时就把桶数定死而是随着元素增多底层桶数组可以按需翻倍扩张同时把已有数据重新分布到新桶里。这套机制对应的是经典的可扩展哈希思想。普通静态哈希表桶数固定一旦装满了就只能重建整张表代价极高而PG选择了两层索引结构来避免全量重建外层是一个“段目录”segment directory内层是真正的桶bucket。段目录可以动态追加新增桶时只需要处理部分受影响的分区不需要把全部元素搬到新表里。牺牲一点指针间接跳转的开销换来了接近线性的扩容成本这个设计放在数据库这种“数据量大、不能停服”的场景里非常划算。如果你的工作里接触过共享内存那基本绕不开它。举个实际例子共享缓冲区要快速判断一个页是否在缓冲池里用的就是一张以“表空间号文件号页号”为键的动态哈希表。表大小完全无法预估又不能为了极端情况一次性分配超大内存动态增长就成了必然选择。1.2 段目录与桶的两层结构要操作好这个结构先得把它的存储形态刻在脑子里。动态哈希表由三块内存构成HASHHDR全局头信息记录桶数、掩码、填充因子、元素总数这些元数据dir段目录也就是一个指针数组每个元素指向一段连续的桶每个桶内部是一条由元素节点组成的链表元素节点就是实际存放键和值的内存块。查询时哈希函数先算出key的哈希值再用HASHHDR里的high_mask、low_mask做位运算算出它落在第几个段、段内第几个桶最后沿链表找目标元素。扩容时段目录长度翻倍相应桶数增加旧桶的一部分元素会被重新哈希到新桶里。这里我习惯用一个比喻普通哈希表是固定车位的停车场满员了只能另找新场子把所有车挪过去动态哈希表则是可以旁边加盖新楼的停车场车多起来就多盖几个车位层已经停好的车最多挪动一小部分整体不用停工。理解两层结构是后面所有操作的基础尤其是你去看报错和排查性能瓶颈时脑子里要时刻挂着“现在查到了第几段、第几个桶”这根弦。2. 动手前先读懂三个关键结构体2.1 HASHCTL创建哈希表时传入的参数包dynahash的对外接口统一收敛在hash_create()这一个函数上签名是HTAB *hash_create(const char *tabname, long nelem, HASHCTL *info, int flags);nelem是你预估的表大小info是参数集合flags告诉内核info里哪些字段有效。HASHCTL 是第一个必须吃透的结构它里面常用的字段如下字段名作用需要配合的flagskeysize键的字节长度HASH_ELEMentrysize单个元素节点字节长度必须大于keysizeHASH_ELEMhash自定义哈希函数指针HASH_FUNCTIONkeycopy自定义键拷贝函数指针HASH_KEYCOPYalloc自定义内存分配函数指针HASH_ALLOCnum_partitions分区数用于并发控制HASH_PARTITIONmax_table_size表最大元素数上限HASH_TABLE_SIZEffactor填充因子每桶允许的元素数HASH_FFACTORhcctl共享内存场景下的HASHHDR指针HASH_SHARED_MEMflags是位掩码用的是HASH_ELEM、HASH_FUNCTION这类常量含义就是“我提供了某个字段”。大多数场景下只需要HASH_ELEM它意味着keysize和entrysize有效。如果不传HASH_FUNCTION内核默认使用tag_hash这也是PG通用哈希函数对二进制字节流做混合运算绝大多数场景直接够用。这里有一个新手容易搞混的点entrysize和keysize的区别。元素的前keysize字节就是键本身entrysize是整个元素占用的字节数所以必须满足entrysize keysize 你想要附带的数据大小。后面写扩展时我会用一个具体例子说明。2.2 HTAB与HASHHDR运行时的“表”与“头”当你创建完表拿到的是HTAB *相当于这张表的门面。HTAB里保存了指向上层所需的数据哈希函数指针hash、键拷贝函数keycopy、内存分配函数alloc以及真正核心的头结构指针hctl。HASHHDR是动态哈希表的发动机字段不多但每个都参与运算typedef struct HASHHDR { uint32 max_bucket; /* 当前最大桶编号 */ uint32 high_mask; /* 桶定位高位掩码 */ uint32 low_mask; /* 桶定位低位掩码 */ uint32 ffactor; /* 每桶期望元素数 */ uint32 nentries; /* 元素总数 */ uint32 nsegs; /* 段数量 */ uint32 dsizeseg; /* 每段包含的桶数 */ ... } HASHHDR;max_bucket、high_mask、low_mask三者共同决定了“哈希值落到哪个桶”。简单说当桶数小于等于某个阈值时用低位掩码决定桶号一旦扩容翻倍掩码跟着变化老数据自动落入新桶。nentries是已存元素数nsegs是段目录长度。在共享内存场景下HASHHDR本体可能也放在共享内存里多个进程通过指针访问同一份头信息这也是动态哈希表能在多进程间共享数据的关键前提。读源码时我建议先盯住HASHHDR里这几个掩码字段的变化函数也就是init_htab_calculations()。理解了掩码计算你对“为什么扩容之后只有一部分桶要重排”会一目了然后面排查死循环、异常慢查询时这个认知能帮你省半天时间。2.3 初始化时的内存估算创建哈希表不是一拍脑袋hash_create(name, 1024, ctl, flags)就完事了。nelem这个参数直接影响初始段数和桶数给小了会导致频繁扩容给大了浪费共享内存。PG专门提供了估算函数long hash_estimate_size(long num_entries, Size entrysize); long hash_select_dir_estimate_size(long num_entries);其中hash_estimate_size会根据你预估的元素数和元素大小返回需要分配的总字节数常和ShmemInitStruct配合使用用来在共享内存初始化阶段精确申请资源。hash_select_dir_estimate_size则是单独估算段目录大小的。我自己的习惯是nelem取实际业务峰值预估值的1.5倍ffactor保持默认值内核默认是1表示每桶期望1个元素或者设为2。如果设置HASH_FFACTOR时ffactor填过大桶数量会变少哈希冲突概率上升填得过小表会提前扩容rehash开销变多。这个参数不是越大越好需要结合平均链长来平衡。3. 操作动态哈希表从创建到增删查改3.1 一个可以直接抄的完整示例下面这段代码是我在某模拟项目中写过的缓存表操作场景是用会话ID作为键缓存对应的整型状态值。逻辑很简单但覆盖了动态哈希表最常用的全套操作。#include postgres.h #include utils/hsearch.h #include utils/memutils.h typedef struct SessionCacheEntry { uint32 session_id; /* 哈希键 */ int state_value; /* 缓存数据 */ } SessionCacheEntry; static HTAB *session_cache NULL; void init_session_cache(void) { HASHCTL ctl; memset(ctl, 0, sizeof(ctl)); ctl.keysize sizeof(uint32); ctl.entrysize sizeof(SessionCacheEntry); /* 给4个分区降低并发插入时的锁竞争 */ ctl.num_partitions 4; session_cache hash_create(session cache, 1024, ctl, HASH_ELEM | HASH_PARTITION); }这里有几个细节必须注意。第一keysize用的是sizeof(uint32)而不是4防止平台差异。第二entrysize是sizeof(SessionCacheEntry)这个结构体刚好是keysize加一个int字段布局正好匹配。第三我加了HASH_PARTITION并指定num_partitions 4这个参数后面讲并发时会展开。读值int get_session_state(uint32 session_id) { SessionCacheEntry *entry; uint32 key session_id; entry (SessionCacheEntry *) hash_search(session_cache, (void *) key, HASH_FIND, NULL); if (entry NULL) return -1; /* 没找到 */ return entry-state_value; }写值void set_session_state(uint32 session_id, int state_value) { SessionCacheEntry *entry; bool found; entry (SessionCacheEntry *) hash_search(session_cache, (void *) session_id, HASH_ENTER, found); if (!found) { /* 新插入的元素需要手动初始化数据字段 */ entry-state_value state_value; } else { /* 老元素直接更新 */ entry-state_value state_value; } }删除void remove_session_state(uint32 session_id) { (void) hash_search(session_cache, (void *) session_id, HASH_REMOVE, NULL); }注意hash_search返回的是void *指向元素节点的起始地址。由于节点头部就是键你可以直接(SessionCacheEntry *)强转后访问整块数据。键本身是嵌入式的不需要单独分配内存保存拷贝。3.2 深入HASH_ENTER/HASH_FIND/HASH_REMOVEhash_search的完整签名是void *hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr);action有四种取值HASH_FIND查找元素查不到返回NULL。HASH_ENTER查找并插入元素不存在就创建空元素节点存在就返回已有节点。HASH_ENTER_NULL和HASH_ENTER类似但共享内存不足时返回NULL而不是报错。HASH_REMOVE删除元素删除后返回被删除元素的指针但不等于指针还可继续使用它指向的是释放前的内存块。foundPtr是个输出参数告诉你本次操作是“找到了老元素”还是“新建了元素”。尤其是HASH_ENTER时如果不检查found直接把数据写入entry会把老数据覆盖掉。检查它之后才能决定是初始化还是更新。内核代码里大量使用这种模式。比如锁管理器为每个锁对象建条目时第一步就是hash_search(lock_table, locktag, HASH_ENTER, found)found为空就初始化锁计数否则直接累加。操作这套接口时“先ENTER再检查found”是标准姿势能有效避免重复键插入的数据错乱。另外一个容易被忽略的函数是hash_search_with_hash_value()它比hash_search多一个hashvalue参数。如果你调用前已经算好了键的哈希值传进去可以让哈希表避免内部二次计算高频操作路径上这个优化很可观。内核中很多查询场景会先用别的方式算好哈希再走这个变体接口。3.3 全表遍历与hash_seq_search动态哈希表没有像数组那样的固定下标遍历必须借助专用游标。完整流程是这个样子void dump_all_sessions(void) { HASH_SEQ_STATUS status; SessionCacheEntry *entry; hash_seq_init(status, session_cache); while ((entry (SessionCacheEntry *) hash_seq_search(status)) ! NULL) { elog(LOG, session %u - state %d, entry-session_id, entry-state_value); } }hash_seq_init初始化游标结构hash_seq_search每次返回一个元素指针遍历到底返回NULL。这里有个雷遍历过程中如果调用了hash_search并执行了HASH_REMOVE或HASH_ENTER可能会影响当前游标的稳定性。尤其是删除当前元素这类操作内核的HASH_REMOVE会把元素从当前桶链中摘掉但游标本身并不会自动跳过已经删除的节点。安全的做法有两种一种是一边遍历一边确认当前元素还有效再处理不要反复引用返回值另一种是干脆遍历时只收集key遍历结束后再统一删除。我踩过一次锅边遍历边按条件删除结果漏掉了相邻元素排查了半天才发现是删除操作改变了桶链结构后来改成两阶段处理问题消失。3.4 销毁与统计表不用了调用void *hash_destroy(HTAB *hashp);它会把所有元素节点、段目录、头信息全部释放。私有内存场景下如果哈希表创建在某个内存上下文里释放后这个内存上下文里的相关数据也不能再触碰。共享内存场景下hash_destroy只是清理逻辑状态物理内存由共享内存管理模型统一回收千万别手工free。想了解表容量和元素量内核还提供了几个工具接口hash_get_num_entries(HTAB *hashp)返回当前元素总数。hash_stats(const char *where, HTAB *hashp)打印哈希表的详细统计信息包括桶数、段数、元素数可以直接输出到日志。我在定位性能问题时习惯先在关键路径前后各打一次hash_get_num_entries确认表有没有膨胀到接近max_bucket的容量边界。如果元素数蹭蹭涨但桶数没跟上大概率是扩容没有触发或者触发了但高峰期rehash开销吃掉了CPU。4. 并发、内存与扩容高手才关心的三个侧面4.1 分区哈希表与并发写入数据库是多进程架构动态哈希表经常被多个后台进程同时读写。PG为它提供的并发保护策略是分区锁把整个哈希表按哈希值分成num_partitions个分区每个分区拥有独立的锁写入时只锁对应分区避免全局锁互斥。创建时指定HASH_PARTITION后后续使用hash_search时内核会根据key的哈希值自动选择一个分区在内部获得该分区的LWLock再执行操作。这个设计在元素量大、并发高的场景下收益明显。一个真实场景是锁管理器它默认把锁表切成多个分区不同进程争抢不同锁对象时不会挤在同一个锁上。分区数的选择建议参考CPU核数。设太少并发瓶颈还在设太多锁对象本身占用额外内存而且分区管理本身也有开销。我一般取max(4, cpu核数/4)这个经验值实测在16核机器上性能和资源占用比较均衡。4.2 内存上下文与共享内存的边界动态哈希表的内存分配有两个渠道私有内存和共享内存。私有内存场景最简单默认使用当前内存上下文分配元素节点。这带来一个隐蔽的坑如果你在TopMemoryContext里创建了表然后切到某个事务上下文里做插入元素节点会分配到当前上下文中。事务结束时这些节点被释放但哈希表头信息还在表就成了半残状态。操作动态哈希表之前务必用MemoryContextSwitchTo固定一个长生命周期的上下文保证所有节点都在同一个表面下。共享内存场景就要特殊处理。比如在shared_preload_libraries里加载的扩展中建表需要用ShmemInitStruct申请空间这时必须给HASHCTL.alloc传一个基于ShmemAlloc的回调函数否则默认分配器会尝试在进程本地内存里分配所有进程看到的内存地址就不一致了轻则数据错乱重则直接segfault。我写过的一个模拟项目里共享内存哈希表初始化时没有提供自定义alloc结果两个backend进程明明写的是同一个key查询却互相看不到数据。查了半天才发现元素被各自进程私有分配了这就是典型的“表头共享、数据不共享”。4.3 扩容机制与性能尖峰动态哈希表扩容是增量式的但并不是没有代价。当元素数量逼近阈值时内核会把段目录翻倍导致桶数量增加已有元素需要重新计算桶位置。这个rehash过程不是全部重排只影响一部分桶但单次触发的开销依然可能让当时正在写入的那个进程显著变慢表现为一次突发的CPU尖峰和写延迟抖动。要平滑这个尖峰能做的主要是两件事准确预估nelem让初始桶数尽量贴近业务峰值减少扩容次数适当调低ffactor让每个桶的期望元素少一点桶的装载率降低rehash时迁移的数据量也变小。代码路径上关注expand_table这个函数。每次扩容时它要分配新的段目录逐个迁移受影响桶里的元素。如果num_partitions较大扩容过程中分区锁的协调也更复杂这也是为什么并发极高且键数量大致可预估的场景有人会放弃dynahash改用PG源码里后来加入的simplehash——后者基于固定数组加开放寻址完全不支持动态扩容但纯内存场景下性能和可预测性都好很多。用哪个核心就看你的表到底能不能预判大小。5. 实际排查中遇到的典型问题5.1 常见异常现象速查我把过去几年在动态哈希表上遇到的典型问题做了个表按“现象—原因—解法”列出来方便对照。现象可能原因解决建议插入时进程卡死或CPU飙升哈希值低位分布不均导致rehash反复迁移同一个桶形成无限循环检查自定义哈希函数优先换用tag_hash提高ffactor降低桶满载率共享内存表多进程数据不一致没提供alloc回调元素分配在进程私有内存使用基于ShmemAlloc的分配回调或用HASH_SHARED_MEM初始化遍历时元素丢失或重复遍历中插入/删除元素破坏了桶链两阶段遍历或使用hash_seq_search的HASH_REMOVE参数并在回调里正确处理游标表一直不长但内存持续上涨元素被分配到长生命周期内存上下文定位插入时的CurrentMemoryContext给表绑定专用上下文并发写入性能随表变大明显下降分区数设置不合理或桶数膨胀检查num_partitions与CPU核数匹配度调用hash_stats观察桶装载状态报错out of shared memory共享内存预留不足调大shared_preload_libraries中的预留量重新估算hash_estimate_size5.2 一个典型的死循环案例分析某次我在内核调试时遇到一个插入操作挂死的现象后端的堆栈停在hash_search里CPU占用100%等多久都不返回。初步怀疑桶链表有环形结构。用gdb挂上去看发现hash_search内部在不断执行element element-next但始终回到同一个节点。后来发现根因出在哈希函数上当时自定义的哈希函数对某些key只产生了低位变化而高位完全一样rehash之后所有元素还是挤在同一个桶里。ffactor又设了1桶满后反复扩容扩容又触发rehash可哈希函数的高位熵不足每次rehash仍然把大量元素送回同一个桶陷入活锁。解决方式是放弃自定义哈希直接用tag_hash处理二进制键同时把ffactor从1调成2问题立刻消失。这个教训告诉我自定义哈希函数必须覆盖键的各个字节位尤其是数值小的键否则你省掉的那点哈希计算时间会在扩容rehash时十倍百倍地还回来。5.3 调试技巧看穿哈希表内部状态黑盒测试动态哈希表太憋屈了我强烈建议在开发环境里临时写一个辅助函数直接打印哈希表内部关键状态void debug_dump_hash_state(HTAB *hashp) { HASHHDR *hctl hashp-hctl; elog(LOG, nentries%u max_bucket%u high_mask0x%X low_mask0x%X nsegs%u ffactor%u, hctl-nentries, hctl-max_bucket, hctl-high_mask, hctl-low_mask, hctl-nsegs, hctl-ffactor); }通过观察nentries和max_bucket的比值你能直观判断表是否长期处于高负载状态。如果nentries接近max_bucket * ffactor说明即将触发扩容如果高层级频繁变化就要回头检查哈希分布。排查内存问题时hashp-dir里的段指针也可以逐一打印确认每段的桶地址是否落在预期的共享内存区域。这个辅助函数不用上线但调试阶段能省掉大量反复猜测的时间。最后分享一个排查心得有一次我定位一个线上会话退出变慢的问题最后跟到exit_time附近有个哈希表清理逻辑。用hash_stats一看表里元素数快顶到上限而且nentries一直在涨却不触发扩容因为HASHCTL里我传了max_table_size限死了上限。动态哈希表默认不限制最大元素数当内存不可控时才应该设置这个参数。那次的教训是不要随手加限制尤其别把max_table_size和nelem混为一谈。前者是硬上限达到后插入直接报错后者只是估算参数。这个细节文档里写得很隐晦代码注释也只有一行真踩起来特别疼。操作动态哈希表这件事本质上就是和三个角色打交道HASHCTL决定它怎么配HTAB/HASHHDR决定它怎么存hash_search/hash_seq_search决定它怎么用。把这三层都理顺了不管是看dynahash.c源码还是写自己的缓存模块都会顺很多。如果再遇到哈希相关的问题建议先看hctl-nentries和max_bucket再判断去哪儿找原因方向对了问题往往就解决了一半。 
长河君 · 2026/10/21 17:33:58 · 阅读 1.2k PostgreSQL动态哈希表完全指南：原理、使用与踩坑实践
上周有个做内核扩展的朋友问我想在自己的PostgreSQL插件里加一个缓存表记录会话级的状态用什么数据结构最省事我直接告诉他去翻src/backend/utils/hash/dynahash.c用现成的PostgreSQL动态哈希表。这不是我敷衍而是动态哈希表确实是PG内核里用得最广、最皮实的基础结构之一——共享缓冲区映射、锁管理器的主锁表、订阅关系的映射几乎凡是需要“按key快速查value”的地方底层都是它。但“会用”和“操作明白”完全是两回事。动态哈希表这六个字看着简单真到初始化参数、扩容机制、遍历游标、共享内存分配这些环节坑一个接一个。我这些年读源码加写扩展在它身上踩过的雷不在少数也见过不少同事在扩容时撞上莫名其妙的死循环。这篇文章就把“操作动态哈希表”这件事彻底拆开从它为什么设计成动态的到核心结构长什么样再到初始化、增查删改、遍历清理的完整代码路径最后附上我实际排查问题的经验。适合三类人写PostgreSQL扩展的C开发者、想入门数据库内核源码的读者、以及做性能问题定位时总在哈希表附近打转的运维朋友。1. 动态哈希表到底“动态”在哪1.1 一句话解释它的定位PostgreSQL里的动态哈希表通常叫dynahash是一套带自动扩容能力的哈希表实现。注意“自动扩容”这四个字——它不是创建时就把桶数定死而是随着元素增多底层桶数组可以按需翻倍扩张同时把已有数据重新分布到新桶里。这套机制对应的是经典的可扩展哈希思想。普通静态哈希表桶数固定一旦装满了就只能重建整张表代价极高而PG选择了两层索引结构来避免全量重建外层是一个“段目录”segment directory内层是真正的桶bucket。段目录可以动态追加新增桶时只需要处理部分受影响的分区不需要把全部元素搬到新表里。牺牲一点指针间接跳转的开销换来了接近线性的扩容成本这个设计放在数据库这种“数据量大、不能停服”的场景里非常划算。如果你的工作里接触过共享内存那基本绕不开它。举个实际例子共享缓冲区要快速判断一个页是否在缓冲池里用的就是一张以“表空间号文件号页号”为键的动态哈希表。表大小完全无法预估又不能为了极端情况一次性分配超大内存动态增长就成了必然选择。1.2 段目录与桶的两层结构要操作好这个结构先得把它的存储形态刻在脑子里。动态哈希表由三块内存构成HASHHDR全局头信息记录桶数、掩码、填充因子、元素总数这些元数据dir段目录也就是一个指针数组每个元素指向一段连续的桶每个桶内部是一条由元素节点组成的链表元素节点就是实际存放键和值的内存块。查询时哈希函数先算出key的哈希值再用HASHHDR里的high_mask、low_mask做位运算算出它落在第几个段、段内第几个桶最后沿链表找目标元素。扩容时段目录长度翻倍相应桶数增加旧桶的一部分元素会被重新哈希到新桶里。这里我习惯用一个比喻普通哈希表是固定车位的停车场满员了只能另找新场子把所有车挪过去动态哈希表则是可以旁边加盖新楼的停车场车多起来就多盖几个车位层已经停好的车最多挪动一小部分整体不用停工。理解两层结构是后面所有操作的基础尤其是你去看报错和排查性能瓶颈时脑子里要时刻挂着“现在查到了第几段、第几个桶”这根弦。2. 动手前先读懂三个关键结构体2.1 HASHCTL创建哈希表时传入的参数包dynahash的对外接口统一收敛在hash_create()这一个函数上签名是HTAB *hash_create(const char *tabname, long nelem, HASHCTL *info, int flags);nelem是你预估的表大小info是参数集合flags告诉内核info里哪些字段有效。HASHCTL 是第一个必须吃透的结构它里面常用的字段如下字段名作用需要配合的flagskeysize键的字节长度HASH_ELEMentrysize单个元素节点字节长度必须大于keysizeHASH_ELEMhash自定义哈希函数指针HASH_FUNCTIONkeycopy自定义键拷贝函数指针HASH_KEYCOPYalloc自定义内存分配函数指针HASH_ALLOCnum_partitions分区数用于并发控制HASH_PARTITIONmax_table_size表最大元素数上限HASH_TABLE_SIZEffactor填充因子每桶允许的元素数HASH_FFACTORhcctl共享内存场景下的HASHHDR指针HASH_SHARED_MEMflags是位掩码用的是HASH_ELEM、HASH_FUNCTION这类常量含义就是“我提供了某个字段”。大多数场景下只需要HASH_ELEM它意味着keysize和entrysize有效。如果不传HASH_FUNCTION内核默认使用tag_hash这也是PG通用哈希函数对二进制字节流做混合运算绝大多数场景直接够用。这里有一个新手容易搞混的点entrysize和keysize的区别。元素的前keysize字节就是键本身entrysize是整个元素占用的字节数所以必须满足entrysize keysize 你想要附带的数据大小。后面写扩展时我会用一个具体例子说明。2.2 HTAB与HASHHDR运行时的“表”与“头”当你创建完表拿到的是HTAB *相当于这张表的门面。HTAB里保存了指向上层所需的数据哈希函数指针hash、键拷贝函数keycopy、内存分配函数alloc以及真正核心的头结构指针hctl。HASHHDR是动态哈希表的发动机字段不多但每个都参与运算typedef struct HASHHDR { uint32 max_bucket; /* 当前最大桶编号 */ uint32 high_mask; /* 桶定位高位掩码 */ uint32 low_mask; /* 桶定位低位掩码 */ uint32 ffactor; /* 每桶期望元素数 */ uint32 nentries; /* 元素总数 */ uint32 nsegs; /* 段数量 */ uint32 dsizeseg; /* 每段包含的桶数 */ ... } HASHHDR;max_bucket、high_mask、low_mask三者共同决定了“哈希值落到哪个桶”。简单说当桶数小于等于某个阈值时用低位掩码决定桶号一旦扩容翻倍掩码跟着变化老数据自动落入新桶。nentries是已存元素数nsegs是段目录长度。在共享内存场景下HASHHDR本体可能也放在共享内存里多个进程通过指针访问同一份头信息这也是动态哈希表能在多进程间共享数据的关键前提。读源码时我建议先盯住HASHHDR里这几个掩码字段的变化函数也就是init_htab_calculations()。理解了掩码计算你对“为什么扩容之后只有一部分桶要重排”会一目了然后面排查死循环、异常慢查询时这个认知能帮你省半天时间。2.3 初始化时的内存估算创建哈希表不是一拍脑袋hash_create(name, 1024, ctl, flags)就完事了。nelem这个参数直接影响初始段数和桶数给小了会导致频繁扩容给大了浪费共享内存。PG专门提供了估算函数long hash_estimate_size(long num_entries, Size entrysize); long hash_select_dir_estimate_size(long num_entries);其中hash_estimate_size会根据你预估的元素数和元素大小返回需要分配的总字节数常和ShmemInitStruct配合使用用来在共享内存初始化阶段精确申请资源。hash_select_dir_estimate_size则是单独估算段目录大小的。我自己的习惯是nelem取实际业务峰值预估值的1.5倍ffactor保持默认值内核默认是1表示每桶期望1个元素或者设为2。如果设置HASH_FFACTOR时ffactor填过大桶数量会变少哈希冲突概率上升填得过小表会提前扩容rehash开销变多。这个参数不是越大越好需要结合平均链长来平衡。3. 操作动态哈希表从创建到增删查改3.1 一个可以直接抄的完整示例下面这段代码是我在某模拟项目中写过的缓存表操作场景是用会话ID作为键缓存对应的整型状态值。逻辑很简单但覆盖了动态哈希表最常用的全套操作。#include postgres.h #include utils/hsearch.h #include utils/memutils.h typedef struct SessionCacheEntry { uint32 session_id; /* 哈希键 */ int state_value; /* 缓存数据 */ } SessionCacheEntry; static HTAB *session_cache NULL; void init_session_cache(void) { HASHCTL ctl; memset(ctl, 0, sizeof(ctl)); ctl.keysize sizeof(uint32); ctl.entrysize sizeof(SessionCacheEntry); /* 给4个分区降低并发插入时的锁竞争 */ ctl.num_partitions 4; session_cache hash_create(session cache, 1024, ctl, HASH_ELEM | HASH_PARTITION); }这里有几个细节必须注意。第一keysize用的是sizeof(uint32)而不是4防止平台差异。第二entrysize是sizeof(SessionCacheEntry)这个结构体刚好是keysize加一个int字段布局正好匹配。第三我加了HASH_PARTITION并指定num_partitions 4这个参数后面讲并发时会展开。读值int get_session_state(uint32 session_id) { SessionCacheEntry *entry; uint32 key session_id; entry (SessionCacheEntry *) hash_search(session_cache, (void *) key, HASH_FIND, NULL); if (entry NULL) return -1; /* 没找到 */ return entry-state_value; }写值void set_session_state(uint32 session_id, int state_value) { SessionCacheEntry *entry; bool found; entry (SessionCacheEntry *) hash_search(session_cache, (void *) session_id, HASH_ENTER, found); if (!found) { /* 新插入的元素需要手动初始化数据字段 */ entry-state_value state_value; } else { /* 老元素直接更新 */ entry-state_value state_value; } }删除void remove_session_state(uint32 session_id) { (void) hash_search(session_cache, (void *) session_id, HASH_REMOVE, NULL); }注意hash_search返回的是void *指向元素节点的起始地址。由于节点头部就是键你可以直接(SessionCacheEntry *)强转后访问整块数据。键本身是嵌入式的不需要单独分配内存保存拷贝。3.2 深入HASH_ENTER/HASH_FIND/HASH_REMOVEhash_search的完整签名是void *hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr);action有四种取值HASH_FIND查找元素查不到返回NULL。HASH_ENTER查找并插入元素不存在就创建空元素节点存在就返回已有节点。HASH_ENTER_NULL和HASH_ENTER类似但共享内存不足时返回NULL而不是报错。HASH_REMOVE删除元素删除后返回被删除元素的指针但不等于指针还可继续使用它指向的是释放前的内存块。foundPtr是个输出参数告诉你本次操作是“找到了老元素”还是“新建了元素”。尤其是HASH_ENTER时如果不检查found直接把数据写入entry会把老数据覆盖掉。检查它之后才能决定是初始化还是更新。内核代码里大量使用这种模式。比如锁管理器为每个锁对象建条目时第一步就是hash_search(lock_table, locktag, HASH_ENTER, found)found为空就初始化锁计数否则直接累加。操作这套接口时“先ENTER再检查found”是标准姿势能有效避免重复键插入的数据错乱。另外一个容易被忽略的函数是hash_search_with_hash_value()它比hash_search多一个hashvalue参数。如果你调用前已经算好了键的哈希值传进去可以让哈希表避免内部二次计算高频操作路径上这个优化很可观。内核中很多查询场景会先用别的方式算好哈希再走这个变体接口。3.3 全表遍历与hash_seq_search动态哈希表没有像数组那样的固定下标遍历必须借助专用游标。完整流程是这个样子void dump_all_sessions(void) { HASH_SEQ_STATUS status; SessionCacheEntry *entry; hash_seq_init(status, session_cache); while ((entry (SessionCacheEntry *) hash_seq_search(status)) ! NULL) { elog(LOG, session %u - state %d, entry-session_id, entry-state_value); } }hash_seq_init初始化游标结构hash_seq_search每次返回一个元素指针遍历到底返回NULL。这里有个雷遍历过程中如果调用了hash_search并执行了HASH_REMOVE或HASH_ENTER可能会影响当前游标的稳定性。尤其是删除当前元素这类操作内核的HASH_REMOVE会把元素从当前桶链中摘掉但游标本身并不会自动跳过已经删除的节点。安全的做法有两种一种是一边遍历一边确认当前元素还有效再处理不要反复引用返回值另一种是干脆遍历时只收集key遍历结束后再统一删除。我踩过一次锅边遍历边按条件删除结果漏掉了相邻元素排查了半天才发现是删除操作改变了桶链结构后来改成两阶段处理问题消失。3.4 销毁与统计表不用了调用void *hash_destroy(HTAB *hashp);它会把所有元素节点、段目录、头信息全部释放。私有内存场景下如果哈希表创建在某个内存上下文里释放后这个内存上下文里的相关数据也不能再触碰。共享内存场景下hash_destroy只是清理逻辑状态物理内存由共享内存管理模型统一回收千万别手工free。想了解表容量和元素量内核还提供了几个工具接口hash_get_num_entries(HTAB *hashp)返回当前元素总数。hash_stats(const char *where, HTAB *hashp)打印哈希表的详细统计信息包括桶数、段数、元素数可以直接输出到日志。我在定位性能问题时习惯先在关键路径前后各打一次hash_get_num_entries确认表有没有膨胀到接近max_bucket的容量边界。如果元素数蹭蹭涨但桶数没跟上大概率是扩容没有触发或者触发了但高峰期rehash开销吃掉了CPU。4. 并发、内存与扩容高手才关心的三个侧面4.1 分区哈希表与并发写入数据库是多进程架构动态哈希表经常被多个后台进程同时读写。PG为它提供的并发保护策略是分区锁把整个哈希表按哈希值分成num_partitions个分区每个分区拥有独立的锁写入时只锁对应分区避免全局锁互斥。创建时指定HASH_PARTITION后后续使用hash_search时内核会根据key的哈希值自动选择一个分区在内部获得该分区的LWLock再执行操作。这个设计在元素量大、并发高的场景下收益明显。一个真实场景是锁管理器它默认把锁表切成多个分区不同进程争抢不同锁对象时不会挤在同一个锁上。分区数的选择建议参考CPU核数。设太少并发瓶颈还在设太多锁对象本身占用额外内存而且分区管理本身也有开销。我一般取max(4, cpu核数/4)这个经验值实测在16核机器上性能和资源占用比较均衡。4.2 内存上下文与共享内存的边界动态哈希表的内存分配有两个渠道私有内存和共享内存。私有内存场景最简单默认使用当前内存上下文分配元素节点。这带来一个隐蔽的坑如果你在TopMemoryContext里创建了表然后切到某个事务上下文里做插入元素节点会分配到当前上下文中。事务结束时这些节点被释放但哈希表头信息还在表就成了半残状态。操作动态哈希表之前务必用MemoryContextSwitchTo固定一个长生命周期的上下文保证所有节点都在同一个表面下。共享内存场景就要特殊处理。比如在shared_preload_libraries里加载的扩展中建表需要用ShmemInitStruct申请空间这时必须给HASHCTL.alloc传一个基于ShmemAlloc的回调函数否则默认分配器会尝试在进程本地内存里分配所有进程看到的内存地址就不一致了轻则数据错乱重则直接segfault。我写过的一个模拟项目里共享内存哈希表初始化时没有提供自定义alloc结果两个backend进程明明写的是同一个key查询却互相看不到数据。查了半天才发现元素被各自进程私有分配了这就是典型的“表头共享、数据不共享”。4.3 扩容机制与性能尖峰动态哈希表扩容是增量式的但并不是没有代价。当元素数量逼近阈值时内核会把段目录翻倍导致桶数量增加已有元素需要重新计算桶位置。这个rehash过程不是全部重排只影响一部分桶但单次触发的开销依然可能让当时正在写入的那个进程显著变慢表现为一次突发的CPU尖峰和写延迟抖动。要平滑这个尖峰能做的主要是两件事准确预估nelem让初始桶数尽量贴近业务峰值减少扩容次数适当调低ffactor让每个桶的期望元素少一点桶的装载率降低rehash时迁移的数据量也变小。代码路径上关注expand_table这个函数。每次扩容时它要分配新的段目录逐个迁移受影响桶里的元素。如果num_partitions较大扩容过程中分区锁的协调也更复杂这也是为什么并发极高且键数量大致可预估的场景有人会放弃dynahash改用PG源码里后来加入的simplehash——后者基于固定数组加开放寻址完全不支持动态扩容但纯内存场景下性能和可预测性都好很多。用哪个核心就看你的表到底能不能预判大小。5. 实际排查中遇到的典型问题5.1 常见异常现象速查我把过去几年在动态哈希表上遇到的典型问题做了个表按“现象—原因—解法”列出来方便对照。现象可能原因解决建议插入时进程卡死或CPU飙升哈希值低位分布不均导致rehash反复迁移同一个桶形成无限循环检查自定义哈希函数优先换用tag_hash提高ffactor降低桶满载率共享内存表多进程数据不一致没提供alloc回调元素分配在进程私有内存使用基于ShmemAlloc的分配回调或用HASH_SHARED_MEM初始化遍历时元素丢失或重复遍历中插入/删除元素破坏了桶链两阶段遍历或使用hash_seq_search的HASH_REMOVE参数并在回调里正确处理游标表一直不长但内存持续上涨元素被分配到长生命周期内存上下文定位插入时的CurrentMemoryContext给表绑定专用上下文并发写入性能随表变大明显下降分区数设置不合理或桶数膨胀检查num_partitions与CPU核数匹配度调用hash_stats观察桶装载状态报错out of shared memory共享内存预留不足调大shared_preload_libraries中的预留量重新估算hash_estimate_size5.2 一个典型的死循环案例分析某次我在内核调试时遇到一个插入操作挂死的现象后端的堆栈停在hash_search里CPU占用100%等多久都不返回。初步怀疑桶链表有环形结构。用gdb挂上去看发现hash_search内部在不断执行element element-next但始终回到同一个节点。后来发现根因出在哈希函数上当时自定义的哈希函数对某些key只产生了低位变化而高位完全一样rehash之后所有元素还是挤在同一个桶里。ffactor又设了1桶满后反复扩容扩容又触发rehash可哈希函数的高位熵不足每次rehash仍然把大量元素送回同一个桶陷入活锁。解决方式是放弃自定义哈希直接用tag_hash处理二进制键同时把ffactor从1调成2问题立刻消失。这个教训告诉我自定义哈希函数必须覆盖键的各个字节位尤其是数值小的键否则你省掉的那点哈希计算时间会在扩容rehash时十倍百倍地还回来。5.3 调试技巧看穿哈希表内部状态黑盒测试动态哈希表太憋屈了我强烈建议在开发环境里临时写一个辅助函数直接打印哈希表内部关键状态void debug_dump_hash_state(HTAB *hashp) { HASHHDR *hctl hashp-hctl; elog(LOG, nentries%u max_bucket%u high_mask0x%X low_mask0x%X nsegs%u ffactor%u, hctl-nentries, hctl-max_bucket, hctl-high_mask, hctl-low_mask, hctl-nsegs, hctl-ffactor); }通过观察nentries和max_bucket的比值你能直观判断表是否长期处于高负载状态。如果nentries接近max_bucket * ffactor说明即将触发扩容如果高层级频繁变化就要回头检查哈希分布。排查内存问题时hashp-dir里的段指针也可以逐一打印确认每段的桶地址是否落在预期的共享内存区域。这个辅助函数不用上线但调试阶段能省掉大量反复猜测的时间。最后分享一个排查心得有一次我定位一个线上会话退出变慢的问题最后跟到exit_time附近有个哈希表清理逻辑。用hash_stats一看表里元素数快顶到上限而且nentries一直在涨却不触发扩容因为HASHCTL里我传了max_table_size限死了上限。动态哈希表默认不限制最大元素数当内存不可控时才应该设置这个参数。那次的教训是不要随手加限制尤其别把max_table_size和nelem混为一谈。前者是硬上限达到后插入直接报错后者只是估算参数。这个细节文档里写得很隐晦代码注释也只有一行真踩起来特别疼。操作动态哈希表这件事本质上就是和三个角色打交道HASHCTL决定它怎么配HTAB/HASHHDR决定它怎么存hash_search/hash_seq_search决定它怎么用。把这三层都理顺了不管是看dynahash.c源码还是写自己的缓存模块都会顺很多。如果再遇到哈希相关的问题建议先看hctl-nentries和max_bucket再判断去哪儿找原因方向对了问题往往就解决了一半。