Yelp计划明年提供更多本地团购服务或进行IPO
06-18
需求设计 Uber后端，让我们设计一个像Uber一样的共享乘车服务，将需要乘车的乘客与有车的司机联系起来。类似服务：Lyft、滴滴、Via、Sidecar等。
难度：难，基于附近的人或搜索服务前提设计 1.什么是Uber？优步允许其客户向出租车司机预订服务。优步司机开着他们的私家车载着顾客到处走走。
顾客和司机都使用 Uber 应用程序通过智能手机相互沟通。 2. 系统要求和目标 让我们从构建一个更简单的 Uber 版本开始。
我们的系统中有两种类型的用户：1）司机2）客户。 ?司机必须定期通知服务人员其当前位置以及是否可以接送乘客。
?乘客可以看到附近所有可用的司机。 ? 客户可以叫车；附近的司机会收到有关已准备好接载顾客的通知。
? 一旦司机和顾客接受乘车，他们就可以持续看到彼此的当前位置，直到行程完成。 ?到达目的地后，司机会将行程标记为完成，以便乘客下次乘车时使用。
3. 容量估算和限制 ? 假设我们每天有3 亿客户和10,000 名司机，以及10,000 名活跃客户和10,000 名活跃司机。假设每天有 10,000 次骑行。
?假设所有活跃驾驶员每三秒通知一次他们当前的位置。 ? 一旦客户提出乘车请求，系统应该能够实时联系司机 - 时间 4. 基本系统设计和算法 我们将采用设计 Yelp 时讨论的解决方案并对其进行修改，使其适合“Uber”如上所述用例。
我们最大的区别是，我们的四叉树在构建时并没有考虑到它会经常更新。因此，我们的动态网格解决方案存在两个问题： ? 由于所有活动驾驶员每三秒报告一次其位置，因此我们需要更新数据结构以反映这一点。
如果我们必须针对驾驶员位置的每次变化来更新四叉树，这将需要大量的时间和资源。要将驱动程序更新到新位置，我们必须根据驱动程序之前的位置找到正确的网格。
如果新位置不属于当前网格，我们必须从当前网格中删除驱动程序并将用户移动/重新插入到正确的网格。在此移动之后，如果新的网格达到驱动程序的最大限制，我们必须重新绘制它。
?我们需要有一个快速机制，将所有附近司机的当前位置传播给该地区的任何活跃客户。此外，在骑行时，我们的系统需要告知驾驶员和乘客汽车的当前位置。
虽然我们的四叉树可以帮助我们快速找到附近的驱动程序，但它并不能保证树中的快速更新。每次司机报告其位置时，我们是否都需要修改我们的四叉树？如果我们不在每次更新驱动程序时更新四叉树，它将包含一些旧数据，并且无法正确反映驱动程序的当前位置。
如果您还记得的话，构建四叉树的目的是有效地找到附近的驱动程序（或地点）。由于所有活动驱动程序每三秒报告一次其位置，因此我们的树上发生的更新比查询附近的驱动程序要多得多。
那么，如果我们将所有驱动程序报告的最新位置保留在哈希表中并稍微减少四叉树的更新频率，会怎么样呢？假设我们保证驾驶员的当前位置将在 15 秒内反映在四叉树中。同时，我们会维护一个哈希表，存储驱动程序报告的当前位置；我们称之为 DriverLocationHT。
DriverLocationHT 需要多少内存？我们需要将 DriveID 及其当前和旧位置存储在哈希表中。因此，我们总共需要 35 个字节来存储一条记录： 1. DriverID（3 个字节 - 一万个驱动程序） 2. 旧纬度（8 字节） 3. 旧经度（8 字节） 4. 新纬度（8 字节） 5新经度（8 字节） 总计 = 35 字节 如果我们总共有一万个驱动程序，我们需要以下内存（忽略哈希表开销）： 100 万 * 35 字节 => 35 MB 我们的服务将消耗多少带宽来接收所有司机的位置更新？如果我们获得 DriverID 及其位置，它将是（3 =>?? 19 字节）。
如果我们每三秒收到一百万条驱动程序消息，那么每三秒我们将获得 19MB。我们需要将DriverLocationHT分发到多个服务器吗？虽然我们的内存和带宽需求不需要这样做，因为所有这些信息都可以轻松存储在一台服务器上，但为了可扩展性、性能和容错能力，我们应该将 DriverLocationHT 分布在多个服务器上。
我们可以根据DriverID进行分发，使分发完全随机。让我们将持有 DriverLocation 的机器称为 Driver Location 服务器。
除了存储驾驶员的位置之外，每个服务器还将执行两件事： 1. 一旦服务器收到驾驶员位置的更新，它们就会将该信息广播给所有感兴趣的客户端。 2. 服务器需要通知对应的四叉树服务器刷新驱动程序的位置。
如上所述，这可能每 10 秒发生一次。如何有效地将司机的位置广播给客户？我们可以有一个推送模型，服务器将位置推送给所有相关用户。
我们可以提供专门的通知服务，向所有感兴趣的客户广播驾驶员的当前位置。我们可以在发布者/订阅者模型上构建通知服务。
当客户在手机上打开 Uber 应用程序时，他们会查询服务器以查找附近的司机。在服务器端，我们将在将驱动程序列表返回给客户端之前向客户端订阅这些驱动程序的所有更新。
我们可以维护一个有兴趣了解某个驱动程序位置的客户端（订阅者）列表，每当我们更新该驱动程序的 DriverLocationHT 时，我们就可以将该驱动程序广播到所有订阅客户端的当前位置。这样，我们的系统可确保始终向客户显示驾驶员的当前位置。
我们需要多少内存来存储所有这些订阅？如上所述，我们将拥有 10,000 名日活跃客户和 500,000 名日活跃司机。假设平均有 5 位客户订阅了一名司机。
假设我们将所有这些信息存储在哈希表中，以便我们可以有效地更新它。我们需要存储司机和客户 ID 来维护订阅。
假设DriverID需要3个字节，CustomerID需要8个字节，那么我们需要21MB的内存。 (K * 3) + (K * 5 * 8 ) ~= 21 MB 我们需要多少带宽来向客户端广播驾驶员的位置？对于每个活动驱动程序，我们有 5 个订阅者，因此我们的订阅者总数为： 5*K => 2.5M 对于所有这些客户端，我们需要每秒发送 DriverID（3 字节）及其位置（16 字节），因此，我们需要如下带宽： 2.5M * 19 bytes => 47.5 MB/s 如何高效地实现通知服务？我们可以使用 HTTP 长轮询或推送通知。
如何为当前客户添加新的发布者/驱动程序？正如我们上面所建议的，当客户第一次打开 Uber 应用程序时，他们会订阅附近的司机，当新司机进入客户正在查看的区域时会发生什么？为了动态添加新客户/驱动订阅，我们需要跟踪客户关注的领域。这会使我们的解决方案变得复杂；那么如果客户端不推送这些信息，而是从服务器拉取信息呢？如果客户端从服务器获取有关附近驱动程序的信息怎么办？客户端可以发送当前位置，服务器将从四叉树中找到所有附近的驱动程序并将其返回给客户端。
收到此信息后，客户可以更新屏幕以反映驾驶员的当前位置。客户端可以每五秒查询一次，以限制到服务器的往返次数。
与上面提到的推送模型相比，这个解决方案看起来更简单。当网格达到最大限制时，我们是否需要重新划分网格？我们可以有一个缓冲区，允许每个网格在我们决定对其进行网格划分之前超过大小限制。
假设我们的网格在分割/合并之前可以额外增长/收缩 10%。这将减少高流量网格上的网格分区或组合负载。
“叫车”用例将如何运作？ 1. 顾客提出乘车请求。 2. 聚合服务器之一将收到请求并要求四叉树服务器返回附近的驱动程序。
3. 聚合器服务器收集所有结果并按评级对它们进行排序。 4. 聚合器服务器将同时向排名靠前（例如三个）的司机发送通知，首先接受请求的司机将被分配行程。
其他司机将收到取消请求。如果这三名司机都没有回应，聚合商将要求列表中接下来的三名司机搭车。
5. 一旦司机接受请求，顾客就会收到通知。 5. 容错和复制 如果驱动程序位置服务器或通知服务器死机了怎么办？我们需要这些服务器的副本，以便如果主服务器挂掉，辅助服务器可以接管控制权。
此外，我们可以将这些数据存储在一些持久存储中，例如SSD，它可以提供快速的IO；这将确保如果主服务器和辅助服务器都死掉，我们可以从持久存储中恢复数据。 6. 排名 如果我们不仅要根据邻近度，还要根据流行度或相关性对搜索结果进行排名，该怎么办？如何才能返回给定半径内的顶级司机呢？假设我们在数据库和四叉树中跟踪每个驾驶员的总体评分。
在我们的系统中，一个总数可以代表这个受欢迎程度，例如，一个司机在十颗星中得到多少颗星？当搜索给定半径内的前 10 个司机时，我们可以要求四叉树的每个分区返回评分最高的前 10 个司机。然后，聚合服务器可以确定不同分区返回的所有驱动程序中的前 10 个驱动程序。
版权声明：本文内容由互联网用户自发贡献，本站不拥有所有权，不承担相关法律责任。如果发现本站有涉嫌抄袭的内容，欢迎发送邮件 举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。
标签：
相关文章
06-18
06-17
06-17
06-18
06-06
06-18
06-21
06-06
最新文章
【玩转GPU】ControlNet初学者生存指南
【实战】获取小程序中用户的城市信息（附源码）
包雪雪简单介绍Vue.js：开学
Go进阶：使用Gin框架简单实现服务端渲染
线程池介绍及实际案例分享
JMeter 注释 18 - JMeter 常用配置组件介绍
基于Sentry的大数据权限解决方案
【云+社区年度征文集】GPE监控介绍及使用