佇列是現代運算中極為實用的工具，在網頁應用程式中，經常被用來將一些可能比較耗時的運算延後執行。基本上，佇列讓我們能把一次運算拆成兩個時間點：排程的時間，以及實際執行的時間。「生產者」（producer）會把待執行的任務放進佇列，而「消費者」或「工作者」（consumer / worker）則會從佇列中取出任務來執行。舉例來說，當新使用者在網頁應用程式中完成註冊流程後，應用程式就會在佇列中新增一個任務，用來寄送包含啟用連結的電子郵件。至於實際寄送郵件的過程——包含遇到暫時性網路故障或其他錯誤時需要重試——就交由工作者來負責。

嚴格來說，我們可以把佇列視為一種行程間訊息傳遞的原語（primitive），其中接收端行程必須確認已收到訊息。訊息不能是發後即忘（fire-and-forget）的形式，因為佇列需要知道訊息是否可以從佇列中移除，所以某種形式的確認（acknowledgement）是絕對必要的。

當接收到訊息會觸發任務執行時——就像我們現在討論的這類佇列——確認收到訊息的時機點會改變佇列的語意。當工作者行程在處理訊息之前就確認收到訊息時，如果工作者隨後發生故障，訊息就有可能在任務根本還沒執行前就遺失了。如果確認是在訊息處理之後才送出，那麼一旦工作者故障或因為網路分割，佇列就可能會再次投遞同一則訊息。無論佇列的一致性屬性為何，這種情況都會發生，也就是說，即使佇列是建立在提供強一致性的系統之上，這種不確定性依然存在：

• 如果在處理之前就確認訊息，佇列將具有至多一次（at-most-once）投遞的特性。這表示訊息可能會被處理零次或一次。
• 如果在處理之後才確認訊息，佇列將具有至少一次（at-least-once）投遞的特性。這表示訊息可能會被處理一次到無限多次。

雖然這兩種情況都不完美，但在現實世界中，第二種行為通常更受青睞，因為要處理訊息被重複投遞（因而導致任務被重複執行）的情況，通常比處理系統偶爾完全不執行某個任務的情況要簡單得多。一個至少一次投遞系統的例子就是 Amazon SQS（Simple Queue Service）。

還有一個更根本的原因，讓至少一次投遞的系統更值得優先考慮，這與分散式系統有關：另一種語意（至多一次投遞）要求佇列必須具備強一致性：一旦訊息被確認，就不能再有其他工作者能確認同一則訊息，這是一個很強的保證。

一旦我們把焦點轉向至少一次投遞的系統，就會發現用 CP 系統來建模佇列其實是一種浪費，甚至是一種缺點：

• 無論如何，我們都無法保證比至少一次更好的投遞保證。
• 我們的佇列會失去在網路分割的少數分區（minority side）中繼續運作的能力。
• 由於一致性的要求，佇列需要達成共識，因此我們是在毫無正當理由的情況下浪費效能並增加延遲。

既然訊息可能會被投遞多次，從概念上來說，我們想要的是一個可交換的資料結構，以及一個最終一致的系統。訊息可以儲存在一個複製到 N 個節點的集合（set）資料結構中，其合併函式就是集合之間的聯集。由工作者在訊息執行完畢後送回的確認，在概念上也同樣是集合中的元素，用來標記某個元素已被處理。這是一個非常簡化的例子，對於實際系統來說並不特別實用，但它說明了某種特定的佇列如何能很好地由分散式系統的一組特性來建模。

實際上，我們的佇列還可以嘗試提供其他一些有用的特性：

• 在一段時間內保證只投遞給單一工作者：雖然允許多重投遞，但我們仍希望盡可能避免。
• 盡力而為地檢查，避免在訊息已經被處理過的情況下，於逾時後又重新投遞。同樣地，我們無法保證這個特性，但可以盡力減少重新發送那些其實已經處理過的訊息。
• 在正常運作期間，有足夠的內部狀態能以 FIFO 的方式處理訊息，讓先抵達的訊息先被處理。
• 自動清理內部資料結構。

除此之外，我們還需要在網路分割期間保留訊息，因此從概念上來說（即使實務上我們可能會使用不同的資料結構），待投遞的訊息集合就是所有節點上所有訊息的聯集。

遺憾的是，雖然已經有許多基於 Redis 的佇列實作，卻沒有任何一個嘗試利用 N 個獨立的 Redis 節點及其提供的原語，來作為建構具有上述特性的分散式系統的基礎。利用 Redis 的資料結構與效能，並搭配能提供特定有用保證的演算法，或許能打造出一個非常實用、易於管理與擴展，同時在每個節點上都能提供極佳效能（每秒訊息數）的佇列系統。

因為我覺得這個主題很有趣，而且這正是 Redis 的一個絕佳應用場景，所以我正在非常緩慢地為這樣一個基於 Redis 的佇列系統進行設計。如果時間允許，希望能在接下來的幾週內展示一些成果。