本帖最后由 alcooo 于 2016-1-7 11:05 编辑
12306 余票是怎么计算的？(转载Man Lee)
闲扯 12306 余票查询设计，肯定不太对（尤其是算法），但是扯下思路吧。
车票售卖特点，有一张车票卖出去就会影响到整个列车线的票数：北京开往广州的一趟列车有人买了石家庄到郑州的票，同时意味着出发点在北京 - 石家庄，目的地是郑州 - 广州的所有情况都会少一张票。
1. 最 low 的方法。每次查询车票时候都算一遍各个站点的票数，取最小值。假设一共 3 站，北京，石家庄，广州，共 10 个座位。有人要查询北京 - 广州的票：已经卖出了北京 - 石家庄 9 张票，石家庄 - 广州 1 张票，取中间车站的最小值 10-9=1，剩一张。这样如果是 20 站查看两头车站的余票就要计算 19 次再找最小值。
为什么说它 low 呢？因为票数不多但是查看余票的人太多！而且人都不傻，在没票时候还会刷新！所以来一次访问计算 20 次，10 万人加上每个黄牛开 10 台电脑用来刷票，瞬间访问数达到 100W，想要 1 秒内都得到响应需要 1 秒计算 2000W 次。
2. 稍微好一点的方法。票被买走时候把每个车站余票计算一下存储起来(Nosql，redis，memcache)，查看余票时候直接返回这个结果。同样每秒 100W 访问，但是只有 1000 人在这秒买到了票，计算余票时候只需要 1000*20=20W 次，省下了 1800W 次的运算。
3. 更“实际”一点的方法。每隔 1 秒同步一次数据状态，而不是每次操作。假设 12306 每次查余票需要更新 1k 数据，一般单个网卡 1G 带宽，理论能同时支持 12.8W 的访问量，100W 人都要看就至少有 8 个服务器在工作，方法 2 中，余票需要存放 8 份的话就需要 1000*8=8000 次更新。还要考虑各个地区访问的不均等性，电信，网通，铁通等线路，整体列车余票情况数据量也有几十 K，所以 1 秒 8000 次更新也几百兆的流量了。但是如果每隔 1 秒同步当前的数据状态就好很多，这样变成了 1*8=8 次，更新数据库传输总量 1M/s 左右，差不多吧？
即便如此，还是扛不住访问量。因为我们上边讨论的是 1 辆列车的情况
因为电脑上 12306 是用的网页模式，查询车票那个页面大小 6K，即便是用了 ajax，刷新一次北京 - 郑州，这样的大站需要传输 7K 的纯 json 数据，个人感觉有很多字段都浪费了，没什么用。
所以就我看来，12306 可以做以下改进，不是一切问题都要用技术解决的。
1. 已经做了，分段放票，减少扎堆
2. 12306 自制一款好的抢票软件。既然抢票权在自己手里了，刷票软件就少了，大量减少流量。
3. 别搞现在的图片验证码了，这些验证码刷不出来，辨识度低根本是暴力防刷，不但防机器人，真人都不行。
4. 更改抢票规则，反正都是拼手速，拼网速，拼人品，何必这么费劲大家一顿刷刷刷呢？写个算法分配下吧。
供需是主要矛盾，供小于求必定导致各种买不到票，没办法。
有些看官想学习高性能，高并发，分布式网站架构设计，还是仁者见仁智者见智吧，我真心不敢大放厥词……
建议看看看《大型网站技术架构_核心原理与案例分析_李智慧》，《大型网站系统与 Java 中间件实践》这两本书，大数据分析的话《Hadoop 实战》这本也不错。
-- 下方是闲扯，下方是正文 --
由于 12306 这个开放性问题太大，我就只能说下为什么看到票却买不到的最基本情况，权当抛砖引玉吧。
12306 网站是全世界最繁忙的网络之一，由于大量的人集中在某个时间点大量访问该网站，导致网站的并发处理能力要求非常高。我是个 it 小菜鸟，就给没有计算机基础的各位看官讲讲皮毛知识，大牛莫笑。
网上有这么一个统计图：
1. 网站是怎么运作的。 一个用户想知道现在有没有票，于是打开网页，网站的后台就去查看自己的数据库，检索下有没有用户需要的数据，然后将结果展示到页面上，就形成了页面上的余票信息。 然后用户看到：嘿~有票！买买买！点击购买后，网站后台将用户订票的信息在数据库中更新一下：北京到巴黎的票 100 张变成了 99 张，然后购票成功。 我这里说的很简单，没有提到支付环节与退票，咱们先看这个简单的例子，画个图大概是这个样子的：
2. 当有 101 个人都在抢票时候呢？ 悲剧了，现在抢票更接近真实了，在早上 8:00:00，有 101 个人同时要抢这 100 张票，会发生什么呢？对于一个人来说，网站实行“查看有多少票”（检索数据库），“买一张票”（修改数据库）的时间非常快，大约在 50ms 以内，所以很顺利就执行了。但是 101 人同时点击购买呢？全按照上图的简单流程，就多卖了 1 张票！所以需要再加一层检查： 由于不止一个人同时买票，所以看到票数一瞬间与点击买票的一瞬间实际上剩余的车票数量发生了变化！因此买票时候会再次检查余票。如下图，虽然红框内同时发生，不过你网速手速不行……
所以，你看到有票但是买时候没票 3. 上百万人同时访问一个网站呢？ 基本与上边步骤都一样，不过网站后台把用来给用户看的数据库与用来给系统改写的数据库拆开了。也就是说有一个（多个）数据库专门是给用户读的，有一个数据库专门是用来做加减操作的。它们之间每隔一定时间就把内容同步一次。（用来改写的数据库叫主库，用来读取的数据库叫从库，一般情况下主库只有一个，从库有很多个。主库的数据每隔一段时间同步到从库中） 查看票数时候只访问从库：还有票哇，好开心！
买票时候改成了访问主库：你妹！说好的有票呢！
最后：实际应用中 12306 流程比这个复杂的多，比如同时 10 人抢 1 张票给谁？这么大访问量我带宽扛不住怎么办？由于列车太多，少一张票就会影响整个列车线，计算量太大怎么办？40 分钟等待时间车票怎么办？所以这里只列举了正常情况下比较简单的逻辑，权当一看。
@Man Lee 讲了很多技术上的问题，我补充一个非技术上的：
某张票处于在预定但未支付的状态时，会显示成有余票但无法购票。
这张票不是在 12306 上，而是卡在售票窗口上，铁路售票终端那是先选出若干张车票，再刷身份证，再支付，再出票这么一个流程，但如果窗口那边有张票卡在出票之前的步骤上，余票数不一定为 0，但这张票事实上已经被占了。
至少过去的出票逻辑有这种条件，现在是不是这样不清楚了，但可以确定的是：12306 本身和铁路售票系统是两套独立的系统，12306 向售票系统发送请求（过去这里还有过瓶颈），所以 12306 上购票、退票的瞬间可能会有两边状态不一致的情况。
| 
发表于 2016-1-7 11:03:52
