精读《Immutable 结构共享》：以空间换时间的持久化数据结构原理与工程实践

文档技术博客教程【免费下载链接】weekly前端精读周刊。帮你理解最前沿、实用的技术。项目地址https://gitcode.com/GitHub_Trending/we/weekly点击查看免费下载本文是对前端精读周刊《Immutable 结构共享是如何实现的》一文的深度展开。文章以 Hash maps trie 与 Vector trie 两种持久化数据结构为主线讲清 Immutable 库以空间换时间的底层设计并结合 redux 的引用相等性判定回答三个高频工程问题Object.assign能否替代 ImmutableMap性能更好能否替代 Immutable什么时候才真正需要 Immutablejs读完你既能理解 5bit 切分寻址的原理也能据此在项目里做出正确的数据不可变方案选型。1 引言为什么结构共享值得预热本篇文章的讨论起点是 mobx-state-tree 的发布。这个库实现了 mutable 到 immutable 数据的自由转换让开发者可以用 mobx 的写法组织数据流再无缝接入 redux 生态或继续使用 mobx 生态。mobx-state-tree 本质上把事务性、可追溯性与依赖追踪特性结合在了一起同时兼顾开发体验与数据流可维护性。而这一切能力的地基正是结构共享Structural Sharing。所谓结构共享指的是当一棵数据树发生局部更新时根节点引用必须改变但未被修改的节点其引用依然指向旧节点从而让新的完整数据与旧数据在内存中最大限度复用。这个机制是否高效直接决定了 mobx-state-tree、Immutablejs、Immer 这类库在大数据量下的可用性。结构共享并不是一个孤立的技巧其背后依赖的是 Hash maps trie 与 vector tries 两类树状结构的支持。如果让我们自己设计一个结构共享功能需要考虑哪些点这正是本期精读文章给出的答案也是本文要展开的核心。2 内容概要Object.assign 大对象操作的成本问题先看结构共享要解决的最直接问题引用操作的数量。使用Object.assign作用于大对象时速度会成为瓶颈。比如对一个拥有100,000个属性的对象执行合并操作一次操作耗费了134ms。性能损失的主要原因是结构共享操作需要遍历近 10 万个属性而这些引用操作本身就耗费了 100ms 以上的时间。进一步观察会发现一个关键事实引用指向到任何对象的损耗几乎一致——无论目标对象极小还是无穷大建立一次引用的耗时几乎没有区别。因此解决问题的方向就变成了设计一种精心构造的树状结构把原本打平的引用建立深度用树的层级来减少每次更新需要触碰的引用数量vector tries就是其中一种解决方案。寻址路径示例如下假设 key 为t0143c274经过 hash 后得到的值为621051904注此处的 hash 与 md5 不同例如hash(a) 0、hash(c) 2。将这个值转化为二进制得到10010 10000 01001 00000 00000 00000这条路径是唯一的。为了减少树的深度按5bit 切分切分后的每一段路径依然是唯一的寻址时就从根节点逐段下钻。因此结构共享的核心思路可以概括为一句话以空间换时间。通过冗余的树形索引结构换取更新操作 O(log n) 级别的时间复杂度。3 Immutable 树结构的特性树宽与树高的平衡结构共享的树形结构有一个重要的特性权衡当树越宽子节点越多时树的高度会下降查询效率随之提高但更新效率会下降。试想极限情况如果每个节点都拥有所有子节点树就退化为线性结构更新时整条链路的节点几乎都要重建结构共享的优势荡然无存。为了在更新与查询之间取得平衡Immutablejs 选择了5bit 一分割每个节点拥有2^5 32个子节点。这样既把树高控制在合理范围对于 10 万量级的数据路径深度依然很浅又不会因为分支过宽导致更新代价线性增长。在此基础上通过Vector trie与Hash maps trie两种结构压缩空间使树的深度最小、性能最优。下面分别展开。3.1 Vector trie按顺序索引的持久化向量Vector trie 的原理是使用二叉树实际实现为多叉树将所有值按照顺序从左到右存放于叶子节点。因为叶子节点的顺序天然对应数组的下标顺序所以它适合用来实现 Immutable 的List有序列表。其更新策略是结构共享的教科书式演示当需要更新某个下标的值时只将更新路径上的节点生成新的对象没有被改动路径经过的节点继续沿用旧引用不做任何复制。例如对一棵深度为 5 的 vector trie 更新一个叶子节点需要新建的对象只有从根到该叶子的 5 个路径节点每个节点内部是 32 个槽位的数组复制成本很低其余兄弟子树全部复用旧引用。对比扁平数组的整体拷贝引用操作数量从 O(n) 降到了 O(log n)这正是第一节中 134ms 瓶颈的解法。3.2 Hash maps trie键的哈希寻址与树的压缩Immutablejs 对Map无序键值集合使用 Hash maps trie 进行优化键先经过哈希得到定长的二进制路径再按 5bit 切分逐段定位。为了进一步压缩空间Immutablejs 做了两类优化树宽压缩如果路径中的相邻几段在整棵树上没有分叉就把它们聚合为一个节点。比如10010 10000两段路径只通向唯一子节点时可以直接合并成一个节点减少中间层。树高压缩同时移除同级的空节点即路径上没有任何兄弟键值的空洞层进一步压低树的高度。压缩后Map 的寻址路径变短内存占用更低。再结合 Vector trie 对有序序列的支持Immutablejs 得以同时保证更新性能最优且查询路径相对较优。这也是结构共享真正达到可用的两个支柱——Hash maps trie 负责无序键值集合Vector trie 负责有序序列两者配合覆盖了日常数据的大部分形态。4 Object.assign 是否可替代 Immutable先给结论可以而且Object.assign本身就是最朴素的结构共享实现。结构共享的定义是根节点的引用改变但对未修改的节点引用依然指向旧节点。Object.assign恰好满足这个语义const objA { a: 1, b: 2, c: 3 } const objB Object.assign({}, objA, { c: 4 }) objA objB // false objA.a objB.a // true objA.b objB.b // trueobjA objB为false新对象产生了新的根引用符合 redux 的更新判定前提objA.a objB.a与objA.b objB.b为true未修改的a、b属性直接复用了旧引用没有发生任何深拷贝。这证明Object.assign完全可以胜任 Immutable 场景。但正如前文所述当对象属性庞大时10 万属性级Object.assign需要遍历全部属性建立新引用效率较低因此在特殊的大数据场景不适合用它生成 immutable 数据。不过对大部分场景而言性能并不是瓶颈Object.assign完全可用。唯一繁琐的点在于深层次对象的赋值书写起来很麻烦——每改一层子属性都要沿着父级路径逐层Object.assign代码会变得冗长且容易出错。5 Map 性能更好是否可以替代 Immutable再看另一个常见疑问原生Map在性能上优于Object.assign当一层节点达到 1,000,000 个时immutable.get的查询性能是object.key的10 倍以上那么 Map 能否替代 Immutable答案是就性能而言可以但就结合 redux 使用而言无法替代。关键在于 redux 的数据更新判定机制redux 判断数据更新的条件是对象引用是否变化并且必须满足当修改对象的子属性时父级对象的引用也要一并修改否则父级组件无法感知子属性的变化。原生Map恰好跪在这个特性上map.set(key, value)之后Map 对象本身没有产生一份新的引用它只是原地修改了内部结构。这意味着Connect 了一个style对象当它的backgroundColor属性变化时由于父级引用没有变化redux 的connect不会认为 state 发生了更新组件不会触发 reRender。因此虽然Map性能不错但它无法像Object.assign或 Immutablejs 那样为 redux 提供修改子属性后父级引用同步更新的语义支持也就无法胜任 redux 生态的数据流要求。6 仓库佐证结构共享在现代库中的工程化落地结构共享并非只存在于理论层面本仓库的姊妹篇精读正好记录了它在真实库中的两种落地形态可作为上述原理的实现证据。6.1 Immer代理 按需浅拷贝的 copy-on-write在 源码解读/48.精读《Immer.js》源码.md 中Immer 用代理对象实现了结构共享的现代版本draft是原始obj的代理用户对draft的 mutable 修改都会流入自定义settersetter 并不修改原始对象而是对base原始对象做一次浅拷贝存入copy属性并将modified置为true——浅拷贝成本远低于深拷贝加上按需触发性能可控根据parent属性递归父级不断浅拷贝直到从叶子结点到根结点的整条链路对象都换新为止——这正是更新路径上的节点生成新对象、未修改节点继续共用在工程代码里的直接体现。produce结束后若modified为false用户根本没改直接返回原始base若modified为true则递归拼接base中未修改的部分与copy中修改的部分生成最终的新对象。整个机制可以看作以空间换时间思想在 Proxy 时代的延续空间上只冗余了路径上的浅拷贝时间上避免了对整个对象的深拷贝。6.2 dob / dob-reduxmutable 写法产出 immutable 结果在 前沿技术/38.精读《dob - 框架使用》.md 中可以看到结构共享的另一种应用动机Store 扁平化的很大原因正是 js 对 immutable 支持力度不够导致深层数据修改非常麻烦。dob-redux 通过类似this.store.articles.push(article)的 mutable 写法对接 react-redux内部自动完成类似immutable.set的事情——即看起来在改原对象实际产出新引用。这与 mobx-state-tree 的目标一致也印证了本文开头提到的mutable 到 immutable 自由转换是数据流生态反复出现的核心诉求。7 总结结构共享的选型结论数据结构共享要达到真正可用需要借助 Hash maps tries 与 vector tries 两种数据结构的帮助前者以哈希路径 树宽/树高压缩支撑无序键值集合后者以顺序叶子节点 路径节点重建支撑有序序列。理解了这两者也就理解了 Immutablejs 系库的性能底牌。至于日常工程选型可以拿走这个结论在大部分情况下可以使用Object.assign代替 Immutablejs——只要你不怕深度赋值的麻烦语法其效果与 Immutablejs 一模一样因为两者都满足根引用变化 未改节点复用的结构共享语义在数据量巨大的字段上如十万级属性的对象、百万级键的 Map使用 Immutablejs 代替以提高性能借助 5bit 切分的 trie 结构把更新复杂度从 O(n) 降到 O(log n)如果项目基于 redux 且对深层数据修改频繁可以进一步关注 Immer 这类代理 copy-on-write方案以及 mobx-state-tree 这类mutable 写法产出 immutable 数据的方案它们的底层都是结构共享思想的工程化延伸。延伸阅读源码解读/48.精读《Immer.js》源码.md结构共享在 Proxy 时代的 copy-on-write 实现细节。前沿技术/38.精读《dob - 框架使用》.mdmutable 写法对接 redux 生态的实践与 Store 管理约定。前沿技术/35.精读《dob - 框架实现》.md依赖追踪依赖收集与触发回调的底层实现可与结构共享对照理解响应式数据流的另一半。前沿技术/42.精读《前端数据流哲学》.md从更宏观的视角理解 redux、mobx 等数据流方案的设计取舍。赞分享文档技术博客教程【免费下载链接】weekly前端精读周刊。帮你理解最前沿、实用的技术。项目地址https://gitcode.com/GitHub_Trending/we/weekly点击查看免费下载相关推荐猫抓浏览器资源嗅探插件:免费把网页视频保存到本地的完整指南猫抓浏览器资源嗅探插件:免费把网页视频保存到本地的完整指南 猫抓 cat catch 是一款开源免费的浏览器资源嗅探插件,能自动列出当前页面的视频、音频与图片资音视频实时竞价核心引擎RTBkit架构解析与核心组件详解实时竞价核心引擎RTBkit架构解析与核心组件详解 RTBkit是一个开源实时竞价框架专为程序化广告交易设计。这个强大的工具让开发者能够快速构建和部署高性能后端Immutable.js性能优化Trie数据结构与结构共享Immutable.js性能优化Trie数据结构与结构共享 Immutable.js通过哈希数组映射TrieHAMT数据结构和精巧的结构共享机制实现了卓越开发框架与应用上一篇从一张草图到一台装配体新手用 FreeCAD 参数化 3D 建模快速上手下一篇Swagger Codegen 生成 C 枚举模型实战以 Petstore 的 EnumTest 为例解析 OpenAPI 枚举到 .NET Standard 的完整映射创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考