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

嚴格來說，我們可以將佇列視為一種 inter-process messaging primitive(行程間訊息傳遞原語)，其中接收行程需要確認訊息的接收。訊息不能採用 fire-and-forget(發後即忘) 的形式，因為佇列需要知道訊息是否可以從佇列中移除，因此某種形式的 acknowledgement(確認) 是絕對必要的。

當接收到訊息會觸發任務的執行時——就像我們所討論的這類佇列一樣——訊息接收被確認的時機點會改變佇列的語意。當 worker 行程在處理訊息之前就確認接收該訊息時，若 worker 發生故障，訊息可能會在任務尚未執行前就遺失。如果確認僅在訊息處理之後才發送，若 worker 故障或因發生 network partition(網路分割)，佇列可能會再次重新投遞該訊息。無論佇列的一致性屬性為何，這種情況都會發生，因此，即使佇列是透過提供 strong consistency(強一致性) 的系統來建模，這種不確定性依然存在：

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

雖然這兩種情況都不完美，但在現實世界中，第二種行為通常較受青睞，因為處理訊息多次投遞的情況（導致任務被多次執行）通常遠比處理一個時不時完全不執行特定任務的系統來得簡單。Amazon SQS (Simple Queue Service) 就是一個 at-least-once delivery 系統的例子。

at-least-once delivery 系統之所以更受青睞，還有一個與分散式系統相關的根本原因：另一種語意（at-most-once delivery）要求佇列必須是 strongly consistent 的——一旦訊息被確認，就不能有其他 worker 能夠再次確認同一則訊息，這是一項很強的保證。

一旦我們將焦點轉向 at-least-once delivery 系統，就會發現以 CP system(CP 系統) 來建模佇列不僅是浪費，甚至是一種缺點：

• 無論如何，我們都無法保證比 at-least-once delivery 更強的投遞保證。
• 我們的佇列將失去在 network partition 少數邊仍能運作的能力。
• 由於一致性需求，佇列需要達成共識，因此我們在沒有任何充分理由的情況下，耗費了效能並增加了延遲。

由於訊息可能會被投遞多次，從概念上來說，我們想要的是一個 commutative data structure(可交換資料結構) 與一個 eventually consistent system(最終一致性系統)。訊息可以儲存在一個複寫至 N 個節點的 set 資料結構中，其合併函式即為各集合之間的聯集。由 worker 在訊息執行後所發送的 acknowledgement，在概念上也是集合中的元素，用來標記某個元素已被處理。這是一個極為簡化的範例，對於實際系統而言並非特別實用，但它展示了特定類型的佇列如何能透過分散式系統的一組特定屬性來妥善建模。

務實來說，我們的佇列還可以嘗試提供其他有用的功能：

• 在至少一段時間內保證僅投遞給單一 worker：雖然允許多重投遞，我們仍希望盡可能避免這種情況。
• 盡力而為的檢查，以避免在逾時後重新投遞已經處理過的訊息。同樣地，我們無法保證此一屬性，但我們會盡力減少對實際上已處理過的訊息重新發送。
• 具備足夠的內部狀態，以便在正常運作期間將訊息以 FIFO(先進先出) 的方式處理，讓先到達的訊息先被處理。
• 內部資料結構的自動清理。

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

遺憾的是，雖然已存在許多以 Redis 為基礎的佇列實作，卻沒有任何一個嘗試利用 N 個獨立的 Redis 節點及其所提供的原語，作為建構具備此類特性的分散式系統的基石。利用 Redis 的資料結構與效能，以及提供特定有用保證的演算法，或許能提供一個非常實用、易於管理與擴展，同時在每個節點上都能提供優異效能（messages / second）的佇列系統。

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