14. 设计 Uber 后端
难度等级：困难 必备前提：设计 Yelp
让我们设计一个类似于 Uber 的出行共享服务，该服务将需要出行的乘客和有车的司机连接。相似服务：Lyft、Didi、Via、Sidecar 等。
1. 什么是 Uber？
Uber 允许乘客预订出租车出行的司机。Uber 司机使用他们的私家车运送乘客。乘客和司机之间使用智能手机上的 Uber 应用交流。
2. 系统的要求和目标
我们从搭建一个简单版本的 Uber 开始。
我们的系统中有两类用户：1. 司机；2. 乘客。
司机需要定期通知服务，告知他们的当前地点以及是否可以接乘客。
乘客需要看到所有的在附近可以接乘客的司机。
乘客可以请求出行，附近的司机将被通知一个乘客准备被接客。
一旦司机和乘客接受了一次出行，他们可以实时查看对方的当前地点，直到行程完成。
当到达目的地时，司机标记为行程完成，此时可以接下一个乘客。
3. 容量估算和限制
假设有 3 亿乘客和 100 万司机，其中有 100 万日活乘客和 50 万日活司机。
假设每天有 100 万次出行。
假设所有活跃的司机每过三秒告知他们的当前地点。
当乘客发起出行请求时，系统应该可以实时联系司机。
4. 基础系统设计和算法
我们将使用在「设计 Yelp」中讨论的解决方案，将其修改之后即可适用于上文提及的 Uber 使用场景。最大的区别是，上一个问题中建立四叉树的场景是没有大量更新。因此，对于动态网格解决方案，有两个问题：
由于所有活跃的司机每三秒报告一次地点，我们需要更新数据结构以体现这一点。如果我们必须在每次司机的位置发生变化时都更新四叉树，这会花费大量的时间和资源。为了将一个司机更新到新地点，我们必须基于该司机的前一个地点找到正确的网格。如果新位置不属于当前网格，我们必须将该司机从当前网格移除并将该司机移动/重新插入到正确的网格中。在移动之后，如果新网格达到了司机数量的上限，我们必须重新划分。
我们需要一个快速机制将当前地点的所有附近的司机的当前位置传播给该区域内任何活跃用户。同时，当一次行程在进行中时，我们的系统需要将车辆的当前地点通知到司机和乘客。
虽然我们的四叉树可以帮助我们快速找到附近的司机，但是不能保证可以快速更新树。
我们是否需要在每次司机报告地点时都修改四叉树？如果我们不是在每次司机报告地点时都修改四叉树，将会有一些旧数据，无法正确反映司机的当前地点。回想我们建立四叉树的目的是高效地找到附近的司机（或地点）。由于所有活跃的司机每三秒报告一次地点，因此我们的树中更新的次数远超过查询附近司机的次数。因此，如果我们在哈希表中存储所有司机最后报告的地点且更新四叉树的频率降低一点是否可行？假设我们保证司机的当前地点将在 15 秒内反映在四叉树中。与此同时，我们将维护一个哈希表存储司机报告的当前地点，我们将其称为「司机地点哈希表」（DriverLocationHT）。
我们存储司机地点哈希表需要多少内存？我们需要在哈希表中存储司机编号、他们的当前地点和旧地点。因此，我们存储一条记录一共需要 35 个字节：
司机编号（3 个字节——100 万司机）
旧纬度（8 个字节）
旧经度（8 个字节）
新纬度（8 个字节）
新经度（8 个字节）
总计 35 个字节。
如果我们总共有 100 万司机，我们需要的内存是（忽略哈希表的开销）：
1 million * 35 bytes => 35 MB
我们的服务需要消费多少带宽接收所有司机的地点更新？如果我们获得司机编号和他们的地点，将有 3+16 => 19 个字节。如果我们每三秒从 100 万司机处接收这些信息，我们将每三秒接收 19MB 信息。
我们是否需要将司机地点哈希表分布到多台服务器上？虽然我们的内存和带宽需求没有这样的要求，所有的信息都能容易地存储在一台服务器上，但是从可扩展性、性能和容错的角度考虑，我们应该将司机地点哈希表分布到多台服务器上。我们可以基于司机编号分布，使得分布是完全随机的。我们将存放司机地点哈希表的机器称为司机地点服务器。除了存储司机的地点以外，每台这样的机器将做两件事情：
当服务器接收到一个司机的地点更新时，会将该信息广播到所有相关的乘客。
服务器需要通知各自的四叉树服务器将司机的地点刷新。如上文讨论的，每 10 秒发生一次。
我们可以如何高效地将司机地地点广播到乘客？我们可以使用一个推送模型，服务器将地点推送给所有相关用户。我们可以使用一个专用的通知服务将司机的当前地点广播给所有相关的乘客。我们可以将通知服务建立在发布/订阅者模型上。当客户在手机上打开 Uber 应用时，他们查询服务器找到附近的司机。服务器端在将司机列表返回给用户之前，将为乘客订阅这些司机的所有更新。我们可以维护一个关心司机地点的乘客（订阅者）列表，当司机地点哈希表中有该司机的更新时，我们可以将该司机的当前地点广播给所有订阅的乘客。使用这个方法，我们的系统可以保证我们总是将司机的当前地点展示给乘客。
存储所有的订阅需要多少内存？根据我们上文的估算，我们将有 100 万日活乘客和 50 万日活司机。假设平均一个司机有五个乘客订阅。假设我们将所有的这些信息存入哈希表因此我们可以高效地更新。我们需要存储司机编号和乘客编号以维护订阅。假设我们需要 3 个字节存储司机编号和 8 个字节存储乘客编号，我们将需要 21MB 的内存。
(500K * 3) + (500K * 5 * 8 ) ~= 21 MB
我们需要多少带宽将司机的地点广播给用户？对于每个活跃司机，我们有五个订阅者，因此订阅者总数是：
5 * 500K => 2.5M
我们需要每秒将司机编号（3 个字节）和他们的地点（16 个字节）发送给所有的这些乘客，因此我们需要的带宽是：
2.5M * 19 bytes => 47.5 MB/s
我们如何高效地实现通知服务？我们可以使用 HTTP 长轮询或推送通知。
新发布者/司机如何被添加到一个当前用户？根据我们上文提出的方案，当乘客第一次打开 Uber 应用时，将订阅附近的司机。当一个新司机进入乘客正在查看的区域时会发生什么？为了动态添加新的乘客/司机订阅，我们需要追踪乘客正在查看的区域。这将使得我们的解决方案变得复杂。如果将推送信息改成客户端从服务器拉取信息会如何？
如果客户端从服务器拉取信息会如何？客户端可以发送它们的当前地点，服务器将从四叉树中找到所有附近的司机并将它们返回给客户端。当客户端接收到信息时，即可更新屏幕反映司机的当前地点。客户端可以每五秒查询一次以限制和服务器之间的往返。和上文描述的推送模型相比，这个解决方案看上去更简单。
我们是否需要在当一个网格达到上界时立即重新划分？我们可以有一个缓冲区，使得每个网格可以在我们决定重新划分之前增长到略超过上界。例如我们的网格可以在划分/合并之前增长/收缩到 10% 的比例。这应该能减少网格划分或合并高流量网格的负载。
「请求出行」的使用场景如何运作？
乘客发送出行的请求。
一台汇合服务器将接收请求并要求四叉树服务器返回附近的司机。
汇合服务器手机所有的结果并基于评分排序。
汇合服务器将同时给最靠前的（例如三个）司机发送通知，第一个接受请求的司机将被分配该出行。其他司机将收到取消请求。如果三个司机都没有恢复，汇合服务器将对列表中的后面三个司机请求出行。
当一个司机接受了请求时，乘客将被通知。
5. 容错和备份
如果一台司机地点服务器或通知服务器宕机了应该如何处理？我们需要这些服务器的备份，当主服务器宕机时，二级服务器可以获得控制。另外，我们可以将这些数据存放在一些永久存储中，例如可以提供快速输入输出的固态硬盘。这将确保当主服务器和二级服务器都宕机时，我们可以从永久存储中恢复数据。
6. 排名
如果我们将搜索结果排名时不只是考虑距离，还考虑流行度和相关性，应该怎么做？
我们如何返回给定半径内的评分最高的司机？假设我们在数据库和四叉树中跟踪每个司机的总评分。我们的系统中可以使用一个合计数表示流行度，例如一个司机在十颗星中能获得几颗星？当搜索给定半径内的最靠前的 10 个司机时，我们可以从四叉树的每个部分返回流行度最靠前的 10 个司机。然后汇合服务器可以在由不同部分返回的全部司机中决定最靠前的 10 个司机。
7. 高级问题
我们将如何处理网速慢和断网的客户端？
如果一个客户端在行程中时中断了连接应该如何处理？这样的场景下我们将如何处理计费？
如果客户端拉取所有的信息，和服务器总是推送信息相比会如何？
Last updated
