9.1. 競爭條件

在一個線性（就是說只有一個goroutine的）的程序中，程序的執行順序只由程序的邏輯來決定。例如，我們有一段語句序列，第一個在第二個之前（廢話），以此類推。在有兩個或更多goroutine的程序中，每一個goroutine內的語句也是按照既定的順序去執行的，但是一般情況下我們沒法去知道分別位於兩個goroutine的事件x和y的執行順序，x是在y之前還是之後還是同時發生是沒法判斷的。當我們沒有辦法自信地確認一個事件是在另一個事件的前面或者後面發生的話，就說明x和y這兩個事件是併發的。

考慮一下，一個函數在線性程序中可以正確地工作。如果在併發的情況下，這個函數依然可以正確地工作的話，那麼我們就說這個函數是併發安全的，併發安全的函數不需要額外的同步工作。我們可以把這個概念概括為一個特定類型的一些方法和操作函數，對於某個類型來說，如果其所有可訪問的方法和操作都是併發安全的話，那麼該類型便是併發安全的。

在一個程序中有非併發安全的類型的情況下，我們依然可以使這個程序併發安全。確實，併發安全的類型是例外，而不是規則，所以只有當文檔中明確地說明了其是併發安全的情況下，你才可以併發地去訪問它。我們會避免併發訪問大多數的類型，無論是將變量侷限在單一的一個goroutine內，還是用互斥條件維持更高級別的不變性，都是為了這個目的。我們會在本章中說明這些術語。

相反，包級別的導出函數一般情況下都是併發安全的。由於package級的變量沒法被限制在單一的gorouine，所以修改這些變量“必須”使用互斥條件。

一個函數在併發調用時沒法工作的原因太多了，比如死鎖（deadlock）、活鎖（livelock）和餓死（resource starvation）。我們沒有空去討論所有的問題，這裡我們只聚焦在競爭條件上。

競爭條件指的是程序在多個goroutine交叉執行操作時，沒有給出正確的結果。競爭條件是很惡劣的一種場景，因為這種問題會一直潛伏在你的程序裡，然後在非常少見的時候蹦出來，或許只是會在很大的負載時才會發生，又或許是會在使用了某一個編譯器、某一種平臺或者某一種架構的時候才會出現。這些使得競爭條件帶來的問題非常難以復現而且難以分析診斷。

傳統上經常用經濟損失來為競爭條件做比喻，所以我們來看一個簡單的銀行賬戶程序。

// Package bank implements a bank with only one account.
package bank
var balance int
func Deposit(amount int) { balance = balance + amount }
func Balance() int { return balance }

(當然我們也可以把Deposit存款函數寫成balance += amount，這種形式也是等價的，不過長一些的形式解釋起來更方便一些。)

對於這個簡單的程序而言，我們一眼就能看出，以任意順序調用函數Deposit和Balance都會得到正確的結果。也就是說，Balance函數會給出之前的所有存入的額度之和。然而，當我們併發地而不是順序地調用這些函數的話，Balance就再也沒辦法保證結果正確了。考慮一下下面的兩個goroutine，其代表了一個銀行聯合賬戶的兩筆交易：

// Alice:
go func() {
    bank.Deposit(200)                // A1
    fmt.Println("=", bank.Balance()) // A2
}()

// Bob:
go bank.Deposit(100)                 // B

Alice存了$200，然後檢查她的餘額，同時Bob存了$100。因為A1和A2是和B併發執行的，我們沒法預測他們發生的先後順序。直觀地來看的話，我們會認為其執行順序只有三種可能性：“Alice先”，“Bob先”以及“Alice/Bob/Alice”交錯執行。下面的表格會展示經過每一步驟後balance變量的值。引號裡的字符串表示餘額單。

Alice first        Bob first        Alice/Bob/Alice
          0                0                      0
  A1    200        B     100             A1     200
  A2 "= 200"       A1    300             B      300
  B     300        A2 "= 300"            A2  "= 300"

所有情況下最終的餘額都是$300。唯一的變數是Alice的餘額單是否包含了Bob交易，不過無論怎麼著客戶都不會在意。

但是事實是上面的直覺推斷是錯誤的。第四種可能的結果是事實存在的，這種情況下Bob的存款會在Alice存款操作中間，在餘額被讀到（balance + amount）之後，在餘額被更新之前（balance = ...），這樣會導致Bob的交易丟失。而這是因為Alice的存款操作A1實際上是兩個操作的一個序列，讀取然後寫；可以稱之為A1r和A1w。下面是交叉時產生的問題：

Data race
0
A1r      0     ... = balance + amount
B      100
A1w    200     balance = ...
A2  "= 200"

在A1r之後，balance + amount會被計算為200，所以這是A1w會寫入的值，並不受其它存款操作的干預。最終的餘額是$200。銀行的賬戶上的資產比Bob實際的資產多了$100。（譯註：因為丟失了Bob的存款操作，所以其實是說Bob的錢丟了。）

這個程序包含了一個特定的競爭條件，叫作數據競爭。無論任何時候，只要有兩個goroutine併發訪問同一變量，且至少其中的一個是寫操作的時候就會發生數據競爭。

如果數據競爭的對象是一個比一個機器字（譯註：32位機器上一個字=4個字節）更大的類型時，事情就變得更麻煩了，比如interface，string或者slice類型都是如此。下面的代碼會併發地更新兩個不同長度的slice：

var x []int
go func() { x = make([]int, 10) }()
go func() { x = make([]int, 1000000) }()
x[999999] = 1 // NOTE: undefined behavior; memory corruption possible!

最後一個語句中的x的值是未定義的；其可能是nil，或者也可能是一個長度為10的slice，也可能是一個長度為1,000,000的slice。但是回憶一下slice的三個組成部分：指針（pointer）、長度（length）和容量（capacity）。如果指針是從第一個make調用來，而長度從第二個make來，x就變成了一個混合體，一個自稱長度為1,000,000但實際上內部只有10個元素的slice。這樣導致的結果是存儲999,999元素的位置會碰撞一個遙遠的內存位置，這種情況下難以對值進行預測，而且debug也會變成噩夢。這種語義雷區被稱為未定義行為，對C程序員來說應該很熟悉；幸運的是在Go語言裡造成的麻煩要比C裡小得多。

儘管併發程序的概念讓我們知道併發並不是簡單的語句交叉執行。我們將會在9.4節中看到，數據競爭可能會有奇怪的結果。許多程序員，甚至一些非常聰明的人也還是會偶爾提出一些理由來允許數據競爭，比如：“互斥條件代價太高”，“這個邏輯只是用來做logging”，“我不介意丟失一些消息”等等。因為在他們的編譯器或者平臺上很少遇到問題，可能給了他們錯誤的信心。一個好的經驗法則是根本就沒有什麼所謂的良性數據競爭。所以我們一定要避免數據競爭，那麼在我們的程序中要如何做到呢？

我們來重複一下數據競爭的定義，因為實在太重要了：數據競爭會在兩個以上的goroutine併發訪問相同的變量且至少其中一個為寫操作時發生。根據上述定義，有三種方式可以避免數據競爭：

第一種方法是不要去寫變量。考慮一下下面的map，會被“懶”填充，也就是說在每個key被第一次請求到的時候才會去填值。如果Icon是被順序調用的話，這個程序會工作很正常，但如果Icon被併發調用，那麼對於這個map來說就會存在數據競爭。

var icons = make(map[string]image.Image)
func loadIcon(name string) image.Image

// NOTE: not concurrency-safe!
func Icon(name string) image.Image {
    icon, ok := icons[name]
    if !ok {
        icon = loadIcon(name)
        icons[name] = icon
    }
    return icon
}

反之，如果我們在創建goroutine之前的初始化階段，就初始化了map中的所有條目並且再也不去修改它們，那麼任意數量的goroutine併發訪問Icon都是安全的，因為每一個goroutine都只是去讀取而已。

var icons = map[string]image.Image{
    "spades.png":   loadIcon("spades.png"),
    "hearts.png":   loadIcon("hearts.png"),
    "diamonds.png": loadIcon("diamonds.png"),
    "clubs.png":    loadIcon("clubs.png"),
}

// Concurrency-safe.
func Icon(name string) image.Image { return icons[name] }

上面的例子裡icons變量在包初始化階段就已經被賦值了，包的初始化是在程序main函數開始執行之前就完成了的。只要初始化完成了，icons就再也不會被修改。數據結構如果從不被修改或是不變量則是併發安全的，無需進行同步。不過顯然，如果update操作是必要的，我們就沒法用這種方法，比如說銀行賬戶。

第二種避免數據競爭的方法是，避免從多個goroutine訪問變量。這也是前一章中大多數程序所採用的方法。例如前面的併發web爬蟲（§8.6）的main goroutine是唯一一個能夠訪問seen map的goroutine，而聊天服務器（§8.10）中的broadcaster goroutine是唯一一個能夠訪問clients map的goroutine。這些變量都被限定在了一個單獨的goroutine中。

由於其它的goroutine不能夠直接訪問變量，它們只能使用一個channel來發送請求給指定的goroutine來查詢更新變量。這也就是Go的口頭禪“不要使用共享數據來通信；使用通信來共享數據”。一個提供對一個指定的變量通過channel來請求的goroutine叫做這個變量的monitor（監控）goroutine。例如broadcaster goroutine會監控clients map的全部訪問。

下面是一個重寫了的銀行的例子，這個例子中balance變量被限制在了monitor goroutine中，名為teller：

gopl.io/ch9/bank1

// Package bank provides a concurrency-safe bank with one account.
package bank

var deposits = make(chan int) // send amount to deposit
var balances = make(chan int) // receive balance

func Deposit(amount int) { deposits <- amount }
func Balance() int       { return <-balances }

func teller() {
    var balance int // balance is confined to teller goroutine
    for {
        select {
        case amount := <-deposits:
            balance += amount
        case balances <- balance:
        }
    }
}

func init() {
    go teller() // start the monitor goroutine
}

即使當一個變量無法在其整個生命週期內被綁定到一個獨立的goroutine，綁定依然是併發問題的一個解決方案。例如在一條流水線上的goroutine之間共享變量是很普遍的行為，在這兩者間會通過channel來傳輸地址信息。如果流水線的每一個階段都能夠避免在將變量傳送到下一階段後再去訪問它，那麼對這個變量的所有訪問就是線性的。其效果是變量會被綁定到流水線的一個階段，傳送完之後被綁定到下一個，以此類推。這種規則有時被稱為串行綁定。

下面的例子中，Cakes會被嚴格地順序訪問，先是baker gorouine，然後是icer gorouine：

type Cake struct{ state string }

func baker(cooked chan<- *Cake) {
    for {
        cake := new(Cake)
        cake.state = "cooked"
        cooked <- cake // baker never touches this cake again
    }
}

func icer(iced chan<- *Cake, cooked <-chan *Cake) {
    for cake := range cooked {
        cake.state = "iced"
        iced <- cake // icer never touches this cake again
    }
}

第三種避免數據競爭的方法是允許很多goroutine去訪問變量，但是在同一個時刻最多隻有一個goroutine在訪問。這種方式被稱為“互斥”，在下一節來討論這個主題。

練習 9.1： 給gopl.io/ch9/bank1程序添加一個Withdraw(amount int)取款函數。其返回結果應該要表明事務是成功了還是因為沒有足夠資金失敗了。這條消息會被髮送給monitor的goroutine，且消息需要包含取款的額度和一個新的channel，這個新channel會被monitor goroutine來把boolean結果發回給Withdraw。