為什么80%的碼農都做不了架構師？>>> ??

版權聲明：本文由本人撰寫并發表于2012年9月份的《程序員》雜志，原文題目《一種支持自由規劃的Sharding擴容方案——主打無須數據遷移和修改路由代碼》，此處作為本系列的第五篇文章進行轉載, 本文版權歸《程序員》雜志所有，未經許可不得轉載！

作為一種數據存儲層面上的水平伸縮解決方案，數據庫Sharding技術由來已久，很多海量數據系統在其發展演進的歷程中都曾經歷過分庫分表的Sharding改造階段。簡單地說，Sharding就是將原來單一數據庫按照一定的規則進行切分，把數據分散到多臺物理機（我們稱之為Shard)上存儲，從而突破單機限制，使系統能以Scale-Out的方式應對不斷上漲的海量數據，但是這種切分對上層應用來說是透明的，多個物理上分布的數據庫在邏輯上依然是一個庫。實現Sharding需要解決一系列關鍵的技術問題，這些問題主要包括：切分策略、節點路由、全局主鍵生成、跨節點排序/分組/表關聯、多數據源事務處理和數據庫擴容等。關于這些問題可以參考筆者的博客專欄http://blog.csdn.net/column/details/sharding.html?本文將重點圍繞“數據庫擴容”進行深入討論，并提出一種允許自由規劃并能避免數據遷移和修改路由代碼的Sharding擴容方案。

Sharding擴容——系統維護不能承受之重

任何Sharding系統，在上線運行一段時間后，數據就會積累到當前節點規模所能承載的上限，此時就需要對數據庫進行擴容了，也就是增加新的物理結點來分攤數據。如果系統使用的是基于ID進行散列的路由方式，那么團隊需要根據新的節點規模重新計算所有數據應處的目標Shard，并將其遷移過去，這對團隊來說無疑是一個巨大的維護負擔；而如果系統是按增量區間進行路由(如每1千萬條數據或是每一個月的數據存放在一個節點上 )，雖然可以避免數據的遷移，卻有可能帶來“熱點”問題，也就是近期系統的讀寫都集中在最新創建的節點上(很多系統都有此類特點：新生數據的讀寫頻率明顯高于舊有數據)，從而影響了系統性能。面對這種兩難的處境，Sharding擴容顯得異常困難。

一般來說，“理想”的擴容方案應該努力滿足以下幾個要求：

?最好不遷移數據 （無論如何，數據遷移都是一個讓團隊壓力山大的問題）

允許根據硬件資源自由規劃擴容規模和節點存儲負載

能均勻的分布數據讀寫，避免“熱點”問題

保證對已經達到存儲上限的節點不再寫入數據

目前，能夠避免數據遷移的優秀方案并不多，相對可行的有兩種，一種是維護一張記錄數據ID和目標Shard對應關系的映射表，寫入時，數據都寫入新擴容的Shard，同時將ID和目標節點寫入映射表，讀取時，先查映射表，找到目標Shard后再執行查詢。該方案簡單有效，但是讀寫數據都需要訪問兩次數據庫，且映射表本身也極易成為性能瓶頸。為此系統不得不引入分布式緩存來緩存映射表數據，但是這樣也無法避免在寫入時訪問兩次數據庫，同時大量映射數據對緩存資源的消耗以及專門為此而引入分布式緩存的代價都是需要權衡的問題。另一種方案來自淘寶綜合業務平臺團隊，它利用對2的倍數取余具有向前兼容的特性（如對4取余得1的數對2取余也是1）來分配數據，避免了行級別的數據遷移，但是依然需要進行表級別的遷移，同時對擴容規模和分表數量都有限制。總得來說，這些方案都不是十分的理想，多多少少都存在一些缺點，這也從一個側面反映出了Sharding擴容的難度。

取長補短，兼容并包——一種理想的Sharding擴容方案

如前文所述，Sharding擴容與系統采用的路由規則密切相關：基于散列的路由能均勻地分布數據，但卻需要數據遷移，同時也無法避免對達到上限的節點不再寫入新數據；基于增量區間的路由天然不存在數據遷移和向某一節點無上限寫入數據的問題，但卻存在“熱點”困擾。我們設計方案的初衷就是希望能結合兩種路由規則的優勢，摒棄各自的劣勢，創造出一種接近“理想”狀態的擴容方式，而這種方式簡單概括起來就是：全局按增量區間分布數據，使用增量擴容，無數據遷移，局部使用散列方式分散數據讀寫，解決“熱點”問題，同時對Sharding拓撲結構進行建模，使用一致的路由算法，擴容時只需追加節點數據，不再修改散列邏輯代碼。

原理

首先，作為方案的基石，為了能使系統感知到Shard并基于Shard的分布進行路由計算，我們需要建立一個可以描述Sharding拓撲結構的編程模型。按照一般的切分原則，一個單一的數據庫會首先進行垂直切分，垂直切分只是將關系密切的表劃分在一起，我們把這樣分出的一組表稱為一個Partition。 接下來，如果Partition里的表數據量很大且增速迅猛，就再進行水平切分，水平切分會將一張表的數據按增量區間或散列方式分散到多個Shard上存儲。在我們的方案里，我們使用增量區間與散列相結合的方式，全局上，數據按增量區間分布，但是每個增量區間并不是按照某個Shard的存儲規模劃分的，而是根據一組Shard的存儲總量來確定的，我們把這樣的一組Shard稱為一個ShardGroup，局部上，也就是一個ShardGroup內，記錄會再按散列方式均勻分布到組內各Shard上。這樣，一條數據的路由會先根據其ID所處的區間確定ShardGroup，然后再通過散列命中ShardGroup內的某個目標Shard。在每次擴容時，我們會引入一組新的Shard，組成一個新的ShardGroup，為其分配增量區間并標記為“可寫入”，同時將原有ShardGroup標記為“不可寫入”，于是新生數據就會寫入新的ShardGroup，舊有數據不需要遷移。同時，在ShardGroup內部各Shard之間使用散列方式分布數據讀寫，進而又避免了“熱點”問題。最后，在Shard內部，當單表數據達到一定上限時，表的讀寫性能就開始大幅下滑，但是整個數據庫并沒有達到存儲和負載的上限，為了充分發揮服務器的性能，我們通常會新建多張結構一樣的表，并在新表上繼續寫入數據，我們把這樣的表稱為“分段表”（Fragment Table）。不過，引入分段表后所有的SQL在執行前都需要根據ID將其中的表名替換成真正的分段表名，這無疑增加了實現Sharding的難度，如果系統再使用了某種ORM框架，那么替換起來可能會更加困難。目前很多數據庫提供一種與分段表類似的“分區”機制，但沒有分段表的副作用，團隊可以根據系統的實現情況在分段表和分區機制中靈活選擇。總之，基于上述切分原理，我們將得到如下Sharding拓撲結構的領域模型：

圖1. Sharding拓撲結構領域模型

在這個模型中，有幾個細節需要注意：ShardGroup的writable屬性用于標識該ShardGroup是否可以寫入數據，一個Partition在任何時候只能有一個ShardGroup是可寫的，這個ShardGroup往往是最近一次擴容引入的；startId和endId屬性用于標識該ShardGroup的ID增量區間；Shard的hashValue屬性用于標識該Shard節點接受哪些散列值的數據；FragmentTable的startId和endId是用于標識該分段表儲存數據的ID區間。

確立上述模型后，我們需要通過配置文件或是在數據庫中建立與之對應的表來存儲節點元數據，這樣，整個存儲系統的拓撲結構就可以被持久化起來，系統啟動時就能從配置文件或數據庫中加載出當前的Sharding拓撲結構進行路由計算了（如果結點規模并不大可以使用配置文件，如果節點規模非常大，需要建立相關表結構存儲這些結點元數據。從最新的Oracle發布的《面向大規模可伸縮網站基礎設施的MySQL參考架構》白皮書一文的“超大型系統架構參考”章節給出的架構圖中我們可以看到一種名為：Shard Catalog的專用服務器，這個其實是保存結點配置信息的數據庫），擴容時只需要向對應的文件或表中加入相關的節點信息重啟系統即可，不需要修改任何路由邏輯代碼。

示例

讓我們通過示例來了解這套方案是如何工作的。

階段一：初始上線

假設某系統初始上線，規劃為某表提供4000W條記錄的存儲能力，若單表存儲上限為1000W條，單庫存儲上限為2000W條，共需2個Shard，每個Shard包含兩個分段表，ShardGroup增量區間為0-4000W，按2取余分散到2個Shard上，具體規劃方案如下：

圖2. 初始4000W存儲規模的規劃方案

與之相適應，Sharding拓撲結構的元數據如下：

圖3. 對應Sharding元數據

階段二：系統擴容

經過一段時間的運行，當原表總數據逼近4000W條上限時，系統就需要擴容了。為了演示方案的靈活性，我們假設現在有三臺服務器Shard2、Shard3、Shard4，其性能和存儲能力表現依次為Shard2<Shard3<Shard4，我們安排Shard2儲存1000W條記錄，Shard3儲存2000W條記錄，Shard4儲存3000W條記錄，這樣，該表的總存儲能力將由擴容前的4000W條提升到10000W條，以下是詳細的規劃方案：

圖4. 二次擴容6000W存儲規模的規劃方案

相應拓撲結構表數據下：

圖5. 對應Sharding元數據

從這個擴容案例中我們可以看出該方案允許根據硬件情況進行靈活規劃，對擴容規模和節點數量沒有硬性規定，是一種非常自由的擴容方案。

增強

接下來讓我們討論一個高級話題：對“再生”存儲空間的利用。對于大多數系統來說，歷史數據較為穩定，被更新或是刪除的概率并不高，反映到數據庫上就是歷史Shard的數據量基本保持恒定，但也不排除某些系統其數據有同等的刪除概率，甚至是越老的數據被刪除的可能性越大，這樣反映到數據庫上就是歷史Shard隨著時間的推移，數據量會持續下降，在經歷了一段時間后，節點就會騰出很大一部分存儲空間，我們把這樣的存儲空間叫“再生”存儲空間，如何有效利用再生存儲空間是這些系統在設計擴容方案時需要特別考慮的。回到我們的方案，實際上我們只需要在現有基礎上進行一個簡單的升級就可以實現對再生存儲空間的利用，升級的關鍵就是將過去ShardGroup和FragmentTable的單一的ID區間提升為多重ID區間。為此我們把ShardGroup和FragmentTable的ID區間屬性抽離出來，分別用ShardGroupInterval和FragmentTableIdInterval表示，并和它們保持一對多關系。

圖6. 增強后的Sharding拓撲結構領域模型

讓我們還是通過一個示例來了解升級后的方案是如何工作的。

階段三：不擴容，重復利用再生存儲空間

假設系統又經過一段時間的運行之后，二次擴容的6000W條存儲空間即將耗盡，但是由于系統自身的特點，早期的很多數據被刪除，Shard0和Shard1又各自騰出了一半的存儲空間，于是ShardGroup0總計有2000W條的存儲空間可以重新利用。為此，我們重新將ShardGroup0標記為writable=true，并給它追加一段ID區間：10000W-12000W，進而得到如下規劃方案：

圖7. 重復利用2000W再生存儲空間的規劃方案

相應拓撲結構的元數據如下：

圖8. 對應Sharding元數據

小結

這套方案綜合利用了增量區間和散列兩種路由方式的優勢，避免了數據遷移和“熱點”問題，同時，它對Sharding拓撲結構建模，使用了一致的路由算法，從而避免了擴容時修改路由代碼，是一種理想的Sharding擴容方案。

相關閱讀：

數據庫分庫分表(sharding)系列(五) 一種支持自由規劃無須數據遷移和修改路由代碼的Sharding擴容方案

數據庫分庫分表(sharding)系列(四) 多數據源的事務處理

數據庫分庫分表(sharding)系列(三) 關于使用框架還是自主開發以及sharding實現層面的考量

數據庫分庫分表(sharding)系列(二) 全局主鍵生成策略

數據庫分庫分表(sharding)系列(一) 拆分實施策略和示例演示

關于垂直切分Vertical Sharding的粒度

數據庫Sharding的基本思想和切分策略

轉載于:https://my.oschina.net/boltwu/blog/425238

總結

以上是生活随笔為你收集整理的数据库分库分表(sharding)系列(五) 一种支持自由规划无须数据迁移和修改路由代码的Sharding扩容方案...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。