m***i
发帖数: 37 | 1 挂在了设计题, 设计Uber app的两个service。
driver/车
update (carId,log,lat), 1 update per sec.
rider
getCarsAndETA(log,lat), 1 request per sec.
某个城市，假设是SF，有1000辆车，1000个active users.
Q：
单机可以吗？
如何存储数据，用数据库吗？
如何update车移动的数据（设计数据结构）。
如何设计getCarsAndETA求得ETA最小的10辆车 （可以简单的假设距离近就ETA小）。
如果update的响应速度比getCarsAndETA快得多(getCarsAndETA计算量很大），怎么
scale这两个service，即怎么使getCarsAndETA跟得上update的响应速度。
如何scale到其他城市
1）周边小城市
2）距离很远的大城市
看过一个talk讲到Uber用的是google的一个library,将地图分成一个个block，根据某
个点画个圈，只计算圈所覆盖的blocks。
我就是按这个思路答的，不过被指出这样有个问题是如果block size不小，那同一个
block里面车，即使是在两个对角的也算同一个block，以block为单位计算距离的话不
够准确。
各位有什么想法/解法，请不吝赐教。谢谢。 |
A********d
发帖数: 558 | 2 赞楼主的分享精神！这个版太缺了，总有人把我和swjtuer那个傻逼相提并论，最大的
区别就是姐当年把所有面试面筋都奉献出来了，swjtuer就只发挑拨离间贴和阴阳怪气
的留言。 |
l*******i
发帖数: 25 | 3 Use a hash map to store locations of cars.
Cars location is updated every second, but reconstruct a KD tree only every
minute.
cache the result of getCarsAndETA() so it is only update every minute. |
l*******i
发帖数: 25 | 4 To be more accurate. You can compute the velocity of cars and estimate their
locations between minutes. |
s*********n
发帖数: 35 | 5 一共就1000辆车 单机存内存应该可以吧 （反正数据每秒上报，后面车的数据覆盖前
面的，不存在持久化问题）
然后将地图分为六边形小块，每个车更新位置时以hexgon id做一个index。 这样找车
的时候查当前六边形附近几个的candidates
找车api算的慢，估计时间都耗在计算距离上了，可以单独提出来做一个前端，部署多
台机器，从后端内存数据库里提取candidate list 然后逐一计算距离。
大家感觉这么的靠谱不
【在 m***i 的大作中提到】
: 挂在了设计题, 设计Uber app的两个service。
: driver/车
: update (carId,log,lat), 1 update per sec.
: rider
: getCarsAndETA(log,lat), 1 request per sec.
: 某个城市，假设是SF，有1000辆车，1000个active users.
: Q：
: 单机可以吗？
: 如何存储数据，用数据库吗？
: 如何update车移动的数据（设计数据结构）。
|
G****A
发帖数: 4160 | 6 lat是latitude的意思？
【在 m***i 的大作中提到】
: 挂在了设计题, 设计Uber app的两个service。
: driver/车
: update (carId,log,lat), 1 update per sec.
: rider
: getCarsAndETA(log,lat), 1 request per sec.
: 某个城市，假设是SF，有1000辆车，1000个active users.
: Q：
: 单机可以吗？
: 如何存储数据，用数据库吗？
: 如何update车移动的数据（设计数据结构）。
|
z*********8
发帖数: 2070 | 7 瓶颈应该不在内存而在cpu上面吧， 2000qps的计算量估计单机扛不住
【在 s*********n 的大作中提到】
: 一共就1000辆车 单机存内存应该可以吧 （反正数据每秒上报，后面车的数据覆盖前
: 面的，不存在持久化问题）
: 然后将地图分为六边形小块，每个车更新位置时以hexgon id做一个index。 这样找车
: 的时候查当前六边形附近几个的candidates
: 找车api算的慢，估计时间都耗在计算距离上了，可以单独提出来做一个前端，部署多
: 台机器，从后端内存数据库里提取candidate list 然后逐一计算距离。
: 大家感觉这么的靠谱不
|
G****A
发帖数: 4160 | 8 lat是latitude的意思？
【在 m***i 的大作中提到】
: 挂在了设计题, 设计Uber app的两个service。
: driver/车
: update (carId,log,lat), 1 update per sec.
: rider
: getCarsAndETA(log,lat), 1 request per sec.
: 某个城市，假设是SF，有1000辆车，1000个active users.
: Q：
: 单机可以吗？
: 如何存储数据，用数据库吗？
: 如何update车移动的数据（设计数据结构）。
|
z*********n
发帖数: 1451 | 9 我帮lz回答下最后一问，block的那个问题，看过网上的文章，正解（事实人家就是这
么做的）就是把周围的一圈block也考虑进来，然后以实际距离决出一个最近的。。。
lz看到这个会不会很无语
。。 |
s**x
发帖数: 7506 | 10 Block 有好多缺点阿，这是最普通的办法。估计最好是 kd tree , quad tree 或
Geohash, 其实就是 hierarchical block.
每秒update 一次，连数据库都用不着.
1000 辆车，一台机器应该足够了，但要容错，就要加备份。
: 我帮lz回答下最后一问，block的那个问题，看过网上的文章，正解（事实人家
就是这
: 么做的）就是把周围的一圈block也考虑进来，然后以实际距离决出一个最近的
。。。
: lz看到这个会不会很无语
: 。。
【在 z*********n 的大作中提到】
: 我帮lz回答下最后一问，block的那个问题，看过网上的文章，正解（事实人家就是这
: 么做的）就是把周围的一圈block也考虑进来，然后以实际距离决出一个最近的。。。
: lz看到这个会不会很无语
: 。。
|
|
|
z*********8
发帖数: 2070 | 11 kdtree quadtree不还是把地图分块的思想吗。。。实际上uber就是用的google s2
library把地图分成若干cell
【在 s**x 的大作中提到】
: Block 有好多缺点阿，这是最普通的办法。估计最好是 kd tree , quad tree 或
: Geohash, 其实就是 hierarchical block.
: 每秒update 一次，连数据库都用不着.
: 1000 辆车，一台机器应该足够了，但要容错，就要加备份。
:
:
: 我帮lz回答下最后一问，block的那个问题，看过网上的文章，正解（事实人家
: 就是这
:
: 么做的）就是把周围的一圈block也考虑进来，然后以实际距离决出一个最近的
: 。。。
:
: lz看到这个会不会很无语
|
j**********3
发帖数: 3211 | |
k***a
发帖数: 1199 | 13 看看geohashing的文档
【在 m***i 的大作中提到】
: 挂在了设计题, 设计Uber app的两个service。
: driver/车
: update (carId,log,lat), 1 update per sec.
: rider
: getCarsAndETA(log,lat), 1 request per sec.
: 某个城市，假设是SF，有1000辆车，1000个active users.
: Q：
: 单机可以吗？
: 如何存储数据，用数据库吗？
: 如何update车移动的数据（设计数据结构）。
|
s****7
发帖数: 19 | 14 难得的正能量帖，先顶再看，感谢分享
【在 m***i 的大作中提到】
: 挂在了设计题, 设计Uber app的两个service。
: driver/车
: update (carId,log,lat), 1 update per sec.
: rider
: getCarsAndETA(log,lat), 1 request per sec.
: 某个城市，假设是SF，有1000辆车，1000个active users.
: Q：
: 单机可以吗？
: 如何存储数据，用数据库吗？
: 如何update车移动的数据（设计数据结构）。
|
z*********n
发帖数: 1451 | 15
我怎么记得Google S2的精度要高于Geohash呢。。Geohash主要优点是速度快，对数据
库比较友好吧
【在 s**x 的大作中提到】
: Block 有好多缺点阿，这是最普通的办法。估计最好是 kd tree , quad tree 或
: Geohash, 其实就是 hierarchical block.
: 每秒update 一次，连数据库都用不着.
: 1000 辆车，一台机器应该足够了，但要容错，就要加备份。
:
:
: 我帮lz回答下最后一问，block的那个问题，看过网上的文章，正解（事实人家
: 就是这
:
: 么做的）就是把周围的一圈block也考虑进来，然后以实际距离决出一个最近的
: 。。。
:
: lz看到这个会不会很无语
|
w******g
发帖数: 262 | |
w*m
发帖数: 1806 | |
s**x
发帖数: 7506 | 18 那个cell不是简单的分块，是用Hilbert curve 弄的。俺也不憧。
: kdtree quadtree不还是把地图分块的思想吗。。。实际上uber就是用的google
s2
: library把地图分成若干cell
【在 z*********8 的大作中提到】
: kdtree quadtree不还是把地图分块的思想吗。。。实际上uber就是用的google s2
: library把地图分成若干cell
|
w*m
发帖数: 1806 | |
z*********n
发帖数: 1451 | 20
google
用Hilbert curve弄就是简单的把2维映射到1维，方便数据库检索而已，有一定的错误
率
【在 s**x 的大作中提到】
: 那个cell不是简单的分块，是用Hilbert curve 弄的。俺也不憧。
:
:
: kdtree quadtree不还是把地图分块的思想吗。。。实际上uber就是用的google
: s2
:
: library把地图分成若干cell
:
|
