12306 售票仓储结构的设计

八风不动 发布于 2014/01/22 20:25
阅读 2K+
收藏 19

前阵子看到一篇说12306类似于电商但仓储更复杂的文章,觉得有点意思。抽空琢磨了一下12306的特殊货物仓储,设计一下仓储管理的数据结构

1、大多数线路的总站点数不超过64个,即便有个别超过的,也可以单独处理,或者留出一个比特位表示是否有后续站点。

  2、一个long值(64bit)表示一张全程票,每一个比特位表示一个站点。初始值是全1,如果卖出了全程票,全部置0,如果卖的是半程票,就把沿途几个站点置0,其他站点依然是1,还可以继续卖。例如:111,111,111,111,111表示一张全程票,现在卖出了一张第三站到第9站的票变成了111,000,001,111,111,之后又卖出了第一站到第三站的票,变成了000,000,001,111,111,依此类推,直到全程车票卖完,该仓储的所有比特位全部变0。

  3、一趟列车有多个座位,就是有多张全程票,每张全程票用一个long表示。其实也不需要那么多内存,只要建一棵多叉树就可以了,按照一定的分叉规则把相同数值的全程票合并到一个节点下,每个节点记录一个掩码和剩余的车票数量。例如:全程票还剩121张,卖出了3-9车站的票还剩33张,卖出了0-9车站的票还剩68张,依此类推。

  4、在多叉树结构上实现几种算法,一种是统计n-m点可售车票的数量,一种是修改某节点的车票,例如把3-9节点上的余票减一,0-9节点加一,完成0-3站点的一张售票。还有一种则是退票,就是售票的逆运算。

  5、树合并算法:有的票售出了0-9,有的票剩下0-9,这两张票可以合成一张全程票,然后再灵活决定如何出售。

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

   使用以上数据结构,可以把所有的车票库存压缩到一个可承受的内存文件中。一趟车次是一棵树,1000趟车就是1000棵树,就算每棵树1M内存,1G内存也放下了。如果是多服务器并发处理,只需共享更新一个内存文件即可完成库存状态的同步。一切都在内存里,No Database,No File,No Disk,high speed。

    


加载中
0
无极小子
八风不动
八风不动
发个续篇地址:http://www.oschina.net/question/124158_142265
八风不动
八风不动
没看懂
十一文
十一文
这个容易实现
0
十一文
十一文
用位存储 这个 想法不错
IdleMan
IdleMan
不要以为都装到内存里面了就能高并发了。30T内存还装不下车票信息?
0
宏哥
宏哥

这种破讨论和讨论制造航空母舰有什么区别?

不如一起探讨一下, 如何用位存储解决航空母舰制造的问题

没有两个凡是的指导, 你们什么都不是 

八风不动
八风不动
捞干货,吹牛皮说大话谁都会,有本事就写点真东西。
0
吐槽的达达仔
吐槽的达达仔
感觉不错,有点意思~~
0
喻恒春
喻恒春

64bit(8字节)表示一个全程票非常关键

事实上一趟列车席位在2000以内,停靠站点最多的有50多个站点.

就算卖站票也不会超过65535(64k)

目前客运列车总数2000左右,就算按照10000计算.

64*8*10000=5G.

其实中心服务器要运算的数据量没有那么大.

核心要维护的数据量.其他辅助的服务器神马的各种问题,都是可以解决的.

八风不动
八风不动
你的计算方法是不加树的情况。我文中说了,掩码值相同的多个库存可以合并表示,这样1000张全程票只需一个节点就表示了(掩码+余量),所以实际用到的内存恐怕1G都不到。
八风不动
八风不动
是的,理论上各种车票的组合是几何级数,但实际出售的车票并不会占据所有可能性,因此设计时要根据实际情况选择合适的方案。
0
daishunchao
daishunchao
以前做啥项目忘记了,也是用0,1来进行位运算
0
灌直
灌直
做出来看看
八风不动
八风不动
如果有人付钱,我可以做个引擎出来,免费且开源。
0
Shazi199
Shazi199
没票,再好的设计也是白搭
0
风从东方来
风从东方来
如果要查询某站到某站是否有票,是不是就要要逐个遍历这趟车上每一张票的int64的每一位?
bovver
bovver
回复 @八风不动 : 开始时我理解错了,我大概明白你的意思了。
八风不动
八风不动
64bit源于火车售票的特殊性,一张全程票可以划分成多段出售。64bit可以用掩码运算快速判断中间某一段是否可售。
bovver
bovver
按照楼主的说法应该不用遍历每张票,而且枚举了所有的乘车段,并作为树的节点,每个节点存放票量信息。只是他开始说的64个bit就没什么意义了
0
汤医森
汤医森
解决不掉锁和带宽消耗,这种节省意义不大
八风不动
八风不动
锁分全局锁和局部锁,如果按路线分配将任务分配给多个服务器,各卖各的就不需要全局锁。
返回顶部
顶部