继续:12306

八风不动 发布于 2014/01/29 23:25
阅读 809
收藏 7

       前文请移步至:

        12306 售票仓储结构的设计

        续篇:12306 火车售票系统的仓储结构设计

        再续:12306 火车售票系统的仓储引擎设计

            再再续:一张图搞定 12306


        


        根据网友提问,这次解决车票座位号的问题。按照最初的思路,座位号,车次信息、发车时间等这些描述性信息都放到外层就可以了,底层只实现最复杂的仓储算法,微内核架构。但计算下来发现售票进程的负载其实有冗余,可以继续加磅,于是就改进一下内核,把座位号的分配工作也纳入进来。


        一趟列车会有多种席位(站票、硬座、软卧等),各类席位的总数加起来就算1000~2000个。我们用一个字节表示车厢号,一个字节表示席位号,再加一个8字节的沿途售出情况掩码值。这些内容组成一个数组,这就是10~20K的一块内存。


        在这个数组里,相同的席位排在一起,形成不同席位的几个片断,然后在数组头里记录每种席位的类型和数组的起始索引。车票售出时,变更8字节的掩码值。该席位的车票全程售出时,将此节点交换到该席位类别的数组段最前端,然后把该席位类别的数组索引加1。

        

        售票线程完成售票运算后,在这个数组里根据所售车票的席位类型和售票前仓储状态掩码经多次比较找到第一个匹配的坐席号,将此坐席的掩码变更为售票后状态,然后将坐席号附在结果对象上返回给上层应用。此时上层应用收到的售票结果就包含席位信息了(车厢号,座位号)

        

        性能分析:只给售票线程增加了一个查询操作,而且查询操作仅仅是数值是否相等的比较。

        

        前文说的线路,其实指的是车次。一个特定的车次一般一天一趟,有的两天一趟,还有临时车辆。这里我们把仓储引擎的内核数据延伸一下,每个售票进程维护20个仓储状态的树结构,这就涵盖了20天预售期的全部数据。一个仓储状态树3k,一个席位列表20k,一个售票进程维护同一车次20天的预售票务,总内存是23k * 20 = 500K。 总的进程数量就是全国铁路列车车次的总数,这个总数目前也就是几百。

        

        顺便再说下并发问题。首先浏览器点击产生的并发已经分散到多个子域名下了,所以Web部分不会有并发拥堵了。其次后台的运算服务器集群是基于线路做运算的,各负责一摊儿,Web服务器相当于做了一次分拣操作,不同线路的请求交给不同网址的运算服务器。所以后面的运算服务器也是均摊压力的。至于带宽问题,前台的Web服务器是多个子域名,我说了,你分散到多个国家都行。其次内部的运算查询数据量极小,查询任务用16个字节就能描述清楚,查询结果用32个字节就能表述明白,又有多台服务器均摊压力,还能有多大负载?就算美秒40W次查询都放到一台服务器上,也不过是(32+16)*8*40W = 120M。这个我算得对么?

    

        至于数据库方面,仓储状态OK了,座位号码OK了,剩下的都是查询请求,没有并发锁了。也就是说剩下的数据库操作就是查询一下描述信息,然后返回给客户端了。再进一步,如果上层数据库是只读的,能否每台Web服务器各存一份呢?


加载中
0
mallon
mallon
你再想想你的那个掩码模型对还是错
八风不动
八风不动
请详解!
0
yak
yak
  在这个数组里,相同的席位排在一起,形成不同席位的几个片断,然后在数组头里记录每种席位的类型和数组的起始索引。车票售出时,变更8字节的掩码值。该席位的车票全程售出时,将此节点交换到该席位类别的数组段最前端,然后把该席位类别的数组索引加1。       
你画个图出来说明一下
yak
yak
举个最简单的例子, 比如北京从广州的车,有两个人买票,一个人买到广州,一个买到武汉,两个席位数据变动有什么不同吗?然后有个武汉到广州的人来查余票,根据什么方法来查?
八风不动
八风不动
空空空空硬硬硬硬硬硬硬硬硬硬硬硬空空空空空空软软软软软软卧卧卧卧卧
0
haitaosoft
haitaosoft
根据我的了解和理解,12306只是与窗口、电话、代售点一样的接入通道而已,
真正的核心后台:票务系统,并没有改动。12306其实只相当于一个前置子系统。
而卖票过程、余票信息(包括每个座位的各站可卖性),都是原来的票务系统实现的。
12306只是提交给后台锁定或释放或购买的请求,查询余票而已。
所以,每个座位的各站可卖性(a-e站卖了,f-z还是可以买的)都是原后台已经解决了的
0
阿侯
阿侯
膜拜LZ的行为,尚!
0
小微OA
小微OA

给不同站点预留的票怎么处理

比如青岛到北京 一共200个座位 

100张预留青岛。

100张预留济南

离发车1个小时之前在济南开始卖 青岛-》济南的票腾出来的座位。

这只是举个简单的例子,其实现状远比这个有更多复杂的情况。

并发的问题,只是问题的一小部分而已。

需要满足更复杂的策略才是难点。



0
八风不动
八风不动

引用来自“小微OA”的答案

给不同站点预留的票怎么处理

比如青岛到北京 一共200个座位 

100张预留青岛。

100张预留济南

离发车1个小时之前在济南开始卖 青岛-》济南的票腾出来的座位。

这只是举个简单的例子,其实现状远比这个有更多复杂的情况。

并发的问题,只是问题的一小部分而已。

需要满足更复杂的策略才是难点。



第一篇的预分配算法:

6、预分配:车票可以根据历史经验或大数据分析作出合理的预分配,即把一张全程票分成0-9以卖出状态和剩下0-9状态两张票,挂在树结构的两个不同的节点上。这样就可以在售票之初,对路线分段作预处理,提高售票效率。(即:111,111,111,111,111分成111,111,111,000,000和000,000,000,111,111两张票)

不怕有问题,就怕没问题,有啥问题就解决啥问题,世上没有解决不了的问题。:)

0
修改登录密码
修改登录密码

还没有仔细读, 但看到这一句:  查询结果用32个字节就能表述明白

你觉得我要查询从北京到广州的所有车票信息, 你能用32个字节表述出所有信息?(大概有十条车次, 每车次包括 车次4-6字节 , 出发日期和时间,达到时间, 软/硬/卧/站票剩余票数和价格 )

事实上,我看了你的所有文章,我觉得你没有抓住问题的核心。 我觉得12306的关键在于数据的共享/并发操作上。一个问题是满足数据请求的压力,一个问题是必须保证数据一致性。  至于你前面说的那张图,只是考虑了把前台请求分散到若干服务器上的问题, 但是所有进程都是在访问一个数据库,数据库如何抵抗如此高的压力?  如果采用集中式数据库, 能否支撑40w次的查询?  如果采用分布式数据库, 为了维护一致性,需要付出多少带宽和内存的代价?

我个人以为,这个数据库的查询和更新机制才是最关键的问题所在。



修改登录密码
修改登录密码
回复 @八风不动 : 按照你的说法 40w次点击就要产生400w+次查询了 你的数据库一秒钟能支持多少次查询?
八风不动
八风不动
好几篇文章,你只看了一张图。 十几个车次,可以分散成十几个查询,最后汇总发给用户,这是Web服务器要做的事。
0
yak
yak
问题是 所有的车次的的车票信息状态更改和查询是集中在一台机器上能保证数据一致性,但单台机器的并发就算是纯内存操作也有c10k的天花板,如果不同车次分布到不同机器, 不同节点换乘线路的事务操作如何保证数据的一致性,你这种方案只适合全国就一条线路的极简情况,实际上对于最终用户的请求,是一个连通图的两个结点之间的路径,每一个用户对每一条路径涉及的节点状态变更都是全局的,都要通知到全网节点才能保证数据一致性,这里还不考虑支付系统与票务的事务操作,所以说这种把所有车站全部耦合在一起思路是个死胡同,,合理的结构是两层结构,前面是一层线路系统,只共查询用的,后面的是真正的票务处理系统,票务数据不是存在一片内存里面,而是一个线路将其不同节点通过映射关系映射到不同机器上,任一节点信息变更以后,主动通知到线路系统
八风不动
八风不动
前文回复里有说,换乘问题类似于公交换乘,上层应用算好了最优的几种换乘方式再到引擎里查有无余票。至于换乘算法,那个已经很普及了。
0
yak
yak

解决办法只有两个

1:如果为了保证数据一致性,票据信息集中存储,那请求在时间上分布 比如回家买票的请求在一年365天中均匀分布

2 如果买票在时间上集中请求,那数据就分散在不同节点,一趟车次的不同车厢分布在不同的机器节点上(最极端的情况是一个座位用一台机器标识),系统只维护这种影射关系,这种映射关系可以用代码的形式发布到很多不同的节点上,保证请求不论在任一节点,业务逻辑都是一致的,这样就算解决了买票问题,最后的结果是可能你鼠标 还没 来得及点,票已经卖完了。

所有问题的根源还是这种传统文化与集权优质资源聚集的矛盾,要么改变传统文化,要么分散优质资源到不同节点,只要把北上广深的大学和医院分一部分出来分散到中小城市, 12306一根毛都不用动,就能解决买票难的问题,而且保证人手一票

返回顶部
顶部