?

第一章 數據的分片與路由

分片包括二個映射:

1.key-partition映射，將數據記錄映射到數據分片空間中，一般是多對一的映射即一個數據分片包含多條記錄

2.partition-macheine映射，將數據分片映射到物理機器中，也是多對一映射，即一臺物理機器容納多個數據分片

?

哈希分片(hash partition)

1.Round Robin

? ? H(key) = hash(key) mod (K+1) ? ? K為當前機器數量，新增一臺物理機器就是K+1

? ? RoundRobin算法在增加一臺機器后整個結果都變了

2.虛擬桶(Virtual Buckets)

? ? Membase(現更名為Couchbase)使用的算法

3.一致性hash(Consistent Hashing)

? ? 如memcached使用的一致性hash算法

范圍分片(Range Partition)

? ? 將所有記錄的主鍵先排序，然后在排好序的主鍵記錄空間里將記錄劃分成數據分片，每個數據分片存儲有序的主鍵空間片段內的所有記錄。現實實現中使用一個數據分片映射表，記錄表每一項記載數據分片的最小主鍵及其對應的物理主機地址

? ? 也就是需要一個元記錄表，記錄最終記錄所在機器的位置，比如HBase的meta表

memcache一致性hash算法介紹

?

?

?

?

?

第二章 數據復制與一致性

CAP

一致性(Consistency)在分布式系統中的同一數據多副本情形下，對于數據的更新操作提現處的效果與只有

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?單份數據是一樣的

可用性(Availability) 客戶端在任何時刻對大規模數據系統的讀/寫操作都應該保證在限定的時間內完成

分區容忍性(Partition Tolerance) ?在大規模分布式數據系統中，網絡分區現象，即分區間的機器無法進行

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 網絡通訊的情況是必然會發生的，所以系統應該能夠在這種情況下繼續工作

對于分布式系統來說P 是一定要滿足的，所以在CAP三者不能兼顧的情況下，要不選擇AP，要不選擇CP

?

ACID原則

原子性(Atomicity) 一個事務要么全部執行，要么全部不執行

一致性(Consistency) 事務在開始和結束時，應該始終滿足一致性約束條件，比如系統要求A+B=100，那么

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?事務如果改變了A的數值，則B的數值也要相應的修改來滿足這種一致性要求

事務獨立(Isolationi) 如果有多個事務同時執行，彼此之間不需要知曉對方的存在，而且執行時相互不影響，

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?不允許出現兩個事務交錯，間隔執行部分任務的情況，也即事務之間需要序列化執行

持久性(Durability) 事務運行成功以后，對系統狀態的更新是永久的，不會無緣無故的回滾撤銷

?

BASE原則

基本可用(Basically Available)在絕大多數時間內系統處于可用狀態，允許偶爾的失敗，所以稱基本可用

軟狀態或者柔性狀態(Soft State)是指數據狀態不要求在任意時刻都完全保持同步，到目前為止軟狀態并

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 無一個統一明晰的定義，即處于有狀態和無狀態之間

最終一致性(Eventual Consistency)在給定時間窗口內數據會達到一致狀態

?

一致性模型

1.強一致性

2.最終一致性

3.因果一致性

4.讀你所讀一致性

5.會話一致性

6.單調讀一致性

7.單調寫一致性

?

副本更新策略

1.同時更新(通過一致性協議來更新)

2.主從更新(同步，異步更新，混合更新)

3.任意節點更新(同步，異步)

?

一致性協議

兩階段提交(Two-Phrase Commit 2PC)

?

向量時鐘

RWN協議

N表示在分布式系統中有多少個備份數據

W表示一次成功的更新操作至少要有W份數據寫入成功

R表示一次成功的讀取數據要求至少有R份數據成功讀取

如果滿足 ? ?R + W > N ? ? ? 則可稱為滿足 數據一致性協議

?

Paxos一致協議

Raft協議

?

詳細解析Dynamo存儲引擎

向量時鐘

事務和兩階段提交

關于分布式事務、兩階段提交、一階段提交、Best Efforts 1PC模式和事務補償機制的研究

Paxos百科

Paxos算法細節詳解(一)--通過現實世界描述算法

分布式一致性Paxos算法學習筆記（一）：paxos大雜燴

分布式系統的Raft算法

Raft一致性算法

?

?

?

?

?

第三章 大數據常用的算法與數據結構

布隆過濾器(Bloom Filter)

使用一個N個函數，對指定要查找的key執行函數 fun1(key)如果落到了數組的某一位上就將這位設置為1

所以指定了三個函數之后會有三個bit被設置為1

bloom filter會誤判但不會漏判，而且存在一定的誤判率，和數組大小，函數個數都有關系

bloom filter只能用于數據添加操作，數據刪除就不行了，因為一個bit只能表示有和無不能再有其他狀態了。解決辦法是用多個bit來表示一個狀態

這個就是計數BF(Counting Bloom Filter)

布隆過濾器在Chrome的URL判斷，比特幣歷史交易，hbase，cassandra中都有使用

布隆過濾器百科

?

SkipList

在插入，刪除，查找數據時都能保證O(long(N))時間復雜度，hbase和levelDB都使用了跳表

本質上是一個鏈表結構，但是每個每個節點可能都有N個指向后面的節點，即一個節點有多個后續，而節點包含多少個后續是隨機產生的。

最下面那層包含所有的數據，倒數第二層的數據節點個數就少一些，層數越往上節點數就越少

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

SkipList跳表的基本原理

?

LSM樹

首先將數據寫到預寫日志中，然后將寫的數據先放到內存中這樣就可以保證以后的隨機讀了，如果內存中的數據到一定大小后，就將數據flush到磁盤上。從整個結構上來說就像一顆樹，整體是字典排序有序的。

一個節點下可能會被flush了一個或多個文件，如果定位到某個節點(就類似HBase中的region)那么就需要遍歷下面的所有文件(也就是HFile)才能讀取到對應的值了，這個讀取的可以使用布隆過濾器優化提高速度。

本質上來說就像region一樣，一開始可能很少，后來越來越多，region按照key順序排序，其實只有三層的樹，root表-->meta表-->業務表

然后region不斷變多，但是region下面的HFile數量還是1個到7個(默認最多7個)，當達到HFile達到一定數量后就會合并，這樣就減少region下面的HFile提高讀性能。

LSM樹由來、設計思想以及應用到HBase的索引

LSM樹 VS B+樹

?

Merkle Hash Tree

每個節點和其所有子節點都會計算一次hash，這樣如果比較根節點的hash有變化了，則會依次找尋到變化的子節點，最后找到最終的變化數據

被廣泛運用于分布式領域，主要用來在海量數據下快速定位少量變化的數據內容(變化原因可能是損毀，篡改或者正常變化等)

如P2P下載系統BitTorrent，Git等工具，比特幣以及Dynamo，Riak，Cassandra等

Dynamo中結合Merkle樹和Gossip協議，假設A和B存儲了相同的數據副本。此時兩個節點都對兩者所存儲數據的共同鍵值范圍(Key Range)部分建立Merkle樹。之后可以比較兩個節點的Merkle樹節點hash值來查找不同部分，首先比較根節點再比較所有葉子節點。Gossip協議在上述過程中起的作用是：兩個節點在交換Merkle樹節點內容以及同步數據內容時可通過這個協議來進行

比特幣通過Merkle樹來驗證交易的歷史數據。

Merkle Hash Tree

Merkle Tree算法詳解

?

Snappy與LZSS算法

LZSS是LZ77的一種，LZ77是一種動態詞典編碼(dictionary coding)

詞典編碼的意思是：文本中的詞用它在詞典中表示位置的號碼代替無損數據壓縮方法，一般分為靜態詞典和動態詞典。

靜態詞典需要事先構造，采用動態詞典時編碼器將被壓縮的文本中自動導出詞典，解碼器解碼時邊解碼邊構造詞典。?

?

LZ77采用滑動窗口和前向緩沖區

新讀入的字節放到滑動窗口中(也是處理過的字節)，如果前向緩沖區(也就是未處理的部分)和滑動窗口中數據有匹配，則記錄一個標號，類似三元數組<指針，長度，后續字符>，如(3,2)表示從開頭第三個字節開始匹配兩個

一個常用的技巧是：將滑動窗口內字符串的各種長度片段存入哈希表，哈希表的值記載在滑動窗口的出現位置

Snappy則做了一些優化，設置了最少長度為4，也就是說必須至少匹配4個字符串才進行壓縮處理。同時設定hash表內的字符串片段固定長度為4。此外Snappy將數據切割成32K大小，數據塊之間無關聯。

LZ77壓縮算法

LZ77 算法的基本流程

snappy百科

?

Cuckoo Hashing

傳統hash只使用一個hash函數，cuckoo同時使用兩個不同的hash函數H1(x)和H2(x)

如果計算出H1(x)和H2(x)任意一個不為空就可以插入，如果兩者都不為空則選擇一個桶將已有的值y踢出去，由x來插入相應的位置。y的值重復上述步驟計算一個新的值如果再由沖突，則踢掉z插入y繼續執行。這樣可能導致無限循環所以需要設定一個最大替換次數，如果到了最大替換次數需要更換hash函數或者增加hash空間中桶的數量

Cuckoo hashing算法分析

?

?

?

?

?

第四章 集群資源管理與調度

采用獨立的資源管理與調度系統而非靜態劃分資源有如下好處

1.集群整體資源利用率高，所有的資源統一管理與調度，可以根據不同計算任務的即時需要動態分配資源

2.可增加數據共享能力，對于有些共享的數據資源，需要分別在分配給不同計算任務的子集群中重復存儲

3.支持多類型計算框架和多版本計算框架

?

調度系統設計的基本問題

1.資源異質性與工作負載異質性

2.數據局部性(從性能角度盡量選擇A，再是B)

? ? A節點局部性

? ? B機架局部性

? ? C全局局部性

3.搶占式調度和非搶占式調度

4.資源分配粒度

5.餓死與死鎖(如果不斷出現高優先級任務，低優先級的可能出現餓死)

6.資源隔離

?

三種資源管理與調度系統范型

1.集中式調度器(Monolithic Scheduler)

2.兩級調度器(Two-Level Scheduler)

3.狀態共享調度器(Shared-State Scheduler)

?

資源調度策略

1.FIFO調度側路了

2.公平調度策略

3.能力調度器

4.延遲調度器(提交任務延遲執行，等到數據盡可能局部化后再執行)

5.主資源公平調度策略

Mesos

YARN(Yet Another Resource Negotiator)另一個資源調度器

統一資源管理與調度平臺（系統）介紹

YARN百科

Apache Mesos總體架構?

?

?

?

?

?

第五章 分布式協調系統

跟分布式協調系統相關的問題

1.當主控服務器發生故障時，為了使系統不至癱瘓，如何能夠快速從備份機中選出新的主控服務器

2.當分布式系統負載過高時，可以動態加入新機器通過水平擴展來進行負載均衡，此時分布式系統如何自動

? ?探測到有一臺新機器加入進來？如何自動向其分配任務？

3.如何在分布式環境下實現鎖服務？

4.如何在多個進程或者機器之間實現任務同步，比如所有進程同時在某個時間點開始或者結束？

5.如何判斷集群中某臺機器是否依然存活？

6.如何快速構建生產者-消費者消息隊列？

?

Chubby鎖服務

google發開的分布式協調系統，基于Paxos協議，做了一些改進

?

Zookeeper

Yahoo開發的分布式協調系統

和Chubby不同，Zookeeper的從節點可以接收讀請求，主節點負責更新請求。這樣整體吞吐量會很高

使用了改進的Paxos協議ZAB協議

如果主節點來沒來得及更新，讀取從節點就可以讀到舊數據，Zookeeper提供了sync命令，強制從主節點獲取狀態同步信息，這樣就不會讀到舊數據了

采用類似UNIX的目錄結構

Zookeeper的典型應用場景

1.領導者選舉(leader election)

2.配置管理(Configuration Management)

3.組成員管理(Group Membership)

4.任務分配

5.鎖管理(Locks)

6.雙向路障同步(Double Barrier)

?

使用Zookeeper的開源系統

1.HBase

2.Storm

3.Mesos

4.Pub-Sub(Yahoo)

5.SolrCloud

6.Kafka

?

?

?

?

?

第六章 分布式通訊

序列化與RPC框架

1.Protocol Buffer ? ?如果追求序列化的高效但不適用RPC可選擇

2.Thrift ? ? ? ? ? ? ? ? ? ?如果需要內奸的便捷RPC支持可以選擇

3.Avro ? ? ? ? ? ? ? ? ? ? 如果需要和動態語言方便的繼承可選擇

消息隊列Kafka

應用層多播通訊(Application-Level Multi-Broadcast) ?Gossip協議

也被稱為感染協議(Epidemic Protocol)

Dynamo和它的模仿者Cassandra，Riak等系統使用Gossip來進行估值檢測，集群成員管理或副本修復

P2P下載系統BitTorrent使用Gossip在節點之間交換信息

Gossip包含三種

1.全部通知模型(Best Effort或Direct Mail)

? ? 當某個節點有更新消息，則立即通知所有其他節點，這種傳播方式簡單但是容錯性不好

2.反熵模型(Anti-Entropy)

? ? 節點P隨機選擇另外一個節點Q然后與Q交換更新信息

? ? A)Push模式，P將更新信息退給Q，Q判斷是否比本地信息要新，如果是則更新本地消息

? ? B)Pull模式，P從Q獲取信息，如果比P本地信息要新，則P更新本地信息

? ? C)Push-Pull模式，P和Q同時進行push和pull操作，即兩者同時互相通知對方更新

? ? Push推送給的節點可能已經更新過了，所以越往后效率越差，pull是主動拉的所以越往后效果越好

? ? 效果來說 Push-Pull > Pull > Push

3.散布謠言模型(Rumor Mongering)

? ? 增加了傳播停止判斷，如果節點Q已被其他節點通知更新了，那么節點P增加其不再主動通知其他節點的概率

?

?

?

?

?

第七章 數據通道

一般Log數據收集系統的設計關注如下點

1.低延遲

2.可擴展性

3.容錯性

Chukwa (包括數據收集和數據分析，但是過于依賴MR，而且設計定位不夠清晰未來發展堪憂)

Scribe

?

數據總線的作用是能夠形成數據變化通知通道，當集中存儲的數據源(往往是關系型數據庫)的數據發生變化時，能盡快通知對數據變化敏感的相關應用或者系統構件。

設計數據總線系統要關注以下三點

1.近實時性

2.數據回溯能力

3.主題訂閱能力

Databus

Wormhole

?

數據導入/導出，將HDFS中的數據導入導出到關系數據庫中

sqoop專門用于在hadoop和其他關系數據庫或nosql之間進行相互數據導入導出的工具

?

?

?

?

?

第八章 分布式文件系統

google文件系統GFS

colossus 谷歌下一代文件系統

HDFS

HayStack

?

文件存儲布局

1.行式存儲

2.列式存儲(Dremel)

3.混合式存儲(RCFile，ORCFile，Parquet)

?

糾刪碼(Erasure Code)

對于冷備的數據沒有必須再存三份，通過糾刪碼只需保留一份

糾刪碼通過對原始數據進行校驗并保留，以增加冗余的方式來保證數據的可恢復性。

極大距離可分碼(Maximum Distance Separable codes MDS)是一種非常常用的糾刪碼，其將數據文件切割為等長的n個數據塊，并根據這n個數據塊生成m個冗余的校驗信息，這樣使得n+m塊數據中即使任意m塊數據丟失，也可以通過剩下的n塊數據對m塊損失的數據進行重構，以此來完成容錯功能

Reed-Solomon糾刪碼

LRC編碼，RS編碼雖然是最優的，但是如果10個塊中損壞了一個就需要從其他9個塊中拷貝數據恢復。在分布式環境中恢復需要大量的網絡數據拷貝，LRC編碼就是為了解決這種數據恢復時導致的大量網絡傳輸造成的網絡阻塞問題

?

?

?

?

?

第九章 內存KV數據庫

對于內存級數據庫來說，有兩種選擇

1.忽略成本提高可用性，與外存一樣在內存中對數據進行備份如常用的3備份策略，提高可用性，同時提高

? ? 并發讀性能

2.降低成本，內存只保留一份，數據備份放在磁盤或者SSD中，但是可用性會有問題

RAMCloud使用第二種策略

Redis和Membase(現更名為CouchBase)使用第一種策略

?

?

?

?

?

第十章 列式數據庫

BigTable

PNUTS存儲系統

MegaStore

Spanner

?