Go语言中对结构体进行原子比较与交换的实现策略

在go语言中，直接对包含指针和整数的复合结构体执行原子比较与交换（CAS）操作是不被标准sync/atomic包支持的，因为大多数架构仅支持对单个机器字进行原子操作。本文将探讨两种实现类似功能的策略：利用指针位窃取（Bit Stealing）在64位系统上编码额外信息，以及采用写时复制（copy-On-Write, COW）模式通过原子替换结构体指针来间接实现对结构体内容的原子更新。

原子操作与结构体：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)

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

立即学习“go语言免费学习笔记（深入）”；

策略二：写时复制 (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时，执行以下步骤：

   

   Latent Labs

   36

   查看详情

   • 读取当前的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）模式是更推荐的选择，因为它更易于理解和维护，并且适用于更广泛的场景。在设计无锁数据结构时，选择合适的原子操作策略是确保并发正确性和性能的关键。