Immutable 结构共享是如何实现的？

[ascoders]

文章地址：https://medium.com/@dtinth/immutable-js-persistent-data-structures-and-structural-sharing-6d163fbd73d2
鉴于 mobx-state-tree 的发布，完美融合了 redux 与 mobx，最大的特色是使用 mutable 数据，完成 immutable 的快照，这种机制是 structural sharing，让我们先夯实基础，聊聊结构共享吧。

[rccoder]

实现上

文章中 Immutable 的实现是利用 object 的 key 构建了一棵 tire 树，然后在 update 之后针对没有修改的地方依旧指向老的 node，针对改变了的地方创建新的 node。

做个动画就是 camsong 之前画过的：

正是借助这种指向老节点的方式实现了 结构共享，在保持快速复制的同时保持内存占用低（有种软链接的感觉 😂）。

疑问？
如果是 tire 树的实现方式，在数据没怎么变化的情况下目测会增高内存占用？构建树本身应该需要一定的内存占用，记忆中这棵树还是比较大的。不过利用多数组 tire 树好像可以解决，目测相关库应该做了这方面的工作？

除此，如果实现一个简单的 Immutable，也可以不上 tire 树，比如: seamless-immutable

使用上

目前 Immutable 数据的更新都是借助相关库的 API 来更新，有比较强的侵入性。用了他之后我们之前熟悉的赋值，取值甚至判断相等都会发生变化。

如果在老代码中混合使用 Immutable 容易造成混淆，写出一堆乱七八糟的东西（可以想想混用 jQuery 和 浏览器原生支持的 DOM 操作混淆使用）；在新代码中的话可以强制使用 Immutable。

最后期待 ES Next 支持原生的 Immutable。

[ascoders]

我认为结构共享核心概念不是指针指向老节点，而是使用了 tire 树。
看如下代码：

const obj = { a: 1 }
const shallow = Object.assign({}, obj, { b: 2 })
console.log(shallow === obj) // false
console.log(shallow.a === obj.a) // true

可见 Object.assign 浅拷贝本身就是创建新对象，将指针指（js里是引用）向老节点的行为，只是当对象內数据量过大的时候，本身引用链接的过程就很慢。

而 tire 树的数据结构，保证其拷贝引用的次数降到了最低，这张图最为形象：

就是通过极端的方式，大大降低拷贝数量，一个拥有100万条属性的对象，浅拷贝需要赋值 99.9999万次，而在 tire 树中，根据其访问的深度，只有一个层级只需要拷贝 31 次，这个数字不随着对象属性的增加而增大。而随着层级的深入，会线性增加拷贝数量，但由于对象访问深度不会特别高，10 层已经几乎见不到了，因此最多拷贝300次，速度还是非常快的。

[cisen]

共享应该是指新旧节点共享子节点

1. 旧节点本来就指向这个子节点，而且这个指向也不能更改，你修改需要用它的接口，它的接口不会让你改，immutablejs会new一个node，所以还是没改，所以没问题
2. 新节点指向这个旧节点应该直接通过一个=号就解决了，比如：this.entries = newEntries;

我研究过immutablejs的源码，抽象上还不是很理解，只懂点具体代码。里面好多递归，修改和两个非迭代关系的数据的比较都很耗性能。immutable无非就是读写，读比较简单略过。写的话每个节点都有自己的update函数，这个update会判断递归新建还是递归结束。实质上我觉得immutablejs好多都是抄scala的，iterable、seq、map等。估计就是scala不可变数据的js实现版，然后加上一堆好用的接口，然后就完成了。

[BlackGanglion]

本次精读的内容与刚结束的 JSConf EU 中的 Immutable data structures for functional JS 颇为相似。但均在 Tire 树的实现与优化上讲得比较简略，特做两点补充，欢迎指正~~

• 为何 Tire 树的每一个节点有 32 个分支？对于一个 Map 而言，我们所关心的是查询与更新。当树越宽（子节点越多）时，相应树的高度会下降，随之查询效率会提高，但更新效率则会下降（试想一下极限情况，就相当于线性结构）。为寻求更新与查询的平衡，我们便选择了 32 位，下图是相应的研究成果，上面一条表示更新，下面一条表示查询，点离 x 轴越近表示效率越高。

• 作为一个 Map，key 可能会有多种形式，字符串、数字、对象等等，Immutable.js 会对 key 进行 hash 映射，将得到的 hash 值转化为二进制，每 5 位进行分割后再转化为 Tire 树。之前有同学也提到了内存占用的问题，Tire 树本质就是利用空间来换取时间。Immutable.js 应该采取了一些剪枝策略，比如使用 bitmap，单一子孙直接存储，来降低空间的使用。

图中，t0143c274 经过 Immutable.js 的 hash 函数计算后，得到 621051904，转化为二进制为 10010 10000 01001 00000 00000 00000

[jasonslyvia]

文中的 不要将应用的业务逻辑与数据结构绑定 小节，提到需要搜索 10 万个 todo 中包含指定 assignee 的 todo，需要将这 10 万个元素遍历一遍，而解决方案是修改底层的数据结构，维护一个 taskId 与 assigneeId 之间的反向查找表。

事实上，反向查找表（Reverse Lookup Table）在安全领域是一个非常常见的概念，经常被用来做 MD5 的碰撞，又称彩虹表（Rainbow Table）。

所以解决方案大概就是：

{
  't79444dae': [1, 2],
  't7eaf70c3': [2],
  't2fd2ffa0': [3],
  ...
  (100,000 items)
}

默默感觉有点像 Redux 里的 normalizr 的概念？

[TingGe]

关于结构共享的话题。我来闲聊下：

可变(Mutable)和不可变（Immutable）是数据结构的属性，而不是某种语言的。

各开发语言在实现上也各有不同。举些例子： Java.util.ArrayList 是结构上不可变的对象；Clojure 则原子在结构上不可变。当然也有 Immutable Object 模式这类优良实践的存在。

我了解的 JavaScript ，还是在依赖第三方库如 mori、Immutable.js 等实现结构上不可变的对象，可能 提供的 API 上风格有些差异。

最近在 Github 上发现个 js-structural-sharing 的一个示例，摘段代码给大家参考：

// returns true if the second object has a reference to the first object anywhere in its graph tree

function referencesAnywhereInItsGraph(obj1: any, obj2: any) {
  if (isValue(obj1) || isValue(obj2)) return false;
  if (obj1 === obj2) return true;
  const obj2Props = properties(obj2, "enumerable && height>=1", x => {
    return { prop: x.prop, value: x.value };
  });

  for (let i = 0; i < obj2Props.length; i++) {
    const vb = obj2Props[i].value;
    if (isValue(vb)) continue;
    if (obj1 === vb) {
      return true;
    } else {
      const subTreeReferences = referencesAnywhereInItsGraph(obj1, vb);
      if (subTreeReferences) return true;
    }
  }
  return false;
}

通常，结构共享与不可变数据结构相关联，但它也适用于结构上不可变的对象。完全可变的数据结构是不可能的，因为结构修改会破坏结构共享。

结构上不可变的对象的组成，即你可以将两个结构上不可变的对象粘合在一起，并创建一个新的结构上不可变的对象。这样可以通过将原始对象的两个引用保持在组合来利用结构共享，即新的组合对象可以非常轻量化。

另外，可以通过结构共享再次支持可变的子视图。您可以将视图创建为结构不可变数据结构的子集，其中，视图的更改还会更改底层数据，反之亦然。

[twobin]

immutable 内部使用了 trie 数据结构，参考 hash maps trie（HAMT）和 vector trie，来实现 persist data structure。

Vector trie
由于：
（1）串具有较好的空间效率和顺序访问性能，但缺乏随机访问数据的能力；
（2）树具有较好的操作数据能力，但空间效率和顺序访问性能较差；
Vector trie 结合了串和树的特点，将所有的数据都保存在树的根节点，则树的最下一层叶子节点可以被看成是串，再将其分割成等长的分段，通过 Trie 树结构作为每个数据节点的索引。
Vector trie 在每次修改操作的时候， 复制从根到叶子节点的路径而不是直接修改它们，这样从两个根就可以访问到对数据不同时刻的两个快照。

hash maps trie（HAMT）
首先了解下 Hash Table，它是利用对象的 Hash 值对所储存的键进行散列从而实现快速的插入、删除和访问的数据结构。
HAMT 是将元素的 Hash 值按位分割成固定宽度的序列，在 Trie 树上以这些序列按顺序查找元素应该存放的位置，并且增加了节点内部的空间压缩和树高的压缩。

节点内部的空间压缩：

树高的压缩：

不过，Immutable.js 提供的API比较多，包括 List、Stack、Map、OrderedMap、Set、OrderedSet、Record等，库的体积比较大，个人觉得如果可以将 Immutable.js 拆分，提供按需打包会更好，如：'immutable/list'、'immutable/map' 等。

[ascoders]

@twobin 回答很给力。关于 immutable/list 这种引用过会带来以下问题：

1. 使用了不稳定的内部结构，而不是稳定的导出 api
2. typescript 定义无从查找
3. webpack external: "immutable" 将会失效

因此要拆我也建议拆成 immutable-list 这种包。

[camsong]

Immutable.js 提供的类大多是基于 Hash maps tries 和 vector tries 这两个数据结构来做的增强，这些都是 DAG 无回路有向图的具体实现算法。上面 @BlackGanglion @twobin 讲的很详细。

Immutable.js 文档里很明确的指出这样做的目的就是为了减少对象的复制，也就是尽可能多的把没有变化的地方依旧指向老 node。但 Object.assign 却不是这样。

我来对比下 Immutable.js 和它的最大竞争对手 Object.assign 之间的关系。

1. 对于非引用类型会简单粗暴的复制。{a: 123, b: 123, …10000 items} 当你改变其中一个 items 时，Object.assign 会把 10000 个对象全部复制一遍。因此 Object.assign 并不能实现不变数据指向旧的引用。
2. 引用数据类型，虽然 Object.assign 会使用旧对象的引用，但改对象的引用还是需要一步操作啊。但 immutable 却把这个操作降到最小，结果有了 134ms 到 1.2ms 的提升。
3. 当 key 过多时，object.key 查找变得非常慢，大部分浏览器使用类似字典查找算法，非常慢，chrome 虽然做了优化，但结果还是不如多层级的结构共享。况且按 key 查找本身也不是 Object 的重点，你可以使用 ES6 的 Map 啊，它的 key 查找性能接近 Immutable.js。实测当一层节点达到 1000000 时，immutable.get 查询性能是 object.key 的 10 倍以上。

总之，在处理大量数据情况下，immutable.js 非常有价值。