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

課程版本

v5.1

主講

東邪掃描

/獲取

面試題及

解答:ninechapter:

ht

/ninechapter知乎:

http://z

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

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

Based

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

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

UberDesignDesign

YelpNearbyDesign

Pokemon

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

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

Please

designUberSimilar

questions:How

to

design

nearbyHow

to

design

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

Architecture

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

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

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

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

Remote

Procedure

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

/一個地理位置信息RiakDynamo

DB

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

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

more

on

Uber

Eng

Blogh

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

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

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

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

場景FeaturesQPS

/

StorageService

服務(wù)Service

Oriented

ArchitectureStorage

數(shù)據(jù)SchemaScale

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

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

Design50%Make

it

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

Design

50%Make

it

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

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

Design

=Logic

Design

+

Infrastructure

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

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

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

社區(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

場景無所謂的加分項，如果你都答到這里了，說明你前面都秒殺了第11頁本和經(jīng)教濟程賠由償

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

2011

年的QPS猜猜Uber

2015

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

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

20

萬

同時Driver

QPS

=

200k

/

4

=

50kDriver

report

locations

by

every

4

secondsPeak

Driver

QPS

=

50k

*

3

=

150

kUber

自己的說法：2015

新年夜的Peak

QPS

是170KRead

More:Rider

QPS

可以忽略無需隨時匯報位置一定遠小于Driver

QPSUber

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

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

k

*

86400/4

*

100bytes(每條位置記錄）~

0.5

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

k

*

100

bytes=20

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

的寫操作是不容小覷的必須找一個寫速度快的

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

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

主要干的事情就兩件記錄車的位置GeoService匹配打車請求DispatchServiceService

服務(wù)GeoServiceDispatchServiceReport

Locationsevery

4sRequest

UberDriver

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

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

如何獲得打車請求？Report

location

的同時，服務(wù)器順便返回匹配上的打車請求Service服務(wù)GeoServiceDispatchServiceDriver:

Save

locationRider:

Find

drivers

nearby問：Service

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

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

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

Save

locationRider:

Find

drivers

nearbyTrip

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

社區(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

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

社區(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

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

Tabletypecommentsdriver_idfkPrimary

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

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

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

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

SolutionSELECT

*

FROM

LocationWHERE

lat

<

myLat

+

deltaAND

lat

>

myLat

-

deltaAND

lng

<

myLng

+

deltaAND

lng

>

myLng

-

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

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

more:Hilbert

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

(-30.043800,

-51.140220)

→GeohashRead

more:Peano

CurveBase32：0-9,a-z

去掉(a,i,l,o)為什么用base32?因為剛好25可以用5

位二進制表示思路二分法特性：公共前綴越長，兩個點越接近Example:

(-30.043800,

-51.140220)

→

6feth68y4tb015Storage

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

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

HQ:

9q9hu3hhsjxx??HQ:

9q9hvu7wbq2sHQ:

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

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

break5

分鐘后回來第23頁本和經(jīng)教濟程賠由償

社區(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頁本和經(jīng)教濟程賠由償

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

9q9hvu7wbq2s找到位置以9q9hv以開頭的所有車輛查詢

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

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

數(shù)據(jù)庫首先需要對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

的位置分級如

Driver的位置如果是

9q9hvt，則

在

9q9hvt，

9q9hv，

9q9h

這

3

個

key

中6位

geohash

的精度已經(jīng)在

以內(nèi)，對于

Uber

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

的精度在20公里以上了，再大就沒意義了，你不會打20公里以外的車key

=

9q9hvt,

value

=

set

of

drivers

in

this

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

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

可以，但相對較慢原因1：Like

query

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

的應(yīng)用中，Driver

需要實時Update

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

可以，但相對較慢原因：Driver

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

Key

是有index

的，被index

的column

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

并不合適原因1：Memcached

沒有持久化

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

并不原生支持set

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

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

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

-

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

速度

>100k

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

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

→

geohash

→

[driver1,

driver2,

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

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

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

成功，用戶查詢driver1

→

(lat,

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

Tablekeydriver_idvalue(lat,

lng,

status,

updated_at,

trip_id)Location

Tablekeygeohashvalue{driver1_id,

driver2_id,

driver3_id

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

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

geohash5,

geohash6查詢自己原來所在的位置geohash4’,geohash5’,

geohash6’在Driver

Table中更新自己的最后活躍時間接受打車請求修改Trip

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

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

并Match上最近的在Driver

Table

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

結(jié)束一次Trip在Trip

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

Table

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

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

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

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

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

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

Table

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

Table

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

Table

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

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

Table，Trip

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

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

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

社區(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頁本和經(jīng)教濟程賠由償

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

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

QPS

Redis

的讀寫效率>100

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

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

Redis

server

is

down?隨便掛一臺，分分鐘損失幾百萬$第35頁本和經(jīng)教濟程賠由償

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

Sharding目的1：分攤流量目的2：Avoid

Single

Point

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

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

來sharding？第37頁本和經(jīng)教濟程賠由償

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

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

How

to

check

rideris

in

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

FenceRead

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

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

How

to

reduceimpact

on

db

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

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

by

RedisMaster

-

Slave方法2：Replica

by

yourself底層

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

key

從123

(city_id)

擴展為123-0123-1123-2的時候，從任意一份

replica

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

讀三份replica極有可能存在3個