12306售票算法

Published: 13 Jan 2019 Category: arch

一、需求分析

先不考虑高并发性,售票可以简化为单列车上的出票系统,即在车次、日期、出发点、目的地确定时,判断无票或返回一个座位号。

整个列车所能承载的人数,或者说是负荷,都将始终是个常量。如果将无座号也视为一种虚拟的座位,那么对列车而言只需要区分满载与未满载两种情况:满载时不能再售票,未满载时可售后续区段的票。

在这样的设定下,能否出票的问题就变成了判断列车在特定的区段是否会超载的问题了。至于『有座票』与『无座票』,就自然退化为次要问题了。

二、问题及解决

根据区间确定座位,座位确定后又影响区间,区间又影响确定座位,座位确定后,又影响区间。这是一个关键问题,可以通过限制订票流程解决:

  • 1.找到座位。
  • 2.确定座位,更新座位的可订票区间。
  • 3.生成票。
  • 4.刷新确定座位的可订票区间。

为了保证订票的合理性,这4个步骤必须是原子的,否则就会出现问题了。

2.1 订票(以下只是网络上的一种解法)

经过上面的分析,订票就是根据区间确定座位,并生成票。确定座位是很重要的一环,输入就是区间,输出就是座位。

1.找到座位

那么最优的算法,就是直接简单的从输入得到输出。那么按照这个原则,于是我们就想到了区间到座位的映射。 于是有了Map<区间,座位>,根据区间得到座位。找到了座位,这个订票就完成一大半了,没找到这个座位,那就说明没票了。

这个Map<区间,座位>,我叫它为确定座位的可订票区间。

那么这个Map怎么设计呢?

假如:

这个车次,共有9个站点,分别为1,2,3...到9。   
一共有1000个座位,座位号为1,2,3...到1000.(暂时不考虑什么一等座,二等座什么的)  
区间15,就是表第1站到第5站。  
那这个Map<区间,座位>的数据就像这样:{15,1-500},{19,200-500},{57,150-550}等等。

2.确定座位

经过上面的分析,这个座位是有可订票区间的,其实这个确定步骤,就是更新这些可订票区间。

可以这样更新这个区间:

  • 订票时,会把原来的可订票区间分裂,减去订票区间。
  • 退票时,会把原来的可订票区间合并,加上订票区间。

分离还好,这个合并会有点小复杂,牵扯到前合并,后合并,同时前后合并问题。

下面举例:

假设座位A的可订票区间变化如下:

未出票前:{19}        全程票
出57票后:{15,79}     分裂19变为{15,57,79},去掉57,就剩下{15,79},去掉原19
出35票后:{13,79}     分裂15变为{13,35,79},去掉35,就剩下{13,79},去掉原15
出78票后:{13,89}     分裂79变为{13,78,89},去掉78,就剩下{13,89},去掉原79

退57票后:{13,57,89}  不能合并,增加57变成{15,57,89}
退35票后:{17,89}     合并13,35,57,变为{17,89},去掉原13,57
退78票后:{19}        合并17,78,89,变为{19},去掉原17,89

出19票后:{}          直接去掉原{19}

座位区间的变化算法,就是分裂与合并,经过上面的演变,可以看出分裂和合并的具体细节。
分裂:减少原来的区间,可能会增加分裂后的新区间。
合并:可能减少原来合并前的区间,增加合并后的新区间。

3.生成票

这个没什么可说的,就是生成一张凭证。包含出发时间、出发地、目的地、车次、座位号这些信息。

4.刷新确定座位的可订票区间 Map<区间,座位>

经过2步骤,根据座位的区间变化,来更新Map<区间,座位>的座位内容:

  • 添加的区间,在Map<区间,座位>中,找到对应的区间元素,添加这个座位,如果没有这个区间配备的元素就新建。
  • 减少的区间,在Map<区间,座位>中,根据区间找到对应的座位列表,移除这个座位,如果座位数为0了,可以移除这个区间元素。

举例说明,Map<区间,座位>的数据变化如下:

1.未出票前:{19,1-1000}
2.订57区间票后:{19,2-1000},{15,1},{79,1}
3.订35区间票后:{19,2-1000},{13,1},{79,1}
4.退35区间票后:{19,2-1000},{15,1},{79,1}
5.退57区间票后:{19,1-1000}

2.2 退票

大体上和订票差不多,为了保证能退票,你的车次聚合根要有一个所有票的实体,如:List

1.退票:就是消除这张凭证。从List中移除这张票。

2.释放座位:退票时,会把原来的可订票区间合并,加上订票区间。处理同上面的订票部分。

合并会有点小复杂,牵扯到前合并,后合并,同时前后合并问题。

下面举例座位A的可订票区间变化如下:

未出票前:{19}
出57票后:{15,79} 分裂19变为{15,57,79},去掉57,就剩下{15,79}去掉原19
出35票后:{13,79} 分裂15变为{13,35,79},去掉35,就剩下{13,79},去掉原15
出78票后:{13,89} 分裂79变为{13,78,89},去掉78,就剩下{13,89},去掉原79

退57票后:{13,57,89} 不能合并,增加57变成{15,57,89}
退35票后:{17,89} 合并13,35,57,变为{17,89},去掉原13,57
退78票后:{19} 合并17,78,89,变为{19},去掉原17,89

出19票后:{} 直接去掉原{19}

3.刷新确定座位的可订票区间:处理同上面的订票部分。

三、优化问题

前端性能优化技术(CDN、减少传输连接数、其他缓存技术)、后端性能优化技术(数据冗余、数据拆分、负载均衡、异步处理、限流、批量处理)

参见:由 12306.cn 谈谈高并发+高负载网站性能技术

REF

由 12306.cn 谈谈高并发+高负载网站性能技术
浅谈12306设计思路和算法