最近因為我在開發 Zoraxy 時需要設計一個可以做到 high speed concurrent READ 跟間中 write 的 map，跟另一位高雄的工程師大佬討論了一個晚上，後來我發現原來滿多人對 concurrent / racing conditions 的處理有一定程度的誤解，所以我就來簡單的解釋一下最常見的誤解 – Check for locking。

問題

假設你有兩個 process，一邊要讀取一個無法同時讀寫的 map 資料結構（例如 Go 的 map[string]struct{}），另一個要寫入新的 key 到同一個 map。由於 map 並沒辦法處理 concurrent R/W，所以你要怎樣做呢？

解決方法 1：改用專用的 concurrent map （如 Go 的 sync.Map）

這個解決方法簡單直接，我就不再詳細解釋了。然而由於我在開發 Zoraxy 的 high concurrent access 特質，使用 sync.Map 的話會做成很高的 over-head，因此我並不是很想用它（但是也不影響 sync.Map 作為沒法解決時用的最後方案的決定）

解決方法 2：mutex lock

這算是比較正規的方案之一。在讀取和寫入之前先對 map (或是 slice) 進行鎖定，然後在寫入或讀取之後解鎖。這樣就能確保同時間只有一個 process 對這個 map 有 R/W access。但是這同時也會產生另一個問題，就是在 read lock 了之後，假設有另一個 process 也想同時進行讀取的話就必須要等前面的讀完，因此這個方案對於高並發的 request handling 來說並不是太有效率。

那聽到這裡的時候很多人會直覺的覺得：那只有 write 的時候 lock 就好啦，read 的時候檢查 map 是不是被 lock，沒 lock 的話就讀取。由於檢查的時候不會 lock，因此其他需要 read 的 process 也不會被擋不是嗎？

聽上去好像沒錯喔？讓我簡單寫一個 pseudocode 例子：

function write(){
    mutex.lock()
    map.write("foo", "bar")
    mutex.unlock()
}

function read(){
    if (!mutex.isLocked()){
        //Map is not locked
        var value = map.read("foo")
        print(value)
    }else{
      //Map is locked, retry after 100ms
      delay(100)
      read()
    }
}

mutex 的部分可以是 programming language 自帶的 mutex 功能或是簡單的 boolean，效果都是一樣的。但是如果你有注意到，你不會找到 mutex.isLocked() 這個功能。

這是為甚麼呢？那是因為 OS 層基本運作原理所引起的。這裡對於本科沒修 Computer Architecture （計算機架構）的工程師可能比較難理解。簡單來說就是，CPU 上就只有 n 個核心，但是你的作業系統上面有很多東西在執行，所以 OS 會對上面執行的工作（process）進行快速切換。每次切換的時候因為速度很快，所以會讓你有一種它們在並行處理的感覺。而實質上，每個 process switching 都會有一個 overhead，而這個 overhead 就是為甚麼 mutex lock 沒辦法被用於檢查的原因。

關於 CPU scheduling 跟 scheduling 演算法的詳情可以看這邊

所以為甚麼 Mutex 不能檢查是不是被其他 process 鎖上？

當你去檢查一個 mutex 是否被鎖的時候，檢查當下可能沒被鎖，但是檢查完到執行下一個邏輯的時候可能已經被另一個 process 鎖上了

以 compile language 為例，你的 if then else case 在 assembly 下其實是一句 conditional jump 指令。很多時候，就如上圖 round robin 所顯示的，這句 byte code 會繼續多執行幾句 byte code 才會換另一個 process 的 stack pointer（即是切換到另一個 process），但是在高並發環境下， CPU 有很大機會在執行完 if-then-else check 是不是 mutex lock 之後就會切換到下一個 process。而如果剛好那個 process 把它 lock 了，你先前檢查的 lock state 就不適用了，繼而導致 runtime panic。

所以用 check for mutex lock 這種 coding logic 在 production 環境下用是非常危險的。因為這種 code 寫出來後，很多時候在 development 環境 / low load 環境下是能用而且也能通過 compiler，可是到了 production 的環境 / high load 環境下炸掉。如果你對 concurrent access 概念不熟的話你就只能花幾天從 stack trace 裡面慢慢把原因翻出來了。

後來的解決方法

後來我改用 pointer 的方式，在需要寫入的時候先對原先的 map 進行 deep copy，然後把改好的新 map 以改 pointer 的方式寫入到原先的 struct 裡面。另外在 READ 邏輯裡面，我也會先把 pointer 指向的 map 先寫到一個新的 local scope pointer variable 裡，然後在後面的 READ 邏輯（如 for loop）都使用一開始複製下來的 pointer。這樣即使是在 READ 的時候被寫入，READ 的邏輯也會保持使用舊的 map 。待 READ 邏輯完成之後，舊 map 就會自然被 GC （Garbage Collection）從 memory 處理掉。

就這樣，我們就做好一個能 concurrent R/W 的（類似） map 的方案啦~