n*****t
发帖数: 22014 | 1 1、用 DISK 替代 NETWORK
考虑 SSD 大概是 500M，双 10GBE 大概 2.5G，老魏吃亏点，不过 DISK IO 稍微简单
点，大家看看合理不合理，怎么折算。
2、测试数据如下，1000 车次，每个车次 5 个等级，每趟车 1000 张票
3、REQ 编码如下：
操作码 4 BIT, 00 查询有没有票，01 锁票，10 开锁，11 确认售出
车次 12 BIT，等级 4 BIT，起始站 6 BIT，终点站 6 BIT，一共 4 BYTE一个请求
4、RESP 就是 1 个字节，TRUE OR FALSE
考虑老魏的单机是 2 CPU 8 CORE EACH 4GHZ，假如 1 CPU 4 CORE 2GHZ 大概能达到 1
/8 的性能即 625K/S。老魏看看有没有异议。
老魏负责写 SERVER，如果不想公开 CODE 可以 MAKE BIN，古德霸负责写测试数据和测
试结果。 |
z****e
发帖数: 54598 | 2 用 DISK 替代 NETWORK？
不觉得有道理，显然后者更现实 |
i*****o
发帖数: 1714 | 3 你害老魏？谁不知道network更快？
★ 发自iPhone App: ChineseWeb 8.6
【在 n*****t 的大作中提到】
: 1、用 DISK 替代 NETWORK
: 考虑 SSD 大概是 500M，双 10GBE 大概 2.5G，老魏吃亏点，不过 DISK IO 稍微简单
: 点，大家看看合理不合理，怎么折算。
: 2、测试数据如下，1000 车次，每个车次 5 个等级，每趟车 1000 张票
: 3、REQ 编码如下：
: 操作码 4 BIT, 00 查询有没有票，01 锁票，10 开锁，11 确认售出
: 车次 12 BIT，等级 4 BIT，起始站 6 BIT，终点站 6 BIT，一共 4 BYTE一个请求
: 4、RESP 就是 1 个字节，TRUE OR FALSE
: 考虑老魏的单机是 2 CPU 8 CORE EACH 4GHZ，假如 1 CPU 4 CORE 2GHZ 大概能达到 1
: /8 的性能即 625K/S。老魏看看有没有异议。
|
n*****t
发帖数: 22014 | 4 还好吧，总共 20M REQ 的数据 。。。差别不大吧。如果测试结果只差这点时间，我们
认为通过了？
【在 i*****o 的大作中提到】
: 你害老魏？谁不知道network更快？
:
: ★ 发自iPhone App: ChineseWeb 8.6
|
h**********c
发帖数: 4120 | 5 localhost socket is in memory, the bandwidth is memory bw.
if not is, then should be.
opinion |
L*****e
发帖数: 8347 | 6 第二步具体怎么做差别很大，老魏的数据库里估计没法拿到真实的车次及起点终点靠停
站的数据，所以没法模拟现实应用中的情形，但是如果要支持理论上的各种可能性，老
魏太吃亏。但又不能太简单使之基本没有耦合性。。。
然后关于怎样的测试数据才算是valid的请求，估计他俩能再吵上三个月。。。
1
【在 n*****t 的大作中提到】
: 1、用 DISK 替代 NETWORK
: 考虑 SSD 大概是 500M，双 10GBE 大概 2.5G，老魏吃亏点，不过 DISK IO 稍微简单
: 点，大家看看合理不合理，怎么折算。
: 2、测试数据如下，1000 车次，每个车次 5 个等级，每趟车 1000 张票
: 3、REQ 编码如下：
: 操作码 4 BIT, 00 查询有没有票，01 锁票，10 开锁，11 确认售出
: 车次 12 BIT，等级 4 BIT，起始站 6 BIT，终点站 6 BIT，一共 4 BYTE一个请求
: 4、RESP 就是 1 个字节，TRUE OR FALSE
: 考虑老魏的单机是 2 CPU 8 CORE EACH 4GHZ，假如 1 CPU 4 CORE 2GHZ 大概能达到 1
: /8 的性能即 625K/S。老魏看看有没有异议。
|
n*****t
发帖数: 22014 | 7 这个就是古德八拿各种刁钻的数据去测试了，反正老魏看到的就是把这个区间算锁，不
需要知道0123 到底是哪个车次
【在 L*****e 的大作中提到】
: 第二步具体怎么做差别很大，老魏的数据库里估计没法拿到真实的车次及起点终点靠停
: 站的数据，所以没法模拟现实应用中的情形，但是如果要支持理论上的各种可能性，老
: 魏太吃亏。但又不能太简单使之基本没有耦合性。。。
: 然后关于怎样的测试数据才算是valid的请求，估计他俩能再吵上三个月。。。
:
: 1
|
b*******s
发帖数: 5216 | 8 大人讲话，你什么都不懂的插什么嘴
【在 z****e 的大作中提到】
: 用 DISK 替代 NETWORK？
: 不觉得有道理，显然后者更现实
|
n**x
发帖数: 606 | 9 老魏的发法是用户决定联票如何联，车次，起点，终点都是常量。然后对一个巨大二维
矩阵做interlock加减法。
【在 L*****e 的大作中提到】
: 第二步具体怎么做差别很大，老魏的数据库里估计没法拿到真实的车次及起点终点靠停
: 站的数据，所以没法模拟现实应用中的情形，但是如果要支持理论上的各种可能性，老
: 魏太吃亏。但又不能太简单使之基本没有耦合性。。。
: 然后关于怎样的测试数据才算是valid的请求，估计他俩能再吵上三个月。。。
:
: 1
|
g*****g
发帖数: 34805 | 10 他连compare都不敢做，不用提io serialization/deserialization. 就一太监。
【在 n**x 的大作中提到】
: 老魏的发法是用户决定联票如何联，车次，起点，终点都是常量。然后对一个巨大二维
: 矩阵做interlock加减法。
|
|
|
n*****t
发帖数: 22014 | 11 你也是废话多，就这么个方案，折中一下，大家都能测，也不花大钱。你要没问题就签
字，完了看老魏啥情况。你觉得亏了就提，大家看怎么公平。
好歹弄出个结果，输了赢了也有个交代。老实说，结果跟预期差别不大的话，也是虽败
犹荣，我个人觉得。总比不练强多了。
最后，测试可以多次，不一定一锤子买卖。
【在 g*****g 的大作中提到】
: 他连compare都不敢做，不用提io serialization/deserialization. 就一太监。
|
g*****g
发帖数: 34805 | 12 操，太监连一个compare都不敢做，还让什么步，一个太监就会PA罢了。
【在 n*****t 的大作中提到】
: 你也是废话多，就这么个方案，折中一下，大家都能测，也不花大钱。你要没问题就签
: 字，完了看老魏啥情况。你觉得亏了就提，大家看怎么公平。
: 好歹弄出个结果，输了赢了也有个交代。老实说，结果跟预期差别不大的话，也是虽败
: 犹荣，我个人觉得。总比不练强多了。
: 最后，测试可以多次，不一定一锤子买卖。
|
L*****e
发帖数: 8347 | 13 如果老魏需要解决理论上所有需要解决的情况，那么古德八可以一千个车次，每个联票
请求的起点（甚至停靠站）都是另一个联票请求的中转，那么所有的联票请求得形成一
个巨大的耦合圈，然后500W个都是这样的请求话，多线程P的作用都没有，不断的
rollback反而要花比单线程更多的时间。。。
【在 n*****t 的大作中提到】
: 这个就是古德八拿各种刁钻的数据去测试了，反正老魏看到的就是把这个区间算锁，不
: 需要知道0123 到底是哪个车次
|
d***a
发帖数: 13752 | 14 从软件开发的角度来说，算法内部怎么做都可以，只要输出对应于输入是正确的就行了。
是系统还是用户来决定联票的问题，双方有定论了吗？这个是关键。如果这个spec不一
致，那就算了，别再上火吵下去了。Spec上可以争几个月都没有结果。
【在 n**x 的大作中提到】
: 老魏的发法是用户决定联票如何联，车次，起点，终点都是常量。然后对一个巨大二维
: 矩阵做interlock加减法。
|
n*****t
发帖数: 22014 | 15 你管他怎么做，最后性能达标没有重票就行了，废话多
【在 g*****g 的大作中提到】
: 操，太监连一个compare都不敢做，还让什么步，一个太监就会PA罢了。
|
d***a
发帖数: 13752 | 16 直觉上说，这是个NP-hard的问题，如果要求schedule结果是优化的。
【在 L*****e 的大作中提到】
: 如果老魏需要解决理论上所有需要解决的情况，那么古德八可以一千个车次，每个联票
: 请求的起点（甚至停靠站）都是另一个联票请求的中转，那么所有的联票请求得形成一
: 个巨大的耦合圈，然后500W个都是这样的请求话，多线程P的作用都没有，不断的
: rollback反而要花比单线程更多的时间。。。
|
n*****t
发帖数: 22014 | 17 老魏这里不存在这问题，是处理 5M 的 request，不是出 5M 张票
【在 L*****e 的大作中提到】
: 如果老魏需要解决理论上所有需要解决的情况，那么古德八可以一千个车次，每个联票
: 请求的起点（甚至停靠站）都是另一个联票请求的中转，那么所有的联票请求得形成一
: 个巨大的耦合圈，然后500W个都是这样的请求话，多线程P的作用都没有，不断的
: rollback反而要花比单线程更多的时间。。。
|
n*****t
发帖数: 22014 | 18 现在 12306 就是用户选车次，决定怎么联票，系统没必要干这活
了。
【在 d***a 的大作中提到】
: 从软件开发的角度来说，算法内部怎么做都可以，只要输出对应于输入是正确的就行了。
: 是系统还是用户来决定联票的问题，双方有定论了吗？这个是关键。如果这个spec不一
: 致，那就算了，别再上火吵下去了。Spec上可以争几个月都没有结果。
|
L*****e
发帖数: 8347 | 19 我知道，理论的valid的数据，和现实真实数据相差很远，理论上valid的数据，可以让
老魏解决方案的多线程全部白费，就是在interlock上做无用功的加减法。。。
【在 n**x 的大作中提到】
: 老魏的发法是用户决定联票如何联，车次，起点，终点都是常量。然后对一个巨大二维
: 矩阵做interlock加减法。
|
z****e
发帖数: 54598 | 20 简化得太厉害了
【在 n*****t 的大作中提到】
: 老魏这里不存在这问题，是处理 5M 的 request，不是出 5M 张票
|
|
|
n*****t
发帖数: 22014 | 21 12306 能处理那么多 request 吗？实际能有 1/10 处理能力需求就满足了。
你也别整没用的，要不你提个大家方便验证的方案
【在 z****e 的大作中提到】
: 简化得太厉害了
|
z****e
发帖数: 54598 | 22 simulation也不能把所有东西简化成一个计数器阿
没有太多意义
【在 n*****t 的大作中提到】
: 12306 能处理那么多 request 吗？实际能有 1/10 处理能力需求就满足了。
: 你也别整没用的，要不你提个大家方便验证的方案
|
L*****e
发帖数: 8347 | 23 不是说出票，是说他的interlocked的rollback。假设他两百个线程同时处理两百个联
票请求，这两百给联票请求是上面我说到的一个大耦合圈，那么第一个请求的成功或失
败会影响其余199个的成功或失败。。。
【在 n*****t 的大作中提到】
: 老魏这里不存在这问题，是处理 5M 的 request，不是出 5M 张票
|
n*****t
发帖数: 22014 | 24 艾玛，计数器拿到了你前端上 cloud 慢慢整不行啊，就是纯体力活了，还非得把
12306 全实现算，现实吗？
【在 z****e 的大作中提到】
: simulation也不能把所有东西简化成一个计数器阿
: 没有太多意义
|
z****e
发帖数: 54598 | 25 那这个也不重要
那个也不重要
12306还有什么需要老魏处理的阿？
【在 n*****t 的大作中提到】
: 艾玛，计数器拿到了你前端上 cloud 慢慢整不行啊，就是纯体力活了，还非得把
: 12306 全实现算，现实吗？
|
L***n
发帖数: 6727 | 26 这个，本版广大网友可以帮这两位刷数据，访问铁路网站，copy poste一些车次起点终点
停靠信息
【在 L*****e 的大作中提到】
: 第二步具体怎么做差别很大，老魏的数据库里估计没法拿到真实的车次及起点终点靠停
: 站的数据，所以没法模拟现实应用中的情形，但是如果要支持理论上的各种可能性，老
: 魏太吃亏。但又不能太简单使之基本没有耦合性。。。
: 然后关于怎样的测试数据才算是valid的请求，估计他俩能再吵上三个月。。。
:
: 1
|
n*****t
发帖数: 22014 | 27 抛开这个不谈，实际铁道部不关心这个问题，票一会有一会没是常态，所以才有刷票的
必要，最终都会卖掉，不重票就行
【在 L*****e 的大作中提到】
: 不是说出票，是说他的interlocked的rollback。假设他两百个线程同时处理两百个联
: 票请求，这两百给联票请求是上面我说到的一个大耦合圈，那么第一个请求的成功或失
: 败会影响其余199个的成功或失败。。。
|
n*****t
发帖数: 22014 | 28 重要的是系统的极限性能是多大，老魏用单机搞定，古德八说领号排队
作为普通网民，我对排队毫无兴趣，我很想知道极限性能是多少
【在 z****e 的大作中提到】
: 那这个也不重要
: 那个也不重要
: 12306还有什么需要老魏处理的阿？
|
h**********c
发帖数: 4120 | 29 Maybe, the data structure:
simple graph connected
dijkstra find path |
L*****e
发帖数: 8347 | 30 哦，我以为他们说过实际有票但是说没票也算failure呢。。。（退票的情况不算）
【在 n*****t 的大作中提到】
: 抛开这个不谈，实际铁道部不关心这个问题，票一会有一会没是常态，所以才有刷票的
: 必要，最终都会卖掉，不重票就行
|
|
|
z****e
发帖数: 54598 | 31 要算吧，那要不然还做什么，错误率太高了
【在 L*****e 的大作中提到】
: 哦，我以为他们说过实际有票但是说没票也算failure呢。。。（退票的情况不算）
|
L*****e
发帖数: 8347 | 32 不要想复杂了，老魏说的是用户提供车次，起点，终点，系统不需要找路径。。。
【在 h**********c 的大作中提到】
: Maybe, the data structure:
: simple graph connected
: dijkstra find path
|
t****t
发帖数: 6806 | 33 没有关系, 成功或失败都算一个请求. 失败了加回去就可以了.
【在 L*****e 的大作中提到】
: 不是说出票，是说他的interlocked的rollback。假设他两百个线程同时处理两百个联
: 票请求，这两百给联票请求是上面我说到的一个大耦合圈，那么第一个请求的成功或失
: 败会影响其余199个的成功或失败。。。
|
n*****t
发帖数: 22014 | 34 你怎么验证？实际情况中甲乙同时申请一张票，结果乙经过的路由器打了个嘎嘣，甲的
thread 刚好慢了一拍，最后谁拿到票无法确定。
所以这种情况不需要纠结，也没法纠结，保证不重票就没事了。
【在 z****e 的大作中提到】
: 要算吧，那要不然还做什么，错误率太高了
|
i*****o
发帖数: 1714 | 35 这个设定很合理。而且大部分的请求（2/3）是query。
★ 发自iPhone App: ChineseWeb 8.6
【在 L*****e 的大作中提到】
: 不要想复杂了，老魏说的是用户提供车次，起点，终点，系统不需要找路径。。。
|
L*****e
发帖数: 8347 | 36 那么老魏的方案就是：
输入：车次，起点，终点
对该车次从起点到终点的每一个站，依次：
（1）读取剩余票数，interlock
（2）如果大于0，票数减一，解锁。
（3）如果等于0，rollback从起点到当前站之前所有站的票数（因为是加1所以不用
锁），并返回失败。
这样，确实是联票申请的复杂度只和联票内的停靠站数有关。联票就只把它当做更长路
程的两个合并车次而已，联票的引入不过是增加了请求失败的概率，不会造成重票。。。
【在 z****e 的大作中提到】
: 要算吧，那要不然还做什么，错误率太高了
|
T********i
发帖数: 2416 | 37 你的基本思路对。但是对interlocked 加减理解还是错误。
【在 L*****e 的大作中提到】
: 那么老魏的方案就是：
: 输入：车次，起点，终点
: 对该车次从起点到终点的每一个站，依次：
: （1）读取剩余票数，interlock
: （2）如果大于0，票数减一，解锁。
: （3）如果等于0，rollback从起点到当前站之前所有站的票数（因为是加1所以不用
: 锁），并返回失败。
: 这样，确实是联票申请的复杂度只和联票内的停靠站数有关。联票就只把它当做更长路
: 程的两个合并车次而已，联票的引入不过是增加了请求失败的概率，不会造成重票。。。
|
z****e
发帖数: 54598 | 38 客户端程序拿到结果后放到一个DB里面
然后写程序来验证
【在 n*****t 的大作中提到】
: 你怎么验证？实际情况中甲乙同时申请一张票，结果乙经过的路由器打了个嘎嘣，甲的
: thread 刚好慢了一拍，最后谁拿到票无法确定。
: 所以这种情况不需要纠结，也没法纠结，保证不重票就没事了。
|
t****t
发帖数: 6806 | 39 不用锁, 直接减一. 如果失败就加一.
。。
【在 L*****e 的大作中提到】
: 那么老魏的方案就是：
: 输入：车次，起点，终点
: 对该车次从起点到终点的每一个站，依次：
: （1）读取剩余票数，interlock
: （2）如果大于0，票数减一，解锁。
: （3）如果等于0，rollback从起点到当前站之前所有站的票数（因为是加1所以不用
: 锁），并返回失败。
: 这样，确实是联票申请的复杂度只和联票内的停靠站数有关。联票就只把它当做更长路
: 程的两个合并车次而已，联票的引入不过是增加了请求失败的概率，不会造成重票。。。
|
L*****e
发帖数: 8347 | 40 哦，没用过，回头找资料加强学习。。。
【在 T********i 的大作中提到】
: 你的基本思路对。但是对interlocked 加减理解还是错误。
|
|
|
b*******s
发帖数: 5216 | 41 lol
【在 z****e 的大作中提到】
: 客户端程序拿到结果后放到一个DB里面
: 然后写程序来验证
|
n*****t
发帖数: 22014 | 42 靠，本来结果就是不确定的，你能说先递申请的一定拿到票啊？
除了重票，你都无法验证
【在 z****e 的大作中提到】
: 客户端程序拿到结果后放到一个DB里面
: 然后写程序来验证
|
z****e
发帖数: 54598 | 43 拿不到再申请，先假设一切正确，除非系统挂了
然后再验证结果，你要担心先后，加时间戳咯
【在 n*****t 的大作中提到】
: 靠，本来结果就是不确定的，你能说先递申请的一定拿到票啊？
: 除了重票，你都无法验证
|
i*****o
发帖数: 1714 | 44 我个人感觉你的算法很有希望成功，为什么不写个接口让大家未来看看？即使goodbug
不认同其它人说不定愿意一试。
★ 发自iPhone App: ChineseWeb 8.6
【在 T********i 的大作中提到】
: 你的基本思路对。但是对interlocked 加减理解还是错误。
|
b*******s
发帖数: 5216 | 45 你还真有耐心，我看到这堆又在说搞笑的话就直接嘲讽之，还不告诉他错在哪里
【在 n*****t 的大作中提到】
: 靠，本来结果就是不确定的，你能说先递申请的一定拿到票啊？
: 除了重票，你都无法验证
|
b*******s
发帖数: 5216 | 46 lol
【在 z****e 的大作中提到】
: 拿不到再申请，先假设一切正确，除非系统挂了
: 然后再验证结果，你要担心先后，加时间戳咯
|
z****e
发帖数: 54598 | 47 不要你来说，SCP知道怎么搞没？
【在 b*******s 的大作中提到】
: 你还真有耐心，我看到这堆又在说搞笑的话就直接嘲讽之，还不告诉他错在哪里
|
L*****e
发帖数: 8347 | 48 说得也有道理，比如说线程1对当前变量减一，同时线程2也对这个变量减一使得该变量
为0了，那么线程1只要对减一的结果做一个检查，如果小于0就是失败，然后rollback
。。。
但是，锁更贵还是减一后的结果检查更贵？
【在 t****t 的大作中提到】
: 不用锁, 直接减一. 如果失败就加一.
:
: 。。
|
t****t
发帖数: 6806 | 49 比较一下是不是大于0能有多贵???
rollback
【在 L*****e 的大作中提到】
: 说得也有道理，比如说线程1对当前变量减一，同时线程2也对这个变量减一使得该变量
: 为0了，那么线程1只要对减一的结果做一个检查，如果小于0就是失败，然后rollback
: 。。。
: 但是，锁更贵还是减一后的结果检查更贵？
|
z****e
发帖数: 54598 | 50 难就难在排队上
极限有p用，论证了半天500w的计数器在单机上可行
你很有兴趣知道这个结果？
所以一开始就说了，你要上主机，也行
但是这个策略是错的，主机太贵
一定会往分布式方向去发展
老魏就是死活不承认
现在自己也说了，11台机器，你说这是什么？
所谓单机一开始就是有意误导
【在 n*****t 的大作中提到】
: 重要的是系统的极限性能是多大，老魏用单机搞定，古德八说领号排队
: 作为普通网民，我对排队毫无兴趣，我很想知道极限性能是多少
|
|
|
L*****e
发帖数: 8347 | 51 对interlock不懂，听他们的意思好像是对一个变量计算开始时就算是自动锁上了？然
后计算完成时，就解锁了？那就是说和0比较的运算时间于加1的计算时间相比，比较应
该比更新的计算时间短吧？
但是别忘了，如果失败的概率大的话，是先做了一次无用计算使得变量成为-1后再
rollback的，所以里外里多了两次计算。。。
如果失败的概率小，你的做法可以省时间，如果失败的概率大的话，会更费时间。。。
【在 t****t 的大作中提到】
: 比较一下是不是大于0能有多贵???
:
: rollback
|
z****e
发帖数: 54598 | 52 应该让老魏做
但是老魏如果这么做，估计他的cpu顶不住
如果让古德霸来做
那后果对老魏来说不可接受，因为联票方案可以有很多种
挨个试都弄死老魏的机器了，如果前一秒有一定数量的人拿不到票
那么重试是必然的，那下一秒就不只有500w了，而是550w
然后逐步增加，最后太多人试，挂了
了。
【在 d***a 的大作中提到】
: 从软件开发的角度来说，算法内部怎么做都可以，只要输出对应于输入是正确的就行了。
: 是系统还是用户来决定联票的问题，双方有定论了吗？这个是关键。如果这个spec不一
: 致，那就算了，别再上火吵下去了。Spec上可以争几个月都没有结果。
|
t****t
发帖数: 6806 | 53 对.
举个例子.
一开始n=3, b=-1.
lock xadd n, b
就是n=n+b, b=n-b. 这两步是atomic的. 结果n=2, b=3.
【在 L*****e 的大作中提到】
: 对interlock不懂，听他们的意思好像是对一个变量计算开始时就算是自动锁上了？然
: 后计算完成时，就解锁了？那就是说和0比较的运算时间于加1的计算时间相比，比较应
: 该比更新的计算时间短吧？
: 但是别忘了，如果失败的概率大的话，是先做了一次无用计算使得变量成为-1后再
: rollback的，所以里外里多了两次计算。。。
: 如果失败的概率小，你的做法可以省时间，如果失败的概率大的话，会更费时间。。。
|
