Dragonfly Dashtable 深度解析基于分段式开放寻址哈希表的高效内存字典【免费下载链接】dragonflyA modern replacement for Redis and Memcached项目地址: https://gitcode.com/GitHub_Trending/dr/dragonflyDashtableDynamic And Scalable HashingDASH是 Dragonfly 引擎内部最核心的数据结构之一每一个可被SELECT选择的数据库Db都持有一张承载全部键值条目的主表PrimeTable另外还维护一张专门存放带 TTL 过期信息的辅助表。本文以仓库内 docs/dashtable.md 为主线从经典 Redis 字典RD的缺陷讲起逐步拆解 Dashtable 的目录-分段directory-segment结构、插入/分裂/垃圾回收流程并结合 src/core/dash.h、src/core/dash_internal.h、src/server/detail/table.h 等源码佐证其内存与 CPU 优势最后给出文档中的实测基准数据。读完本文你将理解 Dragonfly 如何在保持 Redis 兼容的同时把每条记录的平均字典元数据开销压到 6~16 字节并为 forkless save 与按段垃圾回收这类高级特性打下基础。Dashtable 在 Dragonfly 引擎中的位置在 Dragonfly 中Dashtable 并非某个独立模块的附属品而是数据面的地基。从源码 src/server/table.h 可以看到每个DbTable对应一个可被SELECT选择的数据库直接内嵌了两张 Dashtablestruct DbTable : boost::intrusive_ref_counterDbTable, boost::thread_unsafe_counter { PrimeTable prime; // 主表承载所有条目 DashTablePrimeKey, uint32_t, detail::ExpireTablePolicy mcflag; // 过期表存放带 TTL 的键 ... };其中PrimeTable是DashTablePrimeKey, PrimeValue, detail::PrimeTablePolicy的类型别名见 src/server/table.h键与值分别采用CompactKey/CompactValue见 src/server/detail/table.h而第二张 Dashtable 负责记录“哪些键带 TTL 以及何时过期”其值类型是uint32_t时间戳。这与文档开篇的描述一一对应主表存全部数据过期表只存有 TTL 的键的到期信息。另外Dragonfly 采用 share-nothing无共享架构每个 CPU 线程拥有自己的分片shard与自己的 Dashtable 实例——这一点是后续多线程填充基准中速度近乎线性扩展的前提也是“每个线程维护更小的表”从而整体内存反而更优的原因。Redis 字典RD回顾每次插入都要付出 16~32 字节开销“计算机科学中的一切问题都可以通过增加一层间接层来解决。”在深入 Dashtable 之前先简要回顾经典 Redis 字典Redis DictionaryRD的实现因为 Dashtable 的每一项设计几乎都是针对 RD 的痛点展开的。每个RD实际上包含两张哈希表ht[0]与ht[1]第二张用于渐进式扩容。每张表dictht是经典的**分离链接separate chaining**哈希表dictEntry是以链表节点形式包裹每个键值对的条目每个dictEntry含 3 个指针占用 24 字节dictht的桶数组按 2 的幂次扩容因此负载因子通常落在 50%~100% 之间。RD 的开销估算假设表内有 N 个条目Case 1100% 负载桶数等于条目数。每个桶存放一个指向dictEntry的指针8 字节总开销为8N 24N 32N字节/条。Case 275% 负载桶数是条目数的 1.33 倍总开销约为N×1.33×8 24N ≈ 34N字节/条。Case 350% 负载刚扩容完桶数是条目数的 2 倍总开销为N×2×8 24N 40N字节/条。由于最理想情况下存储一个键值对本身至少需要 16 字节可得出dictht的平均元数据开销约为16~24 字节/条。再考虑渐进扩容的瞬时峰值当ht[0]写满需要迁移时RD 会新建一个容量为2N桶的临时表ht[1]两张表并存直到数据全部迁完。若把 Case 3 与 Case 1 组合起来看迁移瞬间需要32N 16N 48N字节即峰值内存比平时多出一半。综合来看RD 的字典元数据开销在16~32 字节/条之间而且这一开销无论数据多小都“刚性存在”——这正是小键值场景下 Redis 内存利用率低的根源。Dashtable 设计可扩展哈希的现代演化Dashtable 是 1979 年提出的可扩展哈希extendible hashing算法的现代演进。它与经典哈希表的关键区别在于经典哈希表前置指针数组指向链表的头节点Dashtable前置指针数组指向定长的迷你哈希表segment。这个前置指针数组被称为目录directory。插入时先根据键的哈希值的高位确定目标 segment再在 segment 内部完成实际插入。每个 segment 是采用开放寻址方案、容量恒定的哈希表。当 segment 插入失败“满了”时Dashtable 会把它分裂成两个 segment把新 segment 追加进目录然后重试插入。一句话概括经典链式哈希表是“动态数组 链表”而 Dashtable 是“动态数组 定长扁平哈希表”。上图中目录里的每个 slot 指向一个 segment每个 segment 由K个 bucket 组成。在 Dragonfly 的具体实现中K即每 segment 的 bucket 数是编译期参数常规桶 56 个、stash 桶 4 个见 src/server/detail/table.h 中PrimeTablePolicy/ExpireTablePolicy的kBucketNum 56以及 src/core/dash_internal.h 中Segment的kStashBucketNum 4。文档中“60 个桶/segment”即56 4的合计。Segment 内部结构bucket 与 slot每个 segment 由常规 bucket和stash bucket组成每个 bucket 又包含k个 slot每个 slot 可容纳一条键值记录。在 Dragonfly 的实现中每个 segment 有56 个常规 bucket和4 个 stash bucket每个 bucket 含14 个 slotkSlotNum 14因此每个 segment 的总容量为(56 4) × 14 840条记录。插入流程对应源码Segment::InsertUniq与Bucket::TryInsertToBucket见 src/core/dash_internal.h根据键的哈希值计算home bucket即 56 个常规 bucket 之一若 home bucket 有空闲 slot则插入若 home bucket 已满尝试插入其右侧相邻的常规 bucket若邻居 bucket 也已满则尝试插入4 个 stash bucket之一——这些桶被有意单独留出来承接常规桶的溢出只有当 home bucket、邻居 bucket 和全部 4 个 stash bucket 都满时segment 才判定为“满”。注意segment“满”并不意味着所有 bucket 都被填满——其他 bucket 可能还有大量空位但该条目只能落入上述 6 个候选 bucket 中因此必须触发分裂。分裂Split与合并Merge发生分裂时Dashtable 创建一个新 segment加入目录然后把旧 segment 中的条目部分迁移到新 segment、部分在旧 segment 内重新平衡。一次分裂只触及两个 segment这与 RD 扩容时需重哈希整张表形成鲜明对比。源码层面分裂逻辑在Segment::Splitsrc/core/dash_internal.hlocal_depth加一后按哈希值的第local_depth位is_mine判定(hash (64 - local_depth) 1) 0决定条目去留常规桶与 stash 桶分别处理stash 中留在原 segment 的条目还会尝试TryMoveFromStash卸载回常规桶。反向的收缩操作由DashTable::Mergesrc/core/dash.h完成当两个同深度的“buddy”segment 都很空时可把二者合并回一个回收内存。为什么 Dashtable 更省内存、更快内存维度目录开销几乎消失要承载 N 个条目Dashtable 只需约N/840个目录项即8N/840字节。以 100 万条目为例大约只需1000000/840 ≈ 1200个 segment主数组仅约 9600 字节而 RD 无论如何都需要整整8N 8MB的桶数组。无需 dictEntry 之类的链节点segment 采用开放寻址 探测probing不需要链式哈希表那样的额外指针链。元数据极薄Dragonfly 的实现中每条记录的平均“税”tax不足20 比特而 RD 光是dictEntry.next指针就要 64 比特。增量扩容不分配大表每次分裂只新增一个 segment而不是一次性分配2N个桶。文档给出更精确的估算假设键值对条目与 RD 一样是两条 8 字节指针则在 100% 利用率下DT ≈ 16N (8N/840) 2.5N O(1) ≈ 19N 字节这个数字非常接近 16 字节的理论最优值。在最坏情况下所有 segment 恰好同时翻倍、利用率降到 50%可能达到38N字节/条。但在实践中每个 segment 独立增长因此整体内存平滑地维持在22~32 字节/条即6~16 字节/条的开销相比 RD 的 16~32 字节几乎砍半。CPU 维度RD 每次插入需要分配一个dictEntry、删除时再释放且链式访问对现代 CPU 缓存极不友好工程与研究社区普遍认为链式方案慢于开放寻址方案。Dashtable 虽然也要经过一层目录指针间接寻址但目录非常小上面的例子中约 9K 字节可整体驻留 L1 缓存确定 segment 之后插入操作主要命中 1~3 条缓存行。扩容时 RD 要分配2N大小的桶数组——想象一次性分配 1 亿个桶的开销Dashtable 每次只做定长 segment 的分配消除了延迟尖峰、降低了尾延迟。需要强调的是Dashtable 并不能大幅降低整体内存——它的首要目标是减少围绕字典管理本身的浪费。但正是“元数据足够薄”这一点让 Dragonfly 得以在表元数据中塞入自有属性从而支撑 forkless save 等智能化算法详见后文。源码佐证从哈希布局到按段遍历为了验证上文的设计描述可以对照核心源码哈希位布局DashTable::Findsrc/core/dash.h的注释明确给出哈希结构[SSUUUUBF]S为 segment id取哈希的高global_depth位见DashTableBase::SegmentId中hash (64 - global_depth)B为 bucket idF为 8 位指纹fingerprint。segment 定位后段内用哈希低位完成指纹比对与探测。指纹加速BucketBase::CompareFPsrc/core/dash_internal.h用 SSE 指令一次性把 16 字节指纹数组与目标指纹比较并折叠成位掩码实现极快的预筛Segment::FindIt中还对 home bucket 做了__builtin_prefetch预取。按段遍历与游标DashTable::Traverse/TraverseBucketssrc/core/dash.h以DashCursorsrc/core/dash_internal.h游标驱动按段遍历游标在表扩容/收缩后依然稳定有效——这是快照snapshot、过期扫描与 forkless save 依赖的遍历基础。内存计量DashTable::mem_usagesrc/core/dash.h只统计表的扁平内存segment_.capacity() * sizeof(void*) sizeof(SegmentType) * unique_segments_即目录数组加实际 segment 内存。统计计数表级维护garbage_collected_与stash_unloaded_计数器src/core/dash.h用于观测 GC 与 stash 卸载的效果。这些实现细节与文档描述完全吻合也说明 Dashtable 的“薄元数据”不是靠牺牲特性换来的而是通过位图压缩SlotBitmap把 busy/probe/count 压缩进 32 位字、指纹预筛和分段局部性共同实现的。实测基准文档中的对比数据文档中的基准运行于作者 2022 年 5 月的家用机AMD Ryzen 5 3400G8 核使用内部调试命令debug populate填充数据该命令的实现见 src/server/debugcmd.cc可绕过网络与解析直接压测字典填充速度。以下数据仅代表当时本地环境的对比结果请注意其时效与硬件前提。单线程填充debug populate 2000000020M 条目小数据DragonflyRedis 6耗时10.8s16.0s内存占用1GB1.73G查看 Redis 6 的info memory可知其used_memory_overhead高达1.0GB——即 1.73GB 分配内存中约六成被元数据吃掉。在小数据场景下Redis 的元数据成本甚至超过了数据本身。多线程填充Dragonfly 跑满 8 核DragonflyRedis 6耗时2.43s16.0s内存占用896MB1.73G得益于 share-nothing 架构每个线程维护自己的 Dashtable 分片各填 20M 的 1/8速度接近 8 倍提升由于各线程的表更小总内存甚至进一步下降但文档也指出这并非恒成立——具体取决于相对哈希表利用率的位置。Forkless SaveBGSAVE 内存曲线Dragonfly 的 BGSAVE 与 SAVE 本质上是同一套流程——完全异步算法维护点-时间快照保证。测试分三步在两台服务器上执行debug populate 5000000 key 1024快速填充约 5GB 数据用memtier_benchmark --ratio 1:0 -n 600000 --threads2 -c 20 --distinct-client-seed --key-prefixkey: --hide-histogram --key-maximum5000000 -d 1024制造持续更新流量对两台服务器执行bgsave并持续测量内存。由于 Redis 的 BGSAVE 通过 fork 子进程共享父进程内存难以精确测量文档采用cgroupsv2对每台服务器单独建组并采样memory.currentfork 出的 Redis 子进程继承父进程 cgroup因此能准确反映总内存。从曲线看BGSAVE 尚未开始前 Redis 已多用约 50% 内存约第 14 秒 BGSAVE 在两端启动Dragonfly 曲线上几乎看不出事件且几秒内完成快照第 39 秒 Redis 完成快照其峰值内存接近自身基线的 3 倍。这正是 Dashtable 薄元数据 分段遍历带来的 forkless save 优势的直观体现。写入期间的过期Expiry效率高效过期对缓存类场景至关重要。Dragonfly 利用 Dashtable 的分段结构实现低 CPU 开销的被动过期并辅以后台渐进扫描。其核心思想是Dashtable 在插入导致 segment 变满、需要分裂时恰好是执行垃圾回收的天然时机——只扫描这一个 segment扫描其 bucket 中的过期条目并删除若删掉了足够多甚至可以完全避免这次表扩容扫描成本不超过分裂本身可视为O(1)。这一逻辑在源码中的落点是PrimeEvictionPolicy::GarbageCollectsrc/server/db_slice.cc遍历PrimeTable::HotBuckets中的候选桶home bucket、邻居与 stash对过期条目调用ExpireIfNeeded删除其相关统计expired_keys等也维护在DbTableStats中src/server/table.h。测试命令本地运行memtier_benchmark --ratio 1:0 -n 600000 --threads2 -c 20 --distinct-client-seed \ --key-prefixkey: --hide-histogram --expiry-range30-30 --key-maximum100000000 -d 256使用 256 字节大 value 以降低元数据节省的影响DragonflyRedis 6峰值内存1.45GB1.95GB平均 SET qps131K100K注意 Redis 的 qps 低约 30%意味着两者维持的工作集大小不同Dragonfly 任一时刻需承载至少20s × 131K个条目Redis 只需20s × 100K个。面对大 30% 的工作集Dragonfly 的峰值内存反而少用 25%。文档亦明确声明该测试仅为作者本地演示不代表真实吞吐基准请勿据此得出性能优劣结论。小结Dashtable 把经典可扩展哈希与现代开放寻址工程技巧结合为 Dragonfly 带来了三项核心收益目录开销近于零1M 条目仅约 9.6KB、每条记录元数据仅约 20 比特整体开销 6~16 字节/条、增量扩容按段进行从而消除延迟尖峰。更重要的是这个分段化的结构为 forkless save、按段垃圾回收等引擎级能力提供了天然支点——这些正是 Dragonfly 作为 Redis/Memcached 现代替代品的内存效率来源。想继续深入可以直接阅读 src/core/dash.h 与 src/core/dash_internal.h 的完整实现以及 src/core/dash_test.cc 中的测试用例。【免费下载链接】dragonflyA modern replacement for Redis and Memcached项目地址: https://gitcode.com/GitHub_Trending/dr/dragonfly创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考