Persistent data structures

发表于 |

在 rust 中，immutable 的数据结构的性质是非常好的。在大部分函数式语言中，都不允许存在 mutable 的数据。

如果要在不可变数据结构上进行修改，就需要 clone 一份出来。因此：

  • 对于一些较大的结构，希望能够尽量复用
  • 如果此时只有一份引用，则可以直接获取 mut 引用就地修改

所以有了 Persistent data structures 的概念：

  • 每一次修改该结构，都会保留之前的版本
  • 历史的版本可以被查询
  • 如果历史版本的数据也支持修改，则称为 Full persistence，否则称为 Partial persistence

实现方案

Copy on Write

用一个数组存放所有的历史版本，非常 bruteforce。

Fat node

为每一个 field 维护历史记录。例如

1
2
3
4
5
struct Node {
    int value;
    Node* left;
    Node* right;
}

会变成

1
2
3
4
5
struct FatNode {
    vector<Pair<version, value>> value_history;
    vector<Pair<version, Node*>> left_history;
    vector<Pair<version, Node*>> right_history;
}

查询的过程就有点像是 MVCC 了。给定一个 version，去 lower_bound 找到最大的小于 version 的修改。

容易看到，Fat node 不支持 Full persistence。

Split

Fat Node 不能无限制增长，否则：

  • 历史太长
  • 查询复杂度上升
  • 节点缓存局部性变差

因此，需要将节点 split 为两个节点：

  • 新节点记录最新版本的值
  • 老节点保留早期历史
  • 结构中指向该节点的指针，也在相应版本中被更新为指向新的节点

Path copying

常见的结构实现

List

Vec

Reference