设为首页收藏本站邮件列表

12306NG开源项目组

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
查看: 2755|回复: 10

12306票池架构探讨(二)

[复制链接]

19

主题

9

听众

619

积分

少年英雄

Rank: 4

发表于 2012-10-17 12:46:04 |显示全部楼层
本帖最后由 shiyimin 于 2012-11-11 22:58 编辑

数据结构设计
在原来的基于boost设计的帖子里,我提了一个有向图的方案,主要思路是:
1、每个站点都是有向图里的一个节点。
2、车次这个路径,是由连接站点的多条边来描述的,每条边(例如北京南 – 德州东的G107次车,包含了北京南可以卖的票,德州东如果不卖票的话,可以将票数置零)。
3、火车时刻表用adjancency_list图结构来表示,基本上就是图上所有顶点保存在一个数组里(每个节点通过站点名代表的索引值索引),而每个节点附带了一个列表,就是经过这个节点的边(out edges和in edges),而这个边的权就是车次号,同样车次号也是一个索引,如下图所示(以北京和上海来回的高铁G107和G108为例):


在上图里面,可以看到,每个站点(就是图里面的节点)用一个列表保存了经过它的所有的车次(边),通过有向边的方式指明车次的方向,一个车次其实是由多条边组成的。

可以把站点(例如北京)和车次(例如G017)本身看成获取数据的索引,例如在server-core/cpp/sites.h里,将所有的站点定义成一个枚举型;server-core/cpp/trains.h里,将所有的车次定义成一个枚举型(以数字开头的,在前面加上下划线就可以了)。由于站点和车次不是经常更换,因此可以固定起来,以后有更新的话,只需要提供站点和车次的配置文件,直接生成上面两个代码就可以了,如果买票订单保存的是起始和终点站的索引的话,在重新生成的时候就需要考虑保证相同站点名的索引值不变,但如果订单直接保存站点名称,就没必要保证索引值不变了。

索引如下图的二维表所示,其中上面两个数组分别是车次G108和G107的余票信息,“-”表示这个位置车次经过该站点,它的值实际是一个指针,指向对应车次的余票数组:




又因为需要考虑中间上车的情况,二进制的方案如果是放在数据库里,会有很大的性能的问题,那么我在考虑是否可以将二进制的方案整个放在内存呢?我觉得是可能的,主要是出于下面几个发现:
1. 首先在上图里,车次的余票信息的确是一个大数组,这个数组可以是一个位数组,每一位代表这个座位的售票情况,只要这个座位有过售票 - 不管是从始发站坐到终点站的,还是中间上车的,那么就将这个位设成1。而一个车次的车厢配置、车厢的座位、铺位配置在一个固定的时间段,至少是一天内是固定的,可以认为是不经常改变的。
2. 还没有卖出去票,是不需要保存在内存里,只要在上面的数组里将对应位设为0就好了。
3. 所有从始发站坐到终点站的车票也不需要保留在内存里,只要在上面的数组里将对应位设为1就好了.
4. 在内存里我们只要找到一个数据结构,用来保存中间会上下车的座位信息就可以了,这个信息就可以用二进制的方案来表述,第一是占用的内存量小,第二是对比和修改都很快。
5. 至于退票,我还在考虑是放回票池,还是用一个单独的链表结构来保存,我现在倾向于放回票池。
6. 那保存每个车次的中间上下车的余票信息,我们可以借鉴Windows系统管理内存分配的数据结构,这个结构可以做成一个包含数组的数组,数组的下标代表这个位置的元素的空闲位数,如下图所示:

每个车次都有类似上图的二维数组,在上图里,数组的第一个元素里,包含的是该车次所有最大连续空闲站点数为1的座位,也就是说只有1站没有人坐的位置;第二个元素,是该车次有连续2站没有人坐的位置,虽然第二个元素我们看到实际是有三站空余,但我们仍然放在第二个元素里。

这个时候,如果有人买票,例如是坐一站的,那我们就首先去第一个数组里找,找到第一个匹配,将位补齐,这个时候发现位置已满,因此将其从上图的数组中移除,移除它剩下的空就放在那里,如下图所示:


如果有人买两站的票,跟上面一样,找到第二个数组的第一个座位匹配,买了票之后,它的值变成:“11111101”,因为它只有一站是空闲的,因此我们将其放到第一个数组中去,如下图所示:


这个二维数组,每一个车次的列数是固定的 – 因为每个车次经过的站点数目是固定的,而每列对应的数组,如果空间不够了,可以动态分配(这里是一个风险,我还没有仔细计算过极端情形)。

为了节省内存,每个座位的车次是一个长整形,即8个字节组成,这8个字节里,前14位用来表示座位在车次的索引(14位里,可以有12位表示索引,可以表示4096个座位,应该可以满足一趟车上的坐票、卧铺和站票信息了,另外两位可以用来做一些标志位,具体干什么我还没有想好),后50位就是座位的站点占用信息。如下图所示:


对于运行区间超过50个站点的车次,作为特殊车次特殊处理 - 这样的车次应该不是很多,可以先枚举下。

还有对分布式的支持、负载均衡等方面的想法,还没有写完,这两周慢慢写,先把现在想到的发出来,抛砖引玉。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

回复

使用道具 举报

38

主题

9

听众

1020

积分

版主

Rank: 7Rank: 7Rank: 7

活跃会员

发表于 2012-10-17 15:46:08 |显示全部楼层
你的确逆天了。呵呵
对于数据的使用的确是最精简了。
究竟要做成啥样子的系统捏?
回复

使用道具 举报

28

主题

35

听众

2981

积分

名震江湖

Rank: 6Rank: 6

活跃会员

发表于 2012-10-17 20:00:47 |显示全部楼层
看了N遍。勉强看明白。
回复

使用道具 举报

19

主题

9

听众

619

积分

少年英雄

Rank: 4

发表于 2012-10-18 00:18:51 |显示全部楼层
晚起的虫子 发表于 2012-10-17 20:00
看了N遍。勉强看明白。

,那我需要加强文笔功力啊!
回复

使用道具 举报

28

主题

35

听众

2981

积分

名震江湖

Rank: 6Rank: 6

活跃会员

发表于 2012-10-19 16:19:03 |显示全部楼层
shiyimin 发表于 2012-10-18 02:18
,那我需要加强文笔功力啊!

不是。 没这么写过代码。
回复

使用道具 举报

0

主题

0

听众

64

积分

初出茅庐

Rank: 2

发表于 2012-11-18 14:24:45 |显示全部楼层
如果看完,再在yy上讨论一遍,是不能更便于理解
回复

使用道具 举报

0

主题

0

听众

16

积分

新手上路

Rank: 1

发表于 2013-1-8 17:12:50 |显示全部楼层
参考二进制的那种吗 ?
回复

使用道具 举报

0

主题

0

听众

22

积分

新手上路

Rank: 1

发表于 2013-1-26 21:43:19 |显示全部楼层
12306最大的压力是刷票,即查询,号称的15亿PV应该有99%都是查询(一天最多的下单数应该也在500万以内,其余全是查询),因此对查询的优化是最关键的,其中很重要的就是应该将查询结果放到缓存和预先计算好,避免每次都做重复性计算。对于查询我也有个想法:与基于座位不一样,而是基于站点来说
1,将某个日期的某车次,如2013-01-25的K150当一个对象,途径30个站,共有2000个座位(硬卧100张+硬座1900张),理论下是要是每张票都卖一个站点的话那么每个站点度可能卖2000张票,我们将途径多个站点的当做多张一站票来扣数,其结构:
初始:
2013-01-25_k150:         途经站:  A站     B站    C站      D站   E站
                             硬卧余票          100    100    100     100   100
                             硬座余票         1900   1900   1900  1900  1900
                                总余票         2000   2000   2000  2000  2000
预订B到D1张卧铺和A到C硬座一张后:
2013-01-25_k150:         途经站:  A站     B站    C站      D站   E站
                             硬卧余票          100    99      99       100   100
                             硬座余票         1899   1899   1900  1900  1900
                                总余票         1999   1998   1999  2000  2000
当查询B站到D站的时候只需要统计两站间最小数即可:99+1899=1998;而且可以迅速知道之间各种坐席的剩票
这种结构也可以直接存储到数据库,一个车次坐席才一条记录,将20天可预订的车次独立出来,那么预售期总车次:20天*2000车次/天=4万条记录(再乘以坐席数)
2,中国总车站数也才不到两千个,将常用车站独立出来,每个对应一个途经该站的车次队列,这个队列最多也就几百个车次(每天车次乘以20天预售期)对象,列出可在这个车站预订的车次,而查询的时候,车站是必填的(或者直接车次),因此可以直接根据车站找到该车次队列,再遍历这队列查出所有车次
像影子一样,时隐时现  象玻璃一样,说有,可就是看不见
回复

使用道具 举报

19

主题

9

听众

619

积分

少年英雄

Rank: 4

发表于 2013-1-27 22:45:25 |显示全部楼层
babyhe 发表于 2013-1-26 21:43
12306最大的压力是刷票,即查询,号称的15亿PV应该有99%都是查询(一天最多的下单数应该也在500万以内,其 ...

这两个星期太慢了,晚点答复你。
回复

使用道具 举报

1

主题

0

听众

92

积分

初出茅庐

Rank: 2

发表于 2013-2-27 09:48:33 |显示全部楼层
babyhe 发表于 2013-1-26 21:43
12306最大的压力是刷票,即查询,号称的15亿PV应该有99%都是查询(一天最多的下单数应该也在500万以内,其 ...

这种数据结构和算法总体上是比较好的,具体实现时可以进行局部细化
回复

使用道具 举报

Archiver|手机版|12306NG开源项目组    

GMT+8, 2014-2-14 01:59 , Processed in 0.099072 second(s), 33 queries , Xcache On.

Powered by Discuz! X2.5

© 2001-2012 Comsenz Inc.

回顶部