適應性並行處理¶

這份心得全部歸功於這部影片和這篇部落格文章。因為這份心得將會於 104 TOL 中發表，所以將會以簡報的樣子進行撰寫。

註1：相關 PPT 只能被 104 的員工查看，但本篇以涵蓋全部的內容。

註2：相關程式碼實作在 GitHub 上。

前言¶

在今日（2022年），許多人對於適應性並行處理（Adaptive Concurrency）是陌生的，但實際上它自 1988 年便已存在於我們很常使用的協定 TCP 當中。他在這之中扮演了什麼角色，又為什麼會重新浮出水面來讓我們重新思考它的價值呢？

在開始前，我想先以銀行作為思考範例，其實這並不是偶然，在後面提到的利特爾法則中就會讓大家知道為什麼要以銀行作為範例。

銀行的並行處理¶

你現在經營著一家銀行，你雇用了一些行員，而你身為熱情的經營者，會站在顧客和行員中間，幫忙接待、套近乎和引導顧客至指定行員。在實際營業前，我們對於分行內的氣氛想像可能如下：

快樂的銀行生活持續不長，事實上在開張後不久你就面臨了一些狀況：

• 冷氣壞掉，原本十分鐘可以處理一位顧客，因為煩悶所以現在十五分鐘才能完成
• 數抄機壞掉，比冷氣壞掉更糟，現在三十分鐘才能處理一位顧客
• 行員臨時請假，銀行現在完全沒辦法處理顧客的業務了
• 某政策的執行，導致業務量大增，顧客數量多到你和行員都沒辦法負荷
• 顧客因為等太久了，把你抓出來臭罵一頓

當這些問題沒有解決，或著連續數天發生這種狀況，你的銀行就會開始受到顧客的批評。而這種名譽傷害通常需要數倍的時間和金錢來解決。

超級保鑣，萊特利米特¶

為了解決這問題，你請了一位超級保鑣，萊特利米特（Rate Limit）。他會透過限制單一顧客的使用總量來減少那些因為特定人士導致的服務品質下降。換句話說，如果有人一天來 30 次，每次都是需要處理 30 分鐘的業務，那你很可能會請萊特利米特出來，並限制該顧客的次數，避免其他顧客不能正常處理他們的業務。

但是回想一下我們最一開始的問題，冷氣壞掉、行員請假、業務量合理地大增，這些好像都不是一個保鑣能夠解決的。事實上也沒有任何一家銀行會用這種方式來處理顧客等太久的問題。你想像一下，每次進去銀行處理業務，就有個保鑣在旁邊計時檢查，當超過一秒鐘後就把你強制踢出，這種可能讓正常操作的顧客變得惱火的行為，應該是在可預見的未來中都不會出現的政策。

聽起來很可笑，但這卻實作在我們很多的網路服務中。

API Management¶

現在我們把場景回到網路服務中，這裡有個很好的例子，API Management（APIM）。它的定位是承接各個後台服務的中繼站，舉例來說前端使用者在他的電腦按下表格送出時，很可能就會先經過 APIM 再到處理這個表格商務邏輯的服務節點中。

這個 APIM 不只是會把流量導到指定的服務中，他也需要幫我們檢查使用者身份、惡意請求和限制流量。這個角色有沒有聽起來像是在銀行例子中的你？你的工作就是檢查顧客身份、確認是否惡意、確認初步需求後再導流到指定行員。接下來我們看看 APIM 即將面臨的一些挑戰：

• 某個服務的請求突然增加，導致上游服務和 APIM 本身的負載能力受到挑戰
• 請求的總量突然增加，原因可能不止是外在因素，也有可能是前端的 bug
• 上游服務回應速度變慢了，不管是服務本身的處理速度降低、有程式上的錯或者網路環境等等。

當某個服務的請求突然增加，我們可以透過限流機制（Rate Limit，沒錯就是超級保鑣 萊特利米特）來避免上游和 APIM 本身的服務降載，進而引發全服務的降載。其邏輯大致是當某個服務或使用者每分鐘的請求數超過上限，就拒絕接下來的所有請求。

當請求的總量突然增加時，我們可以透過自動增長（auto scaling）的機制，增加 APIM 的節點數量。但是當請求增長的速度過快就可能會來不及增加 APIM 的節點數，例如壞掉的服務重啟瞬間。就算 APIM 有自動增長的機制，但如果上游服務沒有這個機制，對於上游來說突然增加的請求仍然會對服務造成傷害。

最後，當上游服務降載時，現有的限流機制沒辦法快速反應這個服務的健康狀況，此時的限流就如同虛設。舉例來說，本來服務每秒可以接受 100 個請求，因此在 APIM 中的設定便限制每秒最多 100 個請求送過去，但是因為服務開始降載了（例如正在做垃圾回收），此時它只能承載 50 個請求，但 APIM 沒辦法感知到這件事。所以 APIM 就把超過 50 個請求往上游送，造成服務節點負載過重，直接中斷程序。

APIM 之所以稱為 API Management，就是因為我們期望他能做到管理 API 的功能，不僅僅是要做到驗證授權和導流的功能。它也要能避免給予上游服務過多的請求導致其服務崩潰，否則就應該稱其為 Auth Proxy 而非 Management。

負載測試¶

所以問題回到：我要怎麼知道一個服務每秒能承載的量？這個問題聽起來很簡單，其實很複雜。首先我們需要做一個負載測試確認該服務能承擔的負載。但是這個測試環境需要盡可能的減少和線上環境的差異，例如本地端常駐程序（daemon）的差異、應用程式的設定差異、網路環境的差異。再來還有，測試時是在同一台電腦還是拿多台電腦一起發送並行請求？，這些請求的連線是否需要 keep alive ？每個請求的酬載（payload）都要有差異嗎？最後是應用程式本身要測哪些功能？有些功能會需要跑約 10 秒，有些卻是單純的請求故僅需 30 毫秒就會回應，這代表不同的功能有不同能承載的量。

在測試時也需要注意並行請求數上升時，服務的通量並不會維持在最高水平，而是會開始進入退化期（degradation），這時我們要找的「服務每秒能承載的量」就會是在這個曲線的最高點。所以在測試時不能一昧的增加並行請求的數量然後計算潛伏（latency），而是要計算通量和並行請求數的平面圖，並同時計算出這個服務的容量，才能得出高請求量時服務所表現的行為。

壅塞控制¶

負載測試聽起來要注意很多眉眉角角，這樣我們有沒有一個自動化的機制呢？這時就會提到自動化處理壅塞的控制系統，或者稱壅塞控制（congestion avoidance control）。相關論文始於 1988 年，而最一開始應用的地方就如前言所述，是在 TCP 協定中。

隨著該控制演算法的優勢顯現出來，開始出現一些相關的優化和設計，例如 1995 年的 Vegas、2002 年的 AIMD-FC、2004 年的 BIC 等等各種演算法。然而這樣一個稱不上最新的領域為什麼又重新浮出水面了呢？這是因為這個東西可以很好的解決我們上面提到 APIM 的請求管理問題。

出乎意料地，上面提到的很多演算法，和負載測試的眉眉角角竟能透過一個簡單公式歸納起來！這個公式就是 1954 年利特爾提出的利特爾法則。

... This relationship is covered very nicely with Little's Law Netflix - concurrency-limit

利特爾法則¶

利特爾法則（Little's law）於 1954 年利特爾提出。我們回到一開始銀行的例子，如果我現在想要設計銀行的椅子數量或者大廳提供人等待的空間大小時，就要思考「銀行平均會有幾個顧客在裡面」這個問題，這時就可以使用利特爾透過精妙的推導得出的這個法則。假設銀行每小時平均進來的人數有 30 個人（\(30\; p/hr\)）而每個人等待加處理業務的平均時間是 6 分鐘（也就是 0.1 個小時，\(0.1\; hr\)）這樣我們就可以算出平均的顧客人數為 \(30\; p/hr \times 0.1\; hr = 3\; p\)，三個人。所以我們只需要準備三張椅子就可以讓在銀行的人都能得到位子坐（至少機率上來說是這樣）。

我們再看看一個例子，倉儲中心想要知道「倉庫要多大來存放這些貨品」，所以他開始計算每天平均送進來的貨品數和每件貨物平均要放多久才會被送出，並得出有每天有 100 件貨品進來且每件貨品要存放三天才會被送出，這時我們就知道這個倉庫要可以放 300 件貨品才夠大。這個計算代表了什麼？即使在計算這個非常抽象的結果「我需要多大的倉庫」時，我僅僅需要兩個參數就可以完成計算，並且不受到貨流程分配、服務分配、服務順序，或任何其他因素影響，厲害吧？

網路服務的利特爾法則¶

我們把例子放回網路服務中，當我們想知道這個服務能不能處理這個請求量，我們就可以開始套用利特爾法則。

\(L\) 代表平均請求量，\(\lambda\) 代表請求率，\(W\) 代表執行時間。

沒辦法想像？沒關係，我們來實作。

請先到 playground-adaptive-concurrency，照著 README 操作，把服務啟動起來。

實作一¶

每秒 15 個請求且每個請求 500 毫秒後執行完成。

node src/client.js --wait 500 --rate 15 --duration 120 --port 8080

圖的上半部是請求的數量分佈，由於每秒鐘會有 15 個請求，所以總量會維持在 15 個。正在處理（in-flight）的請求會一直維持在 10 個（根據設定，一個 server 最多只能同時處理 10 個請求），而 pending 的數量會維持在 5 個。會看到 pending 的數量抖動是因為在做 metrics 的時候是每 0.5 秒輸出一次，有時過了 0.5 秒後所有的請求都處理完了（因為有 jitter），所以就會顯示變動的 pending 數量。圖中的左下角代表 server 每秒處理的請求數量，也就是通量（throughput）。右下角是平均的潛時，10 個請求需耗時 500ms，5 個請求需耗時 1000ms，故而 \(\left ( 10 \times 500 + 5 \times 1000 \right )/15 \approx 667\; ms\)。

用拼圖的方式來呈現請求的狀態就會如下圖：

這個結果應該是可以想像的，但是下一個實作呢？

實作二¶

每秒 15 個請求且每個請求 600 毫秒後執行完成。

node src/client.js --wait 600 --rate 15 --duration 120 --port 8080

在開始前，你可以試著回答這個問題：現在應用程式能服務這個量的請求嗎？

跟你想的一樣嗎？即使請求來到 600 毫秒，這個服務也能處理！這聽起來有點違反直覺，因為多出來的 100 毫秒好像會逐漸累積，最後導致服務來不及處理。但其實我們照上面把請求用拼圖的方式畫出來就能知道實際怎麼運作的。

由上圖就可以知道隨著時間進行，請求處理的模式就會一直循環下去，留下中間 200 ms（\(2000 - 600 \times 3 = 200\; ms\)）的空白。

這樣每次我在算服務能處理的量都需要畫這個拼圖嗎？不要忘了，我們還有利特爾法則！當我們把數值帶進公式裡就會發現生命的美好！\(L = \lambda \times W = 15\; req/s \times 0.6\; s = 9\; req\)，所以如果我們的應用程式擁有大於 9 的容量（capacity），我就能處理這個潛時（latency）的請求。各位也可以試著算一下右下角的「Server latency」為什麼會維持在 0.88 秒左右。

實作三¶

每秒 15 個請求且每個請求 700 毫秒後執行完成。

node src/client.js --wait 700 --rate 15 --duration 120 --port 8080

我們在開始前就可以試著用利特爾法則算一下這樣服務能不能承載，要注意 server 只能承載 10 個請求的量，換句話說他的容量只有 10，當請求數超過 10 就會讓請求 pending。

\(15 \times 0.7 = 11.5\; req\)，由此可知因為他超過服務的容量，所以就會開始讓請求延宕（pending），並等待有能力時再做運算，最後 Nginx 等太久，出現 timeout 的請求，並回應 504。

這裡的圖就需要好好解釋一下了，首先看上面 server 的處理狀況，因為還沒處理好上一秒的請求，又接著來了下一秒的請求，所以 pending 的請求數就會開始無止境的累積。在左下角的 client 的角度，就會發現當到了 10:15:50 HTTP 200 的請求開始減少，取而代之的是 Nginx 回的 504 Timeout，且這個過程是漸進的。這是因為在過程中仍然有請求在 4 秒內回應請求（pending 轉到 in-flight 並花 0.7 秒處理完成），但是當超過臨界點時，也就是所有請求都需要執行超過 4 秒時，client 就會收到所有的請求皆為 504，同一時間我們可以看右下角的圖來驗證平均潛時正逐步往 4 秒靠近。當到了 10:17:05 時，我們再回到 server 的角度，因為兩分鐘（120 秒）過去了，client 不再送請求過來時，他就能逐步把肚子中的請求消化下來，因而 pending 的請求數開始驟降。

接著我們來算一下左下角中淡藍色的線（HTTP 200 每秒的請求數並每十秒平均一次），server 的通量在高峰時平均來說是多少（也就是 10:15:10 到 10:15:45 之間）？這時就是把利特爾法則換一下：\(\lambda = L / W = 10 / 0.7 \approx 14.3\)，反過來說，如果我要求這個服務要能每秒處理 15 個請求，這時需要讓每個請求壓在幾秒內完成？\(W = L / \lambda = 10 / 15 \approx 0.67\)，也就是如果請求在 0.67 秒內完成，他就不會讓請求開始雍塞並堆積，感受到利特爾法則的方便了嗎！

AIMD¶

有了利特爾法則，當我們把「平均請求量」設為控制變因（以上面實作為例就是 10），我們就可以知道當潛時（latency）上升，服務的通量（throughput）就會降低。故而身為 APIM，我們就可以降低請求導流到該服務的量，來避免服務持續地阻塞未能處理的請求。

但問題是，我們很可能不知道上游服務限制請求的量，這時我們就只能透過觀測潛時來自動修正服務能收到的請求量。這個精神，就是 Additive-Increase/Multiplicative-Decrease（AIMD）在做的事。

當潛時穩定時，逐步增加（Additive-Increase）請求的限制數，當潛時過高時，就壓低請求數（Multiplicative-Decrease），讓上游服務有時間能處理現有的請求。聽起來沒什麼用？我們來 DEMO 看看吧！

AIMD 實作細節詳見相關程式碼。

實作 AIMD¶

node src/client.js --wait 700 --rate 15 --duration 120 --port 8081

現在你就可以看到對上游服務來說很明顯的差異了，他不再會有不斷上升的 pending 請求，而是在一個持續穩定的水平中。這是因為在實作 AIMD 的 proxy 中，它開始紀錄服務可以承載的量，並拒絕那些超出限制的請求。以左下角的圖來說，因為 proxy 初始的限制是十個請求，所以一開始會有一個小山丘，當他開始逐步增加（Additive-Increase）請求的限制數時，這個紅色小山丘就開始下降，最後來到一個平穩的水平線中。對於上游服務來說，他的通量（throughput）仍然維持著約 \(14.3 req/s\) 左右，但重點是他不再累積那些無法消化的請求，而是透過 proxy 直接拒絕這些請求。

我們再來看看另外一個實作，這次實作是讓上游服務的潛時從 600ms 升到 700ms 再升到 1000ms。

# 使 server 預設等待 600ms
curl localhost:8000/set-wait/600
# --wait = 0 代表使用 server 預設的 waiting time
node src/client.js --wait 0 --rate 15 --duration 0 --port 8081
# 逐步增加
curl localhost:8000/set-wait/700
curl localhost:8000/set-wait/1000

在 11:06:30 以前，行為都和前面差不多，值得注意的是，當潛時來到 1000ms 時，可以看到 proxy 開始自動降低請求數，開始拒絕多出的 5 個請求。這裡重點是上圖的請求數，他的曲線很典型的反應了 AIMD 的增幅：逐步上升，快速陡落。這一切都不需要調整應用程式，只是在 proxy 中加上一些小程式，就可以大大的降低上游服務承載過多的請求發生的機會。

比較¶

接下來我們就來比較一下限流機制和適應性並行處理（AIMD 就是一種實作）。

利用率的比較¶

所謂的利用率，就是服務被完整地使用的比例。舉例來說，如果一個服務擁有 100 的通量，但是為了避免各個使用者（client）搶佔資源，所以限制 使用者A 每秒只能打 15 個請求，使用者B 每秒只能打 40 個請求，而這些使用者的請求總限制會小於等於 100，這是因為避免當每個服務都同時使用最高上限，就很可能讓這個 APIM 中斷程序。但是當這個服務前面掛載了適應性並行處理的機制，就可以安心讓 使用者A 和 使用者B 都擁有每秒 80 個請求的限制，即使他們合計起來是 160 也就是大於能負荷的每秒 100 個請求。

這有什麼優勢？第一個就是服務的資源能被有效利用，第二個就是當請求的量增加時，使用者比較不會踩到限制而被拒絕（通常限流的限制是有時效的，例如不再接受這個使用者或服務接下來 5 分鐘的請求）。

我們來實作看看吧！

# 分別在兩個終端輸入其中一個指令
node src/client.js --wait 700 --rate 10 --duration 120 --name A --port 8081
node src/client.js --wait 700 --rate 10 --duration 120 --name B --port 8081

我們可以看到左下的 使用者A 和右下的 使用者 B 都可以得到 HTTP 200 的回應，且兩者的總通量（左上角）仍然是單一使用者的 14.3。如果有興趣，可以測試一下執行這些 client 的先後順序是否會對獲得 504 的比例有所影響，這個議題我們留到延伸再提一下。

可擴展性的比較¶

隨著應用程式的成長，我們勢必會面臨可擴展性的挑戰。限流機制很難做到可擴展性，事實上他要面臨的是分散式系統最困難的問題——狀態機的分散式處理。因為要做限流，勢必需要儲存各個使用者的使用紀錄，例如紀錄其五分鐘內的請求數。可能的做法有：

• 透過外部的資料庫來儲存這些狀態，例如 Redis、Dragonfly。把擴展性的問題丟給資料庫。
• 留言協議（Gossip），讓各個節點彼此溝通協調各自的狀態，他不像共識演算法這麼嚴謹。
• 協調者，把資料的處理丟給一個外部協調者，很像資料庫，但這協調者是一種應用程式。
• 相對於協調者，你可以在叢集內部推舉一個或多個領袖來決定限流的狀態，但是領袖的選擇需要共識演算法。
• 放棄準確性，讓各個節點處理各自的狀態，例如原本每個使用者每秒限制 100 個請求，當分散到四個節點就是限制每個使用者每秒 25 個請求

把擴展性的問題放到適應性並行處理會發生什麼事？我們來實作看看吧！

# 分別在兩個終端輸入其中一個指令
node src/client.js --wait 700 --rate 10 --duration 0 --port 8081
node src/client.js --wait 700 --rate 10 --duration 0 --port 8082

我們可以看到這實作中有兩個 proxy，ProxyA 的 port 是 8081、ProxyB 的 port 是 8082。當兩個 proxy 各自接收十個請求時，他們會自己根據上游的潛時找出最適當的請求限制，所以對於上游服務來說，實際通量仍然維持 \(14.3 req/s\) 左右。這時你完全不需要考慮擴展性的問題，因為這些 proxy 會自動找出最適當的限制，只是你不能給予過高的通量最低限制，因為當流量分散到多個 proxy 時，各自 proxy 的通量可能會很低，設定過高的最低限制將會破壞預期的行為。

總結¶

我們看到了適應性並行處理可以幫助我們排解上游服務的過載，我們甚至不需要知道上游服務的通量或容量，透過持續觀測的潛時來調整應該送往上游的請求數。最後再來問個問題，古老的訓言中，有得必有失，在這裡失準了嗎？聽起來他好像可以完全取代限流機制？這是因為限流機制和適應性並行處理分別要解決的問題不同，回到我們最一開始的例子，保鑣並不是一個無能的職業，只是他們能處理的事情和業務處理時間被拉長這兩者之間的關聯性並不高。限流機制在面對惡意（無意）的請求的破壞是可以很好的防範的，透過 IP、UA 甚至 Header 來辨別使用者並給予限制。

在適應性並行處理中，「有得必有失」是適用在實作的演算法上，例如上述的 AIMD。

延伸¶

其實還有很多延伸可以調整和優化，這裡列舉幾個：

• 不同的請求，可能會有不同的優先程度，例如 VIP 會員。
• 根據不同功能，潛時可能會有不同的高低，所以不只是根據服務記錄潛時，甚至要根據不同 path 紀錄潛時。
• 前面提的利用率，很簡單的把 100 個限制分成 80/80，有沒有更好或更通用的分法？

除了這些問題，如果你對於如何增加網路服務的穩定度，最好的辦法還是讀書，因為書裡的內容都會比較系統性的講解，推薦的書有 Google 內部工程師寫的 Site Reliability Engineering。