Partitioning and Secondary Indexes

本文為 Design Data Intensive Applications 的書摘 + 個人心得。

前幾篇文章我們討論了如何將資料分散到不同節點的 Replication,對那些大型資料集或超大的查詢吞吐量來說,只用 Replication 是沒有效率的,我們需要把資料切成小塊,這個動作稱為 partitionssharding

partitions 通常是定義如何把資料切成小塊的方法,所有的小塊都屬於每一筆 row、document 或 record,做 partition 最主要的目的就是 scalability,將 partition 分散到多個節點後,每一個 query 都能獨立進行,所以 query 的吞吐量也能隨著節點的增加而提高。

Partitioning and Replication

partition 通常會隨著 replication 一起做,一個節點會儲存許多不同的 partition,如果我們使用 base-leader 這個 replication 模型,組合 partition 後資料流看起來會如下圖:

figure_6-1

每一個節點都能為 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 的最小值到最大值),就像下圖那樣,每一本百科全書都用首字字母分開放。

figure_6-2

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 函式可讓資料平均分佈,如下示意圖:

figure_6-3

這個 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 partitioningterm-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,建立完成後如下圖:

figure_6-4

可以看到這個 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 裡,如下圖:

figure_6-5

可以看到我們的紅色二手車 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。

tshine73
tshine73
文章: 50

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *