iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 27
1
AI & Data

資料工程師修煉之路系列 第 27

[Day 27] Partitioning (1) - Partitioning of key-value data

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

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

Partitioning and Replication

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

figure_6-1

每一個節點都能為 partition 的 leader 或 follower,其中做的事情就全部跟 Day 21 ~ Day 26 討論的 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 (Day 9),這個好處就是做範圍查詢非常快;然而,它的缺點就是某些操作會讓 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 中的排序,這個在一對多 (Day 4) 的資料關係上好處尤其明顯,例如在一個社群網站,每一個 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 個數字)。


上一篇
[Day 26] Replication (4-3) - Leaderless Replication - Detecting Concurrent Writes & 結論
下一篇
[Day 28] Partitioning (2) - Partitioning and Secondary Indexes
系列文
資料工程師修煉之路30

尚未有邦友留言

立即登入留言