Chapter 10 Design Uber/Lyft
10.1 Open source
Youtube Channel:
https://www.youtube.com/channel/UCQlvjgieHGgkpP_9GiVyTGw
https://github.com/shadowwalker2718/chaperone
https://eng.uber.com/billion-data-point-challenge/
10.2 Official Articles
How Uber scaled its Real Time Infrastructure to Trillion events per day
10+ Million messages per second >>> (2**40)/ (24*3600) / (2**20) = 12
https://www.slideshare.net/AnkurBansal50/uber-real-time-data-analytics
- Matching
https://youtu.be/GyPq2joHZv4?t=305
trip upgrade https://youtu.be/GyPq2joHZv4?t=385
mapping service: input as time from point A to B
10.4 Articles about Uber’s challenges and solutions
http://highscalability.com/blog/2015/9/14/how-uber-scales-their-real-time-market-platform.html
https://www.infoq.com/presentations/uber-market-platform
Matt Ranney explains the Uber architecture overall, with a focus on the dispatch systems, the geospatial index, handling failure, and dealing with the distributed traveling salesman problem.
SOA
10.6 Uber Eats
- Beacon functionality
https://youtu.be/8coYi-Jgv7I?t=519
https://youtu.be/8coYi-Jgv7I?t=100
https://youtu.be/K-fI2BeTLkk?t=193
ETA problem: https://youtu.be/K-fI2BeTLkk?t=208
- Fraud Detection
https://www.jiuzhang.com/qa/4985/
其实这个系统很简单,没啥可 design 的.具体他要问什么可能还得跟他沟通一下才能知道.大致的方向就是:
1.用户订餐,通知餐馆.
2.餐馆做好菜了,通知 Uber 取餐 or 接单的时候给出 ETA
3.送餐员在Pickup 和 Deliver 这个过程需要优化一些路径,让他可以更节省成本.比如可以用一些聚类之类的算法.
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=172326
Uber Eat是uber现在那个订餐吗?uber好像现在有一个服务是你提前定好然后uber司机去送过去给你.
但是我朋友问的和现在这个服务稍微有些不太一样,是一个系统设计题.我朋友面试的反馈说,uber希望做一个系统可以全自动匹配饭店、司机、顾客三方,就是给司机一个预估的路线和时间,然后自己说出一套可实现的算法,建议用二维dp做.设计路线的时候最好也要考虑好先送a家还是先送b家.然后还有可以回答如何存储地址簿.面试官也可能会让你写出某一部分的代码.
朋友说最重要的是要跟面试官沟通,面试官不仅是考虑的是你自己的能力,还有和团队配合的能力,即使面试官很可能心里已经有个答案了.
10.8 task management system
设计一个task management system, (1) 会有1million可能出现的task种类,每个种类处理速度不同,有的甚至耗费几天, (2) 1000 task execution per second, 这1000个task其中的种类不一定,有可能都不同,也有可能是同一种task (3) 要求保证每个task至少完成一次, (4) 且durably store task result.
10.9 Design a system to track traffic of ad clicking.
由於他們是用nginx 做service proxy, 每個被clicked Ad的link 都會發經過nignx, 並且紀錄在log file中, 剛好這方面我也有經驗, 在這邊聊了一下, 怎麼offline process nginx 的log, 並且怎麼用map reduce 去統計ad click count.
10.10 design netflix recommendation system
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=447200&highlight=uber
问我应该怎么给用户推荐,选哪些features,我只说了按照genre分类用户选了某些题材以后可以推荐同类型的,然而hm并不满意,后来在网上看到如果两个用户有相似的浏览记录那可以group together用一个的click给另一个人推荐,所以正确答案是啥有没有小伙伴知道.
netflix选出每个题材下,在7天,30天和总共的时间段内view最多的10个视频,当时给的定义是如果一个用户在一天之内view了video长度的90%以上那么就算一个view,一个用户会不停的往server发(user, video, 看video的start和endtime),然后脑子里瞬间想到各种算法题merge intervals算video的covered时间（但是如果动态添加interval就不知道怎么搞了),以及当时总觉得有个什么data structure可以根据view的个数维持一个video的sorted array并且能动态更新view的数量,面完以后想了想应该是LFU.但是这不是system design吗…中年烙印全程面无表情不引导话题走向,到后面甚至玩上了手机,看来是凉透了
algorithm的情境是你有n个server,每个server负责一定数量的地区的叫车请求,然后你有m个地区, 如果两个地区的距离小于一个threshold,那么这两个地区应该归同一个server管.让你写一个function ,输入参数是server的数量,城市的坐标和城市的业务量,返回一个server与城市的对应关系,要求是 每个server的总业务量balance.
设计一个发邮件的系统,给内部用.要自己问他有什么要求,然后就是要我先写API之 类,再讨论scale和情况之类的
monitor service,follow up,scale,single point of failure
第三轮:设计一个可以scale的metrics系统 第四轮:设计一个股票系统,支持查询当前时刻某只股票的股价,当天的涨幅最大和跌幅最大的股票 ,和某只股票历史股价
system design就是关于货车司机的,要解决两个问题,好像如何设计货车司机端,查找附近的仓库, 如何确认司机到达仓库等等,然后scala成一个可行的architect.要很详细,比如数据库具体怎么存 的.然后后面scala的时候,也要具体到怎么scala的.
- Design:设计Uber.
https://jiayi797.github.io/2018/01/21/%E7%B3%BB%E7%BB%9F%E8%AE%BE%E8%AE%A1-%E8%AE%BE%E8%AE%A1Uber/
感觉实践中这个题目可以有很多变化,侧重不同部分,建议多想想相关feature……准备的时候我主要看的是关于Geo的部分和如何实时汇报位置,实际面试中面官并没有对这部分深入追问,我说了Geo Hash又提了一下可以用google S2就满意了.但是让我具体写了一下数据库schema.还问了如果我们要schedule ride（比如说提前预定明天凌晨去机场的ride)应该怎么办.我答的先提前问司机们谁愿意接,然后在预约时间接近时如果提前接订单的司机cancel了或者距离pickup地点距离太远则重新找司机.
后来答完了时间富裕就有问了payment的问题.ride结束后,payment一般不会立刻处理,而是先暂存信息随后再集中处理,问这种情况下该怎么设计.没准备就瞎说的,不过似乎因为是附加题也不是很重要.面官给的方案是因为可以delay,可以不使用任何数据库,而是直接把raw data写到HDFS,然后集中进行batch处理. 一个细节是开始问payment相关问题之前对方看了下手机说我们还有些时间,所以我认为后面的payment部分是附加题……
https://www.youtube.com/watch?v=rp7_7HcqmKA&list=PLLEUtp5eGr7Dz3fWGUpiSiG3d_WgJe-KJ
设计一个可以追踪卡车司机位置的系统.需要实现两个功能:实时告诉供货商司机的位置,当司 机出发或者到达指定地点时通知供货商.
第四轮coding,让写一个chess游戏,见我对chess规则不太了解,改德州扑克,这个我也不熟悉但起码比chess好点, 就开始写,从card类,到牌堆,到玩家,到dealer.面试官是要求能run.code是在自己的笔记本上写,很遗憾没写完
Uber总是考一些系统设计的题目,而且重复率很高,汇总了一下地里的所有design的题目,希望可以跟小伙伴们讨论下.
Uber Design Questions
1. 让design uber app
2. 常见题-Design spotify,主要在问playlist和shuffle list功能.
3. facebook friends recommendation.
4. Excel设计
5. 聊项目 + 设计Messenger.因为我之前写过P2P的聊天软件就先讨论了一下P2P vs. S/C, 然后就有服务器的情况深入,authentication,scalability,reliability, database, cache …
6. 设计一个parkinglot, 然后parking lot 有digital sign 可以显示汽车和摩托车还有多少空位然后我就用两个变量去记录cur .然后followup 继续问,那要是有好多种新的车型
6. Desing, tiny url.
7. System design, subscription
8. design game:tilt maze
9. 设计rate limiter.
10. 有一个第三方的API,写一个wrapper来限制这个API每分钟call的次数,比如每分钟100次.如果,没超过限制,就call这个API;否则,就给userthrow个exception
11. 一个国人中年人,设计题:设计一个email系统,搞了半天才发现面试官要求focus在数据库里面table的设计上面,在面试官的提示下瞎设计了一个
12. SystemDesign. 设计Instagram.
13. DesignYoutube / Netflix
14. 题目是设计一个租车系统
10.11 Design Uber
- rider/driver matching
https://ringpop.readthedocs.io/en/latest/architecture_design.html
- schedule ride
delay queue, data structure with a due timestamp.
- payment
10.12 Payment
- payments platform
- single integrated money system
- zero sum system
- auditable
- business independent
- single integrated money system
- payment onboarding platform
- single integrated money system
- dev/ops
- compliance
- security
- single integrated money system
- driver payments
- engagement
- on-demand payments
- uber visa/debit card
https://youtu.be/Dz6dAZs8Scg?t=304
Payment Integration (Rider Payments Team) – Use case: build
google payinto the system
– Add flow
– charge flow
– authorize flow
– delete flow– payment profile
– backend ops: add, charge, auth, capture, void/refund, delete
https://developers.braintreepayments.com/guides/payment-method-nonces
use case:
switch payment on-trip, tipping, scheduled rides(google pay token only valid for 7 days), EATs order flow, promotions, uber for business, scheduled dunning…
sandbox testing, testing with real cards, debugging