# 7-4 PNUTS: Yahoo!’s Hosted Data Serving Platform

:::info
PNUTS是一個用於 Yahoo! 網路應用程式的大規模並行和地理分散的NoSQL資料庫系統，利用自動負載平衡和故障轉移來減少運營複雜性，設計重點是為網路應用程式提供資料服務，而不是複雜的查詢。
特點如下:
1. 可擴展性
2. 地理分佈廣泛，分佈在全球多個資料中心
3. 高可用性及容錯
4. 最終一致性
5. 適合儲存相對較小的記錄，不適合儲存大型檔案、串流媒體等
:::

## Introduction
系統主要針對線上服務工作負載而設計，這些工作負載主要由讀取和寫入單一記錄或小組記錄的查詢組成。
* 設計目標
* 可擴展性
* 低延遲: 儘管網路用戶分散在全球各地，也需保證對地理分散的用戶提供快速的響應時間。
* 高可用性及容錯
* 最終一致性
### PNUTS overview
* 資料模型和特徵
* 簡單的關聯式模型，支持有條件的single-table scans。
* 額外功能
* scatter-gather operation
* 用於異步通知客戶端的設施
>對於像廣告投放這樣的應用程式非常重要，這些應用程式必須在廣告合約到期時使廣告的快取副本失效。
* bulk loading(批量加載)
>對於像比價購物這樣的應用程式是必要的，這些應用程式每天要將大量的新銷售列表上傳到資料庫中，批量插入可以並行進行到多個存儲單元，以實現快速加載。
* 容錯能力
* 在多個層級（資料、元資料、服務元件等）採用冗餘，利用本文的一致性模型，即使在出現故障或分區後，也支持高可用的讀寫操作。
* 發佈-訂閱消息系統
* 選擇 pub/sub 而不是其他非同步協定（例如 gossip），因為它可以針對地理位置較遠的副本進行最佳化，而且副本不需要知道其他副本的位置。
>異步操作是通過topic-based pub/sub system進行的，稱為Yahoo! Messsage Broker。
* 記錄級主控(Record-level Mastering)
* 為了滿足回應時間目標，PNUTS 不能使用本地叢集中部署的系統（例如 GFS）所採用的全寫複製協議。
* **使所有高延遲操作非同步**，並支持record-level mastering.，非同步使我們能夠滿足延遲預算（50-100 毫秒），而不受地理分佈的影響，而Record-level Mastering處理允許大多數請求（包括寫入）在本地得到滿足。
* 託管
* PNUTS 是一個託管的、中央管理的資料庫服務，由多個應用共享。
* 將多個應用程式整合到一個服務中使我們能夠分攤多個應用程式的營運成本，並將相同的最佳實踐應用於許多不同應用程式的資料管理。
* 擁有一個共享服務讓我們能夠保留資源（server、disk等），並快速將它們分配給突然流行起來的應用。
### PNUTS Contributions
1. 基於*record-level*、異步地理複寫的架構，以及使用保證消息傳遞服務而不是持久性日誌。
2. 一致性模型為應用提供了交易特性，但不提供完全的可序列化。
3. 謹慎選擇要包括（例如，雜湊和有序表組織、靈活的架構）或排除（例如，對臨時查詢的限制、無參照完整性或可序列化交易）的特性。
4. 以託管服務的形式提供數據處理。

## FUNCTIONALITY
### Data and Query Model
* 數據被組織成具有屬性的記錄表。
* 每行都有一個主行，行可以有二進位 blob欄位。
* PNUTS的查詢語言支持從單一表中選擇和投影(更新和刪除必須指定主鍵)，單表查詢提供了與分佈式雜湊或有序資料存儲相比非常靈活的訪問，並為系統未來的優化提供了機會。
* 查詢
* point access: 使用者更新自己的記錄
* range access: 按順序掃描一組朋友
* 不支援複雜的即席查詢（joins、group-by等）

### Consistency Model: Hiding the Complexity of Replication
PNUTS提供了一種一致性模型，介於一般可序列化和最終一致性的兩個極端之間。
**提供每條記錄的時間線一致性(per-record timeline consistency)**，給定記錄的所有副本以相同的順序應用該記錄的所有更新，如下圖展示對一條紀錄的更新序列。

每條記錄獨立，指定其中一個副本為主副本，接收大多數該記錄寫請求的副本成為該記錄的主副本，並將該記錄的所有更新轉發到主副本，主副本會根據工作負載適應性地變化。

如下圖，時間線上的事件是針對特定主鍵的插入、更新和刪除。圖中顯示的插入和刪除之間的間隔，由一條深色線表示，這段時間內記錄在資料庫中實際存在，記錄攜帶一個版本號，每次寫入時都會增加，任何副本的讀取都將返回此時間線上的一個一致版本，且副本始終在時間線上向前移動。
>（目前）在每個副本中只保留記錄的一個版本。


* 具有不同一致性保證級別的API
* Read-any: 當獲取最新的值並不是絕對必要時會使用的，延遲性低，但一致性也低，可能會看到舊版的紀錄。
* Read-critical(required version): 返回紀錄的版本要比所要求的新或一樣。
* Read-latest: 返回反映所有已成功寫入的最新副本的記錄。
* Write: 提供與其中包含單個寫操作的事務相同的 ACID 保證。
* Test-and-set-write(required version)：只有當記錄的當前版本與required version相同時，才執行所請求的寫入，確保這樣的兩個並發增量事務被正確序列化。

此一致性模型可以**在每條記錄的基礎上提供可序列化**，如果一個應用在同一個「事務」中多次讀取或寫入同一條記錄，應用必須使用記錄版本來驗證它自己的讀取和寫入，以確保該「事務」的可序列化。
但**不保證多記錄交易的一致性**。

## SYSTEM ARCHITECTURE
系統被劃分為多個區域，每個區域包含一整套系統組件和每個表的完整副本，區域通常是根據地理位置分布的。
系統沒有傳統的資料庫日誌或歸檔數據，使用發布/訂閱機制來實現可靠性和複製。
### Data Storage and Retrieval
這邊討論區域內的組件如何提供資料存儲和檢索。
資料表被水平分割成稱為*tablet*的記錄組，一個*tablet*包含數千或數萬條記錄，每個*tablet*在同一區域只會被存在單一server上，每個server會有很多*tablet*。
如*Figure 1*，每個資料中心的PNUTS結構由四個部分構成，其中前三個主要負責管理和提供對data tablet的存取
1. **Storage Units (SU)**: 負責儲存tablet，每個儲存伺服器上面都包含多個tablets，tablets是PNUTS上的基本儲存單元。
3. **Router**: 確定記錄存在哪個tablet，然後確定哪個儲存單元擁有那個tablet。
* 使用區間映射實現，僅包含區間映射的快取副本(映射由tablet controller擁有)。
* 有序資料: tablet的主鍵空間被劃分成若干區間，每個區間對應一個平板。如Figure 2(a)。
* 無序資料: 對key進行hash，然後再次使用二分搜尋對區間集合進行搜索，以定位包含該區間的平板和儲存單元。如Figure 2(b)。
4. **Tablet Controller**: router的位置只是記憶體快照，實際的位置由tablet controller unit決定。確定何時將tablet從一個儲存單元移動到另一個儲存單元以進行負載平衡或恢復，以及何時需要分割一個大tablet。
5. message broker: 處理遠端資料的同步。

### Replication and Consistency
系統透過異步複製來達到低延遲的更新。使用Yahoo!Message Broker(YMB)，一個發布/訂閱系統，作為重作log的替代品，也可作為複製機制。
#### YMB
* 收到的訊息被記錄並複製
* 資料更新發佈到 YMB 後即被視為「已提交」。
* 在提交後的某個時刻，更新將非同步傳播到不同的區域並應用於其他副本。
* 在PNUTS驗證更新已應用於資料庫的所有副本前，消息不會從YMB日誌中清除。
* YMB cluster 位於不同的、地理上分離的數據中心。
* 訊息在YMB區域內排序，但不同地區可以有不同的排序。
#### Consistency via YMB and mastership
* 透過將記錄的一個副本指定為主副本並將所有更新導向到主副本，提供每個記錄時間軸的一致性，一條記錄的更新可以起源於非主控區域，但必須在提交前轉發到主副本。
* 主控權是依記錄分配的，同一個表中的不同記錄可以在不同的群集中進行主控。
* 為了強制主鍵約束，將具有相同主鍵的記錄insert傳送到相同的儲存單元，該儲存單元決定哪個插入首先出現並拒絕其他插入，因此必須指定每個tablet的一個副本作為tablet master，並將給定tablet中的所有插入發送到tablet master。
* tablet master可能與record master不同。
* tablet master主機將更新序列化以記錄。
* 主記錄是資料的「真實」副本。
* 一旦記錄主機取得更新，更新就被視為“已提交”。
#### Recovery
1. tablet controller從特定的遠端副本(source tablet)請求一份複製。
2. 一個checkpoint message被發布到YMB，以確保在啟動複製時的任何正在傳輸的更新都被應用到source tablet。
3. 將source tablet複製到目標區域。

### Other Database System Functionality
#### Query Processing
* 多條記錄的操作需要一個生成多個請求並監控它們成功或失敗的組件，這邊使用scatter-gather engine接收一個多紀錄請求，將其分割成多個針對單條記錄或單個tablet掃描的單獨請求，並行發起這些請求。
* engine在server端而不是客戶端。
* 減少客戶端和服務器間必要的TCP/IP連接數，避免網路stack overloading。
* 允許進行優化，例如通過將同一儲存服務器的多個請求分組到同一個 Web 服務調用中。
* range query被分解
* 客戶端保留一個*continuation object*用來檢索下一組結果。

#### Notifications
* 使用發布/訂閱消息代理在各區域之間複製更新
* 允許外部客戶端訂閱我們的消息代理並接收更新。
* 提供了一種機制來訂閱一個table的所有主題，每當tablet更新或分割時，都可以發出通知。

### Hosted Database Service
PNUTS 是一個託管的、中央管理的資料庫服務，由多個應用共享，透過增加伺服器來增加容量，系統會自動適應的將一些負載轉移到新伺服器上。
目標是擴展到十個以上的全球副本，每個副本擁有 1000 台或更多的伺服器，在這個規模上，自動故障轉移和負載平衡是管理操作負載的唯一方式。
* 系統必須支援不同的工作負載配置檔，並能自動或輕鬆地調整到不同的配置檔。
* 性能隔離，以免一個重量級應用負面影響其他應用的性能。(目前性能隔離是通過將不同應用分配到一個區域內不同的儲存單元集來提供)。

## PNUTS APPLICATIONS
* **User Database**
Yahoo database每次用戶頁面瀏覽都會讀取並可能寫入資料，因此流量非常高，PNUTS 的大規模並行性將有助於支援海量的並發請求。可以接受寬鬆的一致性：用戶必須看到他自己的更改，但如果其他用戶在一段時間內看不到用戶的更改也是可以的。
* **Social Applications**
可以創建一個關係表，其主鍵是（Friend1, Friend2）的複合鍵，然後通過請求一個範圍掃描，對所有以給定用戶 ID 為前綴的鍵的記錄，找到某個用戶的所有朋友，我們的託管服務模型非常適合。
* **Content Meta-Data**
雖然 PNUTS 並不是為提供批量存儲而優化，但它可以作為分佈式批量存儲系統的元數據存儲，PNUTS 可以管理通常存儲在目錄和inodes內的結構化元數據。
* **Listings Management**
PNUTS的有序表可以用來存儲商品列表，按時間戳排序，以便購物網站顯示最新的 N 件商品。
* **Session Data**
網站經常維護每個會話的狀態，這些狀態不需要強一致性，為了增強性能，應用程式可能決定關閉 PNUTS 對會話表的所有一致性保證。

## Conclusion
PNUTS 的設計目標是在大規模情況下提供豐富的資料庫功能和低延遲。
* 用異步複寫來確保低寫入延遲，同時提供地理複寫。
* 開發了一種一致性模型，為應用提供了有用的保證，而不會犧牲可擴展性。
* 構建了一個託管服務，以最小化應用的運營成本，並專注於自動調整、優化和維護託管服務。

以上決策導致了系統中幾個新穎的方面
1. 每條記錄的時間線一致性，使應用更容易應對異步複寫。
2. 一個同時作為資料庫的複寫機制和重做日誌的消息代理。
3. 一個靈活的將平板映射到存儲單元的方式，以支持自動故障轉移和負載平衡。

## Reference
[筆記] https://zhu45.org/posts/2018/Mar/08/pnuts-yahoos-hosted-data-serving-platform/
[筆記] https://timyang.net/architecture/yahoo-pnuts/
[筆記] https://highscalability.com/yahoos-pnuts-database-too-hot-too-cold-or-just-right/
[筆記] https://stephenholiday.com/notes/pnuts/