需求
让我们设计一个在线售票系统，销售Ticketmaster或BookMyShow等电影票。
类似服务：bookmyshow.com，ticketmaster.com
难度等级：难
1.什么是在线电影票预订系统？
电影票预订系统为其客户提供了在线购买影院座位的能力。Eticketing系统允许客户浏览当前正在播放的电影并预订座位，随时随地。
2.系统的要求和目标
我们的订票服务应满足以下要求：
功能要求：
1.我们的订票服务应该能够列出其附属影院所在的不同城市位于。
2.一旦用户选择城市，服务应显示该特定城市发布的电影城市
3.一旦用户选择了一部电影，该服务应显示运行该电影的电影院及其可用的演出时间。
4.用户应该能够在特定电影院选择一场演出并预订门票。
5.服务应能向用户展示电影院大厅的座位安排。这个用户应该能够根据自己的喜好选择多个座位。
6.用户应该能够区分可用座位和预定座位。
7.用户应该能够在向用户付款之前，在座位上停留五分钟完成预订。
8.如果座位有可能可用，用户应该能够等待，例如：当其他用户的保留过期时。
9.等待的客户应以公平、先到先得的方式进行服务。
非功能性需求：
1.系统需要高度并发。将有多个预订请求在任何特定时间点都是同一个座位。服务应该优雅而公平地处理这个问题。
2.这项服务的核心是订票，即金融交易。这意味着系统应该是安全的，数据库符合ACID。
3.一些设计考虑
1.为了简单起见，假设我们的服务不需要任何用户身份验证。
2.系统不会处理部分票订单。要么用户得到他们想要的所有门票，要么什么也得不到。
3.公平是制度的强制性要求。
4.为了防止系统滥用，我们可以限制用户一次预订超过10个座位。
5.我们可以假设，在广受欢迎/期待已久的电影发行和座位上，流量会激增会很快填满的。该系统应具有可扩展性和高可用性，以跟上交通量激增。
4.容量估算
流量估计：
假设我们的服务每月有30亿次页面浏览量，销量为10%一个月一百万张票。
存储量估算：
假设我们有500个城市，平均每个城市有10家电影院。如果每家电影院有2000个座位，平均每天有两场演出。
假设每个座位预订需要50字节（ID、NumberOfSeats、ShowID、MovieID、SeatNumber、SeatStatus、Timestamp等）存储在数据库中。我们还需要存储关于电影和电影院的信息；假设需要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（Enum:“是”或“否”）：是，在响应中包含拼写检查建议。
results_per_page (number)：每页返回的结果数。最多30个。
sorting_order (string)：搜索结果的排序顺序。一些允许的值：“名称，asc”，
'名称，描述'，'日期，描述'，'日期，描述'，'距离，描述'，'名称，日期，描述'，'名称，日期，描述'，'日期，名称，描述'，
“日期、姓名、描述”。
Returns: (JSON)
以下是电影及其节目的示例列表：
代码语言：javascript复制[
{
"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[])
Parameters：
api_dev_key (string)：同上
session_id（string）：跟踪此预订的用户会话id。一旦预定时间到期，将使用此ID删除用户在服务器上的保留。
movie_id (string):要预订的电影。
show_id (string)：show to reserve。
seats_to_reserve（number）：包含要预订的座位ID的数组。
Returns: (JSON)
返回预订的状态，它将是以下状态之一：
1）“预订成功”
2） “预订失败-显示完整，
3）预订失败-重试，因为其他用户正在保留“座位”。
6.数据库设计
以下是我们将要存储的数据的一些观察结果：
1.每个城市可以有多家电影院。
2.每家电影院将有多个大厅。
3.每部电影将有多场演出，每场演出将有多个预订。
4.一个用户可以有多个预订。
7.高级设计
在高层，我们的web服务器将管理用户的会话，而应用服务器将处理所有这些会话票证管理，将数据存储在数据库中，并与缓存服务器一起处理预定。
8.详细部件设计
首先，让我们尝试构建我们的服务，假设它是从单个服务器提供的。售票流程：以下是典型的售票流程：
1.用户搜索电影。
2.用户选择一部电影。
3.向用户显示电影的可用放映。
4.用户选择一个节目。
5.用户选择要预订的座位数。
6.如果有所需数量的座位，则会向用户显示要选择的剧院地图座位。如果没有，用户将进入下面的“步骤8”。
7.一旦用户选择了座位，系统将尝试预订这些选定的座位。
8.如果无法预订座位，我们有以下选择：
•节目已满；向用户显示错误消息。
•用户想要预订的座位不再可用，但还有其他座位可用，所以用户被带回剧院地图，选择不同的座位。没有可预订的座位，但所有的座位都还没有预订，因为还有一些座位其他用户在预订池中持有但尚未预订的座位。用户将被带到等待页面，在那里他们可以等待，直到所需的座位从座位上释放出来预订池。这种等待可能会导致以下选项：
•如果所需的座位数量可用，用户将被带到影院地图，他们可以选择座位的页面。
•等待时，如果所有座位都已预订，或预订池中的座位少于用户想要预订的，则会向用户显示错误消息。
•用户取消等待并返回电影搜索页面。
•在用户的会话过期后，用户最多可以等待一个小时返回到电影搜索页面。
9.如果成功预订座位，用户有五分钟的时间支付预订费用。之后付款，预订被标记为完成。如果用户无法在五分钟内付款，则其所有保留的座位将被释放，以供其他用户使用。
服务器如何跟踪所有尚未预订的活动预订？和服务器如何跟踪所有等待的客户？
我们需要两个守护程序服务，一个用于跟踪所有活动预订并删除任何过期预订
系统预约；我们称之为ActiveReservationService。另一项服务是跟踪所有等待的用户请求，并在所需的座位数量达到如果可用，它将通知（等待时间最长的）用户选择座位；我们打电话吧它正在等待服务。
a、 ActiveReservationsService
我们可以将“show”的所有保留保存在内存中，保存在类似于链接HashMap的数据结构中或者一个树映射，除了保存数据库中的所有数据。我们需要一个链接的HashMap类型一种数据结构，允许我们跳转到任何预订，以便在预订完成后将其删除。
此外，由于我们将有与每个预订相关的到期时间，HashMap的负责人将始终指向最早的预订记录，以便在超时时预订可以过期达到。
为了存储每场演出的所有预订，我们可以在“键”所在的哈希表中设置“ShowID”和“value”将是包含“BookingID”和“creation”的链接HashMap“时间戳”。
在数据库中，我们将预订存储在“预订”表中，到期时间将在时间戳列。“状态”字段的值为“保留（1）”，一旦预订完成完成后，系统将“状态”更新为“已预订（2）”，并从中删除预订记录相关节目的链接哈希图。当预订过期时，我们可以将其删除从预订表中删除，或者将其标记为“过期（3）”，并将其从内存中删除。
ActiveReservationsService还将与外部金融服务一起处理用户付款。无论何时预订完成，或预订过期，WaitingSersService都会收到一个信号这样就可以为任何等待的客户提供服务。
ActiveReservation服务跟踪所有活动预订
b、 等待服务
就像ActiveReservationsService一样，我们可以将一个节目的所有等待用户保留在内存中链接的HashMap或TreeMap。我们需要一个类似于链接HashMap的数据结构，以便当用户取消请求时，跳转到任何用户以将其从HashMap中删除。还有，既然我们
如果以先到先得的方式提供服务，链接HashMap的负责人将始终是指向等待时间最长的用户，这样每当有座位可用时，我们就可以在公平的态度。我们将有一个哈希表来存储每个节目的所有等待用户。“关键”应该是“ShowID”，值”是一个包含“用户ID”及其等待开始时间的链接哈希图。客户端可以使用长轮询来更新自己的预订状态。无论何时如果座位可用，服务器可以使用此请求通知用户。
预订到期在服务器上，ActiveReservationsService跟踪活动的过期时间（基于保留时间）预定。由于客户端将显示一个计时器（用于过期时间），这可能有点超出了预期与服务器同步，我们可以在服务器上添加一个5秒的缓冲区，以防止出现故障
体验，这样客户端在服务器运行后就不会超时，从而阻止了成功购买。
9.并发性
如何处理并发性，使两个用户无法预订同一座位。我们可以使用SQL数据库中的事务，以避免任何冲突。例如，如果我们使用的是SQL server，我们可以在更新行之前，利用事务隔离级别锁定行。这是样品代码：
代码语言：javascript复制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 ...提交事务；“Serializable”是最高的隔离级别，可确保不受脏读、不可重复和幻读的影响。这里要注意一件事；在一个事务中，如果我们读取行，就会得到一个写锁
这样他们就不会被其他人更新。一旦上述数据库事务成功，我们就可以在ActiveReservationService。
10.容错
当ActiveReservationsService或WaitingUserService崩溃时会发生什么？
每当ActiveReservationsService崩溃时，我们都可以从“预订”桌。请记住，我们将“状态”列保留为“保留（1）”，直到获得保留
预定了。另一种选择是采用主从式配置，以便在主从式崩溃时slave可以接管。我们没有将等待的用户存储在数据库中，因此，当WaitingUserService崩溃时，我们没有任何方法来恢复这些数据，除非我们有一个主从设置。类似地，我们将对数据库进行主从设置，使其具有容错性。
11.数据分区
数据库分区：
如果我们按“MovieID”进行分区，那么一部电影的所有放映都将在同一个屏幕上进行服务器对于非常热门的电影，这可能会在该服务器上造成大量负载。更好的方法是基于ShowID的分区；这样，负载就分布在不同的服务器上。ActiveReservationService和WaitingUserService分区：我们的web服务器将管理所有活动用户的会话并处理与用户的所有通信。我们可以使用一致的哈希为ActiveReservationService和WaitingUserService分配应用程序服务器基于“ShowID”。这样，特定节目的所有预订和等待用户都将由一组特定的服务器处理。让我们假设为了负载平衡我们的一致哈希分配任何节目都有三台服务器，因此每当预订过期时，保留该预订的服务器将执行以下操作：
1.更新数据库以删除预订（或将其标记为过期），并更新中的座位状态“展示座位”表。
2.从链接的HashMap中删除保留。
3.通知用户他们的预订已过期。
4.向所有等待该服务的用户所在的WaitingUserService服务器广播一条消息显示以计算等待时间最长的用户。一致的散列方案将告诉哪些服务器正在关押这些用户。
5.向等待时间最长的用户所在的WaitingUserService服务器发送消息，如果有需要的座位，他们会提出要求。
只要预订成功，就会发生以下事情：
1.持有该预订的服务器向持有该预订的等待用户的所有服务器发送一条消息。这样一来，那些服务器就可以让所有需要比服务器更多座位的等待用户过期有空位。
2.收到上述消息后，所有等待用户的服务器都会查询数据库，看看现在有多少免费座位。数据库缓存将大大有助于这里的运行。这个查询只有一次。
3.让所有想要预订比可用座位更多座位的等待用户过期。为此，WaitingUserService必须遍历所有等待用户的链接HashMap。
参考资料
grok_system_design_interview.pdf
