Go结构体原子比较交换技巧

从现在开始，努力学习吧！本文《Go语言结构体原子比较交换实现方法》主要讲解了等等相关知识点，我会在golang学习网中持续更新相关的系列文章，欢迎大家关注并积极留言建议。下面就先一起来看一下本篇正文内容吧，希望能帮到你！

原子操作与结构体：Go语言的限制

在构建高性能的无锁数据结构时，原子比较与交换（Compare And Swap, CAS）是核心原语。例如，在Maged M. Michael和Michael L. Scott的无锁队列算法中，经常需要对包含指针和计数器的复合类型（如pointer_t）进行CAS操作。然而，Go语言的sync/atomic包提供的CompareAndSwapPointer、CompareAndSwapUint64等函数，仅支持对单一机器字（如uintptr、int64）进行原子操作。

当尝试对以下结构体执行原子CAS时：

type pointer_t struct {
    ptr   *node_t
    count uint
}

type node_t struct {
    value interface{}
    next  pointer_t // 目标是对此字段进行原子更新
}

直接使用atomic.CompareAndSwap是不可能的，因为pointer_t是一个包含两个字段的结构体，其大小通常超过一个机器字。大多数CPU架构只支持对单个机器字进行原子CAS操作。为了解决这个问题，我们需要采用一些间接策略。

策略一：指针位窃取 (Bit Stealing)

原理： 在64位系统中，内存地址空间通常远小于64位所能表示的范围（例如，在现代系统中，通常只使用48位或52位地址线）。这意味着64位指针的高位或低位可能存在未被使用的比特位。我们可以“窃取”这些未使用的比特位来存储额外的小型数据，例如一个计数器。

实现细节与注意事项：

1. 位掩码操作： 在将指针存储到uintptr类型时，使用位掩码将计数器编码到指针的空闲位中。
2. 原子操作： 使用atomic.CompareAndSwapPointer对这个编码后的uintptr进行原子操作。
3. 解码： 在使用指针之前，需要通过位掩码将计数器从指针中分离出来，并将指针恢复到其原始形式。
4. 局限性：
   • 此方法仅适用于64位系统，因为32位系统上的指针通常没有足够的空闲位。
   • 能存储的计数器值大小有限，取决于可用的比特位数。
   • 需要对指针进行复杂的位操作，增加了代码的复杂性和出错的可能性。
   • 需要确保被窃取的位确实是空闲的，这可能依赖于特定的操作系统和架构特性。

示例概念： 假设我们决定使用指针的最低有效位来存储一个小的计数器（例如，2-4位）。

• 编码： encodedPtr = (uintptr(actualPtr) & ^mask) | (count & mask)
• 解码指针： decodedPtr = (*node_t)(unsafe.Pointer(encodedPtr & ^mask))
• 解码计数： decodedCount = uint(encodedPtr & mask)
• 原子更新： atomic.CompareAndSwapUintptr(&target, oldEncoded, newEncoded)

这种方法虽然高效，但其复杂性和平台依赖性使其在实际应用中需要谨慎评估。

策略二：写时复制 (Copy-On-Write, COW)

原理： 写时复制（COW）是一种更通用且更安全的方法，适用于需要原子更新任意大小结构体的场景。其核心思想是将需要原子更新的结构体视为不可变对象。当需要修改结构体时，不直接修改原始结构体，而是：

1. 创建一个原始结构体的副本。
2. 在副本上进行修改。
3. 使用原子操作（如atomic.CompareAndSwapPointer）将指向旧结构体的指针替换为指向新结构体的指针。

实现细节与注意事项：

1. 修改结构体定义： 将node_t中的next字段从pointer_t类型修改为*pointer_t类型。这样，node.next就变成了一个指向pointer_t结构体的指针，我们可以对这个指针进行原子操作。

   type pointer_t struct {
       ptr   *node_t
       count uint
   }
   
   type node_t struct {
       value interface{}
       next  *pointer_t // 修改为指针类型
   }

2. 原子更新逻辑： 当需要更新node.next时，执行以下步骤：

   • 读取当前的node.next指针，得到旧的pointer_t实例。
   • 创建一个新的pointer_t实例，复制旧实例的内容，并进行必要的修改（例如，更新ptr或count）。
   • 使用atomic.CompareAndSwapPointer尝试将node.next字段从指向旧pointer_t的指针原子地替换为指向新pointer_t的指针。如果CAS失败（说明在读取和更新之间有其他协程修改了该字段），则需要重试。

示例代码：

import (
    "sync/atomic"
    "unsafe"
)

// pointer_t 定义不变
type pointer_t struct {
    ptr   *node_t
    count uint
}

// node_t 的 next 字段改为 *pointer_t
type node_t struct {
    value interface{}
    // next 字段现在是一个指向 pointer_t 结构体的指针
    // 我们将对这个指针进行原子操作
    next  *pointer_t
}

// updateNodeNext 尝试原子地更新一个 node_t 的 next 字段
// node: 目标 node_t 实例
// oldNextPointerT: 期望的当前 node.next 指向的 pointer_t 实例
// newNodeRef: 新的 node_t 实例，用于更新 pointer_t.ptr
func updateNodeNext(node *node_t, oldNextPointerT *pointer_t, newNodeRef *node_t) bool {
    // 1. 创建一个新的 pointer_t 结构体实例
    //    包含更新后的 node 引用和递增的计数
    newNextPointerT := &pointer_t{
        ptr:   newNodeRef,
        count: oldNextPointerT.count + 1, // 计数器递增
    }

    // 2. 使用 atomic.CompareAndSwapPointer 原子地替换 node.next 字段
    //    参数解释：
    //    - (*unsafe.Pointer)(unsafe.Pointer(&node.next)): 获取 node.next 字段的地址，并转换为 *unsafe.Pointer 类型
    //    - unsafe.Pointer(oldNextPointerT): 期望的旧值（oldNextPointerT 的内存地址）
    //    - unsafe.Pointer(newNextPointerT): 新值（newNextPointerT 的内存地址）
    return atomic.CompareAndSwapPointer(
        (*unsafe.Pointer)(unsafe.Pointer(&node.next)),
        unsafe.Pointer(oldNextPointerT),
        unsafe.Pointer(newNextPointerT),
    )
}

// 示例使用
func main() {
    // 假设我们有一个初始的 node 和它的 next 字段
    initialNode := &node_t{value: "A"}
    initialNextPointer := &pointer_t{ptr: nil, count: 0}
    initialNode.next = initialNextPointer

    // 假设我们想要将 initialNode 的 next 字段更新为指向 newChildNode
    newChildNode := &node_t{value: "B"}

    // 尝试原子更新
    success := updateNodeNext(initialNode, initialNextPointer, newChildNode)
    if success {
        // 更新成功，initialNode.next 现在指向一个新的 pointer_t 实例
        // 这个新实例的 ptr 字段指向 newChildNode，count 为 1
        println("Atomic update successful!")
        println("New next pointer count:", initialNode.next.count) // 应该输出 1
    } else {
        println("Atomic update failed, retry needed.")
    }
}

注意事项：

• 内存分配： 每次修改都会创建一个新的pointer_t实例，这会引入额外的内存分配和潜在的垃圾回收开销。对于频繁更新的场景，需要评估其性能影响。
• 不可变性： pointer_t结构体本身在被引用后，其内容应被视为不可变。所有修改都通过创建新副本来实现。
• Go 1.19+ atomic.Pointer[T]： 对于Go 1.19及更高版本，可以使用atomic.Pointer[T]来更安全、更简洁地实现对任意类型指针的原子操作，避免直接使用unsafe.Pointer。上述示例为兼容性考虑使用了unsafe.Pointer。

实际应用与参考

上述COW模式是实现无锁数据结构（如无锁队列、无锁链表）的常用技术。例如，在实现无锁链表时，节点的next指针可能需要携带一个“标记”或“版本号”来处理节点删除等并发问题。Go语言中，可以参考开源项目中的实现，例如tux21b/goco库中的list.go文件。该文件中的MarkAndRef结构体与pointer_t非常相似，它使用一个布尔值（标记）和一个指针，并通过原子操作来确保节点状态的一致性。

总结

在Go语言中直接对复合结构体进行原子比较与交换是不支持的。为了实现类似功能，我们可以选择两种主要策略：

1. 指针位窃取： 利用64位指针的空闲位编码额外信息，通过atomic.CompareAndSwapPointer进行原子操作。此方法高效但复杂且平台依赖性强。
2. 写时复制 (COW)： 将结构体视为不可变，通过原子替换指向结构体实例的指针来间接更新其内容。此方法通用、安全，但会引入内存分配开销。

在大多数情况下，写时复制（COW）模式是更推荐的选择，因为它更易于理解和维护，并且适用于更广泛的场景。在设计无锁数据结构时，选择合适的原子操作策略是确保并发正确性和性能的关键。

好了，本文到此结束，带大家了解了《Go结构体原子比较交换技巧》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多Golang知识！