進(jìn)入到第六章了堰汉，我們要開始聊聊分布式系統(tǒng)之中的核心問題：數(shù)據(jù)分區(qū)翘鸭。分布式系統(tǒng)通常是通過大規(guī)模的數(shù)據(jù)節(jié)點來處理單機(jī)沒有辦法處理的海量數(shù)據(jù)集就乓，因此，可以將一個大型數(shù)據(jù)集可以分布在多個磁盤上，查詢負(fù)載可以分布在多個處理器上守伸。在這一章中尼摹，我們首先討論劃分大型數(shù)據(jù)集的不同方法蠢涝，并觀察數(shù)據(jù)索引如何與分區(qū)交互和二，然后將探索數(shù)據(jù)分區(qū)重新平衡的策略惕它。最后废登，來看看路由技術(shù)怎么將查詢索引到正確的分區(qū)甲锡。內(nèi)容看起來還不少缤沦，我們開始吧疚俱。

1. 分區(qū)與副本

分區(qū)與副本是很容易混淆的概念呆奕，我們這里離清一下兩者梁钾。
數(shù)據(jù)分區(qū)的每個副本可以存儲在多個節(jié)點上零酪。這意味著四苇，即使每個記錄恰好屬于一個分區(qū)月腋，它仍然可以存儲在幾個不同的節(jié)點上進(jìn)行容錯榆骚。

數(shù)據(jù)分區(qū)與副本的關(guān)系：

由上圖可以看出，分區(qū)和副本是需要解決不同問題的苫纤，并不能混為一談，兩者同樣作為分布式系統(tǒng)之中的核心技術(shù)放钦，共同為分布式系統(tǒng)提供好的解決方案操禀。

2. 分區(qū)策略

數(shù)據(jù)分區(qū)的目的是：將數(shù)據(jù)和查詢負(fù)載均勻地分布在節(jié)點上。（其實副本也有同樣的效果揪惦，取決于副本同步機(jī)制）而如果數(shù)據(jù)分區(qū)不公平，則會出現(xiàn)某些分區(qū)的數(shù)據(jù)或查詢比其他分區(qū)要多纫塌，我們稱之為偏斜怎披。數(shù)據(jù)偏斜就使得分區(qū)效果變差胸嘁，導(dǎo)致負(fù)載不均衡形成分區(qū)熱點。 所以分區(qū)策略通常以分區(qū)均勻為考量凉逛，接下來我們介紹幾種常見的分區(qū)策略：

范圍分區(qū)

范圍分區(qū)是分配一個連續(xù)的范圍鍵性宏，如同幾冊百科全書一般。如果知道范圍之間的邊界状飞，就可以很容易地確定哪個分區(qū)包含給定的鍵毫胜。如果您還知道哪個分區(qū)被分配到哪個節(jié)點，那么您可以直接將請求發(fā)送到適當(dāng)?shù)墓?jié)點昔瞧。

多冊百科全書按照范圍分冊

但是很多時候鍵的范圍不一定是均勻分布的，為了均勻地分布數(shù)據(jù)菩佑，分區(qū)邊界需要和數(shù)據(jù)的特點相適應(yīng)。對于每一個分區(qū)，我們可以把按鍵順序排列，如SSTable，顯然這樣可以大幅提升范圍掃描的效率。

而范圍分區(qū)的缺點是某些訪問模式會導(dǎo)致熱點遮糖。如果某個范圍的鍵頻繁被訪問赛不，將導(dǎo)致某個分區(qū)的讀寫量遙遙領(lǐng)先，而其他分區(qū)被閑置。（這種情況考慮細(xì)分分區(qū)粒度或者級聯(lián)索引，用一個較均勻的特征先做一次分區(qū)）

哈希分區(qū)

由于范圍分區(qū)容易產(chǎn)生熱點問題偏友，許多分布式數(shù)據(jù)存儲使用一個哈希函數(shù)來確定一個鍵值的分區(qū)舞竿。一個好的哈希函數(shù)可以將傾斜的數(shù)據(jù)均勻分布重归，即使數(shù)據(jù)范圍很接近，但是它們的哈希值是均勻分布的值香椎。如下圖所示万矾，時間接近的鍵值被哈希函數(shù)均勻的分區(qū)在多個分區(qū)，每個鍵的哈希值落在一個分區(qū)的范圍將被存儲在該分區(qū)：

哈希分區(qū)

使用哈希分區(qū)漫玄，我們失去了鍵范圍分區(qū)的一個很好的特性凳谦，曾經(jīng)相鄰的鍵現(xiàn)在分散在所有分區(qū)上绊诲，因此它們的排序順序丟失世舰。我們可以通過級聯(lián)索引的方式解決這個問題。級聯(lián)索引方法支持一對多關(guān)系的優(yōu)雅的數(shù)據(jù)模型梗搅，通過兩分區(qū)方式來綜合不同分區(qū)方式的優(yōu)點哆键，通過鍵哈希來確定分區(qū)的第一部分异赫，但其他列作為SSTables的數(shù)據(jù)排序串聯(lián)靠抑。因此稚伍，查詢不能在復(fù)合鍵的第一列內(nèi)搜索范圍內(nèi)的值呼寸，但是如果它為第一列指定一個固定值，它就可以在鍵的其他列上執(zhí)行有效的范圍掃描。例如，在社交媒體站點上，一個用戶可以發(fā)布許多更新百炬。如果更新主鍵（user_id固惯，update_timestamp）梆造，那么你可以有效地檢索在一定時間間隔內(nèi)特定用戶的所有更新。不同的用戶可以存儲在不同的分區(qū)上葬毫，但是在每個用戶中镇辉，更新是在單個分區(qū)上以時間戳順序存儲的屡穗。

Tip：緩解熱點

通過哈希函數(shù)分區(qū)的確有助于減少熱點。然而忽肛，它不能完全避免它們：在極端情況下村砂，所有讀寫操作都是相同的鍵，最終仍然會將所有請求到同一分區(qū)屹逛。例如础废，在社交媒體網(wǎng)站上，一個擁有數(shù)百萬追隨者的名人用戶在做某事時可能會引發(fā)一場讀寫風(fēng)暴罕模。此事件可能導(dǎo)致短時間內(nèi)大量寫入同一個鍵（其中的Key可能是名人的用戶ID色迂，或者是人們評論的行為ID）。這時哈希函數(shù)也無能為力手销，因為兩個相同ID的哈希值仍然相同歇僧。

大多數(shù)數(shù)據(jù)系統(tǒng)不能自動補償這種高度傾斜的工作負(fù)載，因此應(yīng)用程序有責(zé)任減少偏斜锋拖。例如诈悍，如果已知一個鍵非常熱，一個簡單的方法就是在鍵的開頭或結(jié)尾加上一個隨機(jī)數(shù)兽埃。只有一個兩位數(shù)的十進(jìn)制隨機(jī)數(shù)將把寫入分成100個不同的鍵侥钳，允許這些鍵被分配到不同的分區(qū)。但是將不同的鍵分開寫入后柄错，現(xiàn)在任何讀取都必須做額外的工作舷夺，因為它們必須從所有100個鍵讀取數(shù)據(jù)并將其組合起來。而且這種方式還需要額外的記錄：因為只為少量的熱鍵添加隨機(jī)數(shù)是有意義的售貌；對于絕大多數(shù)具有低寫入吞吐量的鍵给猾，這將是不必要的開銷。因此颂跨，還需要一些方法來跟蹤哪些鍵正在被分割敢伸。

2. 分區(qū)與二級索引

上文討論的分區(qū)方案依賴于一個關(guān)鍵值數(shù)據(jù)模型。通過主鍵訪問記錄恒削，可以由該鍵確定分區(qū)池颈，并使用它將讀取和寫入請求路由到負(fù)責(zé)該鍵的分區(qū)。

而一旦涉及到二級索引钓丰，情況會變得更加復(fù)雜躯砰。二級索引通常不確定記錄的唯一性而應(yīng)該是尋找一個特定的值出現(xiàn)的方式如：找到所有顏色是紅色的車 這樣的查詢。二級索引的問題是它不能映射到分區(qū)携丁。有兩種主要方法將數(shù)據(jù)庫分為二級索引：基于分區(qū)的索引和基于全局的索引琢歇。

基于分區(qū)的索引

假如有一個賣二手車的網(wǎng)站，每個列表都有一個唯一的ID，稱之為文檔矿微。通過文檔id（例如痕慢，分區(qū)0中的IDS 0到499、分區(qū)1中的IDS 500到999）對數(shù)據(jù)庫進(jìn)行分區(qū)涌矢。
您希望讓用戶搜索汽車掖举，允許它們按顏色和按顏色進(jìn)行過濾，因此需要對顏色進(jìn)行二級索引索引娜庇，每當(dāng)一輛紅色的車是添加到數(shù)據(jù)庫中塔次，數(shù)據(jù)庫分區(qū)自動添加到索引的文檔的ID到紅色索引處。如下圖所示：

基于分區(qū)的索引

在這種索引方法中名秀，每個分區(qū)都是完全獨立的励负，每個分區(qū)都保留自己的索引，只覆蓋分區(qū)中的文檔id匕得。它不關(guān)心存儲在其他分區(qū)中的數(shù)據(jù)继榆。每當(dāng)您需要向數(shù)據(jù)庫寫入添加、刪除或更新文檔時汁掠，只需要處理包含您正在編寫的文檔ID的分區(qū)略吨。

但是，從索引讀取時需要注意考阱，如果您想搜索紅色的汽車翠忠，您需要將查詢發(fā)送到所有分區(qū)，并將所有返回的結(jié)果組合起來乞榨。這樣導(dǎo)致了二級索引上的讀取查詢非常耗時秽之。即使并行的寫入和查詢分區(qū)，分散/聚集操作會導(dǎo)致延遲放大吃既。

基于全局的索引

上節(jié)提到分區(qū)索引的缺點考榨，所以我們可以建立一個全局的索引，涵蓋所有的分區(qū)數(shù)據(jù)态秧。但是董虱，不能只存儲索引在一個節(jié)點扼鞋，因為它可能會成為一個瓶頸和故障點申鱼。所以全局索引也必須被分區(qū)，但它可以劃分不同的主鍵索引云头。如下圖所示：

全局索引的索引分區(qū)

3 分區(qū)平衡

隨著時間的推移拂共，數(shù)據(jù)庫中的東西發(fā)生了變化：

• (1) 查詢吞吐量增加牺弄，因此您需要添加更多CPU來處理負(fù)載。
• (2) 數(shù)據(jù)集大小增加宜狐，所以您需要添加更多的磁盤和RAM來存儲它势告。
• (3) 機(jī)器故障，其他機(jī)器需要接管故障機(jī)器的責(zé)任抚恒。

所有這些變化都要求將數(shù)據(jù)和請求從一個節(jié)點移動到另一個節(jié)點咱台。而負(fù)載從集群中的一個節(jié)點轉(zhuǎn)移到另一個節(jié)點的過程稱為分區(qū)平衡。

無論采用哪種分區(qū)方案俭驮，通常都希望分區(qū)平衡以滿足下面的要求：

• (1) 重新平衡后回溺，集群中的節(jié)點之間應(yīng)該公平地共享負(fù)載（數(shù)據(jù)存儲、讀寫請求）混萝。
• (2) 當(dāng)分區(qū)平衡工作時馅而，數(shù)據(jù)庫應(yīng)該繼續(xù)接受讀寫操作。
• (3) 在節(jié)點之間移動盡量減少數(shù)據(jù)的移動譬圣，以便使平衡快速完整瓮恭，并減少網(wǎng)絡(luò)和磁盤I/O負(fù)載。

海量分區(qū)

節(jié)點創(chuàng)建遠(yuǎn)超節(jié)點數(shù)目的分區(qū)數(shù)厘熟，并為每個節(jié)點分配幾個分區(qū)屯蹦。例如，在10個節(jié)點的群集上運行的數(shù)據(jù)庫可以從一開始分裂成1000個分區(qū)绳姨，以便分配給每個節(jié)點大約100個分區(qū)登澜。當(dāng)將一個節(jié)點添加到集群中，新節(jié)點可以從每個現(xiàn)有節(jié)點竊取一些分區(qū)飘庄，直到再次公平分配分區(qū)為止脑蠕。如下圖所示：

海量分區(qū)的再平衡

分區(qū)的數(shù)量不會改變，分區(qū)的鍵分配也不會改變跪削。唯一改變的是分區(qū)與節(jié)點之間的映射谴仙。這種分區(qū)平衡的變化不是即時的，在網(wǎng)絡(luò)上傳輸大量數(shù)據(jù)需要一定的時間碾盐，所以舊的分區(qū)節(jié)點在分區(qū)平衡時需要承擔(dān)這個過程之中的讀寫操作晃跺。通過海量分區(qū)同樣也可以通過給性能更強悍的節(jié)點分配更多的分區(qū)，可以強制這些節(jié)點承擔(dān)更大的負(fù)載份額毫玖。

一開始配置的分區(qū)數(shù)量就是所能擁有的最大節(jié)點數(shù)掀虎，因此您需要選擇足夠高的分區(qū)數(shù)目以適應(yīng)未來的增長凌盯。然而，每個分區(qū)也有管理開銷烹玉，所以選擇過高的值會適得其反驰怎。

動態(tài)分區(qū)

對于使用鍵范圍分區(qū)的數(shù)據(jù)庫，固定范圍值的固定分區(qū)數(shù)量將非常不方便：如果您的邊界錯誤二打，您可能會將所有數(shù)據(jù)放在一個分區(qū)中砸西，而所有其他分區(qū)都是空的。手動重新分區(qū)分區(qū)將非常繁瑣址儒。所以可以采取動態(tài)分區(qū)的機(jī)制：

當(dāng)一個分區(qū)的增長超過配置的大小芹枷，它被分為兩個分區(qū)，大約一半的數(shù)據(jù)分配在兩個新的分區(qū)莲趣。相反鸳慈，如果大量數(shù)據(jù)被刪除，一個分區(qū)縮小到某個閾值以下喧伞，它可以與相鄰分區(qū)合并走芋。動態(tài)分區(qū)的優(yōu)點是分區(qū)的數(shù)量與總數(shù)據(jù)量相適應(yīng)。如果只有少量的數(shù)據(jù)潘鲫，少量的分區(qū)就足夠了翁逞，因此開銷很小溉仑；如果有大量的數(shù)據(jù)挖函，每個單獨的分區(qū)的大小限制為一個可配置的最大值。

4. 請求路由

在多臺機(jī)器上運行的多個節(jié)點上對數(shù)據(jù)集進(jìn)行分區(qū)浊竟，所以會面臨一個核心問題：當(dāng)客戶端想要提出請求時怨喘，它如何知道要連接哪個節(jié)點？當(dāng)分區(qū)被重新平衡振定，分區(qū)節(jié)點變化的時候客戶端如何感知變化必怜。

在高層次上，對這個問題有幾種不同的解決方案：

• 1.允許客戶端與任何節(jié)點聯(lián)系后频。如果該節(jié)點恰好擁有請求所應(yīng)用的分區(qū)梳庆，則它可以直接處理請求；否則卑惜，它將請求轉(zhuǎn)發(fā)到適當(dāng)?shù)墓?jié)點膏执，接收應(yīng)答，并將應(yīng)答傳遞給客戶端残揉。
• 2. 將客戶端的所有請求首先發(fā)送到路由層胧后，這將決定應(yīng)處理每個請求并相應(yīng)轉(zhuǎn)發(fā)它的節(jié)點。
• 3. 要求客戶端知道分區(qū)和分配給節(jié)點的分區(qū)抱环。在這種情況下壳快，客戶機(jī)可以直接連接到適當(dāng)?shù)墓?jié)點，而不需要任何中介镇草。

三種路由解決方案

在三種情況之中關(guān)鍵的問題是：組成路由決策的組件（可能是其中一個節(jié)點眶痰，或者路由層，或客戶端）如何了解分區(qū)分配給節(jié)點的變化梯啤？

許多分布式數(shù)據(jù)系統(tǒng)依賴于一個單獨的協(xié)調(diào)服務(wù)如ZooKeeper跟蹤這個集群的元數(shù)據(jù)，每個節(jié)點在ZooKeeper之中注冊自己。ZooKeeper維護(hù)分區(qū)節(jié)點映射的權(quán)威械巡，而路由層或客戶端乳怎，可以訂閱這個ZooKeeper。當(dāng)一個分區(qū)發(fā)生變化時察滑，或添加一個節(jié)點或刪除打厘，ZooKeeper通知路由層，這樣可以保持它的路由信息更新贺辰。如下圖所示：

基于ZooKeeper的請求路由

Cassandra和Riak采取了不同的方法：通過使用Gossip協(xié)議節(jié)點之間傳播集群狀態(tài)的任何變化户盯。請求可以發(fā)送到任何節(jié)點，該節(jié)點將它們轉(zhuǎn)發(fā)到所請求分區(qū)的適當(dāng)節(jié)點饲化。該模型提出了更復(fù)雜的數(shù)據(jù)庫節(jié)點莽鸭，但避免了外部協(xié)調(diào)服務(wù)的依賴。

當(dāng)使用路由層或向隨機(jī)節(jié)點發(fā)送請求時吃靠，客戶端仍然需要找到連接到的IP地址硫眨。這些并不像分區(qū)對節(jié)點的分配那樣快速變化，因此經(jīng)常使用DNS來達(dá)到此目的巢块。

小結(jié)：

我們在本篇之中總結(jié)了數(shù)據(jù)分區(qū)技術(shù)運用到的多種策略與技術(shù)捺球，希望大家能夠更好的認(rèn)識數(shù)據(jù)分區(qū)技術(shù)在分布式存儲之中的重要意義。