of56《云計算》第三版配套PPT課件目錄2.1

G

o

o

g

l

e文件系統(tǒng)G

F

S2.2分布式數(shù)據(jù)處理M

a

p

R

e

d

u

c

e2.3分布式鎖服務C

h

u

b

b

y2.4分布式結構化數(shù)據(jù)表B

i

g

t

a

b

l

e2.5分布式存儲系統(tǒng)M

e

g

a

s

t

o

r

e2.6大規(guī)模分布式系統(tǒng)的監(jiān)控基礎架構Dapper2.7海量數(shù)據(jù)的交互式分析工具D

r

e

m

e

l2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)P

o

w

e

r

D

r

i

l

l

2.9

G

o

o

g

l

e應用程序引擎56《云計算》第三版配套PPT課件初步了解ChubbyC

h

u

b

b

y是G

o

o

g

l

e設計的提供粗粒度鎖服務的一個文件系統(tǒng)，它基于松耦合分布式系統(tǒng)，解決了分布的一致性問題。通過使用Chubby的鎖

服務，用戶可以確保數(shù)據(jù)操作過程中的一致性Chubby作為一個穩(wěn)定

的存儲系統(tǒng)存儲包括元數(shù)據(jù)在內(nèi)的小數(shù)據(jù)Google內(nèi)部還使用Chubby進行名字服務（Name

Server）2

of2.3分布式鎖服務C

h

u

b

b

yof56《云計算》第三版配套PPT課件2.3

分布式鎖服務Chubby2.3.1

P

a

x

o

s算法2.3.2

C

h

u

b

b

y系統(tǒng)設計

2.3.3

C

h

u

b

b

y中的P

a

x

o

s2.3.4

C

h

u

b

b

y文件系統(tǒng)

2.3.5通信協(xié)議2.3.6正確性與性能《云計算》第三版配套PPT課件Paxos算法proposersacceptors提出決議批準決議三個

節(jié)點learners

獲取并使用已經(jīng)通過的決議決議只有在被proposers提出后才能批準每次只批準一個決議只有決議確定被批準后learners才能獲取這個決議三個4

of56條件2.3分布式鎖服務C

h

u

b

b

y《云計算》第三版配套PPT課件系統(tǒng)的約束條件p1：每個acceptor只接受它得到的第一個決議。p2：一旦某個決議得到通過，之后通過的決議必須和該決議保持一致。p2a：一旦某個決議v得到通過，之后任何acceptor再批準的決議必須是v。p2b：一旦某個決議v得到通過，之后任何proposer再提出的決議必須是v。p2c：如果一個編號為n的提案具有值v，那么存在一個“多數(shù)派”，要么它們中沒有誰批準過編號小于n的任何提案，要么它們進行的最近一次批準具有值v。為了保證決議的唯一性，acceptors也要滿足一個約束條件：當且僅當acceptors沒有收到編號大于n的請求時，acceptors才批準編號為n的提案。5

of562.3分布式鎖服務C

h

u

b

b

y《云計算》第三版配套PPT課件1準備階段2批準階段一個決議分為兩個階段proposers選擇一個提案并將它的編號設為n將它發(fā)送給acceptors中的一個“多數(shù)派”acceptors收到后，如果提案的編號大于它已經(jīng)回復的所有消息，則acceptors將自己上次的批準回復給proposers，并不再批準小于n的提案。當proposers接收到acceptors中的這個“多數(shù)派”的回復后，

就向回復請求的acceptors發(fā)送accept請求，在符合acceptors一方的約束條件下，acceptors收到accept請求后即批準這個請求。6

of562.3分布式鎖服務C

h

u

b

b

yof56《云計算》第三版配套PPT課件2.3

分布式鎖服務Chubby2.3.1

P

a

x

o

s算法2.3.2

C

h

u

b

b

y系統(tǒng)設計

2.3.3

C

h

u

b

b

y中的P

a

x

o

s2.3.4

C

h

u

b

b

y文件系統(tǒng)

2.3.5通信協(xié)議2.3.6正確性與性能《云計算》第三版配套PPT課件546Chubby的設計目標主要有以下幾點高可用性和高可靠性213高擴展性支持粗粒度的建議性鎖服務服務信息的直接存儲支持通報機制支持緩存機制2.3分布式鎖服務C

h

u

b

b

y8

of56《云計算》第三版配套PPT課件客戶端應用程序客戶端應用程序Chubby程序率Chubby程序率…遠程過程調(diào)用Chubby單元的五個服務器主服務器客戶端進程Chubby的基本架構在客戶這一端每個客戶應用程序都有

一個Chubby程序庫（ChubbyLibrary），客戶端的所有應用都是通過調(diào)用這個庫中的相關函數(shù)來完成的。服務器一端稱為Chubby單元，一般是由五個稱為副本（Replica）的服務器組成的，這五個副本在配置上完全一致，并且在系統(tǒng)剛開始時處于對等地位?？蛻舳朔掌鞫?

of562.3分布式鎖服務C

h

u

b

b

yof56《云計算》第三版配套PPT課件2.3

分布式鎖服務Chubby2.3.1

P

a

x

o

s算法2.3.2

C

h

u

b

b

y系統(tǒng)設計

2.3.3

C

h

u

b

b

y中的P

a

x

o

s2.3.4

C

h

u

b

b

y文件系統(tǒng)

2.3.5通信協(xié)議2.3.6正確性與性能《云計算》第三版配套PPT課件Chubby客戶端網(wǎng)絡副本網(wǎng)絡快照互換（Sanpshot

exchange）Paxos協(xié)議本地文件系統(tǒng)日志文件I/O快照容錯的日志（Fault-tolerant

Log）容錯的數(shù)據(jù)庫（Fault-tolerant

DB）ChubbyChubby協(xié)議RPC單個Chubby副本結構文件傳輸11

of562.3分布式鎖服務C

h

u

b

b

y《云計算》第三版配套PPT課件副本1副本2副本3值值值響應響應響應值提交客戶端應用程序Paxos構架Paxos協(xié)議容錯日志的API12

of562.3分布式鎖服務C

h

u

b

b

yof56《云計算》第三版配套PPT課件2.3

分布式鎖服務Chubby2.3.1

P

a

x

o

s算法2.3.2

C

h

u

b

b

y系統(tǒng)設計

2.3.3

C

h

u

b

b

y中的P

a

x

o

s2.3.4

C

h

u

b

b

y文件系統(tǒng)

2.3.5通信協(xié)議2.3.6正確性與性能《云計算》第三版配套PPT課件單調(diào)遞增的64位編號新節(jié)點實例號必定大于舊節(jié)點的實例號。1

實例號I

ns

t

a

nc

e

N

u

m

b

e

r鎖生成號Lock

Generation

Number鎖被用戶持有時該號增加。內(nèi)容生成號Content

Generation

Number文件內(nèi)容修改時該號增加。23A

C

L生成號ACL

Generation

NumberACL名被覆寫時該號增加。414

of562.3分布式鎖服務C

h

u

b

b

y《云計算》第三版配套PPT課件作

用Open()Close()Poison()GetContentsAndStat()GetStat()ReadDir()SetContents()SetACL()Delete()Acquire()Release()GetSequencer()SetSequencer()CheckSequencer()打開某個文件或者目錄來創(chuàng)建句柄關閉打開的句柄，后續(xù)的任何操作都將中止

中止當前未完成及后續(xù)的操作，但不關閉句柄返回文件內(nèi)容及元數(shù)據(jù)只返回文件元數(shù)據(jù)返回子目錄名稱及其元數(shù)據(jù)向文件中寫入內(nèi)容設置ACL名稱如果該節(jié)點沒有子節(jié)點的話則執(zhí)行刪除操作獲取鎖釋放鎖返回一個sequencer將sequencer和某個句柄進行關聯(lián)檢查某個sequencer是否有效常用的句柄函數(shù)及作用函數(shù)名稱2.3分布式鎖服務C

h

u

b

b

y15

of56of56《云計算》第三版配套PPT課件2.3

分布式鎖服務Chubby2.3.1

P

a

x

o

s算法2.3.2

C

h

u

b

b

y系統(tǒng)設計

2.3.3

C

h

u

b

b

y中的P

a

x

o

s2.3.4

C

h

u

b

b

y文件系統(tǒng)

2.3.5通信協(xié)議2.3.6正確性與性能《云計算》第三版配套PPT課件Chubby客戶端與服務器端的通信過程17

of562.3分布式鎖服務C

h

u

b

b

y《云計算》第三版配套PPT課件可能出現(xiàn)的兩種故障2.3分布式鎖服務C

h

u

b

b

y客戶端租約過期主服務器出錯1218

of56of56《云計算》第三版配套PPT課件2.3

分布式鎖服務Chubby2.3.1

P

a

x

o

s算法2.3.2

C

h

u

b

b

y系統(tǒng)設計

2.3.3

C

h

u

b

b

y中的P

a

x

o

s2.3.4

C

h

u

b

b

y文件系統(tǒng)

2.3.5通信協(xié)議2.3.6正確性與性能《云計算》第三版配套PPT課件—致性2.3分布式鎖服務C

h

u

b

b

y正確性與性能每個Chubby單元是由五

個副本組成的，這五個副本中需要選舉產(chǎn)生一個主服務器，這種選舉本質上就是一個一致性問題安全性采用的是ACL形式的安全保障措施。只要不被覆寫，子節(jié)點都是直接繼承父節(jié)點的ACL名性能優(yōu)化提高主服務器默認的租約期、使用協(xié)議轉換服務將

Chubby協(xié)議轉換成較簡

單的協(xié)議、客戶端一致性緩存等20

of56《云計算》第三版配套PPT課件Chubby的ACL機制2.3分布式鎖服務C

h

u

b

b

y用戶chinacloud提出向文件CLOUD中寫入內(nèi)容的請求。CLOUD首先讀取自身的寫ACL名fun，接著在fun中查到了chinacloud這一行記錄，于是返回信息允許chinacloud對文件進行寫操作，此時chinacloud才被允許向CLOUD寫入內(nèi)容。其他的操作和寫操作類似。21

of56《云計算》第三版配套PPT課件目錄2.1

G

o

o

g

l

e文件系統(tǒng)G

F

S2.2分布式數(shù)據(jù)處理M

a

p

R

e

d

u

c

e2.3分布式鎖服務C

h

u

b

b

y2.4分布式結構化數(shù)據(jù)表B

i

g

t

a

b

l

e2.5分布式存儲系統(tǒng)M

e

g

a

s

t

o

r

e2.6大規(guī)模分布式系統(tǒng)的監(jiān)控基礎架構Dapper2.7海量數(shù)據(jù)的交互式分析工具D

r

e

m

e

l2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)P

o

w

e

r

D

r

i

l

l

2.9

G

o

o

g

l

e應用程序引擎22of56《云計算》第三版配套PPT課件2.4

分布式結構化數(shù)據(jù)表Bigtable2.4.1設計動機與目標2.4.2數(shù)據(jù)模型2.4.3系統(tǒng)架構2.4.4主服務器2.4.5子表服務器2.4.6性能優(yōu)化of56《云計算》第三版配套PPT課件2.4分布式結構化數(shù)據(jù)表B

i

g

t

a

b

l

eBigtable的設計動機123需要存儲的數(shù)據(jù)種類繁多海量的服務請求商用數(shù)據(jù)庫

無法滿足需求包括URL、網(wǎng)頁內(nèi)容、用戶的個性化設置在內(nèi)的數(shù)據(jù)都是Google需要經(jīng)常處理的Google運行著目前世界上最繁忙的系統(tǒng)，它每時每刻處理的客戶服務請求數(shù)量是普通的系統(tǒng)根本無法承受的一方面現(xiàn)有商用數(shù)據(jù)庫的設計著眼點在于其通用性。

另一方面對于底層系統(tǒng)的完全掌控會給后期的系統(tǒng)維護、升級帶來極大的便利24

of56《云計算》第三版配套PPT課件2.4分布式結構化數(shù)據(jù)表B

i

g

t

a

b

l

e25

of56Bigtable應達到的基本目標廣泛的適用性很強的可擴展性高可用性簡單性B

i

g

t

a

b

l

e是為了滿足一系列G

o

o

g

l

e產(chǎn)品而并非特定產(chǎn)品的存儲要求。根據(jù)需要隨時可以加入或撤銷服務器確保幾乎所有的情況下系統(tǒng)都可用底層系統(tǒng)的簡單性既可以減少系統(tǒng)出錯的概率，也為上層應用的開發(fā)帶來便利of56《云計算》第三版配套PPT課件2.4

分布式結構化數(shù)據(jù)表Bigtable2.4.1設計動機與目標2.4.2數(shù)據(jù)模型2.4.3系統(tǒng)架構2.4.4主服務器2.4.5子表服務器2.4.6性能優(yōu)化《云計算》第三版配套PPT課件2.4分布式結構化數(shù)據(jù)表B

i

g

t

a

b

l

e27

of56Bigtable數(shù)據(jù)的存儲格式Bigtable是一個分布式多維映射表，表中的數(shù)據(jù)通過一個行關鍵字（Row

Key）、一個列關鍵字（Column

Key）以及一個時間戳（Time

Stamp）進行索引Bigtable的存儲邏輯可以表示為：(row:string,

column:string,

time:int64)→string《云計算》第三版配套PPT課件2.4分布式結構化數(shù)據(jù)表B

i

g

t

a

b

l

e行列時間戳Bigtable的行關鍵字可以是任意的字符串，但是大小不能夠超過

64KB28

of56表中數(shù)據(jù)都是根據(jù)行關鍵字進行排序的，排序使用的是詞典序同一地址域的網(wǎng)頁會被存儲在表中的連續(xù)位置倒排便于數(shù)據(jù)壓縮，可以大幅提高壓縮率將其組織成所謂的列族（Column

Family）族名必須有意義，限定詞則可以任意選定組織的數(shù)據(jù)結構清晰明了，含義也很清楚族同時也是Bigtable中訪問控制（Access

Control）的基本單元Bigtable中的時間戳是64位整型數(shù)，具體的賦值方式可以用戶自行定義Google的很多服務比如網(wǎng)頁檢

索和用戶的個性化設置等都需要保存不同時間的數(shù)據(jù)，這些不同的數(shù)據(jù)版本必須通過時間戳來區(qū)分。of56《云計算》第三版配套PPT課件2.4

分布式結構化數(shù)據(jù)表Bigtable2.4.1設計動機與目標2.4.2數(shù)據(jù)模型2.4.3系統(tǒng)架構2.4.4主服務器2.4.5子表服務器2.4.6性能優(yōu)化《云計算》第三版配套PPT課件Bigtable基本架構30

of562.4分布式結構化數(shù)據(jù)表B

i

g

t

a

b

l

e《云計算》第三版配套PPT課件2.4分布式結構化數(shù)據(jù)表B

i

g

t

a

b

l

e31

of56Bigtable中Chubby的主要作用作用一選取并保證同一時間內(nèi)只有一個主服務器（

M

a

s

t

e

r

S

e

r

v

e

r

）。獲取子表的位置信息。保存B

i

g

t

a

b

l

e的模式信息及訪問控制列表。作用二作用三of56《云計算》第三版配套PPT課件2.4

分布式結構化數(shù)據(jù)表Bigtable2.4.1設計動機與目標2.4.2數(shù)據(jù)模型2.4.3系統(tǒng)架構2.4.4主服務器2.4.5子表服務器2.4.6性能優(yōu)化《云計算》第三版配套PPT課件2.4分布式結構化數(shù)據(jù)表B

i

g

t

a

b

l

e主服務器新子表分配子表服務器狀態(tài)監(jiān)控子服務器之間的負載均衡當一個新的子表產(chǎn)生時，主服務器通過一個加載命令將其分配給一個空間足夠的子表服務器。創(chuàng)建新表、表合并以及較大子表的分裂都會產(chǎn)生一個或多個新子表。分割完成之后子服務器需要向主服務發(fā)出一個通知。主服務器必須對子表服務器的狀態(tài)進行監(jiān)控，以便及時檢測到服務器的加入或撤銷33

of56《云計算》第三版配套PPT課件2.4分布式結構化數(shù)據(jù)表B

i

g

t

a

b

l

e從Chubby中獲取

一個獨占鎖，確保同一時間只有一個主服務器Bigtable中Chubby的主要作用掃描服務器目錄，發(fā)現(xiàn)目前活躍的子表服務器與所有的活躍子表服務器取得聯(lián)系以便了解所有子表的分配情況通過掃描元數(shù)據(jù)表（MetadataTable），發(fā)現(xiàn)未分配的子表并將其分配到合適的子表服務器步驟

1步驟

3步驟

2步驟

434

of56of56《云計算》第三版配套PPT課件2.4

分布式結構化數(shù)據(jù)表Bigtable2.4.1設計動機與目標2.4.2數(shù)據(jù)模型2.4.3系統(tǒng)架構2.4.4主服務器2.4.5子表服務器2.4.6性能優(yōu)化《云計算》第三版配套PPT課件64KB塊64KB塊…SSTable索引2.4分布式結構化數(shù)據(jù)表B

i

g

t

a

b

l

e36

of56SSTable格式的基本示意SSTable是Google為Bigtable設計的內(nèi)部數(shù)據(jù)存儲格式。所有的SSTable文件都存儲在GFS上，用戶可以通過鍵來查詢相應的值。《云計算》第三版配套PPT課件64KB塊塊…

64KBSSTable索引塊37

of5664KB

…

64KB塊SSTable索引…2.4分布式結構化數(shù)據(jù)表B

i

g

t

a

b

l

e子表實際組成不同子表的SSTable可以共享每個子表服務器上僅保存一個日志文件Bigtable規(guī)定將日志的內(nèi)容按照鍵值進行排序每個子表服務器上保存的子表數(shù)量可以從幾十到上千不等，通常情況下是100個左右日志《云計算》第三版配套PPT課件Chubby文件根子表（元數(shù)據(jù)表中第一條記錄）

…

…

…

…

…

用戶表1

…

用戶表N其他元數(shù)據(jù)子表······2.4分布式結構化數(shù)據(jù)表B

i

g

t

a

b

l

e子表地址組成Bigtable系統(tǒng)的內(nèi)部采用的是一種類似B+樹的三層查詢體系……···38

of56《云計算》第三版配套PPT課件2.4分布式結構化數(shù)據(jù)表B

i

g

t

a

b

l

eBigtable數(shù)據(jù)存儲及讀/寫操作較新的數(shù)據(jù)存儲在內(nèi)存中一個稱為內(nèi)存表（Memtable）的有序緩沖里，較

的數(shù)據(jù)則以SSTable格式保存在GFS中。讀和寫操作有很大的差異性39

of56《云計算》第三版配套PPT課件2.4分布式結構化數(shù)據(jù)表B

i

g

t

a

b

l

eSSTableSSTable內(nèi)存表SSTable內(nèi)存表內(nèi)存表三種形式壓縮之間的關系次壓縮次壓縮SSTableSSTable合并壓縮SSTable主壓縮……40

of56…………of56《云計算》第三版配套PPT課件2.4

分布式結構化數(shù)據(jù)表Bigtable2.4.1設計動機與目標2.4.2數(shù)據(jù)模型2.4.3系統(tǒng)架構2.4.4主服務器2.4.5子表服務器2.4.6性能