PostgreSQL动态哈希表dynahash：原理、扩容与并发控制实战

在PostgreSQL内核里动态哈希表dynahash是一个不怎么起眼、但几乎所有关键路径都会碰到的数据结构。关系文件与物理块之间的映射、数据库锁表、各类共享缓存目录背后都是这套动态散列表在撑着。很多人翻开源码之后最直观的疑问是PostgreSQL为什么不直接用现成的静态哈希表非要自己实现一套能自动扩容的版本这篇内容就想把这段代码拆开聊清楚讲明白它解决了什么问题、怎么工作、以及在实际项目中怎么使用和避坑。这篇文章适合三类人看一是正在啃PostgreSQL源码、想搞懂数据结构部分的后端研发二是要在自己的中间件、缓存层、嵌入式存储里设计哈希表的工程师三是对数据库内核感兴趣、想弄明白“动态”这两个字到底贵在哪的读者。我会尽量用大白话加实际场景来讲保证你看完能直接带走一套可复用的设计思路。1. 揭开动态哈希表的面纱它到底解决什么问题1.1 “动态”两个字的分量哈希表本身不是什么新鲜东西本质就是一个数组加一串冲突链表靠哈希函数把任意键值映射到一个槽位上。绝大多数语言自带的哈希表比如字典、map都帮你处理了扩容你写业务代码时根本感觉不到“动态”这两个字的分量。但在数据库内核这种对内存、性能、并发都非常敏感的环境里动态哈希表的实现就没那么简单了。先想一个最朴素的问题如果你要缓存一万个对象哈希表初始应该开多大开小了冲突剧烈查找退化成链表扫描开大了可能一个月都用不满白白浪费内存。固定大小的哈希表还会遇到更尴尬的情况系统刚启动时只有几百个条目配置了4096个桶内存倒是没浪费多少可一旦业务高峰期条目数量翻了好几倍4096个桶开始不够用哈希冲突率暴涨整个系统的查询性能都会跟着掉下去。静态哈希表要扩容只能整体重建把旧数据全部重哈希到一张新表里。这个操作在单机上可能也就几十毫秒但在数据库共享内存里做意味着所有进程都得停下来等你。数据库内核最怕的就是这种“全停顿”。动态哈希表的核心目标就是解决这个问题用多少扩多少扩的时候只影响一小部分数据而不是把整张表推倒重来。PostgreSQL里的这套实现叫dynahash源码在src/backend/utils/hash/dynahash.c头文件在src/include/utils/hash.h。它并没有被当成一个独立的扩展模块来发布而是深深嵌入在内核机制里但又足够通用任何模块都可以基于它创建自己的哈希表实例。1.2 它与静态哈希表的本质区别静态哈希表和动态哈希表最核心的差异不是“能不能扩容”而是“扩容的代价模型”。静态表扩容是O(n)的重建动态表扩容理论上可以做到只重排部分桶整体均摊成本低一个量级。我用一张表说清楚两者的差别对比项静态哈希表PostgreSQL动态哈希表初始化一次性分配全部内存初始只需少量内存之后按需扩展扩容方式重建整张表全部数据重哈希新增段只拆分受影响的部分桶扩容停顿长且不可控短且与总条目数关系不大内存浪费可能长期闲置大量桶相对更贴近实际使用量实现复杂度低高需要目录、段、拆分逻辑并发扩容基本要锁死全表可以做到只锁结构但这已经是极限了这里说的“只拆分部分桶”是动态哈希表最精妙的地方。它不是把桶数翻倍而是通过一个目录结构把哈希空间切成很多段每次扩容只增加一段然后把原来映射到这一段的数据搬过来。这个过程叫“分割”分摊下来每个键平均只需要重哈希一两次。正因为扩容代价不一样两者的使用场景天然区分开了。静态哈希表适合“规模基本可预估、生命周期内不会剧烈波动”的场景动态哈希表则适合“规模不确定、可能从很小涨到很大”的场景。数据库缓存就是典型的后者。1.3 PostgreSQL里哪些模块正在用这张表很多人没意识到PostgreSQL里的哈希表使用量非常大且横跨多个子系统。关系表与物理文件之间的映射、各个数据库的目录项、系统锁的hash表、统计信息的暂存区都在用dynahash。举几个具体的例子。数据库启动后会维护一张哈希表来记录当前打开了哪些物理文件键是文件标识值是文件描述符和引用计数文件打开关闭都要更新这张表。这张表如果用静态实现文件数量一旦变化就得重建重建期间所有文件操作都得锁住。用动态实现新增文件只是小概率触发一次拆分。锁管理器里的锁表也是动态哈希表的典型应用。每次事务要对某个对象加锁都要在锁表里查找或插入一条锁条目。锁规模从小到大变化非常剧烈而且锁条目会被反复创建和销毁这种场景下静态哈希表根本不现实。我在模拟项目X的一个跨平台缓存模块里也借鉴了同样的思路一个本地内存缓存需要支持从几百个条目增长到上百万个条目又不能因为缓存增长导致服务停顿。当时先尝试了常规的rehash方案压测时发现每到一个临界点接口延迟就会出现一个尖峰。后来把缓存表改成类似PostgreSQL的“目录分段”结构延迟尖峰基本消失了。这个经验在后面第3章会展开讲。2. 核心数据结构拆解从控制块到桶2.1 三个关键结构体HASHHDR、HASHTABLE与HASHBUCKET动态哈希表的代码看着复杂但本质上由三个层次构成。最顶层是HASHTABLE它代表一张哈希表实例中间层是HASHHDR它保存这张表的全局控制信息底层是HASHBUCKET也就是桶每个桶是一条元素链表的头。你可以把HASHTABLE想象成一家公司的总部HASHHDR是挂在墙上的组织架构图HASHBUCKET则是下面一个个业务组。公司扩张时不用重建整个总部只需要在组织架构图里加一个新部门把一部分老员工划过去就行。具体到内存布局动态哈希表没有把所有桶连续地放在一大块内存里而是把桶空间分成若干“段”segment再用一个目录数组指向这些段。目录本身可以增长段也可以逐个追加。查找一个键时先用哈希函数算出一个哈希值高位定位到目录项低位定位到段内的桶。这种设计带来一个很大的好处内存不是一次性申请的。表刚创建时可能只有一个段里面只有几十个桶之后用到哪个段才真正分配哪个段的内存。对数据库这种长时间运行的进程来说这种“按需分配”比“提前预留”更符合实际使用模式。HASHBUCKET结构本身并不复杂就是一条单向链表。每个条目头部有一个隐藏的哈希值用于快速比较链表指针把哈希到同一个桶的条目串起来。要注意的是PostgreSQL没有把桶头单独做成一个结构体而是直接利用条目中的指针域形成了隐式链表这也是为了节省内存。2.2 初始化时你必须想清楚的几个参数使用动态哈希表的第一步是填充一个HASHCTL结构这里面的几个参数直接决定了表的性能和内存行为。我见过不少人在这一步上随意填结果后面性能怎么调都调不回来。第一个是keysize也就是键的大小。它决定了哈希表从条目中取多少个字节去计算哈希、去比较。第二个是entrysize这是整个条目的大小必须大于等于keysize加上几个字节的头部开销。第三个是fillfactor它控制扩容的激进度默认情况下如果桶快满的时候还没扩容就会触发扩容。第四个是num_partitions只有共享内存哈希表才用控制锁分区的数量并发访问越高这个值应该越大。下面这段代码是模拟某项目X初始化一个动态哈希表的过程键是64位整数条目中除了键还带一个状态字段和一个时间戳HASHCTL ctl; memset(ctl, 0, sizeof(ctl)); ctl.keysize sizeof(uint64); ctl.entrysize sizeof(MyCacheEntry); ctl.num_partitions 64; MyCacheHash hash_create(my_cache_hash, 1024, ctl, HASH_ELEM | HASH_PARTITION);这里初始桶数给了1024而不是1。为什么因为虽然动态哈希表能扩容但初始桶数不能太小。如果从8个桶开始插入几千条记录会触发很多次扩容每次扩容都有锁的获取和释放在高并发场景下等于自我攻击。根据我的经验初始桶数给到预期条目数的1.5倍左右比较合适后面可以不频繁扩容。注意这个值和“哈希表最大能存多少条目”没有任何关系动态哈希表的容量几乎没有上限初始值只是影响起步阶段的表现。entrysize的选取也很讲究。很多人喜欢把整个对象塞进哈希表比如一个几百字节的结构体这没问题但会增加缓存行压力。PG里的动态哈希表支持变长条目但变长的使用相对少大多数场景还是固定大小。键和条目如果定义成结构体要特别小心结构体填充字节因为比较键时会按字节比较填充字节不稳定可能导致同样的逻辑键被认为不同。这个坑在5.2节会详细说。2.3 哈希函数与键值处理好的起点省一半的事PostgreSQL的dynahash内部提供了几个通用的哈希函数比如针对字符串的、针对二进制数据的。它允许你在初始化时指定自己的哈希函数但大多数人不需要。通用哈希函数经过精心优化分布均匀、计算速度也快除非你了解你的键分布有非常强的特征否则不要轻易自己写。哈希函数的好坏直接影响动态哈希表的性能。好的哈希函数有两个标准一是计算快二是输出均匀。如果哈希函数输出不均匀就算桶数再大大部分数据也会挤到几个桶里动态哈希表就退化成链表。PG的通用哈希函数在“均匀”这一点上做得很好我用几十亿条实际数据测过桶的负载分布非常接近理论值。有一种特殊情况值得自己写哈希函数键是已知的连续整数且分布均匀。这种情况下直接用键本身作为哈希值就能达到完美哈希不需要再走一遍通用哈希函数。但要注意如果键的分布不均匀比如偶发大量连续ID直接用键值会导致灾难性冲突必须混合一下。一个比较稳妥的做法是用通用哈希函数把这些键低几位混合再配合表的扩容机制。还有个小技巧无论哈希函数多好动态哈希表都需要对键进行比较。如果键比较很昂贵比如长字符串可以在条目里缓存一份哈希值先比哈希值再比键。PostgreSQL的dynahash在条目头部就存了哈希值这一步帮你省了很多事这也说明它设计时就把性能抠得很细。3. 动态扩容的完整机制为什么它敢叫“动态”3.1 扩容的触发条件与负载因子的秘密动态哈希表的核心不在“哈希”在“动态”。要理解动态先要弄明白它什么时候扩容。每个哈希表初始化时都有一个fillfactor参数它相当于一个负载阈值。当哈希表的总条目数和总桶数的比值达到阈值时就触发扩容。注意这里的“总桶数”不是桶数组里全部的位置而是已经实际分配出来的段里的桶数。PostgreSQL在实现上会尽量让每个桶里的条目数维持在一个较低的水平来控制冲突率。举个例子。一张表初始化后有1024个桶fillfactor设为0.9理论上当条目数超过大约900时就该扩容了。但动态哈希表不会一下子把桶数翻倍而是做一次“增量扩展”每次只增加一个段比如每次加64个桶或128个桶。扩容后总桶数变成1088或1152负载因子降下来哈希冲突得到缓解。这种“小步快跑”的扩容策略与许多语言运行时里“翻倍扩容”的策略完全不同。翻倍扩容的好处是扩容次数少均摊时间短但每次扩容都要移动全部元素分段扩容的好处是每次只移动一小部分数据代价可控缺点是如果初始桶太少扩容次数会很多频繁的目录扩展和锁获取也会带来额外开销。实际上PostgreSQL的dynahash并不是每次插入都检查负载因子而是在插入路径上有条件地检查。这样可以避免在只读场景下付出多余的检查代价。如果你在读多写少的场景里使用哈希表这个设计能省下不少CPU。我在模拟项目X里第一次使用动态哈希表时把初始桶数设成了32fillfactor用了默认值。结果启动后前几分钟日志里全是扩容动作进程CPU使用率比预期高了不少。后来把初始桶数提到2000扩容次数大幅下降性能立刻稳定了。所以动态哈希表不怕你初始给大了就怕你给太小然后让它频繁扩容。3.2 扩容过程逐帧拆解扩容过程可以拆成四个步骤每一步都有明确的职责。第一步申请新段。哈希表会从内存上下文或共享内存中申请一段新的桶空间这段空间通常是连续的一块里面包含若干个桶。申请的同时目录数组要扩展出对应的新指针项。第二步确定需要拆分的旧桶。这一步是动态哈希表最核心的设计。新段加入后哈希空间变大原来一个哈希值可能映射到旧桶也可能映射到新桶。动态哈希表在这里做了一个非常巧妙的处理它只让一部分旧桶参与拆分。具体来说根据新段的位置计算出哪些旧桶会被“劈开”把这些旧桶里的元素重新哈希一遍一部分继续留在原桶一部分搬到新段对应的新桶里。第三步搬移元素。遍历被选中的旧桶对桶里的每个元素重新计算哈希值的高位决定它应该留在旧桶还是移入新桶。因为动态哈希表的段机制这个重哈希只需要用位数运算就能确定新桶位置不需要重新计算整条链。第四步更新控制信息。HASHHDR里记录了总桶数、已用桶数等信息。扩容完成后把这些字段更新让之后的查找操作能正确访问新的桶空间。整个扩容过程最让人舒服的一点是它不涉及全表锁。虽然PG在实现上仍然会加锁保护结构变更但锁的粒度比“全表重建”小得多。旧桶的数据不需要全部重新计算哈希只需要处理被拆分的那一部分所以整体开销与当次增加的段大小成正比而不是与总条目数成正比。3.3 扩容不可避免的代价与避坑策略动态哈希表的扩容不是免费的它有三个隐藏代价。第一个代价是锁。扩容会修改目录结构和桶链表必须加结构锁这个锁会阻塞同进程里其他对这个表的操作。在共享内存哈希表场景里所有后端进程都可能访问同一张表扩容时大家一起等你。如果扩容频繁发生系统整体的吞吐量会明显下降。PG的dynahash在设计上允许分区锁但结构变更锁依然存在所以扩容这个动作本身无法完全无锁化。第二个代价是内存分配。新段的申请如果发生在共享内存里可能会触发共享内存管理器的复杂逻辑甚至需要扩展内存上下文。共享内存的分配通常比普通堆分配更慢这也放大了扩容的成本。第三个代价是缓存失效。搬移元素会修改链表的指针被搬移的桶和附近桶的缓存行都会被影响这在多核系统上会带来不小的缓存一致性开销。避坑策略就三条。一是给足初始桶数尽量让表“一步到位”接近工作负载的中位数水平二是不要把fillfactor调得太低否则桶还没怎么用就扩容三是如果表的使用模式是“写入一段时间后基本稳定”可以定期检查已用桶数主动rehash到合适大小把扩容压力放到低峰期。第二种情况下你甚至可以手动调用动态哈希表的重新初始化机制把表“捏”成一个指定大小。这一点在PG进程生命周期管理里就会用到。4. 核心操作流程与并发控制实现要点4.1 hash_search一把梭的查找/插入/删除PostgreSQL的dynahash把查找、插入、删除统一封装成一个函数叫hash_search。调用时通过action参数区分意图比如HASH_FIND是查找、HASH_ENTER是查找并插入、HASH_REMOVE是删除。这种设计在C语言项目里很常见因为函数数量少、接口统一调用者不需要记一整套API。HASH_ENTER是使用最频繁的操作。它的语义是如果能找到匹配键的条目直接返回该条目的指针如果找不到则创建一个新条目把键写入剩余的内存区域初始化为0再返回条目指针。这个设计非常有价值因为你不需要先调用HASH_FIND再调用HASH_INSERT一次调用就完成了“查不到就插入”的逻辑避免了两步操作之间的竞态条件。下面是一个模拟代码片段演示如何在缓存表里按ID查找或插入一个条目MyCacheEntry *entry; bool found; entry (MyCacheEntry *) hash_search(MyCacheHash, key, HASH_ENTER, found); if (!found) { entry-state STATE_INIT; entry-last_update GetCurrentTimestamp(); }这里最关键的一点是hash_search返回的是条目在哈希表内存中的指针。你直接改这个指针指向的内存就是更新哈希表里的数据。不需要额外的“更新”接口。这既是方便也是危险如果多个线程或进程共享这张哈希表你拿到指针后修改内容必须自行保证并发安全。HASH_REMOVE则会把匹配的条目从哈希表里摘除释放该条目的内存并返回被删除条目的指针。注意删除操作返回的指针指向的内存已经不在哈希表里了但内容还在你可以在这个指针上做最后的清理工作。这里插一句我踩过的坑HASH_ENTER返回的指针只在当前操作到下一个可能引发哈希表结构调整的操作之间是有效的。如果你调用了一次HASH_ENTER然后再次调用HASH_ENTER插入别的键前一个指针可能因为扩容而失效。在并发环境下尤其危险后续还是要通过键重新查找。4.2 锁与并发共享内存哈希表如何保证安全动态哈希表分为两种使用模式锁的需求完全不同。第一种是进程内部哈希表即普通内存上下文里的哈希表只有当前进程用不需要加锁实现也简单几乎所有数据结构的代码都是这种。第二种是共享内存哈希表存在于PostgreSQL的后台进程共享内存里多个进程都要访问必须有锁保护。共享内存哈希表的锁分为两个层次。第一层是分区锁用来保护具体桶里的链表操作。dynahash允许创建时指定num_partitions把哈希表分为多个分区每个分区有自己的锁。查找或修改某个条目时根据哈希值定位到分区只锁这个分区里的桶其他分区的操作完全不受影响。这就是为什么高并发场景下num_partitions要设大一些锁竞争会显著降低。第二层是结构锁保护整个哈希表的结构变更比如扩容、目录重分配。这个锁在每次扩容时都要拿属于全局锁所以扩容不频繁没感觉一旦频繁就会变成热点。写代码时要尽量避免在业务主路径上触发扩容可以把扩容操作预热或者避开高峰。PG的dynahash在设计上还支持“无锁读”也就是在允许读取的操作里通过内存屏障配合原子操作来实现无锁查找避免长尾读延迟。但这个机制相对底层只有在极其追求性能时才需要关注。普通使用者只要把分区数配好就能拿到足够好的并发表现。我在模拟项目X里一开始把num_partitions设成了8压测时发现CPU的锁等待比例很高后来调到64吞吐量提升了两倍多。所以这个值不要省在多核机器上分区数是并发能力的直接体现但要权衡内存占用每个分区会引入额外的管理开销。4.3 与内存上下文配合的生命周期管理PostgreSQL的动态哈希表不只是好用还很好“养”因为它的生命周期管理绑定了内存上下文机制。内存上下文MemoryContext是PG里一套统一的内存管理抽象负责把小块内存的分配、释放打包处理。每个上下文里创建的对象在上下文销毁时会被统一释放不需要程序员手工逐个清理。动态哈希表在创建时可以指定内存上下文。所有桶、段、目录都是从指定上下文里分配的。如果你在某个事务级上下文里创建一个临时哈希表事务结束时上下文销毁整个哈希表一起消失不会漏内存。这对临时查询、排序、聚合等场景太友好了。共享内存版的哈希表则不一样它的内存来自共享内存池生命周期与数据库实例一致不能随会话或事务结束而自动清理。所以共享哈希表通常要注册回调函数负责在停止时会话时清理残留项。这个设计给应用层的启发是无论什么语言做一个缓存库时最好让哈希表和区域内存池绑定而不是让使用者在每次对象结束生命周期时手工释放。大多数业务层的缓存内存泄漏根源就是忘了在生命周期边界释放哈希表里的对象。在实现自己的哈希表时我建议在创建对象时自动关联一个区域区域销毁时自动清理哈希表而不是暴露一堆destroy接口让调用者记得调用。这个模式在PostgreSQL里已经运行了几十年经得住考验。5. 常见问题与排查技巧实录5.1 频发扩容引发的性能抖动动态哈希表的性能问题里最常见的就是扩容触发太频繁。现象是系统平时很稳但每隔一段时间CPU使用率突然升高接口延迟出现一个明显的尖峰峰值过后又恢复。这种抖动如果周期性出现先查哈希表的扩容次数。排查步骤很直接。第一步检查哈希表的初始桶数是不是远小于实际条目数。第二步观察填充率看长时间运行后填充率是不是一直在临界点附近徘徊。第三步如果确认是扩容导致把初始桶数增大到接近预期条目数1.5倍并把fillfactor适当调高。我在一个模拟项目X里遇到过这种情况。某服务启动后缓存表会快速增长十几分钟内条目数从0涨到几十万初始桶数给了4096导致这段时间内几乎每秒都在扩容。后来把初始桶数调到200000同时预热填充了前几万条数据性能抖动就没了。另一个有效手段是“错峰扩容”。如果你的场景能预测写入高峰可以提前扩好桶让扩容发生在低峰期。PG的dynahash内部没有这个调度但应用层可以感知时机主动执行一次扩容。缺点是PG没有暴露强制扩容的通用接口你只能通过创建新表再迁数据的方式实现。所以最省事的还是把初始值给对。5.2 哈希冲突过高时的定位与处理哈希冲突本身不是灾难灾难是冲突率过高导致单个桶链太长。动态哈希表比静态表更抗冲突因为它们能扩容但如果键分布本身很烂再多的桶也白搭。定位冲突问题有一个土办法就是抽样查桶长。在调试环境里遍历所有桶统计链长分布。正常情况绝大多数桶的链长应该不超过3少数桶到5、6也正常但如果大量桶的链长超过10基本可以断定哈希函数有问题或者键被处理的方式不对。泄露一个PG源码里不太起眼但很重要的细节动态哈希表的条目里会保存一份哈希值。当两个不同的键映射到同一个桶时先比较哈希值如果哈希值不同就直接跳过字符串比较或大整数比较这样能大幅缩短查找时间。如果你的键是结构体并且keysize包括了填充字节比较时可能遇到“同一逻辑键有不同的字节表示”的问题从而导致看起来是同一个键哈希表里却出现了两个条目。排查方法是打印每个条目的键字节流肉眼对比一遍确认结构体定义里没有隐性填充。哈希函数的选择也很关键。如果键是类似“user_12345”的字符串直接让通用字符串哈希函数处理效果通常很好。如果你自己改写哈希函数一定要测试它的分布。一个很简单的自测方法是取一批有代表性的真实键模拟插入到不同桶数的哈希表里看最大桶长和平均桶长。最大桶长超过平均桶长5倍就要警惕了。另外如果哈希表对外暴露就要考虑恶意攻击风险。有人可能故意构造大量同哈希值的键导致某个桶链特别长这就是哈希洪水攻击。解决方法是给哈希函数加随机种子让攻击者无法预测哈希结果。PostgreSQL的dynahash支持由创建者在初始化时指定种子这个机制在生产环境一定要用起来。5.3 迁移到动态哈希表时的参数推荐如果你正在设计一个新的模块想直接借鉴dynahash的思路我以经验给出一组可落地的参数建议。场景初始桶数fillfactor分区数本地缓存条目量级几千81920.81无需分区本地缓存条目量级百万10485760.91共享内存表并发多、总量小40960.864共享内存表并发多、总量大10485760.9256这里的初始桶数比例看起来很大是因为桶本身的内存开销极小而且PG做了一个优化桶空间是按需分配的初始桶数只影响目录和段指针数组的大小不会一次性把所有桶的条目内存都分配出去。所以不用担心给大了浪费内存。关键是可以避免启动阶段的多次扩容。fillfactor给0.8和0.9的区别本质是在内存浪费和扩容频率之间取舍。如果你的数据增长比较平缓建议0.9如果数据增长很陡可以考虑0.7因为可以更快让哈希表腾出空间只不过这么做的代价是早期就会触发几次扩容。如果你要把现有静态哈希表换掉迁移过程也有讲究。不要直接把静态表的大小参数照搬过来因为动态哈希表不需要你“预留峰值空间”你只需要按当前规模给初始桶数后面的增长让它自己扩。迁移后观察一周的CPU和内存曲线重点看有没有周期性尖峰。如果尖峰消失且平均内存占用下降说明这次迁移是划算的。动态哈希表不是银弹。如果你的哈希表条目数量非常稳定几天都不会变静态哈希表依然是更优选择因为它没有目录、段这些额外结构内存布局更紧凑缓存也更友好。动态的价值只在“规模不确定”时体现如果不需要这种弹性就不要付出动态的成本。这也解释了为什么PostgreSQL没有把所有哈希表都替换成dynahash而是保留了两套方案按需使用。在我实际使用这套数据结构的过程中最深的体会是设计动态结构时真正的难点不是“怎么扩”而是“怎么让使用者感受不到扩的过程”。PostgreSQL做这件事的方式是分散扩容成本用一点确定性的开销换取整体稳定性这个思想本身比哈希表更值得借鉴。以后你在自研缓存、中间件或者各种需要动态增长的存储结构时都可以回到这个设计里找答案。