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

课程版本

v5.1

主讲

东邪扫描

/获取

面试题及

解答:ninechapter:

ht

/ninechapter知乎:

http://z

/jiuzhang官网:http:

基于地理位置的服务Location

Based

Service第1页本和经教济程赔由偿

社区用户整理与，否则将Design

UberDesignDesign

YelpNearbyDesign

Pokemon

Go总结系统设计今日课程大纲第2页本和经教济程赔由偿

社区用户整理与，否则将Interviewer:

Please

designUberSimilar

questions:How

to

design

nearbyHow

to

design

yelp是否看过关于Uber

Architecture

的，讲座或是文章？第3页本和经教济程赔由偿

社区用户整理与，否则将RingPop

/uber/ringpop-node一个分布式架构扩展阅读••[Hard][Hard]TChannel•

/uber/tchannel一个高效的RPC协议RPC:

Remote

Procedure

CallS2/s2-geometry-library-java与查询的算法

/一个地理位置信息RiakDynamo

DB

的开源实现你大概会知道Uber用了如下一些技术告诉我你看到这些词的感受是不是这样？第4页本和经教济程赔由偿

社区用户整理与，否则将Read

more

on

Uber

Eng

Blogh

/是不是答出Uber是怎么实现的，就可以拿到Offer?第5页本和经教济程赔由偿

社区用户整理与，否则将系统设计面试常见误区以为答出该公司是怎么做的，就可以拿到Offer了第6页本和经教济程赔由偿

社区用户整理与，否则将Uber的架构非常小众Uber用到的技术是自己设计出的一套东西如果Uber面你这个题，你不可能比他们清楚，并且显得你是准备过的，不能代表你真实的能力如果其他公司面你这个题，这也不会是期望答案第7页本和经教济程赔由偿

社区用户整理与，否则将Scenario

场景FeaturesQPS

/

StorageService

服务Service

Oriented

ArchitectureStorage

数据SchemaScale

进化RobustFeature系统设计的4S

分析法逻辑设计Logic

Design50%Make

it

work!架构设计Infrastructure

Design

50%Make

it

robust!第8页本和经教济程赔由偿

社区用户整理与，否则将System

Design

=Logic

Design

+

Infrastructure

Design系统设计=逻辑设计+架构设计第9页本和经教济程赔由偿

社区用户整理与，否则将Scenario

场景需要设计哪些功能，设计得多牛设计哪些功能？第10页本和经教济程赔由偿

社区用户整理与，否则将第一阶段：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页本和经教济程赔由偿

社区用户整理与，否则将Scenario-设计得多牛？问问面试官:贵优步现在多少辆车了？贵优步现在多少QPS呀？贵优步遍布多少城市呀？猜猜Uber

2011

年的QPS猜猜Uber

2015

年的QPS第12页本和经教济程赔由偿

社区用户整理与，否则将假设问到

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

自己定的设计目标支持1M

QPS这些数字是多少并不重要，你算给面试官看就好了估算假如每条Location都记录：200

k

*

86400/4

*

100bytes(每条位置记录）~

0.5

T/天假如只记录当前位置信息：200

k

*

100

bytes=20

MScenario-设计得多牛初步感觉：150k

的写操作是不容小觑的必须找一个写速度快的

！第13页本和经教济程赔由偿

社区用户整理与，否则将Uber

主要干的事情就两件记录车的位置GeoService匹配打车请求DispatchServiceService

服务GeoServiceDispatchServiceReport

Locationsevery

4sRequest

UberDriver

info这张图里漏了什么？第14页本和经教济程赔由偿

社区用户整理与，否则将Driver

如何获得打车请求？Report

location

的同时，服务器顺便返回匹配上的打车请求Service服务GeoServiceDispatchServiceDriver:

Save

locationRider:

Find

drivers

nearby问：Service

里到底包含了什么？答：逻辑处理+数据

的整合第15页本和经教济程赔由偿

社区用户整理与，否则将DispatchServiceStorageDriver:

Save

locationRider:

Find

drivers

nearbyTrip

Table(?)DispatchWebServerGeoWebServerLocationTable(?)GeoService读vs写?读vs写?第16页本和经教济程赔由偿

社区用户整理与，否则将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

细化数据表单第17页本和经教济程赔由偿

社区用户整理与，否则将Trip

Tabletypecommentsidpkprimary

keyrider_idfkUseriddriver_idfkUser

idlatfloatLatitude

纬度lngfloatLongitude

经度statusintNew

request

/

waiting

for

driver

/

on

the

way

to

pick

up

/

in

trip

/

cancelled/

endedcreated_attimestampStorage——Schema

细化数据表单Location

Tabletypecommentsdriver_idfkPrimary

keylatfk纬度lngfk经度updated_attimestamp存最后更新的时间，这样知道 是不是掉线了第18页本和经教济程赔由偿

社区用户整理与，否则将LBS

类系统的难点：和查询地理位置信息？如何如，查询某个乘客周围5公里内的第19页本和经教济程赔由偿

社区用户整理与，否则将查询地理位置信息Naive

SolutionSELECT

*

FROM

LocationWHERE

lat

<

myLat

+

deltaAND

lat

>

myLat

-

deltaAND

lng

<

myLng

+

deltaAND

lng

>

myLng

-

delta;——这个基本等同于扫描了一遍所有的数据第20页本和经教济程赔由偿

社区用户整理与，否则将•S2Read

more:Hilbert

Curve:将地址空间到2^64的整数特性：如果空间上比较接近的两个点，对应的整数也比较接近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

——地理位置信息的与查询更精准，库函数API丰富比较简单，准确度差一些第21页本和经教济程赔由偿

社区用户整理与，否则将Examples:LinkedIn

HQ:

9q9hu3hhsjxx••HQ:

9q9hvu7wbq2sHQ:

9q9j45zvr0seGeohash第22页本和经教济程赔由偿

社区用户整理与，否则将Takea

break5

分钟后回来第23页本和经教济程赔由偿

社区用户整理与，否则将北海公园：lat=39.928167,lng=116.389550二分(-180,180)

近经度༌

左半部记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…

(

还可以继续二分求获得 的精度༉Geohash先经后纬，经纬交替1110011101W

X课后作业：http:

/problem/geohash/第24页本和经教济程赔由偿

社区用户整理与，否则将找到精度误差>2公里的最长长度HQ:

9q9hvu7wbq2s找到位置以9q9hv以开头的所有车辆查询

半径2公里内的车辆怎样在数据库中实现该功能？第25页本和经教济程赔由偿

社区用户整理与，否则将SQL

数据库首先需要对geohash

建索引CREATE

INDEX

on

geohash;使用Like

QuerySELECT

*

FROM

location

WHERE

geohash

LIKE`

9q9hv%`;NoSQL

-

Cassandra将geohash

设为column

key使用range

query

(9q9hv0,9q9hvz)NoSQL

-

Redis

/

MemcachedDriver

的位置分级如

Driver的位置如果是

9q9hvt，则

在

9q9hvt，

9q9hv，

9q9h

这

3

个

key

中6位

geohash

的精度已经在

以内，对于

Uber

这类应用足够了4位geohash

的精度在20公里以上了，再大就没意义了，你不会打20公里以外的车key

=

9q9hvt,

value

=

set

of

drivers

in

this

locationStorage从数据 与查询的角度哪种结构更合？第26页本和经教济程赔由偿

社区用户整理与，否则将结构的特性，对于面试十分加分！能够熟悉每种数据SQL

可以，但相对较慢原因1：Like

query

很慢，应该尽量避免即便有index，也很慢原因2：Uber

的应用中，Driver

需要实时Update

自己的地理位置被index的column并不适合经常被修改B+树不停变动，效率低NoSQL–Cassandra

可以，但相对较慢原因：Driver

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

Key

是有index

的，被index

的column

不适合经常被“修改”NoSQL–Memcached

并不合适原因1：Memcached

没有持久化

，一旦挂了，数据就丢失原因2：Memcached

并不原生支持set

结构需要读出整个set，添加一个新元素，然后再把整个set

赋回去Storage如果是设计Yelp呢？第27页本和经教济程赔由偿

社区用户整理与，否则将NoSQL

-

Redis数据可持久化原生支持list，set等结构读写速度接近内存

速度

>100k

QPS第28页本和经教济程赔由偿

社区用户整理与，否则将用户发出打车请求，查询给定位置周围的(lat,lng)

→

geohash

→

[driver1,

driver2,

…]先查6位的geohash༌找0.6公里以内的如果没有༌

再查5位的geohash༌找2.4公里以内的如果没有༌

再查4位的geohash༌找20公里以内的匹配

成功，用户查询driver1

→

(lat,

lng)所在位置打车用户的角度Driver

Tablekeydriver_idvalue(lat,

lng,

status,

updated_at,

trip_id)Location

Tablekeygeohashvalue{driver1_id,

driver2_id,

driver3_id

…}指向UserTable，UserTable存在其他数据库中，可以是SQL数据库第29页本和经教济程赔由偿

社区用户整理与，否则将•汇报自己的位置计算当前位置lat,lng的geohashgeohash4,

geohash5,

geohash6查询自己原来所在的位置geohash4’,geohash5’,

geohash6’在Driver

Table中更新自己的最后活跃时间接受打车请求修改Trip

状态用户发出请求时就已经在Trip

Table中创建一次旅程༌

并Match上最近的在Driver

Table

中标记自己的状态进入不可用状态完成接送༌

结束一次Trip在Trip

Table中修改旅程状态在Driver

Table

中标记自己的状态进入可用状态的角度对比是否发生变化并将变化的部分在Redis

中进行修改第30页本和经教济程赔由偿

社区用户整理与，否则将乘客发出打车请求，服务器创建一次Trip将trip_id

返回给用户乘客每隔几秒询问一次服务器是否匹配成功2.

服务器找到匹配的

，写入Trip，状态为等待回应同时修改Driver

Table

中的汇报自己的位置状态为不可用，并存入对应的trip_id3.顺便在Driver

Table

中发现有分配给自己的trip_id去Trip

Table

查询对应的Trip，返回给接受打车请求修改Driver

Table,Trip中的状态信息4.信息乘客发现自己匹配成功，获得打车请求修改Driver

Table，Trip

中的状态信息，标记该5.已经了该trip重新匹配一个

，重复第2步可行解Work

Solution第31页本和经教济程赔由偿

社区用户整理与，否则将可行解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页本和经教济程赔由偿

社区用户整理与，否则将看看有哪些问题没有解决，需要优化出现故障怎么办Scale拓展第33页本和经教济程赔由偿

社区用户整理与，否则将有什么隐患？需求是150k

QPS

Redis

的读写效率>100

QPS是不是1-2台就可以了？第34页本和经教济程赔由偿

社区用户整理与，否则将Interviewer:

Redis

server

is

down?随便挂一台，分分钟损失几百万$第35页本和经教济程赔由偿

社区用户整理与，否则将DB

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

Single

Point

Failure按照什么来Sharding?第36页本和经教济程赔由偿

社区用户整理与，否则将按照城市Sharding难点1：如何定义城市？难点2：如何根据位置信息知道用户在哪个城市？为什么不能按照其他的比如user_id

来sharding？第37页本和经教济程赔由偿

社区用户整理与，否则将用多边形代表城市的范围问题本质：求一个点是否在多边形内计算几何问题城市的数目：400个乘客站在两个城市的边界上怎么办？找到乘客周围的2-3个城市这些城市不能隔太远以至于车太远汇总多个城市的查询结果这种情况下 的记录在存哪个城市关系不大GeoFence第38页本和经教济程赔由偿

社区用户整理与，否则将Interviewer:

How

to

check

rideris

in

Airport?同样可以用GeoFence类似机场这样的区域有上万个，直接O(N)查询太慢分为两级Fence查询，先找到城市，再在城市中查询Airport

FenceRead

More:第39页本和经教济程赔由偿

社区用户整理与，否则将Interviewer:

How

to

reduceimpact

on

db

crash?多台Redis虽然能减少损失但是再小的机器挂了，都还是会影响如何减小损失？第40页本和经教济程赔由偿

社区用户整理与，否则将方法1：Replica

by

RedisMaster

-

Slave方法2：Replica

by

yourself底层

的接口将每份数据写3份sharding

key

从123

(city_id)

扩展为123-0123-1123-2的时候，从任意一份

replica

数据读不到的时候，就从其他的replica

读三份replica极有可能存在3个