避免無法克服的佇列待處理項目

自從我在大學學習第一門電腦科學課程以來，我一直對演算法在現實世界中的表現很感興趣。當我們考慮現實世界中發生的某些事情時，我們可以提出模仿這些事情的演算法。當我在雜貨店、擁擠路上或機場排隊等候時，尤其會這樣做。我發現排隊時的無聊，對於思考佇列理論提供了很大的機會。

十多年前，我在 Amazon 配送中心工作過一天。透過演算法的引導，我從貨架上挑選物品，將物品從一個盒子搬到另一個，然後搬走箱子。與許多其他人同時工作時，我發現，成為本質上精心設計的實體合併分類的一部分自有其美感。

在佇列理論中，當佇列較短時，其行為相對無趣。畢竟，當佇列較短時，每個人都很高興。只有當佇列的待處理項目積壓，且佇列一直排到門口並拐個彎時，人們才開始思考輸送量和優先級。

在本文中，我將討論我們在 Amazon 用於處理佇列待處理項目場景的策略，我們採用的設計方法可快速耗盡隊列，並確定工作負載的優先級。我首先介紹如何防止佇列待處理項目，這一點十分重要。在上半部分，我描述了導致產生待處理項目的場景，在下半部分中，我將介紹 Amazon 在免待處理項目，或優雅地處理待辦項目時使用的許多方法。

為了在本文中闡述基於佇列的系統，我將介紹兩種 AWS 服務的幕後工作：AWS Lambda，這是一種執行代碼來回應事件的服務，無須擔心其執行的基礎架構；AWS IoT Core，這是一項託管服務，可讓聯網裝置輕鬆、安全地與雲端應用程式和其他裝置互動。

使用 AWS Lambda，您可以上傳函數代碼，然後叫用以下兩種方法之一：

• 同步：在 HTTP 回應時將函數的輸出返回給您
• 異步：在 HTTP 回應時立即返回，並且您的函數在後台執行並重試

Lambda 確保即使在伺服器發生故障時，也可以執行您的函數，因此 Lambda 需要耐用佇列來儲存請求。使用耐用佇列，若函數第一次失敗，可以重新驅動您的請求。

使用 AWS IoT Core，您的裝置和應用程式可以連線並訂閱 PubSub 訊息主題。當裝置或應用程式發佈訊息時，具有相符訂閱的應用程式會收到其自己的訊息副本。由於受限 IoT 裝置不想花費有限的資源，等待確保所有訂閱裝置、應用程式和系統均收到副本，因此大多數 PubSub 訊息傳遞都是異步發生。這一點尤其重要，因為當另一部裝置發佈其感興趣的訊息時，訂閱裝置可能處於離線狀態。離線裝置重新連線時，希望首先恢復速度，然後再接收向其傳遞的訊息 (如需重新連線後對系統編碼以管理訊息傳遞的相關資訊，請參閱《AWS IoT 開發人員指南》中的 MQTT 持續性工作階段)。為實現此目的，在後台進行了多種持續性和異步處理。

這類隊列型系統通常使用耐用佇列來實現。SQS 提供耐用、可擴展、至少一次的訊息傳遞語意，因此包括 Lambda 和 IoT 在內的 Amazon 團隊在建構可擴展異步系統時，都會定期使用。在基於佇列的系統中，一個元件透過將訊息放入佇列來產生資料，而另一個元件透過定期詢問訊息、處理訊息並在完成後最終將其刪除來使用資料。

在 AWS Lambda 中，若您的函數叫用比正常叫用慢 (例如，由於相依性關係)，或者若暫時失敗，不會遺失任何資料，並且 Lambda 會重試您的函數。Lambda 將您的叫用排入佇列，當函數再次開始工作時，Lambda 會完成函數的待處理項目。但是，我們考慮一下完成待處理項目，並恢復正常所需的時間。

想像一下，系統在處理訊息時經歷了一小時的中斷。無論給定速率和處理容量如何，從中斷復原，在復原後的另一小時需要系統容量增加一倍。實際上，該系統的可用容量可能會增加一倍以上，尤其是在使用 Lambda 等彈性服務時，復原速度可能會更快。另一方面，在您完成待處理項目時，函數與之互動的其他系統可能未做好大量處理的準備。發生此情況時，可能需要更長的時間才能趕上。與同步服務不同，異步服務會在中斷期間丟棄請求，但復原時間會更快，因此異步服務會在中斷期間積壓待處理項目，導致復原時間較長。

多年來，在考慮佇列時，我們有時傾向於認為延遲對於異步系統並不重要。異步系統通常專為耐用性而建構，或者為了將直接叫用者與延遲隔離開來。但實際上，我們已經看到處理時間確實很重要，而且通常異步系統有望實現亞秒級或更短的延遲。當引入佇列來提高耐用性時，很容易錯過折衷方案，這會在面對待處理項目時，導致極高的處理延遲。異步系統的隱藏風險在於處理大量待處理項目。

關於權衡延遲問題的討論，提出了一個有趣的問題：我們如何針對異步服務的延遲和可用性來量測和設定目標？ 從生產者的角度量測錯誤率，可以讓我們了解可用性的一部分情況，但並不是很多。生產者可用性與我們所用系統的佇列可用性成正比。因此，當我們基於 SQS 建構時，生產者可用性與 SQS 可用性相符。

另一方面，若我們量測取用者端的可用性，則可能會讓系統可用性看起來比實際情況更糟，因為可能會重試故障，然後在下一次嘗試中成功。

我們還從無法寄出信件佇列 (DLQ) 獲得可用性指標。若訊息用盡了重試時間，則將其丟棄或放入 DLQ 中。DLQ 只是一個單獨的佇列，用於儲存無法進行後續調查和乾預的訊息。丟棄率或 DLQ 訊息是一個很好的可用性量測值，但可能發現問題為時已晚。雖然設定 DLQ 數量警示是個好主意，但 DLQ 資訊對於我們來說太遲，無法完全依靠其來偵測問題。

延遲呢？ 同樣，生產者觀測到的延遲反映了我們佇列服務本身的延遲。因此，我們更多地專注於量測佇列中訊息的使用期限。這樣一來，可以迅速發現系統落後，或經常出錯並導致重試的情況。SQS 之類的服務提供每則訊息到達佇列的時間戳記。藉助時間戳記資訊，每當我們從佇列中處理一則訊息時，就能記錄並產生有關系統落後程度的指標。

延遲問題可能會更加細微。畢竟，待處理項目可以預期，而實際上對於某些訊息也可以。例如，在 AWS IoT 中，裝置有時可能會離線或讀取訊息的速度較慢。這是因為許多物聯網裝置效能低下，並且網際網路連線品質不一。作為 AWS IoT Core 的營運商，我們需要能夠區分，因裝置離線或選擇緩慢讀取訊息導致的預期較少待處理項目，與整個系統出現非預期待處理項目的差異。

在 AWS IoT 中，我們使用另一項指標來量測服務︰AgeOfFirstAttempt。現在用此量測記錄減去訊息排入佇列的時間，但前提是，這是 AWS IoT 首次嘗試將訊息傳遞至裝置。這樣，在裝置設備時，我們得到了一個乾淨的指標，不會因裝置重試訊息或排入佇列而受到干擾。為了使指標更加清晰，我們發出了第二項指標 – AgeOfFirstSubscriberFirstAttempt。在 AWS IoT 這類 PubSub 系統中，對於可訂閱特定主題的裝置或應用程式數目沒有實際限制，因此，將訊息傳送至一百萬個裝置的延遲比傳送至單一裝置的延遲高。為提供一個穩定的指標，我們在首次嘗試向該主題第一位訂閱者發佈訊息時，發出計時器指標。我們還有其他量測指標，可用於量測發佈剩餘訊息時系統的進度。

AgeOfFirstAttempt 指標可作為全系統問題的早期預警，很大程度上是因為，其可過濾掉那些選擇更慢讀取訊息裝置的雜訊。值得一提的是，AWS IoT 這類系統配備了更多指標。但在所有延遲相關指標均可用的情況下，Amazon 通常使用將首次嘗試延遲與重試嘗試延遲分開的分類策略。

量測異步系統的延遲和可用性極具挑戰性，並且偵錯也很棘手，因為請求在伺服器之間彈跳，並且可能在每個系統之外的地方延遲。為協助進行分散式追蹤，我們在佇列訊息中傳播一個請求 ID，以便將其組合在一起。我們通常也使用 X-Ray 之類的系統來協助解決此問題。

許多異步系統都為多租用戶，代表許多不同的客戶來處理工作。這增加了管理延遲和可用性的複雜維度。多租用戶的優點在於，它節省了我們不得不分別操作多個機群的營運開銷，並且讓我們能以更高的資源利用率，來執行組合的工作負載。然而，客戶期望其行為像他們自己的單租用戶系統一樣，具有可預期的延遲和高可用性，而與其他客戶的工作負載無關。

AWS 服務不會直接公開其內部佇列，以讓叫用者放入訊息。取而代之的是，實作輕量級 API 來驗證叫用者，並在排入佇列之前，將叫用者資訊附加至每則訊息。這類似於之前描述的 Lambda 架構：當您異步叫用函數時，Lambda 會將訊息放入 Lambda 擁有的佇列中並立即返回，而非直接將 Lambda 的內部佇列公開給您。

這些輕量級 API 還讓我們能夠新增公平調節。多租用戶系統中的公平性很重要，因此任何客戶的工作負載都不會影響其他客戶。AWS 實作公平性的一種常見方式是，設定基於每位客戶的費率限制，並具有一定的突發靈活性。在我們的許多系統中，例如 SQS 本身，隨著客戶自然增長，我們會增加每位客戶的限制。這些限制充當非預期尖峰的護欄，讓我們有時間在幕後進行佈建調整。

在某些方面，異步系統中的公平性就像同步系統中的調節一樣。然而，我們認為思考異步系統中的情況更為重要，因為待處理項目的積壓可能會非常迅速。

為說明這一點，請考慮若異步系統內建雜訊鄰居保護不足，會發生什麼情況。若系統的一位客戶突然增加流量卻沒有調節，並產生了全系統待處理項目，則可能需要 30 分鐘左右的時間，操作人員才會介入，了解發生的情況並緩解問題。在那 30 分鐘期間，系統的生產方可能擴展良好，並將所有訊息排入佇列。但是，若佇列中訊息的數量是取用者端擴展容量的 10 倍，這意味著系統需要 300 分鐘，才能完成待處理項目並復原。即使較短的負載尖峰也可能導致數小時的復原時間，從而引起數小時的中斷。

實際上，AWS 中的系統具有眾多補償因素，可以最大程度地減少或防止佇列待處理項目帶來的負面影響。例如，自動擴展有助於減輕負載增加時的問題。但是，僅考慮佇列影響而不考慮補償因素會有所幫助，因為這有助於設計可靠的多層系統。 我們發現，一些設計模式有助於避免大量的佇列待處理項目，以及較長的復原時間：

• 在異步系統中，每一層保護都很重要。 由於同步系統往往不會積壓待處理項目，因此我們透過前門調節和准入控制來對其進行保護。在異步系統中，系統的每個元件都需要保護自身免受過載影響，並防止一個工作負載消耗不公平的資源份額。前門准入控制總是存在一些工作負載，因此我們需要帶式、吊帶式和口袋式保護裝置來防止過載。
• 使用多個佇列有助於調整流量。 在某些方面，單一隊列和多租用戶彼此矛盾。當工作在共用佇列中排入佇列時，很難將一個工作負載與另一個隔離開。
• 即時系統通常使用 FIFO 佇列來實現，但更偏好 LIFO 類似行為。 我們從客戶那裡得知，面對待處理項目時，他們希望立即處理其新資料。當容量可用時，中斷或爆衝期間積累的任何資料都可以進行處理。

Amazon 系統採用多種模式，能讓其多租用戶異步系統適應工作負載的變化。採用的技術很多，但整個 Amazon 使用的系統也很多，每種系統都有其自身的活躍度和耐用性要求。在下文中，我將介紹一些我們使用的模式，以及 AWS 客戶告訴我們他們在系統中使用的模式。

在某些系統中，我們不是與所有客戶共用一個佇列，而是讓每位客戶有其自己的佇列。為每位客戶或工作負載新增佇列並非總是具有成本效益，因為服務將需要花費資源來輪詢所有佇列。但在包含少量客戶或相鄰系統的系統中，這種簡單的解決方案很有用。另一方面，如果系統有甚至成千上萬個客戶，則單獨的佇列可能開始變得笨拙。例如，AWS IoT 不會對 Universe 中的每部物聯網裝置使用單獨的佇列。在這種情況下，輪詢成本無法很好地擴展。

AWS Lambda 是系統以下情況的一個範例，其中每位 Lambda 客戶輪詢一個單獨的佇列會非常昂貴。然而，只有一個佇列可能會導致本文中所述的某些問題。因此，AWS Lambda 不會使用一個佇列，而是佈建固定數目的佇列，並將每位客戶散列至少量佇列。在將訊息排入佇列之前，其將檢查以查看哪些目標佇列中包含最少訊息，然後將其排入佇列。當一位客戶的工作負載增加時，它將在其對應佇列中引發待處理項目，但其他工作負載將自動從這些佇列中路由出去。建立一些神奇的資源隔離並不需要大量的佇列。這只是 Lambda 內建諸多保護措施之一，但這項技術也已在 Amazon 的其他服務中使用。

在某些方面，當佇列中積壓了待處理項目時，對流量排列優先順序為時已晚。但是，若處理訊息相對昂貴或費時，則仍然值得將訊息移至單獨的溢出佇列。在 Amazon 的某些系統中，取用者服務實作分散式調節，當他們為已超過設定速率的客戶清除訊息佇列時，他們會將那些多餘的訊息放入單獨的溢出佇列，並從主佇列中刪除訊息。只要有可用的資源，系統仍會處理溢出佇列中的訊息。本質上，這與優先佇列相近。生產者端有時會實作類似邏輯。這樣一來，若系統接受來自單一工作負載的大量請求，則該工作負載不會擠占熱路徑佇列中的其他工作負載。

與擱置處理多餘的流量類似，我們也可以擱置處理舊的流量。當我們清除訊息佇列時，我們可以查看其存在時間。我們可以利用該資訊來決定是否將訊息移入待處理項目佇列，而不僅僅是將存在時間記錄下來，只有當我們趕上即時佇列後才可以進行處理。若存在負載尖峰，需要擷取大量資料，而我們落後了，則可以將流量的波峰擱置於另一個佇列處理，這樣我們就可以清除流量佇列，並重新排入佇列。相較於僅按順序處理待處理項目，這可以釋放取用者資源，使其更快地處理新訊息。這是一種近似 LIFO 排序的方法。

某些系統可以容忍被丟棄的非常舊的訊息。例如，某些系統快速處理系統的增量，但也會定期進行完全同步。我們經常稱這些週期性同步系統為反熵清理工具。在這些情況下，若它是在最近一次掃描之前進入的話，我們可以實惠地將其丟棄，而不是讓舊的佇列流量擱置處理。

與我們的同步服務非常相似，我們設計異步系統的目的是，防止一個工作負載使用超出其合理份額的執行緒。我們尚未討論的 AWS IoT 其中一方面是規則引擎。客戶可以設定 AWS IoT，以將訊息從其裝置路由至客戶擁有的 Amazon Elasticsearch 叢集、Kinesis Stream 等。若那些客戶擁有的資源延遲變慢，但傳入訊息速率保持恆定，則系統中的並行量會增加。而且，由於系統可以隨時處理的並行量受到限制，因此規則引擎可以防止任何一個工作負載消耗的資源，超過其與並行相關資源的合理份額。

利特爾法則描述了工作的力量，該法則指出系統中的並行等於到達率乘以每個請求的平均延遲。例如，若伺服器以平均 100 毫秒的速度，每秒處理 100 則訊息，則平均將消耗 10 個執行緒。若延遲突然增加至 10 秒，則會突然使用 1,000 個執行緒 (平均而言，因此實際上可能更多)，這很容易耗盡執行緒集區。

規則引擎使用多種技術來防止這種情況發生。它使用非封鎖 I/O 來避免執行緒耗盡，儘管給定伺服器的工作量還有其他限制 (例如，用戶端流失連線且相依性逾時情況下的記憶體和檔案描述元)。可以使用的第二項並行防護是信號，它可量測和限制可在任何時間瞬間用於任何單一工作負載的並行量。規則引擎還使用基於速率的公平性限制。然而，由於工作負載隨時間變化是完全正常的，因此規則引擎還會自動調整隨時間變化的限制，以適應工作負載的變化。而且由於規則引擎基於佇列，因此它充當了物聯網裝置與幕後資源和安全限制自動擴展之間的緩衝。

在 Amazon 的所有服務中，我們為每個工作負載使用單獨的執行緒集區，以避免一個工作負載消耗所有可用執行緒。我們還針對每個工作負載，使用 AtomicInteger 來限制每個工作負載的允許並行，以及使用基於速率的調節方法來隔離基於速率的資源。

若工作負載造成取用者無法跟上處理進度的不合理待處理項目，我們的許多系統會自動開始更積極地拒絕生產者中的工作。工作負載很容易積壓一整天的待處理項目。即使隔離了該工作負載，也可能是偶然的，並且流失花費昂貴。這種方法的實作可能像偶爾量測工作負載的佇列深度一樣簡單 (假設工作負載在其自己的隊列中)，然後根據待處理項目大小，按比例調整對內調節大小限制 (相反)。

在我們針對多個工作負載共用一個 SQS 佇列的情況下，這種方法變得棘手。雖然有一個 SQS API 返回佇列中訊息數目，但沒有 API 可以返回具有特定屬性的佇列中訊息數目。我們仍然可以量測佇列深度，並相應地施加背壓，但這會不公平地對恰好共用同一佇列的無辜工作負載施加背壓。其他系統，如 Amazon MQ，具有更細粒度的待處理項目可視性。

背壓不適用於 Amazon 上的所有系統。例如，在為 amazon.com 執行訂單處理的系統中，即使待處理項目積壓，我們仍傾向於接受訂單，而非阻止新訂單被接受。但是，當然這伴隨著幕後的許多優先事項，以便最先處理最緊急的訂單。

當系統感覺到需要減少特定工作負載的輸送量時，我們嘗試對該工作負載使用停止策略。為實作這一點，我們經常使用 SQS 功能，該功能可延遲到以後傳遞訊息。當我們處理一則訊息，並決定將其儲存以備後用時，有時會將該訊息重新排入佇列至單獨的爆衝佇列中，但會設定延遲參數，以便該訊息在延遲佇列中保持隱藏狀態幾分鐘。這樣，系統就有機會處理更新的資料。

某些 SQS 之類的佇列服務，對於可向佇列取用者傳遞的傳遞中訊息量有限制。這與佇列中可能存在的訊息數目 (沒有實際限制) 不同，而是取用者機群立即處理的訊息數目。若系統清除訊息佇列，則可以增加該數目，但隨後無法將其刪除。例如，我們已經看到一些錯誤，這些錯誤使得代碼在處理訊息時無法擷取異常，並忘記刪除訊息。在這些情況下，對於訊息的可視性逾時，從 SQS 角度來看，訊息仍在傳遞中。在設計錯誤處理和重載策略時，請牢記這些限制，並傾向於將多餘的訊息移至其他隊列，而不是讓其保持可視狀態。

SQS FIFO 佇列具有相似但細微的限制。使用 SQS FIFO，系統按給定訊息群組順序處理訊息，但不同群組的訊息按任何順序處理。因此，若在一個訊息群組中產生少量待處理項目，會繼續處理其他群組中的訊息。然而，SQS FIFO 僅輪詢最近未處理的 20000 則訊息。因此，若訊息群組的子集中有超過 20000 則未處理訊息，則其他包含新訊息的訊息群組將被耗盡。

無法處理的訊息會導致系統過載。若系統將無法處理的訊息排入佇列 (可能是因為其觸發輸入驗證邊緣情況)，則 SQS 可以透過將這些訊息自動移至具有無法寄出信件佇列 (DLQ) 功能的單獨佇列來提供協助。若此佇列中有任何訊息，我們會發出警示，因為這意味著我們有一個錯誤需要修復。DLQ 的優勢是，它讓我們能夠在錯誤修復後重新處理訊息。

若工作負載將足夠的輸送量驅動至以下狀態點，即使穩態期間，輪詢執行緒都始終終處於繁忙狀態，則系統可能已經達到沒有緩衝區來吸收流量爆衝的狀態點。在這種狀態下，傳入流量的小幅尖峰將導致持續的未處理待處理項目量，從而導致更高的延遲。我們計劃在輪詢執行緒中增加緩衝區，以吸收此類高載。一種量測是，追蹤導致空回應的輪詢嘗試次數。若每次輪詢嘗試都將擷取一則訊息，則要么輪詢執行緒數目正好合適，要么可能不足以跟上傳入流量。

當系統處理 SQS 訊息時，SQS 會在假設系統崩潰之前，讓系統有一定的時間來完成對訊息的處理，然後將訊息傳遞給另一個取用者再試一次。若代碼持續執行且忘記此期限，則可以平行多次傳送相同的訊息。當第一個處理器在其逾時後仍在處理訊息時，第二個處理器將撿拾該訊息，同樣在逾時後逐漸流失，然後是第三個，依此類推。這種潛在的串聯管制是我們實作訊息處理邏輯的原因所在，以便在訊息到期時停止工作，或者繼續對訊息進行活動訊號檢查，以提醒 SQS 我們仍在努力處理。此概念類似於領導人選舉中的任期。

這是一個隱患，因為我們發現，系統的延遲可能會在過載期間增加，這可能是因為查詢資料庫所花費的時間更長，或者伺服器僅承擔了超出其處理能力的工作。當系統延遲超過該 VisibilityTimeout 閾值時，其將導致已經超載的服務本質上成為 fork 炸彈本身。

了解分散式系統中的故障已經困難重重。關於檢測的相關文章介紹了我們檢測異步系統的幾種方法，從定期記錄佇列深度，到傳播「追蹤 ID」，以及整合 X-Ray。或者，當我們的系統具有超出一般 SQS 佇列的複雜異步工作流程時，我們通常使用 Step Functions 之類的其他異步工作流程服務，該服務可提供工作流程可視性，以及簡化分散式偵錯。

在異步系統中，很容易忘記考慮延遲的重要性。畢竟，異步系統應偶爾會花費更長時間，因為它們前面有正在執行可靠重試的佇列。然而，過載和故障方案可能會積壓大量無法解決的待處理項目，這導致服務無法在合理的時間內復原。這些待處理項目可能源自一個工作負載，或客戶以非預期的高速率排入佇列，源自變得比預期處理更昂貴的工作負載，或者源自延遲或相依性故障。

在建構異步系統時，我們需要關注並預測這些待處理項目情況，並使用排列優先順序，擱置處理和背壓之類的技術盡可能將其減少。

• 佇列理論
• 利特爾法則
• 阿姆達爾定律
• Little A Proof for the Queuing Formula: L = λW, Case Western, 1961
• McKenney, Stochastic Fairness Queuing, IBM, 1990
• Nichols and Jacobson, Controlling Queue Delay, PARC, 2011