# Ceph: A Scalable, High-Performance Distributed File System

## 1. Introduction
Ceph 是一個分散式檔案系統，保證了在可擴充性的前提下仍有很好的表現與可靠性。
Ceph 透過把 file allocation table 取代成 generating function 來達到把 data 跟 metadata 分離。
如此 Ceph 可以利用 **OSD(object storage devices)** 的特點來化解資料存取、更新、複製、可靠度、錯誤偵測、修復的麻煩之處。

## 2. System Overview

Ceph 檔案系統由三個主要部分組成：
1. 客戶端：每個實例都提供近似 POSIX 的操作介面給主機或程序
2. OSD 叢集：負責儲存所有資料與 metadata
3. metadata 伺服器叢集：管理 namespace 同時協調安全性、一致性、連貫性

我們說 Ceph 使用近似 POSIX 操作，是為了可以透過延伸介面並放寬一致性語法來對齊現有應用需求與增進系統表現。


最主要的目標是可擴充性(即使是在數百 PB 以上)、效能還有可靠性。
我們的目標工作量可能包括成千上萬的主機同時讀取或寫入同個檔案或建立檔案於同個目錄底下。

Ceph 探討了可擴充性的議題，同時達到高效能與可靠性，主要透過以下三個基本的設計特色：

### Decouple Data and Metadata

Ceph 極大幅度地把檔案的 metadata 與檔案的儲存分離開來
Metadata (open, name, etc.) 都是由 metadata 伺服器叢集管理，同時用戶直接與 OSD 互動來存取檔案。
與現存 object-based file systems 相比，Ceph 完全消除了 allocation list。
檔案資料是被分割於可預測的命名檔案(predictably named objects)內，同時一個專門的資料分布函數 CRUSH 負責分配物件到儲存裝置。
==此舉允許了任何人自行計算要存取的物件的位置，從而減緩了 metadata 叢集的工作量。==

### Dynamic Distributed Metadata Management

因為檔案 metadata 的操作占了大半部分的檔案系統工作量，有效率的 metadata 操作事關重大。
Ceph 採用了基於動態子樹劃分(Dynamic Subtree Partitioning)的新型 metadata 叢集結構，其可以動態且智慧的分散管理檔案系統目錄層級的責任到上百個 **MDS(Metadata Server)**
層級化可以保留每個 MDS 的 locality，有助於更新與激烈的預存取來增進效能表現。
工作量分配是基於現有存取規律，允許 Ceph 可以有效的利用所有 MDS ，並達成於 MDS 的增加時有近似線性的成長。

### Reliable Autonomic Distributed Object Storage

由上千個設備組成的大型系統本質上是動態的；系統都是逐漸成長、新舊裝置更迭導致成長與緊縮、裝置出錯是可預見且常態的、會有大量的檔案創建修改與刪除。
==Ceph 將資料遷移、複製、錯誤偵測與錯誤復原的責任交由 OSD。==

## 3. Client Operation

Ceph 客戶端提供操作介面給應用程序使用。
每個客戶端各自維護檔案快取。

### 3.1 File I/O and Capabilities

當一個程序開啟一個檔案時，客戶端會送請求到 MDS 叢集。
一個 MDS 會走訪檔案系統層級以轉換檔案名稱為 *file inode* ，其中資訊包含獨特 inode 號碼、檔案所有者、模式、大小還有其他 metadata。
如果檔案存在且允許存取，MDS 便回傳 inode 號碼、檔案大小、映射檔案資料成物件的條串化策略資訊。

Ceph 歸納了很多條帶化的策略。為了避免對檔案配置 metadata 的需要，物件名稱簡單的由檔案 inode 號碼與條帶號碼組成。
物件接著透過 CRUSH 來分配給 OSD。

### 3.2 Client Synchronization

POSIX 語意實際地要求讀取要能夠反映所有先前的寫入，且寫入必須是 atomic。
當有一或多個客戶想要寫入時，MDS 就會招回所有先前發給的讀取快取與寫入緩衝，強制客戶 I/O 達成同步。
也就是說所有讀寫的操作都會被 block 直到被 OSD 確認。
這種方法有效的將更新序列化與同步的問題交給 OSD。

### 3.3 Namespace Operations

客戶與檔案系統 namespace 的互動是由 metadata 伺服器叢集管理的。
讀與寫的操作會被同步的由 MDS 套用，來保證序列化、一致性、正確性與安全性。

Ceph 優化了最常見的 metadata 存取場景。
一個 `readdir` 後面跟著每個文件的 stat (例如 `ls -l`) 是常見的用法，並且在很大的目錄裡是個效能殺手。
在 Ceph 中，一個 `readdir` 指令只需要一個簡單的 MDS 請求，他可以得到整個目錄 inode 的內容。
預設情況下，如果 `readdir` 後面緊跟著一個或多個 stat ，則返回快取的訊息；否則就將他丟棄。
儘管這樣的放寬連貫性可能讓中間節點的更動被忽視，我們很樂意以此代價換來更好的效能。

Ceph 可以透過長時間的快取 metadata 來進一步放寬一致性，就如早期的 NFS 一樣快取 30 秒。然而，這種方法在某種程度上破壞了連貫性，這對應用程序來說是非常關鍵的。例如使用 stat 來判斷檔案是否有被更新的程序，要麼行為不正確，要麼等待舊的快取過時。

我們再次選擇提供正確的行為，為了返回正確的檔案大小和修改時間，MDS 會撤回所有的寫入授權來停止更新並蒐集最新的資料大小還有寫入時間。
最高的值將被用來回傳 stat ，並重新配給授權。
儘管停止一大批寫入授權有點極端，不過為了一致性是必須的。

## 4. Dynamically Distributed Metadata

Metadata 操作往往佔據大半工作量，而且盤踞在關鍵路徑上，使得 MDS 叢集的效能表現事關重大。
Ceph 中的檔案以及目錄的 metadata 非常小，幾乎只由 directory entries (file names) 以及 inode 組成。
物件名稱由 inode 編號組成並藉由 CRUSH 分配到 OSD

### 4.1 Metadata Storage

- 為了安全性考量，metadata 的更新需要被 commit 到硬碟。
- journals 允許每個 MDS 快速的將更新串流到 OSD；各 MDS 的 journals 也能協助吸收重複的 metadata 更新。

這個策略提供了兩個最好的結果：
1. 有效率地串流資料到硬碟
2. 大幅減少重新寫入的工作量

- inode 直接被內嵌在目錄中，允許 MDS 透過單個 OSD 請求來得到整個目錄。
- 每個目錄的內容都被以跟 metadata journal 和 檔案資料相同的條串化方法寫入。

### 4.2 Dynamic Subtree Partitioning

- 主副本快取策略讓單個被授權的 MDS 負責管理快取一致性，並條串化任何給定 metadata 更新。

大多現有分散式檔案系統使用一些基於靜態子樹劃分來委託權限。
但是一些現有檔案系統使用 hash 來分配目錄和文件的 metadata。

- 靜態子樹劃分無法應付動態工作調整與資料集。
- hashing 破壞了 locality 與有效的預存取。

Ceph 的 MDS 叢集市基於動態子樹劃分的策略，該策略會自我調適的將快取的 metadata 分配到一些節點上。
- 每個節點有一個指數衰減的計數器來測量目錄的流行度。
- 任何操作都會影響該節點及其所有親代節點上的計數器。
- Ceph 會根據目前工作量負載，動態的將目錄層級結構的子樹映射到 metadata 伺服器。
- 只有當單個目錄成為熱區才會跨多個節點分布。


MDS 負載的值會定期的被比較，並且適當大小的子樹會被遷移，好讓負載平衡。

### 4.3 Traffic Control

分配目錄層級予多個節點可以讓工作負載平衡，但沒辦法一直對付熱區或群聚，即許多客戶對同個目錄或檔案做存取。

- Ceph 僅在需要時廣泛分布熱區，避免不必要的開銷和目錄的局部性損失。
- 頻繁讀取的目錄（如許多開啟的目錄）內容會選擇性跨多節點複製以分散負載。
- 對於大或繁重寫入工作負載的目錄，內容按文件名哈希處理以平衡分布，犧牲目錄本地性。
- 客戶端通常知道不受歡迎（未複製）的 metadata 位置，並能直接聯絡適當的 MDS。
- 客戶端會被告知流行 metadata 分布於不同或多個 MDS 節點上，避免熱區和群聚。

## 5 Distributed Object Storage

Ceph 客戶端和 metadata 伺服器將整個物件存儲集群視為單一邏輯物件存儲和命名空間。
Ceph 的 RADOS 系統以分散式方式管理物件複製、叢集擴張、故障檢測和恢復，實現容量和聚合表現的線性擴展。

### 5.1 Data Distribution with CRUSH

- Ceph 必須在由數千個存儲設備組成的集群中分發PB級別的數據，有效利用存儲和頻寬資源。
- 為了避免不平衡和負載不對稱，採用隨機分配新數據的策略，將現有數據的隨機子樣本遷移到新設備，並均勻地重新分配被移除設備的數據。
- Ceph 利用一個簡單的 hash 函數將對象映射到放置組（PGs）中，並使用可調的 mask 來控制PG的數量。
- 每個 OSD 維持約100個 PG，以平衡 OSD 利用率的變化和每個 OSD 維護的複製相關元數據的數量。
- 使用 CRUSH 來將 PGs 分配給 OSD，這種方法不依賴於任何塊或對象列表 metadata。

### 5.2 Replication

- 在RADOS中，數據以放置組（PG）進行複製，每個PG被映射到一個有序的n個 OSD 列表中。
- 客戶端將所有寫入發送到對象PG的第一個可用 OSD（主副本），該 OSD 為對象和 PG 分配新版本號，然後將寫入提交給其他副本 OSD。
- 每個副本都實施了更新並向主副本響應後，主副本在本地實施更新，確認寫操作完成。
- 讀操作直接在主副本上執行，這種方法使客戶端免除了圍繞副本的串行化和一致性的任何複雜操作。

### 5.3 Data Safety

在分散式存儲系統中，將資料寫入共享存儲的主要原因有兩個：
1. 讓客戶端的更新對其他客戶端可見。這應該快速實現，特別是在多個寫入者或混合讀寫的情況下需要同步操作。
2. 確保客戶端已寫入的資料安全複製到磁碟上，以在斷電或其他故障時保留資料。

RADOS 將同步與安全分離來確認更新，實現低延遲更新和明確的資料安全語義。


- 主節點 (Primary) 將更新轉發給副本 (Replicas)，並在所有 OSD 的內存緩存中應用更新後回應確認訊息 (ack) 給客戶端，允許同步 POSIX 調用返回。
- 當資料安全寫入磁碟後，才會發送最終確認通知 (commit) 給客戶端。
- 將確認訊息發送給客戶端僅在更新完全複製後，以無縫容忍任何單個 OSD 的故障，雖然這會增加客戶端延遲。
- 預設情況下，客戶端也會緩衝寫入直到提交，以避免在所有 OSD 同時斷電時資料丟失。在這種情況下恢復時，RADOS 允許重播先前確認的更新以恢復一致性。

### 5.4 Failure Detection

- 即時故障偵測對於維護資料安全至關重要，尤其在集群擴展到數千個設備時變得更為困難。
- 針對磁碟錯誤或數據損壞等特定故障，OSD 可以自我報告。
- 對於網路無法達到的故障 (Unreachable Network Failures)：需要主動監控，RADOS 通過讓每個 OSD 監控其共享 PG 的同伴來分散監控責任。
#### 偵測方法
1. 被動確認：現有的複製流量作為活躍確認，無需額外的通信開銷。
2. 主動 Ping：如果一段時間內未收到同伴的消息，則發送明確的 Ping 訊息。
3. 兩個維度的活躍度 (Liveness Dimensions)：
- 可達性 (Reachability)：是否能夠通過網路連接到 OSD。
- 分配狀態 (Assigned Status)：是否有數據被 CRUSH 分配給 OSD。

#### 故障處理
- 標記為當機 (Marked Down)：無響應的 OSD 會被初步標記為當機，其主節點責任（更新序列化、複製）會臨時轉移到每個 PG 中的下一個 OSD。
- 標記為退出 (Marked Out)：如果 OSD 沒有快速恢復，它會被標記為退出數據分佈，並由另一個 OSD 加入每個 PG 以重新複製其內容。
- 故障報告與過濾 (Failure Reports and Filtering)：小型監控集群會收集故障報告並過濾暫時性或系統性問題（如網路分區）。

RADOS 為了避免由於系統性問題引發的廣泛數據重新複製，會將 OSD 標記為宕機但不標記為退出。

### 5.5 Recovery and Cluster Updates

Ceph 的 OSD 叢集地圖會因 OSD 故障、恢復和明確的叢集變更（如新存儲設備的部署）而改變。Ceph 對所有這些變更的處理方式相同。

- 物件版本號和變更日誌：為了促進快速恢復，OSD 為每個物件維護一個版本號，並為每個放置組 (PG) 記錄最近的變更（日誌記錄更新或刪除的物件名稱和版本號）。
- 叢集地圖更新：當活動的 OSD 收到更新的叢集地圖時，它會遍歷所有本地存儲的放置組，並計算 CRUSH 映射以確定自己是否是主要或副本。
- PG 成員變更：如果 PG 的成員變更或 OSD 剛啟動，OSD 必須與 PG 的其他 OSD 同步。對於複製 PG，OSD 會向主要節點提供當前的 PG 版本號。

#### 恢復過程
1. 版本號同步：如果 OSD 是 PG 的主要節點，它會收集當前（和以前）副本的 PG 版本號。如果主要節點缺少最新的 PG 狀態，它會從當前或之前的 OSD 獲取最近的 PG 變更日誌（或完整內容摘要）。
2. 共享最新狀態：主要節點將每個副本的增量日誌更新（或完整內容摘要）發送給它們，以確保所有方都知道 PG 的正確內容，即使本地存儲的物件集不匹配。在主要節點確定 PG 狀態並與副本共享後，才允許對 PG 中的物件進行 I/O 操作。
3. 自我修復：OSD 獨立地從其同伴中查詢缺失或過時的物件。如果 OSD 收到過時或缺失物件的請求，它會延遲處理並將該物件移至恢復隊列的前面。

### 5.6 Object Storage with EBOFS

Ceph 的每個 OSD 使用 EBOFS（基於 Extent 和 B-tree 的物件檔案系統）來管理本地物件儲存。

#### 主要特點
- 使用者空間實現 (User Space Implementation)：EBOFS 完全在使用者空間中實現，直接與原始區塊設備交互，允許定義自有的低階物件儲存介面和更新語義。這將更新序列化（同步）與磁碟提交（安全）分離。
- 原子交易 (Atomic Transactions)：EBOFS 支援原子交易（例如，對多個物件進行寫入和屬性更新），更新函數在記憶體緩存更新後返回，並提供非同步提交通知。
- 避開 Linux VFS 和頁面快取 (Avoid Linux VFS and Page Cache)：此方法提供更大的靈活性和更容易的實現，避免與 Linux VFS 和頁面快取的繁瑣互動，這些都設計於不同的介面和工作負載。
- 積極安排磁碟寫入 (Aggressive Disk Write Scheduling)：EBOFS 積極安排磁碟寫入，選擇在後續更新使掛起的 I/O 操作變得多餘時取消這些操作，這提供了更長的 I/O 隊列和相應的調度效率增長。使用者空間的調度器也使得最終優先處理工作負載（例如，客戶端 I/O 與恢復）或提供服務品質保證變得更容易。

#### 效能與擴展性 (Performance and Scalability)
- 優越的效能和安全語義：EBOFS 提供優越的效能和安全語義，通過 CRUSH 生成的平衡數據分佈和委託給 OSD 的複製與故障恢復管理，允許聚合 I/O 性能隨 OSD 叢集大小線性擴展。
- 與通用檔案系統比較 (Comparison with General-purpose File Systems)：與 ext3、ReiserFS 和 XFS 等通用檔案系統相比，EBOFS 在處理 Ceph 工作負載時表現出色。尤其是大於 32 KB 的寫入操作，EBOFS 幾乎飽和可用磁碟頻寬，且讀取工作負載表現顯著優於其他系統。

# CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data

## 1. Introduction

分散式存儲系統需要有效地分配大量數據並管理硬體故障。我們開發了 CRUSH (Controlled Replication Under Scalable Hashing) 演算法，用於高效、分散的物件存儲系統數據分配。
需要在數百或數千個存儲設備中均勻分配數據和工作負載，並管理系統擴展和硬體故障。

- 無中心目錄：CRUSH 不依賴中心目錄，而是使用一個伪随机、确定性的函数將数据对象映射到存储设备上。
- 動態調整：設計能在添加或移除存儲設備時，最小化不必要的數據移動。
- 靈活的數據複製和可靠性機制：支持多種數據複製和可靠性機制，並按照用戶定義的策略在故障域之間分離副本。

CRUSH 通過分佈數據和重組數據來最大化資源利用率和系統性能，並且能夠在設備故障時進行自動修復。

## 2 Related Work

對象存儲 (Object-based storage) 最近引起了很多關注，作為提升存儲系統擴展性的機制。許多研究和生產系統採用了對象存儲的方法。

現有系統：
- NASD file system
- Panasas file system
- Lustre
- GPFS
- Federated Array of Bricks (FAB)

這些系統使用半隨機或啟發式的方法將新數據分配到有可用容量的存儲設備，但很少重新分配數據來維持平衡。

傳統方法：
- 這些系統依賴於某種類型的 metadata 目錄來定位數據，而 CRUSH 則依賴緊湊的集群描述和確定性映射函數。
- Sorrento storage system 使用一致性哈希 (consistent hashing)，但缺乏對設備加權的支持、數據分佈的平衡性以及改進數據安全性的故障域 (failure domains)。

數據遷移問題：

- 傳統方法有較重的 metadata 需求，而 CRUSH 避免了這些需求。
- 某些研究使用哈希函數來分配數據，但不支持加權、複製或設備移除。

CRUSH 的優勢：
- CRUSH 基於 RUSH 演算法，但進一步解決了可靠性和複製問題，並提供了更好的性能和靈活性。

## 3 The CRUSH algorithm

CRUSH 演算法根據每個設備的權重值分配數據對象到存儲設備上，接近於均勻的機率分佈。

分佈控制：
- 使用階層集群圖 (hierarchical cluster map) 來表示可用的存儲資源，並由構建它的邏輯元素組成。
例如，可以將大型安裝描述為一排伺服器機櫃，機櫃內裝滿磁碟架，磁碟架內裝滿存儲設備。

數據分佈策略：
- 定義放置規則 (placement rules)，指定從集群中選擇多少副本目標以及對副本放置施加什麼限制。
例如，可以指定三個鏡像副本放置在不同的物理機櫃中，以避免共享同一電路。

映射計算：
- 給定一個整數輸入值 $x$，CRUSH 將輸出一個有序的 $n$ 個不同存儲目標的列表 $\overrightarrow{R}$。
- 使用強大的多輸入整數哈希函數，輸入包括 $x$，使得映射完全確定且僅依賴於集群圖、放置規則和 $x$ 計算。
- 分佈是偽隨機的，沒有明顯的相關性。

去集群化分佈：
- CRUSH 生成一個去集群化 (declustered) 的副本分佈，表示共享某個項目的副本的設備集合似乎獨立於所有其他項目。

### 3.1 Hierarchical Cluster Map

CRUSH 使用階層集群圖來表示和管理存儲資源，確保數據分佈均衡且高效。

設備與桶：
- 集群圖由設備 (devices) 和桶 (buckets) 組成，每個都有數值標識符和權重值。
- 桶可以包含多個設備或其他桶，形成存儲層次結構，設備總是在葉節點。

權重分配：
- 存儲設備根據其能力被分配權重，以控制其存儲數據的相對量。
- 桶的權重為其所包含項目的權重之和。

層次結構示例：
- 可以創建表示相同設備組的 *shelf* 桶，然後將其組合成 *cabinet* 桶，再進一步組合成 *row* 或 *room* 桶。

數據放置過程：
- 通過使用類似哈希的偽隨機函數遞歸選擇嵌套桶項目，將數據放置到層次結構中。
- CRUSH 使用四種不同的桶類型，每種都有不同的選擇算法，以應對設備增加或移除引起的數據移動和計算複雜性。

### 3.2 Replica Placement


CRUSH 設計用來均勻分配數據到加權設備上，維持存儲和設備頻寬資源的平衡利用率。

副本放置對數據安全的影響：
- CRUSH 能夠反映安裝的物理組織，並模型化潛在的相關設備故障來源。
放置策略可以將對象副本分離到不同的故障域 (failure domains) 以提高數據安全性。

放置規則：
- 為每種複製策略或分佈策略定義放置規則。
規則允許存儲系統或管理員指定對象副本的具體放置方式。
例如，可以有選擇兩個目標進行 2-way mirroring 的規則，或選擇三個目標進行 3-way mirroring 的規則。

放置算法：
- CRUSH 利用多輸入整數哈希函數來選擇副本目標。
- 算法通過層次結構中遞歸選擇嵌套桶項目來確定存儲目標。
- 使用 take 和 select 操作來選擇和過濾目標項目。


#### 3.2.1 Collisions, Failure, and Overload
- 算法會重新選擇項目以避免衝突 (collision) 和處理設備故障或過載 (overload)。
- 對於過載設備，CRUSH 通過隨機拒絕一定比例的數據來均勻地重新分佈項目。

#### 3.2.2 Replica Ranks
- 在容錯和糾刪碼 (erasure coding) 計劃中，副本的排列順序很重要。
- CRUSH 通過特定算法重新選擇失敗設備，確保副本順序不變。

### 3.3 Map Changes and Data Movement

在大型檔案系統中，對存儲資源的變更需要有效地處理，以維持數據和工作負載的均衡分佈。


設備故障：
- CRUSH 標記故障設備但保留在層次結構中，數據會均勻地重新分佈到其他存儲目標上。
- 這種方法使得只需要移動故障設備上的數據，最小化數據重分佈。

集群層次結構變更：
- 當集群層次結構發生變更（如添加或移除存儲設備）時，CRUSH 使用權重調整來確定需要移動的數據量。
- 由於每層決策是統計獨立的，數據移動會在子樹內均勻重新分佈。
- 數據移動的理論下限為 $\frac{𝐷𝑤}{𝑊}$（新設備權重與總權重之比）。

數據移動範圍：
- 在階層結構中的每層，權重變更會導致部分數據從權重減少的子樹移動到權重增加的子樹。
- 隨著層次結構深度增加，數據移動量會接近其上限，當新設備權重相對總權重較小時，移動量會達到最大。

效率優化：
- CRUSH 定義了四種不同的桶類型：uniform buckets、list buckets、tree buckets 和 straw buckets。
- 每種桶類型針對不同的計算和重組效率需求進行優化。

### 3.4 Bucket Types

CRUSH 定義了四種不同的桶類型來表示集群層次結構中的內部節點，每種類型在計算和重組效率上都有不同的權衡。

#### 3.4.1 Uniform Buckets

- 特點：
- Uniform buckets 包含相同權重的項目，類似於傳統的哈希分佈函數。
- 映射到 uniform buckets 的時間是常數時間 $𝑂(1)$。
- 映射函數：
- 使用函數 $c(r,x)=(hash(x)+rp)\%m$ 選擇項目，其中 $p$ 是大於 $m$ 的質數。
- 保證 $r≤m$ 時選擇不同的項目。
- 變更處理：
- 若 bucket 大小改變，數據會完全重新分佈，類似於傳統的哈希分佈策略。

#### 3.4.2 List Buckets

- 特點：
- List buckets 使用鏈表結構，能包含任意權重的項目。
- 適合於僅增加項目、不移除項目的場景。
- 映射過程：
- 從鏈表頭部開始，根據 hash 值和剩餘項目權重比較決定選擇項目或繼續遍歷。
- 最後選擇最符合條件的項目。
- 變更處理：
- 新項目加入鏈表頭部時數據遷移效率最佳，但移除中間或尾部項目時會導致大量數據移動。

#### 3.4.3 Tree Buckets

- 特點：
- Tree buckets 使用二元樹結構，適合管理大規模設備或嵌套桶。
- 映射時間為 $O(logn)$。
- 結構：
- 使用加權二元搜索樹，內部節點保存其左右子樹的總權重。
- 固定標記策略避免因樹的增長或縮小導致的標記變更。
- 映射過程：
- 從根節點開始，根據 hash 值和左右子樹權重比決定訪問子節點。
- 直到達到葉節點，選擇對應項目。
- 變更處理：
- 標記策略確保對現有葉節點的訪問路徑只會因樹根變更而改變，控制數據移動範圍。

#### 3.4.4 Straw Buckets

- 特點：
- Straw buckets 讓所有項目通過抽籤競爭來決定副本放置，確保公平。
- 適合於需要頻繁增減或調整權重的場景。
- 映射過程：
- 每個項目根據 hash 值抽取一根吸管，吸管長度由項目權重決定，長度最大的項目獲勝。
- 變更處理：
- 當桶中的項目變更時，straw buckets 能最佳地重新分佈數據。
- 性能比較：
- 相比 list 和 tree buckets，straw buckets 映射速度較慢，但數據重新分佈效率最高。