主题：【讨论】回应对12306.cn网站的技术质疑 -- 忘情

1.铁路订票系统的定位

铁路订票系统应该公平地将火车票资源按照旅客的请求分发出去。至少应该满足先订先得的要求。包含两层意思：（1）分发票的顺序不能颠倒；（2）订票不会出现失败的情况。也就是说，只要下订单的时候有票，就一定可以得到票。

2.铁路订票系统的模型

下面给出一个满足先订先得要求的铁路订票系统模型。假设旅客订票只关心出发站，出发时间段，到达站，到达时间段。铁路订票系统接收上述四个数据。根据旅客列车时刻表，有算法在近似O(1)的时间内通过上述四个数据取得旅客可以选择的车次的集合。大概思路是，把时间按照一定间隔（譬如2小时）划分为若干段，作为x轴。把所有车次的所有可能停靠站作为y轴，那么某个坐标(x0,y0)可以确定一个车次集合，表示所有在时间段x0经过车站y0的车次。由于列车时刻表是固定的，这个x-y平面中的点与车次集合的对应关系也是固定的，因此可以事先求出，用二维数组的数据结构表示。当旅客给定出发时间段和出发站时，可以在O(1)的时间内读出满足出发要求的车次集合C1。同理，可以在O(1)的时间内读出满足到达要求的车次集合C2。同时满足出发要求和到达要求的车次集合是C1,C2的交集。因为C1,C2的元素个数相对较少，因此求交集可以近似视为在常数时间内完成。由此，我们把旅客提交的出发和到达要求在常数时间内转换成了旅客可以选择的车次集合。

知道可选车次，出发站和到达站，就可以进行订票操作了。这里，基本的数据结构是一个以车次为行，所有可能停靠站为列的二维数组。在二维数组的一个存储单元内，存储某次车在某个停靠站的余票数。如果以n表示旅客提交的出发站与到达站之间的总停靠站数，那么查询余票可以通过n个基本操作完成。道理是这样的，可以出售的车票数等于在出发站与到达站之间的所有停靠站的余票数的最小值。因此对n个站点进行读取就可以得到满足旅客需求的余票数。

旅客的订票需要4*n个基本操作。首先锁定沿途各站的余票数，需要n个基本操作。其次查询余票，需要n个基本操作。如果存在余票，对沿途各站的余票数减1，需要n个基本操作。最后解除锁定，需要n个基本操作。

以上，对于一个旅客的订票活动，需要进行4*n次的存储单元访问。考虑到中国目前有5亿网民，假设在高峰期，有5亿次/秒的订票请求，每个请求中，旅客指定的出发站与到达站之间都有100个停靠站，那么就需要4*100*5亿次/秒，也就是2000亿次/秒的存储单元访问。这可以视为是订票系统的极限性能需求。理论上，如果不考虑网络连接方面的问题，达到该性能的系统可以无压力地满足广大旅客的订票需求。

3.分析及结论

2000亿次/秒的存储单元访问，对于计算机的性能是一个不小的挑战。一个解决方案是，采用分布式计算。如果将不同车次的余票信息分别存储在2000台计算机上，按照车次对旅客提交的订票请求进行分流，那么理想情况下每台计算机的存储单元访问就可以降到1亿次/秒，一般的计算机将可以胜任。

在达不到所需的数据处理性能的情况下，系统将无法实现实时订票，退化为一个异步订票系统。对于一个能处理1亿次/秒存储单元访问的计算机来说，面对5亿次/秒的订票请求，最坏的情况下，最后提交的请求将延迟2000秒，也就是半个多小时才能完成订票。

由上述分析可见，采用高性能的数据库，采用并行计算方案，适当牺牲订票系统的实时性，有助于解决铁路订票系统的问题。