走進系統(tǒng)設(shè)計高級進階視頻教程

系統(tǒng)設(shè)計Distributed

System

Design

2（九章

課件）本節(jié)主講人：北丐：九章課程不允許

，否則將

，賠償損失掃描

/獲取

面試題及

解答:

ninechapter:

ht

/ninechapter知乎:

http://z

/jiuzhang官網(wǎng):

http:

第1頁今日課程大綱Design

a

Bigtable, ,

Amazon,

AlibabaNoSQL

database

設(shè)計框架和原理SStable

讀和寫B(tài)loom

Filter第2頁Interviewer:

What

is

bigtable?第3頁What

isbigtable?NoSQL

DataBaseCompanyBigtableHbaseYahoo(Alitaba)Open

Source

of

BigtableCassandraDynamoDBAmazonComparison

of

different

No

SQL

database:/communiparison-of-nosql-database-management-systems-and-models第4頁為什么要講bigtable

的實現(xiàn)？面試題1.解決相類似系統(tǒng)設(shè)計題,比如:Look

upservice追問NoSQL

How

to

scale的原理第5頁文件系統(tǒng)vs

數(shù)據(jù)庫系統(tǒng)第6頁文件系統(tǒng)?操作：輸入：/home/jinyong/character_name.txt輸出:文件內(nèi)容第7頁如果有下面需求找到“ ”的“顏值”1、打開文件2、For循環(huán)掃描文件的內(nèi)容然后找 的顏值‘顏值’:5,‘身高’:‘顏值’:9,‘顏值’:7,‘身高’:‘180cm’},‘身高’:‘170cm’},{{‘ ’

:‘’,‘160cm’},{‘ ’

:‘

’,{‘

’:‘東邪’,}/home/jinyong/character_name.txt第8頁文件系統(tǒng)缺點？文件系統(tǒng)提供一些簡單的讀寫文件操作所以實際查詢當中有復(fù)雜的查詢需求：比如：查詢

顏值查詢顏值小于5的查詢所有人的身高平均值需要一個更復(fù)雜的系統(tǒng)建立在文件系統(tǒng)之上第9頁第10頁數(shù)據(jù)庫系統(tǒng)1、建立在文件系統(tǒng)之上2、負責組織把一些數(shù)據(jù)存到文件系統(tǒng)3、對外的接口比較方便操作數(shù)據(jù)數(shù)據(jù)庫系統(tǒng)操作輸入：

key（

+顏值）輸出:value

（5）查詢

顏值顏值身高5東邪第11頁設(shè)計數(shù)據(jù)庫系統(tǒng)第12頁Scenario需求第13查詢：

key

（

+

顏值）返回：

value

（5）因為后端系統(tǒng)通常給web

server使用，Scenario比較單一頁Storage數(shù)據(jù)庫怎么以表的形式？Yes/No第顏值身高東邪170頁數(shù)據(jù)最終都會存到文件里面‘顏值’

:

5,

‘身高’

:{{‘ ’

:

‘linghuchong’,‘160cm’},‘顏值’

:

9,

‘身高’

:‘顏值’

:

7,

‘身高’

:{‘ ’

:

‘guojing’,‘180cm’},{‘ ’

:

‘dongxie’,‘170cm’},}第15頁從文件系統(tǒng)基礎(chǔ)上思考搭建數(shù)據(jù)庫系統(tǒng)第16頁在文件里面怎么更好支持查詢操作？{{‘ ’

:

‘linghuchong’,

‘顏值’

:

5,

‘身高’

:‘160cm’},第17頁‘顏值’

:

9,

‘身高’

:‘顏值’

:

7,

‘身高’

:{‘ ’

:

‘guojing’,‘180cm’},{‘ ’

:

‘dongxie’,‘170cm’},}文件到內(nèi)存里面內(nèi)存里面查詢有什么問題？第18頁先對數(shù)據(jù)進行排序？不需要一個一個在文件里面查詢只需要二分掃描那么文件在硬盤里面，怎么在硬盤里面進行二分呢？第19頁第20頁硬盤二分查詢畫圖解釋硬盤二分Read

More:http:/

/questions/736556/binary-search-in-a-sorted-memory-mapped-file-in-java有一天查詢解決了，整容了怎么辦？修改

顏值，從5變到61.

直接在文件里面修改整個文件，修改好了，重新寫入覆蓋原來文件3.

不修改，直接append操作加在文件最后面2.第21頁1.

直接在文件里面修改很難做到直接修改內(nèi)容，如果原來是4個字節(jié)，現(xiàn)在修改成8個字節(jié)，那么之后的內(nèi)容都需要移動位置。2.整個文件，修改好了，重新寫入覆蓋原來文件非常耗費時間，每次要讀出寫入其他多余不變的內(nèi)容3.

直接append操作加在文件最后面好處：特別快修改文件內(nèi)容第22頁Bigtable為了寫優(yōu)化選擇了直接Append壞處：數(shù)據(jù)怎么辦，文件沒有順序,？第23頁把所有關(guān)于數(shù)據(jù)怎么辦？的顏值記錄都讀出來第24頁怎么解決文件沒有順序不能二分查詢的問題？過一段時間

把文件有序整理第25頁有木有一個辦法既可以讀的時候二分查詢又可以寫的時候?qū)懺谧詈骯ppend操作？分塊有序每一塊都是

有序?qū)懙臅r候只有最后一塊是無序的第26頁塊會越寫越多，會有很多重復(fù)(

經(jīng)常做整形手術(shù))重復(fù)非常多每次查詢所有的塊非常消耗時間http:定期K路歸并/en/problem/merge-k-sorted-arrays/第27頁第28頁完整系統(tǒng)讀/寫過程One

Work

Solution第29頁寫入過程Write

key:linghuchong+appearance,value:

7One

MachineMemoryfile0,

Address0file1,

Address12.

Append

key:linghuchoappearance,value:

7DiskFile

0

（有序）Linghuchong+appearance:

5Renyingying+appearance:

8…File

1

（無序）ng+

Chen+appearance:

9Angelababy+appearance:

10…Linghuchong+appearance:

7寫入過程Client

1第30頁1.第31頁怎么把最后一個File從無序變成有序？讀入到內(nèi)存快速排序硬盤外部排序可不可以一開始就存在內(nèi)存里面？1. 讀入到內(nèi)存快速排序。所有數(shù)據(jù)1次硬盤寫入，1次硬盤+內(nèi)存排序+1次硬盤寫入硬盤外部排序有必要么？可不可以一開始就存在內(nèi)存里面？內(nèi)存排序+1次硬盤寫入寫入過程第32頁寫入過程File

0

（有序）Linghuchong+appearance:

5Renyingying+appearance:

8…Client

11. Write

key:linghuchong+appearance,value:

7DiskFile

1（有序）Memoryfile0,

Address0file1,

Address12.

Append

key:liappearance,valunghuchong+e:

7One

MachineSorted

ListChen+appearance:

9Angelababy+appearance:

10…Linghuchong+appearance:

73.

Serialize

to

disk第33頁第34頁Serializationhttp:

/en/problem/binary-tree-serialization/第35頁Interviewer:機器掛了，內(nèi)存沒了？第36頁Write

Ahead

Log(WAL)那寫log豈不是又要寫硬盤WAL

非常方便,不像重要數(shù)據(jù)需要整理第37頁內(nèi)存排序+1次硬盤寫入+1次硬盤寫LogLink:http://w/2010/01/hbase-architecture-101-write-ahead-log.html讀出過程第38頁讀出過程Memoryfile0,

Address0file1,

Address11. Read

key:linghuch+

appearance,Client

1One

MachineSorted

ListGuojing

：Linghuchong+appearance:

9DiskFile

0

（有序）Linghuchong+appearance:

5Renyingying+appearance:

8…File

1

（有序）Angelababy+appearance:

10Chen+appearance:

9Linghuchong+appearance:

7ongQuestion:Sorted

ListFile

0File

1尋找【真】？第39頁過程File

0

（有序）Linghuchong+appearance:

5Renyingying+appearance:

8…Client

11. Read

key:linghuchong+

appearance,DiskFile

1（有序）Angelababy+appearance:

10Chen+appearance:

9Linghuchong+appearance:

7One

MachineSorted

ListGuojing

：Linghuchong+appearance:

9Memoryfile0,

Address0file1,

Address12.

Read

key:linappearance,ghuchong

+3.

Read

key:linghuchong+

appearance,第40頁一個File里面怎么查詢？讀出來for循環(huán)硬盤二分有木有更好的方法？第41頁第42頁建立Index目的：加快查詢怎么建？One

easy

way

to

build

indexDiskFile

0Angelababy:

10Chenhe:

5DengChao:

8Linghuchong:

7Sunli:

9…MemoryIndexA:

addressD:

addressS:

address…Key把一些Key放入內(nèi)存作為IndexIndex有效減少磁盤讀寫次數(shù)1.

Look

up

KeyLinghuchong第43頁2.

We

just

needbinarysearch

from

Dto

SIntersection

of

Two

Arrays

iiFollow

Uphttp:/en/problem/intersection-of-two-arrays-ii/這道題的challenge題目Read

More:B

tree

index:第44頁休息5分鐘第45頁有木有更好的方法檢查一個key在不在一個File里面？第46頁為什么要做如此多的讀優(yōu)化？因為在寫的時候做了Append優(yōu)化，才會想辦法加快讀的速度。第47頁BloomFilter第48頁Interview:

How

to

look

up

inbloom

filter?Interview:

How

to

buildbloom

filter?HuHash1(Ling)

=

1Hash2(Ling

)=2Hash1(Hu)

=5Hash2(Hu)

=

7值0110010100下標0123456789第49頁Chen

LILingInterview:

How

to

find

in

bloom

filter?如何檢查“chen”在bloom

filter

里面？ChenHash1(chen)=

2Hash2(chen)=4值0110010100下標0123456789第50頁sun第51頁Bloom

Filter

誤判率Bloom

Filter

PoetryFalse

is

always

False.True

may

beTrue.How

many

false

is

hidden

in

true?Interview:

How

to

find

in

bloom

filter?如何檢查“sun”在bloom

filter

里面？SunHash1(Sun)=

2Hash2(Sun)

=5值0110010100下標0123456789第52頁sun第53頁Bloom

Filter精確度跟什么有關(guān)？哈希函數(shù)個數(shù)位數(shù)組長度加入的字符串數(shù)目Bloom

Filter

誤判率舉個例子如果哈希函數(shù)的個數(shù)15個、位數(shù)組大小200w、加入的字符串數(shù)量10w個的話、判斷2000w個新的字符串誤判率在3~4%

左右計算誤判率公式:第54頁Bloom

Filter可以高效幫助

查找key是否在sstable里面Bloomfilter里面能夠找到key的話，接下來 再用index去查找參考閱讀:第55頁完整的讀出過程(with

Index,BF)第56頁讀出過程File

0

（有序）Linghuchong+appearance:

5Renyingying+appearance:

8Index0BloomFilter

0Client

11. Read

key:linghuchong+

appearance,DiskFile

1（有序）Angelababy+appearance:

10Chen+appearance:

9Linghuchong+appearance:

7Index

1BloomFilter

1One

MachineSorted

ListLinghuchong+appearance:

9Memoryfile0,

Address0Index0,

bloomfilter

0file1,

Address1Index1,

bloomfilter

12.

Read

key:lin+

appearance,ghuchong5.

Read

key:linghuchong+

appearance,3,

check

bloom

Filter

for

each

file第57頁has

this

key4.

Use

the

Index

to

find

the

valuefor

the

key第58頁Specific

Name

in

BigtableString

is

Store

in

the

File.Sstable

=

Sorted

StringTableSorted

List

用Skip

List

實現(xiàn)One

ServerMemoryfile0,

Address0Index0,

bloomfilter

0file1,

Address1Index1,

bloomfilter

1Skip

ListGuojing

：Linghuchong+appearance:

9DiskSstable

0

（有序）Linghuchong+appearance:

5Renyingying+appearance:

8Index

0BloomFilter

0Sstable

1

（有序）Angelababy+appearance:

10Chen+appearance:

9Linghuchong+appearance:

7Index1BloomFilter

1寫入過程Client

1第59頁已經(jīng)學(xué)會了一臺機器Bigtable的操作讀/寫Key:+顏值Value:5顏值身高5東邪第60頁1. Skip

ListCode:

/petegoodliffe/skip_list

Wiki:2.

SstableSstable

Page:拓展閱讀第61頁Interviewer:

How

to

read/writekey:value

from

1PB

file第62頁ScaleSharding?顏值身高5東邪第63頁ShardingVertical

Sharding?Horizontal

Sharding?難點：取“顏值”是不是會取“身高”，“武功”相關(guān)屬性第64頁BigtableColumnRowRow

key顏值身高5東邪ShardingConsistent

Hash(row

key:姓名)顏值身高5東邪表顏值身高表顏值身高東邪170第66頁第67頁一臺機器搞不定，那么需要多臺機器了Master

+

SlaveInterviewer:How

to

manager

server?KeyMaster

+

SlaveMaster

has

HashMap[key,

server

address]Master(Consistent

HashMap)Server1Server2第68頁第69頁Interviewer:

How

do

we

read

inbigtable

with

multi-server?Interview:How

to

read

a

key?

（宏觀）:顏1,

Read

key(值)2,

Get

the

row

key( )fromkey,Use

the

row

key

to

get

server

Id

=

1:顏3.

Read

key(值)4.Value(5)BigtableMaster(Consistent

HashMap)Slave

Server1MemoryCheck

Memory

Skip

ListCheck

Bloom

FilterCheck

IndexDiska) Find

the

value

in

Sstable表1顏值身高5160第70頁第71頁Interviewer:

How

do

wewritebigtable?Interview:How

to

write

a

key?(宏觀)1,

Write

key(:顏值:3)2,

Get

the

row

key

from

key,Use

the

row

key

to

get

serverIdBigtableMaster(Consistent

HashMap)Slave

Server14.

Done:顏值,3.

Write

key,value(3)Memory直接把數(shù)據(jù)放到內(nèi)存里面寫一次Write

Ahead

LogDisk如果SkipList滿了那么就寫到硬盤表1顏值身高5160第72頁第73頁Interviewer:每臺機器數(shù)據(jù)越寫越多存不下怎么辦？現(xiàn)在所有的數(shù)據(jù)都存在Slave

Server

disk里面第74頁把所有數(shù)據(jù)存到GFS里面Advantage：Disk

SizeReplicaFailure

and

RecoverySlaveServer1SlaveServer2MasterBigtableSlaveServer1SlaveServer2MasterGFS第75頁第76頁Bigtable

vs

GFS都是Master+Slave是否就用一個Master+Slave把兩個都實現(xiàn)了？Sstable

怎么寫到GFS里面呢？難點：Bigtable里面單位是SstableGFS讀寫單位是chunk第77頁第78頁BigtableNamingWhat

isTabletConsistent

Hash(row

key:

姓名)顏值身高5東邪表顏值身高表顏值身高東邪170BigtableTablet0Tablet1第79頁What

is

Tablet

ServerTablet

Server

=

Store

Tablet

Slave

ServerTabletServer1TabletServer2BigtableMaster第80頁Tablet

ServerTabletServer1TabletServer2GFSTablet1

Column_

Column_key1

key2Row_Key1value1value2物理真實框架Key:value(Row_Key1:ColumnKey1):value1(Row_Key1:ColumnKey2):value2(Row_Key2:ColumnKey1):value3邏輯框架Bigtable第81頁第82頁看看還有什么問題沒有解決讀和寫同時發(fā)生？寫的過程當中，有讀請求?RaceConditionInterviewer:

What

if

we

read

and

write

the

same

key

at

same

time?TabletServer1Client

1Read

KeyClient

2WritekeyRace

Condition?第83頁We

need

alockWe

need

a

distributedlock.由多臺機器組成的分布式鎖服務(wù)ChubbyZookeeperRead

More:??第84頁Interview:

How

to

write

a

key?1,

write

Key

and

lock

the

key3.

Key,value4.doneTabletServer1Lock

ServerConsistent

HashMapClient

1Client

21,

read

Key

and

lock

the

key2,

key

is

locked2,

Get

the

row

key

from

key,Use

the

row

key

to

get

serverId5,

unlock

Key第85頁Advantage

Distributed

LockThe

Metadata

is

store

on

the

LockLock

本來要

Metadata那master就不需要

MetaData了第86頁第87頁Summary

ofW