走进系统设计高级进阶视频教程

系统设计Distributed

System

Design

2（九章

课件）本节主讲人：北丐：九章课程不允许

，否则将

，赔偿损失扫描

/获取

面试题及

解答:

ninechapter:

ht

/ninechapter知乎:

http://z

/jiuzhang官网:

http:

第1页今日课程大纲Design

a

Bigtable, ,

Amazon,

AlibabaNoSQL

database

设计框架和原理SStable

读和写Bloom

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

的实现？面试题1.解决相类似系统设计题,比如:Look

upservice追问NoSQL

How

to

scale的原理第5页文件系统vs

数据库系统第6页文件系统?操作：输入：/home/jinyong/character_name.txt输出:文件内容第7页如果有下面需求找到“ ”的“颜值”1、打开文件2、For循环扫描文件的内容然后找 的颜值‘颜值’:5,‘身高’:‘颜值’:9,‘颜值’:7,‘身高’:‘180cm’},‘身高’:‘170cm’},{{‘ ’

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

:‘

’,{‘

’:‘东邪’,}/home/jinyong/character_name.txt第8页文件系统缺点？文件系统提供一些简单的读写文件操作所以实际查询当中有复杂的查询需求：比如：查询

颜值查询颜值小于5的查询所有人的身高平均值需要一个更复杂的系统建立在文件系统之上第9页第10页数据库系统1、建立在文件系统之上2、负责组织把一些数据存到文件系统3、对外的接口比较方便操作数据数据库系统操作输入：

key（

+颜值）输出:value

（5）查询

颜值颜值身高5东邪第11页设计数据库系统第12页Scenario需求第13查询：

key

（

+

颜值）返回：

value

（5）因为后端系统通常给web

server使用，Scenario比较单一页Storage数据库怎么以表的形式？Yes/No第颜值身高东邪170页数据最终都会存到文件里面‘颜值’

:

5,

‘身高’

:{{‘ ’

:

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

:

9,

‘身高’

:‘颜值’

:

7,

‘身高’

:{‘ ’

:

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

:

‘dongxie’,‘170cm’},}第15页从文件系统基础上思考搭建数据库系统第16页在文件里面怎么更好支持查询操作？{{‘ ’

:

‘linghuchong’,

‘颜值’

:

5,

‘身高’

:‘160cm’},第17页‘颜值’

:

9,

‘身高’

:‘颜值’

:

7,

‘身高’

:{‘ ’

:

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

:

‘dongxie’,‘170cm’},}文件到内存里面内存里面查询有什么问题？第18页先对数据进行排序？不需要一个一个在文件里面查询只需要二分扫描那么文件在硬盘里面，怎么在硬盘里面进行二分呢？第19页第20页硬盘二分查询画图解释硬盘二分Read

More:http:/

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

颜值，从5变到61.

直接在文件里面修改整个文件，修改好了，重新写入覆盖原来文件3.

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

直接在文件里面修改很难做到直接修改内容，如果原来是4个字节，现在修改成8个字节，那么之后的内容都需要移动位置。2.整个文件，修改好了，重新写入覆盖原来文件非常耗费时间，每次要读出写入其他多余不变的内容3.

直接append操作加在文件最后面好处：特别快修改文件内容第22页Bigtable为了写优化选择了直接Append坏处：数据怎么办，文件没有顺序,？第23页把所有关于数据怎么办？的颜值记录都读出来第24页怎么解决文件没有顺序不能二分查询的问题？过一段时间

把文件有序整理第25页有木有一个办法既可以读的时候二分查询又可以写的时候写在最后append操作？分块有序每一块都是

有序写的时候只有最后一块是无序的第26页块会越写越多，会有很多重复(

经常做整形手术)重复非常多每次查询所有的块非常消耗时间http:定期K路归并/en/problem/merge-k-sorted-arrays/第27页第28页完整系统读/写过程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从无序变成有序？读入到内存快速排序硬盘外部排序可不可以一开始就存在内存里面？1. 读入到内存快速排序。所有数据1次硬盘写入，1次硬盘+内存排序+1次硬盘写入硬盘外部排序有必要么？可不可以一开始就存在内存里面？内存排序+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:机器挂了，内存没了？第36页Write

Ahead

Log(WAL)那写log岂不是又要写硬盘WAL

非常方便,不像重要数据需要整理第37页内存排序+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循环硬盘二分有木有更好的方法？第41页第42页建立Index目的：加快查询怎么建？One

easy

way

to

build

indexDiskFile

0Angelababy:

10Chenhe:

5DengChao:

8Linghuchong:

7Sunli:

9…MemoryIndexA:

addressD:

addressS:

address…Key把一些Key放入内存作为IndexIndex有效减少磁盘读写次数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页为什么要做如此多的读优化？因为在写的时候做了Append优化，才会想办法加快读的速度。第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精确度跟什么有关？哈希函数个数位数组长度加入的字符串数目Bloom

Filter

误判率举个例子如果哈希函数的个数15个、位数组大小200w、加入的字符串数量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

实现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页已经学会了一台机器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?难点：取“颜值”是不是会取“身高”，“武功”相关属性第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直接把数据放到内存里面写一次Write

Ahead

LogDisk如果SkipList满了那么就写到硬盘表1颜值身高5160第72页第73页Interviewer:每台机器数据越写越多存不下怎么办？现在所有的数据都存在Slave

Server

disk里面第74页把所有数据存到GFS里面Advantage：Disk

SizeReplicaFailure

and

RecoverySlaveServer1SlaveServer2MasterBigtableSlaveServer1SlaveServer2MasterGFS第75页第76页Bigtable

vs

GFS都是Master+Slave是否就用一个Master+Slave把两个都实现了？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页看看还有什么问题没有解决读和写同时发生？写的过程当中，有读请求?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.由多台机器组成的分布式锁服务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