本文為 Design Data Intensive Applications 的書摘 + 個人心得。
前幾篇文章我們討論了如何將資料分散到不同節點的 Replication，對那些大型資料集或超大的查詢吞吐量來說，只用 Replication 是沒有效率的，我們需要把資料切成小塊，這個動作稱為 partitions 或 sharding。
partitions 通常是定義如何把資料切成小塊的方法，所有的小塊都屬於每一筆 row、document 或 record，做 partition 最主要的目的就是 scalability，將 partition 分散到多個節點後，每一個 query 都能獨立進行，所以 query 的吞吐量也能隨著節點的增加而提高。
Partitioning and Replication
partition 通常會隨著 replication 一起做，一個節點會儲存許多不同的 partition，如果我們使用 base-leader 這個 replication 模型，組合 partition 後資料流看起來會如下圖：
每一個節點都能為 partition 的 leader 或 follower，之中做的事情就全部就跟前面幾篇討論的 Replication 一樣，因為 partition 的 schema 是獨立於 replication schema 的，所以往後幾天再討論 partition 時會忽略 replication 的事情。
Partitioning of Key-Value Data
我們該如何決定哪些資料到哪些節點上呢？
我們的目標是要把資料平均的分配到各節點上以利查詢時能平均查，理論上來看， 10 個節點的查詢和寫入速度應該要比單 1 個節點快 10 倍 (請暫時忽略 replication的事)，如果做 partition 時不公平，某些節點的 partition 資料量或查詢量比其他節點大很多，我們稱之為 skewed (偏斜) ；以最極限的例子來看，所有的流量最終只會查 1 個節點的 partition，其他 9 台很閒，1 個有著高流量的 partition 我們稱之為 hot spot。
一個最簡單避免 hot spot 的方法就是把資料隨機放，雖然節點的資料平均了，但缺點是你不知道資料在哪裡，意味者若要查詢特定 key 資料，你得去查所有節點的 partition。
在來會介紹 2 種更好、更實際的方法。
Partitioning by Key Range
首先第一種方法就是用 key 的範圍做 partition (從 key 的最小值到最大值)，就像下圖那樣，每一本百科全書都用首字字母分開放。
key 的範圍不用平均，因為你的資料本來就不會平均，試想這個百科全書的例子，若將字母以 2 個字母來平均分的話，T ~ Z 這區間的書會很少，這個 partition 的邊界需要以資料做調整。
對於每個 partition 中的資料，我們可以保持 key 為排序的狀態，例如 LSM-Tree，這個好處就是做範圍查詢非常快；然而，它的缺點就是某些操作會讓 partition hot spot，舉例來說你現在需要存感應器的資料，key 為 timestamp，partition 為日，感應器只會在檢測到某些事情時才存資料，所以你可能會有非常大量資料的 partition。
避免的方式就是用別的資訊當做第一個 key，例如感應器的名字，所以在做 partition 時會先用名字分，然後在用 timestamp。
Partitioning by Hash of Key
第二種做 partition 方法就是對 key 做 hash，因為是給 partition 用的 hash，所以我們的安全性不用太講究，例如 Cassandra 和 MongoDB 皆使用 MD5 做為 hash 函式；許多的程式語言皆有內建 hash 函式，要留意的是這些可能不是這麼適合做 partition，例如 Java 的 Object.hashCode() 在某些目的下相同的 key 會有不同的 hash 值。
一個好的 hash 函式可讓資料平均分佈，如下示意圖：
這個 partition 邊界就會很平均了，但有一好就有一壞，這個 partition 方法會損失範圍查詢的效率，因為 key 的排序消失了。
Cassandra 用 compound primary key 的方式來達到一種平衡，Cassandra 只 hash 第一個 key 來做 partition，然後用其他的 key 以 concatenated index 方式做 SSTables 中的排序，這個在一對多 的資料關係上好處尤其明顯，例如在一個社群網站，每一個 user 有許多貼文，此時若你貼文的 key 選擇 [user_id, update_timestamp]，你就能非常快速的查找某個 user 且也能快速的做時間範圍查詢。
Skewed Workloads and Relieving Hot Spots
講了這麼多我們還得要談談極端例子，即使你使用 key 的 hash 做 partition，還是有可能所有的查詢跟寫入都是同一個 key，所以就會發生 skewed 和 hot spot，以我們網路媒體來舉例，重大新聞發生時，user 都只會看那新聞，其他新聞沒興趣，該新聞的 partition 就會發生大量寫入和查詢。
直到今日，大多數的資料系統並不會自動偵測且補償 skewed 工作量，所以應用程式端得有責任做這些處理，但要留意的是你讓在寫入時的 partition 平均了，可能會順勢拉高查詢時間，例如上面那個新聞事件，我們可以在那新聞 ID 上加上 0～99 的數字，但你查詢時就得要多查 100 個 partition。
老話一句，依舊需要依不同應用軟體的場景做權衡，一定會有某種平衡的方法適合你公司 (例如只加 5 個數字)。
Partitioning and Secondary Indexes
在實務上，我們可能會為一些具指標性的欄位建立第二、第三個 index，secondary index 的目的不是要識別到單筆資料，而是要透過這個幫助工程師更快速的查詢到特定的值，例如快速找到所有紅色的車款。
許多的 relational 和 document 資料庫都支援 scondary index，既然這麼實用，我們就得研究研究如何在已用 key 切好 partition 的情況下，讓我們的 secondary index 也做 partition ，接下來介紹 2 種主要的方法：document-based partitioning 和 term-based partitioning。
Partitioning Secondary Indexes by Document
想像一下你有一個賣二手車的網站，每台車都有自己的 unique ID (也是 document ID，我們使用 document 資料庫)，你的 partition 策略選擇 key 範圍，例㜶 0~499 為 partition 0，500~999 為 partition 1 以此類推。
你想讓 user 能用顏色和車廠來搜尋二手車，所以你需要為這 2 個 fields 建立 secondary index，爾後你在新增紅色的車款時，資料庫就會自動將 color:red 當做進入點字串來建立 index，建立完成後如下圖：
可以看到這個 index 的方法，每個 partition 都是完全的將 index 分離，每個 partition 都維護自己的 secondary index ，裡頭只列出該 partition 底下的 document id，互不干擾，之後不管你是新增、更新、刪除都只會影響某一個 partition，這就是 document-partition 也被稱為 local index 。
現在我們想查紅色二手車，在這個 index 方法底下，我們一定得查詢 所有 的 partition，這個查詢方法也稱為 scatter/gather ，因為是查所有的 partition，所以這個查詢操作是昂貴的，會傾向增加 P99 response time。
儘管如此，document-partition 還是被廣泛的運用到 MongoDB, Riak, Cassandra, Elasticsearch, SolorCloud 這些資料庫上。
Partitioning Secondary Indexes by Term
不像前一個 index 方法是存在每個 partition 裡 (local index)，接下來這個 index 方法也稱為 global index ，它就只把它存在一個 partition 裡，如下圖：
可以看到我們的紅色二手車 color_red 只出現在 partition 0 裡頭了，partition 1 裡沒有，這個方法會將 color_red 視為完整字串項目來做 partition，所以 partition 0 只存了 a ~ r 字母顏色開頭的車， partition 1 只存了 s ~ z 字母顏色開頭的車，車廠 make: 亦同，這就是 term-partition 。
gobal (term-partition) index 的好處就是讀取變的有效率了，因為它不用像 document-partition 那樣需要讀所有的 partition，反之缺點就是寫入比較慢和複雜，因為一筆 document 會影響許多的 partition。
