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

八风不动 发布于 2014/01/27 21:52
阅读 1K+
收藏 8

    

    本文是前两篇文章的续篇,继续研讨12306网站特殊仓储结构的售票引擎设计。

    前文请看:12306 售票仓储结构的设计

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


    关于大并发时系统处理能力的问题,在这里详细说明一下解决方案。


    1、首先分析业务需求,查询操作是最多的,并发最大的,因此先讨论查询操作的并发处理。买票和退票的操作已经在前文中提过,买票就是一个节点余票数减1,另一个节点余票数加1,退票就是一个节点余票数加1,放票就是一个节点加N,底层引擎把它当退票操作来处理,这样就把问题简化了。


    2、一个进程处理一条路线。我们先给它命个名叫“售票进程”,售票进程首先启动两个线程,分别是“监听线程”和“回送线程”,监听线程监听一个TCP端口,接收查询、买票、退票等任务,回送线程通过TCP连接将结果队列中的查询或运算结果发送回去。


    3、监听线程维护多个任务队列,其中查询任务的多个队列用双向指针连成环状,监听线程收到查询任务后,从多个队列中选择未满的队列添加任务。队列全满时分配一个新的查询线程和新的任务队列。每个任务队列只在监听线程和一个查询线程间共享。分配任务时发现有任务队列为空的,就把该任务队列及其相关的查询线程回收,这样就有了动态适应能力。


    4、回送线程维护一个结果队列。多个查询线程的查询结果都放到结果队列里等待回送。此处回送线程和多个查询线程共享一个结果队列,如果造成了瓶颈,也可以改为多个任务队列,类似于前面的查询任务队列,每个队列只被两个线程共享。


    5、查询操作的具体流程:从根节点开始做两个long值的位运算,如果有票,就记录余票数量,然后找符合条件的子节点,再做位运算,有票就累计余票数量,依此类推。大多数情况下,只需10次以内的位运算就可以统计出某一路段的余票数量了。


    6、普通的余票查询和联程票的余票查询当作两个不同的查询任务类型来处理,只有在普通余票查询无票的情况下才去查询联程票,至于联程票是什么,请参考前一篇文章:续篇:12306 火车售票系统的仓储结构设计


    7、买票操作的任务分析:买票操作首先是查询有没有余票,如果有余票,还要找到余票售出后的对应节点。例如:(111,111,111,111,111)售出0-9站的车票后变成了(000,000,001,111,111)。售票操作的处理过程就是找到这两个节点,然后前一个节点余票数量减1,后一个节点余票数量加1,这就完成了一次售票操作。退票操作比买票操作更简单,它只涉及一个节点,找到相应的节点然后将余票数量加1即可。


    8、买票线程的并发设计:通过以上分析可以看出,买票操作其实很简单,速度也很快。后面还会指出,由于我们精心设计的树结构只占3k内存,整棵树都可以放到CPU内置的高速缓存里运算,不光是没有磁盘IO,运算时甚至内存IO都没有。从磁盘到主存,再从主存到高速缓存,这对系统处理速度的提升可以是几个数量级飞跃。至于为什么整棵树只有3k,请参考第一篇数据结构设计:12306 售票仓储结构的设计。另外,还可以参考Intel 酷睿i7的市场介绍,主频3.4G,三级高速缓存共8M。8M除以3k,那可以是多少条线路的仓储数据?全都可以在高速缓存里。


    9、基于以上分析,再参考Node.js这个单进程,单线程的成功案例,我们可以相信,单线程足以承载大并发的任务冲击。因此买票线程设计为单线程,这样就没有并发竞争,不需要内存锁,进一步提高了处理速度。至于这个单线程能承载多大的并发,我们可以参考Node.js的并发承载能力,再乘以1000,因为多数的Node.js测试都是基于数据库的,有磁盘IO,即便是没有磁盘IO的,也要乘以10~100,因为我们的目标数据没在内存里,都在高速缓存里。


    10、如果对买票线程的处理能力仍有疑虑,我们还有备用的手段就是外置的一个调度进程。每个售票进程开辟一块共享内存,定期写入本进程的当前状态,例如查询队列的数量、长度、结果队列的数量、长度、买票队列的长度等内容,调度进程对这块共享内存只读不写,所以也无需加锁。调度进程根据实际情况,可以选择提高买票线程的优先级,或者干脆将一个CPU内核单独绑定给买票线程。有了这样的一个调度进程作外部保障,再大的并发都可以轻松应对了。


    11、动态迁移:高效的动态迁移能力同样来自于前面精巧的存储结构设计,由于每条线路的仓储数据只占3k,当一台设备无法满足多条线路的并发处理时,可以把其中几条线路的处理任务迅速迁移到其他设备上,所需的操作仅仅是把当前的仓储状态(3k数据)传送到另一台设备上,然后在另一台设备上启动一个售票进程。然后对此线路的查询、处理请求就可以发送到新启用的设备上了。


加载中
0
张金富
张金富
快过年了 还在思考技术 不容易 帮顶一下!
八风不动
八风不动
:)
0
张金富
张金富

intel xeon处理器L3缓存多者能达到30M 

多路CPU 容量还可以翻倍

问题是如何把数据放到缓存里?

八风不动
八风不动
没有找到缓存操作的指令支持,但程序上的特意优化应可以提高特定小内存块的缓存驻留概率。
0
阿侯
阿侯
这三篇文章都很棒!膜拜中ing...
0
悠悠然然
悠悠然然
问题1:机器宕机了数据怎么办? 问题2:一台计算机计算量不够怎么扩展? 问题3:查询和订票退票之间的一致性如何保证? 你的前提是机器不会死机,数据在内存永远安全有效,当然快了。 实际上逻辑是这样的: 如果所有的问题都不考虑,性能可能如你所说。 但是考虑一个问题就会降低一、俩个数量级,考虑几个问题,你的方案就会被多米诺骨牌效应拍死。 所以,亲,不能太理想化。设计更多的不是解决没有问题或风险,而是解决出现问题,风险怎么办。 否则再快再好的方案都是个屁。 要考虑到每一秒几千万次的并发访问,你单机肯定无法满足。 所以必须以分布式,soa为基础来解决此类问题。
八风不动
八风不动
关于千万并发的问题,后面做了详细回复。简单说就是千万并发不是针对一条线路,而我们的单进程只处理一条线路,所以不是这么算的。
八风不动
八风不动
关于宕机问题,请看调度线程的共享内存设计。可以把仓储状态和结果队列设计成一个内存块,放到共享内存里,此时调度进程可以随时对仓储和售票状态进行备份,或者同步到其他存储介质。
八风不动
八风不动
计算量问题请看最后一节的动态迁移。查询和退票订票间的一致性问题:买票操作就是一个节点仓储减1,一个节点仓储加1,顶多是查询语句插在了两个操作中间,恰好查询的又是结果路段,所以余票数量少了一个,下一微秒再查询,这张票又有了。这种情况可以当作刚刚退回一张票来对待。
0
悠悠然然
悠悠然然
再假设你一台机器都好了,一次查询或定票,退票需要300字节,也就需要2.4kbits带宽,就按10000000并发,就是说需要24,000,000,000带宽。同学们帮我数数有没有错了位置。 哪里找这么一个机房呢? 当然你可以说不用300字节,那你自己给个数? 确实我们可以褒贬12306,但是不可以随便搞个所谓的方案就以为是正解。
八风不动
八风不动
查询任务就是一个路段掩码long(8字节),一个任务编号uint(4字节),和一些任务类型之类的简单信息(byte)。算上扩展余量也不超过30byte。买票任务类似,只是为提高运算效率增加了起始站点和终到站点两个掩码,用于处理边界情况。
八风不动
八风不动
没那么夸张,一次查询任务十几个字节,一次买/退票任务几十个字节,平均算30字节。你说一千万并发,就是每秒1000万个请求,首先这1000万请求不可针对同一条线路,所以假设不成立。假设全国的铁路线路有1000条,1000万条任务请求在不均匀分配的情况下,一条单独线路的瞬间并发任务请求量也不会超过10万,10万*30=3M带宽。
0
八风不动
八风不动

引用来自“悠悠然然”的答案

问题1:机器宕机了数据怎么办? 问题2:一台计算机计算量不够怎么扩展? 问题3:查询和订票退票之间的一致性如何保证? 你的前提是机器不会死机,数据在内存永远安全有效,当然快了。 实际上逻辑是这样的: 如果所有的问题都不考虑,性能可能如你所说。 但是考虑一个问题就会降低一、俩个数量级,考虑几个问题,你的方案就会被多米诺骨牌效应拍死。 所以,亲,不能太理想化。设计更多的不是解决没有问题或风险,而是解决出现问题,风险怎么办。 否则再快再好的方案都是个屁。 要考虑到每一秒几千万次的并发访问,你单机肯定无法满足。 所以必须以分布式,soa为基础来解决此类问题。

请看新文章。

0
一学修行
一学修行
内存锁争用,物理I0时间是瓶颈
返回顶部
顶部