> For the complete documentation index, see [llms.txt](https://cnwangzhou.gitbook.io/grokking-system-design/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cnwangzhou.gitbook.io/grokking-system-design/ch15.md).

# 15. 设计票务大师

> **难度等级：困难**

让我们设计一个类似于「票务大师」或「预订我的节目」的卖电影票的在线订票系统。相似服务：bookmyshow\.com、ticketmaster.com。

## 1. 什么是在线电影票预订系统？

电影票预订系统给顾客提供了在线购买电影院座位的可能。电子票系统允许顾客随时随地浏览最近上映的电影并预订座位。

## 2. 系统的要求和目标

我们的订票服务应该满足以下要求：

### 功能性要求

1. 我们的订票服务应该可以列举开设附属电影院的不同城市。
2. 一旦用户选择了城市，服务应该显示在该特定城市发布的电影。
3. 一旦用户选择了电影，服务应该选择上映这部电影的电影院和有效的上映时间。
4. 用户应该可以选择一个电影院的特定上映并订票。
5. 服务应该可以给用户展示电影院大厅的座位安排。用户应该可以根据他们的喜好选择多个座位。
6. 用户应该可以区分空余的座位和已经被预订的座位。
7. 用户应该可以在支付和确认预订之前保留座位五分钟。
8. 当座位有机会变成空余时，用户应该可以等待，例如其他用户保留座位超出时限。
9. 等待的顾客应该得到公平地服务，先到先服务。

### 非功能性要求

1. 系统需要高度并发。在任何特定时刻都可能有对同一个座位的多个预订需求。服务应该优雅且公平地处理这种情况。
2. 这个服务的核心是订票，订票包含金融交易。这意味着系统应该安全，数据库应该遵循 ACID（原子性、一致性、隔离性、持久性）。

## 3. 设计需要考虑的方面

1. 为了简单起见，假设我们的服务不要求用户认证。
2. 系统将不会处理部分订票指令。用户或者得到他们想要的所有票，或者什么也不得到。
3. 公平性对于系统是必不可少的。
4. 为了避免滥用系统，我们可以限制用户依次最多预订十个座位。
5. 我们可以假设流量将会集中在流行/期待已久的电影发布的时候，座位将很快被预订完。系统应该是可测量且高度可用的，可以应对流量的急剧增加。

## 4. 容量估算

**流量估算**：假设我们的服务每个月有 30 亿页面浏览，一个月卖出 1000 万张票。

**存储估算**：假设我们有 500 个城市，平均每个城市有 10 个电影院。假设每个电影院有 2000 个座位，每天有两次上映。

假设每个座位预订需要在数据库中使用 50 个字节存储（编号、座位数、上映编号、电影编号、座位编号、座位状态、时间戳等）。我们也需要存储关于电影和电影院的信息，假设需要 50 个字节。因此，存储一天内所有城市中的所有电影院中的所有上映信息需要的空间是：

500 cities \* 10 cinemas \* 2000 seats \* 2 shows \* (50+50) bytes = 2GB / day

存储五年的数据，我们将需要大约 3.6TB。

## 5. 系统 API

我们可以使用 SOAP 或 REST API 将我们的服务的函数公开。以下为搜索电影上映和预订座位的 API 的定义：

```
SearchMovies(api_dev_key, keyword, city, lat_long, radius, start_datetime, end_datetime, postal_code, includeSpellcheck, results_per_page, sorting_order)
```

**参数**： api\_dev\_key（string）：一个已注册的帐号的 API 开发者关键字。关键字将和其他字段一起根据用户分配的额度限制用户。 keyword（string）：查询的关键字。 city（string）：用于过滤电影的城市。 lat\_long（string）：用于过滤的纬度和经度。 radius（number）：我们想搜索事件的区域半径。 start\_datetime（string）：根据开始时间过滤电影。 end\_datetime（string）：根据结束时间过滤电影。 postal\_code（string）：根据邮政编码过滤电影。 includeSpellcheck（枚举值：「是」或「否」）：如果选择是，则在响应中包括拼写检查建议。 results\_per\_page（number）：每页返回的结果数。最大值是 30。 sorting\_order（string）：搜索结果的排序顺序。一些允许的值包括：‘name,asc’、‘name,desc’、‘date,asc’、‘date,desc’、‘distance,asc’、‘name,date,asc’、‘name,date,desc’、‘date,name,asc’、‘date,name,desc’。

**返回**：（JSON） 以下是一个包含电影和上映的样例列表：

```
[
    {
        "MovieID": 1,
        "ShowID": 1,
        "Title": "Cars 2",
        "Description": "About cars",
        "Duration": 120,
        "Genre": "Animation",
        "Language": "English",
        "ReleaseDate": "8th Oct. 2014",
        "Country": USA,
        "StartTime": "14:00",
        "EndTime": "16:00",
        "Seats":
        [
            {
                "Type": "Regular"
                "Price": 14.99
                "Status: "Almost Full"
            },
            {
                "Type": "Premium"
                "Price": 24.99
                "Status: "Available"
            }
        ]
    },
    {
        "MovieID": 1,
        "ShowID": 2,
        "Title": "Cars 2",
        "Description": "About cars",
        "Duration": 120,
        "Genre": "Animation",
        "Language": "English",
        "ReleaseDate": "8th Oct. 2014",
        "Country": USA,
        "StartTime": "16:30",
        "EndTime": "18:30",
        "Seats":
        [
            {
                "Type": "Regular"
                "Price": 14.99
                "Status: "Full"
            },
            {
                "Type": "Premium"
                "Price": 24.99
                "Status: "Almost Full"
            }
        ]
    },
]
```

```
ReserveSeats(api_dev_key, session_id, movie_id, show_id, seats_to_reserve[])
```

**参数**： api\_dev\_key（string）：同上。 session\_id（string）：用于跟踪预订的用户的会话编号。一旦预定时间过期，将使用该编号移除该服务器上的用户预订。 movie\_id（string）：预订的电影。 show\_id（string）：预订的上映。 seats\_to\_reserve（number）：一个数组，包含预订的座位编号。

**返回**：（JSON） 返回预订的状态，是以下结果之一：1. 「预订成功」；2. 「预订失败——上映已预订满」；3. 「预订失败——重试，其他用户正保留预订的座位」。

## 6. 数据库设计

以下是关于我们将要存储的数据的一些观察：

1. 每个城市可以有多个电影院。
2. 每个电影院将有多个大厅。
3. 每个电影将有多次上映，每次上映将有多个预订。
4. 一个用户可以有多个预订。

![](https://3100185414-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FgozhSDAYrrQ6G5G7iYxs%2Fuploads%2Fgit-blob-0a887b701de6aaf1089533ca38d28de2e3291eb4%2Fch15_1.png?alt=media)

## 7. 高阶设计

告诫角度，我们的网络服务器将管理用户的会话，应用服务器将处理所有的票务管理、将数据存入数据库以及和缓存服务器一同工作，处理预订。

![](https://3100185414-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FgozhSDAYrrQ6G5G7iYxs%2Fuploads%2Fgit-blob-189bfb652e6e1ae1f6c58d31145766c05a115544%2Fch15_2.png?alt=media)

## 8. 部件设计细节

首先，我们在假设只有一台服务器的情况下尝试建立我们的服务。

**订票工作流**：以下是典型的订票工作流：

1. 用户搜索一个电影。
2. 用户选择一个电影。
3. 该电影的有效上映展示给用户。
4. 用户选择一次上映。
5. 用户选择要预订的座位数。
6. 如果要求数量的座位有效，则将电影院的地图展示给用户，由用户选择座位。否则，继续执行第 8 步。
7. 一旦用户选择了座位，系统将尝试预订选定的座位。
8. 如果不能预订座位，我们有以下选项：
   * 上映已预订满，给用户展示错误信息。
   * 用户想要预订的座位不再空余，但是有其他空余的座位，因此将用户带回电影院的地图选择不同的座位。
   * 没有空余的座位可以预订，但是并非所有的座位都被订票，由于有些座位是其他用户保留在预订池中尚未订票的。用户将被带到等待页面，用户可以在等待页面等待，直到需要的座位从预订池中开放。等待可能有以下结果：
     * 如果需要数量的座位变成有效，用户被带到电影院的地图页面，在这里用户可以选择座位。
     * 等待过程中，如果所有的座位被预订或者预订池中的座位数少于用户想要预订的座位数，则将错误信息展示给用户。
     * 用户取消等待，被带回电影搜索页面。
     * 用户最多可以等待一小时，在此之后用户的会话超时，用户被带回电影搜索页面。
9. 如果座位成功预订，则用户有五分钟的时间支付预订。支付之后，订票标记为完成。如果用户不能在五分钟内完成支付，则所有预订的座位被清空，向其他用户开放。

![](https://3100185414-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FgozhSDAYrrQ6G5G7iYxs%2Fuploads%2Fgit-blob-53a750384e002022730ac0d204bbb24f643c7f78%2Fch15_3.png?alt=media)

![](https://3100185414-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FgozhSDAYrrQ6G5G7iYxs%2Fuploads%2Fgit-blob-23df303bc73cd60b7c8bc21c57e4f9de76415252%2Fch15_4.png?alt=media)

![](https://3100185414-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FgozhSDAYrrQ6G5G7iYxs%2Fuploads%2Fgit-blob-9defff024d78c0141b01df8b4337721760090012%2Fch15_5.png?alt=media)

![](https://3100185414-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FgozhSDAYrrQ6G5G7iYxs%2Fuploads%2Fgit-blob-1a535cacc5d57df622253f8f89368c1f8c722322%2Fch15_6.png?alt=media)

![](https://3100185414-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FgozhSDAYrrQ6G5G7iYxs%2Fuploads%2Fgit-blob-37ed83077eff48665a910d65c4814cd523d0cfd7%2Fch15_7.png?alt=media)

![](https://3100185414-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FgozhSDAYrrQ6G5G7iYxs%2Fuploads%2Fgit-blob-b73c207b32e1329c59578929621bb646accd1ba1%2Fch15_8.png?alt=media)

![](https://3100185414-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FgozhSDAYrrQ6G5G7iYxs%2Fuploads%2Fgit-blob-44cbb66ede15be27cbfd889f8e95a40b27e4bf38%2Fch15_9.png?alt=media)

![](https://3100185414-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FgozhSDAYrrQ6G5G7iYxs%2Fuploads%2Fgit-blob-4ceed3556247068f7a8e20898a97d822d38ee93e%2Fch15_10.png?alt=media)

**服务器将如何跟踪所有尚未订票的活跃的预订**？**以及服务器将如何跟踪所有等待的顾客**？

我们需要两个守护服务。其中一个跟踪所有活跃的预订，并从系统中移除所有过期的预订，这个服务称为**活跃预订服务**。另一个服务跟踪所有等待用户的请求，并在想要预订的数量的座位变成有效的瞬间通知（等待时间最长的）用户选择座位，这个服务称为**等待用户服务**。

### a. 活跃预订服务

除了将所有数据存入数据库以外，我们可以将一次上映的所有预订存放在内存中，使用类似于 [LinkedHashMap](https://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html) 或 [TreeMap](https://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html) 的数据结构。我们将需要一个类似于 LinkedHashMap 的数据结构以允许我们跳到任何预订，当订票结束时移除该预订。而且，由于每个预订都有过期时间，哈希映射的头部总是指向最老的预订记录，当超过时间限制时该预订就能过期。

为了存储每次上映的每个预订，我们可以使用哈希表，哈希表的关键字是上映编号，值是包含订票编号和创建时间戳的 LinkedHashMap。

数据库中，我们将预订信息存入 Booking 表，过期时间在 Timestamp 列。Status 字段将有一个值「Reserved (1)」，一旦订票完成，系统将 Status 字段的值更新为「Booked (2)」并将预订记录从相关上映的 LinkedHashMap 中移除。当预订过期时，除了从内存中移除预订，我们可以将其从 Booking 表删除或者将其标为「Expired (3)」。

活跃预订服务也将和外部的金融服务共同工作以处理用户支付。任何时候当订票完成或预订过期时，等待用户服务将获得一个信号，此时任何等待的顾客可以被处理。

| Key:    | Value                                               |
| ------- | --------------------------------------------------- |
| ShowID: | LinkedHashMap\\                                     |
| 123:    | {{1, 1499818500}, {2, 1499818700}, {3, 1499818800}} |

### b. 等待用户服务

和活跃预订服务一样，我们可以将所有等待的用户存放在内存中，使用 LinkedHashMap 或 TreeMap。我们需要一个类似于 LinkedHashMap 的数据结构以允许我们跳到任何用户，当用户取消请求时移除该用户。而且，由于我们按照先到先服务的规则服务用户，哈希映射的头部总是指向等待时间最长的用户，因此任何时候当有座位变成空余时，我们可以公平地服务用户。

我们将有一个哈希表存储每次上映的所有等待用户。哈希表的关键字是上映编号，值是包含用户编号和开始等待时间的 LinkedHashMap。

客户端可以使用[长轮询](https://en.wikipedia.org/wiki/Push_technology#Long_polling)保持被更新到最新的预订状态。任何时候当座位变成空余，服务器可以使用该请求通知用户。

**预订过期**

服务器上，活跃预订服务跟踪活跃预订的过期（基于预订时间）。由于客户端将被展示一个计时器（表示过期时间），可能和服务器不完全同步，我们可以在服务器上增加五秒的缓冲以避免不好的体验，使得客户端永远不会在服务器之后过期，避免成功的购买。

## 9. 并发

**如何处理并发使得不允许两个用户预订同一个座位**。我们可以使用 SQL 数据库中的事务避免任何冲突。例如，如果我们使用 SQL 服务器，我们可以利用[事务隔离级别](https://docs.microsoft.com/en-us/sql/odbc/reference/develop-app/transaction-isolation-levels)，在更新行数据之前锁定行。以下是样例代码：

```
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

BEGIN TRANSACTION;

	-- Suppose we intend to reserve three seats (IDs: 54, 55, 56) for ShowID=99
	Select * From Show_Seat where ShowID=99 && ShowSeatID in (54, 55, 56) && Status=0 -- free

	-- if the number of rows returned by the above statement is three, we can update to
	-- return success otherwise return failure to the user.
	update Show_Seat ...
	update Booking ...

COMMIT TRANSACTION;
```

串行化是最高的隔离级别，保证安全，避免[脏读](https://en.wikipedia.org/wiki/Isolation_\(database_systems\)#Dirty_reads)、[不可重复读](https://en.wikipedia.org/wiki/Isolation_\(database_systems\)#Non-repeatable_reads)和[幻读](https://en.wikipedia.org/wiki/Isolation_\(database_systems\)#Phantom_reads)。这里需要说明的一点是，在一个事务中，如果我们按行读取，我们在读取的行上加行锁，使得其他任何人都不能更新这些行。

一旦上述数据库事务成功，我们可以开始跟踪活跃预订服务中的预订。

## 10. 容错

**如果活跃预订服务或等待用户服务宕机了，应该如何处理**？

任何时候当活跃预订服务宕机时，我们可以从 Booking 表读取所有的活跃预订。回想我们将 Status 列的值维持「Reserved (1)」，直到一个预订的订票完成。另一个选项是使用主从配置，使得当主机宕机时，二级服务器可以接手。我们不将等待的用户存在数据库中，因此当等待用户服务宕机时，我们没有任何理由复原数据，除非我们有主从设置。

类似地，我们可以对数据库使用主从设置，达到容错的目的。

## 11. 数据分块

**数据库分块**:如果我们基于电影编号分块，则一部电影的所有上映都将在同一台服务器上。对于一部非常热门的电影，将会导致这台服务器上有大量的负载。一个更好的方法是基于上映编号分块，使用这种方法，负载可以在不同的服务器之间分布。

**活跃预订服务和等待用户服务分块**：我们的网络服务器将管理所有活跃用户的会话并处理这些用户的所有交流。我们可以使用一致性哈希，基于上映编号对活跃预订服务和等待用户服务分配应用服务器。使用这种方法，一次特定上映的所有预订和等待的用户将由特定的服务器处理。对于负载均衡，假设我们的[一致性哈希](https://www.educative.io/collection/page/5668639101419520/5649050225344512/5709068098338816)为任何上映分配三台服务器，因此任何时候当预订过期时，包含该预订的服务器将做以下事情：

1. 更新数据库，将订票移除（或标记为过期）并在 Show\_Seat 表中更新座位的 Status 字段。
2. 从 LinkedHashMap 中移除预订。
3. 通知用户预订过期。
4. 给所有的包含等待该次上映的用户的等待用户服务服务器广播消息，找到等待时间最长的用户。一致性哈希方案将反映哪些服务器有这些用户。
5. 给包含等待时间最长的用户的等待用户服务服务器发送消息，如果想要的座位变成空余则处理请求。

任何时候当预订成功时，将发生以下事情：

1. 包含预订的服务器给所有包含等待该次上映的用户的服务器发送消息，使得那些服务器可以将所有想要预订座位数超过空余座位数的用户设为过期。
2. 当收到上述消息时，所有包含等待用户的服务器将查询数据库，得到现在还有多少空余座位。使用一个数据库缓存有很大的好处，只要运行查询一次。
3. 将所有想要预订座位数超过空余座位数的用户设为过期。对此，等待用户服务必须遍历所有等待用户的 LinkedHashMap。