哈希方式

常見(jiàn)哈希方式：（用戶id） % （機(jī)器（組）數(shù)）=? 分配到0~（機(jī)器（組）數(shù)-1）上

優(yōu)點(diǎn)：只要哈希函數(shù)的散列特性較好，哈希方式可以較為均勻的將數(shù)據(jù)分布到集群中去。

缺點(diǎn)：

①可擴(kuò)展性不高，一旦集群規(guī)模需要擴(kuò)展，則幾乎所有的數(shù)據(jù)需要被遷移并重新分布。

②一旦某數(shù)據(jù)特征值的數(shù)據(jù)嚴(yán)重不均，容易出現(xiàn)“數(shù)據(jù)傾斜”（data skew）問(wèn)題。

解決方式：

①擴(kuò)展哈希分布的數(shù)據(jù)系統(tǒng)時(shí)，要成倍的擴(kuò)展，按照數(shù)據(jù)重新計(jì)算哈希，這樣原本一臺(tái)機(jī)器上的數(shù)據(jù)只需遷移一半到另一臺(tái)對(duì)應(yīng)的機(jī)器上即可完成擴(kuò)展。

②將對(duì)應(yīng)關(guān)系作為元數(shù)據(jù)，由專門(mén)的元數(shù)據(jù)服務(wù)器管理。將哈希值取模的值大于機(jī)器的數(shù)量，這樣同一臺(tái)機(jī)器上需要負(fù)責(zé)多個(gè)哈希取模的余數(shù)。在集群擴(kuò)容時(shí)，將部分余數(shù)分配到新加的機(jī)器并遷移對(duì)應(yīng)的數(shù)據(jù)到新機(jī)器上。

③重新選擇需要哈希的數(shù)據(jù)特征

按數(shù)據(jù)范圍分布

將數(shù)據(jù)按特征值的值域范圍劃分為不同的區(qū)間，使得集群中每臺(tái)（組）服務(wù)器處理不同區(qū)間的數(shù)據(jù)。

常見(jiàn)分布方式：已知某系統(tǒng)中用戶?id?的值域范圍是[1,100)，集群有?3?臺(tái)服務(wù)器，使用按數(shù)據(jù)范圍劃分?jǐn)?shù)據(jù)的數(shù)據(jù)分布方式。將用戶?id?的值域分為三個(gè)區(qū)間[1,?33),[33,?90)，[90,?100)分別由?3?臺(tái)服務(wù)器負(fù)責(zé)處理。

優(yōu)點(diǎn)：

可以靈活的根據(jù)數(shù)據(jù)量的具體情況拆分原有數(shù)據(jù)區(qū)間，拆分后的數(shù)據(jù)區(qū)間可以遷移到其他機(jī)器，當(dāng)需要集群完成負(fù)載均衡時(shí)，與哈希方式相比非常靈活。另外，當(dāng)集群需要擴(kuò)容時(shí)，可以隨意添加機(jī)器，而不限為倍增的方式，只需將原機(jī)器上的部分?jǐn)?shù)據(jù)分區(qū)遷移到新加入的機(jī)器上就可以完成集群擴(kuò)容。

缺點(diǎn)：

①也會(huì)出現(xiàn)“數(shù)據(jù)傾斜”（data?skew）問(wèn)題。例：某個(gè)數(shù)據(jù)的用戶量大

②需要維護(hù)較為復(fù)雜的元信息。隨著集群規(guī)模的增長(zhǎng)，元數(shù)據(jù)服務(wù)器較為容易成為瓶頸，從而需要較多的元數(shù)據(jù)服務(wù)器解決這個(gè)問(wèn)題。

解決方式：

工程中，為了數(shù)據(jù)遷移等負(fù)載均衡操作的方便，往往利用動(dòng)態(tài)劃分區(qū)間的技術(shù)，使得每個(gè)區(qū)間中服務(wù)的數(shù)據(jù)量盡量的一樣多。當(dāng)某個(gè)區(qū)間的數(shù)據(jù)量較大時(shí)，通過(guò)將區(qū)間“分裂”的方式拆分為兩個(gè)區(qū)間，使得每個(gè)數(shù)據(jù)區(qū)間中的數(shù)據(jù)量都盡量維持一個(gè)較為固定的閾值之下。

按數(shù)據(jù)量分布

數(shù)據(jù)量分布數(shù)據(jù)與具體的數(shù)據(jù)特征無(wú)關(guān)，而是將數(shù)據(jù)視為一個(gè)順序增長(zhǎng)的文件，并將這個(gè)文件按照某一較為固定的大小劃分為若干數(shù)據(jù)塊（chunk），不同的數(shù)據(jù)塊分布到不同的服務(wù)器上。

優(yōu)點(diǎn)：一般沒(méi)有數(shù)據(jù)傾斜的問(wèn)題

當(dāng)集群需要重新負(fù)載均衡時(shí)，只需通過(guò)遷移數(shù)據(jù)塊即可完成。

集群擴(kuò)容，只需將部分?jǐn)?shù)據(jù)庫(kù)遷移到新加入的機(jī)器上即可以完成擴(kuò)容。

缺點(diǎn)：需要管理較為復(fù)雜的元信息，高效的管理元信息成為新的課題。

一致性哈希

一致性哈希的基本方式是使用一個(gè)哈希函數(shù)計(jì)算數(shù)據(jù)或數(shù)據(jù)特征的哈希值，令該哈希函數(shù)的輸出值域?yàn)橐粋€(gè)封閉的環(huán)，即哈希函數(shù)輸出的最大值是最小值的前序。將節(jié)點(diǎn)隨機(jī)分布到這個(gè)環(huán)上，每個(gè)節(jié)點(diǎn)負(fù)責(zé)處理從自己開(kāi)始順時(shí)針至下一個(gè)節(jié)點(diǎn)的全部哈希值域上的數(shù)據(jù)。

優(yōu)點(diǎn)：可以任意動(dòng)態(tài)添加、刪除節(jié)點(diǎn)，每次添加、刪除一個(gè)節(jié)點(diǎn)僅影響一致性哈希環(huán)上相鄰的節(jié)點(diǎn)。

缺點(diǎn)：隨機(jī)分布節(jié)點(diǎn)的方式使得很難均勻的分布哈希值域，尤其在動(dòng)態(tài)增加節(jié)點(diǎn)后，即使原先的分布均勻也很難保證繼續(xù)均勻，由此帶來(lái)的另一個(gè)較為嚴(yán)重的缺點(diǎn)是，當(dāng)一個(gè)節(jié)點(diǎn)異常時(shí)，該節(jié)點(diǎn)的壓力全部轉(zhuǎn)移到相鄰的一個(gè)節(jié)點(diǎn)，當(dāng)加入一個(gè)新節(jié)點(diǎn)時(shí)只能為一個(gè)相鄰節(jié)點(diǎn)分?jǐn)倝毫Α?/p>

改進(jìn)算法：引入虛節(jié)點(diǎn)（virtual?node）的概念，系統(tǒng)初始時(shí)就創(chuàng)建許多虛節(jié)點(diǎn)，虛節(jié)點(diǎn)的個(gè)數(shù)一般遠(yuǎn)大于未來(lái)集群中機(jī)器的個(gè)數(shù)，將虛節(jié)點(diǎn)均勻分布到一致性哈希值域環(huán)上，其功能與基本一致性哈希算法中的節(jié)點(diǎn)相同。為每個(gè)節(jié)點(diǎn)分配若干虛節(jié)點(diǎn)。操作數(shù)據(jù)時(shí)，首先通過(guò)數(shù)據(jù)的哈希值在環(huán)上找到對(duì)應(yīng)的虛節(jié)點(diǎn)，進(jìn)而查找元數(shù)據(jù)找到對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)。

副本與數(shù)據(jù)分布

分布式系統(tǒng)容錯(cuò)、提高可用性的基本手段就是使用副本。一種基本的數(shù)據(jù)副本策略是以機(jī)器為單位，若干機(jī)器互為副本，副本機(jī)器之間的數(shù)據(jù)完全相同。

優(yōu)點(diǎn)：非常簡(jiǎn)單

缺點(diǎn)：恢復(fù)數(shù)據(jù)的效率不高、可擴(kuò)展性也不高。

注：副本之間的數(shù)據(jù)完全相同，1、2、3互為副本?? 4、5、6互為副本?? 7、8、9互為副本

如果其中1臺(tái)機(jī)器出現(xiàn)故障，為了不影響服務(wù)需要新機(jī)器從剩下的2臺(tái)上拷貝數(shù)據(jù)。
①如果全盤(pán)拷貝相當(dāng)消耗資源，如果將一臺(tái)可用的副本下線專門(mén)拷貝，那么此時(shí)正常的副本數(shù)只有一個(gè)，會(huì)有巨大的安全隱患。
②如果用限速的方法從2個(gè)副本上拷貝數(shù)據(jù)，恢復(fù)的時(shí)間又很長(zhǎng)
③不利于提高擴(kuò)展性，如果只增加2臺(tái)機(jī)器，因?yàn)?臺(tái)機(jī)器無(wú)法組成新的副本組，則無(wú)法擴(kuò)容。相當(dāng)于加了66%的機(jī)器卻擴(kuò)容失敗
（此處并非無(wú)法擴(kuò)容，可以擴(kuò)容只不過(guò)承擔(dān)的風(fēng)險(xiǎn)會(huì)比較大，同時(shí)2臺(tái)機(jī)器的壓力會(huì)增加，如果有1臺(tái)宕機(jī)那么只有一臺(tái)可以提供服務(wù)）
④不利于系統(tǒng)容錯(cuò)，加個(gè)有3個(gè)副本，1臺(tái)宕機(jī)后剩下2臺(tái)的壓力將增大50%

更合適的做法不是以機(jī)器作為副本單位，而是將數(shù)據(jù)拆為較合理的數(shù)據(jù)段，以數(shù)據(jù)段為單位作為副本。

數(shù)據(jù)段的選擇：

①哈希：每個(gè)哈希分桶后的余數(shù)可以作為一個(gè)數(shù)據(jù)段，為了控制數(shù)據(jù)段的大小，常常使得分桶個(gè)數(shù)大于集群規(guī)模。

②按數(shù)據(jù)范圍分布：將每個(gè)數(shù)據(jù)區(qū)間作為一個(gè)數(shù)據(jù)段，并控制數(shù)據(jù)區(qū)間中數(shù)據(jù)的大小。

③按數(shù)據(jù)量分?jǐn)?shù)據(jù)：按照每個(gè)數(shù)據(jù)塊作為數(shù)據(jù)段。

④一致性哈希：將一致性哈希環(huán)分為若干等長(zhǎng)分區(qū)，分區(qū)個(gè)數(shù)一般遠(yuǎn)大于節(jié)點(diǎn)個(gè)數(shù)，假設(shè)哈希函數(shù)均勻，則每個(gè)分區(qū)中的數(shù)據(jù)可以作為一個(gè)數(shù)據(jù)段。

此種方式的優(yōu)點(diǎn)： ①這種方式使副本分布與機(jī)器無(wú)關(guān)，副本丟失后的恢復(fù)效率非常高，如果機(jī)器1宕機(jī)，那可以從集群中剩下的所有機(jī)器上同時(shí)拷貝恢復(fù)數(shù)據(jù)（即使限速也會(huì)很快，因?yàn)闄C(jī)器多啊） ②利于集群容錯(cuò)，宕機(jī)機(jī)器上的副本分散于整個(gè)集群，壓力分散到整個(gè)集群自然就小了 ③利于集群擴(kuò)展，加入一臺(tái)新機(jī)器的時(shí)候只需要從各機(jī)器上遷移1/n比例的數(shù)據(jù)段到新機(jī)器就可以實(shí)現(xiàn)新的負(fù)載均衡。

本地化計(jì)算

對(duì)于分布式系統(tǒng)而言，除了解決大規(guī)模存儲(chǔ)問(wèn)題更需要解決大規(guī)模的計(jì)算問(wèn)題。

如果計(jì)算節(jié)點(diǎn)和存儲(chǔ)節(jié)點(diǎn)位于不同的物理機(jī)器則計(jì)算的數(shù)據(jù)需要通過(guò)網(wǎng)絡(luò)傳輸，此種方式的開(kāi)銷很大，甚至網(wǎng)絡(luò)帶寬會(huì)成為系統(tǒng)的總體瓶頸。另一種思路是，將計(jì)算盡量調(diào)度到與存儲(chǔ)節(jié)點(diǎn)在同一臺(tái)物理機(jī)器上的計(jì)算節(jié)點(diǎn)上進(jìn)行，這稱之為本地化計(jì)算。本地化計(jì)算是計(jì)算調(diào)度的一種重要優(yōu)化，其體現(xiàn)了一種重要的分布式調(diào)度思想：“移動(dòng)數(shù)據(jù)不如移動(dòng)計(jì)算”。

數(shù)據(jù)分布方式的選擇

數(shù)據(jù)傾斜問(wèn)題：在按哈希分?jǐn)?shù)據(jù)的基礎(chǔ)上引入按數(shù)據(jù)量分布數(shù)據(jù)的方式，解決該數(shù)據(jù)傾斜問(wèn)題。

按用戶 id 的哈希值分?jǐn)?shù)據(jù)，當(dāng)某個(gè)用戶 id 的數(shù)據(jù)量特別大時(shí)，該用戶的數(shù)據(jù)始終落在某一臺(tái)機(jī)器上。此時(shí)，引入按數(shù)據(jù)量分布數(shù)據(jù)的方式，統(tǒng)計(jì)用戶的數(shù)據(jù)量，并按某一閾值將用戶的數(shù)據(jù)切為多個(gè)均勻的數(shù)據(jù)段，將這些數(shù)據(jù)段分布到集群中去。由于大部分用戶的數(shù)據(jù)量不會(huì)超過(guò)閾值，所以元數(shù)據(jù)中僅僅保存超過(guò)閾值的用戶的數(shù)據(jù)段分布信息，從而可以控制元數(shù)據(jù)的規(guī)模。

常見(jiàn)分布式系統(tǒng)的數(shù)據(jù)分布方式系統(tǒng)

GFS & HDFS 按數(shù)據(jù)量分布

Map reduce 按 GFS 的數(shù)據(jù)分布做本地化

Big Table & HBase 按數(shù)據(jù)范圍分布

PNUTS 哈希方式/按數(shù)據(jù)范圍分布（可選）

Dynamo & Cassandra 一致性哈希

Mola & Armor? 哈希方式

Big Pipe? 哈希方式

Doris 哈希方式與按數(shù)據(jù)量分布組合

?

?

?

參考資料：《分布式系統(tǒng)原理介紹》作者：劉杰

如有錯(cuò)誤歡迎指正！

總結(jié)

以上是生活随笔為你收集整理的分布式系统的数据分布方式的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。