聊聊partition的方式

序

本文主要聊一下開源主流產(chǎn)品的partition方式。

partition

一般來說，數(shù)據(jù)庫的繁忙體現(xiàn)在：不同用戶需要訪問數(shù)據(jù)集中的不同部分，這種情況下，我們把數(shù)據(jù)的各個部分存放在不同的服務(wù)器/節(jié)點中，每個服務(wù)器/節(jié)點負責(zé)自身數(shù)據(jù)的讀取與寫入操作，以此實現(xiàn)橫向擴展，這種技術(shù)成為分片，即sharding。

理想情況下，不同的節(jié)點服務(wù)于不同的用戶，每個用戶只需要與一個節(jié)點通信，并且很快就能獲得服務(wù)器的響應(yīng)。當然理想情況比較罕見，為了獲得近乎理想的效果，必須保證需要同時訪問的那些數(shù)據(jù)都存放在同一個節(jié)點上，而且節(jié)點必須排布好這些數(shù)據(jù)塊，使得訪問速度最優(yōu)。

分片可以極大地提高讀取性能，但對于要頻繁寫的應(yīng)用，幫助不大。另外，分片對改善故障恢復(fù)能力并沒有幫助，但是它減少了故障范圍，只有訪問這個節(jié)點的那些用戶才會受影響，其余用戶可以正常訪問。雖然數(shù)據(jù)缺失了一部分，但是還是其余部分還是可以正常運轉(zhuǎn)。

問題點

1.怎樣分片/路由

怎樣存放數(shù)據(jù)，才能保證用戶基本上只需要從一個節(jié)點獲取它。如果使用的是面向聚合的數(shù)據(jù)庫而非面向元組的數(shù)據(jù)庫，那么就非常容易解決了。之所以設(shè)計聚合這一結(jié)構(gòu)，就是為了把那些經(jīng)常需要同時訪問的數(shù)據(jù)存放在一起。因此，可以把聚合作為分布數(shù)據(jù)的單元。

另外還要考慮的是：如何保持負載均衡。即如何把聚合數(shù)據(jù)均勻地分布在各個節(jié)點中，讓它們需要處理的負載量相等。負載分布情況可能隨著時間變化，因此需要一些領(lǐng)域特定的規(guī)則。比如有的需要按字典順序，有的需要按逆域名序列等。
很多NoSQL都提供自動分片（auto-sharding）功能，可以讓數(shù)據(jù)庫自己負責(zé)把數(shù)據(jù)分布到各個分片，并且將數(shù)據(jù)訪問請求引導(dǎo)到適當?shù)姆制稀?/p>

2.怎樣rebalance

在動態(tài)增減機器或partition的情況下，如果重新rebalance，使數(shù)據(jù)分布均勻或者避免熱點訪問

分片方式

這里主要分為兩大類，一類是哈希分片(hash based partitionning)，一類是范圍分片(range based partitioning)

1.哈希分片(hash based partitionning)

通過哈希函數(shù)來進行數(shù)據(jù)分片，主要有Round Robbin、虛擬桶、一致性哈希三種算法。

A、Round Robbin
俗稱哈希取模算法，H(key) = hash(key) mode K（其中對物理機進行從0到K-1編號，key為某個記錄的主鍵，H（key）為存儲該數(shù)據(jù)的物理機編號）。好處是簡單，缺點是增減機器要重新hash，缺乏靈活性。它實際上是將物理機和數(shù)據(jù)分片兩個功能點合二為一了，因而缺乏靈活性。
B、虛擬桶
membase在待存儲記錄和物理機之間引入了虛擬桶，形成兩級映射。其中key-partition映射采用哈希函數(shù)，partition-machine采用表格管理實現(xiàn)。新加入機器時，只需要將原來一些虛擬桶劃分給新的機器，只要修改partition-machine映射即可，具有靈活性。
C、一致性哈希
一致性哈希是分布式哈希表的一種實現(xiàn)算法，將哈希數(shù)值空間按照大小組成一個首尾相接的環(huán)狀序列，對于每臺機器，可以根據(jù)IP和端口號經(jīng)過哈希函數(shù)映射到哈希數(shù)值空間內(nèi)。通過有向環(huán)順序查找或路由表（Finger Table）來查找。對于一致性哈?？赡茉斐傻母鱾€節(jié)點負載不均衡的情況，可以采用虛擬節(jié)點的方式來解決。一個物理機節(jié)點虛擬成若干虛擬節(jié)點，映射到環(huán)狀結(jié)構(gòu)的不同位置。

哈希分片的好處是可以使數(shù)據(jù)均勻分布，但是可能造成數(shù)據(jù)無序不方面range

mongo2.4版本+支持hash partition

2.范圍分片(range based partitioning)

這個是根據(jù)key排序來分布的，比如字典按24個首字母來分，這個的好處是方便range，但是容易造成數(shù)據(jù)分布不均勻以及熱點訪問問題(比如個別節(jié)點的數(shù)據(jù)訪問量/查詢/計算量大，造成負載特別高)。

Bigtable，hbase、2.4版本之前的mongo都使用此方式。

索引分片策略(secondary indexes)

除了數(shù)據(jù)本身要分片外，索引也需要分片。比較著名的兩個反向索引分片策略就是document-based partitioning以及term-based partitioning。然后再此兩個基本的策略之上衍生出了hybrid的方案。

1.local index(document-based partitioning)

也稱作document-based partitioning.在每個partition本地維護一份關(guān)于本地數(shù)據(jù)的反向索引。這種方式的話，主要使用的是scatter/gather模式，即每次查詢需要發(fā)送請求給所有的partition，然后每個partition根據(jù)本地的索引檢索返回，之后匯總得出結(jié)果。

  • 好處
    簡單好維護
  • 缺點
    查詢比較費勁，比如有n個partition，要查top k，則每個partition都要查top k，總共需要n*k份文檔被匯總。

mongo,cassandra,es,solr采用此方案

2.global index(term-based partitioning)

也稱作term-based partitioning，這種方式的話，創(chuàng)建的索引不是基于partition的部分數(shù)據(jù)，而是基于所有數(shù)據(jù)來索引的。只不過這些全局索引使用range-based partitioning的方式再分布到各個節(jié)點上。

  • 好處
    讀取效率高，因為索引是有序的，基于range parititioning，非?？焖僬业剿饕?，而且這些索引是全局的，立馬就可以定位到文檔的位置。
  • 缺點
    寫入成本比較高，每個文檔的寫入都需要維護/更新全局的索引。另外一個缺點就是range-partitioning本身的帶來的缺點，容易造成數(shù)據(jù)分布不均勻，造成熱點，影響吞吐量。

dynamodb,riak支持此方案

rebalance

當partition所在節(jié)點壞掉，或者新增機器的時候，這個時候就涉及到partition的rebalance。原來本應(yīng)該請求這個node的，現(xiàn)在都需要轉(zhuǎn)移請求另外一個node的過程叫做rebalancing。

rebalancing的目標

  • 均分數(shù)據(jù)存儲以及讀寫請求，避免熱點
  • rebalancing期間不影響正常讀寫
  • 要盡量快而且盡量少的網(wǎng)絡(luò)及IO負載來完成

rebalance策略

直接哈希(模數(shù)固定)

即key-machine的直接映射，這個的缺點就是：增減機器要重新hash，缺乏靈活性。

兩級映射(partition hashing，固定partition數(shù)目)

為了提升直接哈希的靈活性，引入了兩級映射，即key-partition，partition-matchine/node這樣兩級，通過partition來解耦key跟machine/node的關(guān)聯(lián)。對于新加入機器時，只需要將原來各個node的一些partition劃分給新的機器，只要修改partition-machine映射即可，具有靈活性。

  • 好處
    相對于直接哈希來講，節(jié)點增減的時候，只需要調(diào)整partiton-matchine的映射關(guān)系，客戶端無需重新路由。

  • 缺點
    固定partition的話，需要一個合理的數(shù)目，每個partition大小需要合理確定。相當于這些固定數(shù)目的partition要均分整個數(shù)據(jù)集。如果數(shù)據(jù)集不斷增長的話，如果原來partition個數(shù)太少，則每個partition大小則不斷增加，造成節(jié)點恢復(fù)/rebalance相對耗時。如果原來partition個數(shù)太多，而數(shù)據(jù)集后續(xù)增長不多，則可能造成有些partition的數(shù)據(jù)量過少，無法達到均分效果。

Elasticsearch采用此方案，在創(chuàng)建索引的時候需指定shard/partition數(shù)目以及replication的數(shù)目
Couchbase引入了vBucket的概念在這里可以理解為虛擬的paritition。


動態(tài)partition

partition的數(shù)目是動態(tài)變化的，根據(jù)設(shè)定的partition大小的閾值，來進行動態(tài)的分裂或合并。

hbase采用的就是這種方式

一致性哈希(hash ring)

一致性哈希與前兩者有些不同，因為該算法把machine/node也一起進行了hash，然后與key的哈希值一起進行區(qū)間匹配，來確定key落在哪個machine/node上面。分布式緩存用到的比較多，比如redis就是用了一致性哈希。

具體如下：

  • 將環(huán)形空間總共分成2^32個區(qū)

  • 將key跟machine采用某種哈希算法轉(zhuǎn)化為一個32位的二進制數(shù)，然后落到對應(yīng)的區(qū)間范圍內(nèi)

  • 每一個key的順時針方向最近節(jié)點，就是key所歸屬的存儲節(jié)點。

  • 好處
    節(jié)點增減的時候，整個環(huán)形空間的映射仍然會保持一致性哈希的順時針規(guī)則，所以有一小部分key的歸屬會受到影響。當節(jié)點掛掉的時候，相當于緩存未命中，下次訪問的時候重新緩存。

  • 缺點
    使用一般的hash函數(shù)的話，machine的映射分布非常不均勻，可能造成熱點，對于這種情況，引入虛擬節(jié)點來解決。也就是借鑒了兩級映射的模式，key-vnode，vnode-machine。將一個machine映射為多個vnode，然后分散到環(huán)形結(jié)構(gòu)上，這樣可以使得vnode分布均勻，然后最后每個machine的存儲也相對均勻。


不過引入虛擬節(jié)點也會有問題，當新增machine的時候，也就相當于新增多個vnode分散到環(huán)上，但是這樣子就會造成更多的范圍的key需要rebalance。

1、提升單調(diào)性（通過環(huán)形算法減少增減節(jié)點時cache的遷移成本） 2、提升平衡性（通過虛擬節(jié)點，盡可能減少節(jié)點增減帶來的cache分布不均勻問題）

小結(jié)

產(chǎn)品 partition方式 索引分片策略
redis 一致性哈希 -
elasticsearch 固定partition兩級映射 local index
mongo 2.4版本之前是范圍分片，2.4+支持hash分片 local index
kafka 固定partition -

kafka的key到partition的映射高版本支持自定義策略，如果cluster增減node，對之前創(chuàng)建的topic不生效，需要調(diào)用reassign-partitions重新分布，避免熱點

doc

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容