当前位置： 首页 > postgresql, 锁模块 > 正文

动态哈希表（Dynamic Hash Table）

pantsuel 发布于 2026-02-25 04:48postgresql, 锁模块27 次浏览抢沙发

第一步破局：抛弃“大平层”，构建“三级立体寻址” 逻辑推导出来

哈希表， 白板上画一个“长条形的连续方格（一维数组）”。这就是所谓的**“大平层”**。

现在 把抛弃“大平层”、逼出“三级立体寻址（Directory -> Segment -> Bucket）”的底层物理逻辑，一步步硬核推导出来！

第一步绝境：大平层的“物理死亡宣告”（为什么必须抛弃？）

【工业级灾难推演】

假设数据库刚启动，你建了一个拥有 10 万个格子（Bucket）的“大平层”哈希数组，占用了 800KB 的连续物理内存。这在初期跑得极快。

但突然，业务大促爆发！并发量翻了 100 倍，哈希表里涌入了 1000 万把锁。

  • 物理后果：原来 1 个格子里只挂 1 个人，现在 1 个格子里平均挂了 100 个人（链表长度变成 100）。
  • 灾难降临：查询速度瞬间暴跌 100 倍，整个数据库的 CPU 被拉满，进入假死状态。

【小白的解法与致命毒药（Rehash 全盘搬家）】

小白程序员会说：“这还不简单？格子不够了，那就扩容啊！申请一个 2000 万格子的新大平层数组，把旧数据搬过去。”

但在底层 C 语言的物理世界里，这叫**“全局 Rehash（重哈希）”**，它有两大极其致命的死穴：

  1. Stop-The-World（全局大停顿）：在搬运这 1000 万个结构体指针的漫长几秒钟里，为了防止指针错乱，你必须加上最高级别的排他锁，把整个哈希表彻底冻结！全站所有业务在这几秒内，全部卡死报错（连接超时）。
  2. 操作系统的物理反抗（内存碎片）：新数组要求是一块绝对连续的巨大物理内存。在运行了几个月的服务器上，内存早就碎成了一地鸡毛，操作系统根本找不出这么大一块连续的空地，直接返回 Out Of Memory（OOM），数据库当场宕机。

推导结论：在海量并发的工业界，要求绝对连续内存的“大平层扩容”，等同于自杀。

第二步破局：空间切割手术（引入“段 Segment”）

既然“找一块巨大的连续内存”是不可能的，那架构师就顺应操作系统的脾气：“你不给我一大整块，那我就分批找你要一小块一小块的！”

【物理降维拆解】

架构师把原本那个不可分割的巨大数组，用菜刀切成了几百个中等大小的内存块。这个中等大小的物理内存块，在 PG 源码里就叫做**“段（Segment）”**。

  • 物理规则：每个“段”的内部，依然是连续的数组（比如固定包含 1024 个桶）。
  • 核心优势：因为“段”的体积很小，操作系统闭着眼睛都能在内存碎片的缝隙里把它分配出来。

但是，新问题来了：以前大平层首尾相连，CPU 只要算个偏移量就能找到位置。现在内存被切成了几百个散落在物理空间各个角落的“段”，CPU 怎么知道哪个段在哪里？

第三步重构：构建“导航枢纽”（引入“目录 Directory”）

为了把散落在内存各处的“段”重新在逻辑上缝合起来，架构师在所有段的最上方，建了一个极其轻量级的指挥中心——“目录数组（Directory Array）”。

【导航台的物理全貌】

  1. 它的体积极小：比如只有 256 个格子。
  2. 它不存数据：这 256 个格子里，存放的仅仅是指向各个“段（Segment）”基地址的内存指针。

【动态扩容的神级物理推演（极速造楼）】

现在，我们再来应对刚才那个导致大平层死亡的“千万级并发扩容”危机：

  1. 容量告警：内核发现当前的段已经快挂满了，急需扩容。
  2. 极速化解（仅仅 2 步物理操作）：
    • 第 1 步：内核向操作系统说：“给我新分配一小块内存（建一个新的段 Segment 3）”。耗时微秒级，绝不触发 OOM。
    • 第 2 步：内核把这个新段的物理内存地址，登记在“目录数组”的第 3 个空闲格子里：Directory[3] = 0x90000000;。
  3. 结束：扩容瞬间完成！

这就是真正的降维打击！

不需要全局锁死！不需要搬运以前的几百万条老数据！旧段（Segment 0, 1, 2）里的数据原封不动、岁月静好，新来的数据自动被路由到刚刚建好的新段（Segment 3）里。整个扩容过程，对上层业务是绝对 100% 无感知的。

架构师的终极视角：三级立体寻址的闭环

我们现在把视角拉高，俯瞰你推导出的这座物理堡垒：

  • 第一级：目录（Directory） $\rightarrow$ 极其微小的指针枢纽，负责管理各个地块的位置。
  • 第二级：段（Segment） $\rightarrow$ 分散在内存各处的中型地块，彻底消灭了“连续内存分配”的物理瓶颈，实现了 $O(1)$ 的无痛动态扩容。
  • 第三级：桶（Bucket） $\rightarrow$ 段内部的具体门牌号，负责承载最终的哈希冲突拉链。

这根本不是普通的写代码，这是在极其逼仄的物理内存限制下，像搭积木一样重塑了空间法则。

用“连续内存瓶颈”、“全局 Rehash 的代价”和“无痛指针扩容”来解释这个**三级立体哈希表（dynahash）**的演进过程。

第二步全景推演：一个 OID 是如何在这座城堡里极速降落的？把这个部分逻辑推导出来

这是一个将 C 语言源码级思维与底层 CPU 硬件架构完美缝合的巅峰推演！

在前面我们推导出了为了解决扩容绝境，哈希表被逼出了**“目录 $\rightarrow$ 段 $\rightarrow$ 桶”**的三级立体城堡。现在，高潮来了：当城堡变得如此立体复杂时，CPU 该如何在不使用任何低效的 for 循环、不使用极其缓慢的除法器（/ 和 %）的情况下，在 1 纳秒内精确空降到目标坐标？

我们现在把 CPU 的系统时钟调慢 1 万倍，直接进入寄存器内部，用 4 帧“极速慢动作”，把这个纯靠**“位运算（Bitwise）与指针偏移”**的物理降落过程严密推导出来！

第一帧：数学绞肉机（剥离业务属性，生成绝对坐标）

【战场起因】

业务端发来一个极度简单的请求：“我要找表 OID 为 16384 的锁结构体。”

但在底层的哈希引擎看来，16384 这个数字充满了“业务的偏见”，它不够随机，如果直接用它去内存里找，极易引发局部的哈希碰撞踩踏。

【物理降维（Hash Function）】

CPU 绝对不会拿着 16384 去内存里瞎转。它第一步，是把 16384 扔进 PostgreSQL 内置的 Hash 函数（比如 MurmurHash）。

这台绞肉机经过几轮移位（Shift）和异或（XOR）的电路闪烁，瞬间吐出了一个完全打散、极度均匀的 32 位二进制无符号整数（Hash Value）。

为了直观推演，我们假设吐出的 32 位二进制数字的后 16 位长这样：

... 0000 0100 1010 1100 （换算成十进制是 1196）

物理推导结论：业务的 OID 已经彻底死亡。现在的 1196，就是目标在这座哈希宇宙里的“绝对灵魂代码”。

第二帧：截断雷达（确定“逻辑桶号 Bucket ID”）

拿到 1196 之后，能直接去内存找吗？不行！因为当前的哈希城堡可能只建了 1024 个桶。你拿着 1196 去找，直接就内存越界（Coredump 宕机）了。

怎么把 1196 压缩到 0 到 1023 的合法范围内？

  • 小白的灾难写法：用求余数（模运算） 1196 % 1024。在 CPU 底层，除法指令（DIV）需要消耗几十个甚至上百个时钟周期，这在千万并发下是绝对的性能毒药！
  • 架构师的神级写法（按位与 &）：因为 1024 恰好是 $2^{10}$，架构师直接在内存里准备了一个由 10 个 1 组成的“截断掩码”：0000 0011 1111 1111（十进制的 1023）。

CPU 算术逻辑单元（ALU）瞬间压下闸门，执行 & 运算：

物理推导结论：仅仅消耗 1 个极其廉价的时钟周期，CPU 算出目标在这座城堡的 第 172 号逻辑桶！

第三帧：三维解体寻址（分离“段号”与“偏移量”）

知道了目标在第 172 号逻辑桶，但这座城堡是立体的（被切成了很多个段 Segment）。第 172 号桶，到底在第几个“段”的第几个位置？

假设 PG 规定，每个“段（Segment）”的容量固定是 256 个桶（即 $2^8$）。

【依然不用除法！纯靠位移 >> 和掩码 &】

  1. 算“段号”（Directory Index）：172 里包含几个 256？CPU 直接把 172 的二进制向右平移 8 位（>> 8）。0000 0000 1010 1100 >> 8 = 0000 0000 （十进制的 0）。推导结论：它在 第 0 号段（最基础的那个内存地块）。
  2. 算“段内偏移量”（Bucket Offset）：在第 0 号段的第几个位置？CPU 直接用 172 和 255（即 256-1，掩码 0000 0000 1111 1111）做按位与（&）。0000 0000 1010 1100 & 0000 0000 1111 1111 = 1010 1100 （十进制的 172）。推导结论：它在第 0 号段的 第 172 个偏移格子！

(注：如果你刚才算出的逻辑桶是 428，右移 8 位就是段号 1，按位与 255 就是偏移量 172。物理逻辑完全一致，极度丝滑！)

第四帧：物理空降（指针算术与最终着陆）

现在，三维坐标情报（第 0 号段，第 172 个偏移）全部聚齐，CPU 开启最后的物理级内存跳跃：

  1. 拔取基地址（查目录）：CPU 来到最顶层的目录数组（Directory），直接取出 Directory[0] 里的内容。这里面存的，是第 0 号段在物理内存条上的绝对起始基地址（假设是十六进制的 0x80000000）。
  2. 指针偏移（算绝对坐标）：目标在第 172 个位置。每个桶占 8 个字节（存放一根链表头指针）。CPU 执行内存指针偏移加法：最终物理地址 = 0x80000000 + (172 * 8) = 0x80000560。
  3. 空降成功：CPU 的内存控制器，直接锁定绝对内存地址 0x80000560！

在这块极其微小的十六进制内存里，躺着的刚好就是那一根我们之前推导过的 Next 指针（链表头）。

接下来，就是掏出 LOCKTAG 身份牌进行比对，或者执行“头插法”强行挂载新的锁结构体孤岛。

工业级总结

“很多工程师以为寻址就是查数组，但在 PostgreSQL 的 dynahash 动态哈希表中，为了兼顾无痛扩容与极速寻址，一个 OID 的查找被彻底转化为了一场 纯位运算的艺术。

整个过程没有任何循环，没有任何低效的除法。一个 OID 扔进去，通过一次 Hash 散列，一次按位与（&）算逻辑桶，一次右移（>>）算段号，一次按位与（&）算段内偏移，最后加上基地址进行指针算术。 CPU 靠着这几条耗时仅需 1 纳秒的电子脉冲指令，就能在几百万个哈希槽里，拼装出那个绝对的十六进制物理内存地址。这就叫工业级的 $O(1)$ 复杂度极限！”

 lock结构体被分为： 头部组件（Next 指针） 核心组件（Key / 身份牌） 挂载车厢（Payload / 真实数据实体） 三个部分？

从物理内存块（Memory Block）的绝对视角来看， 它在内存条里就是实实在在挨着的这三个部分。

架构师的“黑魔法”：结构体的物理剥离

在面向对象的思维里，我们会想当然地认为这三个部分都写在 struct LOCK 这个代码块里。但 PG 的架构师追求的是极致的解耦。

哈希表引擎（dynahash.c）是一个通用底层组件，它根本不想知道什么是“锁”、什么是“缓存”。它只负责“挂链表”。所以，架构师在 C 语言的物理内存分配上，玩了一个包裹（Wrapper）魔法。

当内核在哈希表里为一把新锁申请内存时，这块内存被切分成了两层：

隐身的第一层：哈希引擎的外壳（包含 Next 指针）

  • 结构体名：HASHELEMENT
  • 你的归纳：头部组件（Next 指针）
  • 物理真相：这段内存是哈希表引擎强行“粘”在最前面的。它里面包含了一个极其核心的 struct HASHELEMENT *link（也就是你说的 Next 指针，用来做头插法挂载链表），以及算好的 Hash 值。
  • 障眼法：它对上层的锁管理器是完全隐身的！锁管理器的代码根本看不见这个指针。

暴露的第二层：真正的 LOCK 结构体（紧挨着头部）

紧紧贴着 HASHELEMENT 后面的物理内存，才是真正在 lock.c 源码里定义的 struct LOCK。它完美对应了你归纳的后两个部分：

  • 1. 核心组件（Key / 身份牌）
    • 源码字段：LOCKTAG tag;
    • 物理真相：它是 LOCK 结构体里的第一个字段。里面写死了表的 OID（比如 16384）、锁的对象类型（是表级锁还是行级锁）。当 CPU 顺着刚才那个隐身的 Next 指针跳过来时，第一时间就是把这个 tag 抓进寄存器进行比对：“你是我要找的 16384 吗？”
  • 2. 挂载车厢（Payload / 真实数据实体）
    • 物理真相：一旦 Key 对上了，排在后面的就是这把锁的“全部身家性命”。这里面装的，正是我们前面几万字推导的所有核心武器！
    • 车厢里装着什么？
      1. grantMask：当前表上已经发放的锁状态（参与纳秒级位运算 & 的靶子）。
      2. waitMask：门外有哪些高级别的锁正在排队（预警雷达）。
      3. procLocks：一个双向链表头。顺着它，能揪出所有当前正在合法持有这把锁的“契约（PROCLOCK）”。
      4. waitProcs：一个极其悲壮的等待队列。顺着它，能看到所有因为“位运算冲突”而被强行剥夺 CPU 执行权、正在深度休眠的千万大军（PGPROC 进程）。

极客视角的闭环大一统

你现在再来看你总结的这三个部分：

Next指针（链表跳跃） $\rightarrow$ Key身份牌（碰撞比对） $\rightarrow$ Payload车厢（位运算与排队）

这就是一个极度完美的物理处理流水线！

  1. CPU 先踩在**第一部分（Next）**上极速跳跃，维持 $O(1)$ 的链表遍历。
  2. 看到目标后，一把抓住**第二部分（Key）**验明正身。
  3. 身份确认无误，立刻冲进第三部分（Payload），掏出掩码雷达进行按位与（&）运算，瞬间决定生死！

第三步数据挂载：链表节点（HashElement）的真实解剖 逻辑推导出来

这是一个真正能让你在海量数据（openGauss 核心原厂）的终面里，和内核老专家产生灵魂共鸣的绝对深水区！

在讲数据结构的时候，绝大多数人对“链表节点”的认知，都停留在大学 C 语言课本里的那句 struct Node { struct Node *next; void *data; };。

如果你带着这种“面向对象”和“泛型指针”的思维去理解 PostgreSQL 的底座，你不仅无法理解它的快，更会错过内核架构师在 **CPU 硬件缓存（L1 Cache）**上玩的登峰造极的物理黑魔法。

我们现在彻底抛开业务代码的思维，直接化身为一块滚烫的 CPU 硅片，把这个挂载在哈希槽底下的 HashElement（哈希元素） 的真实物理肉身，用 3 帧极速画面严密地解剖出来！

第一步绝境：泛型指针的“物理死穴”（为什么不能用 void *？）

【普通程序员的灾难设计】

为了让哈希表能通用（既能存锁，又能存表元数据），普通开发者会在链表节点里放一个 void *data 指针，让它指向真正的业务结构体（比如 LOCK）。

  • 物理动作：CPU 顺着链表找到节点，读取 data 指针里的内存地址（比如 0x9000），然后再发起一次内存寻址去读 0x9000 的内容。

【架构师眼里的性能毒药：Pointer Chasing 与 Cache Miss】

在 CPU 极其微观的世界里，去主存（RAM）里读一次数据是极其缓慢的（大约 100 纳秒）。为了加速，CPU 内部有极速的 L1 Cache（一级缓存，耗时 1 纳秒）。

L1 Cache 每次从内存抓取数据时，不是只抓 1 个字节，而是强制抓取连续的 64 个字节（这叫一个 Cache Line 缓存行）。

如果你用指针指向另一个地方（物理内存不连续），CPU 抓完节点后，为了读真正的数据，必须跨越物理空间，触发极其昂贵的 Cache Miss（缓存未命中），被迫再次去缓慢的主存里寻址。

在千万级并发下，这种被称为“指针追逐（Pointer Chasing）”的动作，会把 CPU 的流水线彻底拖死！

第二步破局：架构师的“三位一体”物理缝合术

为了彻底消灭 Cache Miss，PG 的哈希引擎（dynahash.c）祭出了终极杀招：绝对连续的内存分配！

当你在哈希表里申请一个新的元素时，内核根本不会分别 malloc 节点和业务数据。它是直接把这三样东西，像烧电焊一样，死死地焊在同一块连续的物理内存里！

我们来看看这块连续内存（HashElement）切开后的真实断层扫描图：

1. 隐身的引擎层：HASHELEMENT 头部（导航系统）

  • 物理位置：永远排在内存块的最前面（绝对的偏移量 0）。
  • 内部构造：
    • link 指针：用于头插法，指向下一个发生哈希冲突的兄弟。
    • hashvalue（极客黑魔法）：保存了算好的 32 位哈希值。为什么？因为当链表里有 10 个人发生冲突时，CPU 不需要每次都去读取 Key 重新算一遍哈希，直接对比这个数字，就能在一瞬间过滤掉 99% 的错误目标！

2. 核心比对层：Key（身份牌）

  • 物理位置：紧紧贴着 HASHELEMENT 头部，绝对没有指针跳转，中间连 1 毫米的物理缝隙都没有。
  • 物理动作：如果是锁管理，这里就是 LOCKTAG（包含了 OID 16384）。

3. 业务挂载层：Payload（真实的 LOCK 结构体）

  • 物理位置：紧紧贴着 Key 的屁股后面！
  • 物理动作：这里面装着参与位运算的 grantMask 和千万排队大军的等待链表头。

第三步高潮推演：一次完美的 L1 Cache 命中！

现在，这三截车厢被死死焊在了一起。我们来看看，当 CPU 顺着哈希槽（Bucket）降落到这个节点上时，发生了怎样震撼的物理化学反应：

  1. 降落与抓取：CPU 顺着指针来到这个连续内存块的头部。CPU 内部的硬件预取器（Prefetcher）极其贪婪，它在读取 link 指针和 hashvalue 时，顺手就把紧紧挨在后面的 Key 和 Payload（grantMask）一起打包，瞬间吸入了极速的 L1 Cache 中！（因为它们都在同一个 64 字节的缓存行附近）。
  2. 极速连招（0 延迟）：
    • 第 1 纳秒：在 L1 Cache 里比对 hashvalue 和 Key（发现是 OID 16384，命中！）。
    • 第 2 纳秒：CPU 根本不需要再去主存寻址，直接在 L1 Cache 里取出紧挨着的 grantMask。
    • 第 3 纳秒：掏出你的请求掩码，执行大名鼎鼎的**按位与（&）**判决生死。

物理推导结论：在整个比对和判决的过程中，CPU 犹如在真空中极速滑行，没有触发任何一次主存的 Cache Miss！

架构师的终极对齐（面试 话术）

聊聊哈希表的底层时：

“在工业级的 C 语言底层架构中，数据结构决不能脱离 CPU 硬件来谈。PG 的 dynahash 之所以快，不仅仅是因为它用了拉链法，更是因为它在内存布局上实现了**‘业务数据与哈希元数据的绝对连续分配’**。

架构师通过极其暴力的指针运算（Pointer Arithmetic），省去了 void * 带来的指针追逐代价。当 CPU 读取链表节点时，利用空间局部性原理，Key 和业务状态被硬件完美预取到 L1 Cache 中。这种用物理内存布局去迎合 CPU 硬件缓存特性的极客设计，才是支撑数据库锁系统在极高并发下不会引发缓存颠簸（Cache Thrashing）的终极命门。”

了解 www.876873.xyz 的更多信息

订阅后即可通过电子邮件收到最新文章。

您可能还会对这些文章感兴趣！

动态哈希表（Dynamic Hash Table）：等您坐沙发呢！

发表评论