前言

CPU （Central Processing Unit）作為整個馮·諾依曼架構的控制與運算中心，終其一生都在執行沒有邊界的指令，用無差別的計算支撐起智能時代“算力取之不盡用之不竭”的夢。
但這樣的計算并不是100%有意義的：糟糕的算法設計造成了大量的重復計算；忽視局部性與連續性的代碼用cache miss粗暴地蹂躪著多級緩存，甚至觸發頻繁的cpu stall；低效的調度和密集的資源競爭拉低了程序的整體運行效率與吞吐...etc
因此在CS的不同領域，不管是kernel，語言運行時，網絡，存儲...都結合了各自的場景，催生出了無數的策略以最小化“等待”的計算量，讓寶貴的算力盡可能服務于真正有價值的指令。本文羅列的的例子也許并不是那么Apple to apple，但它們都從不同的視角給我啟發，且有一定的共通。

出于篇幅考慮文章內容可能不盡詳細，默認讀者對操作系統，網絡，concurrency control等前置知識有一定程度的了解。

Spin Lock

在多核處理器的并發編程中，線程/進程（后統一用線程）間的同步原語是永遠都繞不開的，spin lock可以說是其中最簡單直接的一種實現。說白了spin lock只是一個忙等待的循環，看似低效，但在kernel和各種高性能庫中卻應用廣泛。
歪？并發的資源競爭中，保護臨界區的方法無非兩種：1. 搶占并持續獲得線程所有權；2. 依賴內核的線程調度機制。但內核調度的隱性開銷是content switching，在競爭密集時這樣的開銷會被放大，代價十分可觀，但如果臨界區長度短小可控，spin的次數也可控，那么顯然spin lock會成為一個更優的選擇。

// 一個最簡單的spin lock實現
std::atomic<bool> lock_{false};
void lock() {
    while(true) {
        while (lock_.load());
        if (!lock_.exchange(true)) break;
    }
}
void unlock() {
    lock_.store(false);
}

但聰明的CPU與編譯器并不會直譯代碼，為了指令最大程度的并行執行通常會對代碼進行一定程度的打亂和重排序，你親手敲下的代碼的行為可能會與預期有出入，而約束指令亂序行為依賴于不同等級的memory-order內存序模型。在主流的x86平臺中，默認的memory order約束實現為SC（Sequential Consistency），是一種較強的內存序保證。Wiki上的官方定義為：

...the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program...

簡而言之，還是會有一定的亂序和重排，但是在程序員的可見視角，最終的執行順序與代碼定義的提交順序是一致的。上述實現中使用了c++標準庫封裝的atomic接口，默認的memory order同樣也是SC。C++提供了6種標準的memory order實現，我們可以在保證臨界區安全性的前提下，通過放松內存序來進一步提升spin lock的性能。

保證臨界區安全性前提是：臨界區內的代碼必須嚴格遵循sequential consistency。
對照6種內存序列，我們把目光聚焦在通常成對使用的acquire-release模型上：acquire-release模型能夠保證原子變量一端store，另一端永遠能夠load到最新的值，其隱含的意思是：release之前的store()操作，對其他線程acquire之后的任何load()操作都可見！同時，acquire前的代碼可以往后亂序（但acquire后的代碼不允許往前亂序），release后的代碼可以往前亂序（但release前的代碼不允許往后亂序）！應用到spin lock中，意味著aquire-release保護的臨界區可以在多個線程之間保證SC-level的可見性。

在臨界區安全的前提下擴大了亂序執行的區間，通過細粒度的memory order配置進一步提升了并發度，縮短spin等待時間。

// acquire-release模型的spin lock
std::atomic<bool> lock_{false};
void lock() {
    while(true) {
        while (lock_.load(std::memory_order_relaxed));
        if (!lock_.exchange(true, std::memory_order_acquire)) break;
    }
}
void unlock() {
    lock_.store(false, std::memory_order_release);
}

x86平臺中，為了進一步壓榨spin lock的性能，實現了一種平臺獨占的pause指令：不同于thread::yield()，pause并沒有放棄線程使用權，而是告訴processor這是一個spin-lock，可以把一些指令優化暫時關閉，稍稍減慢線程的執行速度，帶來的收益是：減少了鎖變量的競爭，免去了潛在的memory order檢測，以及保護了當前的cache line不被其他waiter清空，優化的效果顯著。通常的使用姿勢如下：

// acquire-release模型+pause指令的spin lock
#define PAUSE() asm("pausen")
std::atomic<bool> lock_{false};
void lock() {
    while(true) {
        while (lock_.load(std::memory_order_relaxed)) {
            PAUSE();
        }
        if (!lock_.exchange(true, std::memory_order_acquire)) break;
    }
}
void unlock() {
    lock_.store(false, std::memory_order_release);
}

作為高頻使用的利器，spin lock的優化并未止步于此，諸如以下。

MCS spin lock

MCS spin lock是學術界提出的一種spin lock改進版本，已被最新的linux kernel采納，目的是減少lock在不同cpu core之間的遷移，每個core都持有一個本地標志變量，每個core上的線程只在本地變量自旋，通過一個全局的鏈表將這些waiters串聯起來。申請MCS spin lock時會得到前置鎖擁有者的鎖結構體指針（其中包含各自的waiting本地標識變量），并把next指針指向自己，在原子操作的保證下獲得了一個FIFO的申請順序。當一個線程執行完臨界區的代碼后，判斷next指針域是否還有別的waiter，如果有的話就按的順序把它的waiting置0，交出鎖的使用權。以這種巧妙的方法實現了鎖的傳遞，大幅減少鎖的競爭和跨cpu core傳遞。

NUMA Aware spin lock

當前主流服務器支持的NUMA（Non-Uniform Memory Access）架構下，每個cpu socket都被分配了自己的內存空間，極大降低了local socket的內存訪問延遲，如果需要訪問的數據在其他cpu socket（NUMA node），則需要依賴特殊的remote access協議。在這樣的場景下，可以引入分布式一致性機制來減少cache line在不同cpu socket之間的遷移，詳見參考資料。
（底層的世界就是分布式系統的微觀表現！）

Mutex per core

當線程數>cpu核數時，在spin和CFS調度的共同作用下，大量線程持續不斷在爭奪鎖資源，這時為每個cpu core引入一個mutex，使得每個core上的某個時刻只允許有一個線程參與競爭，大幅減少全局的鎖競爭程度。

Golang Runtime

Golang作為云計算時代的"C"語言（見仁見智了），也是筆者目前的主力語言，其重要特色之一是其內置的用戶態協程機制——goroutine，在runtime的優秀設計與調度下，goroutine真正實現了高效運行而無需過多關心棧空間、上下文切換、并發上限等問題，just run as you go！
Golang遵循M-P-G的并發模型，將用戶態的最小執行單元goroutine映射到內核態的OS線程中，呈M:N的映射關系：

M：machine，對應OS線程的概念，OS線程是CPU的最小調度單元，由內核調度模塊負責調度。一般Runtime會限制同時運行M（阻塞的M另算）的數量與CPU核數（邏輯核）相同，這樣可以減少OS級別的上下文切換，大部分都切換都在用戶態完成。
P：Process，虛擬處理器的概念，一般一個邏輯核分配一個P，負責本邏輯核上的goroutine調度，解決全局共享隊列的鎖競爭問題。M與P互相關聯，M不能獨立于P存在。
G：Goroutine，用戶態協程，執行用戶代碼的實體，維護了堆棧與狀態相關的信息，并分配了很小的棧空間（通常2KB）。

M-P-G模型

Runtime的工作，就是基于以上的模型定義讓每一個Machine充分負載，無間斷地執行用戶代碼，做一個沒有感情的指令執行機。順利的話，runtime的工作流如下：

P從其維護的本地可運行隊列（LRQ）里取出G來執行。為保證公平，也有一定幾率（1/61）會從全局可運行隊列中（GRQ）取G。
P的LRQ滿了（運行隊列的本質是一個ring buffer），就把新到達的G放入GRQ，把負載轉移給其他相對空閑的P。
P的LRQ空，P就嘗試去GRQ中偷任務，把其中的一半G轉移到自己的LRQ中。
如果LRQ與GRQ都為空，則P從隨機選擇一個其他P，從其LRQ里偷一半的G來執行。
還有一個單獨的daemon goroutine，負責監控其他goroutine的執行時間，把運行時長>10ms的goroutine調度到GRQ中，讓短而小的goroutine優先執行并結束。

goroutine主要狀態遷移

但以上工作流，還不足以做到“無間斷地執行用戶代碼”。Goroutine和POSIX線程一樣，主要在3種狀態之間轉移：Waiting/Runnable/Running，注意LRQ和GRQ存儲的是狀態為可運行（Runnable）的G，P拿到G后，將它的狀態置為Running并分配給M來真正執行代碼。但當陷入系統調用（syscall）或同步/異步等待IO時，goroutine會阻塞并進入Waiting狀態，這時runtime會有其他機制來保證計算資源被充分利用：

當陷入系統調用時，或同步等待IO時，當前M被阻塞，M與P暫時解綁但M-G保持關聯關系，P會創建一個新的M，即向OS申請一個新的線程，把新到達的G繼續分配給新M執行。等阻塞解除，原先的M會被保存起來靜待后續復用。
當陷入異步等待IO，如網絡IO時，阻塞的G會被一個成?.NETwork poller的結構接手，而M則繼續服務別的G，異步IO相關的文件描述符（fd）就緒后，阻塞的G重新進入LRQ。在Linux平臺，network poller實際上是對epoll的封裝，注冊阻塞的fd并監聽到達的事件，就緒的fd所在的G就會被重新調度，回到原來的LRQ等待被執行。

至此，基本實現了golang runtime的高效調度模型，實際上用戶態的協程切換除了上下文切換的代價小，還有其他諸如CPU緩存友好等隱性收益。而很多內置的語言特性及標準庫實現都基于這個模型，：

Mutex、RWMutex、WaitGroup為代表的線程間同步原語實現，都通過觸發調度來協調執行順序。
Timer通過觸發調度來實現休眠與喚醒。
channel通過配合調度來實現安全且優雅的線程間通信和select多路復用。
...

淺析channel

把channel單獨拎出來說說，它是golang最為推崇的并發通信哲學的實現:

Don't communicate by sharing memory; share memory by communicating.

扒一下channel的定義：

// channel runtime struct
type hchan struct {
    // 過濾部分重點成員變量
    qcount   uint
    dataqsiz uint
    buf      unsafe.Pointer
    sendx    uint  
    recvx    uint
    recvq    waitq
    sendq    waitq
    // ...
}

// waitq代表channel收/發的兩個隊列
// sudog是對goroutine結構的封裝，channel持有相關等待goroutine的引用，
// sudog中也同樣持有對channel結構的指針
type waitq struct {
    first *sudog
    last  *sudog
}

可以看到實現跨線程消息收發，主要依賴了channel結構中的ring buffer和用waitq表示的收/發兩個goroutine隊列。
channel也分為unbuffered chan和buffered chan，通過初始化時是否制定了capacity來區分，unbuffered chan是標準的同步阻塞IO模型，而buffered chan則給予了一定限度的異步非阻塞空間。

goroutine channel

下面從一些關鍵的代碼片段來看看這兩種chan在runtime的實現中具體有什么區別：

func chansend(c *hchan, ep unsafe.Pointer, block bool, callerpc uintptr) bool {

    // ...

    // 已有chan在別的goroutine中等待接受，可以直接發送并返回
    if sg := c.recvq.dequeue(); sg != nil {
        // Found a waiting receiver. We pass the value we want to send
        // directly to the receiver, bypassing the channel buffer (if any).
        send(c, sg, ep, func() { unlock(&c.lock) }, 3)
        return true
    }

    // ...

    // 當前為buffered chan，且buffer還有富余，直接將變量拷貝到buffer，
    // 更新相關標記位后直接可以返回
    if c.qcount < c.dataqsiz {
        // Space is available in the channel buffer. Enqueue the element to send.
        qp := chanbuf(c, c.sendx)
        typedmemmove(c.elemtype, qp, ep)
        c.sendx++
        if c.sendx == c.dataqsiz {
            c.sendx = 0
        }
        c.qcount++
        unlock(&c.lock)
        return true
    }

    // ...

    // 最后剩下阻塞發送的邏輯，既不是buffered chan且其他goroutine中暫無
    // 就緒的接收方，或者buffered chan已滿，都會執行阻塞發送，以下代碼仍
    // 有所精簡
    if !block {
        unlock(&c.lock)
        return false
    }

    // 主要的動作是獲取當前goroutine，和channel一起與sudog綁定并設置到
    // channel的發送隊列中，同時通過goparkunlock函數讓出當前的goroutine
    // 執行權，等待接收方的喚醒

    // Block on the channel. Some receiver will complete our operation for us.
    gp := getg()
    mysg := acquireSudog()
    // No stack splits between assigning elem and enqueuing mysg
    // on gp.waiting where copystack can find it.
    mysg.elem = ep
    mysg.waitlink = nil
    mysg.g = gp
    mysg.isSelect = false
    mysg.c = c
    gp.waiting = mysg
    gp.param = nil
    c.sendq.enqueue(mysg)
    goparkunlock(&c.lock, waitReasonChanSend, traceEvGoBlockSend, 3)

    // ...
    // 被接收方喚醒后，該goroutine重新獲得執行權，繼續掃尾工作
    mysg.c = nil
    releaseSudog(mysg)
    return true
}

以上是channel發送端的主要邏輯，在一段邏輯中區分開了3種case，比較有意思的是函數并不是一次性執行完的，發送前的準備工作就緒后即讓出當前的執行權，等待接收方喚醒后進行掃尾工作，函數正常退出。

func chanrecv(c *hchan, ep unsafe.Pointer, block bool) (selected, received bool) {

    // 從nil chan中試圖接收，直接讓出執行權
    if c == nil {
        if !block {
            return
        }
        gopark(nil, nil, waitReasonChanReceiveNilChan, traceEvGoStop, 2)
        throw("unreachable")
    }

    // ...

    // chan已被關閉，且buffer中沒有殘留元素，清除相關堆棧信息后返回
    if c.closed != 0 && c.qcount == 0 {
        unlock(&c.lock)
        if ep != nil {
            typedmemclr(c.elemtype, ep)
        }
        return true, false
    }

    // 對于同步阻塞的chan發送方，執行recv，接收并拷貝對應的變量值，然后通過goready
    // 函數喚醒發送方的goroutine
    if sg := c.sendq.dequeue(); sg != nil {
        // Found a waiting sender. If buffer is size 0, receive value
        // directly from sender. Otherwise, receive from head of queue
        // and add sender's value to the tail of the queue (both map to
        // the same buffer slot because the queue is full).
        recv(c, sg, ep, func() { unlock(&c.lock) }, 3)
        return true, true
    }

    // 對于buffered chan，從buffer的對應索引處取出元素并消費后直接返回，這里不需要
    // 調用goready，因為對于成功發送的發送方本就是一個異步操作，無需喚醒
    if c.qcount > 0 {
        // Receive directly from queue
        qp := chanbuf(c, c.recvx)
        if ep != nil {
            typedmemmove(c.elemtype, ep, qp)
        }
        typedmemclr(c.elemtype, qp)
        c.recvx++
        if c.recvx == c.dataqsiz {
            c.recvx = 0
        }
        c.qcount--
        unlock(&c.lock)
        return true, true
    }

    // 最后落到了和sendchan類似的邏輯，接收方等待接收但當前沒有可用的發送方，于是陷入
    // 阻塞等待，獲取當前goroutine，連同channel一起與sudog綁定，設置到channel的
    // 接受隊列中，并讓出執行權
    if !block {
        unlock(&c.lock)
        return false, false
    }

    // no sender available: block on this channel.
    gp := getg()
    mysg := acquireSudog()
    // No stack splits between assigning elem and enqueuing mysg
    // on gp.waiting where copystack can find it.
    mysg.elem = ep
    mysg.waitlink = nil
    gp.waiting = mysg
    mysg.g = gp
    mysg.isSelect = false
    mysg.c = c
    gp.param = nil
    c.recvq.enqueue(mysg)
    goparkunlock(&c.lock, waitReasonChanReceive, traceEvGoBlockRecv, 3)

    // ...

    // 被發送方喚醒后，該goroutine重新獲得執行權，繼續掃尾工作
    closed := gp.param == nil
    gp.param = nil
    mysg.c = nil
    releaseSudog(mysg)
    return true, !closed
}

以上是channel接收端的主要邏輯，細分了5個case，大致的工作流與發送端類似。已經做了精簡但兩段代碼看著還是比較長，不過好在邏輯清晰，應該很容易能看懂。
為了在channel與goroutine之間建立聯系，runtime封裝了sudog結構，引用了當前阻塞的channel與goroutine，并追加到發送/接收隊列中，經過調度獲得執行權后又可以解引用來喚醒對端執行數據的收與發，讀與寫，巧妙地實現了并發通信機制。限于篇幅，還是有很多細節沒有鋪開，感興趣的讀者可以從參考資料中獲取更多信息。

值得一提的是，經過不斷的版本迭代，go runtime的STW（Stop The World）時間已被控制的十分優秀，這也是"優化等待"的一個重要主題。

Token Bucket

網絡也是計算機科學中的宏大主題，是所謂“萬物互聯”的根基，而網絡的可用性基本決定了一個復雜分布式系統可用性的下限。出于全局可用性的考慮，誕生了各種各樣的控制算法，如我們非常熟悉的TCP/IP協議中的基于滑動窗口的的流量控制算法，基于慢開始、快速重傳、快速恢復等機制的擁塞控制算法。其中在流量整形（Traffic Shaping）與限流（Rate Limiting）中，Token Bucket算法被廣泛應用。
例如：在kubernetes非常普遍的controller pattern中，通常會持有一個RateLimitingQueue將其監聽到的events先入隊，然后由多個goroutine去消費events，而events出隊的速率就是由Token Bucket算法保證的。除此之外，在多租戶網絡限流，路由限速，全局流控等方面，TokenBucket都有妙用，通過局部的限流整形措施，來達到全局的更優。
樸素的TokenBucket算法簡單直觀：

token是當前可用的網絡數據包抽象，一般一個token代表一個bit或一次api調用。
bucket是容納token的容器，有一定的容量上限。網絡數據傳輸發生時需要向bucket申請消費對應數量的token，如果token數量不足則需要丟棄數據包或等待新token到達。以此來限制使用該bucket的數據流動速度。
每隔一定的interval會有新的token補充，補充間隔一般為1/bps或1/qps。
允許有一定限度的突發流量。

Token Bucket

當然在具體的實現上，間隔interval補充token并不意味著真的要有一個工作線程去定時觸發，可以記錄相關的tick offset（而不是直接時間戳，tick才是時間維度的最小單位），把補充token的動作延遲到消費token，通過對比時間差去動態的調整token數量。

bucket的大小依據一般是突發流量最長可容忍時長*每一幀數據包的平均大小，超過限流閾值的流量就會因為token不足而觸發管制措施：丟包或阻塞等待，至于阻塞等待的時長則會根據缺少的token數量換算出來，并重置bucket。
但網絡是個大黑盒，你不會知道下一秒到達的數據包payload有多大，也無法100%準確預測流量的峰值速率，這時候如果只是粗暴地丟包或者等待，對穩定性或性能都存在潛在的風險。于是在樸素TokenBucket算法的基礎上，RFC擴展了對于數據包處理的行為：單速率三色標記算法（single rate threecolor marker，srTCM）和雙速率三色標記算法（two rate threecolor marker，trTCM）。兩者都將數據包分為紅/黃/綠三種顏色等級，不同顏色對應不同的處理行為。

單速率三色標記算法

srTCM引入了一個新bucket：Excess Bucket，簡稱E桶，原先正常使用的bucket為Committed Bucket，簡稱C桶，雙桶共同協作。單速率指的是這兩個桶的信息速率相同，即有相同的interval去補充token，每次補充的數量也相同，補充的順序為先C后E。但兩桶的容量可以不相同，E桶的大小即允許的最大超額大小，稱為Te，C桶大小為Tc，Te > Tc。
正常情況下并不會用到E桶，只有C桶中未消費完的token，以及C桶滿了以后新到達的token會被移交入E桶作備用。當有突發的大尺寸數據包到達，且C桶內的token不足時，就會消費E桶內的token而不會觸發限流。
若TokenBucket用于發送端的限流，三色標記就派上用場了，紅色代表丟棄數據包，黃色代表阻塞等待，綠色代表合法。同時還有色盲（color-blind）與感色（color-aware）兩種工作模式：

色盲模式：數據包沒有預先著色，根據數據包的尺寸標記顏色：size < Tc為綠色，Tc < size < Te為黃色，size > Te為紅色。
感色模式：數據包已預先根據IEEE標準著色，與“色盲模式”中的條件一起共同確定數據包的標記，例如size < Tc或已被標記綠色則被認為是綠色，后同。

單速率三色標記算法更關注處理突發的數據包尺寸。

雙速率三色標記算法

trTCM與srTCM的區別主要就在于雙桶的信息速率可以不同，即interval與每次補充的token量都可以不同。雙速率三色標記算法更注重突發的數據速率。
在trTCM中，第二個桶被稱為P（Peak）桶，與srTCM不同，兩個桶的token是互相隔離的，C桶中的token并不會轉移到P桶。另一個重要不同是每一次都會先比較是否為突發速率的流量，再判斷是否為正常速率，因為數據速率并不是對單個數據包的測量。trTCM同樣有色盲與感色模式：

色盲模式：速率超出P桶限制時（Tp/interval），超出Tp+Tc部分的包會被標記為紅色，直接丟棄，未超過Tp+Tc的數據包分別從P桶和C桶消費token，消費P桶部分的標記為黃色，C桶的標記為綠色。速率超出C桶限制（Tc/interval）但未超出P桶限制，則會有黃+綠兩種組合的數據包，否則未超出C桶限制，都為綠色。
感色模式：同樣的，共同考慮實際速率與數據包著色，來確定顏色標記。

關于TokenBucket的實現，推薦參考juju/ratelimit和folly/tokenbucket。