Go 高性能 - 無鎖編程

概述

鎖是一種常見的同步機制，用來解決多個線程同時訪問共享資源導致的數據競爭問題。在高併發場景下，鎖的使用可能會成爲性能瓶頸，因爲線程需要頻繁地加鎖和釋放鎖，這會增加上下文切換開銷並降低程序的吞吐量。

無鎖編程（lock-free programming）是一種併發編程技術，主要用於消除多線程編程中鎖操作帶來的性能損耗。

如果對一個共享的數據結構的所有操作都不需要加鎖 (這裏的操作一般指讀寫操作)，那麼該結構就是 無鎖（lock free）的，將數據結構和操作的組合簡稱爲 無鎖編程。

優勢

減少線程阻塞和等待時間
避免線程的優先級反轉
提高併發性能
消除競態條件（race condition）、死鎖、餓死等潛在問題
代碼更加清晰易懂

常用技術

現在幾乎所有的 CPU 指令都支持 CAS 的原子操作，我們可以直接用 CAS 來實現 無鎖（lock free）的數據結構。

CAS

通過對內存中的值與指定新值進行比較，僅當兩個數值一致時，將內存中的數據替換爲新的值。

CAS (compare and swap) 是原子操作的一種，用於在多線程中實現原子數據交換，避免多線程同時改寫某一共享數據時，由於執行順序不確定性以及中斷的不可預知性產生的數據不一致問題。

使用方法

在使用上，通常會記錄下某塊內存中的舊值，通過對舊值進行一系列的操作後得到新值，然後通過 CAS 操作將新值與舊值進行交換。

如果這塊內存的值在這期間內沒被修改過，則舊值會與內存中的數據相同，這時 CAS 操作將會成功執行，使內存中的數據變爲新值。如果內存中的值在這期間內被修改過，則舊值會與內存中的數據不同，這時 CAS 操作將會失敗，新值將不會被寫入內存。

Go 的標準庫中的 atomic 包提供了 atomic.CompareAndSwap* 系列方法來提供 CAS 操作 API。

func CompareAndSwapInt32(addr *int32, old, new int32) (swapped bool)

func CompareAndSwapInt64(addr *int64, old, new int64) (swapped bool)

...

func CompareAndSwapPointer(addr *unsafe.Pointer, old, new unsafe.Pointer) (swapped bool)

有鎖編程 和 無鎖編程 的性能差距有多少呢？我們通過基準測試來比較一下。

示例: 棧操作

我們通過一個簡單的程序來做演示，程序實現了數據結構 棧 的兩個操作 Push, Pop。

// Stack 接口
type StackInterface interface {
 Push(interface{})
 Pop() interface{}
}

Stack 接口

有鎖編程

// 互斥鎖實現的棧 (有鎖編程)
type MutexStack struct {
 // 棧元素容器用切片表示
 v []interface{}
 // 互斥鎖
 mu sync.Mutex
}

func NewMutexStack() *MutexStack {
 return &MutexStack{v: make([]interface{}, 0)}
}

func (s *MutexStack) Push(v interface{}) {
 // 可能同時有多個 goroutine 操作
 // 棧元素操作爲臨界區，需要加鎖
 s.mu.Lock()
 s.v = append(s.v, v)
 s.mu.Unlock()
}

func (s *MutexStack) Pop() interface{} {
 // 可能同時有多個 goroutine 操作
 // 棧元素操作爲臨界區，需要加鎖
 s.mu.Lock()
 var v interface{}
 if len(s.v) > 0 {
  v = s.v[len(s.v)-1]
  s.v = s.v[:len(s.v)-1]
 }
 s.mu.Unlock()
 return v
}

有鎖棧

無鎖編程

// 棧元素節點
type directItem struct {
 next unsafe.Pointer
 v    interface{}
}

// CAS 操作實現的棧 (無鎖編程)
type LockFreeStack struct {
 // 棧元素容器用鏈表表示
 top unsafe.Pointer
 // 棧長度
 len uint64
}

func NewLockFreeStack() *LockFreeStack {
 return &LockFreeStack{}
}

func (s *LockFreeStack) Push(v interface{}) {
 item := directItem{v: v}
 var top unsafe.Pointer

 for {
  top = atomic.LoadPointer(&s.top)
  item.next = top
  if atomic.CompareAndSwapPointer(&s.top, top, unsafe.Pointer(&item)) {
   // 只有 1 個 goroutine 可以執行到這裏
   // 棧元素數量 + 1
   atomic.AddUint64(&s.len, 1)
   return
  }
 }
}

func (s *LockFreeStack) Pop() interface{} {
 var top, next unsafe.Pointer
 var item *directItem

 for {
  top = atomic.LoadPointer(&s.top)
  if top == nil {
   return nil
  }
  item = (*directItem)(top)
  next = atomic.LoadPointer(&item.next)
  if atomic.CompareAndSwapPointer(&s.top, top, next) {
   // 只有 1 個 goroutine 可以執行到這裏
   // 棧元素數量 - 1
   atomic.AddUint64(&s.len, ^uint64(0))
   return item.v
  }
 }
}

無鎖棧

測試代碼

func Benchmark_Stack(b *testing.B) {
 rand.Seed(time.Now().UnixNano())

 // 初始化測試的隨機參數
 length := 1 << 12
 inputs := make([]int, length)
 for i := 0; i < length; i++ {
  inputs[i] = rand.Int()
 }

 ls, ms := NewLockFreeStack(), NewMutexStack()

 b.ResetTimer()

 for _, s := range [...]StackInterface{ls, ms} {
  b.Run(fmt.Sprintf("%T", s), func(b *testing.B) {
   var c int64

   b.RunParallel(func(pb *testing.PB) {
    for pb.Next() {
     i := int(atomic.AddInt64(&c, 1)-1) % length
     v := inputs[i]
     if v >= 0 {
      s.Push(v)
     } else {
      s.Pop()
     }
    }
   })
  })
 }
}

測試結果比較

運行測試代碼:

$ go test -run='^$' -bench=. -count=1 -benchtime=2s

## 輸出結果如下
Benchmark_Stack/*performance.LockFreeStack-8            16553013               134.0 ns/op
Benchmark_Stack/*performance.MutexStack-8               20625786               172.5 ns/op

通過輸出結果可以看到，使用 CAS 實現的無鎖方案的性能要優於使用 Mutex 實現的有鎖方案。這裏僅僅是一個簡陋的測試實現，感興趣的讀者可以在此基礎上改進，例如提高 goroutine 的數量，棧 的入棧、出棧比例等，然後觀察無所方案帶來的性能優勢。

小結

atomic 包提供的 CAS 操作是一個相對底層的調用，在標準庫中的很多實現中，都可以看到其身影。

CompareAndSwapPointer

篇幅所限，這裏給出標準庫中 atomic.CompareAndSwapPointer 方法調用方的部分截圖。

針對性能敏感場景或者 hot path 中的鎖操作，可以使用 CAS 來進行對應的優化，此外，我們可以通過閱讀標準庫中的源代碼，來學習和理解 CAS 以及原子操作的最佳實踐。

如果從業務開發場景來感受的話，CAS 直覺上很像 樂觀鎖，而 互斥鎖 很像 悲觀鎖。

Reference

sync/atomic 設計與實現
CompareAndSwapPointer[1]
Non-blocking algorithm - 維基百科 [2]
CAS - 維基百科 [3]
An Introduction to Lock-Free Programming[4]
golang-design/lockfree[5]
Go 併發編程 (五) 深入理解 sync/atomic[6]
酷殼 - 無鎖隊列的實現 [7]
bruceshao/lockfree[8]

參考資料

[1]

CompareAndSwapPointer: https://pkg.go.dev/sync/atomic#CompareAndSwapPointer

[2]

Non-blocking algorithm - 維基百科: https://en.wikipedia.org/wiki/Non-blocking_algorithm

[3]

CAS - 維基百科: https://zh.wikipedia.org/wiki/%E6%AF%94%E8%BE%83%E5%B9%B6%E4%BA%A4%E6%8D%A2

[4]

An Introduction to Lock-Free Programming: https://preshing.com/20120612/an-introduction-to-lock-free-programming/

[5]

golang-design/lockfree: https://github.com/golang-design/lockfree

[6]

Go 併發編程 (五) 深入理解 sync/atomic: https://lailin.xyz/post/go-training-week3-atomic.html

[7]

酷殼 - 無鎖隊列的實現: https://coolshell.cn/articles/8239.html

[8]

bruceshao/lockfree: https://github.com/bruceshao/lockfree

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/W3aofshF2qydm759-dvZsA

概述

優勢