?
第一章 數(shù)據(jù)的分片與路由
分片包括二個映射:
1.key-partition映射,將數(shù)據(jù)記錄映射到數(shù)據(jù)分片空間中,一般是多對一的映射即一個數(shù)據(jù)分片包含多條記錄
2.partition-macheine映射,將數(shù)據(jù)分片映射到物理機(jī)器中,也是多對一映射,即一臺物理機(jī)器容納多個數(shù)據(jù)分片
?
哈希分片(hash partition)
1.Round Robin
? ? H(key) = hash(key) mod (K+1) ? ? K為當(dāng)前機(jī)器數(shù)量,新增一臺物理機(jī)器就是K+1
? ? RoundRobin算法在增加一臺機(jī)器后整個結(jié)果都變了
2.虛擬桶(Virtual Buckets)
? ? Membase(現(xiàn)更名為Couchbase)使用的算法
3.一致性hash(Consistent Hashing)
? ? 如memcached使用的一致性hash算法
范圍分片(Range Partition)
? ? 將所有記錄的主鍵先排序,然后在排好序的主鍵記錄空間里將記錄劃分成數(shù)據(jù)分片,每個數(shù)據(jù)分片存儲有序的主鍵空間片段內(nèi)的所有記錄?,F(xiàn)實實現(xiàn)中使用一個數(shù)據(jù)分片映射表,記錄表每一項記載數(shù)據(jù)分片的最小主鍵及其對應(yīng)的物理主機(jī)地址
? ? 也就是需要一個元記錄表,記錄最終記錄所在機(jī)器的位置,比如HBase的meta表
?
?
?
?
?
第二章 數(shù)據(jù)復(fù)制與一致性
CAP
一致性(Consistency)在分布式系統(tǒng)中的同一數(shù)據(jù)多副本情形下,對于數(shù)據(jù)的更新操作提現(xiàn)處的效果與只有
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?單份數(shù)據(jù)是一樣的
可用性(Availability) 客戶端在任何時刻對大規(guī)模數(shù)據(jù)系統(tǒng)的讀/寫操作都應(yīng)該保證在限定的時間內(nèi)完成
分區(qū)容忍性(Partition Tolerance) ?在大規(guī)模分布式數(shù)據(jù)系統(tǒng)中,網(wǎng)絡(luò)分區(qū)現(xiàn)象,即分區(qū)間的機(jī)器無法進(jìn)行
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 網(wǎng)絡(luò)通訊的情況是必然會發(fā)生的,所以系統(tǒng)應(yīng)該能夠在這種情況下繼續(xù)工作
對于分布式系統(tǒng)來說P 是一定要滿足的,所以在CAP三者不能兼顧的情況下,要不選擇AP,要不選擇CP
?
ACID原則
原子性(Atomicity) 一個事務(wù)要么全部執(zhí)行,要么全部不執(zhí)行
一致性(Consistency) 事務(wù)在開始和結(jié)束時,應(yīng)該始終滿足一致性約束條件,比如系統(tǒng)要求A+B=100,那么
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?事務(wù)如果改變了A的數(shù)值,則B的數(shù)值也要相應(yīng)的修改來滿足這種一致性要求
事務(wù)獨立(Isolationi) 如果有多個事務(wù)同時執(zhí)行,彼此之間不需要知曉對方的存在,而且執(zhí)行時相互不影響,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?不允許出現(xiàn)兩個事務(wù)交錯,間隔執(zhí)行部分任務(wù)的情況,也即事務(wù)之間需要序列化執(zhí)行
持久性(Durability) 事務(wù)運行成功以后,對系統(tǒng)狀態(tài)的更新是永久的,不會無緣無故的回滾撤銷
?
BASE原則
基本可用(Basically Available)在絕大多數(shù)時間內(nèi)系統(tǒng)處于可用狀態(tài),允許偶爾的失敗,所以稱基本可用
軟狀態(tài)或者柔性狀態(tài)(Soft State)是指數(shù)據(jù)狀態(tài)不要求在任意時刻都完全保持同步,到目前為止軟狀態(tài)并
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 無一個統(tǒng)一明晰的定義,即處于有狀態(tài)和無狀態(tài)之間
最終一致性(Eventual Consistency)在給定時間窗口內(nèi)數(shù)據(jù)會達(dá)到一致狀態(tài)
?
一致性模型
1.強(qiáng)一致性
2.最終一致性
3.因果一致性
4.讀你所讀一致性
5.會話一致性
6.單調(diào)讀一致性
7.單調(diào)寫一致性
?
副本更新策略
1.同時更新(通過一致性協(xié)議來更新)
2.主從更新(同步,異步更新,混合更新)
3.任意節(jié)點更新(同步,異步)
?
一致性協(xié)議
兩階段提交(Two-Phrase Commit 2PC)
?
向量時鐘
RWN協(xié)議
N表示在分布式系統(tǒng)中有多少個備份數(shù)據(jù)
W表示一次成功的更新操作至少要有W份數(shù)據(jù)寫入成功
R表示一次成功的讀取數(shù)據(jù)要求至少有R份數(shù)據(jù)成功讀取
如果滿足 ? ?R + W > N ? ? ? 則可稱為滿足 數(shù)據(jù)一致性協(xié)議
?
Paxos一致協(xié)議
Raft協(xié)議
?
關(guān)于分布式事務(wù)、兩階段提交、一階段提交、Best Efforts 1PC模式和事務(wù)補(bǔ)償機(jī)制的研究
Paxos算法細(xì)節(jié)詳解(一)--通過現(xiàn)實世界描述算法
分布式一致性Paxos算法學(xué)習(xí)筆記(一):paxos大雜燴
?
?
?
?
?
第三章 大數(shù)據(jù)常用的算法與數(shù)據(jù)結(jié)構(gòu)
布隆過濾器(Bloom Filter)
使用一個N個函數(shù),對指定要查找的key執(zhí)行函數(shù) fun1(key)如果落到了數(shù)組的某一位上就將這位設(shè)置為1
所以指定了三個函數(shù)之后會有三個bit被設(shè)置為1
bloom filter會誤判但不會漏判,而且存在一定的誤判率,和數(shù)組大小,函數(shù)個數(shù)都有關(guān)系
bloom filter只能用于數(shù)據(jù)添加操作,數(shù)據(jù)刪除就不行了,因為一個bit只能表示有和無不能再有其他狀態(tài)了。解決辦法是用多個bit來表示一個狀態(tài)
這個就是計數(shù)BF(Counting Bloom Filter)
布隆過濾器在Chrome的URL判斷,比特幣歷史交易,hbase,cassandra中都有使用
?
SkipList
在插入,刪除,查找數(shù)據(jù)時都能保證O(long(N))時間復(fù)雜度,hbase和levelDB都使用了跳表
本質(zhì)上是一個鏈表結(jié)構(gòu),但是每個每個節(jié)點可能都有N個指向后面的節(jié)點,即一個節(jié)點有多個后續(xù),而節(jié)點包含多少個后續(xù)是隨機(jī)產(chǎn)生的。
最下面那層包含所有的數(shù)據(jù),倒數(shù)第二層的數(shù)據(jù)節(jié)點個數(shù)就少一些,層數(shù)越往上節(jié)點數(shù)就越少
查找的時候首先從第一層開始,再依次往下
?
LSM樹
首先將數(shù)據(jù)寫到預(yù)寫日志中,然后將寫的數(shù)據(jù)先放到內(nèi)存中這樣就可以保證以后的隨機(jī)讀了,如果內(nèi)存中的數(shù)據(jù)到一定大小后,就將數(shù)據(jù)flush到磁盤上。從整個結(jié)構(gòu)上來說就像一顆樹,整體是字典排序有序的。
一個節(jié)點下可能會被flush了一個或多個文件,如果定位到某個節(jié)點(就類似HBase中的region)那么就需要遍歷下面的所有文件(也就是HFile)才能讀取到對應(yīng)的值了,這個讀取的可以使用布隆過濾器優(yōu)化提高速度。
本質(zhì)上來說就像region一樣,一開始可能很少,后來越來越多,region按照key順序排序,其實只有三層的樹,root表-->meta表-->業(yè)務(wù)表
然后region不斷變多,但是region下面的HFile數(shù)量還是1個到7個(默認(rèn)最多7個),當(dāng)達(dá)到HFile達(dá)到一定數(shù)量后就會合并,這樣就減少region下面的HFile提高讀性能。
LSM樹由來、設(shè)計思想以及應(yīng)用到HBase的索引
?
Merkle Hash Tree
每個節(jié)點和其所有子節(jié)點都會計算一次hash,這樣如果比較根節(jié)點的hash有變化了,則會依次找尋到變化的子節(jié)點,最后找到最終的變化數(shù)據(jù)
被廣泛運用于分布式領(lǐng)域,主要用來在海量數(shù)據(jù)下快速定位少量變化的數(shù)據(jù)內(nèi)容(變化原因可能是損毀,篡改或者正常變化等)
如P2P下載系統(tǒng)BitTorrent,Git等工具,比特幣以及Dynamo,Riak,Cassandra等
Dynamo中結(jié)合Merkle樹和Gossip協(xié)議,假設(shè)A和B存儲了相同的數(shù)據(jù)副本。此時兩個節(jié)點都對兩者所存儲數(shù)據(jù)的共同鍵值范圍(Key Range)部分建立Merkle樹。之后可以比較兩個節(jié)點的Merkle樹節(jié)點hash值來查找不同部分,首先比較根節(jié)點再比較所有葉子節(jié)點。Gossip協(xié)議在上述過程中起的作用是:兩個節(jié)點在交換Merkle樹節(jié)點內(nèi)容以及同步數(shù)據(jù)內(nèi)容時可通過這個協(xié)議來進(jìn)行
比特幣通過Merkle樹來驗證交易的歷史數(shù)據(jù)。
?
Snappy與LZSS算法
LZSS是LZ77的一種,LZ77是一種動態(tài)詞典編碼(dictionary coding)
詞典編碼的意思是:文本中的詞用它在詞典中表示位置的號碼代替無損數(shù)據(jù)壓縮方法,一般分為靜態(tài)詞典和動態(tài)詞典。
靜態(tài)詞典需要事先構(gòu)造,采用動態(tài)詞典時編碼器將被壓縮的文本中自動導(dǎo)出詞典,解碼器解碼時邊解碼邊構(gòu)造詞典。?
LZ77采用滑動窗口和前向緩沖區(qū)
新讀入的字節(jié)放到滑動窗口中(也是處理過的字節(jié)),如果前向緩沖區(qū)(也就是未處理的部分)和滑動窗口中數(shù)據(jù)有匹配,則記錄一個標(biāo)號,類似三元數(shù)組<指針,長度,后續(xù)字符>,如(3,2)表示從開頭第三個字節(jié)開始匹配兩個
一個常用的技巧是:將滑動窗口內(nèi)字符串的各種長度片段存入哈希表,哈希表的值記載在滑動窗口的出現(xiàn)位置
Snappy則做了一些優(yōu)化,設(shè)置了最少長度為4,也就是說必須至少匹配4個字符串才進(jìn)行壓縮處理。同時設(shè)定hash表內(nèi)的字符串片段固定長度為4。此外Snappy將數(shù)據(jù)切割成32K大小,數(shù)據(jù)塊之間無關(guān)聯(lián)。
?
Cuckoo Hashing
傳統(tǒng)hash只使用一個hash函數(shù),cuckoo同時使用兩個不同的hash函數(shù)H1(x)和H2(x)
如果計算出H1(x)和H2(x)任意一個不為空就可以插入,如果兩者都不為空則選擇一個桶將已有的值y踢出去,由x來插入相應(yīng)的位置。y的值重復(fù)上述步驟計算一個新的值如果再由沖突,則踢掉z插入y繼續(xù)執(zhí)行。這樣可能導(dǎo)致無限循環(huán)所以需要設(shè)定一個最大替換次數(shù),如果到了最大替換次數(shù)需要更換hash函數(shù)或者增加hash空間中桶的數(shù)量
?
?
?
?
?
第四章 集群資源管理與調(diào)度
采用獨立的資源管理與調(diào)度系統(tǒng)而非靜態(tài)劃分資源有如下好處
1.集群整體資源利用率高,所有的資源統(tǒng)一管理與調(diào)度,可以根據(jù)不同計算任務(wù)的即時需要動態(tài)分配資源
2.可增加數(shù)據(jù)共享能力,對于有些共享的數(shù)據(jù)資源,需要分別在分配給不同計算任務(wù)的子集群中重復(fù)存儲
3.支持多類型計算框架和多版本計算框架
?
調(diào)度系統(tǒng)設(shè)計的基本問題
1.資源異質(zhì)性與工作負(fù)載異質(zhì)性
2.數(shù)據(jù)局部性(從性能角度盡量選擇A,再是B)
? ? A節(jié)點局部性
? ? B機(jī)架局部性
? ? C全局局部性
3.搶占式調(diào)度和非搶占式調(diào)度
4.資源分配粒度
5.餓死與死鎖(如果不斷出現(xiàn)高優(yōu)先級任務(wù),低優(yōu)先級的可能出現(xiàn)餓死)
6.資源隔離
?
三種資源管理與調(diào)度系統(tǒng)范型
1.集中式調(diào)度器(Monolithic Scheduler)
2.兩級調(diào)度器(Two-Level Scheduler)
3.狀態(tài)共享調(diào)度器(Shared-State Scheduler)
?
資源調(diào)度策略
1.FIFO調(diào)度側(cè)路了
2.公平調(diào)度策略
3.能力調(diào)度器
4.延遲調(diào)度器(提交任務(wù)延遲執(zhí)行,等到數(shù)據(jù)盡可能局部化后再執(zhí)行)
5.主資源公平調(diào)度策略
Mesos
YARN(Yet Another Resource Negotiator)另一個資源調(diào)度器
統(tǒng)一資源管理與調(diào)度平臺(系統(tǒng))介紹
?
?
?
?
?
第五章 分布式協(xié)調(diào)系統(tǒng)
跟分布式協(xié)調(diào)系統(tǒng)相關(guān)的問題
1.當(dāng)主控服務(wù)器發(fā)生故障時,為了使系統(tǒng)不至癱瘓,如何能夠快速從備份機(jī)中選出新的主控服務(wù)器
2.當(dāng)分布式系統(tǒng)負(fù)載過高時,可以動態(tài)加入新機(jī)器通過水平擴(kuò)展來進(jìn)行負(fù)載均衡,此時分布式系統(tǒng)如何自動
? ?探測到有一臺新機(jī)器加入進(jìn)來?如何自動向其分配任務(wù)?
3.如何在分布式環(huán)境下實現(xiàn)鎖服務(wù)?
4.如何在多個進(jìn)程或者機(jī)器之間實現(xiàn)任務(wù)同步,比如所有進(jìn)程同時在某個時間點開始或者結(jié)束?
5.如何判斷集群中某臺機(jī)器是否依然存活?
6.如何快速構(gòu)建生產(chǎn)者-消費者消息隊列?
?
Chubby鎖服務(wù)
google發(fā)開的分布式協(xié)調(diào)系統(tǒng),基于Paxos協(xié)議,做了一些改進(jìn)
?
Zookeeper
Yahoo開發(fā)的分布式協(xié)調(diào)系統(tǒng)
和Chubby不同,Zookeeper的從節(jié)點可以接收讀請求,主節(jié)點負(fù)責(zé)更新請求。這樣整體吞吐量會很高
使用了改進(jìn)的Paxos協(xié)議ZAB協(xié)議
如果主節(jié)點來沒來得及更新,讀取從節(jié)點就可以讀到舊數(shù)據(jù),Zookeeper提供了sync命令,強(qiáng)制從主節(jié)點獲取狀態(tài)同步信息,這樣就不會讀到舊數(shù)據(jù)了
采用類似UNIX的目錄結(jié)構(gòu)
Zookeeper的典型應(yīng)用場景
1.領(lǐng)導(dǎo)者選舉(leader election)
2.配置管理(Configuration Management)
3.組成員管理(Group Membership)
4.任務(wù)分配
5.鎖管理(Locks)
6.雙向路障同步(Double Barrier)
?
使用Zookeeper的開源系統(tǒng)
1.HBase
2.Storm
3.Mesos
4.Pub-Sub(Yahoo)
5.SolrCloud
6.Kafka
?
?
?
?
?
第六章 分布式通訊
序列化與RPC框架
1.Protocol Buffer ? ?如果追求序列化的高效但不適用RPC可選擇
2.Thrift ? ? ? ? ? ? ? ? ? ?如果需要內(nèi)奸的便捷RPC支持可以選擇
3.Avro ? ? ? ? ? ? ? ? ? ? 如果需要和動態(tài)語言方便的繼承可選擇
消息隊列Kafka
應(yīng)用層多播通訊(Application-Level Multi-Broadcast) ?Gossip協(xié)議
也被稱為感染協(xié)議(Epidemic Protocol)
Dynamo和它的模仿者Cassandra,Riak等系統(tǒng)使用Gossip來進(jìn)行估值檢測,集群成員管理或副本修復(fù)
P2P下載系統(tǒng)BitTorrent使用Gossip在節(jié)點之間交換信息
Gossip包含三種
1.全部通知模型(Best Effort或Direct Mail)
? ? 當(dāng)某個節(jié)點有更新消息,則立即通知所有其他節(jié)點,這種傳播方式簡單但是容錯性不好
2.反熵模型(Anti-Entropy)
? ? 節(jié)點P隨機(jī)選擇另外一個節(jié)點Q然后與Q交換更新信息
? ? A)Push模式,P將更新信息退給Q,Q判斷是否比本地信息要新,如果是則更新本地消息
? ? B)Pull模式,P從Q獲取信息,如果比P本地信息要新,則P更新本地信息
? ? C)Push-Pull模式,P和Q同時進(jìn)行push和pull操作,即兩者同時互相通知對方更新
? ? Push推送給的節(jié)點可能已經(jīng)更新過了,所以越往后效率越差,pull是主動拉的所以越往后效果越好
? ? 效果來說 Push-Pull > Pull > Push
3.散布謠言模型(Rumor Mongering)
? ? 增加了傳播停止判斷,如果節(jié)點Q已被其他節(jié)點通知更新了,那么節(jié)點P增加其不再主動通知其他節(jié)點的概率
?
?
?
?
?
第七章 數(shù)據(jù)通道
一般Log數(shù)據(jù)收集系統(tǒng)的設(shè)計關(guān)注如下點
1.低延遲
2.可擴(kuò)展性
3.容錯性
Chukwa (包括數(shù)據(jù)收集和數(shù)據(jù)分析,但是過于依賴MR,而且設(shè)計定位不夠清晰未來發(fā)展堪憂)
Scribe
?
數(shù)據(jù)總線的作用是能夠形成數(shù)據(jù)變化通知通道,當(dāng)集中存儲的數(shù)據(jù)源(往往是關(guān)系型數(shù)據(jù)庫)的數(shù)據(jù)發(fā)生變化時,能盡快通知對數(shù)據(jù)變化敏感的相關(guān)應(yīng)用或者系統(tǒng)構(gòu)件。
設(shè)計數(shù)據(jù)總線系統(tǒng)要關(guān)注以下三點
1.近實時性
2.數(shù)據(jù)回溯能力
3.主題訂閱能力
Databus
Wormhole
?
數(shù)據(jù)導(dǎo)入/導(dǎo)出,將HDFS中的數(shù)據(jù)導(dǎo)入導(dǎo)出到關(guān)系數(shù)據(jù)庫中
sqoop專門用于在hadoop和其他關(guān)系數(shù)據(jù)庫或nosql之間進(jìn)行相互數(shù)據(jù)導(dǎo)入導(dǎo)出的工具
?
?
?
?
?
第八章 分布式文件系統(tǒng)
google文件系統(tǒng)GFS
colossus 谷歌下一代文件系統(tǒng)
HDFS
HayStack
?
文件存儲布局
1.行式存儲
2.列式存儲(Dremel)
3.混合式存儲(RCFile,ORCFile,Parquet)
?
糾刪碼(Erasure Code)
對于冷備的數(shù)據(jù)沒有必須再存三份,通過糾刪碼只需保留一份
糾刪碼通過對原始數(shù)據(jù)進(jìn)行校驗并保留,以增加冗余的方式來保證數(shù)據(jù)的可恢復(fù)性。
極大距離可分碼(Maximum Distance Separable codes MDS)是一種非常常用的糾刪碼,其將數(shù)據(jù)文件切割為等長的n個數(shù)據(jù)塊,并根據(jù)這n個數(shù)據(jù)塊生成m個冗余的校驗信息,這樣使得n+m塊數(shù)據(jù)中即使任意m塊數(shù)據(jù)丟失,也可以通過剩下的n塊數(shù)據(jù)對m塊損失的數(shù)據(jù)進(jìn)行重構(gòu),以此來完成容錯功能
Reed-Solomon糾刪碼
LRC編碼,RS編碼雖然是最優(yōu)的,但是如果10個塊中損壞了一個就需要從其他9個塊中拷貝數(shù)據(jù)恢復(fù)。在分布式環(huán)境中恢復(fù)需要大量的網(wǎng)絡(luò)數(shù)據(jù)拷貝,LRC編碼就是為了解決這種數(shù)據(jù)恢復(fù)時導(dǎo)致的大量網(wǎng)絡(luò)傳輸造成的網(wǎng)絡(luò)阻塞問題
?
?
?
?
?
第九章 內(nèi)存KV數(shù)據(jù)庫
對于內(nèi)存級數(shù)據(jù)庫來說,有兩種選擇
1.忽略成本提高可用性,與外存一樣在內(nèi)存中對數(shù)據(jù)進(jìn)行備份如常用的3備份策略,提高可用性,同時提高
? ? 并發(fā)讀性能
2.降低成本,內(nèi)存只保留一份,數(shù)據(jù)備份放在磁盤或者SSD中,但是可用性會有問題
RAMCloud使用第二種策略
Redis和Membase(現(xiàn)更名為CouchBase)使用第一種策略
?
?
?
?
?
第十章 列式數(shù)據(jù)庫
BigTable
PNUTS存儲系統(tǒng)
MegaStore
Spanner
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
