# 1. Introduction
現代的網頁應用程式面臨前所未有的資料管理挑戰，即使是管理會話狀態、內容元資料及用戶生成內容這些相對"簡單"的任務。Web 應用程式的主要需求包括可擴展性、對地理分布用戶一致的快速響應時間以及高可用性，同時，這些應用程式通常能容忍放鬆的一致性保證。

- 可擴展性：像 Flickr 和 del.icio.us 這樣的熱門應用程式需要一個可擴展的資料引擎，不僅要求架構上的可擴展性，還要求在快速增長期間能夠通過增加資源來擴展，而對系統性能的影響最小。
- 響應時間和地理範圍：應用程式必須能夠一致地滿足 Yahoo! 的內部服務水平協議 (SLAs)，確保頁面加載時間的要求。由於 Web 用戶遍布全球，必須在多個大陸上擁有資料副本以提供低延遲訪問。
- 高可用性和容錯性：應用程式需要高可用性，在不同故障情況下，服務必須能夠繼續運行，這包括服務器故障、網絡分區和同址設施電源故障。
- 放鬆的一致性保證：傳統資料庫系統提供序列化事務的一致性模型，但在全球分佈系統中實現這一目標的代價非常高。許多 Yahoo! 的 Web 應用程式通常只操作單個記錄，因此常規事務的序列化是不可行且不必要的。

**Example 1**
考慮一個允許用戶上傳照片並控制訪問權限的照片分享應用程式。假設每個用戶的記錄包含照片列表及允許查看這些照片的人員集合。為了向 Bob 顯示 Alice 的照片，應用程式從資料庫讀取 Alice 的記錄，確定 Bob 是否在訪問列表中，然後使用 Bob 的照片列表從單獨的存儲中檢索實際的照片文件。用戶希望對其記錄進行以下兩個更新：

1. 將他的母親從可以查看照片的人員列表中移除
2. 上傳春假照片

在最終一致性模型下，更新 1 可以發送到記錄的副本 R1，而更新 2 可能發送到副本 R2。即使最終副本 R1 和 R2 的狀態是一致的（最終一致性保證），在 R2 中，在一段時間內，用戶可以讀取一個不應該存在的記錄狀態：照片已上傳但訪問控制變更尚未生效。

這種異常打破了應用程式與用戶的契約。這種異常的產生是因為副本 R1 和 R2 以相反的順序應用了更新 1 和更新 2，即副本 R2 對一個過時版本的記錄應用了更新 2。

這些例子說明了在某些情況下讀取稍微過時的資料是可以接受的，但有時應用程式需要更強的一致性保證。

## 1.1 PNUTS Overview

我們正在構建 PNUTS 系統，一個大規模的託管資料庫系統，用於支持 Yahoo! 的 Web 應用程式。重點是為 Web 應用程式提供資料服務，而非複雜查詢。以下是 PNUTS 的關鍵特性和架構決策的摘要：

- 資料模型和特性：PNUTS 向用戶展示一個簡單的關聯模型，支持帶有條件的單表掃描。
- 容錯性：PNUTS 在多層次上採用冗餘技術，利用一致性模型來支持高可用性讀取和寫入。
- 消息系統：異步操作通過名為 Yahoo! Message Broker (YMB) 的主題型發布/訂閱系統進行。
- 記錄級主控：PNUTS 使高延遲操作異步化，並支持記錄級別的主控。
- 託管：PNUTS 是一個託管的、集中管理的資料庫服務，支持多個應用程式。

## 1.2 Contributions

本文介紹了 PNUTS 的設計和功能，以及用於查詢路由和協調大型資料存儲增長的關鍵協議和演算法：

- 基於記錄級、異步地理複製的架構，使用保證消息交付服務而非持久化日誌。
- 提供事務特性的但不完全是序列化的一致性模型。
- 審慎選擇要包含或排除的功能。
- 作為託管服務提供資料管理。

# 2. Functionality

這一章節簡要介紹了 PNUTS 的功能，並指出我們在保持系統簡單的同時，如何滿足 Yahoo! 應用程式開發者的關鍵需求。我們首先概述資料和查詢模型，接著介紹一致性模型和通知模型，最後簡要討論高效批量加載的需求。

## 2.1 Data and Query Model

PNUTS 向用戶展示了一個簡化的關聯資料模型。資料組織成具有屬性的記錄表。在典型資料類型之外，"blob" 也是一個有效的資料類型，允許記錄內部的任意結構，但不一定是大型二進位對象如圖片或音訊。模式是靈活的，可以隨時添加新屬性而不會中斷查詢或更新活動，且記錄不要求包含所有屬性的值。

- 資料模型：簡化的關聯資料模型，支援 "blob" 類型和靈活的模式。
- 查詢語言：支援單表的選擇和投影。更新和刪除必須指定主鍵。雖然相比於關聯系統有所限制，但單表查詢提供了比分佈式雜湊 (distributed hash) 或有序資料存儲 (ordered data stores) 更靈活的訪問。

系統主要為在線服務工作負載設計，這些工作負載主要包括讀取和寫入單個記錄或小群記錄的查詢。因此，我們優化了大多數只掃描幾十或幾百條記錄的查詢。掃描可以指定謂詞，並在服務器端進行評估。同樣，我們提供了一個 "multiget" 操作，支援通過指定一組主鍵和一個可選的謂詞，並行檢索多個記錄（來自一個或多個表）。

- 多重獲取操作：支援並行檢索多個記錄，但通常只檢索幾千條記錄。
- 限制：系統不強制執行如參照完整性 (referential integrity) 等約束，這需要進一步研究。缺少複雜的即席查詢 (ad hoc queries)（如聯接、分組等），這是未來的工作方向。

## 2.2 Consistency Model: Hiding the Complexity of Replication

PNUTS 提供了一種介於一般序列化 (general serializability) 和最終一致性 (eventual consistency) 之間的一致性模型。這種模型源自於我們早期的觀察，即 Web 應用程式通常一次操作一個記錄，而不同記錄可能具有不同的地理局部性。我們提供每個記錄的時間線一致性(per-record timeline consistency)：所有副本對給定記錄的所有更新按相同順序應用。

在此圖中，時間線上的事件是針對特定主鍵的插入、更新和刪除。插入和刪除之間的間隔表示記錄在資料庫中物理存在的時間。任何副本的讀取都會返回該時間線中的一致版本，且副本總是在時間線中前進。

- 時間線一致性：所有副本對給定記錄的更新按相同順序應用。
- 主控機制：每個記錄獨立指定一個副本為主控，所有更新都轉發到主控副本。主控副本隨工作負載自適應變更，記錄攜帶一個序列號，每次寫入時遞增。

為了實現這種時間線一致性模型，我們支援一系列具有不同一致性保證的 API 調用：
- `Read-any`：返回可能過時但總是有效的記錄版本，適用於性能比一致性更重要的場景。
- `Read-critical(required_version)`：返回一個嚴格不早於所需版本的記錄版本，適用於寫入後希望讀取反映其更改的場景。
- `Read-latest`：返回反映所有成功寫入的最新記錄版本，可能比 `read-any` 和 `read-critical` 延遲更高。
- `Write`：提供與單一寫操作事務相同的 ACID 保證，用於盲寫操作。
- `Test-and-set-write(required_version)`：僅在當前版本與所需版本相同時執行寫操作，用於實現基於讀取後的寫入操作。

## 2.3 Notification

類似觸發器的通知對於如廣告投放這類應用程式非常重要。當廣告合約到期時，必須使緩存的副本失效。PNUTS 允許用戶訂閱表的更新流。通知基於我們的 pub/sub 基礎設施提供，具有與資料複製機制相同的可靠性保證。

## 2.4 Bulk Load

儘管我們強調可擴展性，我們仍然尋求支援重要的資料庫系統功能。批量加載工具對於如比較購物等應用程式是必需的，這些應用程式每天將大量的新銷售清單上傳到資料庫中。批量插入可以並行進行，以快速加載資料。在雜湊表 (hash table) 情況下，雜湊函數自然地將插入均衡分佈到存儲單元上。然而，在有序表 (ordered table) 情況下，對有序記錄的批量插入需要仔細處理以避免熱點並確保高性能。

# 3. System Architecture

PNUTS 是一個地理分佈的資料庫系統，設計目標是提供高可用性、高性能及一致性。它採用了記錄級主控 (record-level master) 架構，每個記錄都有一個主副本 (master replica) 負責處理寫入操作，而多個副本 (replicas) 負責處理讀取操作。這種設計能有效地支援多種一致性需求和高效的資料管理。

## 3.1 Data Storage and Retrieval


資料表被水平分割成稱為 tablets 的記錄群組。tablets 被分散存儲在多個伺服器上，每個伺服器可能有數百或數千個 tablets，但每個 tablet 只存儲在單一伺服器上。每個 tablet 大小為數百 MB 到數 GB，包含成千上萬的記錄。

主要負責管理和訪問資料 tablets 的組件包括儲存單元 (storage unit)、路由器 (router) 和 tablet 控制器 (tablet controller)。

- 儲存單元(Storage Units)：儲存 tablets，處理 get() 和 scan() 請求，並處理 set() 請求的更新。
更新首先寫入消息代理 (message broker)。儲存單元使用適當的物理存儲層，雜湊表仿造 UNIX 文件系統，有序表使用類似 MySQL 和 InnoDB的方法。
- Routers：確認哪個 tablet 包含紀錄與確認哪個儲存單元擁有該 tablet。
- 有序表(ordered tables)：分割主鍵(primary-key)空間成多個區間，每個區間對應 tablet。
Figure 2a 顯示了一個例子。這個映射類似於一個非常大的 B+ 樹的根節點。
使用二分搜尋尋找包含該鍵值的 tablet。
- 雜湊表(Hash-organized Tables)：使用一個 $n$ 位的雜湊函數 $H()$，生成的雜湊值範圍為 $0 \le H() \lt 2^n$。雜湊空間 $[0...2^n)$ 被分成多個區間。
Figure 2b 顯示了一個例子。將鍵映射到 tablet 的過程是，首先對鍵進行雜湊，然後在區間集合中進行二分搜尋，找到包含該區間的 tablet 和儲存單元。
- tablet 控制器(Tablet Controller)：路由器僅包含區間映射的緩存副本。映射由 tablet 控制器擁有，路由器定期輪詢 tablet 控制器以獲取映射的任何更改。
tablet 控制器決定何時將 tablet 在存儲單元之間移動以平衡負載或恢復，何時需要拆分大的 tablet。
tablet 控制器是一對主/備伺服器(active/standby servers)，但控制器不是瓶頸，因為它不在數據路徑上。

## 3.2 Replication and Consistency

PNUTS 系統使用異步複製 (asynchronous replication) 來確保低延遲更新。系統的核心是 Yahoo! Message Broker (YMB)，一個發布/訂閱系統，用於資料複製和可靠性保障。

### 3.2.1 Yahoo! Message Broker

Yahoo! Message Broker (YMB) 是一個基於主題的發布/訂閱系統，是 Yahoo! Sherpa 數據服務平台的一部分。數據更新在發布到 YMB 後被認為是 "已提交"。在提交之後，更新會異步地傳播到不同的區域，並應用到它們的副本上。由於副本可能不反映最新的更新，我們開發了一種一致性模型來幫助程序員處理這種滯後現象。

- **消息交付保證**：YMB 確保在消息應用到數據庫之前不會丟失消息。即使在單個代理機器故障的情況下，YMB 也保證已發布的消息會被交付給所有訂閱該主題的用戶。這是通過將消息記錄到多個伺服器上的多個磁碟來實現的。
- **跨區域複製**：YMB 被設計用於廣域複製，YMB 集群位於不同的地理位置，消息發布到一個 YMB 集群後會被轉發到其他 YMB 集群，以便在當地交付給訂閱者。

YMB 提供已發布消息的部分排序。發布到特定 YMB 集群的消息將按發布順序交付給所有訂閱者。然而，發布到不同 YMB 集群的消息可以按任何順序交付。為了提供時間線一致性，我們開發了每個記錄的主控機制，由記錄的主控發布的更新按發布順序交付給其他副本。

### 3.2.2 Consistency via YMB and Mastership

PNUTS 通過指定每個記錄的一個副本為主控 (master) 來提供每個記錄的時間線一致性。所有更新都指向主控副本。這種記錄級別的主控機制基於每個記錄分配主控，並且同一表中的不同記錄可以在不同的集群中進行主控。

- **高本地性寫入**：我們觀察到在網頁工作負載中，每個記錄的寫入具有顯著的本地性。這樣的高本地性證明了從性能角度使用主控協議的合理性。
- **異步更新傳播**：所有更新通過發布到消息代理來傳播到非主控副本，一旦更新發布，我們將其視為已提交。主控發布其更新到單個代理，並按提交順序將更新交付給副本。
- **主控轉移**：更新可以在非主控區域發起，但必須在提交前轉發給主控副本。每個記錄維護一個隱藏的元數據字段來標識當前的主控。

### 3.2.3 Recovery

故障恢復涉及從其他副本複製丟失的 tablets。複製 tablet 是一個三步驟過程：

- 請求副本：tablet 控制器從特定的遠程副本請求一個副本。
- 發布檢查點消息：確保在複製開始時的任何進行中的更新應用於源 tablet。
- 複製副本：將源 tablet 複製到目標區域。

為支援這一恢復協議，副本之間的 tablet 邊界保持一致。(通過兩階段提交在所有區域進行 tablet 拆分)

## 3.3 Other Database System Functionality

### 3.3.1 Query Processing

PNUTS 支援多種查詢操作，包括單記錄讀寫、多記錄查詢和範圍查詢。

- **單記錄操作**：直接轉發至包含該記錄的儲存單元 (storage unit)。
- **多記錄操作**：由路由器 (router) 中的散佈收集引擎 (scatter-gather engine) 處理。散佈收集引擎將多記錄請求拆分為多個單記錄或單個 tablet 掃描請求，並行執行這些請求，最後將結果組裝並返回給客戶端。

範圍查詢和表掃描 (table scans) 也由散佈收集引擎處理。對於範圍查詢，散佈收集引擎將逐個掃描 tablets 並返回結果，並生成一個續延物件 (continuation object)，使客戶端可以檢索下一組結果。這樣可以將游標狀態保存在客戶端，而不是伺服器端，從而減少伺服器端狀態的管理負擔。

- 未來優化：PNUTS 計劃未來引入查詢優化技術，例如讓客戶端提供多個進程以並行檢索結果，提高吞吐量，並利用系統的並行特性。此外，對於範圍或表掃描的預測掃描次數進行優化，以便在每次返回結果時並行掃描多個 tablets。

我們有意避免了涉及連接和聚合的複雜查詢，以最小化系統工作負載的意外峰值。然而，基於系統使用經驗和用戶需求，我們可能會考慮擴展查詢語言，因為我們的設計並沒有根本上阻止我們支持更豐富的查詢語言。

### 3.3.2 Notifications

PNUTS 提供了一種通知服務，允許外部系統訂閱資料更新。例如，用於維護外部數據緩存或填充關鍵字搜索引擎索引。

- 基於發布/訂閱 (pub/sub)：由於我們已經使用 pub/sub 機制在區域間複製更新，提供基本的通知服務只需允許外部客戶端訂閱消息代理並接收更新即可。
- 主要挑戰：
- 訂閱管理：提供機制訂閱整個表的所有主題，當 tablet 拆分時，客戶端自動訂閱新主題。
- 資源消耗：處理慢速客戶端導致的消息積壓問題，目前策略是當積壓過大時，斷開其訂閱並丟棄消息，未來將研究其他策略。

# 3.4 Hosted Database Service

PNUTS 是一個託管的、集中管理的資料庫服務，由多個應用程式共享。為了增加容量，我們只需增加伺服器。系統會自動調整，將部分負載轉移到新伺服器上。對於某些應用程式，瓶頸在於磁碟搜尋 (disk seeks) 的並行數量；對於其他應用程式，瓶頸在於總體 RAM 用於緩存或 CPU 週期用於處理查詢。在所有情況下，增加更多伺服器會增加瓶頸資源。

當伺服器出現硬體故障（如電源供應故障或 RAID 控制器故障）時，我們會自動恢復，將數據從副本複製到其他在線伺服器（新伺服器或現有伺服器），對失敗伺服器本身進行極少或不進行恢復。

- 自動恢復：從副本中恢復數據到其他伺服器，極少或不進行失敗伺服器的恢復。
- 擴展目標：擴展到超過十個全球副本，每個副本擁有 1,000 台以上的伺服器。
- 管理負載：自動故障轉移和負載平衡。

這種託管模型引入了幾個需要處理的複雜問題。首先，即使在我們相對狹窄的 Web 服務應用程式範疇內，不同應用程式的工作負載和需求也不同。

- 支援不同工作負載：系統必須支援不同的工作負載配置檔，並且能夠自動或輕鬆地調整。
- 主控遷移協議(mastership migration)：根據不同應用程式的寫入模式進行調整。

其次，我們需要防止一個重量級應用程式對其他應用程式的性能產生負面影響。

- 性能隔離：防止一個重量級應用程式影響其他應用程式的性能。
- 實現方式：將不同應用程式分配到區域內不同的儲存單元組。