九章it求职直播课程之系统设计班-课件distributed

扫描

/获取

面试题及

解答:ninechapter:

ht

/ninechapter知乎:

http://z

/jiuzhang官网:http:

系统设计Distributed

System

Design（九章

课件）课程版本v5.1

本节主讲人：北丐老师：九章课程不允许

，否则将 ，赔偿损失第1页分布式系统？一言以概之：用多台机器去解决一台机器上不能够解决的问题。比如： 不够？QPS太大？第2页Distributed

File

System

( File

System)怎么有效

数据？No

SQL

底层需要一个文件系统MapReduce怎么快速处理数据？Bigtable

=

No-SQL

DataBase怎么连接底层

和上层数据Overview谷歌三剑客第3页Design

Distributed

File

System

(File

System)Overview

of

today第4页Master

Slave

Pattern.How

to

check

and

handle

system

failure

anderror.How

to

design

Distributed

File

System.第5页你会掌握Design

Distributed

File

System了解分布式文件系统后可以做什么？， 面试可能会考到.学习经典系统，对其他系统设计也有帮助.比如如何处理failure和recovery.第6页Distributed

File

SystemHadoop

Distributed

File

System(HDFS

叫做“很多分手”)VSFile

System(GFS)俗称“高富帅”又叫“刚分手”Distributed

File

SystemCompany开源GFSNoHDFSYahoo(Alitaba)OpenSource

of

GFSYes第7页按照4S分析Scenario

场景分析Service

服务Storage理清楚work

solutionScale

升级优化Overview第8页Scenario

场景分析需要设计哪些功能第9页一个文件.需求1用户写入一个文件，用户支持多大的文件？越大越好？比如>1000T需求2多台机器

这些文件支持多少台机器？越多越好？10万台,2007

yearScenario

场景分析第10页Service

服务第11页Service

服务第12页Client+ServerService

服务Server第13页多台机器怎么沟通？+第14页Service

服务serverServerServerPeer

to

peer谁也看不惯谁第15页Service

服务serverServerServermasterMaster

+Slave听

的好比“

和他的小弟”What

is

master?Master

也是一台机器第16页DBGFS（HDFS）Master数据管理者（不

数据）SlaveBackUp被管理者（

实际文件，partition关系）Master+Slave架构第17页比较少)Peer

2

Peer( et,Cassandra,不是课程重点，Advantage一台机器挂了还可以工作Disadvantage多台机器需要经常通信保持他们数据一致Master

SlaveAdvantageSimple

Design数据很容易保持一致Disadvantage单master要挂Final

DecisionMaster

+

Slave单master挂了重启就是。挂的概率在0.1%Storage第18页Storage第19页大文件存在哪？内存？数据库？文件系统？Storage第20页大文件存在哪？内存？数据库？文件系统？怎么存在文件系统里面呢？操作系统基础知识怎么存文件的？Storage第21页Interviewer:

How

to

save

a

filein

one

machine？普通的操作系统是怎么做的呢？100G第22页DengChao.mp4一个文件有什么东西？第23页How

to

save

a

file

in

one

machineDiskMetadataFileinfoName=dengchao.mp4CreatedTime=201505031232Size=2044323dengchao.mp4的信息的Metadata:描述“其他数据”而Metadata

常常多于内容的文件是分开 的呢？还是连续呢？，Windows就是连续

Linux就是分开（画个图）第24页How

to

save

a

file

in

one

machineDiskMetadataFileinfoName=dengchao.mp4CreatedTime=201505031232Size=2044323IndexBlock

11->diskOffset1Block

12->diskOffset2Block

13->diskOffset3Block

14->diskOffset4blocksBlock

10Block

11Block

12Block

13Block14Key

point1

block

=

1024ByteBlock

Advantage?方便检查错误碎片化(fragmentation)第25页Interviewer:

How

to

save

a

largefilein

one

machine？第26页Is

block

size

bigenough?100T(多文件)=100*1000G=100*1000*1000M=100*1000*1000*1000K=100*1000*1000*1000block通常大文件是一些数据文件file-merged.txt=

0.3G的第27页Interviewer:

How

to

save

a

large

file

in

one

machine？DiskMetadataFileinfoName=dengchao.mp4CreatedTime=201505031232Size=2044323232IndexChunk

11->diskOffset1Chunk

12->diskOffset2Chunk

13->diskOffset3…..chunksChunk

10Chunk

11Chunk

12Chunk

15Chunk

13Key

point1

chunk=

64M=

64*1024KAdvantageReduce

size

of

metadataDisadvantageWaste

space

for

small

files第28页系统设计没有标准答案就是TradeOff的过程第29页Interviewer:

How

to

save

extra-large

filein

several

machine？第30页10PIs

one

machine

bigenough?这里的文件并不是指一个dengchao.mp4就那么大而是很多个文件Scale

about

the

StorageChunkServer5Offset1Offset2Offset3

Dengchao.mp4-chunk-01Offset4

Dengchao.mp4-chunk-02Offset5

Dengchao.mp4-chunk-03Offset6

Sunli.mp4-chunk-01Offset6

Sunli.mp4-chunk-02MasterMeta

DataName=dengchao.mp4CreatedTime=201505031232Size=40042044323IndexChunk

01->cs5_offset3Chunk

02->cs5_offset4Chunk

03->cs5_offset5Chunk

04->cs3_offset1Chunk

05->cs3_offset2Chunk

06->cs3_offset3Key

pointOne

master

+

many

ChunkServers第31页Chunk

Servers

=

Slave

Servers每个chunk的Offset偏移量可不可以不存在master上面？第32页Scale

about

the

StorageChunkServer5Offset1Offset2Offset3

Dengchao.mp4-chunk-01Offset4

Dengchao.mp4-chunk-02Offset5

Dengchao.mp4-chunk-03Offset6Sunli.mp4-chunk-01Offset6

Sunli.mp4-chunk-02MasterMeta

DataName=dengchao.mp4CreatedTime=201505031232Size=40042044323IndexChunk

01->cs5Chunk

02->cs5Chunk

03->cs5Chunk

04->cs3Chunk

05->cs3Chunk

06->cs3Key

pointThe

master

don’t

record

thediskOffset

of

a

chunk第33页AdvantageReduce

the

size

of

metadatainmasterReduce

the

traffic

between

masterandChunkServer（chunkoffset改变不需要通知master）IndexDengchao.mp4-chunk-01

Offset3Dengchao.mp4-chunk-02offset5Master10P

文件的metadata需要多少容量?1

chunk=64MB

needs

64B.(经验值)10P=16*10^6

chunk

needs

10

G第34页按照4S分析Scenario

场景分析Service

服务Storage理清楚work

solutionScale升级优化Overview第35页One

Work

Solution

forRead

/

Write第36页Interviewer:

How

to

write

a

file?第37页一次写入还是拆分成多份多次写入？把大胖子直接写入呢？还是把大胖子碎尸万段了后写入呢？write

File_name=/gfs/home/dengchao.mp4Server第38页写入过程中出错了，那么需要重新写入，哪

法更好？一次传输得重新传输整个文件，多次只用重新传一小份。如果是分成多份多次写入，那么每一份的大小？文件本来是按照Chunk来 的，所以传输单位也是Chunk如果是分成多份多次写入，那么是告诉master让master来切分？还是client自己切分？client自己按照文件大小切分。比如/gfs/home/dengchao.mp4

size=576M.

那么可以切分问576M/64M=9个chunk。一次

VS

多次第39页How

to

write

a

file?FileClient

Split

file/gfs/home/dengchao.mp4Index00/gfs/home/dengchao.mp4-00-of-09Index01/gfs/home/dengchao.mp4-01-of-09……client

把文件拆分为n份，每一份一个chunk

index所以并不是一下就把胖子写进去第40页/gfs/home/dengchao.mp4那每一个chunk是怎么写入server的呢？第41页直接写到chunk

server？需要先个master沟通，再写入chunk

server？How

to

write

a

file?1,

write

File_name=/gfs/home/dengchao.mp4,

Chunk

index=12,

Assign

Chunkserver_locations=US,

CS13.

Transfer

Data=/gfs/home/dengchao.mp4-01-of-094.

WriteFinishmasterChunkServer1ChunkServer2infoName=/gfs/home/dengchao.mp4IndexChunk

01->ChunkServer1Chunk

02->ChunkServer1Chunk

03->ChunkServer2……KeyMaster

分配chunkserver给client的每个chunk4.

WriteFinish第42页这个地方的client是User么？是

Drive界面么？第43页How

to

write

a

file?ClientServerUserBrowserBroswerWebserverWebserverDatabaseDatabaseGFSWebserverGFS( File

System)第44页要修改Dengchao.mp4怎么办？第45页/gfs/home/dengchao.mp4要修改的部分在哪个chunk？修改了过后chunk变大了要怎么处理？修改了过后chunk变小了要怎么处理？要修改Dengchao.mp4怎么办？第46页One

time

to

write,

Many

time

to

read.先删掉/gfs/home/dengchao.mp4重新把整个文件重写一份跟化妆一样，画丑了，洗掉重画Interviewer:

How

to

read

a

file?第47页一次读整个文件？还是拆分成多份多次读入？Read

File_name=/gfs/home/dengchao.mp4Server第48页那么client怎么知道dengchao.mp4被切成了多少块？How

to

read

from

a

file?1.

Filename=/gfs/home/dengchao.mp42.

return

a

chunk

list.Read

/gfs/home/dengchao.mp4-00-of-09

inChunk

server

1Return

data/gfs/home/dengchao.mp4-00-of-09masterChunkserver1第50页Name=/gfs/home/dengchao

mp4Chunk

ListChunk

indexChunk

Server001012……各个文件数据的metadataMap(file

name

+

chunk

index

->

chunk

server)时找到对应的chunkserver写入时分配空闲的chunkserverQuestion?为什么不把数据直接给master

让master

去写？MasterbottleneckMaster

Task第51页•普通文件系统Meta

Data，Block大文件 ：

Block->

Chunk多台机器超大文件:Chunk

Server+Master写入Master+Client+ChunkServer

沟通流程Master metadata

和chunkserver

表读出Master+Client+ChunkServer

沟通流程One

Work

Solution第52页按照4S分析Scenario

场景分析Service

服务Storage理清楚work

solutionScale升级优化Overview第53页休息5分钟第54页Scale

升级系统如何优化与GFS的精髓第55页单Master

够不够？第56页单Master

够不够？第57页工业界90%的系统都采用单masterSimple

is

perfectSingle

Master

FailureDouble

Master

双龙戏珠P r:

Apache

Hadoop

Goes

Realtime

atMulti

MasterP r:

Paxos

Algorithm第58页Scale

about

the

FailureandRecover第59页Interviewer:

How

to

identify

whethera

chunk

on

the

disk

is

broken?第60页CheckSum第61页数据123Checksum(xor)二进制表示01101100Check

Sum

检查一位错误数据133Checksum(xor)二进制表示01111101错误后原来CheckSum

Method

(MD5,

SHA1,

SHA256

and

SHA512)Read

More:第62页Add

checksum

for

chunk?第63页ChunkHow

to

identify

whether

a

chunk

on

the

disk

is

broken?第64页1

checksumsize?4bytes

=

32bit1

chunk=

64MBEach

chunkhas

achecksumThe

size

of

checksum

of

1P

file1P/64MB*32bit

=

62.5

MB什么时候写入checksum?第65页什么时候写入checksum?Answer:写入一块chunk的时候顺便写入第66页Chunkchecksum什么时候检查checksum?第67页什么时候检查checksum?第68页Answer:读入这一块数据的时候检查重新读数据并且计算现在的checksum比较现在的checksum和之前存的checksum是否一样Interviewer:

How

to

avoid

chunkdata

loss

when

a

ChunkServer

isdown/fail?第69页Interviewer:

How

to

avoid

data

losswhen

a

ChunkServer

is

down/fail?第70页Answer:Replica

（专业词汇）说得好听叫做双保险需要多少个备份？每个备份放在哪？第71页需要多少个备份？每个备份放在哪？第72页三个备份都放在一个地方(加州)。三个备份放在三个相隔较远的地方（加州，滨州，纽约州）两个备份相对比较近，另一个放在较远的地方（2个加州，1个滨州）选chunk

server的时候有什么策略？第73页选chunk

server的时候有什么策略？最近写入比较少的。(LRU)硬盘

比较低的。第74页Interviewer:

How

to

recover

when

achunk

isbroken?第75页Interviewer:

How

to

recover

when

achunk

isbroken?Answer:

Ask

master

for

help第76页Master/gfs/home/dengchao.mp4Chunk03

->CS3,CS5,CS4ChuckServer5Dengchao.mp4-chunk-03ChuckServer4Dengchao.mp4-chunk-03Sunli.mp4-chunk-01Sunli.mp4-chunk-02Key

pointAsk

master

for

helpMy

Chunk03

is

wrong,

where

are

theothersAsk

CS3

and

CS5

?3.

I

need

Chunk3第77页4.

There

u

goHow

to

find

whether

aChunkServer

is

down?第78页How

to

find

whether

aChunkServer

is

down?第79页Interviewer:

HeartBeat.画一个图阐释A:

master

->

chunkservers?B:

chunkservers->master?备胎?Scale

abouttheWriteInterviewer: Whether

write

to

only

one

server

is

safe?第80页How

to

write

a

file?1,

write

File_name=/gfs/home/dengchao.mp4,

Chunkindex=12,

Assign

Chunkserver_server,

CS1,CS2,CS34.

WriteFinishmasterChunkServer1ChunkServer2ChunkServer3第81页Interviewer:

How

to

solve

Clientbottleneck?第82页第83页How

to

solve

Client

bottleneck?1,

write

File_name=/gfs/home/dengchao.mp4,

Chunkindex=12,

Assign

Chunkserver_server,

CS1,CS2,CS33.

Transfer

Data=/gfs/home/dengchao.mp4-01-094.

WriteFinimasterChunkServer1ChunkServer2ChunkServer33.

Transfer

Data=

/gfs/home/dengchao.mp4-01-of-09选队长4.

Write本由

isomh社区用户整理Interviewer:

怎么样选队长?第84页找距离最近的（快）找现在不干活的（平衡traffic）Interviewer:

队长一直不变的么？第85页Interviewer:

How

to

solveChunkServer

failure?第86页How

to

solve

ChunkServer

failure?1,

File

Name,

Chunk

id2,

Chunkserver

locations

,

CS1,CS2,CS33.

data4.

failmasterChunkS