九章it求職直播課程之系統(tǒng)設(shè)計(jì)班

課程版本

v5.1

主講

東邪掃描

/獲取

面試題及

解答:ninechapter:

ht

/ninechapter知乎:

http://z

/jiuzhang官網(wǎng):http:

基于地理位置的服務(wù)Location

Based

Service第1頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將Design

UberDesignDesign

YelpNearbyDesign

Pokemon

Go總結(jié)系統(tǒng)設(shè)計(jì)今日課程大綱第2頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將Interviewer:

Please

designUberSimilar

questions:How

to

design

nearbyHow

to

design

yelp是否看過(guò)關(guān)于Uber

Architecture

的，講座或是文章？第3頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將RingPop

/uber/ringpop-node一個(gè)分布式架構(gòu)擴(kuò)展閱讀??[Hard][Hard]TChannel?

/uber/tchannel一個(gè)高效的RPC協(xié)議RPC:

Remote

Procedure

CallS2/s2-geometry-library-java與查詢的算法

/一個(gè)地理位置信息RiakDynamo

DB

的開(kāi)源實(shí)現(xiàn)你大概會(huì)知道Uber用了如下一些技術(shù)告訴我你看到這些詞的感受是不是這樣？第4頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將Read

more

on

Uber

Eng

Blogh

/是不是答出Uber是怎么實(shí)現(xiàn)的，就可以拿到Offer?第5頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將系統(tǒng)設(shè)計(jì)面試常見(jiàn)誤區(qū)以為答出該公司是怎么做的，就可以拿到Offer了第6頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將Uber的架構(gòu)非常小眾Uber用到的技術(shù)是自己設(shè)計(jì)出的一套東西如果Uber面你這個(gè)題，你不可能比他們清楚，并且顯得你是準(zhǔn)備過(guò)的，不能代表你真實(shí)的能力如果其他公司面你這個(gè)題，這也不會(huì)是期望答案第7頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將Scenario

場(chǎng)景FeaturesQPS

/

StorageService

服務(wù)Service

Oriented

ArchitectureStorage

數(shù)據(jù)SchemaScale

進(jìn)化RobustFeature系統(tǒng)設(shè)計(jì)的4S

分析法邏輯設(shè)計(jì)Logic

Design50%Make

it

work!架構(gòu)設(shè)計(jì)Infrastructure

Design

50%Make

it

robust!第8頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將System

Design

=Logic

Design

+

Infrastructure

Design系統(tǒng)設(shè)計(jì)=邏輯設(shè)計(jì)+架構(gòu)設(shè)計(jì)第9頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將Scenario

場(chǎng)景需要設(shè)計(jì)哪些功能，設(shè)計(jì)得多牛設(shè)計(jì)哪些功能？第10頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將第一階段：Driver

report

locationsRider

request

Uber,

match

a

driver

with

rider第二階段：Driver

deny

/

accept

a

requestDriver

cancel

a

matched

requestRider

cancel

a

requestDriver

pick

up

a

rider

/

start

atripDriver

drop

off

a

rider

/

end

atrip第三階段*：Uber

PoolUberEatScenario

場(chǎng)景無(wú)所謂的加分項(xiàng)，如果你都答到這里了，說(shuō)明你前面都秒殺了第11頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將Scenario-設(shè)計(jì)得多牛？問(wèn)問(wèn)面試官:貴優(yōu)步現(xiàn)在多少輛車(chē)了？貴優(yōu)步現(xiàn)在多少Q(mào)PS呀？貴優(yōu)步遍布多少城市呀？猜猜Uber

2011

年的QPS猜猜Uber

2015

年的QPS第12頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將假設(shè)問(wèn)到

20

萬(wàn)

同時(shí)Driver

QPS

=

200k

/

4

=

50kDriver

report

locations

by

every

4

secondsPeak

Driver

QPS

=

50k

*

3

=

150

kUber

自己的說(shuō)法：2015

新年夜的Peak

QPS

是170KRead

More:Rider

QPS

可以忽略無(wú)需隨時(shí)匯報(bào)位置一定遠(yuǎn)小于Driver

QPSUber

自己定的設(shè)計(jì)目標(biāo)支持1M

QPS這些數(shù)字是多少并不重要，你算給面試官看就好了估算假如每條Location都記錄：200

k

*

86400/4

*

100bytes(每條位置記錄）~

0.5

T/天假如只記錄當(dāng)前位置信息：200

k

*

100

bytes=20

MScenario-設(shè)計(jì)得多牛初步感覺(jué)：150k

的寫(xiě)操作是不容小覷的必須找一個(gè)寫(xiě)速度快的

！第13頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將Uber

主要干的事情就兩件記錄車(chē)的位置GeoService匹配打車(chē)請(qǐng)求DispatchServiceService

服務(wù)GeoServiceDispatchServiceReport

Locationsevery

4sRequest

UberDriver

info這張圖里漏了什么？第14頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將Driver

如何獲得打車(chē)請(qǐng)求？Report

location

的同時(shí)，服務(wù)器順便返回匹配上的打車(chē)請(qǐng)求Service服務(wù)GeoServiceDispatchServiceDriver:

Save

locationRider:

Find

drivers

nearby問(wèn)：Service

里到底包含了什么？答：邏輯處理+數(shù)據(jù)

的整合第15頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將DispatchServiceStorageDriver:

Save

locationRider:

Find

drivers

nearbyTrip

Table(?)DispatchWebServerGeoWebServerLocationTable(?)GeoService讀vs寫(xiě)?讀vs寫(xiě)?第16頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將class

Trip

{public

Integer

tripId;public

Integer

driverId,

riderId;public

Double

Latitude,

Longitude;public

Integer

status;public

Datetime

createdAt;}class

Location

{public

Integer

driverId;public

Double

Latitude,

Longitude;public

Datetime

updatedAt;}Storage

——Schema

細(xì)化數(shù)據(jù)表單第17頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將Trip

Tabletypecommentsidpkprimary

keyrider_idfkUseriddriver_idfkUser

idlatfloatLatitude

緯度lngfloatLongitude

經(jīng)度statusintNew

request

/

waiting

for

driver

/

on

the

way

to

pick

up

/

in

trip

/

cancelled/

endedcreated_attimestampStorage——Schema

細(xì)化數(shù)據(jù)表單Location

Tabletypecommentsdriver_idfkPrimary

keylatfk緯度lngfk經(jīng)度updated_attimestamp存最后更新的時(shí)間，這樣知道 是不是掉線了第18頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將LBS

類系統(tǒng)的難點(diǎn)：和查詢地理位置信息？如何如，查詢某個(gè)乘客周?chē)?公里內(nèi)的第19頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將查詢地理位置信息Naive

SolutionSELECT

*

FROM

LocationWHERE

lat

<

myLat

+

deltaAND

lat

>

myLat

-

deltaAND

lng

<

myLng

+

deltaAND

lng

>

myLng

-

delta;——這個(gè)基本等同于掃描了一遍所有的數(shù)據(jù)第20頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將?S2Read

more:Hilbert

Curve:將地址空間到2^64的整數(shù)特性：如果空間上比較接近的兩個(gè)點(diǎn)，對(duì)應(yīng)的整數(shù)也比較接近Example:

(-30.043800,

-51.140220)

→GeohashRead

more:Peano

CurveBase32：0-9,a-z

去掉(a,i,l,o)為什么用base32?因?yàn)閯偤?5可以用5

位二進(jìn)制表示思路二分法特性：公共前綴越長(zhǎng)，兩個(gè)點(diǎn)越接近Example:

(-30.043800,

-51.140220)

→

6feth68y4tb015Storage

——地理位置信息的與查詢更精準(zhǔn)，庫(kù)函數(shù)API豐富比較簡(jiǎn)單，準(zhǔn)確度差一些第21頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將Examples:LinkedIn

HQ:

9q9hu3hhsjxx??HQ:

9q9hvu7wbq2sHQ:

9q9j45zvr0seGeohash第22頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將Takea

break5

分鐘后回來(lái)第23頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將北海公園：lat=39.928167,lng=116.389550二分(-180,180)

近經(jīng)度?

左半部記0

?

右半部記1(-180,180)里116.389550在右半部→1(0,180)里116.389550在右半部→1(90,180)里116.389550在左半部→0(90,135)里116.389550在右半部→1(112.5,135)里116.389550在左半部→0二分(-90,90)

近緯度，下半部記0，上半部記1(-90,90)里39.928167

在上半部→1(0,90)里39.928167

在下半部→0(0,45)里39.928167

在上半部→1(22.5,45)里39.928167

在上半部→1(33.75,45)里39.928167

在上半部→1…

(

還可以繼續(xù)二分求獲得 的精度?Geohash先經(jīng)后緯，經(jīng)緯交替1110011101W

X課后作業(yè)：http:

/problem/geohash/第24頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將找到精度誤差>2公里的最長(zhǎng)長(zhǎng)度HQ:

9q9hvu7wbq2s找到位置以9q9hv以開(kāi)頭的所有車(chē)輛查詢

半徑2公里內(nèi)的車(chē)輛怎樣在數(shù)據(jù)庫(kù)中實(shí)現(xiàn)該功能？第25頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將SQL

數(shù)據(jù)庫(kù)首先需要對(duì)geohash

建索引CREATE

INDEX

on

geohash;使用Like

QuerySELECT

*

FROM

location

WHERE

geohash

LIKE`

9q9hv%`;NoSQL

-

Cassandra將geohash

設(shè)為column

key使用range

query

(9q9hv0,9q9hvz)NoSQL

-

Redis

/

MemcachedDriver

的位置分級(jí)如

Driver的位置如果是

9q9hvt，則

在

9q9hvt，

9q9hv，

9q9h

這

3

個(gè)

key

中6位

geohash

的精度已經(jīng)在

以內(nèi)，對(duì)于

Uber

這類應(yīng)用足夠了4位geohash

的精度在20公里以上了，再大就沒(méi)意義了，你不會(huì)打20公里以外的車(chē)key

=

9q9hvt,

value

=

set

of

drivers

in

this

locationStorage從數(shù)據(jù) 與查詢的角度哪種結(jié)構(gòu)更合？第26頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將結(jié)構(gòu)的特性，對(duì)于面試十分加分！能夠熟悉每種數(shù)據(jù)SQL

可以，但相對(duì)較慢原因1：Like

query

很慢，應(yīng)該盡量避免即便有index，也很慢原因2：Uber

的應(yīng)用中，Driver

需要實(shí)時(shí)Update

自己的地理位置被index的column并不適合經(jīng)常被修改B+樹(shù)不停變動(dòng)，效率低NoSQL–Cassandra

可以，但相對(duì)較慢原因：Driver

的地理位置信息更新頻次很高Column

Key

是有index

的，被index

的column

不適合經(jīng)常被“修改”NoSQL–Memcached

并不合適原因1：Memcached

沒(méi)有持久化

，一旦掛了，數(shù)據(jù)就丟失原因2：Memcached

并不原生支持set

結(jié)構(gòu)需要讀出整個(gè)set，添加一個(gè)新元素，然后再把整個(gè)set

賦回去Storage如果是設(shè)計(jì)Yelp呢？第27頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將NoSQL

-

Redis數(shù)據(jù)可持久化原生支持list，set等結(jié)構(gòu)讀寫(xiě)速度接近內(nèi)存

速度

>100k

QPS第28頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將用戶發(fā)出打車(chē)請(qǐng)求，查詢給定位置周?chē)?lat,lng)

→

geohash

→

[driver1,

driver2,

…]先查6位的geohash?找0.6公里以內(nèi)的如果沒(méi)有?

再查5位的geohash?找2.4公里以內(nèi)的如果沒(méi)有?

再查4位的geohash?找20公里以內(nèi)的匹配

成功，用戶查詢driver1

→

(lat,

lng)所在位置打車(chē)用戶的角度Driver

Tablekeydriver_idvalue(lat,

lng,

status,

updated_at,

trip_id)Location

Tablekeygeohashvalue{driver1_id,

driver2_id,

driver3_id

…}指向UserTable，UserTable存在其他數(shù)據(jù)庫(kù)中，可以是SQL數(shù)據(jù)庫(kù)第29頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將?匯報(bào)自己的位置計(jì)算當(dāng)前位置lat,lng的geohashgeohash4,

geohash5,

geohash6查詢自己原來(lái)所在的位置geohash4’,geohash5’,

geohash6’在Driver

Table中更新自己的最后活躍時(shí)間接受打車(chē)請(qǐng)求修改Trip

狀態(tài)用戶發(fā)出請(qǐng)求時(shí)就已經(jīng)在Trip

Table中創(chuàng)建一次旅程?

并Match上最近的在Driver

Table

中標(biāo)記自己的狀態(tài)進(jìn)入不可用狀態(tài)完成接送?

結(jié)束一次Trip在Trip

Table中修改旅程狀態(tài)在Driver

Table

中標(biāo)記自己的狀態(tài)進(jìn)入可用狀態(tài)的角度對(duì)比是否發(fā)生變化并將變化的部分在Redis

中進(jìn)行修改第30頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將乘客發(fā)出打車(chē)請(qǐng)求，服務(wù)器創(chuàng)建一次Trip將trip_id

返回給用戶乘客每隔幾秒詢問(wèn)一次服務(wù)器是否匹配成功2.

服務(wù)器找到匹配的

，寫(xiě)入Trip，狀態(tài)為等待回應(yīng)同時(shí)修改Driver

Table

中的匯報(bào)自己的位置狀態(tài)為不可用，并存入對(duì)應(yīng)的trip_id3.順便在Driver

Table

中發(fā)現(xiàn)有分配給自己的trip_id去Trip

Table

查詢對(duì)應(yīng)的Trip，返回給接受打車(chē)請(qǐng)求修改Driver

Table,Trip中的狀態(tài)信息4.信息乘客發(fā)現(xiàn)自己匹配成功，獲得打車(chē)請(qǐng)求修改Driver

Table，Trip

中的狀態(tài)信息，標(biāo)記該5.已經(jīng)了該trip重新匹配一個(gè)

，重復(fù)第2步可行解Work

Solution第31頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將可行解Work

SolutionReport

Locations

every

4sRequest

UberReturn

matched

driverReturn

matched

riderUpdate

driver’s

statusFind

driversnearbyDispatchServiceDispatchWebServerTrip

TableUser

Table(SQL)GeoServiceGeoWebServerLocationTable

Driver

Table(Redis)Look

up

driver’s

locationAccept

/

DenyRequest第32頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將看看有哪些問(wèn)題沒(méi)有解決，需要優(yōu)化出現(xiàn)故障怎么辦Scale拓展第33頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將有什么隱患？需求是150k

QPS

Redis

的讀寫(xiě)效率>100

QPS是不是1-2臺(tái)就可以了？第34頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將Interviewer:

Redis

server

is

down?隨便掛一臺(tái)，分分鐘損失幾百萬(wàn)$第35頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將DB

Sharding目的1：分?jǐn)偭髁磕康?：Avoid

Single

Point

Failure按照什么來(lái)Sharding?第36頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將按照城市Sharding難點(diǎn)1：如何定義城市？難點(diǎn)2：如何根據(jù)位置信息知道用戶在哪個(gè)城市？為什么不能按照其他的比如user_id

來(lái)sharding？第37頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將用多邊形代表城市的范圍問(wèn)題本質(zhì)：求一個(gè)點(diǎn)是否在多邊形內(nèi)計(jì)算幾何問(wèn)題城市的數(shù)目：400個(gè)乘客站在兩個(gè)城市的邊界上怎么辦？找到乘客周?chē)?-3個(gè)城市這些城市不能隔太遠(yuǎn)以至于車(chē)太遠(yuǎn)匯總多個(gè)城市的查詢結(jié)果這種情況下 的記錄在存哪個(gè)城市關(guān)系不大GeoFence第38頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將Interviewer:

How

to

check

rideris

in

Airport?同樣可以用GeoFence類似機(jī)場(chǎng)這樣的區(qū)域有上萬(wàn)個(gè)，直接O(N)查詢太慢分為兩級(jí)Fence查詢，先找到城市，再在城市中查詢Airport

FenceRead

More:第39頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將Interviewer:

How

to

reduceimpact

on

db

crash?多臺(tái)Redis雖然能減少損失但是再小的機(jī)器掛了，都還是會(huì)影響如何減小損失？第40頁(yè)本和經(jīng)教濟(jì)程賠由償

社區(qū)用戶整理與，否則將方法1：Replica

by

RedisMaster

-

Slave方法2：Replica

by

yourself底層

的接口將每份數(shù)據(jù)寫(xiě)3份sharding

key

從123

(city_id)

擴(kuò)展為123-0123-1123-2的時(shí)候，從任意一份

replica

數(shù)據(jù)讀不到的時(shí)候，就從其他的replica

讀三份replica極有可能存在3個(gè)