系统设计：Uber

系统设计

目录

让我们设计一个类似Uber的叫车服务，类似于Lyft、OLA Cabs等服务。

什么是 Uber？

Uber 是一家出行服务提供商，允许用户预订车辆和司机，类似出租车。Uber 提供网页端和 Android、iOS 等移动平台。

要求

我们的系统应满足以下要求：

功能要求

我们将为两种类型的用户设计我们的系统：客户和司机。

顾客

• 顾客应该能够看到附近所有出租车的预计到达时间和价格信息。
• 顾客应该能够预订前往目的地的出租车。
• 顾客应该能够看到司机的位置。

驱动程序

• 司机应该能够接受或拒绝顾客的乘车请求。
• 一旦司机接受行程，他们应该看到客户的接送地点。
• 司机到达目的地后应该能够将行程标记为完成。

非功能性需求

• 高可靠性。
• 高可用性和最小延迟。
• 该系统应具有可扩展性和高效性。

扩展要求

• 顾客可以在行程结束后对行程进行评分。
• 付款处理。
• 指标和分析。

估计和约束

让我们从估计和约束开始。

注意：请务必与面试官核对任何与规模或交通相关的假设。

交通

假设我们有 1 亿日活跃用户 (DAU) 和 100 万名司机，并且我们的平台平均每天可完成 1000 万次乘车。

如果平均每个用户执行 10 个操作（例如请求检查可用的乘车信息、票价、预订乘车等），我们每天将必须处理 10 亿个请求。

每天 10 亿个请求相当于每秒 12000 个请求。

如果我们假设每条消息平均为 400 字节，那么我们每天将需要大约 400 GB 的数据库存储空间。

由于我们的系统每天要处理 400 GB 的入口数据，因此我们需要每秒约 4 MB 的最低带宽。

以下是我们的高级估计：

数据模型设计

这是反映我们要求的通用数据模型。

我们有下表：

顾客

该表将包含客户的信息，例如name、email和其他详细信息。

司机

该表将包含驾驶员的信息，例如name、email和dob其他详细信息。

旅行

该表代表客户所进行的行程，并存储行程的source、、destination和等数据。status

出租车

该表存储了司机将要驾驶的出租车的注册号和类型（如 Uber Go、Uber XL 等）等数据。

评级

顾名思义，该表存储了行程的rating信息。feedback

付款

付款表包含与付款相关的数据及其相应的数据tripID。

我们应该使用什么样的数据库？

虽然我们的数据模型看起来相当相关，但我们不一定需要将所有内容存储在单个数据库中，因为这会限制我们的可扩展性并很快成为瓶颈。

我们将数据拆分到不同的服务，每个服务拥有特定表的所有权。然后，我们可以将关系数据库（例如PostgreSQL）或分布式 NoSQL 数据库（例如Apache Cassandra）用于我们的用例。

API 设计

让我们为我们的服务做一个基本的 API 设计：

叫车

通过此 API，客户将能够请求乘车。

requestRide(customerID: UUID, source: Tuple<float>, destination: Tuple<float>, cabType: Enum<string>, paymentMethod: Enum<string>): Ride

参数

客户 ID（UUID）：客户的 ID。

来源（Tuple<float>）：包含行程起始地点的纬度和经度的元组。

目的地（Tuple<float>）：包含行程目的地的纬度和经度的元组。

返回

结果（boolean）：表示操作是否成功。

取消行程

该 API 将允许客户取消行程。

cancelRide(customerID: UUID, reason?: string): boolean

参数

客户 ID（UUID）：客户的 ID。

原因（UUID）：取消行程的原因（可选）。

返回

结果（boolean）：表示操作是否成功。

接受或拒绝搭乘

该 API 将允许驾驶员接受或拒绝行程。

acceptRide(driverID: UUID, rideID: UUID): boolean
denyRide(driverID: UUID, rideID: UUID): boolean

参数

驾驶员 ID（UUID）：驾驶员的 ID。

乘车 ID ( UUID)：客户请求乘车的 ID。

返回

结果（boolean）：表示操作是否成功。

开始或结束行程

使用此 API，驾驶员将能够开始和结束行程。

startTrip(driverID: UUID, tripID: UUID): boolean
endTrip(driverID: UUID, tripID: UUID): boolean

参数

驾驶员 ID（UUID）：驾驶员的 ID。

行程 ID ( UUID)：请求行程的 ID。

返回

结果（boolean）：表示操作是否成功。

评价行程

该 API 将允许客户对行程进行评分。

rateTrip(customerID: UUID, tripID: UUID, rating: int, feedback?: string): boolean

参数

客户 ID（UUID）：客户的 ID。

行程 ID ( UUID)：已完成行程的 ID。

评分（int）：本次旅行的评分。

反馈（string）：客户对行程的反馈（可选）。

返回

结果（boolean）：表示操作是否成功。

高层设计

现在让我们对我们的系统进行高层设计。

建筑学

我们将使用微服务架构，因为它可以更轻松地水平扩展和解耦我们的服务。每个服务都拥有自己的数据模型。让我们尝试将系统划分为几个核心服务。

客户服务

该服务处理与客户相关的问题，例如身份验证和客户信息。

司机服务

该服务处理与驾驶员相关的问题，例如身份验证和驾驶员信息。

乘车服务

该服务将负责行程匹配和四叉树聚合。具体细节我们将另行讨论。

旅行服务

该服务处理我们系统中与旅行相关的功能。

支付服务

该服务将负责处理我们系统中的付款。

通知服务

该服务只会向用户发送推送通知。具体细节我们将另行讨论。

分析服务

该服务将用于指标和分析用例。

服务间通信和服务发现怎么样？

由于我们的架构基于微服务，因此服务之间也会相互通信。通常，REST 或 HTTP 的性能表现良好，但我们可以使用更轻量、更高效的gRPC进一步提升性能。

服务发现是我们需要考虑的另一件事。我们还可以使用服务网格，实现各个服务之间可管理、可观察且安全的通信。

注意：了解有关REST、GraphQL、gRPC 的更多信息以及它们之间的比较。

这项服务预计如何运作？

我们的服务预期将按以下方式运作：

1. 客户通过指定出发地、目的地、出租车类型、付款方式等来请求乘车。
2. 乘车服务注册此请求，查找附近的司机，并计算预计到达时间（ETA）。
3. 然后将请求广播给附近的司机，让他们接受或拒绝。
4. 如果司机接受，客户在等待接客时会收到有关司机实时位置和预计到达时间 (ETA) 的通知。
5. 乘客被接走后，司机可以开始行程。
6. 一旦到达目的地，司机将标记行程完成并收取费用。
7. 付款完成后，顾客可以根据自己的喜好对行程留下评分和反馈。

位置追踪

我们如何高效地从客户端（顾客和司机）向后端发送和接收实时位置数据？我们有两种选择：

拉动模型

客户端可以定期向服务器发送 HTTP 请求，报告其当前位置并接收预计到达时间和价格信息。这可以通过类似长轮询 的功能实现。

推模型

客户端与服务器建立长连接，一旦有新数据可用，就会将其推送到客户端。我们可以使用WebSocket或服务器发送事件 (SSE)来实现这一点。

拉取模型不可扩展，因为它会在我们的服务器上产生不必要的请求开销，并且大多数情况下响应都是空的，从而浪费我们的资源。为了最大限度地降低延迟，使用WebSocket的推送模型是更好的选择，因为这样，只要与客户端的连接处于打开状态，我们就可以立即将数据推送到客户端，而不会有任何延迟。此外，WebSocket 提供全双工通信，而服务器发送事件 (SSE)则只是单向的。

此外，客户端应用程序应该具有某种后台作业机制，以便在应用程序处于后台时 ping GPS 位置。

注意：了解有关长轮询、WebSockets、服务器发送事件（SSE）的更多信息。

行程匹配

我们需要一种高效存储和查询附近司机信息的方法。让我们探索一下可以融入设计的不同解决方案。

SQL

我们已经可以获取客户的经纬度，并且借助PostgreSQL和MySQL等数据库，我们可以执行查询，根据半径 (R) 内的经纬度 (X, Y) 查找附近的驾驶员位置。

SELECT * FROM locations WHERE lat BETWEEN X-R AND X+R AND long BETWEEN Y-R AND Y+R

然而，这是不可扩展的，并且在大型数据集上执行此查询会非常慢。

地理散列

地理散列是一种地理编码方法，用于将地理坐标（例如经纬度）编码为短的字母数字字符串。它由古斯塔沃·尼迈耶 (Gustavo Niemeyer)于 2008 年创建。

Geohash 是一种使用 Base-32 字母编码的分层空间索引，Geohash 中的第一个字符将初始位置标识为 32 个单元格之一。该单元格也包含 32 个单元格。这意味着，为了表示一个点，需要将世界递归地划分为越来越小的单元格，每个单元格的位数都增加，直到达到所需的精度。精度因子也决定了单元格的大小。

例如，坐标为 的旧金山37.7564, -122.4016在 geohash 中可以表示为9q8yy9mf。

现在，我们只需使用客户的 Geohash 与司机的 Geohash 进行比较，即可确定最近的可用司机。为了提高性能，我们会将司机的 Geohash 索引并存储在内存中，以便更快地检索。

四叉树

四叉树是一种树形数据结构，每个内部节点恰好有四个子节点。它们通常用于通过递归方式将二维空间细分为四个象限或区域来划分空间。每个子节点或叶节点都存储着空间信息。四叉树是八叉树的二维类似物，八叉树用于划分三维空间。

四叉树使我们能够有效地搜索二维范围内的点，其中这些点被定义为纬度/经度坐标或笛卡尔（x，y）坐标。

我们可以通过仅在某个阈值之后细分节点来节省进一步的计算。

四叉树似乎非常适合我们的用例，每次收到司机发来的位置更新时，我们都可以更新四叉树。为了减轻四叉树服务器的负载，我们可以使用Redis等内存数据存储来缓存最新更新。此外，通过应用希尔伯特曲线等映射算法，我们可以执行高效的范围查询，为客户找到附近的司机。

那么竞争条件又如何呢？

当大量乘客同时请求乘车时，很容易出现竞争条件。为了避免这种情况，我们可以将乘车匹配逻辑封装在互斥锁中，以避免任何竞争条件。此外，每个操作都应该具有事务性。

有关更多详细信息，请参阅事务和分布式事务。

如何找到附近最好的司机？

一旦我们从 Quadtree 服务器获得了附近的司机列表，我们就可以根据平均评分、相关性、过去客户反馈等参数进行某种排名。这将使我们能够首先向最佳可用的司机广播通知。

应对高需求

在需求旺盛的情况下，我们可以使用“峰时定价”的概念。峰时定价是一种动态定价方法，即为了应对需求增加和供应受限的情况，暂时提高价格。此峰时定价可以添加到行程的基本价格中。

欲了解更多详情，请了解Uber 的动态定价机制。

付款

处理大规模支付是一项挑战，为了简化我们的系统，我们可以使用Stripe或PayPal等第三方支付处理器。付款完成后，支付处理器会将用户重定向回我们的应用程序，我们可以设置一个webhook来捕获所有与付款相关的数据。

通知

推送通知将成为我们平台不可或缺的一部分。我们可以使用消息队列或消息代理（例如Apache Kafka）配合通知服务，将请求分发到Firebase 云消息传递 (FCM)或Apple 推送通知服务 (APNS)，后者负责将推送通知发送到用户设备。

有关更多详细信息，请参阅我们在其中讨论推送通知的Whatsapp系统设计。

详细设计

现在是时候详细讨论我们的设计决策了。

数据分区

要扩展数据库，我们需要对数据进行分区。水平分区（又称分片）是一个很好的第一步。我们可以基于现有的分区方案或区域对数据库进行分片。如果我们使用邮政编码等方式将位置划分为区域，就可以有效地将给定区域内的所有数据存储在固定节点上。但这仍然会导致数据和负载分布不均匀，我们可以使用一致性哈希来解决这个问题。

有关更多详细信息，请参阅分片和一致性哈希。

指标和分析

记录分析和指标是我们的扩展需求之一。我们可以从不同的服务中捕获数据，并使用Apache Spark（一个用于大规模数据处理的开源统一分析引擎）对数据进行分析。此外，我们可以将关键元数据存储在视图表中，以增加数据中的数据点。

缓存

在基于位置服务的平台中，缓存至关重要。我们必须能够缓存顾客和司机的近期位置，以便快速检索。我们可以使用Redis或Memcached等解决方案，但哪种缓存驱逐策略最适合我们的需求呢？

使用哪种缓存驱逐策略？

对我们的系统来说，最近最少使用（LRU）策略可能是一个不错的选择。在这个策略中，我们首先丢弃最近最少使用的键。

如何处理缓存未命中？

每当出现缓存未命中时，我们的服务器可以直接访问数据库并使用新条目更新缓存。

有关详细信息，请参阅缓存。

识别并解决瓶颈

让我们识别并解决设计中的单点故障等瓶颈：

• “如果我们的某项服务崩溃了怎么办？”
• “我们将如何在组件之间分配流量？”
• “我们如何才能减轻数据库的负载？”
• “如何提高我们的缓存的可用性？”
• “我们如何才能使我们的通知系统更加强大？”

为了使我们的系统更具弹性，我们可以执行以下操作：

• 运行我们每项服务的多个实例。
• 在客户端、服务器、数据库和缓存服务器之间引入负载平衡器。
• 为我们的数据库使用多个读取副本。
• 我们的分布式缓存有多个实例和副本。
• 在分布式系统中，精确一次传递和消息排序是一项挑战，我们可以使用专用消息代理（如Apache Kafka或NATS）来使我们的通知系统更加健壮。

本文是我在 Github 上提供的开源系统设计课程的一部分。