隊列系統(tǒng)是微服務(wù)系統(tǒng)的核心組件之一，本文介紹了Netflix內(nèi)部構(gòu)建的高吞吐量、低優(yōu)先級隊列系統(tǒng)。原文: Timestone: Netflix’s High-Throughput, Low-Latency Priority Queueing System with Built-in Support for Non-Parallelizable Workloads
簡介
Timestone是Netflix內(nèi)部構(gòu)建的高吞吐、低延遲優(yōu)先級隊列系統(tǒng)，以支持Netflix媒體編碼平臺Cosmos的需求。在過去的2年半的時間里，Timestone的使用量一直在增加，現(xiàn)在還成為了Netflix通用工作流編排引擎Conductor的優(yōu)先級隊列引擎，以及用于大規(guī)模數(shù)據(jù)流水線的調(diào)度器(BDP Scheduler)?？偠灾?，Netflix內(nèi)部數(shù)百萬個關(guān)鍵工作流現(xiàn)在都要通過Timestone處理。
Timestone客戶端可以創(chuàng)建隊列，基于用戶定義的截止日期和元數(shù)據(jù)對消息進行排隊，然后以最早截止日期優(yōu)先(EDF, earliest-deadline-first)的方式對消息進行出隊處理，還支持通過條件(例如"屬于隊列X且具有元數(shù)據(jù)Y的消息")篩選EDF消息。
Timestone與其他優(yōu)先級隊列的不同之處在于，它支持一種稱為獨占隊列(exclusive queues) 的結(jié)構(gòu)，這是一種將工作塊標記為不可并行的方法，不需要在消費者端進行任何鎖定或協(xié)調(diào)，所有事情都由后臺獨占隊列處理。我們將在接下來的小節(jié)中詳細解釋這個概念。
為什么用Timestone
當我們在2018年設(shè)計Reloaded(Netflix的媒體編碼系統(tǒng))的后繼系統(tǒng)時(參見Netflix Cosmos Platform一文的"背景"部分)，需要一個優(yōu)先隊列系統(tǒng)，用于在Cosmos的三個組件之間提供隊列(圖1):
- API框架(Optimus)
- 正向鏈式規(guī)則引擎(Plato)
- 無服務(wù)器計算層(Stratum)
這個優(yōu)先級隊列系統(tǒng)需要滿足的一些關(guān)鍵需求:
在任何給定時間內(nèi)，一條消息只能分配給一個處理節(jié)點。在Cosmos中發(fā)生的工作往往是資源密集型的，并且可以觸發(fā)數(shù)以千計的動作。假設(shè)數(shù)據(jù)存儲副本之間存在復(fù)制延遲，剛剛由工作者A通過另一個節(jié)點從隊列中取出的消息也會被顯示為工作者B可取出的消息，這種情況會浪費大量計算周期。這一需求最終將一致的解決方案排除在外，意味著我們希望在隊列級別上實現(xiàn)線性一致性(linearizable consistency)。
允許非并行工作。
假設(shè)(Given) Plato不斷輪詢所有工作流隊列，以便執(zhí)行更多的工作;
當(While) Plato為給定項目執(zhí)行工作流(或者說處理給定服務(wù)的工作請求)時;
那么(Then) Plato就不能在該工作流上為該項目的工作處理額外的請求。否則，Plato推理引擎將過早評估工作流，并可能將工作流遷移到不正確的狀態(tài)。
因此，在Cosmos中存在某種不應(yīng)該并行的工作，要求隊列系統(tǒng)本身支持這種類型的訪問模式，這一要求催生了獨占隊列的概念，我們將在"關(guān)鍵概念"部分解釋獨占隊列在Timestone中的工作原理。
允許使用過濾器(元數(shù)據(jù)鍵-值對)退出消息以及隊列深度查詢
允許在接收消息時自動創(chuàng)建隊列
消息在進入隊列一秒內(nèi)可以標記為可退出
我們之所以創(chuàng)建Timestone，是因為無法找到滿足這些需求的現(xiàn)成解決方案。
系統(tǒng)架構(gòu)
Timestone是基于gRPC的服務(wù)，通過protocol buffers定義服務(wù)接口以及請求、響應(yīng)消息結(jié)構(gòu)。應(yīng)用程序的系統(tǒng)關(guān)系圖如圖2所示。
記錄系統(tǒng)(System of record)
記錄系統(tǒng)是一個持久化Redis集群。到達集群(步驟2)的每個寫請求(參見步驟1，注意該步驟改變了隊列狀態(tài)，包括了出隊列請求)在響應(yīng)發(fā)送回服務(wù)器(步驟3)之前被持久化到事務(wù)日志中。
在數(shù)據(jù)庫內(nèi)部，我們用排序集(sorted set)來表示每個隊列，根據(jù)優(yōu)先級對消息id進行排序(參見"消息"一節(jié))。我們將消息和隊列配置(參見“隊列”一節(jié))作為哈希保存在Redis中。所有與隊列相關(guān)的數(shù)據(jù)結(jié)構(gòu)(從它包含的消息到支持按篩選器出隊列所需的內(nèi)存二級索引)都放在同一個Redis分片中，通過共享一個特定于相關(guān)隊列的公共前綴來實現(xiàn)這一點。然后我們將這個前綴編碼為Redis哈希標簽(hash tag)。每條消息攜帶一個最大32KB的內(nèi)容(參見"消息"一節(jié))。
Timestone和Redis之間的幾乎所有交互(參見"消息狀態(tài)"一節(jié))都被編寫為Lua腳本。大多數(shù)Lua腳本中，我們傾向于更新大量數(shù)據(jù)結(jié)構(gòu)。由于Redis保證每個腳本都是原子執(zhí)行的，腳本成功執(zhí)行可以保證系統(tǒng)處于一致(在ACID意義上)狀態(tài)。
所有API操作都以隊列為作用域，所有修改狀態(tài)的API操作都是冪等的。
二級索引(Secondary indexes)
出于可觀察性的目的，我們在Elasticsearch中維護的兩個二級索引中維護傳入消息及其狀態(tài)之間轉(zhuǎn)換的信息。當我們從Redis得到寫響應(yīng)時，同時(a)將這個響應(yīng)返回給客戶端，(b)將這個響應(yīng)轉(zhuǎn)換為發(fā)布到Kafka集群的事件，如步驟4所示。兩個Flink作業(yè)(維護的每一種類型的索引都有一個)消費對應(yīng)Kafka主題的事件，并更新Elasticsearch中的索引。
一個索引("current")為用戶提供系統(tǒng)當前狀態(tài)的最佳視圖，而另一個索引("historic")為用戶提供消息的最佳縱向視圖，從而允許流經(jīng)Timestone時跟蹤消息，并回答諸如在某個狀態(tài)中花費的時間和處理錯誤的數(shù)量等問題。我們?yōu)槊織l消息維護一個版本計數(shù)器，每次寫操作都觸發(fā)計數(shù)器遞增，通過版本計數(shù)器對歷史索引中的事件進行排序。事件在Elasticsearch集群保存特定時間。
當前在Netflix中的使用情況
系統(tǒng)出隊列的負載很重，每秒有30K的出隊列請求(RPS)， P99延遲為45ms。相比之下，入隊列請求是每秒1.2K和P99延遲是25ms。此外經(jīng)常能看到5K RPS的入隊列突發(fā)流量，P99延遲會增加到85ms。自今年初以來，有150億(15B)消息在Timestone里排隊，出隊列4000億(400B)次，待處理消息通常達到1000萬(10M)條。隨著我們將Reloaded(遺留媒體編碼系統(tǒng))的其余部分遷移到Cosmos，使用量預(yù)計將在明年(2023年)翻一番。
核心概念
消息(Message)
消息攜帶非透明有效負載(payload) 、用戶定義優(yōu)先級(參見"優(yōu)先級"一節(jié))、一組可選的(對于獨占隊列是必選的)元數(shù)據(jù)鍵-值對(set of metadata key-value pairs) ，可用于基于過濾器的出隊，以及可選的不可見持續(xù)時間(invisibility duration) 。放入隊列中的任何消息都可以從隊列中取出有限次數(shù)，我們稱之為嘗試(attempts) ，消息的每一次出隊列調(diào)用都會減少嘗試次數(shù)。
優(yōu)先級(Priority)
消息的優(yōu)先級表示為整數(shù)值，該值越低，優(yōu)先級越高。雖然應(yīng)用程序可以自由使用它們認為合適的取值范圍，但標準是使用以毫秒為單位的Unix時間戳(例如，1661990400000表示UTC時間9/1/2022午夜)。
也完全可以由應(yīng)用程序自己定義優(yōu)先級級別。例如，Cosmos中的流編碼流水線使用郵件優(yōu)先級類，如圖3所示。屬于標準類的消息使用入隊時間作為其優(yōu)先級，而所有其他類的優(yōu)先級值按10年的倍數(shù)調(diào)整。優(yōu)先級是在工作流規(guī)則級別設(shè)置的，但是如果請求帶有studio標記(例如DAY_OF_BROADCAST)，則可以被重寫。
消息狀態(tài)(Message States)
隊列中的Timestone消息處于以下六種狀態(tài)之一(圖4):
- invisible (不可見)
- pending (待處理)
- running (處理中)
- completed (已完成)
- canceled (已取消)
- errored (已出錯)
通常來說，消息可以以不可見(invisible) 或待處理(pending) 的方式進入隊列，對應(yīng)消息處于不可見(invisible) 或待處理(pending) 狀態(tài)。當不可見窗口(invisibility window)消失時，不可見消息將變?yōu)榇幚頎顟B(tài)。工作節(jié)點可以通過指定處理該消息的時間(租期)從隊列中將待處理的最早截止日期優(yōu)先的消息出隊列，還支持批量消息出隊列，從而將消息切換到處理中(running) 狀態(tài)。然后，同一工作節(jié)點可以在分配的租約窗口內(nèi)發(fā)出對Timestone的完成調(diào)用，以將消息遷移到已完成(completed) 狀態(tài)，或者如果希望保持對消息的控制，則發(fā)出租約展期調(diào)用。(工作節(jié)點還可以將通常處于處理中的消息遷移到已取消狀態(tài)，表示不再需要處理該消息。)如果這些調(diào)用都沒有按時發(fā)出，消息將再次變?yōu)榭沙鲫牭模瑢ο⒌倪@次嘗試將結(jié)束。如果消息沒有任何可用的嘗試次數(shù)，將被自動遷移到已出錯(errored) 狀態(tài)。終止狀態(tài)(terminal states) (已完成、已錯誤和已取消)由后臺進程定期進行垃圾回收。
消息可以在工作節(jié)點調(diào)用API時遷移狀態(tài)，也可以在Timestone運行后臺進程時遷移狀態(tài)(圖4，標為紅色，定期運行)，圖4顯示了完整的狀態(tài)轉(zhuǎn)換圖。
隊列(Queues)
所有傳入的消息都存儲在隊列中，按其優(yōu)先級日期排序。Timestone可以托管任意數(shù)量用戶創(chuàng)建的隊列，并提供一組用于隊列管理的API，所有操作都圍繞某個隊列配置對象進行。存儲在這個對象中的數(shù)據(jù)包括隊列類型(參見其余部分)、應(yīng)用于出隊消息的租期或應(yīng)用于出隊消息的不可見持續(xù)時間、消息可以出隊的次數(shù)，以及是否暫時阻止入隊或出隊。注意，消息生產(chǎn)者可以通過在入隊期間在消息級別設(shè)置默認租期或不可見持續(xù)時間來覆蓋對應(yīng)配置。
Timestone中的隊列分為兩種類型: 簡單隊列(simple) 和獨占隊列(exclusive) 。
創(chuàng)建獨占隊列(exclusive queue) 時，需要與用戶定義的獨占鍵(exclusivity key) (例如project)相關(guān)聯(lián)。所有發(fā)布到該隊列的消息都必須在其元數(shù)據(jù)中攜帶此鍵。例如，帶有project=foo的消息將被隊列接受，沒有project鍵的消息將不會被接受。本例中，我們調(diào)用與獨占鍵對應(yīng)的值foo，即消息的獨占值(exclusivity value) 。獨占隊列的約定是，在任何時間點，每個獨占值最多只能有一個消費者。因此，如果示例中的基于project的獨占隊列中有兩個消息，其中的鍵值對是project=foo，并且其中一個消息已經(jīng)被一個工作節(jié)點獲取，那么另一個消息是不可出隊的。如圖5所示。
在簡單隊列中不會應(yīng)用這種契約，也不與消息元數(shù)據(jù)鍵緊密耦合。簡單隊列可以作為典型優(yōu)先級隊列，簡單的以最早截止日期優(yōu)先的方式對消息進行排序。
我們在做什么
我們正在做的一些工作:
- 隨著Timestone在Cosmos中使用量的增加，支持一系列隊列深度查詢的需求也在增加。為了解決這個問題，我們正在構(gòu)建使用不同查詢模型的專用查詢服務(wù)。
- 如上所述(見"記錄系統(tǒng)"一節(jié))，一個隊列及其內(nèi)容目前只能占用一個Redis分片。然而，熱隊列可能會越來越大(特別是當計算能力不足時)。我們希望支持任意大的隊列，因此促使我們構(gòu)建了對隊列分片的支持。
- 消息最多可以攜帶4個鍵值對，目前所有這些鍵值對都會用來填充按篩選器出隊過程中使用的二級索引。這個運算在時間和空間上都是指數(shù)級復(fù)雜度的(
)。我們正在將已排序集合切換到字典排序，以減少一半索引量，并以一種更具成本效益的方式處理元數(shù)據(jù)。
你好，我是俞凡，在Motorola做過研發(fā)，現(xiàn)在在Mavenir做技術(shù)工作，對通信、網(wǎng)絡(luò)、后端架構(gòu)、云原生、DevOps、CICD、區(qū)塊鏈、AI等技術(shù)始終保持著濃厚的興趣，平時喜歡閱讀、思考，相信持續(xù)學(xué)習(xí)、終身成長，歡迎一起交流學(xué)習(xí)。
微信公眾號：DeepNoMind
