如果你打开过PostgreSQL的源码一定会在很多核心模块里反复撞见同一个东西——动态哈希表。锁管理器、系统缓存、统计信息、后台进程之间的状态共享几乎处处都有它的影子。数据结构的名字在源码里叫dynahash文件和接口都带着hash_前缀平时大家讨论PG内核时很少把它单独拎出来讲但真要读源码或者自己写扩展模块它绝对绕不过去。这篇文章就围绕“操作动态哈希表”展开想把三件事讲清楚它为什么是动态的、整体结构长什么样、以及在实际编码里怎么初始化、怎么查、怎么插、怎么删、怎么遍历。顺带把我踩过的坑和排查思路也一并整理出来。适合正在啃PG源码的开发者、准备写自定义扩展或者在自己的工具里复刻这套设计的人参考。1. 为什么PostgreSQL需要一张“会变大的哈希表”1.1 “动态”和非动态的区别普通的哈希表在创建时就把桶数组大小定死了元素放满了就得扩容而扩容通常意味着把所有已有元素重新计算哈希值再搬一次家。这种做法对于静态数据还好对于数据库这种时刻都在读写、并发量很高的场景就不太合适。因为全量rehash会引起明显的停顿停顿期间其他会话都要等这在数据库内核里是不可接受的。PostgreSQL自研的这套动态哈希表不一样。它的桶数组也会变大但不需要一次性把全表重建。具体做法是把“扩容”拆成一个个小步骤当某个桶的链过长、整体负载达到阈值时只挑一个合适的桶做分裂操作把这个桶里的元素按新哈希值重新分配到两个新桶里其他桶完全不动。这种渐进的、按需触发的扩容方式保证了哈希表在元素量增长过程中的性能曲线相对平稳不会出现“突然卡一下”的抖动。从使用者的角度看动态哈希表还有一个更直观的特点你创建它的时候不需要精确预估元素数量给定一个大致的量级即可它会根据实际插入情况自动调整。而且它支持按需销毁、按内存上下文统一管理生命周期这和其他语言里那种需要手动管理一切的哈希容器完全是两种体验。1.2 动态哈希表在PostgreSQL里管什么用如果你在PG内核里搜索hash_create的调用点会发现一个有趣的规律凡是需要按某个键快速定位且数量经常变化的数据几乎都交给了动态哈希表。比如锁管理器每个数据库对象、每个事务的锁信息都需要被快速查找和更新并发访问量极高并且锁的数量会随着业务动态增减。再比如关系缓存表结构Relation缓存需要按照oid快速找到对应缓存项表多了缓存项就多删表了缓存项又要及时清掉。还有统计信息、后台逻辑复制、并行查询的共享状态等统一都靠动态哈希表来承载。我自己常用的一句话是凡是要做“键值对存储”且数量不可预知的内核级场景PG的动态哈希表就是默认答案。它之所以被广泛使用不是因为别的哈希实现不好而是因为这套接口在内核环境下考虑得非常周全——内存怎么管、锁怎么加、键怎么比较、元素怎么对齐全都替你处理好了。理解了它读PG源码时至少能少卡壳一半。2. 动态哈希表的核心结构与初始化参数2.1 三层核心结构动态哈希表并不复杂核心结构可以拆成三层看待。最上层是HTAB这是使用者手里拿到的唯一对象。它代表整张哈希表里面保存了哈希表的元数据、桶数组指针、锁分区状态等信息。你通过hash_create拿到的是一个HTAB指针之后所有操作都围绕它展开。中间层是桶数组也就是HashBucket数组。桶的数量不是一成不变的当负载过高时桶数组会扩容同时把某个已存在的桶分裂成两个。每个桶会指向一个元素链表的头节点哈希值相同的元素会串在这个链表上。最底层是HASHELEMENT代表一个个具体的哈希表元素。每个元素内部包含两部分一部分是键key另一部分是使用者自定义的数据区entry。有点类似把“键”和“值”打包在同一个内存块里而不是通过指针分开存。这样做的最大好处是内存紧凑cache命中率高遍历链表时的局部性也更好。锁分区不是单独的结构它是在桶数组基础上做的逻辑划分。创建哈希表时如果指定了分区数系统会把连续的桶划分到若干个分区里每个分区有独立的锁这样不同分区之间的并发操作可以互不阻塞。2.2 hash_create参数解析先看最常用的创建接口HTAB *hash_create(const char *tabname, long nelem, HASHCTL *info, int flags);tabname就是这张哈希表的名称主要用于错误信息和统计数据输出起个能辨认的名字就行。nelem是你预期这张表最终大约会有多少个元素。注意是“大约”动态哈希表会依据这个值估算初始桶数组的大小但不会因为后续元素数超出预期就报错它会自动扩展。HASHCTL结构体是真正的核心参数它定义在utils/hsearch.h里。常用的字段不多typedef struct HASHCTL { long keysize; /* 键的大小单位是字节 */ long entrysize; /* 整个元素包含键的大小 */ long num_partitions; /* 锁分区数 */ long max_table_size; /* 最大元素数0表示不限制 */ long ffactor; /* 填充因子默认是2 */ Size initTable; /* 固定初始桶数一般不设 */ MemoryContext hcxt; /* 元素分配使用的内存上下文 */ HashFunction hash; /* 自定义哈希函数 */ } HASHCTL;flags参数告诉哈希表怎么解释HASHCTL里的字段。比如设置HASH_ELEM表示keysize和entrysize有效HASH_BLOBS表示键是二进制数据块直接用默认哈希函数计算HASH_FUNCTION表示使用自定义哈希函数HASH_CONTEXT表示元素分配到指定内存上下文HASH_PARTITION表示启用分锁分区。这里有一个容易混淆的点HASH_ELEM并不是“按元素分配”的意思而是“元素尺寸已知”的意思。如果你不传HASH_ELEM系统就不知道每个元素占多大自然没法做后续的分配和寻址。所以几乎所有调用场景都要带上它。2.3 内存上下文的配合方式PostgreSQL有一个贯穿全内核的基础设施叫内存上下文MemoryContext你可以把它理解成一种树状的内存池。每个内存上下文都可以被整体重置或删除里面分配的内存随之释放这个机制大大简化了内存管理。动态哈希表对内存上下文的配合非常自然。创建时可以指定元素分配在哪个上下文里也可以不指定这时它会默认使用CurrentMemoryContext。当这个上下文被重置时哈希表里的元素内存会一起消失。但注意HTAB本身的管理结构并不一定跟着释放你需要调用hash_destroy来显式销毁整张表。实际开发中我一直遵循一条铁律哪个内存上下文管理哈希表元素就让它和哈希表的生命周期完全一致。不要尝试跨上下文长期保存哈希表的某个元素指针因为内存上下文一reset那个指针立刻变成悬空指针调试起来相当痛苦。3. 操作动态哈希表从初始化到增删查改3.1 场景设定建立一个会话状态表光讲结构容易飘我拿一个实际场景串一遍。假设我要写一个PostgreSQL扩展用来在后台进程里跟踪当前所有客户端会话的状态。每个会话有唯一IDint类型需要记录用户名、登录时间、当前执行中的查询数量。会话数量不可预估少则几个多则几千上万个。这正好是动态哈希表的典型使用场景。先定义元素结构体#include postgres.h #include utils/hsearch.h #include utils/timestamp.h typedef struct SessionEntry { int session_id; /* 键会话ID */ char user_name[32]; /* 用户名 */ TimestampTz login_time; /* 登录时间 */ int active_queries; /* 活动查询数 */ } SessionEntry;注意元素结构体的第一个字段应当和键类型保持一致而且keysize小于等于entrysize。PG的哈希查找定位元素时会直接拿传入的键值和元素起始地址处的字节做比较这个设计让键比较非常快但也要求你不能把键字段藏在结构体内部偏移的位置。3.2 初始化代码接下来初始化哈希表。这里我默认当前进程有个独立的内存上下文session_ctx专门存放会话数据HASHCTL ctl; HTAB *session_tab; MemoryContext old_ctx; old_ctx MemoryContextSwitchTo(session_ctx); memset(ctl, 0, sizeof(ctl)); ctl.keysize sizeof(int); /* 键是int类型 */ ctl.entrysize sizeof(SessionEntry); /* 元素结构体 */ ctl.hcxt session_ctx; /* 元素分配到会话上下文 */ session_tab hash_create(session status table, 1024, /* 预期最终约1024个会话 */ ctl, HASH_ELEM | HASH_BLOBS | HASH_CONTEXT); MemoryContextSwitchTo(old_ctx);这里有几个细节值得说明。HASH_BLOBS的意思是键是一块不知道内部结构的二进制数据用系统提供的默认哈希函数来散列。因为键是int类型直接按二进制处理完全没问题。如果你的键是字符串也可以用HASH_BLOBS它会把整个keysize的字节送进哈希函数。1024这个数字只是估值会话数超过它系统会自动扩展不必担心初始化时给少了。HASH_CONTEXT让系统把每个新元素的内存从session_ctx里分配这样我以后只要重置整个session_ctx所有会话记录自动消失。3.3 查找、插入、删除的核心调用动态哈希表的所有操作基本都收敛到一个函数hash_search。它用一个action参数区分三种行为。查找一个会话int key 42; bool found; SessionEntry *entry; entry hash_search(session_tab, key, HASH_FIND, found); if (!found) { /* 这个会话不存在 */ } else { /* entry指向会话数据直接读取字段即可 */ }插入一个新会话int key 42; bool found; SessionEntry *entry; entry hash_search(session_tab, key, HASH_ENTER, found); if (!found) { /* 新插入的元素需要手动初始化字段 */ entry-session_id key; strlcpy(entry-user_name, some_user, sizeof(entry-user_name)); entry-login_time GetCurrentTimestamp(); entry-active_queries 0; } else { /* 已经存在更新字段 */ entry-active_queries; }这里有一个非常容易误解的地方HASH_ENTER不是“只插入不查找”它的语义是“确保这个键在表里存在如果不存在就插入如果存在就返回已有元素”。所以found参数告诉你到底是不是刚创建的。拿到新元素后系统不会帮你初始化数据区所有字段都要自己填。删除一个会话int key 42; bool found; SessionEntry *entry; entry hash_search(session_tab, key, HASH_REMOVE, found); if (entry ! NULL) { /* 删除前的清理工作比如释放元素里指向的其他资源 */ }HASH_REMOVE返回被移除的元素指针如果键不存在则返回NULL。需要注意返回的指针在函数返回后立刻失效因为该元素的内存已经被释放了。如果你在元素里保存了额外malloc的指针必须在HASH_REMOVE调用之前先从entry取出来处理。3.4 顺序遍历与清理策略操作动态哈希表不只有单点增删有时需要遍历整张表。比如会话表需要定期清理超时会话就要把每个元素都看一眼。PG用HASH_SEQ_STATUS配合hash_seq_init和hash_seq_search完成顺序遍历HASH_SEQ_STATUS seq; SessionEntry *entry; hash_seq_init(seq, session_tab); while ((entry hash_seq_search(seq)) ! NULL) { /* 处理每一个会话 */ if (entry-active_queries 0 TimestampDifferenceExceeds(entry-login_time, GetCurrentTimestamp(), 3600)) { /* 找到要清理的会话 */ } }遍历的顺序不是插入顺序也不是键的大小顺序而是哈希表内部桶数组和链表的物理顺序所以不要依赖任何排序特性。另外还有一个重要约束在进行hash_seq_search遍历的过程中不能调用HASH_ENTER或HASH_REMOVE操作同一个哈希表否则遍历指针会错乱出现漏数据或重复数据。正确的做法是先在遍历时把需要删除的键记下来等遍历结束再逐个删除或者干脆用hash_seq_term提前终止遍历然后单独处理。int keys_to_remove[1024]; int i, n 0; hash_seq_init(seq, session_tab); while ((entry hash_seq_search(seq)) ! NULL) { if (需要删除) keys_to_remove[n] entry-session_id; } hash_seq_term(seq); for (i 0; i n; i) { int key keys_to_remove[i]; hash_search(session_tab, key, HASH_REMOVE, NULL); }3.5 关于扩展的深层机制插入新元素时动态哈希表会检查当前负载是否超过阈值。判断依据是填充因子默认值为2意思是平均每个桶里的元素数量达到约2个时就要做一次桶分裂。分裂过程非常有意思。它并不是从头到尾重排所有元素而是选择一个“待分裂”的桶把该桶中的元素重新按哈希值散列到两个新桶里。桶数组本身也会按需扩容但整体代价被摊薄到每次插入操作中不会出现一次性大量搬迁的尖峰。这也是动态哈希表最核心的价值——扩展的优雅性。从使用者的角度你甚至不用知道这些细节。但有一个后果需要记住每次触发扩展后哈希表内部的bucket数组可能被重新分配之前通过hash_search拿到的元素指针大概率仍然有效元素内存没动但是遍历状态可能失效。所以在遍历过程中插入新元素本身也是禁忌原因就在这里。4. 常见问题与排查技巧实录4.1 指针引用失效问题这是使用动态哈希表时最典型的翻车点。很多人会在第一次插入时保存返回的entry指针留着以后一直直接用。这在别的语言里很常见但在PG的动态哈希表场景下非常危险。危险来自两个方面。第一后续当你插入其他键哈希表可能触发桶分裂虽然已有元素本身不会被搬走但如果你的指针指向的元素被删除再使用就会越界。第二当哈希表通过内存上下文被整体清理后所有旧指针都会变成悬空指针。我的建议非常简单直接每次需要读取或修改某个元素时都用hash_search重新查找不要长时间保存entry指针。顶多在当前函数局部范围内短暂使用用完即弃。这个习惯能帮你省下无数排查悬空指针的时间。4.2 遍历时删除导致的漏数据问题不少人在遍历时找到目标就直接调用HASH_REMOVE结果发现有些元素没被遍历到或者遍历无限循环。原因前面说过HASH_REMOVE会改变链表结构而hash_seq_search的游标是基于链表节点位置的删除一个节点后再移动到下一个很可能漏掉原本跟在被删节点后面的元素。排查这类问题时最明显的特征是遍历后处理的数量比预期少。如果只是少量并发插入倒还好但删除操作带来的结构性变化会稳定复现问题。最终的解法还是那两招先记key后删除或者用hash_seq_term终止旧遍历后再开始新遍历。4.3 内存失控与泄漏排查动态哈希表的内存是跟着内存上下文走的这一点既是便利也是陷阱。如果你创建哈希表时指定了错误的上下文比如放在了一个长期存在的上下文中那么随着元素的插入删除虽然元素在HASH_REMOVE时会释放但表结构本身、桶数组、临时分配的空间可能一直留在内存里表现为内存只涨不跌。排查时可以先用hash_stats(htab)打印哈希表当前的统计信息看看元素数和桶数是否符合预期。其次检查创建时传入的hcxt到底是什么。我遇到过的一个真实案例是某后台进程写代码时没指定上下文系统就默认分配到了TopMemoryContext结果每次操作都在最顶层的上下文里分配内存进程运行几天后内存居高不下。后来把哈希表绑定到专用上下文再配合定期重置上下文问题就消失了。另外元素里如果保存了指向其他内存块的指针比如长字符串或数组删除元素前必须先释放这些额外资源。HASH_REMOVE只释放元素本体不会帮你处理那些指针指向的资源。4.4 并发访问与分区锁PostgreSQL的动态哈希表用在共享内存场景下时需要考虑并发安全。系统提供了基于分区的锁机制来缓解竞争创建时设置HASH_PARTITION并指定num_partitions哈希表会把桶数组划分成多个分区每个分区有独立的锁。不同进程操作不同分区时可以减少锁等待。但是要注意分区锁粒度只是“分区级”不是“桶级”也不是“元素级”。如果多个进程同时操作同一个分区里的不同桶仍然有竞争只是竞争概率比全局一把锁低很多。设计共享哈希表时num_partitions需要根据并发规模估算通常取2的幂比如4、8、16。太小了锁竞争明显太大了分区锁本身占用内存和管理开销都会增加。判断是否真的存在锁竞争可以通过压测观察系统在并发插入时的吞吐变化。如果并发数翻倍但吞吐不涨就要怀疑是不是在哈希表的某个分区上争抢了。下面把这些高频问题整理成速查表方便遇到问题时对号入座。问题现象可能原因排查方向推荐解法使用保存的entry指针数据错乱或崩溃元素被删除或内存上下文重置检查delete调用和上下文生命周期每次操作都重新hash_search遍历时删除元素后漏处理HASH_REMOVE改变链表结构检查遍历循环内部是否有删除调用先记录key遍历结束后统一删除内存持续增长不回落元素分配到了长期存在的上下文打印hash_stats 检查hcxt设置绑定专用上下文定期重置删除元素后内存仍泄漏元素内指针指向额外资源未释放检查entry结构内是否有外部指针删除前先释放额外资源并发插入性能上不去锁分区数设置不合理观察perf和锁等待增大num_partitions并压测验证4.5 自定义哈希函数与按键注意事项键的类型不总是int这种简单结构。有时候你需要用字符串、复合结构体甚至二进制块做键。PG的动态哈希表支持自定义哈希函数在HASHCTL里传入hash函数指针并设置HASH_FUNCTION标志。自定义哈希函数需要严格遵循两个约定输入是指向键值的指针返回值是uint32类型的哈希值同一个键必须始终返回同一个哈希值。如果哈希函数不稳定元素会落到错误的桶里后续根本查不到。另外键的字节比较逻辑也需要考虑。默认情况下系统直接按内存字节做二进制比较这对int、二进制块、定长字符串都够用。如果你要支持大小写无关比较或者复杂的业务键规则就不能依赖默认行为更好的方式是把比较规则转化为一个归一化后的键——在写入时统一格式在查找时也使用相同格式。比如键是字符串时可以统一先转小写再作为键存入。我在一个模拟项目里试过用自定义哈希函数处理复合键两个int字段组成一个结构体keysize设为8字节。实测下来插入和查找性能都不错唯一的坑是结构体对齐问题。如果结构体里有padding字节keysize设成sizeof(struct)会把未初始化的padding字节也纳入比较同一个逻辑键可能因为padding内容不同而查不到。解决办法是显式设置精确的键字节数或者用memset先清零整个结构体。写在最后一开始我就是抱着“看个热闹”的心态去读PostgreSQL源码的结果在动态哈希表这里停了好一阵子。真正开始动手写自定义模块、自己创建哈希表之后才对那些设计的精妙处有了体感。特别是渐进式扩容和内存上下文配合这两点超出了普通教科书里哈希表的范畴是PG这种长周期、高并发系统进化出来的独特能力。我个人在实际操作中的体会是理解动态哈希表最好的方式不是只看源码注释而是老老实实写一个自定义数据结构的扩展模块从hash_create开始把HASH_FIND、HASH_ENTER、HASH_REMOVE、遍历和销毁完整走一遍。走完之后回头再看锁管理器或者relcache的代码会明显发现思路顺了很多之前看不懂的调用都变得理所当然。如果你正好也在琢磨PG的数据结构或者打算在自己的项目里借鉴这套设计建议从一个小场景切入先把基本增删查改跑通再去研究扩展和并发细节。动态哈希表不难但细节很多值得多花点时间。