# Part #3 微服務基礎建設 - 排隊機制設計

## [Part #3](https://columns.chicken-house.net/2018/12/12/microservice11-lineup/) 微服務基礎建設 - 排隊機制設計

## 問題與需求

捲起袖子開始動手之前，我先定義一下我講的 “排隊機制” 到底是什麼? 我對這個排隊機制的期待到底有哪些?

首先，我指的 “排隊機制” 是:

> 購物網站在結帳時必須做大量的驗證與計算，為了確保運算能順利進行，同時間只能允許一定個數的使用者進入這個階段。其餘還未能進入結帳的訪客，就必須進入 “排隊” 狀態。若前面的使用者已經結束結帳的程序，空出的資源就可以依序按照順位，讓下一位使用者優先進入結帳。

理想的排隊機制，不只是要保護系統的處理能力不被沖垮而已，同時也應該要顧及排隊者的體驗，例如能隨時得知排隊的順位、預估剩餘時間等等。若以實體的店面當作例子，商店為了應付周年慶湧進的客人，會多開幾台收銀機來結帳。越多的收銀機代表越大的交易處理能力，這是提高 TPS。不過店面的空間有限，必須控制同時待在店內的人數，當店內客人收銀機還沒消化完畢前 (也許有一些只是在店裡面逛逛而已) 其餘的人只好先按照順序在門口排隊，等到有人離開店之後才能進來消費，這就是排隊機制。

我對排隊機制的期望: 我希望這些過程中也要確保不要過度耗用系統的資源，最好也能提供足夠的監控資訊確保運作順暢。

這會不會太貪心了一點? 其實不會。按照慣例，既然是 POC，我在意的就是可行性。我先略過花時間的工程問題，把規模先縮小到單機的範圍，也跟外部的各種工具、服務或是框架的相依性降到最低。雖然規模縮小了，不過平行處理這環節可不能省，因此 thread safe / lock 這件事還是得做，我必須確保這設計將來是可以擴大為分散式的版本。

做這次排隊機制的改善，我歸納一下期待改善的幾項 (有些是前一版的缺點，我一起列):

**面對使用者端的需求** (frontend developer):

1. 必須是 pooling 模式, 使用者必須不斷的 check status, 也可能會在任意時間中途斷線。
2. 核心引擎設計期望的排隊數量 (數量級): 10,000 人, 更新週期為 1 sec
3. 排隊的結果必須是公平的 (只要沒有被剔除隊伍，先排的一定要先使用服務)，不允許後來先到的狀況，尤其是資源有限制數量時更應該確實做到。
4. 排隊的過程必須提供明確的 feedback, 必須讓使用者知道目前狀態 (是否能開始進入結帳)，也必須告知順位 (前面還排幾位)。若能搭配平均處理速度的統計數據的話，就能進一步預估等候時間。

**面對維運人員端的需求**:

1. 必須能排隊的狀態 (排隊中,結帳中,已完成,已放棄…) 的即時數據監控
2. 必須能動態調整排隊的參數 (如排隊上限、允許同時結帳人數等等)
3. 必須有能力手動踢除使用者 (by id, by queue, by idle time … etc)

**核心服務開發人員端的需求**:

1. 每個使用者查詢排隊狀況請求時, 要降低 storage 的 IO 數量 (storage IOPS 過高是舊系統的瓶頸, 也直接影響 cost)
2. 每個使用者查詢排隊狀況請求時, 運算的時間複雜度必須是 O(1)
3. 隨時都可能有使用者決定離開或是斷線。必須設計機制排除這些使用者，避免佔用位置又不進行交易
4. 必須能同時提供多個 (10,000) 個獨立的排隊隊伍

對於架構師來說，這是各方提出來的許願池啊，要同時兼顧實在有點困難。不過這就是挑戰，我期望在 POC 階段就盡可能確定核心的設計能滿足這些需求。考量到我自己一人不可能同時熟悉各種開發實做技術，因此最好的做法就是透過 POC 跟團隊溝通，讓團隊有能力了解設計理念並且有能力接手才是正途。對於開發團隊來說 (要將這 POC 產品化，或是將來要使用我這服務的開發團隊)，這就是最好的 MVP (Minimum Viable Products) 啊，我可以最快的得到 feedback, 就算失敗了我也能快速確認這條路不可行 (快速失敗, Fast fail)。很多團隊往往看了一堆理論方法，卻掌握不到 MVP, Fast Fail 等等作法的要領…，實在可惜。面對越複雜、越關鍵或是越核心的問題，越值得多花點心思確認可行性。這個排隊問題我就用這種標準去看待它，這篇就正好記錄整個過程。

## 現實世界的排隊搶購機制

如果要真的從演算法開始講，那應該會看到睡著… 我先找實際生活中的案例來對比好了。全世界最愛排隊的就是台灣人了 (咦??) 台灣人這麼愛排隊，應該不缺這類經驗吧。當年念書期間受到嚴格的 OOP 訓練洗禮 (老師是 smalltalk 教義派)，很多問題我都習慣先思考一下，沒有電腦的世界是怎麼處理這類問題的? 往往從這些現實世界的解決方式，都可以對應到 code 的處理流程。如果現實世界的店面排序都可以靠工人智慧就能有條理地進行，沒道理線上就不行吧!

所以我想了想，一些熱門餐廳 (比如台灣人去日本最愛排的X蘭拉麵 XD)，排隊時都怎麼做? 讓排隊機制可以更可靠有效率?

1. 餐廳內的座位數量有限 (A)，你可以浪費一些座位，讓位子是空的 (排隊管理的效率差的情況)。但是你絕對不能把兩個顧客塞在同一個座位上
2. 點菜跟上菜需要時間，可以讓快要排到的顧客 (B) 先進行這段程序 (ex: 預估 10 min 內會輪到他入座的顧客, 或是排最前面的 10 位, 或是在排隊隊伍最前面放自動點菜機)
3. 每日限量，過去估計一天若能服務 300 (C) 位客人，那其實可以直接告訴排在第 500 (D) 順位以後的顧客不用排了，今天應該輪不到他。對這些顧客可以採取其他的服務，例如給優惠券、或是留下電話等等若真的還有位子可以通知他…

單純就 “規則” 而言，我覺得這個方式還蠻有效率的。規則訂好之後，每個顧客，還有店員要執行的動作都很簡單，簡單到不需要太多的訓練或說明，就能有效的運作下去。舉例來說，上述幾個例子，都可以按照顧客排在隊伍內的位置決定。如果排隊時顧客都有領號碼牌，那就更容易了，直接找號碼牌在範圍內的顧客就可以了。

## 排隊機制演算法

看 code 前，先來看看這演算法怎麼運作。若暫時不考慮斷線的使用者狀況，還可以更精簡一點。以下的例子我就都先用等待進入餐廳用餐的排隊當作案例。每一組獨立的排隊，只須要維護這些資料就可以運作:

**每組隊伍**:

* **結帳起點** (尚未完成結帳, 數字最小的號碼)
* **排隊起點** (還不能進入店內用餐, 排隊排最前面那位的號碼)
* **排隊終點** (今日允許排隊上限位置的號碼)
* **號碼牌發放機** (下一張號碼牌的號碼)

正常的情況下，其實只要維護好這四個數字，加上每個顧客保管好手上的號碼牌，排隊機制就能順利運作了。不過過程中總是有些意外狀況發生，例如有人離開排隊隊伍，但是你不知道他還會不會回來，因此要記錄他最後一次回報的時間，才能判定他已經離開多久，是否要把他剔除。如果這個人已經確定離開隊伍，則這筆資料就可以刪除。整個隊伍維護的資料範圍是有限的，號碼牌 (以下稱 token) 的範圍最多從 “結帳起點” 到 “號碼牌發放機” 之間的 token 才有可能有使用者資訊。

接下來先看看這機制怎麼運作吧，來看一下連續動作:

### 開店 (初始狀態)

![img](https://columns.chicken-house.net/wp-content/images/2018-12-12-microservice11-lineup/SLIDE-03.png)

如果店內只有 7 個座位，店外排隊隊伍長度最多只設定為 15 (走道空間有限)，超過就直接請他不用排隊了的話，那麼初始值應該如上圖所示:

結帳起點: 0 排隊起點: 7 排隊終點: 22 ( 7 + 15 = 22 ) 號碼機: 1 (下一位加入排隊隊伍的人，會拿到 1 號 token)

因此:

拿到 1 \~ 7 號的使用者，可以直接進入用餐 (紅色) 拿到 8 \~ 21 號的使用者，必須在外面排隊稍後 (藍色)

### 開始營業 (使用者湧入)

![img](https://columns.chicken-house.net/wp-content/images/2018-12-12-microservice11-lineup/SLIDE-04.png)

如果開張之後，有第一位使用者進來了，那麼…

1. 使用者先取 token, 由於 \[號碼機] 數值為 1, 因此他可以取走 token(1)，並且加入隊伍開始排隊。號碼機被抽走 token(1), 下一位取票的會拿到 token(2)
2. 由於這位使用者拿到 token(1)，照隊伍的狀態來看，只要在 \[排隊起點] 數字之前的使用者都可以直接進入用餐。因此這使用者直接可以進入用餐狀態 (紅色)。

此時，數據狀態應該為:

結帳起點: 0 排隊起點: 7 排隊終點: 22 號碼機: 2

![img](https://columns.chicken-house.net/wp-content/images/2018-12-12-microservice11-lineup/SLIDE-05.png)

接著，又一位使用者來排隊，重複上述動作，結果如上圖，此時數據為:

結帳起點: 0 排隊起點: 7 排隊終點: 22 號碼機: 3

![img](https://columns.chicken-house.net/wp-content/images/2018-12-12-microservice11-lineup/SLIDE-06.png)

再來，陸陸續續又來了 7 位，重複上述動作，結果應該如上圖，數據為:

結帳起點: 0 排隊起點: 7 排隊終點: 22 號碼機: 10

這時，拿到 token(8), token(9) 兩張號碼牌的使用者，因為他的數字比 \[排隊起點] 大，因此必須在櫃檯那邊開始排隊了 (藍色)。

因為 \[排隊起點] 的數值是 (7), 這時 token(8) 使用者可以透過簡單的運算 ( 8 - 7 = 1 ) 知道他自己是第一順位。同理 token(9) 也可以不用店員告知，就知道他是 ( 9 - 7 = 2 ) 第二順位。如果搭配平均每個人用餐時間是 15 min 的話，很容易就能預估還要等多久。

### 營業中 (使用者結帳)

![img](https://columns.chicken-house.net/wp-content/images/2018-12-12-microservice11-lineup/SLIDE-07.png)

使用者進去店內用餐後，token(3) 使用者吃得比較快，決定先結帳離開，於是就起身到櫃檯去結帳了 (粉紅色)。

此時，隊伍的數據為:

結帳起點: 0 排隊起點: 7 排隊終點: 22 號碼機: 10

![img](https://columns.chicken-house.net/wp-content/images/2018-12-12-microservice11-lineup/SLIDE-08.png)

結帳過程需要一些時間，從使用者起身去櫃檯付款，直到服務生清理完這座位後，這個位子才能空出來繼續服務。這過程結束後，還在排隊的使用者就可以再放一位進來店內用餐了。因此座位清理好這瞬間，整個隊伍的狀態應該變成上圖所示。紅色空心的數字代表這位使用者已經離開，不過號碼機不會發放重複的 token, 因此 3 號不會從圖上移除，但是它已經不占位子了，替代作法是把 \[排隊起點] 往後移一位，下一位使用者就符合能進入用餐的條件了，下一秒這位使用者在確認能否用餐時就會通過，就能進來店面用餐。

在這瞬間，空出 (3) 之後，隊伍的數據: \[排隊起點] 與 \[排隊終點] 都應該往後移一位。這時 token(8) 因為這次移動，從排隊區 (9 \~ 23, 藍色) 換到用餐區 (1 \~ 8, 紅色)。這時 token(9) 還留在排隊區 (紅色) 沒辦法進入用餐，必須繼續排隊。這時 token(9) 的順位是 9 - 8 = 1 。

前面提到，由於整個隊伍需要維護的資訊範圍是 \[結帳起點] \~ \[號碼機] 的範圍，token(3) 雖然已經離開了，不過還在範圍內，因此暫時保留它的資訊 (號碼牌?)，用實線空心的數字球來表示。

此時，隊伍的數據為:

結帳起點: 0 排隊起點: 8 排隊終點: 23 號碼機: 10

![img](https://columns.chicken-house.net/wp-content/images/2018-12-12-microservice11-lineup/SLIDE-09.png)

此時，如果又有一位使用者 token(2) 用餐完畢，重複上述的步驟，結果如上圖所示。這時 token(9) 也可以進入用餐了。\[排隊起點] 及 \[排隊終點] 的指標再次右移一位。

此時，隊伍的數據為:

結帳起點: 0 排隊起點: 9 排隊終點: 24 號碼機: 10

### 營業中 (清除隊伍不必要的資訊)

![img](https://columns.chicken-house.net/wp-content/images/2018-12-12-microservice11-lineup/SLIDE-10.png)

不知各位有無留意到，即使陸續有人排隊，也有人結帳離開，但是隊伍資訊的 \[結帳起點] 卻一直沒有變化，因為開店後第一位進入用餐的 token(1) 其實都還沒離開，因此 \[結帳起點] 都還維持為 0。簡單的紀錄，方便店家知道，如果他要查閱目前所有隊伍的資訊，只要從 \[結帳起點]: 0 開始往後找就好。

如果這時， token(1) 也要結帳離開了的話… 結果會變成下圖:

![img](https://columns.chicken-house.net/wp-content/images/2018-12-12-microservice11-lineup/SLIDE-11.png)

整個的結帳處理程序，都跟前面一樣。唯獨不同的是，隊伍最前面 1, 2, 3 都已經結完帳走人了，有連續的一塊區塊都已完成結帳，這時 \[結帳起點] 還從 0 開始紀錄已經沒有意義了，下次要維護隊伍資料，或有任何目的要掃描一次所有隊伍資訊時，不再需要從 0 開始，下次直接從 3 開始即可，因此若偵測到原本的 \[結帳起點] 後的使用者已經離開，這個指標就能夠往右移動，直到一到下一個還沒離開隊伍的使用者為止。以這個情境為例，新的 \[結帳起點] 應該是 3 才對，請參考上圖所示。

此時，隊伍的數據為:

結帳起點: 3 排隊起點: 10 排隊終點: 25 號碼機: 10

### 營業中 (預測等待時間)

排隊時，使用者的心理就是一直在想:

> 到底還要等多久? 會不會等到我就賣光了?

隨著排隊隊伍越來越長，這類資訊的需求及更新頻率會越來越高，因此排隊機制最好在設計之初就考慮好這個問題。處理得當可以避免很多後端不必要的運算。延續這個案例，繼續看一下，如果排隊隊伍越來越長，\[號碼牌] 領到 token(18) 的狀況:

![img](https://columns.chicken-house.net/wp-content/images/2018-12-12-microservice11-lineup/SLIDE-12.png)

此時，隊伍的數據為:

結帳起點: 3 排隊起點: 10 排隊終點: 25 號碼機: 19

如同前面說過，如果最後一位排隊的使用者 token(18) 想知道他的順位，馬上就可以得知排隊順位為 18 - 10 = 8 。這個數字完全不需要做任何的搜尋就可以得知，時間複雜度只有 O(1)。

為何我會不斷的強調這件事? 以這個案例，走到現在的狀態是:

排隊中的使用者共有 8 位 (11 \~ 18), 如果每位每一秒都要跟店員確詢問一次:

> 目前排隊起點的號碼是?

則店員每秒鐘會被問這麼多次:

QPS = 8 / 1 sec = 8 次/sec;

如果排隊中的使用者有 N 位，那 QPS 就是 N 了。人數變多，或是查詢頻率提高，都會讓這個查詢的 QPS 拉高。先前我提到舊系統的案例，這邊就是個大瓶頸。當時這部分的開發不完全是為了這個情境設計的，有別的考量，這部分一個使用者查詢執行的時間複雜度是 O(n), 因此整個系統跑下來就變成 O(n^2) 了，然而這個動作，背後還卡到別的雲端服務有 IPOS 的限制 (換句話說後端的服務是照 IPOS 收錢的…)，整個成本跟效能就大爆炸啊啊啊…

回到主題，如果能用很低的運算成本跟運算資源，就能讓使用者取得排隊順位的資訊 (例如裝個顯示器，讓所有使用者抬頭就看的到排隊起點的號碼)，那麼即使是用 pooling 的做法，我也能適當的提高 pooling 的頻率，讓使用者得到更精準的 feedback。如果你的服務做得更到位一點，額外多花了點精神去統計過去一段時間的消費速度，那就可以更貼心地替使用者預估他還要等待的時間。排除額外統計花費的時間 (那個 server 統一做一次就夠了)，對於每個使用者來說，只是排隊順位 x 平均時間而已，複雜度仍然是 O(1)，對店家而言，整體應付詢問的成本只有 O(n)。

### 避免不必要的排隊

![img](https://columns.chicken-house.net/wp-content/images/2018-12-12-microservice11-lineup/SLIDE-13.png)

接下來看個極端的狀況，你的店生意實在太好，排隊排到下條街去了。排隊人數遠遠超過你能服務的數量 (例如餐點的數量有限，賣完就沒有了)。雖然有些人可能會中途放棄排隊會空出一些位置出來；不過按照經驗，總是可以抓個包含候補的範圍出來，超過這個範圍，不用等到真的賣完，當下就可以直接告訴使用者不用排隊了。這個舉動，不但能節省使用者端的時間與資源，店員 (server) 的工作份量也可以降低。

面對這個狀況，同樣的拿 \[號碼牌] 跟 \[排隊終點] 來比較就可以了，只要號碼機下一張號碼牌的數字，在排隊終點之前，下一位使用者就可以來領號碼牌加入排隊隊伍了。如果 \[號碼機] > \[排隊終點]，代表排隊隊伍已經長到極限了，這時就不應該再讓使用者取票排隊，應該直接請他離開了。如果你打算給這些使用者一些補償方案 (例如下次來訪的折價券，或是贈送贈品之類)，取票失敗就是個好時機。

此時，隊伍的數據為:

結帳起點: 3 排隊起點: 10 排隊終點: 25 號碼機: 26

### 放棄排隊/結帳

整個演算法說明的過程中，我沒有特別提到這些例外的處理。排隊過程中最常見的就是: 排到一半不想了，就直接走掉了。或是號碼牌弄丟了，這個號碼永遠不可能進來用餐，使用者也重新取票排隊了。這時，如何確保這個永遠不會進店用餐的號碼牌佔住名額?

其實這個問題很簡單，我分成兩部份考慮:

1. 如何找出那些 token 的號碼??
2. 找到之後，如何正確地將他從隊伍內移除?

其實 (2) 的問題反而很簡單。仔細想一下，我們從開始到現在，討論的問題其實不是結帳，而是加入/離開隊伍而已。因此不管你有沒有結帳，對於隊伍而言就是離開而已。所有動作，包含四個指標的處理方式通通一模一樣，我這邊就省略不談。

剩下的問題只有: 如何偵測已離開的使用者?

前面的過程中，排隊中的人都會不斷的詢問店員目前排隊的起點號碼，店員可以趁詢問/回覆的同時，順便記錄這個 token 最後詢問的時間。假設我們預期每個使用者每分鐘都來詢問一次，那麼我們就可以定義，超過 5 分鐘以上都沒有回來詢問的 token，就把它當作離開了，可以從隊伍內剔除。如果他六分鐘過後真的又回來了，那很抱歉，只能請他再領一張 token 重新排一次。

這時要定義一個 recycle worker, 定期巡一下紀錄，從 \[結帳開始] 到 \[號碼機] 的範圍，把失聯超過五分鐘的 token 通通找出來。每個都按照上述的程序，把它從隊伍內正確的剔掉就可以了。踢掉這些失聯的使用者，自然會讓 \[排隊起點] 與 \[排隊終點] 數字往後移動，讓其他人能進店用餐，或是加入排隊的隊伍。

### 演算法 - 小結

寫到這裡，終於把整個計算方式交代到一段落了。

軟體開發到最後，越來越覺得正確的架構跟演算法還是最重要的，這些搞清楚後，再去找適合的工具或是框架來使用，才會事半功倍。因此我都會強迫自己先撇開這些外圍的干擾，搞清楚問題核心後再來寫 code .. 這個演算法最主要的目的，是改善排隊期間為了管理排隊秩序所花費的運算資源。

以用餐這個例子來說，一個小時內如果可以服務 50 位顧客，隊伍有 300 人排隊，每人每分鐘會詢問一次，店員每分鐘確認有無失聯的話:

1. 詢問的動作，總共會做 (300 - 50) x (60 / 1) = 15000 次
2. 取票的動作，會做 300 次
3. 會移動指標 (只有有人離開才會移動) 會做: 50 次
4. 確認失聯動作，總共會 300 x 60 = 18000 次

從結果來看，很明顯的，必須最佳化的是 (1) 跟 (4), 因此如果你問我我為何會設計這樣的 data structure ? 我會回答我的目的就是想辦法讓 (1) (4) 這兩個動作越有效率越好。我只在 (2) 去更新 \[號碼機] 這指標，只在 (3) 去更新 \[結帳開始]、\[排隊起點]、\[排隊終點] 這三個指標。在相對很少的次數下多花點工夫維護資料，讓佔大多數檢查的時間點用最有效率的計算用 O(1) 來進行，就是我的目的。這樣一來，後端可以用非常低的成本來運行。例如 server instance 可以降好幾個等級的 VM； database 的 IOPS 可以下降非常多； 大部分數值都不會頻繁異動，可以直接到 cache 取得，只要在異動時更新 cache …。

我在做這件事的時候，若接受太多個技術雜訊，反而會干擾我的思路。因此我都會半強迫我自己別在這個階段想太多 framework / tools 的議題。寫到這邊，如果各位讀者還沒完全想通，那可以多花點心思想一下，別急著往下看。這些東西掌握的到位了，才是能受用十幾年的知識。

下一步，就是實作 prototype 來證明計算的結果是正確的。做這件事的目的很簡單，我要交付具體的 “東西” 給我的客戶 (客戶是接手的開發團隊)。確保我規畫出來的東西是他們期望的，能解決它們面臨的問題。在這前提之下，我要採用的各種技術相依性越少越好，code 越少越好，理想的情況是單獨一個 C# console application, 幾百行以內就能跑的狀態是最讚的。

這段如果都想通了，就繼續看下去吧!

## 用 CODE 驗證演算法

這些問題處理的方法，是人的腦袋在想的，但是最後執行卻是要丟給電腦去跑的。排除一堆很工程化的步驟 (如格式轉換, 資料處理, 挑選語言或是資料庫等等)，每種應用應該都有核心的一部分，是要把你的想法寫成 code 的。在驗證階段的 POC 最重要的就是這部份而已，其他通通都可以以後再做 (或是以後交給專業的來)。我在團隊內的角色是架構師，我的職責並不是寫所有的 code, 或是要學會所有的工具跟框架 (這件事我應該也拚不贏年輕人)… 我最重要的任務是告訴團隊該如何去解決問題，因此寫 POC code 就是我認為最有效的方式，也是跟其他工程師溝通最好用的工具。

以這個例子來說，我替團隊構想了問題的解法。與其寫一堆文件，不如一段不會太長 (200 行以內最適合) 的 sample code 的效果。接下來就試試看把上面的想法變成 POC code 吧。

首先，先不管背後怎麼解決問題的，我先思考這個問題的 “邊界” (boundary) 是什麼? OOP 很講求封裝，你要知道哪些要被封裝起來，否則你會寫出一堆語法及執行結果正確，但是結構卻一團亂的 code。所謂的 “邊界”，就是定義你的核心問題，包含在內的就應該被封裝起來，其他的部分就只能透過你定義的介面來跟解決核心問題的元件溝通。

### 核心元件介面設計

這裡的核心問題，就是排隊。我就拿結帳的排隊行為來命名吧! 不論之後是實做成 library / component / services, 是單機版，還是分散式的微服務版本，API 不外乎都要提供這幾個操作。每個隊伍至少要呈現四個指標數字 (號碼機，結帳起點，排隊起點，排隊終點)，以及幾個基本的操作 (取號、詢問、離開、確認失聯的使用者)，我就直接用 C# 的 (abstract) class 來表達:

![img](https://columns.chicken-house.net/wp-content/images/2018-12-12-microservice11-lineup/SLIDE-17.png)

> class diagram

```
public class CheckoutLine
{
    // 指標: 號碼機
    public long CurrentSeed { get; }

    // 指標: 結帳起點
    public long FirstCheckOutPosition { get; }

    // 指標: 排隊起點
    public long LastCheckOutPosition { get; }

    // 指標: 排隊終點
    public long LastQueuePosition { get; }


    public CheckoutLine(int checkoutWindowSize, int queueWindowSize, int timeout = 5)
    {
        // code 略
        // 建構式, 一個 CheckoutLine 物件，可以代表一家店的排隊管理服務。
    }

    public bool TryGetToken(ref long token)
    {
        // code 略
        // 取號的號碼機介面。成功的話 (return bool) 可以取得號碼 (token)
    }

    public CheckoutStateEnum TokenState(long token, bool refresh = true)
    {
        // code 略
        // 查詢某個 token 狀態, 預設這個動作會更新該 token 最後存取時間
    }

    public bool CanCheckout(long token, bool refresh = true)
    {
        // code 略
        // 查詢某個 token 是否已經可以進入店內用餐, 預設這個動作會更新該 token 最後存取時間
    }

    
    public void Remove(long token)
    {
        // code 略
        // 不論因為任何原因, 這個 token 決定離開整個排隊的機制。
    }


    public void Recycle()
    {
        // code 略
        // 巡查整個隊伍，是否有已經超過回報時間的 token, 若有就將之移除，將位置讓給其他還在排隊中的 token。
    }




    // 每發出一張號碼牌(token), 排隊機制背後會建立對應的維護資訊 token info
    // 目前的實作，只須要維護最後查詢時間，作為 timeout 的判定
    public class TokenInfo
    {
        public DateTime LastCheckTime = DateTime.MinValue;
    }

    public enum CheckoutStateEnum
    {
        // 判定為正常排隊的使用者狀態
        NORMAL,

        // 判定為已離開的使用者 (已被呼叫 .Remove() )
        LEAVE,

        // 判定為未離開，但是已經失聯的使用者
        TIMEOUT,

        // 指定的 token 不存在。
        NOTEXIST,
    }

}
```

詳細的實作程式碼，我就不在文章內做過多說明了，大致上就是用這個 class 定義的介面，把前面說明的整個作法封裝起來而已。反而比較重要的是，我另外寫一段 code, 說明這個元件 `class CheckoutLine` 被開發出來之後，會怎麼被使用?

以下這幾個片段的 sample code, 是從後面的模擬程式節錄出來的, 我在這邊當作示範說明使用。

使用這個排隊機制的 application, 必須是先建立好排隊管理的物件 `CheckoutLine`, 你應當替你的服務對象 (如店面) 建立對應的 `CheckoutLine` 物件。如果你的是大老闆，開了五家分店，每家店的排隊機制是互相獨立的，那你就應該建立五個 CheckoutLine instance(s)。

在這個 POC 的案例，你應該要重複使用這個物件才對。重新建立 (new) 的物件，都會被當成另外排一個新的隊伍。適合的作法是把它擺在 static variable, 或是透過 DI (Dependency Injection) 注入, 控制好它只會有一個物件被產生出來。

```
CheckoutLine engine = new CheckoutLine(
    10,     // 可進行結帳程序的人數
    100,    // 可排隊等待的人數
    5);     // 容許失聯的最長時間 (單位: sec)
```

接著就是以下各種應用方式了，請依序參考

### 使用範例: 開始排隊(取號碼牌)

```
//
//  code 略
//

if (engine.TryGetToken(ref item) == false)
{
    // 沒擠進去, 連排隊機會都沒有。直接踢掉
    if (display) Console.WriteLine($"#取號失敗");

    //
    // code 略, 做後續處理, 顯示無法排隊的訊息
    //
    return;
}

if (display) Console.WriteLine($"#取號成功 (號碼牌:{item})");
//
// code 略, 取號成功的後續處理
//
```

我比照 .NET Framework 常用的 `Try...` 這個設計慣例，例如 `Int32.TryParse()`, return value 這管道我用來傳回是否取號成功? 而 ref 參數則用來傳回取號成功的號碼牌數值。

### 使用範例: 判斷目前排隊的進度

```
try {
    Random rnd = new Random();
    while(engine.CanCheckout(item) == false)
    {
        Thread.Sleep(rnd.Next(100) + 400);    // 隨機等待 400 ~ 500 msec
        //
        // code 略, 顯示排隊等待中的訊息, 並且定期 refresh
        //
        if (display) Console.WriteLine($"#目前順位: {item - engine.LastCheckOutPosition}");
    }
}
catch {
    //
    // code 略,無法繼續排隊 (可能情況: timeout, leave, notexist ...)
    //
    throw;
}

//
// code 略, 已可進入結帳流程 (進入餐廳用餐)
//
```

因為我用的 POC 是 console application, 不是 web application, 因此等待的部分也在流程內。我用 `Thread.Sleep()` 來做等待的動作，如果是 web 應該要被拆開，單純 response 等待的畫面，待 browser 下次 refresh 後再重新檢查一次。

這邊提到的，為了改善排隊的體驗，即使需要等待，我也期望能讓使用者知道他現在排隊的進度。這邊我沒做太多例外處理，請自行留意。要跳出 POC 這實驗室的應用前，例外處理是很重要的。`CanCheckout()` 的傳回直定義是:

1. return true, 代表現在已經輪到你進入結帳流程了
2. return false, 正常排隊中，不過還沒輪到你
3. throw exception, 因為各種原因，你已經不在這個隊伍內了。這時已不需要繼續詢問狀態了

實際上可能會碰到 throw Exception 有幾種狀況, 你會永久被剔除排隊隊伍，等不到你進入結帳流程:

1. 程式執行環境有問題, 等太久了, 超過 timeout ..
2. 程式流程有問題, 這個 token 早已完成結帳…
3. 程式有問題, 拿到錯誤的 token…

### 使用範例: 結帳

```
if (display) Console.WriteLine($"#開始結帳: {item}");

Thread.Sleep(rnd.Next(1000) + 4000); // 模擬用餐時間
rate.AcquireRequestAsync().Wait();   // 流量管控，模擬餐廳人手不足，出菜速度受限
//
// code 略, 執行結帳動作
//
engine.Remove(item);  // 結帳完成，離開隊伍

if (display) Console.WriteLine($"#結帳完畢: {item}");
```

這部分就較單純了，沒什麼好判斷的，按照程序進行而已。

不過，這段才會是真正進行交易處理的地方 (前面都只限於排隊等待的管理而已)。這裡可能是購物車真正按下 \[訂單成立] 的地方，因此，在這部分可能會涉及到較多的交易處理，開始會碰到各種資源與效能的瓶頸。例如資料庫過於繁忙等等；在 [上一篇](https://columns.chicken-house.net/2018/06/10/microservice10-throttle/) 提到的流量管控機制，就很適合應用在這個地方。不過在這篇我不打算花篇幅說明這部分，就用一行 code 帶過:

```
rate.AcquireRequestAsync().Wait();   // 流量管控，模擬餐廳人手不足，出菜速度受限
```

如果你結帳時要做一堆確認，例如會員狀態，庫存，還有一堆 blah blah blah 的檢查的話，可能會耗費大量運算資源。為了確保結帳時每筆交易都能順利完成，就有需要嚴格控制每秒鐘能進行交易處理的數量，避免瞬間過多單子處理中衝垮後端服務。

### 使用範例: 剔除發呆使用者

```
Thread r = new Thread(() => {
    do
    {
        Thread.Sleep(1000);
        engine.Recycle();
    } while (_worker_stop_flag == false);
});
r.Start();
```

這段其實不難，定期從排隊隊伍中，找出發呆超過時間的人，逐一呼叫 `Remove()` 把他從隊伍踢掉而已。不過要多加思考的是，負責這件事情的 “糾察隊”，到底算是元件的責任範圍，還是使用元件的店家要負責?

如果我把排隊機制當成 “服務” 來看待，我會把這件事當成排隊服務內部要處理掉的問題。使用這幅務的人只要被通知到有哪些人被踢掉就好了。不過我這 POC 的實作比較偏向 “元件”，提供現成元件給別的開發團隊使用，因此我這邊的安排是把 “巡邏” 的任務都先寫好，讓使用元件的團隊自行決定何時要啟用。

我的作法是，在 POC 程式開始運行之初，就額外建立一個專屬的 thread, 每隔 1 sec 就執行一次 `engine.Recycle()` 任務。

### POC - 小結

這段的 POC, 算是能把想法換成 code 的過程。就如同開始講的，我略過了很多工程問題。例如，token 就是個 long 長整數而已，完全沒有處理防偽造的機制；隊伍的狀態只放在記憶體而已，完全沒有擺在可靠的儲存體內 (如 database 或是 redis 等等)；程式只是單機版而已，完全沒有考慮跨行程的問題。這些不是不重要，而是我相信開發團隊有能力處理後續問題，我只要在這個階段，盡快地確認這樣的演算法能有效率的解決問題即可。剩下的任務，就是把這樣的作法，寫一個分散式的版本出來而已。大部分能力夠的資深工程師應該都能能做這件事，不需要我擔心。

不過，別因為 POC 就馬虎了。POC 有 POC 要驗證的重點，非核心的部分我都可以省略，但是核心的部分還是要照規矩來。例如，單元測試就省不得，壓力測試或是模擬測試更重要。

單元測試我舉個例，測試隊伍 initialize 狀態，用來確認隊伍的數值都正確如預期。 我貼一段讓大家體會一下就好了。要看完整的測試，可以直接 git clone 整包回來看:

```
[TestMethod]
public void InitStateTest()
{
    var c = new CheckoutLine(5, 10);

    Assert.AreEqual(0, c.FirstCheckOutPosition);
    Assert.AreEqual(5, c.LastCheckOutPosition);
    Assert.AreEqual(10, c.LastQueuePosition);
    Assert.AreEqual(1, c.CurrentSeed);
}
```

這邊看起來 code 都不難寫，sample code 也都會動了，那麼我如何模擬實際大量使用者湧進來的排隊成效? 請繼續看下去\~

## 模擬與監控

其實，整個 POC 做下來，最難搞的是這一段… 中間大概整組砍掉重來三次以上了，現在的作法才比較滿意一點，感覺有真的模擬出我要的情境…。 這類服務或元件，不大好開發主要原因就是，正確性其實很好驗證 (單元測試有好好寫就八成穩了)，但是實際執行的表現很難掌握啊!

### 模擬: 使用者行為

先來看第一段 code:

```
static void LoadTestWorker(CheckoutLine engine, RateLimiter rate, bool display = false)
{
    Interlocked.Increment(ref _concurrent_thread);
    Interlocked.Increment(ref _started_thread);

    do {

        // 暖身
        Thread.Sleep(rnd.Next(10000));
        long item = 0;

#region 取號
        if (engine.TryGetToken(ref item) == false)
        {
            // 沒搶到號碼, 連排隊機會都沒有。直接踢掉
            if (display) Console.WriteLine($"#取號失敗");
            Interlocked.Increment(ref _no_entry_count);
            Thread.Sleep(rnd.Next(1000));
            continue;
        }
        if (display) Console.WriteLine($"#取號: {item}");
#endregion

#region 開始排隊
        try
        {
            Interlocked.Increment(ref _queuing_count);
            while (engine.CanCheckout(item) == false)
            {
                // 排隊中
                if (rnd.Next(1000) < _config_queue_fail_probility)
                {
                    if (display) Console.WriteLine($"#放棄排隊: {item}");
                    Interlocked.Increment(ref _abort_queue_count);
                    throw new Exception("giveup");
                }

                if (display) Console.WriteLine($"#蘿蔔蹲: {item} (等候順位: {item - engine.LastCheckOutPosition})");
                Thread.Sleep(rnd.Next(_config_queue_retry_period_ms)); // wait 30 sec and retry
            }
        }
        catch (Exception ex)
        {
            // skip
            if (display) Console.WriteLine($"#放棄排隊: {item} - exception {ex}");
            continue;
        }
        finally
        {
            Interlocked.Decrement(ref _queuing_count);
        }
#endregion            



#region 開始結帳
        if (rnd.Next(1000) < _config_checkout_fail_probility)
        {
            if (display) Console.WriteLine($"#放棄結帳: {item}");
            Interlocked.Increment(ref _abort_checkin_count);
            continue; // 每次確認時都有 10% 機率放棄結帳
        }


        if (display) Console.WriteLine($"#開始結帳: {item}");


        Interlocked.Increment(ref _checking_count);
        Thread.Sleep(rnd.Next(_config_check_process_period_ms)); // 結帳

        // 開始結帳那瞬間，就應該離開排隊隊伍了。接下來的管控交給 ratelimit
        engine.Remove(item);
        rate.AcquireRequestAsync().Wait();

        Interlocked.Decrement(ref _checking_count);
        Interlocked.Increment(ref _success_count);
        if (display) Console.WriteLine($"#結帳完畢: {item}");
#endregion

    } while(false);

    Interlocked.Decrement(ref _concurrent_thread);
}
```

老實說，寫模擬的 code 還蠻煩的… 哈哈，感覺就像看小學生用流水帳寫日記一樣。不過模擬本來就是流水帳… 只好盡量的表達出我要模擬的使用者行為了。這個 method 我想代表單獨一個使用者，開始取號排隊，到完成整個結帳流程為止。其中你看到一堆這種 code, 只是我在更新統計資訊而已:

```
Interlocked.Decrement(ref _concurrent_thread);
```

整段 code 分三大部分，分別是 \[取號]、\[排隊等待]、\[結帳] 三部分，我都用 region 來切段了。任何一段失敗 (例如沒取到號碼牌，不能排隊) 就直接離開了，整個 method 就執行結束，象徵流失的客戶就再也不回來了..

為了更貼近實際的狀況，每個段落我都用`Thread.Sleep()` 插入了不等(隨機)的延遲時間，模擬每個人的動作有快有慢的差距。同時，我也加入了固定機率，會有人不耐煩就不等了，直接離開隊伍的 code …

例如這段排隊中的 code:

```
// 排隊中
if (rnd.Next(1000) < _config_queue_fail_probility)
{
    if (display) Console.WriteLine($"#放棄排隊: {item}");
    Interlocked.Increment(ref _abort_queue_count);
    throw new Exception("giveup");
}
```

這段模擬的是，進入排隊狀態的使用者，會每隔一段時間重新呼叫 `CanCheckout()` 確定是否能進入店內用餐。不過每次詢問可能都會不耐煩，讓他興起放棄排隊的念頭。我模擬的是每次都有固定 1/1000 的機率會離開…

### 模擬: 發動人潮開始排隊

這段開始有點有趣了… 既然我都用 `LoadTestWorker()` 這個 method 封裝每個獨立的使用者完整的行為了，接下來我只要啟動一堆執行緒，就能模擬一堆使用者擠進店裡搶購的情境了! 看過我以前一堆文章的朋友應該不陌生，我研究過一堆掌控執行緒執行的技巧…

```
List<Thread> workers = new List<Thread>();
for(int i = 0; i < _config_total_workers; i++)
{
    Thread t = new Thread(() => {
        LoadTestWorker(engine, rate, false);
    });

    workers.Add(t);
    t.Priority = ThreadPriority.Lowest;

    // reverse proxy hardware rate limit
    SpinWait.SpinUntil(() => { return _concurrent_thread < _max_concurrent_thread; });
    t.Start();
}

foreach (var w in workers)
{
    w.Join();
}
```

這邊有段小插曲，其實這段 code 也很普通 (如果你熟悉 Thread 物件的操作的話)。唯獨一段 `SpinWait` 的部分，因為我的電腦資源有限，瞬間超過 3000 個執行緒同時執行時，這個模擬程式就會 `OutOfMemoryException` 了… 因此不得以設了一條限制，同時間不能超過 3000 個執行緒，否則就暫停緩一緩，先別啟動下一條執行緒。

你也許會問，這為何不用 `Semaphore` ? 不大一樣的是，我這邊控制的點是在 `Thread.Start()` 之前, 因為 `Start()` 後稍有不慎就沒記憶體了.. 而 `Semaphore` 比較適合的場景是好幾個 thread(s) 想要搶奪某些有限的資源，而這些資源同時只限有限個數的 threads 存取。這是 `Thread.Start()` 之後 (在 thread 內部)。想了想，我是為了程式順利執行下去才這樣做的，加上為了統計我本來就有 count, 因此簡單設個 `SpinWait` 就解決他了。

### 監控: Metrics

整個 POC 終於要到最後一步了 T\_T

這種模擬程式，一口氣就有幾千個使用者湧進來，要輸出訊息到畫面上其實也看不到什麼有用的資訊啊… 怎麼呈現結果也是個頭痛的問題。 我把場景拉回實際的系統，面對這麼多人在交易的系統，維運的團隊怎麼掌控狀況? 不外乎是從 dashboard, 監控各種數據的變化來得知。

好，問題來了，這些指標 (metrics) 從來沒有書本教我們該如何設計啊… 要是胡亂開個規格出來，我也不知道 developer 做不做的出來，或是做出來是否能夠真的發揮作用?

的確，這些問題不會有人給你答案的，尤其是你現在都還只停留在演算法驗證的階段而已。不過 code / load 都有 POC 了，metrics 這段也比照辦理吧! 就先憑你的經驗跟想像，先自己弄一版出來，用最快速最直接的方法，先產出一份監控數據的結果來驗證，然後不斷修正它 (修正定義，不是修正數字)。

我的作法是，我想要監控的 metrics, 我就先在模擬程式內自己計算統計，然後定期 (ex: 每 100ms) 把所有的 metrics 數值, 匯出一行 csv (文字檔)。模擬程式跑完了，這個 csv 也不用自己寫 code 處理，直接貼上 EXCEL，想像這是 cloud watch, 自己拉幾個你想看的圖表吧! 如果拉不出你想看的圖表 (我相信這瓶頸絕對不會是 EXCEL 太弱)，就可以回過頭來想想 metrics 是不是設計的不好? 是否應該新增其他的 metrics 才能順利地顯示我要的統計資訊?

我自己來回演練的過程就先省略了，我直接列幾個我想觀察的關鍵數據:

| # | metrics                 | description |
| - | ----------------------- | ----------- |
| 1 | \_queuing\_count        | 隊伍目前排隊中的人數  |
| 2 | \_checking\_count       | 隊伍目前結帳中的人數  |
| 3 | \_abort\_queue\_count   | 放棄排隊累積人數    |
| 4 | \_abort\_checkin\_count | 放棄結帳累積人數    |
| 5 | \_no\_entry\_count      | 無法排隊的累積人數   |
| 6 | \_success\_count        | 成功完成交易的人數   |

另外，加上隊伍的四個指標 (號碼機、結帳起點、排隊起點、排隊終點)，如果都納入這個 csv 匯出清單內，我就有個模擬過程的監控數據了。善用 EXCEL 可以讓我用最輕鬆的方式變成統計圖表。我完全可以靠一個人的人力，完成監控方式的 POC, 將來跟開發團隊溝通會容易的許多。

```
        static void MonitorWorker(CheckoutLine engine)
        {
            string logfile = $"output-{DateTime.Now:yyyyMMddHHmmss}-{_config_total_workers/1000}k.csv";

            File.WriteAllText(
                logfile,
                "SN,SEED,SINCE,UNTIL,LIMIT,ITEMS,CHECKIN,ORDER,ABORTCHECKIN,ABORTQUEUE,NOENTRY,THREAD\n");

            Stopwatch timer = new Stopwatch();
            timer.Restart();
            do
            {
                Thread.Sleep(300);

                Console.Clear();
                //Console.SetCursorPosition(0, 0);
                Console.WriteLine(engine);

                Console.WriteLine($"* 排隊中:       {_queuing_count}.   ");
                Console.WriteLine($"* 結帳中:       {_checking_count}.   ");
                Console.WriteLine($"--");
                Console.WriteLine($"* 成交單:       {_success_count}.   ");
                Console.WriteLine($"* 放棄結帳:     {_abort_checkin_count}.   ");
                Console.WriteLine($"* 放棄排隊:     {_abort_queue_count}.   ");
                Console.WriteLine($"* 無法排隊:     {_no_entry_count}.   ");
                Console.WriteLine($"--");
                Console.WriteLine($"* 執行緒:       {_concurrent_thread} / {_started_thread} / {_config_total_workers}.   ");

                File.AppendAllText(
                    logfile,
                    $"{timer.ElapsedMilliseconds},{engine.CurrentSeed},{engine.FirstCheckOutPosition},{engine.LastCheckOutPosition},{engine.LastQueuePosition},{_queuing_count},{_checking_count},{_success_count},{_abort_checkin_count},{_abort_queue_count},{_no_entry_count},{_concurrent_thread}\n");
            } while (_worker_stop_flag == false);
        }
```

看看實際的 code 吧! 比照 recycle\_worker 的做法，我也寫了 `MonitorWorker()`, 每隔固定時間就輸出一行 CSV 資料，按照格式把這些 metrics 資料匯出。同時為了方便執行過程觀察，我也稍做整理直接把這些資訊顯示在 console 上，想像一下這是 dashboard, 讓我可以看到即時數據的變化。

![img](https://columns.chicken-house.net/wp-content/images/2018-12-12-microservice11-lineup/console.gif)

來看看匯出的 CSV 能給我們什麼資訊?

![img](https://columns.chicken-house.net/wp-content/images/2018-12-12-microservice11-lineup/chart-01.jpg)

上圖我只打開兩筆數據: 排隊中(綠線) 與 結帳中(藍線) 兩筆數據，橫軸是時間軸，縱軸是數值(單位: 人)。可以看到結帳中的人數都維持在 400 \~ 480 之間跳動 (我設定的上限是 500), 可見一些隨機的因素，沒有辦法隨時都 100% 維持在最佳的效率上，不過這也是個不錯的指標，也許後續演算法能持續改善優化，我就能從這樣統計圖表比較，哪種做法的結帳人數能比現在這版更逼近理論值上限 500 ?

![img](https://columns.chicken-house.net/wp-content/images/2018-12-12-microservice11-lineup/chart-02.jpg)

再來看另一組數據，這次我把隊伍的四個指標都秀出來。號碼機(紅)，結帳起點(灰)，排隊起點(黃)，排隊終點(藍)… 想像一下，這四個數值隨著時間不斷的往右移，號碼機不斷地發出新的號碼牌。中間大部分的情況，號碼牌發放的位置都超過排隊起點，代表這家店都維持再客滿的狀態。值到後段號碼牌發放變慢了，逐步被黃線超越，這就代表店面內開始有座位空出來了。值到要結束營業為止，號碼牌跟結帳起點重疊了，代表所有領了牌子的客人都已經結帳完畢了，這家店這時已經沒有半個客人了。

其實這做法，對應到 DevOps 也好, Agile 也好, 甚至績效管理的理論也好, 其中都有一件事情是, 你要先能度量 (量化) 才能管理。這 POC 要產出 metric 數據就是第一步，有數據你才有 feedback。如果我的計算方式設計上就出了問題，我可以在 POC 階段就修正它。如果 POC 夠簡單 (只有兩三百行)，又沒有涉及太多 framework / language 等等因素，其實我有完全的能力可以處理啊! 不用等到 RD 都快寫完了才在線上調整… (通常 RD 很難 100% 掌握你的想法，然而線上的系統你沒辦法自己改，又得靠 RD 找出問題)。

## 結論

寫到這邊，快沒力了 XD，文章越寫越長這樣下去怎麼得了…

不過這邊帶出我一值想傳達的想法，包含如何善用 POC 盡早的用最少力氣確認整個架構? 這句話說來很簡單，但是除了我自己之外，我還真沒看到有別人用這種方式在初期驗證設計架構是否正確? 這是很可惜的一件事，很多理論 (Agile, Scrum, DevOps … etc) 講的都是真的，MVP 也是真的有用，但是難就難在沒人知道這個案子的 “MVP” 到底是什麼東西啊!

另一個我常常在講的，就是 DevOps, 很多人以為 Dev + Ops, 或是把 CI/CD pipeline 建立起來，做好 automation 就好了，這也是一大謬誤。我認為 DevOps 最核心的，就是 Dev + Ops, 你必須在開發階段，就思考你的服務是否能夠維運? 很多 Developer 也是搞不懂這點，所以系統上線了，完全不知道維運 (維運包含: 有效率的部署，有效率的監控)。監控有很多工具可以用，真正的困難點是你到底要監控什麼。我這邊的案例就是說明，先用最簡單的作法 (把草擬的 metrics 直接用 `Console.WriteLine()` 輸出 CSV, 直接貼到 EXCEL 看圖表)，在 POC 模擬階段就先確定你要看的 metrics 到底是那些，以我的例子，POC 做完，我等於也把 metrics 的定義都做完了。這階段不論是給 PO, Team member 等等，都有實際案例可以讓所有人充分了解這些設計。

花點時間寫 POC code, 效果遠勝於你寫一堆規格文件。在台灣對於大部分的團隊而言，做這件事最困難的就是… 負責規劃設計的人要有能力寫 code 啊… 即使是 POC 也好，寫得出 POC code 你專案執行的風險馬上呈指數下降。

很慶幸我是個還有能力寫 code 的架構師, 用的語言也跟團隊熟悉的 C# 一致, 才有機會分享這篇文章… 希望大家有耐心看完 XDD! 想跟我分享擔任架構師的任何經驗都很歡迎，請在底下或是我的 facebook 粉絲專頁留言給我 :)
