g*****g
发帖数: 34805 | 1 可惜的是12306跟你一样强耦合，17个节点都没做下来。就你那一个2万美刀的能行？
像你这样的傻逼就是丢了脸不认错，这个板上哪怕挺你的哪个不是说你撑得太过。
你丫也不撒泡尿照照镜子。一点server端经验都没有，上来就我这个东西宇宙第一。
65536 |
|
g*****g
发帖数: 34805 | 2 我受不了了。感情这班上一队人都是半路出家的吧，一点建模的意识都没有呀。
假定广州到北京线路叫A次，不失一般性假定就这么三段，每段100张票，数据库里三个
row
广州－》武汉 100
武汉－》郑州 100
郑州－》北京 100
你要广州到北京，就是每段1张，DB transaction，锁三个row出票，发现任何一段票数
小于0，roll back. 我实在想不明白这有啥难度。不就是三个商品，不允许超卖。你咋
组合都行。
后端是强耦合，前端没耦合。
C+ |
|
n****1
发帖数: 1136 | 3 你是不是中国人啊, 你不知道广州到北京中途至少30个站? 你准备分几段?
还有你的DB transaction怎么保证座位号一样? 如果人家买了广州到北京的票, 你不能
叫人家每过个站换个座位吧.
受不了就别回贴了 |
|
g*****g
发帖数: 34805 | 4 30站30段呀，事实上中国售票都是每站预留，所以都是不相干的票。A次广州出发，A次
郑州出发。
要不到春运，你要最大化，不是首发久没票了。
我再说一遍，后台不是实时出票，所以你大可以用最优的搜索算法来订票，这样的算法
有现成的。 |
|
|
T********i
发帖数: 2416 | 6 知道为啥飞机票都要临近登机才换登机牌么？
没有程序能预测未来。先给你票，最后时刻再优化座位是唯一的方法。
其实，火车票和飞机票，完全可以说一样的系统。 |
|
n****1
发帖数: 1136 | 7 车次与座位的分配与memory allocator非常相似, 需要保证memory defragmentation,
但复杂度更高.
每当收到一个内存申请(订票申请), allocator都需要先在已经分配的内存块(已经部分
出票的座位)中寻找空隙, 而且最好要找不大不小的空隙. 实在找不到了才向系统申请
新内存块(动用新座位). 这样才能保证所有座位的高效利用.
座位分配更麻烦在于, 内存申请只需大小合适就行, 座位分配还要指定在内存块中的位
置.
这个算法一点也不简单,学问大大的. |
|
T********i
发帖数: 2416 | 8 临出发换登机牌才能保证分配最优。缺点是额外手续带来的效率下降。
, |
|
g*****g
发帖数: 34805 | 9 只有你做client端的才会没这个常识。server端都是用户多，nasdaq那个match的算法
复杂度很高？你忽悠谁呀。 |
|
n****1
发帖数: 1136 | 10 首先不管技术可行性, 最后时刻才决定座位在政治上是行不通的, 媒体与群众无法接受
, 首长更加不会同意的. 不是说你的理念不先进, 而是人们已经习惯了, 不是那么好改
. 你能让全世界从qwerty键盘改成dvorak么?
乘客对座位要求很多的,一家人需要坐一起, 老人不喜欢上铺中铺.复杂度大大的.
程序员别整天想着改变世界运作方式, 以便自己编程简单点.
其次, 最后时刻分配座位, 往往发现座位不够, 或者需要乘客不停地中途换座位. 就像
内存分配一样, fragmentation只可以减少, 无法杜绝. 需要分配的内存永远大于需要
的内存.
机票简单多了, 因为每个订单都像一整块内存. 火车票则是一小部分. |
|
n****1
发帖数: 1136 | 11 我之所以同意你说业务是强耦合, 就是因为这些琐碎的考量.
如果做得像你这么简单, 那直接弱耦合上机群好了. |
|
T********i
发帖数: 2416 | 12 我的算法保证不会超卖。因此不会有超卖问题。
你的问题根本无解。人家支线挑好了座位，干线碎片就产生了。
铁道部的做法是高峰期只卖大区票。
数学上，啥能做，啥不能，很好证明。你再想想。 |
|
T********i
发帖数: 2416 | 13 弱耦合不行，一旦区段锁定一半机器死了，锁定的票就还不回来了。 |
|
n****1
发帖数: 1136 | 14 弱耦合可以像goodbug说的那样分库, 怎么分的话需要分析历史春运数据. 分好了死锁
问题就没啥大不了的了. 反正有一年的时间做规划, 分得再细都行.
如果你的方案无法实时分配座位, 我只能彻底推翻你的方案支持上机群了, 没准这种精
心设计的机群还能保证实时回复余票+实时分配座位. |
|
T********i
发帖数: 2416 | 15 根据我的经历。现在也是网上订票，然后必须到车站窗口取票。
为什么？就是要一个时间缓冲。
先确保你有票。再找机会优化。
人家铁道部也不傻。
能实时确认有票就很了不起了，而且是最重要的。 |
|
n****1
发帖数: 1136 | 16 还有, 最后关头分配座位这个总是要人来做的, 而且计算复杂度很高, 你还准备单机做
么?
你这叫为了面子好看避重就轻, "单机解决12306"只是标题党, 没解决实际问题. |
|
n****1
发帖数: 1136 | 17 不是吧, 我帮我爸妈买卧铺票, 下单时/付款前就知道是哪个座位了, 上中下铺也是说
好了再给钱的. |
|
T********i
发帖数: 2416 | 18 这个其实没你想的那么复杂。不应该是NP问题。
注意长途要优先分配。而且团体座位要集中，也要优先。剩下的随便，按照时间顺序好
了。
最终可能要认为微调，人民铁路为人民服务么。 |
|
|
T********i
发帖数: 2416 | 20 假定一条线路从始至终一共m个区段，n个座位。
初始化：
m个array：[0，n-1] with name SegMap
memset to 0
输入：
任何时候有人购买了区段a,b。a <= b && 0 <= a <= m - 1 && 0 <= b <= m-1。
初始化array t[0, n - 1] = sum of SeqMap[from a to b]
Search array t from 0 to n-1, find the first index with the minimum value V。
If the minimum V > 0 then repeat the algo on "subsegments with which the
seat has been taken"。
具体原则：
座位编号，每次都从第编号座位开始分配。
每次分配一个需要换座最少方案
注意，换座不可避免的。但是可证明这是实时算法中最优化的。
时间复杂度，空间复杂度：
O(m * n)
注意，本算法只能单线程实现。
但是可以scale out。对任何一个车次几百几千个座位，可以保证最差... 阅读全帖 |
|
|
m**********j
发帖数: 8645 | 22 你这个想法，初看起来似乎不错。
但对于在1秒钟之内会达到几百万次的查询来说，是非常无力的。
类比为现在有1万辆车准备过河，但只有2千辆可以过河，其他的8000辆连带司机都要被
炸死。
桥只有一座，你怎么修，也没用。
V。 |
|
|
n****1
发帖数: 1136 | 24 O(m * n)和单线程两个限制都不是很理想. 理论上至少有O(m * log(n))的算法, 而且
可以并行, 就像qsort能并行一样.
也许还能做到O(log(m) * log(n)), 但站点一般不会太大, 暂时可以不优化.
其实用啥C++/java, 单机数据库/机群数据库都无所谓, 模型和数据结构才是最重要的. |
|
g*****g
发帖数: 34805 | 25 每秒百万的请求过来时，让你往单机数据库里写helloworld都得挂，算法再好有啥用。
先把scalability解决了，算法是优化的事情。没听说过架构问题能用算法解决的。
的. |
|
T********i
发帖数: 2416 | 26 这种算法没研究过。貌似和qsort有类似之处。
像这种m，n都比较小的，并行可能反而代价更高。而且提高复杂度，不符合够用即行的
原则。
看你帖子，似乎也没有做过多核concurrency的工作。好像你说过担心过热损坏CPU之类
的话。其实我的系统，16个core有14个常年工作在100% CPU下。故意设计成这样的。
server设计的时候已经考虑好散热的问题。增加个1-200W功耗对我们来讲不算啥。
你的见识，应该另版上某些人汗颜。
的. |
|
m**********j
发帖数: 8645 | 27 记住，你说的这个每秒上百万次的请求。
每一个单独请求被处理后，数据库内跟这个单独请求相关联的信息都是要被重新更新的。
啥网站，都得挂。 |
|
n****1
发帖数: 1136 | 28 我没说过IO架构不重要, IO架构在很多不同行业里都有需求, 所以IO分布式解决方案都
很成熟了. 这方面知识已经渐渐成为IT行业基本要求了. 我并不同意老魏的单机IO打天
下在12306是最好方案, 但我不想纠结这个问题, 也不会老想证明别人是外行.
我只是认为车票分配算法是铁路行业的domain specific logic, 同样重要.而且这种东
西没法找其他行业的先例做借鉴, 所以值得深入探讨.
我只是想探讨些实际问题罢了, 没想和你打嘴仗. 还有这个贴子标题是"最优化的实时
分配车票座位的算法", 你要谈IO去其他帖子好了. |
|
n****1
发帖数: 1136 | 29
你这样搞, 离socket buffer overflow只有一步之遥啊. 也许你们搞trading的整天承
受风险已经惯了, 觉得这个没啥问题, 可首长不同意啊. 你的performance per dollar
再高人家也不买帐的.
n值小的话qsort未必最好,但一列车有一两千个座位, 一秒钟有几百万个request, 单机
很玄. 我还是宁可牺牲性能, 也要上并行保证稳定性的. qsort的并行版就是现在很火
的mapreduce. 这样我就可以只专注于算法/逻辑,不用重造轮子, 也不用担心
consistency/availability.
我的见识是挺浅薄的, 也没35岁, 你要鄙视我就鄙视好了. |
|
b*******s
发帖数: 5216 | 30 你们高频的比较猛，我们一般是每个core到70%左右，线程数是core数量 * 2 |
|
b*******s
发帖数: 5216 | 31 老魏的单机方案可以按车次切，一样可以分布，除了联票，车次间是低耦合
联票也有办法处理 |
|
n****1
发帖数: 1136 | 32 当然可以按车次切, 但老魏貌似现在还在坚持单机, 你确定他肯接受你的补丁?
其次, 进来的request太多, 就算是单机负责一列车也很悬的. qsort是能把一列车上的
不同座位分布到不同机器上去, 然后并行运算的, 我感觉放心点. |
|
b*******s
发帖数: 5216 | 33 o（m*n）会有一定压力，我说的还是那种存在很多碎片的o（1）的算法
而碎片从目前实践来说，最终都被短程乘客买走了，或者被你说的站票的坐了
所以基本上这个问题我把它的优先级降低，不放在当前必备功能里 |
|
|
n****1
发帖数: 1136 | 35 qsort不是mapreduce里面的helloworld么(除了更简单的word count)? 你说的是哪方面
稳定性? |
|
|
n****1
发帖数: 1136 | 37 O(N^2), 这个wikipedia上能搜到的. |
|
b*******s
发帖数: 5216 | 38 我知道，我只是问，你有没有考虑过这方面因素的影响 |
|
b*******s
发帖数: 5216 | 39 在实际系统中，算法稳定性有时是个工程问题，不只是定性就可以的 |
|
n****1
发帖数: 1136 | 40 1. 实践中qsort通常是表现非常好的, 我不觉得worst case O(n^2)有啥大不了的.
2. 我举qsort最关键在于提出了并行的可能性, 从而否定必须强耦合这个假设.
3. 肯定有比qsort更适合上mapreduce的方案, 好像有个terasort就很适合hadoop.
4. sort和寻找座位空隙还不是完全对应, 要思考的还有很多. 我是希望抛砖引玉, 不
是给终极方案. 这里面的水很深的. |
|
|
n****1
发帖数: 1136 | 42 ...
强耦合一直是老魏的假设, which comes from no where. 我现在说明了整个系统中计
算最复杂的地方能实现并行, that is it!
你对强耦合的假设怎么看? |
|
b*******s
发帖数: 5216 | 43 我同意老魏强耦合的观点，想听听你对强耦合是哪些因素在耦合的看法
因为你似乎也把强耦合当成了一个前提条件 |
|
n****1
发帖数: 1136 | 44 我是说希望做到实时计算余票量, 哪里用了强耦合的假设? 能把我说的话quote以下么?
强耦合是个负担, 不是啥好东西, 我为啥要把它当前提条件? |
|
b*******s
发帖数: 5216 | 45 ？ 可能我理解错你的意思了
如果没有强耦合，12306现在的方案显然就不是个最佳了
么? |
|
n****1
发帖数: 1136 | 46 我对老魏说的强耦合理解就是:
铁道业务逻辑只能同时利用一到两个线程. 如果你用了n个线程, 那么业务逻辑会使得
其中n-2个线程处于锁定状态. 所以机群不会比单机效率高.
现在不是用了17台机子么? 虽谈不上高度decouple,但离强耦合还是差很远吧. |
|
T********i
发帖数: 2416 | 47 我感觉我们沟通有问题。
我承认实时分配车票是最复杂的。
而且我在本主题第一贴已经说明"分配车票可以scale out”。也就是扔给其他机器去做。
其实我从来没纠结什么单机。只想说明有时候单机是最优解，没法选择。
至于强耦合。能避免就避免。这个我也没意见。但是有时后不能避免。
这个应用，什么是强耦合呢？我看只有抢票。这个抢票其实也能部分scale out，使用
state cache server先过滤一下实现的。
但是地但是，抢票核心还是强耦合的。我认为还是要用单机。
至于分配车票，又能够scale out了。
这是由于数据依赖性不同决定的。不以我们的意志为转移。
么? |
|
T********i
发帖数: 2416 | 48 大家工作的领域不一样。我理解你说的socket buffer overflow什么意思。但是我的系
统保持CPU 100%有我的道理。
强实时系统，唯一的不确定性就是memory cache miss。我的系统有很多buffer，不只
socket buffer。确保不会overflow很简单。就是确保consumer比producer消耗的快。
我的系统，consumer的速率比producer的速率高一个数量级。就是为了提供足够的余量
。因此有任何buffer overflow检测到，直接crash，因为肯定是程序写错了。
至于socket buffer，其实最容易控制。TCP本身就有flow control，UDP实现一个也简
单。实际应用中，我们的message rate的上限都是已知的。因此设计起来很容易。
至于保持CPU 100%，主要是消除context switch。这个只有我这种系统才有这种需求。
大家做事情的思路完全不一样，没有可比性。我是用效率换延迟。你们不可能这么用。
至于你的见识，我挺佩服的。
dollar |
|
T********i
发帖数: 2416 | 49 事实上，堆处理器核心也是一种scale out。
摩尔定律到了极限，要继续发展，就是要堆越来越多的核心。
多核和多机有啥区别？就是通信开销不一样么！多核有QPI bus。多机是ethernet或者
InfiniBand。
我的抢票核心，完全可以用多核。其实用多机可以不可以？也应该可以。但是通信的开
销并不低，因为要有distributed transaction manager。 |
|
n****1
发帖数: 1136 | 50 AIO+while loop check么? 有点像用户态自旋锁的感觉, 100%就这么来的吧 |
|
