没事瞎思考

没事瞎思考

一种出票算法

12306 一度处在风口上, 2013 年之前听到的多是骂声,幸好之后有大牛正名。正名之后渐渐的就有人开始写关于 12306 相关的技术文章了,看的多了之后,也渐渐开始思考。

其中有一篇文章从电商的角度分析了 12306,认为 12306 的票是一种商品,每种可能的票都是一个 SKU ,假设有 ABCD 四个站,就分别有 AD,AC,BD,AB,BC,CD 这 6 种 SKU。假设有 10 个站, 那么就有 45 个 SKU 了,SO,结论是 12306 是一个相当复杂的系统……

我个人认为,并不能把票看做一种简单的 SKUSKU 真正的含义是库存单位,就是一个买卖的最小单位。同样假设有 ABCD 4 个站,列车共有 10 个座位,一开始,任何种类的票都有 10 张,我买了 1 张 AD 的票之后, 任何票种都只剩下 9 张票了,AD 作为一个 SKU 明显影响了其他的 SKU 的数量,所以这样看是不对的。

现在我们知道, 不能把票看做一种 SKU 来处理, 但是这个类比却引发我一个思考,这个类比错误之处在于没有试图找出票的最小单位 —— 1 站 × 1 座位。以最小单位来当做 SKU 结果会如何了,仍然行不通,假如我买了 BC 区间 6 号座位票,那么 AD 区间的 6 号座位的票是卖不出去的, 尽管在 AB 和 CD 区间我并没有占有 6 号座位,这就导致了,AB 和 CD 可以单独卖 6 号座位的票,但就是不能卖跨越 BC 的 6 号座位的票。

上述例子实际是基于一个规则,就是不能要求乘客中途换座位,假如可以的话,我明显可以让乘客 AB 和 CD 的时候坐 6 号座位,BC 坐其他座位了,那么 6 号座位全程是满的,这对于列车来说倒是再好不过了。

1 几个小结论

  1. 票的最小单位是 1 站 × 1 座位
  2. 一张票必须是连续站区间的,不能 AB,CD 绑在一张票上,如果有人有这个需求,那他就买 2 张票吧
  3. 不能要求乘客中途换座位
  4. 没有站票(好像没有这个规定😁 , 这是我简化问题引入的)

2 模拟卖票

12306 sell ticket 如上图所示,甲买了 cd 2 个站 1 号座位的票,现在如果乙需要买 abc 3 个站的票,那他只能买 2 号座位了,现在我们来看看丙,丙需要买 de 2 个站的票,分配 3 号座位给丙并不是不可以,但是不合理,因为这使得 3 号座位可以组合的票种变少了,卖出去的可能降低,期望利润降低了,丙分配到 2 号位置是最合理的。

2.1 出票规则

基于上述例子,我们来设计一个合理的出票规则:确定票的站区间,从上至下找到一个不和其他票冲突的座位(也就是图形中的色块不重叠)。

这里有 2 个关键点:

  • 「从上至下」保证了座位利用率最高
  • 「不冲突(色块不重叠)」代表改座位在该区间可用

12306 best ticket 丙 de 2 个站的票从上到下找到 2 号座位,最终得到上图结果。我们把卖出去的票(着色区域)标记为数字 0,没卖出的标记为数字 1,那么我们就得到了一张内存图。1 站 × 1 座位就是一个 bit 位,我们每一行(每 1 个座位)用一个 unsiged long 数字代表,就可以代表 64 个站区间,一条线路 65 个站应该满足我们国家需求了😁 。

2.2 判断座位在某站点区间是否可用

拿丙来说,丙买了 de 2 个站点的票,根据我们内存图模型,他买了一张这样的票

0000000000000000000000000000000000000000000000000000000000011000「= 24」

应该倒过来看这一串数字,后面 3 个「0」 代表 abc 3 个站区间,2 个「1」 代表 de 2 个站区间。这张票一串二进制数字就代表 「24」,为了方便,我们称 「24」 为这张票的 ticket value (t-site);同样,座位占用了的区间标为「0」,可使用的区间标为 「1」, 得到座位的 ticket value (t-seat)。那么判断座位是否可用的方法就是:

t-site & t-seat = t-site

确定座位的可用性之后,如果决定出票,只需要用 t-seat 减去 t-site 作为新的 t-seat

3 出票算法

现在我们来确定一下出票步骤:

  1. 计算客户要购买的票的 ticket value t-site
  2. 找到一个座位满足 t-site & t-seat = t-site
  3. 出票,更新该座位的 t-seat = t-seat - t-site

需要注意的是:2、3 步骤得是一个原子操作。

4 总结

我相信,采用这种出票算法,对于 12306 尖峰日 PV 值 297 亿下可每秒出票 1032 张, 不采用内存计算进行优化,直接采用 PostgreSQL 就可以搞定了,每辆列车一个 table 保存所有座位的 ticket value, 不过 😝 , 当然只是指出票而已,车票系统还有很多其他问题需要考虑。不过貌似看这文章,12306 的票是预先分配好的,然后每 2 分钟更新一次。

本人并没有参与过 12306 相关的工作,此文仅仅是个人的一点小思考而已,没有对 12306 构成任何点评!

Comments

comments powered by Disqus