老魏，终于放假了，我给你个多机版的，看看能不能秒你的计 - 未名空间MITBBS历史存档

老魏，终于放假了，我给你个多机版的，看看能不能秒你的计# Programming - 葵花宝典

h*u2015-12-21 08:12

1 楼

刚刚看完了Prometheus 3D,感觉三个字：爽爽爽。作为Alien系列从1到4，再从AVP1到2
各看了三遍以上的铁杆Alien粉，不得不说，Alien又回来了，完全扭转了两部AVP狗血
的颓势。整个戏惊悚，神秘感拿捏的很好，解迷略欠，剧情节奏很好，从头到尾一气呵
成。相较于前几部Alien,感觉Ridley Scott又回到了1979年，重拍了一部Alien 1.
先看情节设定，两部都是一票人马执行外太空任务，在不明星球遭到恐怖生物感染，全
舰阵亡，女主逃亡。Prometheus 由于在故事上复杂一些，多出了Engineer,但整体框架
不变。Alien 1里面Ripley拿着火焰枪逃亡，Prometheus女主拿消防斧逃亡。Alien 1基
本发生在飞船和Engineer老巢，侧重于飞船。Prometheus两者兼顾。人物设定上更是继
承了Alien1,2,4典型的人类船员+生化人的设定，而且生化人都是情节发展的关键人物
。跟1一样，Prometheus里面生化人设定为恶。
再看布景，虽然Prometheus多了些高科技，但是细看两者相似的情景太多了。比如图1
，飞船内部都是软塑料的墙。舱门就更像。图2，Engineer的大炮(?)以及典型的异形云
纹，大量分布在隧道内。图3，这生化人哥们儿脑袋也掉了，仔细看脖子伤口部位，跟
David脑袋被打掉后像不像？特别是那一个个小气囊。图4，Engineer的飞船出来了，一
个样的，呵呵。
要说场景要继承也就算了，Ridley连女主也要继承。我原来也纳闷怎么选女主这么个演
员，看完恍然大悟了。看图5，两人是不是姐妹俩? 尼玛，Ridley。

u*a2015-12-21 08:12

2 楼

似乎从前几个星期开始就算不清了……

q*c2015-12-21 08:12

3 楼

终于放假了，你们这些单机党也太猖獗了。有点时间给你们个堆机器版的。不过时
间很少所以剩余的自己脑补。
老魏你说的能达到你的单机版的 1/10 就了得了，你的也就几M/s. 你看看我这个版本。
用的全是 proven technology. 有点经验的一看就知道肯定能 work. 全套卖票。
当然你也说了，我这个酒不需要实现了，因为比较麻烦。不过你看看就知道肯定无
问题
实现的和你那个功能完全一样。
前段，无状态的 web server. 接受订票. 受到订票直接转到相应的中间集群。
中间，是按照用户 id hash 的用户数据库群＋用户 controller.
收到订单然后在数据库中产生该用户的订票信息. 比如有三张连票，
userid, orderID, start1, end1, status = processing
userid, orderID, start2, end2, status = processing
userid, orderID, start3, end3, status = processing
后端，是按照车次hash 的车次数据库群，一个数据库存一个车次，最开始是 5000
张起始直到终点站票。
然后中间服务器按照从小到大的顺序开始去后端数据库锁票， select top 1 * for
update
where start <= order.start and end >= order.end and date.Day = order.day...
etc . 因为是row lock 所以对perf 没啥影响。
所有连票都锁到，开始处理。根据起始终点站不同，每次操作可能在该车次内产生
0，1 ， 2 张新票。然后用 transaction 搞定一个车次， status = done. 然后操作
下一个车次。
一个用户订票全部车次操作完成，结束返回前段。任何异常情况，返回失败，已经
索票的数据库自动回卷(rollback 或者断电或者whater, 最后 timeout connection)。
如果断电等，重启的时候扫描数据库，对于所有没有完全 done 的 order，全部回
卷。因为是数据库，这些都是自动功能， well tested in real world.
最多加个卡三抓，当后端车票数据库买完一个车次就 mark. 别人就不用继续查询该数
据库了。
这样前段，中间都是无限 scale. 最后的车票数据库可以有最多 3000/5000 个
partition (和车次数目一致）。
－－－－ perf analysis ----
基本出票速度就是后端数据库出票速度。开始有票的时候，或者不是特别特别忙的时
候，基本没 race condition. 最大perf 就是 3000 个数据库同时出票，这种极其简
单的schema，调整调整搞到几万 tps 还是行的。就算 1 万的下限，也是 3000 万
张票每秒。最后一张两张票的时候会有冲突，但是因为顺序锁票，不会出错，毫秒
内就把车次卖光，也就有极其微小的瞬时不公平。
这个可是结结实实的 perf. 用的都是 proven tech. 保证能做到的东西。
老魏这个 perf 比得上你的单机版计算器 1/10? 如果用牛逼服务器，上 ssd 搞到 10
万 tps, 这就是 3亿票／s 的 perf.. :)

l*u2015-12-21 08:12

4 楼

好文，有对比图就更爽了

u*a2015-12-21 08:12

5 楼

似乎从前几个星期开始就算不清了……

T*i2015-12-21 08:12

6 楼

老Q，你仔细想想吧。系统的性能要按照最差情况来衡量才行。
如果数据之间没有依赖性的话，我的算法上72核单机性能是多少？你自己算算。
你的这个，是可靠性比我的高？还是价格比我的方案便宜？还是你代码的行数比我的少
？

C*y2015-12-21 08:12

7 楼

按老头自己的说法，alien 1就是个B级片，几号人和一个怪物在一个屋子里的故事。。
。。
本来要在lv426上多花笔墨的(据说本来圆金字塔那时就要拍得)，一个SJ的‘大炮’花
费就把fox吓死了，赶快砍砍砍，就成B级片了。不过应该是B级片里的战斗机？ lol

到2

【在 h*******u 的大作中提到】

: 刚刚看完了Prometheus 3D,感觉三个字：爽爽爽。作为Alien系列从1到4，再从AVP1到2
: 各看了三遍以上的铁杆Alien粉，不得不说，Alien又回来了，完全扭转了两部AVP狗血
: 的颓势。整个戏惊悚，神秘感拿捏的很好，解迷略欠，剧情节奏很好，从头到尾一气呵
: 成。相较于前几部Alien,感觉Ridley Scott又回到了1979年，重拍了一部Alien 1.
: 先看情节设定，两部都是一票人马执行外太空任务，在不明星球遭到恐怖生物感染，全
: 舰阵亡，女主逃亡。Prometheus 由于在故事上复杂一些，多出了Engineer,但整体框架
: 不变。Alien 1里面Ripley拿着火焰枪逃亡，Prometheus女主拿消防斧逃亡。Alien 1基
: 本发生在飞船和Engineer老巢，侧重于飞船。Prometheus两者兼顾。人物设定上更是继
: 承了Alien1,2,4典型的人类船员+生化人的设定，而且生化人都是情节发展的关键人物
: 。跟1一样，Prometheus里面生化人设定为恶。

a*y2015-12-21 08:12

8 楼

我也发现了。很坑爹。
不过好像是在sync的时候出错。

【在 u******a 的大作中提到】

: 似乎从前几个星期开始就算不清了……

T*i2015-12-21 08:12

9 楼

你买跨车次联票，需要Distributed Transaction，这笔帐我还没和你算呢。

b*d2015-12-21 08:12

10 楼

b级片是按预算划分的？

【在 C******y 的大作中提到】

: 按老头自己的说法，alien 1就是个B级片，几号人和一个怪物在一个屋子里的故事。。
: 。。
: 本来要在lv426上多花笔墨的(据说本来圆金字塔那时就要拍得)，一个SJ的‘大炮’花
: 费就把fox吓死了，赶快砍砍砍，就成B级片了。不过应该是B级片里的战斗机？ lol
:
: 到2

b*n2015-12-21 08:12

11 楼

这是苹果的绝密技术，一个比特可以存多个数据。

【在 u******a 的大作中提到】

: 似乎从前几个星期开始就算不清了……

g*g2015-12-21 08:12

12 楼

没联票就没有什么scale的难度，本来就是如此。

本。

【在 q*c 的大作中提到】

: 终于放假了，你们这些单机党也太猖獗了。有点时间给你们个堆机器版的。不过时
: 间很少所以剩余的自己脑补。
: 老魏你说的能达到你的单机版的 1/10 就了得了，你的也就几M/s. 你看看我这个版本。
: 用的全是 proven technology. 有点经验的一看就知道肯定能 work. 全套卖票。
: 当然你也说了，我这个酒不需要实现了，因为比较麻烦。不过你看看就知道肯定无
: 问题
: 实现的和你那个功能完全一样。
: 前段，无状态的 web server. 接受订票. 受到订票直接转到相应的中间集群。
: 中间，是按照用户 id hash 的用户数据库群＋用户 controller.
: 收到订单然后在数据库中产生该用户的订票信息. 比如有三张连票，

L*t2015-12-21 08:12

13 楼

超强科研精神！！

到2

【在 h*******u 的大作中提到】

: 刚刚看完了Prometheus 3D,感觉三个字：爽爽爽。作为Alien系列从1到4，再从AVP1到2
: 各看了三遍以上的铁杆Alien粉，不得不说，Alien又回来了，完全扭转了两部AVP狗血
: 的颓势。整个戏惊悚，神秘感拿捏的很好，解迷略欠，剧情节奏很好，从头到尾一气呵
: 成。相较于前几部Alien,感觉Ridley Scott又回到了1979年，重拍了一部Alien 1.
: 先看情节设定，两部都是一票人马执行外太空任务，在不明星球遭到恐怖生物感染，全
: 舰阵亡，女主逃亡。Prometheus 由于在故事上复杂一些，多出了Engineer,但整体框架
: 不变。Alien 1里面Ripley拿着火焰枪逃亡，Prometheus女主拿消防斧逃亡。Alien 1基
: 本发生在飞船和Engineer老巢，侧重于飞船。Prometheus两者兼顾。人物设定上更是继
: 承了Alien1,2,4典型的人类船员+生化人的设定，而且生化人都是情节发展的关键人物
: 。跟1一样，Prometheus里面生化人设定为恶。

a*y2015-12-21 08:12

14 楼

用量子物理可以做到么

【在 b****n 的大作中提到】

: 这是苹果的绝密技术，一个比特可以存多个数据。

g*y2015-12-21 08:12

15 楼

没看懂你是怎么保证公平性的。能不能就下面例子解释一下：
1. A最先提交买票请求，买1， 3，5次车的联票。
2. B紧接着要买1次车票。
3. C也要求买1次车票。
如果A先锁了1次车的最后一张票，然后去要3次和5次车票。B需不需要等A的联票结果
出来再开始尝试锁票？
如果等，出票速度可能会相当慢。
如果不等，那B就直接得到没票的回答。然后A的3次车或5次车没票，rollback 1次车票，
C正好赶上就买走了。而B就很惨了，只能重新排到队尾去递交新的request。

本。

【在 q*c 的大作中提到】

: 终于放假了，你们这些单机党也太猖獗了。有点时间给你们个堆机器版的。不过时
: 间很少所以剩余的自己脑补。
: 老魏你说的能达到你的单机版的 1/10 就了得了，你的也就几M/s. 你看看我这个版本。
: 用的全是 proven technology. 有点经验的一看就知道肯定能 work. 全套卖票。
: 当然你也说了，我这个酒不需要实现了，因为比较麻烦。不过你看看就知道肯定无
: 问题
: 实现的和你那个功能完全一样。
: 前段，无状态的 web server. 接受订票. 受到订票直接转到相应的中间集群。
: 中间，是按照用户 id hash 的用户数据库群＋用户 controller.
: 收到订单然后在数据库中产生该用户的订票信息. 比如有三张连票，

d*h2015-12-21 08:12

16 楼

最喜欢的其实就是alien 1, 其他的后面的2，3，4都比较扯淡。

p*22015-12-21 08:12

17 楼

从设计上来说，
B直接没票的情况不但公平，而且对出票速度有利
因为如果说等A，那就要设一个max等待值（比如说3秒），
无论这个时间多少，它终究会过去的，>maxValue之后的1毫秒，
C上来拿到1次票，对B来说和直接没票是一样的公正性，
但是却牺牲了N个人的时间，所以，我个人感觉是直接没票。
或者在等票这块可以写个公式处理，
等票数：RequestCount
锁票数：HoldCount
等待时间：TimeOfWaiting
最大锁票时间：maxHoldTime(锁票不买的最大值)
TimeOfWaiting=f(RequestCount,HoldCount,maxHoldTime)
根据实际情况加个参数，动态load一个等待时间，相对比较好一些。
类似1万等票，10张锁票的情况，直接过，
如果10张等票，1万锁票，那可以考虑等一会儿，
具体参数，肯定要实际情况中调整。

票，

【在 g*****y 的大作中提到】

: 没看懂你是怎么保证公平性的。能不能就下面例子解释一下：
: 1. A最先提交买票请求，买1， 3，5次车的联票。
: 2. B紧接着要买1次车票。
: 3. C也要求买1次车票。
: 如果A先锁了1次车的最后一张票，然后去要3次和5次车票。B需不需要等A的联票结果
: 出来再开始尝试锁票？
: 如果等，出票速度可能会相当慢。
: 如果不等，那B就直接得到没票的回答。然后A的3次车或5次车没票，rollback 1次车票，
: C正好赶上就买走了。而B就很惨了，只能重新排到队尾去递交新的request。
:

m*p2015-12-21 08:12

18 楼

好文mark

到2

【在 h*******u 的大作中提到】

: 刚刚看完了Prometheus 3D,感觉三个字：爽爽爽。作为Alien系列从1到4，再从AVP1到2
: 各看了三遍以上的铁杆Alien粉，不得不说，Alien又回来了，完全扭转了两部AVP狗血
: 的颓势。整个戏惊悚，神秘感拿捏的很好，解迷略欠，剧情节奏很好，从头到尾一气呵
: 成。相较于前几部Alien,感觉Ridley Scott又回到了1979年，重拍了一部Alien 1.
: 先看情节设定，两部都是一票人马执行外太空任务，在不明星球遭到恐怖生物感染，全
: 舰阵亡，女主逃亡。Prometheus 由于在故事上复杂一些，多出了Engineer,但整体框架
: 不变。Alien 1里面Ripley拿着火焰枪逃亡，Prometheus女主拿消防斧逃亡。Alien 1基
: 本发生在飞船和Engineer老巢，侧重于飞船。Prometheus两者兼顾。人物设定上更是继
: 承了Alien1,2,4典型的人类船员+生化人的设定，而且生化人都是情节发展的关键人物
: 。跟1一样，Prometheus里面生化人设定为恶。

q*c2015-12-21 08:12

19 楼

可靠性比你的高啊！你一坏了就全完了，我这个坏了别的路线都没事。可靠性强你
3000 倍。
你上 72 核我也上 72 啊，照样比你快 10 倍 100 倍。
唯一就是要大干快上的话，就是比你的贵。
至于代码，我那全是轮子，什么 jdbc, zookeeper 随便上。

【在 T********i 的大作中提到】

: 老Q，你仔细想想吧。系统的性能要按照最差情况来衡量才行。
: 如果数据之间没有依赖性的话，我的算法上72核单机性能是多少？你自己算算。
: 你的这个，是可靠性比我的高？还是价格比我的方案便宜？还是你代码的行数比我的少
: ？

q*c2015-12-21 08:12

20 楼

算了，你仔细看看我的方案
用户数据库的 acim 保证了连票 eventual consistency.
你也完全一样，靠 log 保证嘛。

【在 T********i 的大作中提到】

: 你买跨车次联票，需要Distributed Transaction，这笔帐我还没和你算呢。

b*i2015-12-21 08:12

21 楼

有道理，估计能差几毫秒？
老魏的前面的流进来也分不清楚几毫秒的差距吧

【在 p**2 的大作中提到】

: 从设计上来说，
: B直接没票的情况不但公平，而且对出票速度有利
: 因为如果说等A，那就要设一个max等待值（比如说3秒），
: 无论这个时间多少，它终究会过去的，>maxValue之后的1毫秒，
: C上来拿到1次票，对B来说和直接没票是一样的公正性，
: 但是却牺牲了N个人的时间，所以，我个人感觉是直接没票。
: 或者在等票这块可以写个公式处理，
: 等票数：RequestCount
: 锁票数：HoldCount
: 等待时间：TimeOfWaiting

q*c2015-12-21 08:12

22 楼

算了，你仔细看看我的方案
用户数据库的 acim 保证了连票 eventual consistency.
你也完全一样，靠 log 保证嘛。

【在 T********i 的大作中提到】

: 你买跨车次联票，需要Distributed Transaction，这笔帐我还没和你算呢。

q*c2015-12-21 08:12

23 楼

等啥，不忙的时候根本不是问题，忙的时候下个 order 进来马上搞定。

【在 p**2 的大作中提到】

: 从设计上来说，
: B直接没票的情况不但公平，而且对出票速度有利
: 因为如果说等A，那就要设一个max等待值（比如说3秒），
: 无论这个时间多少，它终究会过去的，>maxValue之后的1毫秒，
: C上来拿到1次票，对B来说和直接没票是一样的公正性，
: 但是却牺牲了N个人的时间，所以，我个人感觉是直接没票。
: 或者在等票这块可以写个公式处理，
: 等票数：RequestCount
: 锁票数：HoldCount
: 等待时间：TimeOfWaiting

q*c2015-12-21 08:12

24 楼

我都说了绝对的公平毫无意义， 99.9% 的票都是公平的，最后一张票有可能有点次序
问题。
这根本不是问题。

票，

【在 g*****y 的大作中提到】

: 没看懂你是怎么保证公平性的。能不能就下面例子解释一下：
: 1. A最先提交买票请求，买1， 3，5次车的联票。
: 2. B紧接着要买1次车票。
: 3. C也要求买1次车票。
: 如果A先锁了1次车的最后一张票，然后去要3次和5次车票。B需不需要等A的联票结果
: 出来再开始尝试锁票？
: 如果等，出票速度可能会相当慢。
: 如果不等，那B就直接得到没票的回答。然后A的3次车或5次车没票，rollback 1次车票，
: C正好赶上就买走了。而B就很惨了，只能重新排到队尾去递交新的request。
:

T*i2015-12-21 08:12

25 楼

你再想想？
我的怎么叫一坏全完了？我可以有无数台hotstandby的。你这个坏一台，一条线路就没
了。
而且我联票也能保证5M以上，你那个能保证么？

【在 q*c 的大作中提到】

: 可靠性比你的高啊！你一坏了就全完了，我这个坏了别的路线都没事。可靠性强你
: 3000 倍。
: 你上 72 核我也上 72 啊，照样比你快 10 倍 100 倍。
: 唯一就是要大干快上的话，就是比你的贵。
: 至于代码，我那全是轮子，什么 jdbc, zookeeper 随便上。

q*c2015-12-21 08:12

26 楼

当然可以啊，你仔细想想。除了最后一张，都很快。其实最后一张还是快，就是可能
要折腾两下。
你有多少 standby 我每个分区就可以照样办理。稳定性还是比你强几千倍。
你没搞过这个，连票根本不是事情。我给亚麻做的上亿美元的项目， pepsi 的
promotion, 几千亿的交易数目，就这样搞的，根本没事。 diatributed txn 最重要的
就是保证有个地方是 truth. 我这里 order leveL truth 在用户数据库，票 level
在车次数据库。
你仔细看看我的方案在说。我这个除了花钱多，别的样样秒你单机党 1～2 数量级。
而实战里面，硬件钱就不是个事情。这不是你那小 startup, 这是中国14亿人的铁道
部。

【在 T********i 的大作中提到】

: 你再想想？
: 我的怎么叫一坏全完了？我可以有无数台hotstandby的。你这个坏一台，一条线路就没
: 了。
: 而且我联票也能保证5M以上，你那个能保证么？

q*c2015-12-21 08:12

27 楼

老魏你这话显然就是根本没看我的方案。
我那云方案下，单票连票都没啥差别，无非是用户数据库里面插入一张票还是 n 张票
而已。
你还号称连机版本做不了你的单机计数器的 1/10吗？哥为啥比你快？因为哥花的钱多
啊，哈哈哈。

【在 T********i 的大作中提到】

: 你再想想？
: 我的怎么叫一坏全完了？我可以有无数台hotstandby的。你这个坏一台，一条线路就没
: 了。
: 而且我联票也能保证5M以上，你那个能保证么？

q*c2015-12-21 08:12

28 楼

C. 还拍啥队？ b 买了就没票了

票，

【在 g*****y 的大作中提到】

: 没看懂你是怎么保证公平性的。能不能就下面例子解释一下：
: 1. A最先提交买票请求，买1， 3，5次车的联票。
: 2. B紧接着要买1次车票。
: 3. C也要求买1次车票。
: 如果A先锁了1次车的最后一张票，然后去要3次和5次车票。B需不需要等A的联票结果
: 出来再开始尝试锁票？
: 如果等，出票速度可能会相当慢。
: 如果不等，那B就直接得到没票的回答。然后A的3次车或5次车没票，rollback 1次车票，
: C正好赶上就买走了。而B就很惨了，只能重新排到队尾去递交新的request。
:

q*c2015-12-21 08:12

29 楼

b . 还拍啥队？ c 买了就没票了
如果还有票， b C. 都能买到。就是我说的只有到了最后一张票才有一点点点次序问
题，而这在实际中根本不是问题。

票，

【在 g*****y 的大作中提到】

: 没看懂你是怎么保证公平性的。能不能就下面例子解释一下：
: 1. A最先提交买票请求，买1， 3，5次车的联票。
: 2. B紧接着要买1次车票。
: 3. C也要求买1次车票。
: 如果A先锁了1次车的最后一张票，然后去要3次和5次车票。B需不需要等A的联票结果
: 出来再开始尝试锁票？
: 如果等，出票速度可能会相当慢。
: 如果不等，那B就直接得到没票的回答。然后A的3次车或5次车没票，rollback 1次车票，
: C正好赶上就买走了。而B就很惨了，只能重新排到队尾去递交新的request。
:

N*m2015-12-21 08:12

30 楼

b也买联票呢？也可能rollback吧

【在 q*c 的大作中提到】

: C. 还拍啥队？ b 买了就没票了
:
: 票，

q*c2015-12-21 08:12

31 楼

可能啊，然后？然后下面几千个 order 每个都精心设计的来回这样交叉着回滚？
实际中不要 1 豪秒就结束了，根本不会有问题。只要保证正确性就行了，就是说你买
到了票你就一定有。

【在 N*****m 的大作中提到】

: b也买联票呢？也可能rollback吧

N*m2015-12-21 08:12

32 楼

如果是这样，那很简单，排队都没必要了
所有请求lb到每个server直接抢，直接mark每个车次（aka分布式计数器）好了
失败了，就是买票失败，踢走

【在 q*c 的大作中提到】

: 可能啊，然后？然后下面几千个 order 每个都精心设计的来回这样交叉着回滚？
: 实际中不要 1 豪秒就结束了，根本不会有问题。只要保证正确性就行了，就是说你买
: 到了票你就一定有。

q*c2015-12-21 08:12

33 楼

问题是这多机版的不怕连票，没影响，只有老魏那个单机计数器一旦连票，才会有
perf 问题，呵呵。
这些同学竟然不相信钱猛鸡多是王道，妄图想以少胜多这种神话。

【在 g*****g 的大作中提到】

: 没联票就没有什么scale的难度，本来就是如此。
:
: 本。

q*c2015-12-21 08:12

34 楼

我就是这办法。只是要考虑后端车次最多 partiton 5000 个，所以最忙的时候还是要
稍微排一下队。

【在 N*****m 的大作中提到】

: 如果是这样，那很简单，排队都没必要了
: 所有请求lb到每个server直接抢，直接mark每个车次（aka分布式计数器）好了
: 失败了，就是买票失败，踢走

T*i2015-12-21 08:12

35 楼

你的这个方案，不是我和古德霸赌的那个。我们打赌的是有票必须出票。你这个其实做
不到。你要relax需求，可以打破数据耦合。
即使如此，如果请求都是同一个车次，你的throughput顶多10万而已。
关键你还是没看懂我的设计，你的可靠性不可能比我的好。至于什么可靠性高5000倍是
臆想而已。
照你这么做，我还是只需要你1/100的机器，能提供大得多的throughput。
你就说说你的可靠性是我的5000倍咋算出来的就好了。

q*c2015-12-21 08:12

36 楼

我没管你和老霸堵的啥，我这个是车票解决方案。就从最开始火车票问题。
你说的那种特殊情况，全中国人要商量好顺次买第一车，第二。。等，这可能嘛？就算
这样，这种瞬间一秒后也就不存在了。
可靠性我给说错了，应该说，硬件发生问题的时候，这多机办法损失是你单机版的几
千分之一。
最后你其实要上规模，其实也还是要 partition. 只是你那办法是自己的，看着就不靠
谱，全靠你的人品，我这办法是通用的，看着就靠谱的多。

【在 T********i 的大作中提到】

: 你的这个方案，不是我和古德霸赌的那个。我们打赌的是有票必须出票。你这个其实做
: 不到。你要relax需求，可以打破数据耦合。
: 即使如此，如果请求都是同一个车次，你的throughput顶多10万而已。
: 关键你还是没看懂我的设计，你的可靠性不可能比我的好。至于什么可靠性高5000倍是
: 臆想而已。
: 照你这么做，我还是只需要你1/100的机器，能提供大得多的throughput。
: 你就说说你的可靠性是我的5000倍咋算出来的就好了。

p*22015-12-21 08:12

37 楼

请教个问题：为啥最后数据库群要1个车次一个数据库？

本。

【在 q*c 的大作中提到】

: 终于放假了，你们这些单机党也太猖獗了。有点时间给你们个堆机器版的。不过时
: 间很少所以剩余的自己脑补。
: 老魏你说的能达到你的单机版的 1/10 就了得了，你的也就几M/s. 你看看我这个版本。
: 用的全是 proven technology. 有点经验的一看就知道肯定能 work. 全套卖票。
: 当然你也说了，我这个酒不需要实现了，因为比较麻烦。不过你看看就知道肯定无
: 问题
: 实现的和你那个功能完全一样。
: 前段，无状态的 web server. 接受订票. 受到订票直接转到相应的中间集群。
: 中间，是按照用户 id hash 的用户数据库群＋用户 controller.
: 收到订单然后在数据库中产生该用户的订票信息. 比如有三张连票，

n*s2015-12-21 08:12

38 楼

这个方案的perf蛮依赖pubsub的throughput和delay的（假设你的方案是让web server
把信息扔到pubsub里，然后subscriber捡起来之后一个个的commit）。尤其突然几亿人同
时抢票，pubsub里肯定一下就茫茫多的message，速度会越来越慢。
不过当然比单机版好多了。而且似乎也没比这更好的解决方案。

本。

【在 q*c 的大作中提到】

: 终于放假了，你们这些单机党也太猖獗了。有点时间给你们个堆机器版的。不过时
: 间很少所以剩余的自己脑补。
: 老魏你说的能达到你的单机版的 1/10 就了得了，你的也就几M/s. 你看看我这个版本。
: 用的全是 proven technology. 有点经验的一看就知道肯定能 work. 全套卖票。
: 当然你也说了，我这个酒不需要实现了，因为比较麻烦。不过你看看就知道肯定无
: 问题
: 实现的和你那个功能完全一样。
: 前段，无状态的 web server. 接受订票. 受到订票直接转到相应的中间集群。
: 中间，是按照用户 id hash 的用户数据库群＋用户 controller.
: 收到订单然后在数据库中产生该用户的订票信息. 比如有三张连票，

z*e2015-12-21 08:12

39 楼

现在没有人这么搞了
不服来拼毒誓
上个世纪的老头子就不要老拿什么“无数个hotstandby”来现了
现实中有一个hotstandby就不错了
我就没见过有两个及其以上数量的hotstandby

【在 T********i 的大作中提到】

: 你再想想？
: 我的怎么叫一坏全完了？我可以有无数台hotstandby的。你这个坏一台，一条线路就没
: 了。
: 而且我联票也能保证5M以上，你那个能保证么？

b*s2015-12-21 08:12

40 楼

你做一个演示一下性能好了，比如一百列车

【在 q*c 的大作中提到】

: 我没管你和老霸堵的啥，我这个是车票解决方案。就从最开始火车票问题。
: 你说的那种特殊情况，全中国人要商量好顺次买第一车，第二。。等，这可能嘛？就算
: 这样，这种瞬间一秒后也就不存在了。
: 可靠性我给说错了，应该说，硬件发生问题的时候，这多机办法损失是你单机版的几
: 千分之一。
: 最后你其实要上规模，其实也还是要 partition. 只是你那办法是自己的，看着就不靠
: 谱，全靠你的人品，我这办法是通用的，看着就靠谱的多。

z*e2015-12-21 08:12

41 楼

票，
逗了，你以为老魏的方案能保证？
到核心机的序列就能说明b比c先？
外围机也是一大群，每个外围机到核心机的顺序是上帝决定的
其实也是一种随机数，没有半毛钱意义
早就说了，这种无法保证的随机性，直接假设在同一时间点（段，如果非要计较的话）
内到达外围机的请求是同一个优先级，然后自己想办法作出比较合理的安排
也就是想办法找出最优解，这才是programming的问题
而不是十分愚蠢滴把核心机的网卡做成一个排队机

【在 g*****y 的大作中提到】

: 没看懂你是怎么保证公平性的。能不能就下面例子解释一下：
: 1. A最先提交买票请求，买1， 3，5次车的联票。
: 2. B紧接着要买1次车票。
: 3. C也要求买1次车票。
: 如果A先锁了1次车的最后一张票，然后去要3次和5次车票。B需不需要等A的联票结果
: 出来再开始尝试锁票？
: 如果等，出票速度可能会相当慢。
: 如果不等，那B就直接得到没票的回答。然后A的3次车或5次车没票，rollback 1次车票，
: C正好赶上就买走了。而B就很惨了，只能重新排到队尾去递交新的request。
:

T*i2015-12-21 08:12

42 楼

你还是没看懂我的方案么？
你说：硬件发生问题的时候，这多机办法损失是你单机版的几千分之一。
请你说清楚。我的单机核心硬件出问题，hot standby马上顶上，损失是多少？哪里来
的100%的损失？
你这个办法这么好，咋不用来卖股票？人家12306也没用你的办法。

【在 q*c 的大作中提到】

: 我没管你和老霸堵的啥，我这个是车票解决方案。就从最开始火车票问题。
: 你说的那种特殊情况，全中国人要商量好顺次买第一车，第二。。等，这可能嘛？就算
: 这样，这种瞬间一秒后也就不存在了。
: 可靠性我给说错了，应该说，硬件发生问题的时候，这多机办法损失是你单机版的几
: 千分之一。
: 最后你其实要上规模，其实也还是要 partition. 只是你那办法是自己的，看着就不靠
: 谱，全靠你的人品，我这办法是通用的，看着就靠谱的多。

z*e2015-12-21 08:12

43 楼

12306当然用的就是楼主的方法
新闻上早就有了，所以到处都可以搜索到hazelcast
这都看不懂，上个世纪的老年人真是没救了
投行08年之后技术就落伍了，别现了

【在 T********i 的大作中提到】

: 你还是没看懂我的方案么？
: 你说：硬件发生问题的时候，这多机办法损失是你单机版的几千分之一。
: 请你说清楚。我的单机核心硬件出问题，hot standby马上顶上，损失是多少？哪里来
: 的100%的损失？
: 你这个办法这么好，咋不用来卖股票？人家12306也没用你的办法。

z*e2015-12-21 08:12

44 楼

12306用的是gemfire
全球金钱交易，比如银联，用的是hazelcast
visa好像用的也是hazelcast
这个时候还有人在琢磨用单机＋热备
老年人果然是够老

z*e2015-12-21 08:12

45 楼

大规模、大数据量、高并发企业级或者互联网应用为了解决数据缓存、降低数据库负载
、提高查询性能等突出问题，很多采用了Hazelcast或者Oracle Coherence或者GemFire
（比如12306网站）或者目前应用越来越广泛的Redis等缓存技术
所以说，现在还在琢磨如何省机器钱的人明显思想上落伍了，自大得要死，还热备，上
个世纪的破烂构架，不知道有啥好吹的，in memory db现在满大街都是，都快烂大街了
，还在做计数器，看了真是很有喜感，所以说，不弄vert.x，能行吗？vert.x的
cluster模式就是hazelcast，也支持redis这些，比起卖机器来说，vert.x实在是可爱
太多

z*e2015-12-21 08:12

46 楼

老魏的所谓核心机，其实就是主机的简化
性能差了几个档次，所以只能跑一些非常简单的操作
比如各种int操作，远没有主机靠谱
但是从整体结构上看，所谓的核心机就是老魏版的主机
老魏用一个破烂机器替换掉主机
以节省机器的钱，真是寒碜，堂堂一个国家铁道部
连个主机都用不起，还要省这点钱，关键是真能省下来么？
卖机器的人一般都是鼠目寸光
人工的费用远大于软件的费用远大于硬件的费用
硬件每年都在贬值，要多无聊才会去省机器的钱啊？
斤斤计较算半死，过两年，不用算一样便宜下来

z*e2015-12-21 08:12

47 楼

单机热备n>2我费尽心思
总算找到一个n＝4的例子
08年时候n＝3
已经是全球领先了
啧啧，这年头，老年人伤不起啊
http://www.caacnews.com.cn/2011np/20110510/169141.html

【在 T********i 的大作中提到】

: 你还是没看懂我的方案么？
: 你说：硬件发生问题的时候，这多机办法损失是你单机版的几千分之一。
: 请你说清楚。我的单机核心硬件出问题，hot standby马上顶上，损失是多少？哪里来
: 的100%的损失？
: 你这个办法这么好，咋不用来卖股票？人家12306也没用你的办法。

g*y2015-12-21 08:12

48 楼

你想象大家去出票口买票，当然是先到窗口的有优先级。
但是因为买不到联票，A的request是一个transaction，
所以一起fail，直接走人。B紧接着来，应该能买到A不要
的那张票。而不是更晚到的C买到票。
如果因为系统设计者喜欢分库，导致B买不到票，而C买到了，
其实就是没有实现有票必出的要求，虽然可能比例不高。
就像你可以跟人说，我设计了一个分布式计算器，算术比
现有的计算机快1亿倍，还特别容易scale out，就是会有
万分之一的可能会算错结果。不过因为这个比例很小，
所以大伙别介意就行了。

【在 p**2 的大作中提到】

: 从设计上来说，
: B直接没票的情况不但公平，而且对出票速度有利
: 因为如果说等A，那就要设一个max等待值（比如说3秒），
: 无论这个时间多少，它终究会过去的，>maxValue之后的1毫秒，
: C上来拿到1次票，对B来说和直接没票是一样的公正性，
: 但是却牺牲了N个人的时间，所以，我个人感觉是直接没票。
: 或者在等票这块可以写个公式处理，
: 等票数：RequestCount
: 锁票数：HoldCount
: 等待时间：TimeOfWaiting

g*y2015-12-21 08:12

49 楼

你现在的定义是不要over sale就是正确的，有票不出是无所谓的。
老魏的是两个都满足。系统要求都不一样，这两个系统有什么好比的。
正确性的定义有两个方面，一是没票别乱卖，二是有票就要卖给先来的请求。
当然你可以说一更重要（或者说更容易实现），二可有可无（或者说你不会
用分布式系统实现要求二）。我只是好奇，如果二是系统的要求，那么分布式
能不能有效实现这个要求？
印象中好虫原来的设计，让大家提交要求后回家等结果就是因为想要实现
第二个要求。如果只是第一个要求，根本不用搞这么个设计。

【在 q*c 的大作中提到】

: 可能啊，然后？然后下面几千个 order 每个都精心设计的来回这样交叉着回滚？
: 实际中不要 1 豪秒就结束了，根本不会有问题。只要保证正确性就行了，就是说你买
: 到了票你就一定有。

g*y2015-12-21 08:12

50 楼

确实，根本没必要这样分库，可以每个车厢甚至每排座位分一个库，
并行性更高。抢座的要求随机分个车厢号去抢座，抢不到就报没买到。
用户自己重新提交新order。反正也能保证不超售。

【在 p**2 的大作中提到】

: 请教个问题：为啥最后数据库群要1个车次一个数据库？
:
: 本。

p*22015-12-21 08:12

51 楼

你没看我的解释，一样的结果。
就按你说窗口买票，简化过程，顺序如下
A买最后一张
B买票没有，走了，
A发现买错了，退票
C买票，有

【在 g*****y 的大作中提到】

: 你想象大家去出票口买票，当然是先到窗口的有优先级。
: 但是因为买不到联票，A的request是一个transaction，
: 所以一起fail，直接走人。B紧接着来，应该能买到A不要
: 的那张票。而不是更晚到的C买到票。
: 如果因为系统设计者喜欢分库，导致B买不到票，而C买到了，
: 其实就是没有实现有票必出的要求，虽然可能比例不高。
: 就像你可以跟人说，我设计了一个分布式计算器，算术比
: 现有的计算机快1亿倍，还特别容易scale out，就是会有
: 万分之一的可能会算错结果。不过因为这个比例很小，
: 所以大伙别介意就行了。

n*72015-12-21 08:12

52 楼

仔细看了你的方法。“从小到大的顺序开始去后端数据库锁票”和“任何异常情况，
返回失败，已经
索票的数据库自动回卷”归结到数据库底层的实现，都是需要锁的，只是高层应用看不
到罢了。我同意“这些都是自动功能， well tested in real world.”。但实际做出
来，肯定不会有老魏的做法快。你一个车次一个数据库，老魏也一个core只管一个车次
，他的速度快上百倍都是很可能的。
再换一个做法，就用单机，直接实现用C实现roll lock和自动回卷，因为用锁了，比老
魏的做法慢，但是，因为省去数据库的overhead，还是应该比你的方法快。
当然，你的方法是在通用方面是有优势的，就是不要比性能了。

b*s2015-12-21 08:12

53 楼

不奇怪啊，除非你的机器整天出问题，否则几台互备份还不够？同步写状态那种，类似
hb的，其实你想要多少台就可以多少台，只是有这个必要吗

【在 z****e 的大作中提到】

:
: 单机热备n>2我费尽心思
: 总算找到一个n＝4的例子
: 08年时候n＝3
: 已经是全球领先了
: 啧啧，这年头，老年人伤不起啊
: http://www.caacnews.com.cn/2011np/20110510/169141.html

q*c2015-12-21 08:12

54 楼

没人比性能啊，那是老魏说联机版的连他现在这个几兆票每秒的性能的 10 分之
一也做不到。
我是给个例子，就是联机板的，质量绝对保证不出错，而且能 scale 的，性能可以上
去。
你说用现成轮子，性能一般都比不上你单独开发的专门系统，这是肯定的。但是用轮
子的好处就是通用嘛，不需要多少年不断的慢慢 fix bug, 因为别人已经帮助你做了，
也不需要依靠一个人的人品，保证能出货。
更何况老魏那东西车站一多就是平方下降（我没看 code, 看前面说的）。我这个办法
哪怕是几年后无人汽车10000站一条线，性能不变，他那个就要下降 1万倍。这个联
机版的扩展性好的多。
所以要是出去忽悠，J这 sql 联机版的肯定忽悠能力比单机的强。

【在 n*******7 的大作中提到】

: 仔细看了你的方法。“从小到大的顺序开始去后端数据库锁票”和“任何异常情况，
: 返回失败，已经
: 索票的数据库自动回卷”归结到数据库底层的实现，都是需要锁的，只是高层应用看不
: 到罢了。我同意“这些都是自动功能， well tested in real world.”。但实际做出
: 来，肯定不会有老魏的做法快。你一个车次一个数据库，老魏也一个core只管一个车次
: ，他的速度快上百倍都是很可能的。
: 再换一个做法，就用单机，直接实现用C实现roll lock和自动回卷，因为用锁了，比老
: 魏的做法慢，但是，因为省去数据库的overhead，还是应该比你的方法快。
: 当然，你的方法是在通用方面是有优势的，就是不要比性能了。

T*i2015-12-21 08:12

55 楼

老Q，你这可是错的离谱了。废话少说。代码说话。
你不是说一个车次一个数据库么？我不管你咋组织的，你给我一个schema和实时优化座
位的query。就是给定起始站和终点站，有票要出票，而且要能够像我的算法一样优化
座位。
这个做了，把查询，连号座位和退票一起做了。看你的Query是不是车站一多就是平方
下降？
你估计一下你这几个query的效率。
然后，比可靠性。允许对方选择N台机器（N>=1），拿大铁锤砸稀烂，要求系统能够正
常工作，而且数据一致性能够保持。说说你需要几台机器？

【在 q*c 的大作中提到】

: 没人比性能啊，那是老魏说联机版的连他现在这个几兆票每秒的性能的 10 分之
: 一也做不到。
: 我是给个例子，就是联机板的，质量绝对保证不出错，而且能 scale 的，性能可以上
: 去。
: 你说用现成轮子，性能一般都比不上你单独开发的专门系统，这是肯定的。但是用轮
: 子的好处就是通用嘛，不需要多少年不断的慢慢 fix bug, 因为别人已经帮助你做了，
: 也不需要依靠一个人的人品，保证能出货。
: 更何况老魏那东西车站一多就是平方下降（我没看 code, 看前面说的）。我这个办法
: 哪怕是几年后无人汽车10000站一条线，性能不变，他那个就要下降 1万倍。这个联
: 机版的扩展性好的多。

n*72015-12-21 08:12

56 楼

老魏这是在假设qxc用的是一样的算法，才有同样的对站数的scalability。
我的感觉是qxc好像要一个一个座位地搜，那样对站数的scalability是O(1)，但是对座
位数
的scalability是O(seats).
qxc，你能不能澄清一下你找空座的算法？

【在 T********i 的大作中提到】

: 老Q，你这可是错的离谱了。废话少说。代码说话。
: 你不是说一个车次一个数据库么？我不管你咋组织的，你给我一个schema和实时优化座
: 位的query。就是给定起始站和终点站，有票要出票，而且要能够像我的算法一样优化
: 座位。
: 这个做了，把查询，连号座位和退票一起做了。看你的Query是不是车站一多就是平方
: 下降？
: 你估计一下你这几个query的效率。
: 然后，比可靠性。允许对方选择N台机器（N>=1），拿大铁锤砸稀烂，要求系统能够正
: 常工作，而且数据一致性能够保持。说说你需要几台机器？

q*c2015-12-21 08:12

57 楼

我原帖都说了，对当前空票开始结束 index. sql 进去就是 log n. n 是当前空票数目
，logn 很小。
select for update top 1 * from ticket where start <= request.start and end …
第一个 match 就行。如果要优化，最多来个 order by length asc. 选最短的。
结果是对座位数（票数） logn, n 再大也不惧。

【在 n*******7 的大作中提到】

: 老魏这是在假设qxc用的是一样的算法，才有同样的对站数的scalability。
: 我的感觉是qxc好像要一个一个座位地搜，那样对站数的scalability是O(1)，但是对座
: 位数
: 的scalability是O(seats).
: qxc，你能不能澄清一下你找空座的算法？

q*c2015-12-21 08:12

58 楼

我没时间啊，你看看我开始帖子，有描述，优化也就 logn 复杂度，看我前面回帖。

【在 T********i 的大作中提到】

: 老Q，你这可是错的离谱了。废话少说。代码说话。
: 你不是说一个车次一个数据库么？我不管你咋组织的，你给我一个schema和实时优化座
: 位的query。就是给定起始站和终点站，有票要出票，而且要能够像我的算法一样优化
: 座位。
: 这个做了，把查询，连号座位和退票一起做了。看你的Query是不是车站一多就是平方
: 下降？
: 你估计一下你这几个query的效率。
: 然后，比可靠性。允许对方选择N台机器（N>=1），拿大铁锤砸稀烂，要求系统能够正
: 常工作，而且数据一致性能够保持。说说你需要几台机器？

n*72015-12-21 08:12

59 楼

”对当前空票开始结束 index“，是不是就是［开始站，结束站］的二维数组？select
从这个数组找？如果是，你的算法和老魏是一样的，对站数scalability是O（站数^2）
或者你的意思是［开始座，结束座］？
不理解“sql 进去就是 log n”，请解释一下。

…

【在 q*c 的大作中提到】

: 我原帖都说了，对当前空票开始结束 index. sql 进去就是 log n. n 是当前空票数目
: ，logn 很小。
: select for update top 1 * from ticket where start <= request.start and end …
: 第一个 match 就行。如果要优化，最多来个 order by length asc. 选最短的。
: 结果是对座位数（票数） logn, n 再大也不惧。

q*c2015-12-21 08:12

60 楼

check sql index.
我是用了现成的 db. sql db index 过的 column 是 logn.
各种安全完备可靠全部自带。

select

【在 n*******7 的大作中提到】

: ”对当前空票开始结束 index“，是不是就是［开始站，结束站］的二维数组？select
: 从这个数组找？如果是，你的算法和老魏是一样的，对站数scalability是O（站数^2）
: 或者你的意思是［开始座，结束座］？
: 不理解“sql 进去就是 log n”，请解释一下。
:
: …

T*i2015-12-21 08:12

61 楼

你貌似算错了。
你select还可能logn。但是order by优化座位就不是了。
order by应该是nlogn。
而且，咱俩的n不一样。我的n是车站数。你的是座位数。车站数是10。座位数3000。

【在 q*c 的大作中提到】

: check sql index.
: 我是用了现成的 db. sql db index 过的 column 是 logn.
: 各种安全完备可靠全部自带。
:
: select

q*c2015-12-21 08:12

62 楼

length 有 index, order by 不花时间吧？order 都是现成的。
对于 log, n 多少无所谓。我说的就是你这个站，比如将来上无人出租车，全国一盘
其，来个 1 万站或者 10 万站，座位 4 个。我这办法毫无影响，你那个出票马上
就成 10 个每秒了。
所以这个办法通用性好，各种稳定性自带，几十年几亿人彻底测试过，决定可靠出货。

【在 T********i 的大作中提到】

: 你貌似算错了。
: 你select还可能logn。但是order by优化座位就不是了。
: order by应该是nlogn。
: 而且，咱俩的n不一样。我的n是车站数。你的是座位数。车站数是10。座位数3000。

T*i2015-12-21 08:12

63 楼

你再想想：
select for update top 1 * from ticket where start <= request.start and end
… ORDER BY length
你怎么create index能做到log(n)？我读书少，你不能骗我 :)

【在 q*c 的大作中提到】

: length 有 index, order by 不花时间吧？order 都是现成的。
: 对于 log, n 多少无所谓。我说的就是你这个站，比如将来上无人出租车，全国一盘
: 其，来个 1 万站或者 10 万站，座位 4 个。我这办法毫无影响，你那个出票马上
: 就成 10 个每秒了。
: 所以这个办法通用性好，各种稳定性自带，几十年几亿人彻底测试过，决定可靠出货。

k*02015-12-21 08:12

64 楼

这样搞distributed transaction, overhead非常大, 一张联票就需要锁好几个数据库。
dist tran能避开就避开，联写的时候性能下降非常大。
其实比较实用的方法是一个车次放一个table, 同在一个DB server or Server Farm,
不过这就变成架构上的"单机“版了。

本。

【在 q*c 的大作中提到】

: 终于放假了，你们这些单机党也太猖獗了。有点时间给你们个堆机器版的。不过时
: 间很少所以剩余的自己脑补。
: 老魏你说的能达到你的单机版的 1/10 就了得了，你的也就几M/s. 你看看我这个版本。
: 用的全是 proven technology. 有点经验的一看就知道肯定能 work. 全套卖票。
: 当然你也说了，我这个酒不需要实现了，因为比较麻烦。不过你看看就知道肯定无
: 问题
: 实现的和你那个功能完全一样。
: 前段，无状态的 web server. 接受订票. 受到订票直接转到相应的中间集群。
: 中间，是按照用户 id hash 的用户数据库群＋用户 controller.
: 收到订单然后在数据库中产生该用户的订票信息. 比如有三张连票，

q*c2015-12-21 08:12

65 楼

index 在每个写的时候就已经排序好了 length. logn. 整体是 nlogn, 但是每个读写
amortized cost logn. 我不明白你的意思。
当 length index 后， db 在 scan 的时候已经保持 length 顺序，结果已经排序，得
到结果直接返回，不需要重新排序。难道不是这样？

【在 T********i 的大作中提到】

: 你再想想：
: select for update top 1 * from ticket where start <= request.start and end
: … ORDER BY length
: 你怎么create index能做到log(n)？我读书少，你不能骗我 :)

q*c2015-12-21 08:12

66 楼

是 row lock, 开销很小。我就是一个车次放一个 db.

库。

【在 k**0 的大作中提到】

: 这样搞distributed transaction, overhead非常大, 一张联票就需要锁好几个数据库。
: dist tran能避开就避开，联写的时候性能下降非常大。
: 其实比较实用的方法是一个车次放一个table, 同在一个DB server or Server Farm,
: 不过这就变成架构上的"单机“版了。
:
: 本。

k*02015-12-21 08:12

67 楼

这样的架构性能比老魏的会差很多。
你不妨自己在家里放3个DB（不同机器）试试看，即使连在同一个network里, 性能都
会差很多。

【在 q*c 的大作中提到】

: 是 row lock, 开销很小。我就是一个车次放一个 db.
:
: 库。

T*i2015-12-21 08:12

68 楼

OK，你按照length排序。
select for update top 1 * from ticket where start <= request.start and end
… ORDER BY length
worst case复杂度是多少？length一样，你要search start和end。这个是logn么？
连座的query你也给我写一个好了。还是logn么？
还有退票的逻辑。
假定12306查询比抢票请求多100倍，你如何解决这个问题？
可靠性，选一台砸烂，要继续服务而且保持consistency，如何解决？我的那个可以通
过分布式ACID MQ解决。你的呢？
consistency你的问题大了。假定前端web机直连SQL，请问，web机刚完成一个抢票
transaction死掉了，如何恢复？你是否需要中间件？

写

【在 q*c 的大作中提到】

: index 在每个写的时候就已经排序好了 length. logn. 整体是 nlogn, 但是每个读写
: amortized cost logn. 我不明白你的意思。
: 当 length index 后， db 在 scan 的时候已经保持 length 顺序，结果已经排序，得
: 到结果直接返回，不需要重新排序。难道不是这样？

q*c2015-12-21 08:12

69 楼

效率低这是毫无疑问的，这是通用解决方案。虽然低多少不确定－－等老魏把各种
完备性问题解决了，性能还是个未知数。 sql server 慢不是没原因。
但是这个方案的完备性，可靠性，扩展性，都强了太多。现实商业里没人在乎着几
个机器，分分钟 12306 钱就比这个多无数。
要的是可靠，容易维护，已经证明的解决方案。

【在 k**0 的大作中提到】

: 这样的架构性能比老魏的会差很多。
: 你不妨自己在家里放3个DB（不同机器）试试看，即使连在同一个network里, 性能都
: 会差很多。

n*72015-12-21 08:12

70 楼

你怎么保证中途不换座？
每个站的空座是不一样的。你是一个一个站找吗？
1 万站，座位 4 个。在第一站，找到空座1，
一个一个站查，到站9997发现座1不空，
再回头查座2，一个一个站查，到站9998发现座2不空，
再回头查座3，一个一个站查，到站9999发现座3不空，
是这样吗？这个对站数的scalability也是O(站数^2）。
是我理解错了吗？能否用C 或具体例子说明？

【在 q*c 的大作中提到】

: length 有 index, order by 不花时间吧？order 都是现成的。
: 对于 log, n 多少无所谓。我说的就是你这个站，比如将来上无人出租车，全国一盘
: 其，来个 1 万站或者 10 万站，座位 4 个。我这办法毫无影响，你那个出票马上
: 就成 10 个每秒了。
: 所以这个办法通用性好，各种稳定性自带，几十年几亿人彻底测试过，决定可靠出货。

q*c2015-12-21 08:12

71 楼

都是logn, 因为对 start, end & length index.
连坐我前面第一个帖子早写了－－所以要 select for update 就是为了连坐。性能
不变。
我都给你说了这个方案你一看就知道肯定能行，因为亿万人早无数次验证过。
假定12306查询比抢票请求多100倍 - 办法多的是，我们就不提了。因为查询不能保
证买到，这个大家都一样，除非查询的时候就锁票。这个是另外的问题。
还有退票的逻辑- 我这里就太简单了。
insert into tickets (id = ticket.id, start = ticket.start, end = ....)
一张票就是 db 里面一个 row. 咋玩都行。
要继续服务而且保持consistency -- db standby 是成熟 tech, well tested against
anything.

【在 T********i 的大作中提到】

: OK，你按照length排序。
: select for update top 1 * from ticket where start <= request.start and end
: … ORDER BY length
: worst case复杂度是多少？length一样，你要search start和end。这个是logn么？
: 连座的query你也给我写一个好了。还是logn么？
: 还有退票的逻辑。
: 假定12306查询比抢票请求多100倍，你如何解决这个问题？
: 可靠性，选一台砸烂，要继续服务而且保持consistency，如何解决？我的那个可以通
: 过分布式ACID MQ解决。你的呢？
: consistency你的问题大了。假定前端web机直连SQL，请问，web机刚完成一个抢票

q*c2015-12-21 08:12

72 楼

see my initial post
我的办法和老魏的完全不同。我这里db 里面装的都是票，不是站。
起始是 3000 张从开始到结尾的票。根据买卖不断的产生新票，消灭旧票。你根本没
看我的solution。

【在 n*******7 的大作中提到】

: 你怎么保证中途不换座？
: 每个站的空座是不一样的。你是一个一个站找吗？
: 1 万站，座位 4 个。在第一站，找到空座1，
: 一个一个站查，到站9997发现座1不空，
: 再回头查座2，一个一个站查，到站9998发现座2不空，
: 再回头查座3，一个一个站查，到站9999发现座3不空，
: 是这样吗？这个对站数的scalability也是O(站数^2）。
: 是我理解错了吗？能否用C 或具体例子说明？

q*c2015-12-21 08:12

73 楼

"consistency你的问题大了。假定前端web机直连SQL，请问，web机刚完成一个抢票"
才看到这个，哪里有啥问题？我票都在车次数据库里面，用户 order 都在用户数据
库里面，这两个都是数据库, 都 consistent, 没啥 inconsistency 的情况会发生。

【在 T********i 的大作中提到】

: OK，你按照length排序。
: select for update top 1 * from ticket where start <= request.start and end
: … ORDER BY length
: worst case复杂度是多少？length一样，你要search start和end。这个是logn么？
: 连座的query你也给我写一个好了。还是logn么？
: 还有退票的逻辑。
: 假定12306查询比抢票请求多100倍，你如何解决这个问题？
: 可靠性，选一台砸烂，要继续服务而且保持consistency，如何解决？我的那个可以通
: 过分布式ACID MQ解决。你的呢？
: consistency你的问题大了。假定前端web机直连SQL，请问，web机刚完成一个抢票

T*i2015-12-21 08:12

74 楼

是，票都在，哪个付款了？哪个没付款？
前端机刚完成了一个transaction，死翘翘了。咋付款？谁来管？咋管？

【在 q*c 的大作中提到】

: "consistency你的问题大了。假定前端web机直连SQL，请问，web机刚完成一个抢票"
: 才看到这个，哪里有啥问题？我票都在车次数据库里面，用户 order 都在用户数据
: 库里面，这两个都是数据库, 都 consistent, 没啥 inconsistency 的情况会发生。

T*i2015-12-21 08:12

75 楼

你别闹了。对start, end & length index。但是你select where start <= ... AND
end >= ...
其实length在这里都是累赘。这么select，length就是variable了。但是length还要
order by。其中length = end - start。
我还不懂，这么select，order by length，咋安排index能log(n)？
同学，这是基本功啊。

against

【在 q*c 的大作中提到】

: 都是logn, 因为对 start, end & length index.
: 连坐我前面第一个帖子早写了－－所以要 select for update 就是为了连坐。性能
: 不变。
: 我都给你说了这个方案你一看就知道肯定能行，因为亿万人早无数次验证过。
: 假定12306查询比抢票请求多100倍 - 办法多的是，我们就不提了。因为查询不能保
: 证买到，这个大家都一样，除非查询的时候就锁票。这个是另外的问题。
: 还有退票的逻辑- 我这里就太简单了。
: insert into tickets (id = ticket.id, start = ticket.start, end = ....)
: 一张票就是 db 里面一个 row. 咋玩都行。
: 要继续服务而且保持consistency -- db standby 是成熟 tech, well tested against

q*c2015-12-21 08:12

76 楼

在用户数据库里面啊！付了钱的票 status 设置就行了。票还可以设置 foreigh key
userId. 保证知道谁拿的这张票。
order 里面全部票都服了钱， order status = done.
数据库崩溃，重启的时候 scan 所有 order status != done 的 order, 确保对应的
票全部回滚. 最多就是那张票已经回滚过了就不需要回滚而已，总数很小。

【在 T********i 的大作中提到】

: 是，票都在，哪个付款了？哪个没付款？
: 前端机刚完成了一个transaction，死翘翘了。咋付款？谁来管？咋管？

q*c2015-12-21 08:12

77 楼

length 在插入的时候就计算好，不是 variable.
你这样动态设置 length = end - start 才是 variable.
专门设置一个length column. length = end -start
这样select 完了就是自然排序的。
就算退一万步，也是 nlogn. 对于100万以下的 n, 近视 o(n), 比n^2 强到天上去了。
anyway 这个不是重点。

【在 T********i 的大作中提到】

: 你别闹了。对start, end & length index。但是你select where start <= ... AND
: end >= ...
: 其实length在这里都是累赘。这么select，length就是variable了。但是length还要
: order by。其中length = end - start。
: 我还不懂，这么select，order by length，咋安排index能log(n)？
: 同学，这是基本功啊。
:
: against

T*i2015-12-21 08:12

78 楼

刚开始start, end, length都一样，就是有3000票候选。是log(n)么？
当然你可以argue只选第一张就好了。但是将来不一定，尤其是有退票。
退票可能会concat其他碎票。也是O(n)的。
其实这个可以证明最多就O(n)。O(nlog(n))都不对。
你的分析对不对是原则问题。

了。

【在 q*c 的大作中提到】

: length 在插入的时候就计算好，不是 variable.
: 你这样动态设置 length = end - start 才是 variable.
: 专门设置一个length column. length = end -start
: 这样select 完了就是自然排序的。
: 就算退一万步，也是 nlogn. 对于100万以下的 n, 近视 o(n), 比n^2 强到天上去了。
: anyway 这个不是重点。

q*c2015-12-21 08:12

79 楼

港开始时（1）
我记得 db index 用的是红黑搜索树，进去都是同一个节点根本不用排序，直接拿
第一个出来就行了，因为值一样。也许我记错了？
google:
http://use-the-index-luke.com/sql/sorting-grouping/indexed-orde
有了 index 那么 order by 就不是需要 sort 的。
退票不会产生碎片－退票的时候就把 cancat 做好。退票有没有 1/100? cost 不需
要考虑（其实考虑也很少，因为是 exact match, 最多两张票 match 首尾，还是
logn.)

【在 T********i 的大作中提到】

: 刚开始start, end, length都一样，就是有3000票候选。是log(n)么？
: 当然你可以argue只选第一张就好了。但是将来不一定，尤其是有退票。
: 退票可能会concat其他碎票。也是O(n)的。
: 其实这个可以证明最多就O(n)。O(nlog(n))都不对。
: 你的分析对不对是原则问题。
:
: 了。

T*i2015-12-21 08:12

80 楼

Not impressed。你需要保持的index太多了。实际上更费时。
实际select range优化只能用一个index，用了这个，就不能用那个。实际你还是o(n)。

【在 q*c 的大作中提到】

: 港开始时（1）
: 我记得 db index 用的是红黑搜索树，进去都是同一个节点根本不用排序，直接拿
: 第一个出来就行了，因为值一样。也许我记错了？
: google:
: http://use-the-index-luke.com/sql/sorting-grouping/indexed-orde
: 有了 index 那么 order by 就不是需要 sort 的。
: 退票不会产生碎片－退票的时候就把 cancat 做好。退票有没有 1/100? cost 不需
: 要考虑（其实考虑也很少，因为是 exact match, 最多两张票 match 首尾，还是
: logn.)

q*c2015-12-21 08:12

81 楼

o(n) 还是比 n^2 强到天上去了，而且这是最坏情况。
就3 个 index 哪里算多，维持每个 index 也就 logn 开销。最后还是 logn.
平均下来我这个就是 logn 性能。你看过几年后无人汽车公交普及了，一条线 1万站
，你那玩意立马就歇菜了，我这个照样杠杠的。
话说你同意不同意
1 联机板的可以做到性能远超你的办法的 1/10？
2. 这方案用的是不是全部是成熟技术，可靠性稳定性等一切都是绝对有保障的？
这是真正的解决方案，比你那个东西靠近产品多的多。

)。

【在 T********i 的大作中提到】

: Not impressed。你需要保持的index太多了。实际上更费时。
: 实际select range优化只能用一个index，用了这个，就不能用那个。实际你还是o(n)。

q*c2015-12-21 08:12

82 楼

如果只能用一个 index 我就建个 composite index.
还是 logn. :)

)。

【在 T********i 的大作中提到】

: Not impressed。你需要保持的index太多了。实际上更费时。
: 实际select range优化只能用一个index，用了这个，就不能用那个。实际你还是o(n)。

k*02015-12-21 08:12

83 楼

呵呵，换了我就用一个sql server farm, 即解决了分布锁的问题，也保证可靠性和扩
展性。
不过这就是centralized ticketing system的架构了（“单机”)。出票不会比老魏这
种搞底层的快，但有轮子可用。

【在 q*c 的大作中提到】

: 效率低这是毫无疑问的，这是通用解决方案。虽然低多少不确定－－等老魏把各种
: 完备性问题解决了，性能还是个未知数。 sql server 慢不是没原因。
: 但是这个方案的完备性，可靠性，扩展性，都强了太多。现实商业里没人在乎着几
: 个机器，分分钟 12306 钱就比这个多无数。
: 要的是可靠，容易维护，已经证明的解决方案。

T*i2015-12-21 08:12

84 楼

你建一个给我看看。然后证明是log(n)？这是基本功问题！
咱俩的n不一样，我说过很多次了。我的n是车站=10，你的n是座位数=3000。其实我懒
的仔细分析，你的那个n应该是O(m * n)。m=车站。
你退票，连座还没写呢。查询的scalability呢？砸碎了恢复呢？server farm貌似可行
，不知道license多少钱？

【在 q*c 的大作中提到】

: 如果只能用一个 index 我就建个 composite index.
: 还是 logn. :)
:
: )。

q*c2015-12-21 08:12

85 楼

就是多花钱。别的都没事。
或者像 kz80 说的，直接上 server farm. 当然那样钱更多。
我给你说了你那个 n 是平方性能降低，不好扩张。砸碎了恢复都是 proven tech,
投资人问都不会问。倒是你那个玩意要被人问死，呵呵，全靠你一个人啊。
我这个和车站数毫无关系，因为我只存剩票，随着票卖出性能越来越快。
无论咋样，这办法性能肯定没问题，扩展性稳定性绝对靠得住，都是现实成熟技术。

【在 T********i 的大作中提到】

: 你建一个给我看看。然后证明是log(n)？这是基本功问题！
: 咱俩的n不一样，我说过很多次了。我的n是车站=10，你的n是座位数=3000。其实我懒
: 的仔细分析，你的那个n应该是O(m * n)。m=车站。
: 你退票，连座还没写呢。查询的scalability呢？砸碎了恢复呢？server farm貌似可行
: ，不知道license多少钱？

T*i2015-12-21 08:12

86 楼

见仁见智吧。反正很多话我不好意思说。比如我说性能必须要说最差和平均。而且这个
n和那个n不一样，我就不会拿出来比较。n=10, 才最多55次，n=20不到300次。座位
3000个。我不会做这种比较。
咱们既不投标，又不招标，我仍然说话谨慎。
真投标的话，也不会全靠我一个人。这个版上的凑够一个team没问题。wdong不是一直
还嚷嚷着开源么？

术。

【在 q*c 的大作中提到】

: 就是多花钱。别的都没事。
: 或者像 kz80 说的，直接上 server farm. 当然那样钱更多。
: 我给你说了你那个 n 是平方性能降低，不好扩张。砸碎了恢复都是 proven tech,
: 投资人问都不会问。倒是你那个玩意要被人问死，呵呵，全靠你一个人啊。
: 我这个和车站数毫无关系，因为我只存剩票，随着票卖出性能越来越快。
: 无论咋样，这办法性能肯定没问题，扩展性稳定性绝对靠得住，都是现实成熟技术。

q*c2015-12-21 08:12

87 楼

...
create index on (start, end, length)
Composite indexes work just like regular indexes, except they have multi-
values keys.
If you define an index on the fields (a,b,c) , the records are sorted first
on a, then b, then c.
Example:
| A | B | C |
-------------
| 1 | 2 | 3 |
| 1 | 4 | 2 |
| 1 | 4 | 4 |
| 2 | 3 | 5 |
| 2 | 4 | 4 |
| 2 | 4 | 5 |
select top 1 from ticket where start <=request.start AND end >= request.end
ORDER BY length
where clause (1) start <=request.start, logn time locate the record based on
start column
where clause (2) end >=request.end, from resultset of (1) logn time locate
the record on end column (since it is sort and tree structured). 其实比 logn
小的多，因为这里已经根据 startTime filter 过一次了
where clause (3) ORDER BY LENGTH, 直接提取结果
select top 1 - O(1)
最后就是 logn. n 再大根本不是个事情。
这办法比你的单机计数器强了无数，可靠性扩张行可维护性实战性，样样强的多的多,
你不承认是不行的。你单机版强在省钱，这是毫无疑问的。但是省钱不是需要考虑
的问题。机器才花几个钱？而且忙的时候就那几天，闲的时候还可以吧机器放回云
里面去挣钱。

【在 T********i 的大作中提到】

: 你建一个给我看看。然后证明是log(n)？这是基本功问题！
: 咱俩的n不一样，我说过很多次了。我的n是车站=10，你的n是座位数=3000。其实我懒
: 的仔细分析，你的那个n应该是O(m * n)。m=车站。
: 你退票，连座还没写呢。查询的scalability呢？砸碎了恢复呢？server farm貌似可行
: ，不知道license多少钱？

n*72015-12-21 08:12

88 楼

我对数据库不熟。请帮我看看一下对qxc db 找票的理解是否准确。
Index by start，end，length
遍历 start <= order.start，end >= order.end，对所有, ｛
#O(stations^2), same as Wei's
1. 用start和end indices拿出所有票。
＃O(log(stations)), O(seats) vs. Wei's O(1) for both stations and
seats
2. sort by length;
# O(stations*log(stations), O(seats*(log(seats)), vs. Wei's none
｝
遍历对站数的scalability都是平方。qxc强调的log(n)只是在用index从tree拿票的阶
段。这个阶段魏的stack 是O（1）, 支持连座就也变成O(seats).

q*c2015-12-21 08:12

89 楼

。。。
你对我的办法根本没看啊。我db 里面根本没站，全部是当前剩余的票
每张票有起始终点站而已。
一开始就 3000 票，表里面 3000 行。一个位置一个票，始终都是全程，中间就是各
种断开，卖到最后是 0 张票。
数据库里面都是红黑树，哪里来的遍历（table scan)？都是 logN, N 是数据库里
面的行数，也就是剩余票数。
你看看我前面给老魏的解释。

and
none

【在 n*******7 的大作中提到】

: 我对数据库不熟。请帮我看看一下对qxc db 找票的理解是否准确。
: Index by start，end，length
: 遍历 start <= order.start，end >= order.end，对所有, ｛
: #O(stations^2), same as Wei's
: 1. 用start和end indices拿出所有票。
: ＃O(log(stations)), O(seats) vs. Wei's O(1) for both stations and
: seats
: 2. sort by length;
: # O(stations*log(stations), O(seats*(log(seats)), vs. Wei's none
: ｝

T*i2015-12-21 08:12

90 楼

其实吧，老Q认为check start即可，SQL优化器没那么蠢。要check start, end才行。
他需要纸上画画这个index的多层金字塔才能理解的更好些 :)

and
none

【在 n*******7 的大作中提到】

: 我对数据库不熟。请帮我看看一下对qxc db 找票的理解是否准确。
: Index by start，end，length
: 遍历 start <= order.start，end >= order.end，对所有, ｛
: #O(stations^2), same as Wei's
: 1. 用start和end indices拿出所有票。
: ＃O(log(stations)), O(seats) vs. Wei's O(1) for both stations and
: seats
: 2. sort by length;
: # O(stations*log(stations), O(seats*(log(seats)), vs. Wei's none
: ｝

q*c2015-12-21 08:12

91 楼

直接的，你就说是不是 logN 吧。 N 是行数（剩余票数）。

【在 T********i 的大作中提到】

: 其实吧，老Q认为check start即可，SQL优化器没那么蠢。要check start, end才行。
: 他需要纸上画画这个index的多层金字塔才能理解的更好些 :)
:
: and
: none

T*i2015-12-21 08:12

92 楼

我认为不是。不信你把Index列出来，我给你一个data列。

【在 q*c 的大作中提到】

: 直接的，你就说是不是 logN 吧。 N 是行数（剩余票数）。

q*c2015-12-21 08:12

93 楼

我前面不是给了 example? A. b C. 那个。
你给个 Data 列，让我看看我哪里分析的不对？我 index, example 可是都给了。

【在 T********i 的大作中提到】

: 我认为不是。不信你把Index列出来，我给你一个data列。

T*i2015-12-21 08:12

94 楼

其实你那个要每个符合条件的unique {start, end} pair cluster都要找一个最小的
length。
你最多需要找(n/2)^2 = (n^2)/4次。是O(n^2)。n是车站数。
我的算法，现在的search pattern需要搜n * (n-1)/2次。其实很多pattern都是越界的
。因为指标远超也懒的改了。我动态产生search pattern的话，也是最多搜(n^2)/4次。
大家都是O(n^2)。n是车站数。
你再想想。

【在 q*c 的大作中提到】

: 我前面不是给了 example? A. b C. 那个。
: 你给个 Data 列，让我看看我哪里分析的不对？我 index, example 可是都给了。

n*72015-12-21 08:12

95 楼

我想清楚了。老魏是对的。
试这个例子。
select top 1 from ticket where A>＝1 AND B>=2 ORDER BY C
| A | B | C |
-------------
| 1 | 2 | 3 | 《＝qxc result
| 1 | 4 | 2 |
| 1 | 4 | 4 |
| 2 | 3 | 5 |
| 2 | 4 | 1 | 《＝正确
| 2 | 4 | 5 |
按qxc做法，只在｛A，B｝＝｛1，2｝里找最小C。
正确做法是遍历所有满足A>＝1 AND B>=2的｛A，B｝，找最小C。这个遍历过程是站数
平方。
不理解为什么是(n/2)^2，我我觉得好像是n^2/2
composite index, the internal is a hierarchy of trees. For each tree, the
order is log(n).
selecting a range of elements is not log(n).
老魏和qxc的数据库做法tickets是一样的，所以很容易对应比较。
db的composite index，就是二维数组。老魏code里的SearchPatterns，相当于用
length做db的第一个index。
db用tree找站范围｛start，end｝，魏用数组，db用tree找票，魏用stack。
每一个环节都是魏高效，scalability对座位对站数都一样。db唯一的优势是座比较空时
tree的遍历可以跳过很多entries，而查数组还是得一个个查, 但也影响很小，
站数很大时加一层aggregated bitmap就可以了。

T*i2015-12-21 08:12

96 楼

静态搜索，为了保证覆盖，需要向前向后都要搜索总站数那么多。实际上有很多越界就
直接忽略了。
动态搜索，顶多搜索总站数那么多次。这是为啥n^2/4不是n^2/2。
老Q的做法，余票稀疏有利一些。我的做法余票密集好一些。但都是O(n^2)。
实际上，我的专用机，比他的SQL快100倍都有可能。他这个一台机器一个车次，机器数
量还不知道要多少呢？

【在 n*******7 的大作中提到】

: 我想清楚了。老魏是对的。
: 试这个例子。
: select top 1 from ticket where A>＝1 AND B>=2 ORDER BY C
: | A | B | C |
: -------------
: | 1 | 2 | 3 | 《＝qxc result
: | 1 | 4 | 2 |
: | 1 | 4 | 4 |
: | 2 | 3 | 5 |
: | 2 | 4 | 1 | 《＝正确

q*c2015-12-21 08:12

97 楼

b ≧ 2 AND a ≦ 1
只有一个区间。

【在 n*******7 的大作中提到】

: 我想清楚了。老魏是对的。
: 试这个例子。
: select top 1 from ticket where A>＝1 AND B>=2 ORDER BY C
: | A | B | C |
: -------------
: | 1 | 2 | 3 | 《＝qxc result
: | 1 | 4 | 2 |
: | 1 | 4 | 4 |
: | 2 | 3 | 5 |
: | 2 | 4 | 1 | 《＝正确

T*i2015-12-21 08:12

98 楼

你这样搞法P= NP都行。
你看看10个车站，找5-6的票就明白了。

【在 q*c 的大作中提到】

: b ≧ 2 AND a ≦ 1
: 只有一个区间。

n*72015-12-21 08:12

99 楼

i changed it to a>=1. i changed the condition and the data, just to show
you the problem.
the point is that it iterates through all {A,B}, not just one. do you agree?

【在 q*c 的大作中提到】

: b ≧ 2 AND a ≦ 1
: 只有一个区间。