福利：國際頂級盛會HBaseCon Asia 2018将于8月在北京舉行，目前正免費開放申請中，更多詳情參考 https://yq.aliyun.com/promotion/631 如果你對大資料存儲、分布式資料庫、HBase等感興趣，歡迎加入我們，一起做最好的大資料線上存儲，職位參考及聯系方式： https://maimai.cn/job?webjid=1heZGIyM4&srcu=1aOrffoj1&src=app&fr=my_jobsrecruit_job
資料分布問題簡述
分布式産生的根源是“規模”，規模可了解為計算和存儲的需求。當單機能力無法承載日益增長的計算存儲需求時，就要尋求對系統的擴充方法。通常有兩種擴充方式：提升單機能力(scale up)，增加機器(scale out，水準擴充)。限于硬體技術，單機能力的提升在一個階段内是有上限的；而水準擴充在理論上可以是無限的，同時，也更廉價、更容易落地。水準擴充可以通過快速、簡單的“加機器”，有效解決業務快速增長的問題，這幾乎是現代分布式系統必備的能力。對于爆發式增長的業務，水準擴充似乎是唯一可選擇的方案。
對于存儲系統而言，原本存儲在一台機器上的資料，現在要存放在多台機器上。此時必須解決兩個問題：分片，複制。
- 資料分片(sharding)，又稱分區(partition)，将資料集“合理的”拆分成多個分片，每台機器負責其中若幹個分片。以此來突破單機容量的限制，同時也提升了整體的通路能力。另外，分片也降低了單個分片故障的影響範圍。
- 資料複制(replica)，也叫“副本”。分片無法解決單機故障丢資料的問題，是以，必然要通過備援來解決系統高可用的問題。同時，副本機制也是提升系統吞吐、解決熱點問題的重要手段。
分片和副本是正交的，這意味着我們可以隻使用其中一種或都使用，但通常都是同時使用的。因為分片解決的是規模和擴充性的問題，副本解決可靠、可用性的問題。對于一個生産可用的系統，二者必須同時具備。
從使用者/用戶端的角度看，分片和副本可以歸結為同一個問題：請求路由，即請求應該發送給哪台機器來處理。
- 讀資料時，能通過某種機制來確定有一個合适的分片/副本來提供服務
- 寫資料時，能通過同樣的機制來確定寫到一個合适的地方，并確定副本的一緻性
無論用戶端的請求是直達服務端(如HBase/cassandra)，還是通過代理(如公有雲上的基于gateway的通路方式)，請求路由都是分布式系統必須解決的問題。
無論是分片還是副本，本質上都是資料分布的展現。下面我們來看HBase的資料分布模型。
HBase的資料分布模型
HBase的資料分片按表進行，以行為粒度，基于rowkey範圍進行拆分，每個分片稱為一個region。一個叢集有多張表，每張表劃分為多個region，每台伺服器服務很多region。是以，HBase的伺服器稱為RegionServer，簡稱RS。RS與表是正交的，即一張表的region會分布到多台RS上，一台RS也會排程多張表的region。如下圖所示：
“以行為粒度”，意思是行是region劃分的最小機關，即一行資料要麼屬于A region，要麼屬于Bregion，不會被拆到兩個region中去。（對行進行拆分的方式是“垂直分庫”，通常隻能在業務層面進行，HBase是水準拆分）
HBase的副本機制是通過通過底層的HDFS實作的。是以，HBase的副本與分片是解耦的，是存儲計算分離的。這使得region可以在RS之間靈活的移動，而不需要進行資料遷移，這賦予了HBase秒級擴容的能力和極大的靈活性。
對于單個表而言，一個“好”的資料分布，應該是每個region的資料量大小相近，請求量(吞吐)接近，每台機器排程的region數量大緻相同。這樣，這張表的資料和通路能夠均勻的分布在整個叢集中，進而得到最好的資源使用率和服務品質，即達到負載均衡。當叢集進行擴容、縮容時，我們希望這種“均衡”能夠自動保持。如果資料分布未能實作負載均衡，則負載較高的機器很容易稱為整個系統的瓶頸，這台機器的響應慢，可能導緻用戶端的大部分線程都在等待這台機器傳回，進而影響整體吞吐。是以，負載均衡是region劃分和排程的重要目标。
這裡涉及到3層面的負載均衡問題：
- 資料的邏輯分布：即region劃分/分布，是rowkey到region的映射問題
- 資料的實體分布：即region在RS上的排程問題
- 通路的分布：即系統吞吐(請求)在各個RS上的分布問題，涉及資料量和通路量之間的關系，通路熱點等。
可見，一行資料的分布(找到一行資料所在的RS)，存在2個層級的路由：一是rowkey到region的路由，二是region到RS的路由。這一點是HBase能夠實作靈活排程、秒級擴容的關鍵。後面我們會詳細讨論。本文僅讨論前面兩個問題，第三個問題放在後續的文章中讨論。
基于rowkey範圍的region劃分
首先，我們來看資料的邏輯分布，即一張表如何劃分成多個region。
region劃分的粒度是行，region就是這個表中多個連續的行構成的集合。行的唯一辨別符是rowkey，是以，可以将region了解為一段連續分布的rowkey的集合。是以，稱這種方式為基于rowkey範圍的劃分。
一個region負責的rowkey範圍是一個左閉右開區間，是以，後一個region的start key是前一個region的end key。注意，第一個region是沒有start key的，最後一個region是沒有end key的。這樣，這個表的所有region加在一起就能覆寫任意的rowkey值域。如下圖所示：
上圖中，region1是第一個region，沒有startKey，region3是最後一個region，沒有endKey。圖中的region分布是比較均勻的，即每個region的行數是相當的，那麼，這個分布是怎麼得到的呢？或者說，region的邊界是如何确定的？
一般來說，region的生成有3種方式：
- 建表時進行預分區：通過對rowkey進行預估，預先劃分好region
- region分裂：手工分裂，或達到一定條件時自動分裂(如region大小超過一個門檻值)
- region合并：手工合并
建表時如果未顯式指定region分布，HBase就會隻建立一個region，這個region自然也隻能由一台機器進行排程(後面會讨論一個region由多個RS排程的情況)。那這個region的吞吐上限就是單機的吞吐上限。如果通過合理的預分區将表分成8個region，分布在8台RS上，那整表的吞吐上限就是8台機器的吞吐上限。
是以，為了使表從一開始就具備良好的吞吐和性能，實際生産環境中建表通常都需要進行預分區。但也有一些例外，比如無法預先對rowkey範圍進行預估，或者，不容易對rowkey範圍進行均勻的拆分，此時，也可以建立隻有一個region的表，由系統自己分裂，進而逐漸形成一個“均勻的”region分布。
比如一張存儲多個公司的員工資訊的表，rowkey組成是orgId + userid，其中orgId是公司的id。由于每個公司的人數是不确定的，同時也可能是差别很大的，是以，很難确定一個region中包含幾個orgId是合适的。此時，可以為其建立單region的表，然後導入初始資料，随着資料的導入進行region的自動分裂，通常都能得到比較理想的region分布。如果後續公司人員發生較大的變化，也可以随時進行region的分裂與合并，來獲得最佳分布。
字典序與rowkey比較
上一節我們提到region的rowkey範圍是一個左閉右開區間，所有落在這個範圍的rowkey都屬于這個region。為了進行這個判斷，必須将其與這個region的起止rowkey進行比較。除了region歸屬的判斷，在region内部，也需要依賴rowkey的比較規則來對rowkey進行排序。
很多人都會認為rowkey的比較非常簡單，沒有什麼讨論的必要。但正是因為簡單，它的使用才能靈活多樣，使得HBase具備無限的可能性。可以說，rowkey的比較規則是整個HBase資料模型的核心，直接影響了整個請求路由體系的設計、讀寫鍊路、rowkey設計、scan的使用等，貫穿整個HBase。對于使用者而言，深入了解這個規則及其應用有助于做出良好的表設計，寫出精準、高效的scan。
HBase的rowkey是一串二進制資料，在Java中就是一個byte[]，是一行資料的唯一辨別符。而業務的主鍵可能是有各種資料類型的，是以，這裡要解決2個問題：
- 将各種實際使用的資料類型與byte[]進行互相轉換
- 保序：byte[]形式的rowkey的排序結果與原始資料的排序結果一緻
rowkey的比較就是byte[]的比較，按字典序進行比較(二進制排序)，簡單說，就是c語言中memcmp函數。通過下面的示例，我們通過排序結果來對這一比較規則以及資料類型轉換進行了解。
（1）ascii碼的大小比較
1234 -> 0x31 32 33 34
5 -> 0x35
從ascii碼表示的數字來看，1234 > 5， 但從字典序來看，1234 < 5
（2）具有相同字首的ascii碼比較
1234 -> 0x31 32 33 34
12340 -> 0x31 32 33 34 00
在C語言中，字元串一般是以0自己結尾的。本例的兩個字元串雖然字首相同，但第二個末尾多了0位元組，則第二個“較大”。
（3）正數與負數的比較
int類型的100 -> 0x00 00 00 64
int類型的-100 -> 0xFF FF FF 9C
100 > -100，但其二進制表達中，100 < -100
我們可以将這個比較規則總結如下：
- 從左到右逐個位元組進行比較，以第一個不同位元組的比較結果作為兩個byte[]的比較結果
- 位元組的比較是按無符号數方式進行的
- “不存在”比“存在”小
常見的rowkey編碼問題：
- 有符号數：二進制表示中，有符号數的首bit是1，在字典序規則下，負數比正數大，是以，當rowkey的值域同時包含正數和負數時，需要對符号位進行反轉，以確定正數比負數大
- 倒序：通常用long來描述時間，一般都是倒排的，假設原始值是v，則v的倒序編碼是Long#MAX_VALUE - v。
下面通過一個字首掃描的案例來體會一下這個比較規則的應用。
示例：字首掃描
Hbase的rowkey可以了解為單一主鍵列。如果業務場景需要多列一起構成聯合主鍵(也叫多列主鍵，組合主鍵，複合主鍵等等)，就需要将多列拼接為一列。一般來說，直接将二進制拼接在一起即可。例如：
rowkey組成：userId + ts
為了簡單，假設userid和ts都是定長的，且隻有1個位元組。例如：
現在，我們要做的事情是，查找某個userid = 2的所有資料。這是一個典型的字首掃描場景，我們需要構造一個Scan操作來完成：設定正确掃描範圍[startRow, stopRow)，與region的邊界一樣，scan的範圍也是一個左閉右開區間。
一個直接的思路是找到最小和最大的ts，與userid = 2拼接，作為查詢範圍，即[0x02 00, 0x02 FF)。由于scan是左臂右開區間，則0x02 FF不會被作為結果傳回。是以，這個方案不可行。
正确的scan範圍必須滿足：
- startRow：必須必任何userId = 2的rowkey都小，且比任何userId = 1的rowkey都大
- stopRow：必須必任何userId = 2的rowkey都大，且比任何userId = 3的rowkey都小
那如何利用rowkey的排序規則來“找到”這樣一個掃描範圍呢？
正确的掃描範圍是[0x02, 0x03)。
0x02比任何userid = 2的行都小。因為ts這一列是缺失的。同理，0x03比任何userid = 2的行都大，又比任何userId = 3的行都小。可見，要實作字首掃描，隻根據字首的值就可以得到所需的startRow和stopRow，而不需要知道後面的列及其含義。
請讀者仔細體會這個例子，然後思考下面幾個場景該如何構造startRow和stopRow（答案見文末）。
- where userid = 2 and ts >= 5 and ts < 20
- where userid = 2 and ts > 5 and ts < 20
- where userid = 2 and ts > 5 and ts <= 20
- where userid > 2 and userid < 4
還有下面這些組合場景：
- where userid in (3, 5, 7, 9)
- where userid = 2 and ts in (10, 20, 30)
現在，已經可以感受到使用scan的難點和痛點所在了。在上面的例子中，隻有兩個定長的列，但在實際業務中，列可能是變長的，有各種各樣的資料類型，各種豐富的查詢模式。此時，構造一個正确、高效的scan是有難度的。那為什麼會有這些問題呢？有沒有系統性的解決方案呢？
從形式是看，這是一個“如何将業務查詢邏輯轉換為HBase的查詢邏輯”的問題，本質上是關系表模型到KV模型的映射問題。HBase僅提供了KV層的API，使得使用者不得不自己實作這兩個模型之間的轉換。是以，才會有上面這麼多的難點問題。不僅是HBase，所有的KV存儲系統在面臨複雜的業務模型時，都面臨相同的困境。
這個問題的解法是SQL on NoSQL，業界這類方案有很多(如Hive，presto等)，HBase之上的方案就是Phoenix。此類方案通過引入SQL來解決NoSQL的易用性問題。對于傳統的關系型資料庫，雖然有強大的SQL和事務支援，但擴充性和性能受限，為了解決性能問題，MySQL提供了基于Memcached的KV通路方式；為了解決擴充性問題，有了各種NewSQL的産品，如Spanner/F1，TiDB，CockroachDB等。NoSQL在做SQL，支援SQL的在做KV，我們可以想象一下未來的存儲、資料庫系統會是什麼樣子。這個話題很大，不在本文的讨論範圍内，這裡就不展開了。
region的中繼資料管理與路由
前面我們讨論了将一張表的行通過合理的region劃分，可以得到資料量大緻接近的region分布。通過合理的運維手段(region的分裂與合并)，我們可以通保證在系統持續運作期間的region分布均勻。此時，資料在邏輯上的拆分已經可以實作均勻。本節中我們看一下region如何分布在RS上，以及用戶端如何定位region。
因為region的rowkey範圍本身的不确定性或者主觀性(人為拆分)，無法通過一個數學公式來計算rowkey屬于哪個region(對比一緻性hash的分片方式)。是以，基于範圍進行的分片方式，需要一個中繼資料表來記錄一個表被劃分為哪些region，每個region的起止rowkey是什麼。這個中繼資料表就是meta表，在HBase1.x版本中表名是“hbase:meta”(在094或更老的版本中，是-ROOT-和.META.兩個中繼資料表)。
我們從Put操作來簡要的了解region的定位過程。
- ZK上找meta表所在的RS(緩存)
- 到meta表上找rowkey所在的region及這個region所在的RS(緩存)
- 發Put請求給這個RS，RS根據region名字來執行寫操作
- 如果RS發現這個region不在自己這裡，抛異常，用戶端重新路由
無論讀還是寫，其定位region的邏輯都是如此。為了降低用戶端對meta表的通路，用戶端會緩存region location資訊，當且僅當緩存不正确時，才需要通路meta表來擷取最新的資訊。是以，HBase的請求路由是一種基于路由表的解決方案。相對應的，基于一緻性Hash的分片方式，則是通過計算來得到分布資訊的。
這種基于路由表的方式
- 優點：region的歸屬RS可以任意更換，或者說，region在RS上的排程是靈活的、可人工幹預的。
- 缺點：meta表是一個單點，其有限的吞吐限制了叢集的規模和用戶端數量
region的靈活排程，結合存儲計算分離的架構，賦予了HBase極其強大的能力。
- 秒級擴容：新加入的RS隻需要移動region即可立即投産，不依賴資料的遷移(後續慢慢遷)
- 人工隔離：對于有問題的region(如熱點，有異常請求)，可以手工移動到一台單獨的RS上，進行故障域的快速隔離。
這兩點，是衆多基于一緻性hash的分片方案無法做到的。當然，為了獲得這種靈活性，HBase所付出的代價就是複雜的meta表管理機制。其中比較關鍵的問題就是meta表的單點問題。例如：大量的用戶端都會請求meta表來擷取region location，meta表的負載較高，會限制擷取location的整體吞吐，進而限制叢集的規模和用戶端規模。
對于一個擁有數百台機器，數十萬region的叢集來說，這套機制可以很好的工作。但當叢集規模進一步擴充，觸及到meta表的通路上限時，就會因meta表的通路阻塞而影響服務。當然，絕大多數的業務場景都是無法觸達這個臨界規模的。
meta表的問題可以有很多種解決思路，最簡單的方式就是副本。例如TiDB的PD服務，擷取location的請求可以發送給任何一台PD伺服器。
region的排程
下面我們讨論region排程問題：
- region在RS之間的負載均衡
- 同一個region在多個RS上排程
對于第一個問題，HBase的預設均衡政策是：以表為機關，每個RS上排程盡可能相同數量的region。
這個政策假設各個region的資料量分布相對均勻，每個region的請求相對均勻。此時，該政策非常有效。這也是目前使用最多的一種。同時，HBase也提供了基于負載的排程(StochasticLoadBalancer)，會綜合考慮多種因素來進行排程決策，不過，暫時缺少生産環境使用的案例和資料。
對于第二個問題，region同一時間隻在一台RS上排程，使得HBase在請求成功的情況下提供了強一緻的語義，即寫成功的資料可以立即被讀到。其代價是region的單點排程，即region所在的伺服器因為各種原因産生抖動，都會影響這個region的服務品質。我們可将影響region服務的問題分為兩類：
- 不可預期的：當機恢複，GC，網絡問題，磁盤抖動，硬體問題等等
- 可預期的(或人為的)：擴容/縮容導緻的region移動，region split/merge等。
這些事件發生時，會對這個region的服務或多或少産生一些影響。尤其在當機場景，從ZK發現節點當機到region的re-assign，split log，log replay，一些列步驟執行完，一般都需要1分鐘以上的時間。對于當機節點上的region，意味着這段時間這些region都無法服務。
解決方案依然是副本方案，讓region在多個RS上排程，用戶端選擇其中一個進行通路，這個特性叫“region replia”。引入副本必然帶來額外的成本和一緻性問題。目前這個特性的實作并未降低MTTR時間，記憶體水位的控制、髒讀，使得這個特性仍未在生産中大規模使用。
總結
Hbase的資料分布與region排程問題，放大到整個分布式系統中，是任務的拆分與排程問題，這個話題的内涵大到足以寫幾本書。本文隻是從HBase這個切面來對資料分片這個話題進行一些讨論，希望能夠加深讀者對HBase rowkey和region概念的思考和了解，無論是資料庫的使用者還是開發，都能夠從這個讨論中有所收獲。
附錄
正文中一些查詢場景所對應的scan range：
- where userid = 2 and ts >= 5 and ts < 20: [0x02 05, 0x02 14)
- where userid = 2 and ts > 5 and ts < 20: [0x02 06, 0x02 14)
- where userid = 2 and ts > 5 and ts <= 20: [0x02 06, 0x02 15)
- where userid > 2 and userid < 5: [0x03, 0x05)