Transient 及持久化

引言

本文是系列文章的最后一部分，主要介绍如何实现持久化 List 的最后一步：实现 Transient（临时可变）及持久化功能。

如果您尚未浏览过本系列的前序文章，建议先参考以下内容以建立背景知识：

在前文中，我们已经了解了如何实现一个 Vector Trie，以及如何利用它来构建共享数据结构的持久化 List。其核心思路是：在每次修改时，复制从根节点到被修改节点路径上的所有节点，并使用新的 Root 节点构造一个新的 List HEAD 数据结构。这样，通过新的 HEAD 可以访问新数据，而旧的 HEAD 仍能保留旧数据的状态。

基于这一思路，我们需要调整 List 的接口设计。对于每一个会修改 List 元素的操作，都必须返回一个新的 List 对象，而非在原对象上直接修改。例如：

type List interface {
    Get(n int) (interface{}, bool)
    Set(n int, value interface{}) (List, bool)
    PushBack(value interface{}) List
    RemoveBack() (List, interface{})
    Len() int
}

为了实现上述接口，我们主要有两种方案：

直接返回新对象：对于 Set、PushBack 和 RemoveBack 函数，直接修改实现逻辑，使其返回新的 listHead。
引入 Transient 机制：先实现 TransientList，对于修改操作，先将当前 List 转换为 TransientList 进行修改，最后将结果持久化返回。

虽然基于之前的代码设计，两种方案的实现难度差别不大，但考虑到 Transient 支持对数据结构进行一连串高效操作，我们决定采用第二种方案。这不仅性能更优，也能使代码更简洁、复用程度更高。

那么，什么是 Transient？下面我们将详细介绍其原理与实现。

Transient 的原理

前文提到，持久化数据结构的实现原理是“路径复制”（Path Copying）。在我们的设计中，每个节点的宽度为 32。如果连续修改几个相邻的元素，即使它们位于同一个叶子节点上，该节点也会被反复复制。这种行为在批量修改场景下是非常低效的。

为了高效地进行一连串修改，一种解决方案是允许持久化数据结构临时转变为非持久化（Mutable）状态。在这一连串修改完成后，再将其转变回持久化状态。这样，中间的每次修改都可以在原地进行（In-place），从而极大地改善性能。这种临时产生的非持久化数据结构，就是我们所说的 Transient。

风险与权衡

使用 Transient 存在一定的风险：

线程安全：作为一种可变数据结构，Transient 通常是非线程安全的。并发操作可能导致竞态条件（Race Condition）。
持久性破坏：如果用户在将 Transient 转变为持久化对象后，仍然保留了对该 Transient 的引用并继续修改它，那么生成的持久化对象实际上也会被改变。这意味着引入 Transient 可能会导致持久化对象的不可变性被破坏。

尽管存在风险，但考虑到性能上的显著提升，引入 Transient 仍然是值得的。其实现依赖于两个关键点：

唯一 ID 标记：为每个 Transient 分配一个全局唯一的 id。当 Transient 修改内部结构时，确保所有修改过的节点都打上这个 id 作为标记。
所有权检查：当 Transient 需要修改节点时，先检查目标节点的 id 是否与自身相同。
- 如果相同：说明该节点是当前 Transient 之前已经修改或复制过的，可以直接在原节点上修改。
- 如果不同：说明该节点可能属于之前的某个 Transient 或持久化对象。为了防止污染原有数据，必须先复制当前节点，再进行修改。

这两条策略保证了我们可以安全地修改 Transient 而不会意外改变原来的数据。关键在于，通过为 Vector Trie 的节点打上 id 标志，Transient 可以判断节点的内存所有权。对于 id 不一致的节点，它们属于历史版本，不应直接修改；而 id 一致的节点，表明是当前 Transient 新近修改过的，可以再次修改。这一步基于一个假定：持久化过的 Transient 不再会被使用者修改。这也是为什么若 Transient 持久化后仍被修改，会导致持久化对象不可变性被破坏的原因。

下图对比了持久化 List 和 Transient 在执行修改时的差异：

上方（不使用 Transient）：右边三种不同颜色代表连续的三次修改。每次修改都会产生一个新的 Root 节点和一份新的叶子节点，效率较低。
下方（使用 Transient）：每个节点包含一个 ID（图中紫色标记）。第一次修改时，为 Transient 分配新 ID b。检查发现目标节点 ID 为 a，与当前 ID 不同，因此需要复制。在接下来的两次修改中，由于 Transient 生命周期内 ID 不变，目标节点 ID 已与当前 Transient 一致，因此无需再复制，可直接进行原地更新。

结构复用

由上述原理可知，Transient 和持久化 List 可以共享一套底层数据结构，差别仅在于 Transient 拥有一个 ID 而 List 没有。为了区分这两种情况，我们为所有的 List HEAD 分配一个特殊的 ID（例如 0）。List 和 Transient 之间的转换可以通过以下手段实现：

List 转 Transient：使用 ID 生成器生成一个唯一且不同于 List ID 的 ID（如正整数）并分配给 List。
Transient 转 List：将 Transient 的 ID 重置为 List ID（如 0）。

在 Go 语言中，得益于其特殊的类型设计，我们可以将 List 内部数据结构实现为 Transient 内部数据结构的一个衍生类型（基于相同底层结构），从而方便地进行类型转换。

Transient 的实现

Unique ID 生成器的实现

对于 Transient 而言，如何为每次修改生成独一无二的 ID 至关重要。现实中存在多种唯一 ID 生成算法，有的适用于分布式，有的轻量级。在这里，我们选择最简单的方式：累计 uint64 类型的正整数。

通过在单例情况下累计正整数，我们可以保证生成的 Unique ID 在当前进程中具有唯一性。其原理是通过 sync/atomic 包下的原子操作 AddUint64 来实现递增。这一操作既快速又线程安全。

以下是实现这一功能的内部包 counter：

package counter

import "sync/atomic"

var id uint64 = 0

func Next() uint64 {
    return atomic.AddUint64(&id, 1)
}

List 接口的更新

前文提到，可以将 List 实现为基于 Transient 结构的类型。在这一步，我们将之前实现的 List 内部数据结构重命名为 tListHead，代表它是 Transient List 的 Head，之前实现的方法也一并转移过来。此外，我们需要在新的 tListHead 和内部的 Trie 树节点上都添加 ID 字段：

// Transient List Head
type tListHead struct {
    id     uint64
    len    int
    level  int
    offset int
    root   *trieNode
    tail   *trieNode
}

// Trie Node
type trieNode struct {
    id       uint64
    children []interface{}
}

然后我们重新定义 List 的接口和实现方法：

type List interface {
    Get(n int) (interface{}, bool)
    Set(n int, value interface{}) (List, bool)
    PushBack(value interface{}) List
    RemoveBack() (List, interface{})
    TransientList() TransientList
    Len() int
}

type listHead tListHead

新的接口不再是在原来的基础上进行修改，而是每次操作都返回新的 List 对象。我们还添加了一个方法 TransientList 用于将当前 List 转换为一个 Transient。注意到 listHead 只是基于 tListHead 定义的新类型，因此在 Go 语言中它们之间可以相互类型转换。

接下来我们定义一个全局公共的 empty 变量代表空的 List。由于我们希望所有的空 List 都一样，且持久化 List 是不会被改变的，因此我们并不会在 New 时创建新的空对象，而是每次都返回这一个对象。这样也节约了新建 List 时的内存消耗。

var empty = &listHead{0, 0, 0, 0, nil, nil}

func New() List {
    return empty
}

List 的 Get 方法因为不会改变元素的值，我们直接通过类型转化的方法将 listHead 转换为 tListHead 并调用后者的对应方法获得结果：

func (head *listHead) Get(n int) (interface{}, bool) {
    return (*tListHead)(head).Get(n)
}

对于其它修改操作，我们都先将其转换为 Transient，执行完修改操作之后再持久化回来，这样就可以获得新的 List 了。

func (head *listHead) Set(n int, value interface{}) (List, bool) {
    t := head.TransientList()
    if t.Set(n, value) {
        return t.Persist(), true
    } else {
        return head, false
    }
}

func (head *listHead) PushBack(value interface{}) List {
    t := head.TransientList()
    t.PushBack(value)
    return t.Persist()
}

func (head *listHead) RemoveBack() (List, interface{}) {
    if head.len == 1 {
        value, _ := head.Get(0)
        return empty, value
    } else {
        t := head.TransientList()
        value := t.RemoveBack()
        return t.Persist(), value
    }
}

下面给出了 TransientList 方法的实现。由于 List 的不可变性质需要被保留，因此转化为 Transient 实际上需要新建立一个 tListHead，这样对于 Transient 的修改就不会影响到原来的 List。这里调用了之前实现的 counter 包来获得 Unique ID。

func (head *listHead) TransientList() TransientList {
    id := counter.Next()
    return &tListHead{id, head.len, head.level, head.offset, head.root, head.tail}
}

Transient 修改操作的实现

接下来还需要更新 Transient 修改操作的实现，以保证不会影响到其它 Transient 以及之前的持久化 List。之前的 List 在实现过程中已经部分考虑了这个问题，大部分操作被设计为递归执行，同时对 Trie 树的递归操作会赋值给原来节点。在这一基础上，我们首先为 trieNode 添加 clone 和 setChild 两个方法。

clone 方法会将当前节点的内容复制一遍并返回新的节点，它接受一个 id 参数，新复制出来的节点的 id 属性会被设定为该参数。

func (node *trieNode) clone(id uint64) *trieNode {
    children := make([]interface{}, NODE_SIZE)
    copy(children, node.children)
    return &trieNode{id, children}
}

setChild 则是方便实现修改节点功能的函数，它的第一个参数也是 id。如果传入的 id 与节点原来的 id 相同，则这一方法直接在原来的节点上进行修改并返回原来的节点；否则它将会 clone 节点并在新的节点上进行操作。

func (node *trieNode) setChild(id uint64, n int, child interface{}) *trieNode {
    if node.id == id {
        node.children[n] = child
        return node
    } else {
        newNode := node.clone(id)
        newNode.children[n] = child
        return newNode
    }
}

之前 List 修改操作的各个内部函数也都被加上了 id 作为参数。除此之外，如果 Set 前后 List 包含值相同，我们希望实际效果是对象没有被修改，在这一步我们也做了一些小心操作来尽可能保证。具体的代码不再赘述，完整的代码请参考这个文件。

下面是将 Transient 转化为持久化的函数。由于我们预期用户在将 Transient 持久化之后不会再修改原来的 Transient（尽管无法从代码上强制保证），所以我们可以简单地使用类型转换来将 tListHead 转换为 listHead，并将 ID 重置。

func (head *tListHead) Persist() List {
    persistHead := (*listHead)(head)
    persistHead.id = 0
    return persistHead
}

总结

本文介绍了 Transient 的实现原理和最终实现持久化 List 的方法。可以看出，Transient 是为了提高持久化 List 在连续修改操作下的效率而引进的数据结构，同时引入 Transient 也会简化持久化 List 实现的复杂度。

但是，如果用户以不正确的方式使用 Transient（例如持久化后继续修改），可能会破坏持久化 List 的不可变性。在 Transient 存在的情况下，持久化 List 的修改操作被实现为：先转换为 Transient 并修改，最终将 Transient 持久化。

本文地址：https://1diff.fun/archives/transient-ji-chi-jiu-hua.html

如果对本文有什么问题或疑问都可以在评论区留言，我看到后会尽量解答。