12306 一度处在风口上, 2013 年之前听到的多是骂声，幸好之后有大牛正名。正名之后渐渐的就有人开始写关于 12306 相关的技术文章了，看的多了之后，也渐渐开始思考。
其中有一篇文章从电商的角度分析了 12306，认为 12306 的票是一种商品，每种可能的票都是一个 SKU ，假设有 ABCD 四个站，就分别有 AD，AC，BD，AB，BC，CD 这 6 种 SKU。假设有 10 个站， 那么就有 45 个 SKU 了，SO，结论是 12306 是一个相当复杂的系统……
我个人认为，并不能把票看做一种简单的 SKU ， SKU 真正的含义是库存单位，就是一个买卖的最小单位。同样假设有 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 座位
- 一张票必须是连续站区间的，不能 AB，CD 绑在一张票上，如果有人有这个需求，那他就买 2 张票吧
- 不能要求乘客中途换座位
- 没有站票（好像没有这个规定😁 ， 这是我简化问题引入的）
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 出票算法
现在我们来确定一下出票步骤：
- 计算客户要购买的票的 ticket value t-site
- 找到一个座位满足 t-site & t-seat = t-site
- 出票，更新该座位的 t-seat = t-seat - t-site
需要注意的是：2、3 步骤得是一个原子操作。
4 总结
我相信，采用这种出票算法，对于 12306 尖峰日 PV 值 297 亿下可每秒出票 1032 张, 不采用内存计算进行优化，直接采用 PostgreSQL 就可以搞定了，每辆列车一个 table 保存所有座位的 ticket value， 不过 😝 ， 当然只是指出票而已，车票系统还有很多其他问题需要考虑。不过貌似看这文章，12306 的票是预先分配好的，然后每 2 分钟更新一次。
Read full article from 一种出票算法 - 没事瞎思考
No comments:
Post a Comment