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

八风不动 发布于 2014/01/26 21:49
阅读 1K+
收藏 9


    本文是前一篇文章的续篇:http://www.oschina.net/question/124158_141925


    前文概述了火车售票系统仓储结构的设计思路,关键点就是用64bit的long类型数据表示一条线路。这次继续展开,进一步设计票务仓储系统的树结构和细化的数据节点及算法。


    1、大站划分:用线路中途的大站对线路进行分割,形成树结构便于查询统计和售票退票。例如:假设有一条北京开往广州的线路,中途最大站就是上海,于是以上海为节点,对整条线路进行分割。(实际生活中,大站之间以及大站到小站和小站到大站这几种情况是最多的,其他情况发生的概率都很小,所以大站划分最合理)


    假设上海是第9站,全程是111,111,111,111,111,子节点可以划分成北京-上海间已售空且上海广州之间未售出和有售出两个节点000,000,000,111,111000,000,000,***,***,上海-广州已售空且北京-上海之间未售出和有售出两个节点111,111,111,000,000***,***,***,000,000,以及北京-上海-广州之间均未售空但有票售出的(111,111,111,***,***(***,***,***,111,111。这样就是6个子节点。其中有四个节点(带*的)有多个孙节点(不同的掩码值)。


    2、多级划分:如果北京-上海这段中途站点较多,就以中途最大的站点继续划分,形成子树。


    3、数组存储:用数组索引代替子节点指针,多个子节点顺序存储。父节点只需存储一个子节点起始位置(ushort)和一个子节点数量(byte)即可。当然,最好把子节点划分依据也存在父节点,即中间大站的索引序号(byte)。这样整棵树都没用指针(X86系统的指针站32bit,X64系统指针占64bit,省内存省到姥姥家了),而且是一个连续空间的大数组,内存管理上就是一个整体的内存块,极度节约资源,还避免了内存碎片。


    4、多票种联合查询:每个树节点除车站掩码(long)、子节点标识(ushort+byte+byte)之外,还可以存储多个余票数量,分别是站票、坐票、硬卧和软卧。余票数量用ushort保存,就是4个ushort,为了能在64位系统上实现8字节对齐,可以再加两个ushort以便今后扩展,例如增加其他席位类别的余票数量(软座、特席)。这样算下来一个节点只需32字节,一棵树顶多100个节点,算3K,假设全国有10000条线路,只需30M内存就把全国的火车票余量记录下来了。当然这里只记录了仓储数量,即便加上车站名称,站点名称等描述信息,50M内存也放下了。50M内存,用我当年64M的烂PC都能玩儿转,12306却要用多台1TB内存的服务器,还整出几十T的内存池,真是浪费资源啊~。


    5、多票种联合换乘:春节期间车票紧张,买不到北京-广州的直达票,可以买北京-上海间的硬座票和上海-广州间的软卧票。用以上算法,这种查询可以在树结构的一次扫描中获得,今后12306网站可以推出一项新服务,即购买联程票的服务。用户查询北京-广州的车票时,系统发现硬座、硬卧、软卧、软座甚至站票都木有了,但分段购买的话,可以乘一趟列车的不同席位到达广州,于是提示用户可以买多张联程票,即一张北京-上海的硬座票,一张上海-广州的软卧票,于是乘客可以乘一趟列车顺利到达广州。Perfect!


    6、相关算法:参考上一篇文章的内容,在这个内存块上实现各种算法,即可实现火车票仓储引擎的全部功能。


    OK!关于12306火车售票系统仓储引擎的设计就介绍完了,欢迎探讨。

加载中
0
平信
如果一秒钟内1000个人在余票为200张中购买,这两百张在这1000个客户端如何分配?需不需要锁定?线程间共享数据如何管理?
八风不动
八风不动
内存锁定义两个级别,一个是树级锁,一个是节点锁。树级锁就是锁定整棵树,即整条线路。节点锁就是锁定一个节点,即发现此节点有余票可供当前客户购买,于是锁定此节点,做出票运算。 如果并发量大,就用节点锁,先来后到,谁先到先给谁出票。
0
平信
锁间原子操作过于复杂影响锁所涉及共享数据的访问时间,这样的线程间共享设计有多大并行效益。
0
东胜神洲
东胜神洲
其实优化数据结构是其次,最重要的是巨量的并发请求。。这里就涉及到一个春运节日的特殊性。。。举个例子,假设日常使用 10 台服务器就可以满足购票运作,而春运节日则需要 50~100 台服务器甚至更多的资源来处理,那么节日过后呢?。。。那堆服务器摆在那,作为资源浪费的典范被喷?。。本来,租用云计算,充分利用其弹性来运营,是个不错的办法。。可惜没有一家大型的云计算供应商肯做。。。
八风不动
八风不动
巨量并发的问题稍后专文解决。
张亦俊
张亦俊
其实没有云厂商做的原因也能想通。铁路的压力在春运,而春运期间所有东西压力都大,大家要扎堆去电商买礼品,扎堆发短信发微博拜年。估计就是阿里这大地主家也没啥余粮,肯定不会借给别人的。
0
修改登录密码
修改登录密码
50M内存肯定是不够的。 你要记录的内容不仅有当前座位空闲信息 ,还要记录每张售出的票的信息(身份证编码 姓名 购买时间 ,支付时间,支付银行,支付方式,退票信息), 另外还有大量的查询信息(比如每次点击操作都会生成一个火车线路子集),按照传说中的每秒40w次点击(抢票软件的确给12306带来的太大的压力),可以想象其压力之大。此外,数据库中一般很少用位操作。  按照你的估算 ,估计你的系统一上线就垮了  
0
修改登录密码
修改登录密码

这文章的出发点还是码农观点,讨论的内容还是停留在细节实现,没有从总体上考虑架构的实现


skyer_XL
skyer_XL
这话说的 不从细节实现都是白扯
八风不动
八风不动
万丈高楼平地起,没有地基如何盖楼?如果底层数据就整出大型数据库,上层架构再怎么优化也无能为力。照那网上那篇文章的说法,每条线路的都有无数个相互关联的仓储库,有无数种出售方式,上层再怎么架构也是白搭。
0
yak
yak
这种结构就是车站x座位的二维表,再加上车次和趟次,一共是四维空间向量,对于单趟车的查询余票比较简单,但对于中转,改签之类的运算就大了,我认为还需要一个 辅助的站-站之间的实时连通图的数据结构,根据节点之间的时长和票价做权重,有些权重太小的中转线种没有实用价值,就在查询时可以忽略掉, 每次矩阵空间发生变化时,都实时更新这个站与站的连通图的数据,相当于搜索中的倒排表, 这样查询时就用站与站的参数可以直接得到余票数,
八风不动
八风不动
先查出多个换乘线路,然后再从引擎里查各部分有没有余票。
八风不动
八风不动
这个需求类似于公交换乘,可以参考公交换乘的算法进行运算,仓储引擎完成后,在仓储引擎的上层可以做换乘查询。要分层处理,别混在一起。
yak
yak
回复 @八风不动 : 不是同一趟车的查询怎么搞,比如拉萨到青岛,光用矩阵简单吗?
八风不动
八风不动
你这个越整越复杂了,中转改签都可以转化为车票的重新买卖操作,内核引擎只处理查询、买票、退票三种操作就够了,包括放票操作都可以用退票逻辑实现。
0
帖子列表
帖子列表
这种纸上谈兵的设计会被人喷死
八风不动
八风不动
这个位结构的存储模式就是针对那篇说12306仓储结构巨特殊,处理难度超级大的说法设计的,所以就是这个名字了。
帖子列表
帖子列表
但是我看不懂哦, 感觉好厉害的样子
帖子列表
帖子列表
不要叫12306, 叫高访问量系统的仓储结构设计还比较好
0
八风不动
八风不动

引用来自“eel”的答案

50M内存肯定是不够的。 你要记录的内容不仅有当前座位空闲信息 ,还要记录每张售出的票的信息(身份证编码 姓名 购买时间 ,支付时间,支付银行,支付方式,退票信息), 另外还有大量的查询信息(比如每次点击操作都会生成一个火车线路子集),按照传说中的每秒40w次点击(抢票软件的确给12306带来的太大的压力),可以想象其压力之大。此外,数据库中一般很少用位操作。  按照你的估算 ,估计你的系统一上线就垮了  

身份证,姓名,支付信息,帐号信息这些东西不是难点,交给外围系统就可以了,这里只实现难度最大的仓储引擎。系统要分层的,这里是最里面一层,你说的那些在外层。

另外:什么叫

比如每次点击操作都会生成一个火车线路子集

所有的线路子集都在树结构里存着了,就是那个3k的内存块。我觉得你没看前面那篇文章,所以断章取义了。

八风不动
八风不动
晕,你所谓的列出一张表是浏览器页面上列出一张表吧,那只是查询结果返回而已。
修改登录密码
修改登录密码
比如每次点击操作都会生成一个火车线路子集 意思就是说,我每次点击查询从北京到南京的线路,都会列出一张表,包含了所有从北京到南京的线路信息。 按照每秒40w次点击, 这些数据会耗费多少内存?
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部