?

第一章 數(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表

memcache一致性hash算法介紹

?

?

?

?

?

第二章 數(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é)議

?

詳細(xì)解析Dynamo存儲引擎

向量時鐘

事務(wù)和兩階段提交

關(guān)于分布式事務(wù)、兩階段提交、一階段提交、Best Efforts 1PC模式和事務(wù)補(bǔ)償機(jī)制的研究

Paxos百科

Paxos算法細(xì)節(jié)詳解(一)--通過現(xiàn)實世界描述算法

分布式一致性Paxos算法學(xué)習(xí)筆記（一）：paxos大雜燴

分布式系統(tǒng)的Raft算法

Raft一致性算法

?

?

?

?

?

第三章 大數(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ù)就越少

查找的時候首先從第一層開始，再依次往下

SkipList跳表的基本原理

?

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的索引

LSM樹 VS B+樹

?

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ù)。

Merkle Hash Tree

Merkle Tree算法詳解

?

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)。

LZ77壓縮算法

LZ77 算法的基本流程

snappy百科

?

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ù)量

Cuckoo hashing算法分析

?

?

?

?

?

第四章 集群資源管理與調(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)）介紹

YARN百科

Apache Mesos總體架構(gòu)?

?

?

?

?

?

第五章 分布式協(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

?