Redian新闻
>
我来写个老魏的详细实现方案。(更新了缺点)
avatar
我来写个老魏的详细实现方案。(更新了缺点)# Programming - 葵花宝典
b*e
1
大家都怎么买下手的?
avatar
h*o
2
mark my word.
avatar
m*d
3
否则太多Chiglish岂不是很不好
avatar
s*r
4
大家接着奔
XChain
avatar
n*x
5
本人纯凑绕闹,不倾向任何一方。
系统主要特点:
- 多线程。(老魏没有给出具体多少个线程,假定100个吧。我的12 core intel xeon轻
轻松松100 thread)
- 无锁。
- 单机。
数据结构:
1. 全国1000条线 (X1, X2, X... , X1000), 每条20个区段 (S1, S2, S3... S20)。
2. 每条线的每个区段的票的总数计为:T[X1,S1], T[X1, S2]....... T[X1000, S20]
抢票程序(注意举得例子是联票)
1. 100个thread处理收到的请求
2. 每个请求包括三个参数(线路, 起始站,结束战). 比如(234次列车, 济南, 上
海)。 (注意, 234次列车是从沈阳出发,到上海的, 济南是第5个区的开始,上海最
后一个区段的结束)
3. 计算过程就是把234次列车从济南到上海的每个区段的票数做interlocked.
decrement, 如下:
- Interlocked.Decrement( T[X234,S5] )
- Interlocked.Decrement( T[X234,S6] )
- Interlocked.Decrement( T[X234,S7] )
.......
- Interlocked.Decrement( T[X234,S20] )
4. 如果每个interlocked.decrement后的结果还大于0,表示可以出票。 如果有任何一
个环节计算后<0,那么抢票失败,并且要对前面decrement的全部做increment.
5. 北京->上海。 用户选择: 北京-〉济南, 济南-〉上海。 每一张票都可重复step
#3.
方案的本质:
- 就是对一个巨大的内存空间做interlocked加减法。
- 系统的性能由 hardware决定。 100线程,每个需要每秒处理50000个请求。
- 这个方案人人都写得出来。
大家说说目前的硬件可行吗?
缺点:
- 单点失败整个系统失败。 老魏说是100不遇的情况,不考虑。
- 只interlock区段,不interlock整个路线。中途失败需要increment之前所有
decrement过的。 会导致本来有票结果出现没票的结果。
avatar
a*s
6
看到多少

【在 h******o 的大作中提到】
: mark my word.
avatar
x*n
7
顶~
老王,佳佳,萌萌和一众闪奔的同学们可以上照片了。

【在 s*********r 的大作中提到】
: 大家接着奔
: XChain
: 我

avatar
g*g
8
你就2万个数,随机取20个锁更新,看看能有多快就知道了。别忘了这还不能保证座位
。处理输入输出都有开销。
avatar
h*o
9
target: 45!

【在 a********s 的大作中提到】
: 看到多少
avatar
s*r
10
点名的同学快来张遮眼照

【在 x****n 的大作中提到】
: 顶~
: 老王,佳佳,萌萌和一众闪奔的同学们可以上照片了。

avatar
n*x
11
我其实也很想知道。interlock要霸占总线,多出好几个cpu cycle. 不过老魏说没问题
呀。呵呵。

【在 g*****g 的大作中提到】
: 你就2万个数,随机取20个锁更新,看看能有多快就知道了。别忘了这还不能保证座位
: 。处理输入输出都有开销。

avatar
a*s
12
多久啊,到不了找你

【在 h******o 的大作中提到】
: target: 45!
avatar
s*r
13
我点名darkarchon奔咸蛋超人遮眼照。。哈哈
avatar
q*c
14
不行啊, 联票咋办?
每个请求里面有 1-2 个票



【在 n**x 的大作中提到】
: 本人纯凑绕闹,不倾向任何一方。
: 系统主要特点:
: - 多线程。(老魏没有给出具体多少个线程,假定100个吧。我的12 core intel xeon轻
: 轻松松100 thread)
: - 无锁。
: - 单机。
: 数据结构:
: 1. 全国1000条线 (X1, X2, X... , X1000), 每条20个区段 (S1, S2, S3... S20)。
: 2. 每条线的每个区段的票的总数计为:T[X1,S1], T[X1, S2]....... T[X1000, S20]
: 抢票程序(注意举得例子是联票)

avatar
h*o
15
半年内。

【在 a********s 的大作中提到】
: 多久啊,到不了找你
avatar
d*n
16
。。碎大师你的身材怎么飘忽不定啊?一会猛男一会小清新一会星爷一会高僧
你的点奔应该用在lanlan身上,别在我身上浪费了
avatar
n*x
17
按照老魏的说法,这已经有联票了:
北京到上海:北京-〉济南, 济南-〉上海。 每一段重复step #3

【在 q*c 的大作中提到】
: 不行啊, 联票咋办?
: 每个请求里面有 1-2 个票
:
: 。

avatar
g*o
18
大师,300135呢?

【在 h******o 的大作中提到】
: mark my word.
avatar
s*r
19
我是百变星君,看好你搞笑的潜力才点你啊

【在 d********n 的大作中提到】
: 。。碎大师你的身材怎么飘忽不定啊?一会猛男一会小清新一会星爷一会高僧
: 你的点奔应该用在lanlan身上,别在我身上浪费了

avatar
n*t
20
锁 20 个干啥?每个车次一个锁不行吗?

【在 g*****g 的大作中提到】
: 你就2万个数,随机取20个锁更新,看看能有多快就知道了。别忘了这还不能保证座位
: 。处理输入输出都有开销。

avatar
h*o
21
捂着,信我着,得救赎。

【在 g*********o 的大作中提到】
: 大师,300135呢?
avatar
w*g
22
响应两位大佬奔!

【在 s*********r 的大作中提到】
: 大家接着奔
: XChain
: 我

avatar
g*g
23
一个车次20段。每段都得锁。

【在 n*****t 的大作中提到】
: 锁 20 个干啥?每个车次一个锁不行吗?
avatar
w*g
24


【在 w*********g 的大作中提到】
: 响应两位大佬奔!
avatar
n*t
25
靠,我把整个车次一起锁了不行啊,大不了同时请求这个车次的等一下,1000 个车次
,冲突概率只有 0.1%,何必浪费那么多锁。
或者某车次某等级设一个锁,冲突概率更低了。

【在 g*****g 的大作中提到】
: 一个车次20段。每段都得锁。
avatar
w*g
26


【在 w*********g 的大作中提到】
: 响应两位大佬奔!
avatar
q*c
27
ou. 你是把票搞成 global, 跨区段都是一张票。
这样也行

【在 n**x 的大作中提到】
: 按照老魏的说法,这已经有联票了:
: 北京到上海:北京-〉济南, 济南-〉上海。 每一段重复step #3

avatar
x*n
28
好!

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

avatar
i*i
29
(s1 to s20) as a whole piece has to be locked before manipulation.
lock / atom operation on a part cannot guarantee the overall operation is
correct.
cs 102.



【在 n**x 的大作中提到】
: 本人纯凑绕闹,不倾向任何一方。
: 系统主要特点:
: - 多线程。(老魏没有给出具体多少个线程,假定100个吧。我的12 core intel xeon轻
: 轻松松100 thread)
: - 无锁。
: - 单机。
: 数据结构:
: 1. 全国1000条线 (X1, X2, X... , X1000), 每条20个区段 (S1, S2, S3... S20)。
: 2. 每条线的每个区段的票的总数计为:T[X1,S1], T[X1, S2]....... T[X1000, S20]
: 抢票程序(注意举得例子是联票)

avatar
x*n
30
戴帽子这个造型不错。

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

avatar
q*c
31
就两个 thread? 还是单线程?
而且很多热门车次 block 其他大量车次。

【在 n*****t 的大作中提到】
: 靠,我把整个车次一起锁了不行啊,大不了同时请求这个车次的等一下,1000 个车次
: ,冲突概率只有 0.1%,何必浪费那么多锁。
: 或者某车次某等级设一个锁,冲突概率更低了。

avatar
w*g
32
我忘记把照片改小了。。。

【在 x****n 的大作中提到】
: 戴帽子这个造型不错。
avatar
g*g
33
And if you decrement at will and rollback when hitting a zero counter.
Lots of requests will fail although there are actually tickets left, just
temporarily booked and released shortly after. No fairness.

【在 i**i 的大作中提到】
: (s1 to s20) as a whole piece has to be locked before manipulation.
: lock / atom operation on a part cannot guarantee the overall operation is
: correct.
: cs 102.
:
: 。

avatar
w*g
34
改小了重来一次

【在 w*********g 的大作中提到】
: 我忘记把照片改小了。。。
avatar
g*g
35
锁的粒度大不见得有利,北京到上海过天津和南京,本来北京到天津和南京到上海的不
相干,一下子就得等。

【在 n*****t 的大作中提到】
: 靠,我把整个车次一起锁了不行啊,大不了同时请求这个车次的等一下,1000 个车次
: ,冲突概率只有 0.1%,何必浪费那么多锁。
: 或者某车次某等级设一个锁,冲突概率更低了。

avatar
a*t
36
大的也可以有震撼效果。。对了,为啥不叫佳佳了?

【在 w*********g 的大作中提到】
: 改小了重来一次
avatar
n*t
37
1/1000 不严谨,16 个 core 抢 1000 个车次,重复的概率多大?如果按 5 个等级,
那冲突更低了。无论如何,没必要 20 个锁。

【在 q*c 的大作中提到】
: 就两个 thread? 还是单线程?
: 而且很多热门车次 block 其他大量车次。

avatar
K*y
38
身材真好,帅

【在 w*********g 的大作中提到】
: 改小了重来一次
avatar
N*n
39
应该每个车次一个锁。。
否则按老魏的算法到后来有可能整票(从头到尾的)有票卖不出去,区间
票倒先卖掉了

【在 n*****t 的大作中提到】
: 锁 20 个干啥?每个车次一个锁不行吗?
avatar
i*a
40
酷~!

【在 w*********g 的大作中提到】
: 改小了重来一次
avatar
g*g
41
锁少了,每个等锁的队列就长,光等的时间就没戏了。没有holy grail。

【在 n*****t 的大作中提到】
: 1/1000 不严谨,16 个 core 抢 1000 个车次,重复的概率多大?如果按 5 个等级,
: 那冲突更低了。无论如何,没必要 20 个锁。

avatar
i*a
42
强~!呵呵。

【在 s*********r 的大作中提到】
: 大家接着奔
: XChain
: 我

avatar
n*x
43
you are right. 老魏的方案里没有说如何解决这个问题。
老魏?

【在 g*****g 的大作中提到】
: And if you decrement at will and rollback when hitting a zero counter.
: Lots of requests will fail although there are actually tickets left, just
: temporarily booked and released shortly after. No fairness.

avatar
i*r
44
遮眼照很养眼啊!

【在 w*********g 的大作中提到】
: 改小了重来一次
avatar
N*n
45
2nd this

【在 i**i 的大作中提到】
: (s1 to s20) as a whole piece has to be locked before manipulation.
: lock / atom operation on a part cannot guarantee the overall operation is
: correct.
: cs 102.
:
: 。

avatar
d*n
46
灰常灰常养眼。。。赞美女大方奔
avatar
n*t
47
等也比上 20 个锁划算多了。
或者 try lock failed,我把这个请求扔 queue 里,先处理其他 request,完了再
try,没必要 block

【在 g*****g 的大作中提到】
: 锁的粒度大不见得有利,北京到上海过天津和南京,本来北京到天津和南京到上海的不
: 相干,一下子就得等。

avatar
s*r
48
美腿配挪威森林草鞋,太养眼了

【在 w*********g 的大作中提到】
: 改小了重来一次
avatar
g*g
49
整个东西不就是个速度的问题,你要说1万个,我当然信,500万我不信而已。
还是那句话,你自己试试就知道了。按你说的,1000个车次,随机取两个锁住,
然后更新20个计数器,开锁。

【在 n*****t 的大作中提到】
: 等也比上 20 个锁划算多了。
: 或者 try lock failed,我把这个请求扔 queue 里,先处理其他 request,完了再
: try,没必要 block

avatar
l*g
50
我没有和乐器合影啊,我有和西瓜的墨镜照。
avatar
n*t
51
Kernel lock 大概 50 cpu cycles,如果我没记错的话。写计数器 20 个,sync to
disk 再加几十个吧,没测过,你算算够不够。
1M/s 我觉得狠靠谱

【在 g*****g 的大作中提到】
: 整个东西不就是个速度的问题,你要说1万个,我当然信,500万我不信而已。
: 还是那句话,你自己试试就知道了。按你说的,1000个车次,随机取两个锁住,
: 然后更新20个计数器,开锁。

avatar
y*x
52
怎么又点名阿 好吧 有遮眼 有琴 有萌萌

【在 x****n 的大作中提到】
: 顶~
: 老王,佳佳,萌萌和一众闪奔的同学们可以上照片了。

avatar
n*x
53
加了锁老魏的系统就完蛋了。 不枷锁就会出现你前面提到的本来有票结果出现没票的
结果。
老魏人去哪里了?

【在 g*****g 的大作中提到】
: 整个东西不就是个速度的问题,你要说1万个,我当然信,500万我不信而已。
: 还是那句话,你自己试试就知道了。按你说的,1000个车次,随机取两个锁住,
: 然后更新20个计数器,开锁。

avatar
y*x
54
腿又细又直,身材真好!

【在 w*********g 的大作中提到】
: 改小了重来一次
avatar
n*t
55
其实少量的有票出现没票狠正常,计划跟不上变化,现在看到没票继续刷的太多了,最
终这张票还是会卖出去的。只要严格防止重票就可以了。

【在 n**x 的大作中提到】
: 加了锁老魏的系统就完蛋了。 不枷锁就会出现你前面提到的本来有票结果出现没票的
: 结果。
: 老魏人去哪里了?

avatar
q*q
56
第二张的造型太像Keith Haring的画儿了 :)

【在 w*********g 的大作中提到】
: 改小了重来一次
avatar
n*x
57
我同意。 不过古德霸的需求不允许这个。

【在 n*****t 的大作中提到】
: 其实少量的有票出现没票狠正常,计划跟不上变化,现在看到没票继续刷的太多了,最
: 终这张票还是会卖出去的。只要严格防止重票就可以了。

avatar
t*o
58
佳佳妹,typical的四川妹。鼓掌也
avatar
n*t
59
他也没法验证,哈哈,谁知道哪个 request 先到的?

【在 n**x 的大作中提到】
: 我同意。 不过古德霸的需求不允许这个。
avatar
t*o
60
这狗儿貌似很值得一玩,盟主可否邮寄给我

【在 y******x 的大作中提到】
: 怎么又点名阿 好吧 有遮眼 有琴 有萌萌
avatar
g*g
61
峰值请求高,500万。热门票数少3000,你看到的会反过来。

【在 n**x 的大作中提到】
: 我同意。 不过古德霸的需求不允许这个。
avatar
x*n
62
打倒~

【在 y******x 的大作中提到】
: 怎么又点名阿 好吧 有遮眼 有琴 有萌萌
avatar
i*i
63
一个车次(K1,6:00pm)只能由同一个线程写,不需要锁.
可以有只读拷贝,供其他线程调度参考.

【在 n*****t 的大作中提到】
: 其实少量的有票出现没票狠正常,计划跟不上变化,现在看到没票继续刷的太多了,最
: 终这张票还是会卖出去的。只要严格防止重票就可以了。

avatar
w*g
64
今天被人说了。。。其实平常就这么穿的啊,没想太多,主要是配合前辈们奔。。。删
了吧。。。
萌萌不乖了,要求重奔~~
avatar
n*t
65
那是按车次调度 thread 了?我赶脚比 lock 的开销大啊,尤其是都放在 kernel
space 里的话,还不如 lock 糙快猛

【在 i**i 的大作中提到】
: 一个车次(K1,6:00pm)只能由同一个线程写,不需要锁.
: 可以有只读拷贝,供其他线程调度参考.

avatar
i*i
66
我觉得要快,因为没有无用功. 并且内存里设计个20标志不在话下.开锁解锁就麻烦
了.

【在 n*****t 的大作中提到】
: 那是按车次调度 thread 了?我赶脚比 lock 的开销大啊,尤其是都放在 kernel
: space 里的话,还不如 lock 糙快猛

avatar
i*i
67
按照一定规则,把对于(车次,时间)映射到12个thread上,每个thread对应一个核.

【在 n*****t 的大作中提到】
: 那是按车次调度 thread 了?我赶脚比 lock 的开销大啊,尤其是都放在 kernel
: space 里的话,还不如 lock 糙快猛

avatar
n*t
68
先卖完的 core 先下班吗?当然加班帮别人卖也行,这个调度好的话其实也行,唯一的
麻烦是联程,比如跨 thread 出 2 张票,这个怎么协同?

【在 i**i 的大作中提到】
: 按照一定规则,把对于(车次,时间)映射到12个thread上,每个thread对应一个核.
avatar
b*s
69
在前端做判断,有一个失败就提交撤销请求

【在 n*****t 的大作中提到】
: 先卖完的 core 先下班吗?当然加班帮别人卖也行,这个调度好的话其实也行,唯一的
: 麻烦是联程,比如跨 thread 出 2 张票,这个怎么协同?

avatar
n*t
70
这俩线头要唠嗑,你那嘎达有内啥票没?好像稍微复杂了点。具体看情况

【在 b*******s 的大作中提到】
: 在前端做判断,有一个失败就提交撤销请求
avatar
b*s
71
其实就是事务不在后端做,在某个中间服务器甚至前端里面,把联票拆解成2个请求
反正都毫秒级内得到反馈的,可以单独为联票的准备一个小集群

【在 n*****t 的大作中提到】
: 这俩线头要唠嗑,你那嘎达有内啥票没?好像稍微复杂了点。具体看情况
avatar
n*t
72
哦,那也行,拿不到就 request release locked

【在 b*******s 的大作中提到】
: 其实就是事务不在后端做,在某个中间服务器甚至前端里面,把联票拆解成2个请求
: 反正都毫秒级内得到反馈的,可以单独为联票的准备一个小集群

avatar
b*s
73
嗯,就是这个意思

【在 n*****t 的大作中提到】
: 哦,那也行,拿不到就 request release locked
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。