作者：晨義
01 Hash分區 vs. Range分區
使用者在使用分布式資料庫時，最想要的是既能将計算壓力均攤到不同的計算節點(CN)，又能将資料盡量散列在不同的存儲節點(DN)，讓系統的存儲壓力均攤到不同的DN。對于将計算壓力均攤到不同的CN節點，業界的方案一般比較統一，通過負載均衡排程，将業務的請求均勻地排程到不同的CN節點；對于如何将資料打散到DN節點，不同的資料庫廠商有不同政策，主要是兩種流派：按拆分鍵Hash分區和按拆分鍵Range分區，DN節點和分片之間的對應關系是由資料庫存儲排程器來處理的，一般隻要資料能均勻打散到不同的分區，那麼DN節點之間的資料基本就是均勻的。如下圖所示，左邊是表A按照列PK做Hash分區的方式建立4個分區，右邊是表A按照列PK的值做Range分區的方式也建立4個分區：
按照Hash分區的方式，表A的資料會随機的散落在4個分區中，這四個分區的資料之間沒有什麼的依賴關系，這種方式的優點是：
- 隻要分區鍵的區分度高，資料一定能打散；
- 不管是随機寫入/讀取還是按PK順序寫入/讀取，流量都能均勻地分布到這個4個分區中。
Hash分區的缺點是，範圍查詢非常低效。由于資料随機打散到不同分片列，是以對于範圍查詢隻能通過全部掃描才能找到全部所需的資料，隻有等值查詢才能做分區裁剪。
按照Range分區的方式，根據定義，表A會被切分成4個分區，pk為1～1000範圍内的值散落到分區1，pk為1001～2000範圍内的值散落到分區2，pk為2001～3000範圍内的值散落到分區3，pk為3001～4000範圍内的值散落到分區4，由于資料在分區内是連續的，是以Range分區有個很好的特性就是範圍查詢很高效，例如：
select * from A where PK >2 and PK < 500 對于這個查詢我們隻有掃描分區1就可以，其他分區可以裁剪掉。
Range分區方式的缺點是：
- 如果各個分區範圍的資料不均衡，例如pk為[1,1000]的資料隻有10條，而pk為[1001,2000]的資料有1000條，就會發生資料傾斜。是以資料能不能均衡散列跟資料的分布性有關。
- 對于按照拆分列（如例子中的PK列）順序讀取或者寫入，那麼讀或許寫的流量永遠都在最後一個分區，最後一個分片将成為熱點分片。
02 預設拆分方式
為了讓使用者能用較小代價從單機資料庫到分布式資料庫的演進，将原有資料表的schema結構導入到分布式資料系統中，再将資料導入就可以将現有表的資料打散到不同的DN節點，而不需要像我們前面例子中一樣，額外添加
partition by hash/range
這樣的語句，一般的分布式資料都會按照某種預設政策将資料打散。業界有預設兩種政策，一種是預設按主鍵Hash拆分（如yugabyteDB），一種是預設按主鍵Range拆分(如TiDB)。這兩種拆分方式各有什麼優缺點，在PolarDB-X中我們采取什麼樣的政策？我們一起來探索一下。
2.1 主鍵Hash拆分
預設按主鍵Hash拆分，意味着使用者在建立表的時候不需要顯式指定拆分方式，會自動将插入資料庫每一行的主鍵通過hash散列後得到一個HashKey，再根據一定的政策将這個HashKey映射到特定的DN節點，進而實作将資料散列到不同的DN節點的目的。
常見的HashKey和DN的映射政策有兩種方式，按Hash得到的結果取模 (hashKey % n) 和 一緻性Hash（将hashKey劃分成不同的range，每個range和不同的DN對應）。
按Hash結果(hashKey % n)取模
這裡的n是存儲節點的數量，這個方法很簡單，就是将拆分鍵的值按照hash function計算出一個hashKey後，将這個hashKey對存儲節點數量n取模得到一個值，這個值就是存儲節點的編号。是以資料和DN節點的具體的映射關系如下：
DN = F(input) ==> DN = Hash(pk) % n
例如系統中有4個DN節點，假如插入的行的pk=1，hash(1)的結果為200，那麼這一行最終将落在第0個DN節點（200%4=0）。
按hash key取模的方法優點是：使用者能夠根據hashkey的值和DN的數量可以精準計算出資料落在哪個DN上，可以靈活地通過hint控制從哪個DN讀寫資料。
按hash key取模的方法缺點是，當往叢集增加或者減少DN節點的時候，由于DN的數目就是hash取模的n的值，是以隻要發生DN節點的變化都需要将原有的資料rehash 重新打散到現有的DN節點，代價是非常大的。同時這種分區方式對于範圍查詢不友好，因為資料按hashKey散列到不同的DN，隻有全表掃描之後才能找到所需資料。
一緻性Hash
一緻性Hash是一種特殊的Hash算法，先根據拆分鍵（主鍵）的值按照hash function計算一個hashKey，然後再将hashKey定位到對應的分片的分區方式，效果上類似于 Range By (hashFunction(pk)) 。假設計算出來的HashKey的大小全部都是落在[0x0,0xFFFF]區間内，目前系統有4個DN節點，建表可以預設建立4個分區，那麼每個分區就可以配置設定到不同的DN節點，每個分區對應的區間如下圖：
0x～0x4000(左開右合區間)
0x4000～0x8000
0x8000~0xc000
0xc000~0x10000 分區和DN之間的對應關系作為表結構的中繼資料儲存起來，這樣我們得到主鍵的HashKey之後，根據這個HashKey的值的範圍和分區的中繼資料資訊做個二分查找，就可以計算出該主鍵所在的行落在哪個區分，具體的計算公式如下：
DN = F(input) ==> DN = BiSearch(Hash(pk))
一緻性Hash的方法優點是，當添加DN節點時，我們可以将部分分片資料通過分裂或者遷移的方式挪到新的DN，同時更新一下表的中繼資料，其他的分片資料無需變化；當減少DN節點時，也隻需要将待删除的DN節點上的資料遷移到其他節點同時更新一下中繼資料即可，非常靈活。一緻性Hash的方法缺點是對範圍查詢也不友好。
2.2 主鍵Range拆分
主鍵Range拆分的方式和一緻性Hash的本質差別在于，一緻性Hash是對拆分鍵的Hash後得到HashKey，按這個HashKey的取值範圍切分成不同的分區，主鍵Range拆分是按将拆分鍵的實際值的取值範圍拆分不同的分區。對按照主鍵拆分的表，優點是範圍查詢非常高效，因為PK相鄰的資料分區也是相同或者相鄰的；還可以實作快速删除，例如對于是基于時間range分區的表，我們可以很輕松地将某個時間點之前的資料全部删掉，因為隻需要将對應的分區删除就可以了，其他分區的資料可以保持不變，這些特性都是按hash分區無法做到的；缺點是在使用自增主鍵并且連續插入的場景下，最後一個分片一定會成為寫入熱點。
2.3 PolarDB-X的預設拆分方式
了解了這兩種預設的主鍵拆分方式後我們來談談PolarDB-X是如何取舍的。本質上範圍查詢和順序寫入是個沖突點，如果要支援高效的範圍查詢，那麼在按主鍵遞增順序寫入就一定會成為熱點，畢竟範圍查詢之是以高效是因為相鄰的主鍵在存儲實體位置也是相鄰的，存儲位置相鄰意味着按主鍵順序寫入一定會隻寫最後一個分片。對于OLAP的場景，可能問題不大， 畢竟資料主要的場景是讀，但對于OLTP場景，就不一樣了，很多業務需要快速生成一個唯一的ID，通過業務系統生成一個UUID的方式是低效的，存儲代價也比AUTO_INCREMENT列大。
對一個主鍵做範圍查詢場景不是很常見，除非這個主鍵是時間類型，例如某訂單表按照建立一個主鍵為gmt_create的時間類型，為了高效查找某段時間範圍内的訂單，可能會有範圍查詢的訴求。
基于以上分析，在PolarDB-X中我們是預設按主鍵Hash拆分，在Hash算法的選擇中，我們選用的是一緻性Hash的路由政策，因為我們認為在分布式資料庫系統，節點的變更、分區的分裂合并是很常見的。前面分析過使用Hash取模的方式對于這種操作代價太大了，一緻性Hash能保證我們分區的分裂合并，增删DN節點的代價做到和Range分區一樣，能做到按需移動資料，而不需要全部的rehash。
特别的，對于主鍵是時間類型，我們預設是按時間取YYYYDD表達式作用于pk後再按一緻性Hash打散，這樣做的目的是同一天的資料會落在同一個分區，資料能以天為機關打散，這種方式對于按主鍵（時間）做範圍查詢是高效的，前面我們提到過，對于以時間為主鍵的表，範圍查詢是個強訴求，同時能更高效将曆史資料（例如，一年前的資料）歸檔。
03 table group
在PolarDB-X中，為加速SQL的執行效率，優化器會将分區表之間Join操作優化為Partition-Wise Join來做計算下推。但是，當分區表的拓撲發生變更後，例如分區發生分裂或者合并後，原本分區方式完全相同的兩張分區表，就有可能出現分區方式不一緻，這導緻這兩張表之間的計算下推會出現失效，進而對業務産生直接影響。
對于以下的兩個表t1和t2，由于它們的分區類型/拆分鍵類型/分區的數目等都是一緻，我們認為這兩個表的分區規則是完全一緻的。
create table t1 (c1 int auto_increment, c2 varchar(20), c3 int, c4 date, primary key(c1))
PARTITION BY HASH (c1) partition 4
create table t2 (c2 int auto_increment, c2 varchar(20), primary key(c2))
PARTITION BY HASH (c2) partition 4 是以在這兩個表上，執行sql1：select t1.c1, t2.c1 from t1, t2 on t1.c1 = t2.c2，對于這種按照分區鍵做equi-join的sql，PolarDB-X會優化為Partition-Wise Join将其下推到存儲節點将join的結果直接傳回給CN，而無需将資料拉取到CN節點再做join，進而大大降低join的代價（io和計算的代價都大大得減少）。
但是如果t1表的p1發生了分裂，分區數目将從4個變成了5個，這時候sql1就不能再下推了，因為t1和t2的分區方式不完整一緻了，左右表join所需的資料發生在多個DN節點，必須将資料從DN節點拉取到CN節點才能做join了。
為了解決分區表在分裂或合并過程中導緻的計算下推失效的問題，我們創造性地引入了表組（Table Group）和分區組（partition group）的概念，允許使用者将兩張及以上的分區表分區定義一緻的表劃分到同一個表組内，在同一個表組的所有表的分區規則都是一緻的，相同規則的分區屬于同一個分區組，在一個分區組的所有分區都在同一個DN節點（join下推的前提），屬于同一個表組的分區表的分裂合并遷移都是以分區組為基本機關，要麼同時分裂，要麼同時合并，要麼同時遷移，總是保持同步，即使表組内的分區表的分區出現變更，也不會對表組内原來能下推的join産生影響。
特别的，為了減少使用者的學習成本，一開始使用者并不需要關注表組，我們會預設将每個表都單獨放到一個表組裡，使用者并不用感覺它。隻有在需要性能調優或者業務中某些表需要穩定地做join下推時，作為一種最佳實踐，這時候使用者才需要考慮表組。
對于表組我們支援如下的管理方式有：
表組分區組分裂：
一般的，在PolarDB-X中，一個分區表的大小建議維持在500W以内，當一個分區的資料量太大，我們可以對分區進行分裂操作，
alter tablegroup split partition p1 to p10, p11 表組分區組合并：
當一個分區表的某些分區的行數大小遠小于500W時，我們可以對分區進行合并操作，
alter tablegroup merge partition p1,p2 to p10 表組分區組的遷移：
前面我們提到在分布式資料庫系統中，節點的增加或者減少是很常見的事情，例如某商家為了線上促銷，會臨時增加一批節點，在促銷結束後希望将節點縮容回平時正常的量。PolarDB-X中我們是如何支援這種訴求的？
PolarDB-X的CN節點是無狀态的，增删過程隻需往系統注冊，不涉及資料移動。這裡主要讨論增删DN節點，當使用者通過升配增加DN節點後，這個DN節點一開始是沒有任何資料的，我們怎麼快速讓這個新的DN節點能分攤系統的流量呢？在DN節點準備好後，我們背景的管控系統可以通過PolarDB-X提供的分區遷移指令按需批量将資料從老DN節點遷移到新的DN，具體指令如下：
alter tablegroup move partition p1,p2 to DNi 将表D加入表組tg1：
alter tablegroup tg1 add D 将表D加入表組tg1有個前提條件，就是表D的分區方式要和tg1裡的表完全一緻，同時如果對應分區的資料和tg1對應的分區組不在同一個DN節點，會觸發表D的資料遷移。
将表B從表組tg中移除：
alter tablegroup tg1 remove B 04 其他分區方式
前面我們對比了一緻性Hash和Range的差別，并且我們采用預設按主鍵拆分的政策，盡管如此我們還是實作了Range分區和List分區以滿足客戶不同場景的不同訴求
4.1 Range分區
特别提一下，range分區除了上面提到的範圍查詢優化的優點外，在PolarDB-X中，我們的存儲引擎不光支援Innodb，還有我們自研的X-Engine，X-Engine的LSM-tree的分層結構支援混合存儲媒體，通過range分區可以按需将業務任務的是“老分區”的資料遷移到X-Engine，對于遷移過來的冷資料，可以儲存在比較廉價的HDD硬碟中，對于熱資料可以存儲在SSD，進而實作冷熱資料的分離。
4.2 List分區
List分區是實作按照離散的值劃分分區的一種政策，有了list分區的支援，那麼在PolarDB-X中就可以實作Geo Partition的方案，例如對于某個系統，裡面有全球各個國家的資料，那麼就可以按照歐美-亞太-非洲等區域次元拆分，将不同的分區部署在不同地域的實體機房，将資料放在離使用者更近的地域，減少通路延遲。
CREATE TABLE users （ country varchar, id int, name varchar, …)
PARTITION BY LIST (country) (
PARTITION Asia VALUES IN ('CN', 'JP', …),
PARTITION Europe VALUES IN ('GE','FR',..),
....
) 4.3 組合分區
前面提到，在PolarDB-X中我們支援Hash/Range/List分區方式，同時我們也支援這三種分區任意兩兩組合的二級分，以滿足不同業務的不同訴求。下面舉幾個常見的例子來闡述，如何通過這三種分區的組合解決不同的問題。
場景1：用顯式的建立list分區表，例如将省份作為拆分鍵，将不同省份的資料儲存在不同的分片，進而可以将不同身份的分片儲存在不同的DN，這樣做的好處是可以做到按省份資料隔離，然後可以按照區域将不同省份的資料儲存在就近的資料中心（如華南/華北資料中心）。但是這種分區有個缺點，就是力度太粗了，每個省份一個分區，很容易就産生一個很大的分區，而且還沒發直接分裂，對于這種場景，可以采用list+hash的組合，一級分區用list劃分後，分區内再根據主鍵hash，就可以将資料打散的非常均勻，如：
create table AA (pk bigint, provinceName varchar,...) PARTITION BY LIST (provinceName)
SUBPARTITION BY HASH (pk)
SUBPARTITIONS 2
( PARTITION p1 VALUES ('Guangdong','Fujian'),
PARTITION p2 VALUES ('Beijing','HeBei','Tijin')
); 一級分區p1/p2是采用list分區形式，可以将p1的子分區固定在region1，p2的子分區固定在region2，如下圖所示：
場景2：單key熱點，當一個key的資料很多時，該key所在的分片會很大，造成該分片可能成為一個熱點，PolarDB-X中預設按主鍵拆分，并不會出現此類熱點，是以熱點key來自二級索引，因為主表采用按主鍵Hash拆分，二級索引表的拆分鍵就會選擇和主表不一樣的列，對于按非主鍵列拆分就可能産生熱點key。對于熱點key，PoalrDB-X首先會将熱點key通過分裂的方式，放到一個單獨的分片内，随着該分片的負載變大，PolarDB-X會将該分片所在的DN上的其他分片逐漸遷移到其他DN上，最終，這個分片将獨占一個DN節點。如果該分片獨占一個DN節點後，依然無法滿足要求，PolarDB-X會對這個分區二級散列成多個分片，進而這個熱點key就可以遷移到多台DN上。當分片被打散後，對該key的查詢需要聚合來自多個DN的多個分片的資料，在查詢上會有一定的性能損失。PolarDB-X對分片的管理比較靈活，對同一個表的不同分片，允許使用不同打散政策。例如對p1分片打散成2個分片，對p2分片打散成3個分片，對p4分片不做打散，避免熱點分片對非熱點分片的影響。
05 小結
PolarDB-X提供了預設按主鍵Hash分區的分區管理政策，同時為了滿足不同業務的需求也支援了Range和List分區，這三種分區政策可以靈活組合，支援二級分區。為了計算下推，引入了表組的概念，滿足不同業務的需求。
Reference
[1]
Online, Asynchronous Schema Change in F1. [2] https://docs.oracle.com/en/database/oracle/oracle-database/21/vldbg/ [3] https://dev.mysql.com/doc/refman/5.7/en/partitioning-management.html
【相關閱讀】
分布式資料庫如何實作 Join？ PolarDB-X 讓“Online DDL”更Online PolarDB-X SQL限流，為您的核心業務保駕護航 通篇幹貨！縱觀 PolarDB-X 并行計算架構