當資料與查詢量大到 replication 不足以應對？
對於超大 dataset 或超高吞吐量，已經無法只用一台機器儲存與處理，這時可以對資料採用 partitioning (sharding)，它是一種將大型資料庫分解為較小資料庫的方法。
對資料做 partition 的主要原因是為了可擴展性 (scalability)。在無共享架構 cluster 中，不同 partition 可以放在不同節點上，因此一個超大 dataset 可以分散在多個磁碟上，而 query load 也可以分散到多個處理器上。
針對在單個 partition 上跑的 query，可以由各個負責該 partiotion 的節點獨立執行，所以增加更多的節點就能擴展 query 吞吐量。而大型複雜的 query，可能需要跨多個節點平行化執行，雖然比較困難但同樣做得到。不論是為 transaction 或為資料分析而設計的 DB 系統，partitioning 的基本原理都能適用於這兩種 workload。
Partitioning#
partitioning 的目標是將 data 和 query load 均勻分佈在多台機器上，避免產生熱點 (hot spot，即某個節點有誇張的高負載)。這需要選擇適合你的資料的 partitioning 方式，並且當 cluster 有新增或刪除節點時，需要重新平衡 (rebalancing) partition。
partition 的定義一般是這樣：每筆資料 (每個 record、row、document) 只隸屬於一個 partition。(不過因為通常 partition 會跟 replication 結合運用，所以這筆資料仍然可以儲存在多個不同節點上，以提高系統容錯能力。) 而每一個 partition 自身都是一個小 DB。
那麼要對大量資料要做 partition，如何決定哪些資料要儲存在哪些節點上？
對於 key-value data model 的資料，兩種主要的 partitioning 做法有：鍵範圍分區 (key range partitioning)－按 key 的範圍來分區；以及雜湊分區 (hash partitioning)－按 key 的 hash 值來分區。若是針對有次索引 (secondary index) 的資料，像是關聯式 DB 和許多 document DB，次索引也需要做 partition，則有兩種主要做法：document-based partitioning 和 term-based partitioning。
Rebalancing and Request Routing#
將負載 (資料、讀寫請求) 從叢集中的一個節點移動到另一個節點的過程，稱為再平衡 (rebalancing)。隨著時間推移，DB 會有某些變化，比如吞吐量增加我們想增加 CPU、dataset 變大我們想增加 RAM 和磁碟、有機器故障需要其他機器扛起重擔等等，這時就需要重新平衡 partition，也就是將 partition 從一個節點轉移到另一個節點上。而將 partition 再平衡的方法有固定分區數量、動態分區、按節點比例做分區等。
現在我們已經將 dataset 做 partitioning 並運行在多個節點上，但還有一個問題：當 client 發出請求 (比如想讀取 “foo” 這個 key)，要怎麼知道該連到哪個節點？(IP & port?)
這是一個常見的問題稱為 service discovery，不只 DB 會遇到，任何可以透過網路存取的軟體都有這個問題，特別是當它是以多機冗餘達到高可用目標時。在較高的層次上，有幾種方法可以解決這個問題：
由於再平衡使 partition 分配給節點的情況會有變化，那麼做出 routing 決策的元件 (可能是某個節點、 routing 層、client) 要怎麼知道哪一個 partition 被分配到哪一個節點？
許多分散式資料系統會使用一個外部協調服務 ZooKeeper 來追蹤叢集內的 metadata，ZooKeeper 維護 partition 和節點的 mapping 關係，而其他參與者可以向 ZooKeeper 訂閱此資訊來知道 partition 到節點的分配變化。
