需求
设计Uber后端，让我们设计一个像优步这样的共享乘车服务，将需要乘车的乘客与有车的司机连接起来。类似服务：Lyft、滴滴、Via、Sidecar等。
难度等级：难，基于附近人或者搜索服务前提进行设计
1.什么是优步？
Uber使其客户能够为出租车司机预订服务。优步司机用他们的私家车载着顾客四处转悠。客户和司机都使用优步应用程序通过智能手机相互交流。
2.系统的要求和目标
让我们从构建一个更简单的Uber版本开始。
我们的系统中有两种用户：1）司机2）客户。
•司机需要定期通知服务部门他们的当前位置以及他们是否可以接送乘客。
•乘客可以看到附近所有可用的司机。
•客户可以要求乘车；附近的司机会被告知一位顾客已准备好被提货向上的
•一旦司机和客户接受乘坐，他们就可以不断看到对方的当前位置直到旅行结束。
•到达目的地后，司机会标记行程完成，以供乘客使用下一程。
3.容量估算和限制
•假设我们有3亿客户和100万司机，每天有100万活跃客户和500万活跃司机。
假设每天乘坐100万次。
•假设所有活动驾驶员每三秒通知一次当前位置。
•一旦客户提出乘车请求，系统应能够实时联系驾驶员-时间
4.基本系统设计和算法
我们将采用设计Yelp时讨论的解决方案，并对其进行修改，使其适用于上述“优步”用例。我们最大的不同是，我们的四叉树并没有在构建时考虑到它会经常更新。因此，我们的动态网格解决方案有两个问题：
•由于所有活跃驾驶员每三秒报告一次位置，我们需要更新数据结构以反映这一点。如果我们必须为驾驶员位置的每次变化更新四叉树，这将需要大量的时间和资源。要将驱动程序更新到其新位置，我们必须根据驱动程序以前的位置找到正确的网格。如果新位置不属于当前网格，我们必须从当前网格中删除驱动程序，并将用户移动/重新插入正确的网格。在这次移动之后，如果新的网格达到了驱动程序的最大限制，我们必须重新划分它。
•我们需要有一个快速机制，将附近所有司机的当前位置传播给该地区的任何活跃客户。此外，在骑行过程中，我们的系统需要通知驾驶员和乘客汽车的当前位置。
虽然我们的四叉树帮助我们快速找到附近的驱动程序，但不能保证树中的快速更新。
每次司机报告他们的位置时，我们需要修改我们的四叉树吗？
如果我们不使用驱动程序的每次更新更新更新我们的四叉树，它将有一些旧数据，并且不会正确反映驱动程序的当前位置。如果你还记得，我们构建四叉树的目的是高效地找到附近的司机（或地点）。由于所有活动的驱动程序每三秒报告一次他们的位置，因此我们的树上发生的更新比查询附近的驱动程序要多得多。那么，如果我们将所有驱动程序报告的最新位置保存在一个哈希表中，并稍微减少更新四叉树的频率，会怎么样？假设我们保证驾驶员的当前位置将在15秒内反映在四叉树中。同时，我们将维护一个哈希表，存储司机报告的当前位置；我们把这个叫做DriverLocationHT。
DriverLocationHT需要多少内存？
我们需要在哈希表中存储DriveID，以及它们的当前和旧位置。因此，我们总共需要35个字节来存储一条记录：
1.DriverID（3字节-100万个驱动程序）2。旧纬度（8字节）
3.旧经度（8字节）
4.新纬度（8字节）
5.新经度（8字节）总计=35字节
如果我们总共有100万个驱动程序，我们需要以下内存（忽略哈希表开销）：
1 million * 35 bytes => 35 MB
我们的服务将消耗多少带宽来接收来自所有驱动程序的位置更新？
如果我们得到DriverID和它们的位置，它将是（3 16=>19字节）。如果我们每三秒收到一百万个驱动程序的信息，我们将每三秒获得19MB。
我们需要将DriverLocationHT分发到多个服务器上吗？
虽然我们的内存和带宽需求不需要这样做，因为所有这些信息都可以轻松地存储在一台服务器上，但为了实现可扩展性、性能和容错性，我们应该将DriverLocationHT分发到多台服务器上。我们可以基于DriverID进行分布，使分布完全随机。让我们把持有DriverLocation的机器称为Driver Location server。除了存储驱动程序的位置，这些服务器中的每一个都将做两件事：
1.一旦服务器接收到驾驶员位置的更新，他们将向所有感兴趣的客户广播该信息。
2.服务器需要通知相应的四叉树服务器以刷新驱动程序的位置。如上所述，这可能每10秒发生一次。
我们如何有效地向客户广播驾驶员的位置？
我们可以有一个推送模型，服务器会将位置推送给所有相关用户。我们可以提供专门的通知服务，向所有感兴趣的客户广播司机的当前位置。我们可以在发布者/订阅者模型上构建通知服务。当客户在手机上打开Uber应用程序时，他们会查询服务器以查找附近的司机。在服务器端，在将驱动程序列表返回给客户之前，我们将向客户订阅这些驱动程序的所有更新。我们可以维护一个客户（订阅者）列表，这些客户（订阅者）有兴趣知道某个驱动程序的位置，每当我们更新该驱动程序的DriverLocationHT时，我们都可以向所有订阅的客户广播该驱动程序的当前位置。这样，我们的系统确保我们总是向客户显示驾驶员的当前位置。
我们需要多少内存来存储所有这些订阅？
如上所述，我们将拥有100万日常活跃客户和50万日常活跃司机。假设平均有五个客户订阅了一个驱动程序。假设我们将所有这些信息存储在一个哈希表中，以便有效地更新它。我们需要存储驱动程序和客户ID来维护订阅。假设DriverID需要3字节，CustomerID需要8字节，那么我们需要21MB的内存。
(500K * 3) (500K * 5 * 8 ) ~= 21 MB
我们需要多少带宽才能向客户广播司机的位置？
对于每个活动驱动程序，我们有五个订户，因此我们的订户总数为：
5*500K=>2.5M
对于所有这些客户，我们需要每秒发送DriverID（3字节）及其位置（16字节），因此，我们需要以下带宽：
2.5M * 19 bytes => 47.5 MB/s
我们如何高效地实现通知服务？我们可以使用HTTP长轮询或推送通知。
如何为当前客户添加新的发布者/驱动程序？
正如我们上面所建议的，当客户第一次打开Uber应用时，他们会订阅附近的司机，当新司机进入客户正在查看的区域时会发生什么？要动态添加新的客户/驱动订阅，我们需要跟踪客户关注的区域。这将使我们的解决方案变得复杂；
如果客户机不推送这些信息，而是从服务器上提取信息，那又如何？
如果客户端从服务器上获取有关附近司机的信息呢？
客户端可以发送当前位置，服务器将从四叉树中找到所有附近的驱动程序，并将它们返回给客户端。收到此信息后，客户可以更新其屏幕以反映驾驶员的当前位置。客户端可以每五秒钟查询一次，以限制到服务器的往返次数。与上述推送模式相比，该解决方案看起来更简单。
我们是否需要在网格达到最大限制时重新划分网格？
在我们决定划分网格之前，我们可以有一个缓冲区，让每个网格的大小超出限制。假设我们的网格在分割/合并之前可以额外增长/收缩10%。这将减少网格分区或在高流量网格上合并的负载。
“请求骑行”用例将如何工作？
1.客户将提出乘车请求。
2.其中一个聚合服务器将接收请求，并要求四叉树服务器返回附近司机。
3.聚合器服务器收集所有结果，并按评级对其进行排序。
4.聚合器服务器将同时向顶级（比如三个）驱动程序发送通知，
无论哪个驾驶员首先接受请求，都将被分配乘坐。其他驾驶员将收到取消请求。如果这三名司机都没有回应，聚合器将请求列表中接下来的三名司机搭车。
5.一旦驾驶员接受请求，就会通知客户。
5.容错和复制
如果驱动程序位置服务器或通知服务器死亡怎么办？我们需要这些服务器的副本，这样，如果主服务器死亡，辅助服务器就可以控制。此外，我们可以将这些数据存储在一些持久性存储中，比如SSD，它可以提供快速的IOs；这将确保如果主服务器和辅助服务器都死掉，我们可以从持久存储中恢复数据。
6.排名
如果我们不仅要根据接近程度，还要根据受欢迎程度或相关性对搜索结果进行排名，那该怎么办？
我们如何在给定的半径范围内返回顶级司机？假设我们跟踪数据库和四叉树中每个驱动程序的总体评级。在我们的系统中，一个总的数字可以代表这种受欢迎程度，例如，一个司机从十颗星中得到多少颗星？在搜索给定半径内的前10个驱动程序时，我们可以要求四叉树的每个分区返回具有最大评级的前10个驱动程序。然后，聚合服务器可以确定不同分区返回的所有驱动程序中的前10个驱动程序。
7.高级问题
1.我们将如何处理慢速网络和断开网络上的客户端？
2.如果客户在乘车时断开连接怎么办？我们将如何处理账单这样的情况？
3.如果客户端获取所有信息，而服务器总是推送信息，那又如何？
参考资料
grok_system_design_interview.pdf
