Well, after dual boot with GRUB, if the corresponding Linux partition is deleted, the windows MBR must be recovered in order to boot up.
1. get Microsoft media creation tool
2. create a installation USB
3. boot from USB UEFI
4. choose recovery / advanced option
5. In the cmd, type "bootsect /nt60 <drive_letter>: /mbr
6. exit cmd
7. reboot
Saturday, January 30, 2016
Tuesday, January 26, 2016
Secure Ubuntu Server
There are some basic stuff mentioned in the following URLs.
https://www.thefanclub.co.za/how-to/how-secure-ubuntu-1204-lts-server-part-1-basics
https://www.thefanclub.co.za/how-to/how-secure-ubuntu-1204-lts-server-part-2-gui-installer-script
There are some more.
1) Disable USB boot.
If USB boot is enabled, outsider can simply boot machine with their USB bootable image. Then, everything will be exposed.
2)
https://www.thefanclub.co.za/how-to/how-secure-ubuntu-1204-lts-server-part-1-basics
https://www.thefanclub.co.za/how-to/how-secure-ubuntu-1204-lts-server-part-2-gui-installer-script
There are some more.
1) Disable USB boot.
If USB boot is enabled, outsider can simply boot machine with their USB bootable image. Then, everything will be exposed.
2)
Friday, January 1, 2016
标 题: 请教一下老魏pc12306中的算法。
发信人: nanxiang7 (zz), 信区: Programming
标 题: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Sun Dec 27 04:54:29 2015, 美东)
放假，终于有时间run GDB，才对老魏的程序有些理解了。仍然有些疑问。想向老魏和
大家请教。
先陈述一下基本的理解：
TrainTicketMap 是关键的数据库，表征对应车次当前所有空座. 它是一个二维数组，
两个indices分别是起始站和（站数 - 1). 它的值是一个stack（由单向链实现）。
stack上每一元素对应一个座位的站次间的空座范围，表示此座位从该起始站开始数该
站数范围内是空的。该元素的next指针指向stack上下一个对应不同座位的元素。
在初始状态，每个座位从起始站0开始10站都空，所以这个二维数组只在index［0，9］
有非空stack，里面压了对应所有座位的3000个元素，座位1在最上。假设第一个请求是
起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］从［
0，9］变为［0，2］和［4，5］。所以，对这个二维数组的操作（reserve函数里）是
：座位1在index［0，9］stack上的元素被free回TicketPool，从TicketPool重新
allocate两个元素给座位1，分别压进在index［0，2］和［4，5］的stacks。
整个操作分两步：allocate(); reserve().
allocate() 在TrainTicketMap找覆盖所请求站次的空座范围。搜索范围是顺着预先设
定的SearchOffsets，从小到大。所用时间较大而且不定，只读而不修改在
TrainTicketMap。是非transaction部分。
reserve() 是transaction部分，修改TrainTicketMap，用时很少并且固定。
请问，上述理解对吗？
我有几个问题：
1. 对站数能scale吗？如果站数从10变成100，TrainTicketMap与站数^2成正比，搜索
范围就增大100倍。allocate（）时间就增大100倍。当然可以用一个dedicated core
做reserve，把allocate分散到其它cores上。但如何同步就需要一些比较细碎的设计，
不如现在这样简洁了。另外，估计现有的core数很难消化得了100倍的计算量。所以，
对100站是不是就很难达到1M/s的指标了？
2. 如果朝实际方向再进一步，支持一个请求内多个座位连座，该怎么做？这应该是非
常贴近真实需要的。一家人一起走，座位应该是一起买，坐在一起的吧？如果顺着同样
的算法，TrainTicketMap是不是就该扩展成四维，多出的两维是起始座和座位数。那么
，搜索范围就扩大3000^2倍。这个算法是不是就不现实了？
3. 这个算法是源于成熟的理论，还是老魏或老姜的原创？无论如何，针对赌约的指标
要求，解决得非常精巧漂亮，令人佩服。这个问题，在逻辑上相当于在一个二维空间（
两轴分别是座位和站）不空的点上画叉叉，然后找可以容下长（连续座位数）宽（站数
）align在起始站的长方形的空域。这是不是另外还有更generic更好scale的理论和算
法？
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 10:53:35 2015, 美东)
不敢当，我们可以讨论一下。
首先，这个算法是老姜原创。2年多以前他就贴出来过。很不幸立刻淹没在一大堆口水
帖中。这也证明了这个版根本不是严肃讨论技术的地方。我只不过在实现过程中做了一
些优化而已。这个事实我已经反复生命过，不敢掠人之美。
1。站数scalability肯定不好，算法本身很简单。站数从10变成100，allocate（）时
间就增大100倍。这个是肯定的。但是我们讨论的是火车票，不是汽车票。100站现实中
不可能。20站有没有可能我不知道。20站allocate()就要慢四倍。但是可以接受。
2。多个座位连坐的问题。这个倒是不用3000^2倍。其实如果把TrainTicketMap稍加改
变，座位不是stack而是bitmap的话，就会容易很多。搜索连坐估计可以做到O(m^2 ×
log(n))，m是站数，n是座位数；实际代价可以很小。
其实我现在的算法实现也很仓促。比如现在的TrainTicketMap是一个矩形，实际上只用
了一半，就是沿对角线的三角形而已。主要是我看指标远远超过了，就将就了。
事实上，这个算法很适合scale到外围机上去。这也是我故意分两步allocate和reserve
的原因。外围机通过allocate算法可以filter大量的无效请求。而且这个算法能够线性
分布到多核上面去。
至于复杂业务逻辑，可以选择在外围机或者核心机实现，或者both。
其实我认为，相对于算法，大家更应该思考架构的问题。不论业务逻辑复杂与否，这种
耦合问题究竟应该采用何种架构？当然考虑问题要全面，实现，维护，运营成本都要考
虑。简单逻辑你说不考虑公平和运营成本，把3000数据库当分布式计数器用。那么难道
稍微复杂的业务逻辑数据库就能够更优化？给我写一个query看看？
发信人: walkrandom (walkrandom), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 13:02:23 2015, 美东)
个人觉得，魏老师的这个解决方案是一个高频交易的classic demo codebase。要进东
部银行的可以好好看看。
CPU比memory快10倍，memory比SSD快10倍，SSD比hard disk快10倍。hard disk比网线
快10倍。
魏老师告诉我们，高频交易最重要的是全内存运行，规避磁盘的IO限制。实现毫秒级的
transaction，一定要单机高并发。这是为什么东部银行喜欢折磨C＋＋的原因。
像12306这样的电商，瓶颈在磁盘和网线。DB建在磁盘上面，所以一定要选性能最好的
DB。 网线的堵塞没办法，只有靠买CDN来解决。电商大部分的钱都花在这方面了。
魏老师的性能再好，估计也不能改变磁盘和网线的物理限制。所以。。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 13:40:29 2015, 美东)
其实吧，倒不如说该用啥就用啥。指望啥都有现成的，还要你干啥？
你现在，离磁盘和网线的物理限制还差的很远。大概有数量级的差别吧。比如，10G，
40G网卡现在大把。一台server装两块，就是20-80G。能服务多少12306并发用户？
我们谈架构，throughput是最重要的性能指标。所以我当年第一贴就说了，别的都是浮
云，只要拿出throughput就好了。比如我系统能持续多大的throughput，20G,40G,80G
？这事儿，和单机多机真的无关。
【 在 walkrandom (walkrandom) 的大作中提到: 】
: 个人觉得，魏老师的这个解决方案是一个高频交易的classic demo codebase。要进东
: 部银行的可以好好看看。
: CPU比memory快10倍，memory比SSD快10倍，SSD比hard disk快10倍。hard disk比网线
: 快10倍。
: 魏老师告诉我们，高频交易最重要的是全内存运行，规避磁盘的IO限制。实现毫秒级的
: transaction，一定要单机高并发。这是为什么东部银行喜欢折磨C＋＋的原因。
: 像12306这样的电商，瓶颈在磁盘和网线。DB建在磁盘上面，所以一定要选性能最好的
: DB。 网线的堵塞没办法，只有靠买CDN来解决。电商大部分的钱都花在这方面了。
: 魏老师的性能再好，估计也不能改变磁盘和网线的物理限制。所以。。。
发信人: rc256 (ΜΟΛΩΝ ΛΑΒΕ), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 15:08:27 2015, 美东)
Use bitmask makes great sense. If we assume at most 32 stations, then a
single uint32_t (unsigned) can represent one seat availability. A single
train seatmap is just an array of unsigned. Assume 4096 seats per train,
then the entire one train seatmap is only 16KB.
The reserve function would look like this:
unsigned _seatmap[NSEATS];
int Train::reserve(int start, int length)
{
//return seat index reserved, -1 if not available
unsigned mask = ((1 << length)-1) << start;
for (unsigned *seat = _seatmap; seat<_seatmap+NSEATS; ++seat) {
if (!(*seat & mask)) {
*seat |= mask;
return seat - _seatmap;
}
}
return -1;
}
This is essentially a linear search, but should be really fast because
almost all seat is within cache and access is linear. Each match is just a
32bit bitwise AND operation.
发信人: mbp (Mac Book Pro), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 16:04:49 2015, 美东)
确实是hft里面经常看到的高性能单机版无io的东西。
【 在 walkrandom (walkrandom) 的大作中提到: 】
: 个人觉得，魏老师的这个解决方案是一个高频交易的classic demo codebase。要进东
: 部银行的可以好好看看。
: CPU比memory快10倍，memory比SSD快10倍，SSD比hard disk快10倍。hard disk比网线
: 快10倍。
: 魏老师告诉我们，高频交易最重要的是全内存运行，规避磁盘的IO限制。实现毫秒级的
: transaction，一定要单机高并发。这是为什么东部银行喜欢折磨C＋＋的原因。
: 像12306这样的电商，瓶颈在磁盘和网线。DB建在磁盘上面，所以一定要选性能最好的
: DB。 网线的堵塞没办法，只有靠买CDN来解决。电商大部分的钱都花在这方面了。
: 魏老师的性能再好，估计也不能改变磁盘和网线的物理限制。所以。。。
发信人: walkrandom (walkrandom), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 16:20:47 2015, 美东)
单数据中心，运营商能给的稳定带宽能有100MB/s就不错了。每个新用户第一次登陆可
能就下载100KB，想象一下1000个用户同时浏览。
所以理想很丰满，现实总是很残酷。
【 在 TeacherWei (TW) 的大作中提到: 】
: 其实吧，倒不如说该用啥就用啥。指望啥都有现成的，还要你干啥？
: 你现在，离磁盘和网线的物理限制还差的很远。大概有数量级的差别吧。比如，10G，
: 40G网卡现在大把。一台server装两块，就是20-80G。能服务多少12306并发用户？
: 我们谈架构，throughput是最重要的性能指标。所以我当年第一贴就说了，别的都是浮
: 云，只要拿出throughput就好了。比如我系统能持续多大的throughput，20G,40G,
80G
: ？这事儿，和单机多机真的无关。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 16:24:03 2015, 美东)
实际情况比这个复杂一些。连座加上最小碎片检索可能需要先Or最多55种可能性，然后
再搜索。
AVX + prefetch每cycle处理512 bit是有可能的。
【 在 rc256 (ΜΟΛΩΝ ΛΑΒΕ) 的大作中提到: 】
: Use bitmask makes great sense. If we assume at most 32 stations, then a
: single uint32_t (unsigned) can represent one seat availability. A single
: train seatmap is just an array of unsigned. Assume 4096 seats per train,
: then the entire one train seatmap is only 16KB.
: The reserve function would look like this:
: unsigned _seatmap[NSEATS];
: int Train::reserve(int start, int length)
: {
: //return seat index reserved, -1 if not available
: unsigned mask = ((1 << length)-1) << start;
: ...................
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 16:28:28 2015, 美东)
你就别闹了。照你的算法，Google和好虫他们Netflix用户都可以吃屎去了。
【 在 walkrandom (walkrandom) 的大作中提到: 】
: 单数据中心，运营商能给的稳定带宽能有100MB/s就不错了。每个新用户第一次登陆可
: 能就下载100KB，想象一下1000个用户同时浏览。
: 所以理想很丰满，现实总是很残酷。
: 80G
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 03:28:34 2015, 美东)
感谢老魏的详尽回答！老姜的算法和老魏的实现都做得很漂亮。很同意关于架构的论述。
对多票连座如何实现仍有不解。能否具体说说“把TrainTicketMap稍加改变，座位不是
stack而是bitmap”和“连座加上最小碎片检索可能需要先Or最多55种可能性”？
TrainTicketMap的index是［起始站，站数－1］。在［起始站，站数－1］的stack上的
非零值表示对某座这个站的范围（起始站－》起始站＋站数－1）是空的。改成bitmap
是不是bitmap里的1bits和stack上的元素有相同的含义？从同一个［起始站，站数－1
］点上找到的多个座位很可能是不相连的，而相连的座位可能在不同的［起始站，站数
－1］点上，怎样找？
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 03:56:55 2015, 美东)
这个做法没有考虑每一站的seatmap都是不同的而且中途不换座。另外，这个函数没有
处理跨word边界的情况，当然，这是小问题。
【 在 rc256 (ΜΟΛΩΝ ΛΑΒΕ) 的大作中提到: 】
: Use bitmask makes great sense. If we assume at most 32 stations, then a
: single uint32_t (unsigned) can represent one seat availability. A single
: train seatmap is just an array of unsigned. Assume 4096 seats per train,
: then the entire one train seatmap is only 16KB.
: The reserve function would look like this:
: unsigned _seatmap[NSEATS];
: int Train::reserve(int start, int length)
: {
: //return seat index reserved, -1 if not available
: unsigned mask = ((1 << length)-1) << start;
: ...................
发信人: rc256 (ΜΟΛΩΝ ΛΑΒΕ), 信区: Programming
标 题: RE: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 07:11:50 2015, 美东)
1. 中途换座 probably is not a requirement. If really in need, this probably
should be a ticket exchange or reissue.
2. Not sure if I understand "每一站的seatmap都是不同". My definition of one
seat bitmap word is vertical (availability throughout stations for one
particular seat) not horizontal (a snapshot of seat availability at
particular station) if you think entire train seat bitmap is a matrix, the
layout is column major indexes first. It is important because one bitwise
AND operation can check if this seat is a match for the trip riding mask.
【 在 nanxiang7 (zz) 的大作中提到: 】
这个做法没有考虑每一站的seatmap都是不同的而且中途不换座。另外，这个函数没有
处理跨word边界的情况，当然，这是小问题。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 10:18:44 2015, 美东)
还是代码说话吧：
增加了一个函数： allocate2
其目的是，找到所有符合条件的座位空间，放到一个数组里。数组大小是座位数（3000）
剩下的，愿意怎么找相邻座位都简单了。至于优化也很简单，就是找sum(碎片）最小的
相邻座位。
注意，allocate和reserve可以优化到不同的core上做pipeline。也就是机行代码的事
情。
void TrainTicketMap::allocate2(int start, int length, Ticket **seats) {
length--; // normalize to [0, 9]
for (Offsets::iterator it = offsets.begin(); it != offsets.end(); ++it) {
register int curStart = start + it->start;
register int curLength = length - it->start + it->length;
if (curStart >= 0 && curLength < SEGMENTS) {
//printf("Searching %d %d\n", curStart, curLength);
size_t index = curStart + curLength * SEGMENTS;
Ticket *cur = _map[index];
while (cur) {
seats[cur->_seat] = cur;
cur = cur->_next;
}
}
}
}
这个allocate2性能如何呢？
下面的代码基本上是worst case，每次都会收集满3000座位，而且促进最大cache miss。
static void benchmark() {
double t1 = getTime();
printf("start benchmark\n");
Ticket *seats[SEATS];
for (size_t i=0; i<10000000LL; i++) {
int train = rand() % TRAINS;
int start = rand() % SEGMENTS;
int length = rand() % (SEGMENTS - start);
if (length == 0) {
length = 1;
}
memset(seats, 0, sizeof(Ticket *) * SEATS);
trains[train]->allocate2(start, length, seats);
}
double t2 = getTime();
printf("Total time = %f\n", t2 - t1);
}
结果：1000万张票大约34秒。
所以如果支持无限连座，worst case大约30万票/s。Best case可以多核并行，仍然能
超过1000万。
注意，allocate2仍然能够无限scalable。所以查询的throughput基本是无限的。
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: RE: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 10:59:45 2015, 美东)
My bad. I misunderstood seatmap as one bit per seat. You actually mean one
bit per station.
So, it is just scanning the array of seats with complexity of O(seats).
TrainTicketsMap is not used. Right?
【 在 rc256 (ΜΟΛΩΝ ΛΑΒΕ) 的大作中提到: 】
: There is no word boundary problem because at most 32 stations therefore a
: 32bit unsigned represents one seat availability throughout all stations.
: As for adjacent seat issue, we can extend to 64(2 seats) or 128 bit(four
: seats in a row) If no adjacent seats available you can also try to find
: available seats with minimal distance after first scan.
: Like teacher Wei said if you optimize for sse/avx, it is possible to check
: 512bits in a cycle, or 16 seats per cycle. For 4096 seats, you only need
256
: cycles, approaching 85ns (at 3GHz) in worst case.
: The key here is to minimize memory footprint to have sequential cache
memory
: access most of the time. This should be able to achieve an order of
: ...................
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 11:02:18 2015, 美东)
谢谢老魏！确实用代码说话是最清楚的。：）
理解你的做法了。每次memset清空seat数组，找出所有的范围，排出所有seats，然后
找连座和优化碎片就容易了。我没往这个方向想是因为以为这样会慢(O(n) complexity
)，现在看你的benchmark确实performance也还不错。
多谢多谢！
【 在 TeacherWei (TW) 的大作中提到: 】
: 还是代码说话吧：
: 增加了一个函数： allocate2
: 其目的是，找到所有符合条件的座位空间，放到一个数组里。数组大小是座位数（
3000）
: 剩下的，愿意怎么找相邻座位都简单了。至于优化也很简单，就是找sum(碎片）最小的
: 相邻座位。
: 注意，allocate和reserve可以优化到不同的core上做pipeline。也就是机行代码的事
: 情。
: void TrainTicketMap::allocate2(int start, int length, Ticket **seats) {
: length--; // normalize to [0, 9]
: for (Offsets::iterator it = offsets.begin(); it != offsets.end(); ++it
) {
: ...................
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 11:28:04 2015, 美东)
其实还有很多可以讨论的。比如，复杂搜索例如连座之类，是否放在外围机比较好？这
样，核心机出票保证>1000万/s没有问题。
还有，我开始确实考虑每个座位block用bitmap，这样3000要375 bytes。当然OR操作要
用AVX加速。memory带宽需求显著增加，但是实际上不见得比我的allocate2慢。当然需
要实际测才知道。
至于3000数据库并行，我还真希望qxc写个query出来，别的不说，先把单张票优化一下
给我看看？
另外，这个worst case实际上是不会发生的。即使10%请求都是连座的，性能依然远超
1M/s。
至于12306用的gemfire内存数据库，gemfire还是靠Bear Stearns发家的。那时期我还
在Bear Stearns prop desk做Associate Director。具体情况我还是比较了解的。我不
认为gemfire在系统中能够起到任何关键作用。
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 13:08:57 2015, 美东)
reserve() 是应该在一个dedicated的core上以保证速度。复杂搜索可以offload到其它
cores上。你说的外围机是这些cores，还是真正的机子？如果是真正的机子，memory不
在一个系统内，还需要一些message queue的设计吧？
bitmap有可能更快。既然支持AVX，memory带宽应该够吧。
12306的瓶颈估计还是在IO，而不是这些内存操作。
我还有一个不清楚的地方，就是如何处理退票。如果付款出错，就需要把票返回到
TrainTicketsMap里，另外还需要合并原来被此票分裂的范围。这是不是也对称地分两
步，先搜索被此票分裂的范围，再进transaction写进map里？
【 在 TeacherWei (TW) 的大作中提到: 】
: 其实还有很多可以讨论的。比如，复杂搜索例如连座之类，是否放在外围机比较好？这
: 样，核心机出票保证>1000万/s没有问题。
: 还有，我开始确实考虑每个座位block用bitmap，这样3000要375 bytes。当然OR操作要
: 用AVX加速。memory带宽需求显著增加，但是实际上不见得比我的allocate2慢。当然需
: 要实际测才知道。
: 至于3000数据库并行，我还真希望qxc写个query出来，别的不说，先把单张票优化一下
: 给我看看？
: 另外，这个worst case实际上是不会发生的。即使10%请求都是连座的，性能依然远超
: 1M/s。
: 至于12306用的gemfire内存数据库，gemfire还是靠Bear Stearns发家的。那时期我还
: ...................
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 13:38:23 2015, 美东)
单机内，不相关搜索可以offload到多核，所以实际性能应该远远超过1M/s。除非像
goodbug和zhaoce那样专门选最恶劣的sequence来测试。
外围机是真正的机子，本来就需要message queue设计，这个我说过多次了，机制和hot
standby recovery一样。其实，设计中，任何外围机都能当hot standby使用的。
这种load，多机间multicast sync状态基本能够达到latency微秒级别。
退票反正也不多。是一个worst case O(SEATS)的过程。实际性能最差应该在单核每秒
20万-30万票。平均应该远超。
【 在 nanxiang7 (zz) 的大作中提到: 】
: reserve() 是应该在一个dedicated的core上以保证速度。复杂搜索可以offload到其它
: cores上。你说的外围机是这些cores，还是真正的机子？如果是真正的机子，memory不
: 在一个系统内，还需要一些message queue的设计吧？
: bitmap有可能更快。既然支持AVX，memory带宽应该够吧。
: 12306的瓶颈估计还是在IO，而不是这些内存操作。
: 我还有一个不清楚的地方，就是如何处理退票。如果付款出错，就需要把票返回到
: TrainTicketsMap里，另外还需要合并原来被此票分裂的范围。这是不是也对称地分两
: 步，先搜索被此票分裂的范围，再进transaction写进map里？
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 14:08:33 2015, 美东)
懂了，多谢！
多机间multicast sync状态真能达到latency微秒级别吗？throughput是没问题的。但
是，就单个ticket的latency来说，上下两边的protocal stack就要花不少时间吧，再
加上处理message queue的延迟(到queue里也不一定能马上处理），能压缩到微秒级
吗？我没实际测过，不知道。能否说说在实际HFT系统里的message，除去网络的
延迟，在机子里传递过程需要多少时间？
【 在 TeacherWei (TW) 的大作中提到: 】
: 单机内，不相关搜索可以offload到多核，所以实际性能应该远远超过1M/s。除非像
: goodbug和zhaoce那样专门选最恶劣的sequence来测试。
: 外围机是真正的机子，本来就需要message queue设计，这个我说过多次了，机制和
hot
: standby recovery一样。其实，设计中，任何外围机都能当hot standby使用的。
: 这种load，多机间multicast sync状态基本能够达到latency微秒级别。
: 退票反正也不多。是一个worst case O(SEATS)的过程。实际性能最差应该在单核每秒
: 20万-30万票。平均应该远超。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 14:47:10 2015, 美东)
上kernel bypass的10G网卡。我的一个系统，如果进来的market data tick恰好
trigger一个order，用corvil分光测wire-to-wire的速度（half round trip），
median在10us以内，最大的outlier也在20us以内。
实测ping-pong，median 5us左右吧。
我们这种load，latency控制在20us以内没问题。
注意，我现在的实现，针对1G网卡的throughput做了些优化。比如尽量pool输出到一个
MTU以上(1400 bytes)。如果用10G网卡，可以用不同的优化方案。
【 在 nanxiang7 (zz) 的大作中提到: 】
: 懂了，多谢！
: 多机间multicast sync状态真能达到latency微秒级别吗？throughput是没问题的。但
: 是，就单个ticket的latency来说，上下两边的protocal stack就要花不少时间吧，再
: 加上处理message queue的延迟(到queue里也不一定能马上处理），能压缩到微秒级
: 吗？我没实际测过，不知道。能否说说在实际HFT系统里的message，除去网络的
: 延迟，在机子里传递过程需要多少时间？
: hot
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 18:28:06 2015, 美东)
很有用的数据，谢谢！希望这里多些这样实用的信息，比吵架有意义多了。:)
优化到这个数量级差不多是到头了。在这点时间里跑不了多少business logic。
发信人: yuestar (yuestar), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 19:56:46 2015, 美东)
这是上了solarflare以后的数据？
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 10:23:02 2015, 美东)
我用了很多年solarflare。这个pc12306还真没上solarflare。性能足够了。
【 在 yuestar (yuestar) 的大作中提到: 】
: 这是上了solarflare以后的数据？
发信人: yuestar (yuestar), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 10:45:32 2015, 美东)
谢谢回答，我是说你5-20微秒的测试是不是solarflare/openonload 之后的数据。
【 在 TeacherWei (TW) 的大作中提到: 】
: 我用了很多年solarflare。这个pc12306还真没上solarflare。性能足够了。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 10:46:41 2015, 美东)
是。Solarflare卖这么贵就是因为latency低。
【 在 yuestar (yuestar) 的大作中提到: 】
: 谢谢回答，我是说你5-20微秒的测试是不是solarflare/openonload 之后的数据。
发信人: yuestar (yuestar), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 10:49:50 2015, 美东)
从send（）到wire大概多少延时？谢谢。
【 在 TeacherWei (TW) 的大作中提到: 】
: 是。Solarflare卖这么贵就是因为latency低。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 10:54:23 2015, 美东)
3-5us吧。
【 在 yuestar (yuestar) 的大作中提到: 】
: 从send（）到wire大概多少延时？谢谢。
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 11:52:12 2015, 美东)
这3-5us是不是主要在加每层header,每加一层要把payload memcpy一下？
如果追究一下极限，在两个直接连接的机子上，用proprietary protocol，不用支持通
常的protocol，所以不用一层层加header，网卡直接DMA数据到cache里，不知道这样的
物理极限是多少。
【 在 TeacherWei (TW) 的大作中提到: 】
: 3-5us吧。
发信人: yuestar (yuestar), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 12:21:18 2015, 美东)
但前面说ping pong 是5微秒？
【 在 TeacherWei (TW) 的大作中提到: 】
: 3-5us吧。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 12:35:33 2015, 美东)
极限就是PCI-E Latency。Solarflare号称half round trip最低3.X us。根据我的经验
偶尔能够达到。当然我多少有点business logic在里面。
infiniband latency更低，但是没有轮子用它。
【 在 nanxiang7 (zz) 的大作中提到: 】
: 这3-5us是不是主要在加每层header,每加一层要把payload memcpy一下？
: 如果追究一下极限，在两个直接连接的机子上，用proprietary protocol，不用支持通
: 常的protocol，所以不用一层层加header，网卡直接DMA数据到cache里，不知道这样的
: 物理极限是多少。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 12:37:11 2015, 美东)
half round trip.
【 在 yuestar (yuestar) 的大作中提到: 】
: 但前面说ping pong 是5微秒？
发信人: madmonk (madmonk), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 22:47:25 2015, 美东)
:假设第一个请求是
:起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］从［
:0，9］变为［0，2］和［4，5］。
为啥不是 ［0，3］和［4，5］?
:它是一个二维数组，
: 两个indices分别是起始站和（站数 - 1)
这样有何妙处啊？
【 在 nanxiang7 (zz) 的大作中提到: 】
: 放假，终于有时间run GDB，才对老魏的程序有些理解了。仍然有些疑问。想向老魏和
: 大家请教。
: 先陈述一下基本的理解：
: TrainTicketMap 是关键的数据库，表征对应车次当前所有空座. 它是一个二维数组，
: 两个indices分别是起始站和（站数 - 1). 它的值是一个stack（由单向链实现）。
: stack上每一元素对应一个座位的站次间的空座范围，表示此座位从该起始站开始数该
: 站数范围内是空的。该元素的next指针指向stack上下一个对应不同座位的元素。
: 在初始状态，每个座位从起始站0开始10站都空，所以这个二维数组只在index［0，9］
: 有非空stack，里面压了对应所有座位的3000个元素，座位1在最上。假设第一个请求是
: 起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］从［
: ...................
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Thu Dec 31 19:48:57 2015, 美东)
我曾经测过PCIe latency. 用CPU back to back读写PCIe device 同一个32-bit
register, 每次需要500ns。你看到3-5us时你的packet有多少bytes？不知道是
不是同一个cacheline的数据都能在同一个500ns里完成，不然很难解释一个packet
（假设64 bytes）能在几个us内完成。
【 在 TeacherWei (TW) 的大作中提到: 】
: 极限就是PCI-E Latency。Solarflare号称half round trip最低3.X us。根据我的经验
: 偶尔能够达到。当然我多少有点business logic在里面。
: infiniband latency更低，但是没有轮子用它。
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Thu Dec 31 19:58:49 2015, 美东)
: 为啥不是 ［0，3］和［4，5］?
站数是3，站数－1是2， 所以是［0，2］
: 这样有何妙处啊？
就是个记录空座范围的方式，在stack 里O(1)找到空座。
【 在 madmonk (madmonk) 的大作中提到: 】
: :假设第一个请求是
: :起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］
从［
: :0，9］变为［0，2］和［4，5］。
: :它是一个二维数组，
: 这样有何妙处啊？
发信人: madmonk (madmonk), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Fri Jan 1 17:54:10 2016, 美东)
多谢回复，
用个例子来说吧，
假如只有一次车，从北京到广州，共4站，
s0(北京)， s1(天津)， s2(上海)， s3(广州)，s表示station
车上只有两个座位： seat1, seat2
初始状态：
arr[0,0] 表示s0 到 s1的空座位集合，空Stack
...
arr[0,1] 表示s0 到 s2的空座位集合，空Stack
...
arr[0,2] 表示s0 到 s3的空座位集合，a Stack { seat1 , seat2}，
...
没出票时，只有arr[0,2] 有非空值 { seat1 , seat2}，
我的理解对吗？
【 在 nanxiang7 (zz) 的大作中提到: 】
: 为啥不是 ［0，3］和［4，5］?
站数是3，站数－1是2， 所以是［0，2］
: 这样有何妙处啊？
就是个记录空座范围的方式，在stack 里O(1)找到空座。
【 在 madmonk (madmonk) 的大作中提到: 】
: :假设第一个请求是
: :起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］
从［
: :0，9］变为［0，2］和［4，5］。
: :它是一个二维数组，
: 这样有何妙处啊？
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Fri Jan 1 22:58:16 2016, 美东)
你的理解是对的。
code中的变量名ticket有点misleading。这其实是某座在站之间的空座范围。这个数组
＋stack存着所有范围。如果有一个空座，它必然在某个范围之内。所有范围的集合表
征所有空座。数组是这些范围的存储和索引方式。
【 在 madmonk (madmonk) 的大作中提到: 】
: 多谢回复，
: 用个例子来说吧，
: 假如只有一次车，从北京到广州，共4站，
: s0(北京)， s1(天津)， s2(上海)， s3(广州)，s表示station
: 车上只有两个座位： seat1, seat2
: 初始状态：
: arr[0,0] 表示s0 到 s1的空座位集合，空Stack
: ...
: arr[0,1] 表示s0 到 s2的空座位集合，空Stack
: ...
: ...................
标 题: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Sun Dec 27 04:54:29 2015, 美东)
放假，终于有时间run GDB，才对老魏的程序有些理解了。仍然有些疑问。想向老魏和
大家请教。
先陈述一下基本的理解：
TrainTicketMap 是关键的数据库，表征对应车次当前所有空座. 它是一个二维数组，
两个indices分别是起始站和（站数 - 1). 它的值是一个stack（由单向链实现）。
stack上每一元素对应一个座位的站次间的空座范围，表示此座位从该起始站开始数该
站数范围内是空的。该元素的next指针指向stack上下一个对应不同座位的元素。
在初始状态，每个座位从起始站0开始10站都空，所以这个二维数组只在index［0，9］
有非空stack，里面压了对应所有座位的3000个元素，座位1在最上。假设第一个请求是
起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］从［
0，9］变为［0，2］和［4，5］。所以，对这个二维数组的操作（reserve函数里）是
：座位1在index［0，9］stack上的元素被free回TicketPool，从TicketPool重新
allocate两个元素给座位1，分别压进在index［0，2］和［4，5］的stacks。
整个操作分两步：allocate(); reserve().
allocate() 在TrainTicketMap找覆盖所请求站次的空座范围。搜索范围是顺着预先设
定的SearchOffsets，从小到大。所用时间较大而且不定，只读而不修改在
TrainTicketMap。是非transaction部分。
reserve() 是transaction部分，修改TrainTicketMap，用时很少并且固定。
请问，上述理解对吗？
我有几个问题：
1. 对站数能scale吗？如果站数从10变成100，TrainTicketMap与站数^2成正比，搜索
范围就增大100倍。allocate（）时间就增大100倍。当然可以用一个dedicated core
做reserve，把allocate分散到其它cores上。但如何同步就需要一些比较细碎的设计，
不如现在这样简洁了。另外，估计现有的core数很难消化得了100倍的计算量。所以，
对100站是不是就很难达到1M/s的指标了？
2. 如果朝实际方向再进一步，支持一个请求内多个座位连座，该怎么做？这应该是非
常贴近真实需要的。一家人一起走，座位应该是一起买，坐在一起的吧？如果顺着同样
的算法，TrainTicketMap是不是就该扩展成四维，多出的两维是起始座和座位数。那么
，搜索范围就扩大3000^2倍。这个算法是不是就不现实了？
3. 这个算法是源于成熟的理论，还是老魏或老姜的原创？无论如何，针对赌约的指标
要求，解决得非常精巧漂亮，令人佩服。这个问题，在逻辑上相当于在一个二维空间（
两轴分别是座位和站）不空的点上画叉叉，然后找可以容下长（连续座位数）宽（站数
）align在起始站的长方形的空域。这是不是另外还有更generic更好scale的理论和算
法？
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 10:53:35 2015, 美东)
不敢当，我们可以讨论一下。
首先，这个算法是老姜原创。2年多以前他就贴出来过。很不幸立刻淹没在一大堆口水
帖中。这也证明了这个版根本不是严肃讨论技术的地方。我只不过在实现过程中做了一
些优化而已。这个事实我已经反复生命过，不敢掠人之美。
1。站数scalability肯定不好，算法本身很简单。站数从10变成100，allocate（）时
间就增大100倍。这个是肯定的。但是我们讨论的是火车票，不是汽车票。100站现实中
不可能。20站有没有可能我不知道。20站allocate()就要慢四倍。但是可以接受。
2。多个座位连坐的问题。这个倒是不用3000^2倍。其实如果把TrainTicketMap稍加改
变，座位不是stack而是bitmap的话，就会容易很多。搜索连坐估计可以做到O(m^2 ×
log(n))，m是站数，n是座位数；实际代价可以很小。
其实我现在的算法实现也很仓促。比如现在的TrainTicketMap是一个矩形，实际上只用
了一半，就是沿对角线的三角形而已。主要是我看指标远远超过了，就将就了。
事实上，这个算法很适合scale到外围机上去。这也是我故意分两步allocate和reserve
的原因。外围机通过allocate算法可以filter大量的无效请求。而且这个算法能够线性
分布到多核上面去。
至于复杂业务逻辑，可以选择在外围机或者核心机实现，或者both。
其实我认为，相对于算法，大家更应该思考架构的问题。不论业务逻辑复杂与否，这种
耦合问题究竟应该采用何种架构？当然考虑问题要全面，实现，维护，运营成本都要考
虑。简单逻辑你说不考虑公平和运营成本，把3000数据库当分布式计数器用。那么难道
稍微复杂的业务逻辑数据库就能够更优化？给我写一个query看看？
发信人: walkrandom (walkrandom), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 13:02:23 2015, 美东)
个人觉得，魏老师的这个解决方案是一个高频交易的classic demo codebase。要进东
部银行的可以好好看看。
CPU比memory快10倍，memory比SSD快10倍，SSD比hard disk快10倍。hard disk比网线
快10倍。
魏老师告诉我们，高频交易最重要的是全内存运行，规避磁盘的IO限制。实现毫秒级的
transaction，一定要单机高并发。这是为什么东部银行喜欢折磨C＋＋的原因。
像12306这样的电商，瓶颈在磁盘和网线。DB建在磁盘上面，所以一定要选性能最好的
DB。 网线的堵塞没办法，只有靠买CDN来解决。电商大部分的钱都花在这方面了。
魏老师的性能再好，估计也不能改变磁盘和网线的物理限制。所以。。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 13:40:29 2015, 美东)
其实吧，倒不如说该用啥就用啥。指望啥都有现成的，还要你干啥？
你现在，离磁盘和网线的物理限制还差的很远。大概有数量级的差别吧。比如，10G，
40G网卡现在大把。一台server装两块，就是20-80G。能服务多少12306并发用户？
我们谈架构，throughput是最重要的性能指标。所以我当年第一贴就说了，别的都是浮
云，只要拿出throughput就好了。比如我系统能持续多大的throughput，20G,40G,80G
？这事儿，和单机多机真的无关。
【 在 walkrandom (walkrandom) 的大作中提到: 】
: 个人觉得，魏老师的这个解决方案是一个高频交易的classic demo codebase。要进东
: 部银行的可以好好看看。
: CPU比memory快10倍，memory比SSD快10倍，SSD比hard disk快10倍。hard disk比网线
: 快10倍。
: 魏老师告诉我们，高频交易最重要的是全内存运行，规避磁盘的IO限制。实现毫秒级的
: transaction，一定要单机高并发。这是为什么东部银行喜欢折磨C＋＋的原因。
: 像12306这样的电商，瓶颈在磁盘和网线。DB建在磁盘上面，所以一定要选性能最好的
: DB。 网线的堵塞没办法，只有靠买CDN来解决。电商大部分的钱都花在这方面了。
: 魏老师的性能再好，估计也不能改变磁盘和网线的物理限制。所以。。。
发信人: rc256 (ΜΟΛΩΝ ΛΑΒΕ), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 15:08:27 2015, 美东)
Use bitmask makes great sense. If we assume at most 32 stations, then a
single uint32_t (unsigned) can represent one seat availability. A single
train seatmap is just an array of unsigned. Assume 4096 seats per train,
then the entire one train seatmap is only 16KB.
The reserve function would look like this:
unsigned _seatmap[NSEATS];
int Train::reserve(int start, int length)
{
//return seat index reserved, -1 if not available
unsigned mask = ((1 << length)-1) << start;
for (unsigned *seat = _seatmap; seat<_seatmap+NSEATS; ++seat) {
if (!(*seat & mask)) {
*seat |= mask;
return seat - _seatmap;
}
}
return -1;
}
This is essentially a linear search, but should be really fast because
almost all seat is within cache and access is linear. Each match is just a
32bit bitwise AND operation.
发信人: mbp (Mac Book Pro), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 16:04:49 2015, 美东)
确实是hft里面经常看到的高性能单机版无io的东西。
【 在 walkrandom (walkrandom) 的大作中提到: 】
: 个人觉得，魏老师的这个解决方案是一个高频交易的classic demo codebase。要进东
: 部银行的可以好好看看。
: CPU比memory快10倍，memory比SSD快10倍，SSD比hard disk快10倍。hard disk比网线
: 快10倍。
: 魏老师告诉我们，高频交易最重要的是全内存运行，规避磁盘的IO限制。实现毫秒级的
: transaction，一定要单机高并发。这是为什么东部银行喜欢折磨C＋＋的原因。
: 像12306这样的电商，瓶颈在磁盘和网线。DB建在磁盘上面，所以一定要选性能最好的
: DB。 网线的堵塞没办法，只有靠买CDN来解决。电商大部分的钱都花在这方面了。
: 魏老师的性能再好，估计也不能改变磁盘和网线的物理限制。所以。。。
发信人: walkrandom (walkrandom), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 16:20:47 2015, 美东)
单数据中心，运营商能给的稳定带宽能有100MB/s就不错了。每个新用户第一次登陆可
能就下载100KB，想象一下1000个用户同时浏览。
所以理想很丰满，现实总是很残酷。
【 在 TeacherWei (TW) 的大作中提到: 】
: 其实吧，倒不如说该用啥就用啥。指望啥都有现成的，还要你干啥？
: 你现在，离磁盘和网线的物理限制还差的很远。大概有数量级的差别吧。比如，10G，
: 40G网卡现在大把。一台server装两块，就是20-80G。能服务多少12306并发用户？
: 我们谈架构，throughput是最重要的性能指标。所以我当年第一贴就说了，别的都是浮
: 云，只要拿出throughput就好了。比如我系统能持续多大的throughput，20G,40G,
80G
: ？这事儿，和单机多机真的无关。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 16:24:03 2015, 美东)
实际情况比这个复杂一些。连座加上最小碎片检索可能需要先Or最多55种可能性，然后
再搜索。
AVX + prefetch每cycle处理512 bit是有可能的。
【 在 rc256 (ΜΟΛΩΝ ΛΑΒΕ) 的大作中提到: 】
: Use bitmask makes great sense. If we assume at most 32 stations, then a
: single uint32_t (unsigned) can represent one seat availability. A single
: train seatmap is just an array of unsigned. Assume 4096 seats per train,
: then the entire one train seatmap is only 16KB.
: The reserve function would look like this:
: unsigned _seatmap[NSEATS];
: int Train::reserve(int start, int length)
: {
: //return seat index reserved, -1 if not available
: unsigned mask = ((1 << length)-1) << start;
: ...................
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Mon Dec 28 16:28:28 2015, 美东)
你就别闹了。照你的算法，Google和好虫他们Netflix用户都可以吃屎去了。
【 在 walkrandom (walkrandom) 的大作中提到: 】
: 单数据中心，运营商能给的稳定带宽能有100MB/s就不错了。每个新用户第一次登陆可
: 能就下载100KB，想象一下1000个用户同时浏览。
: 所以理想很丰满，现实总是很残酷。
: 80G
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 03:28:34 2015, 美东)
感谢老魏的详尽回答！老姜的算法和老魏的实现都做得很漂亮。很同意关于架构的论述。
对多票连座如何实现仍有不解。能否具体说说“把TrainTicketMap稍加改变，座位不是
stack而是bitmap”和“连座加上最小碎片检索可能需要先Or最多55种可能性”？
TrainTicketMap的index是［起始站，站数－1］。在［起始站，站数－1］的stack上的
非零值表示对某座这个站的范围（起始站－》起始站＋站数－1）是空的。改成bitmap
是不是bitmap里的1bits和stack上的元素有相同的含义？从同一个［起始站，站数－1
］点上找到的多个座位很可能是不相连的，而相连的座位可能在不同的［起始站，站数
－1］点上，怎样找？
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 03:56:55 2015, 美东)
这个做法没有考虑每一站的seatmap都是不同的而且中途不换座。另外，这个函数没有
处理跨word边界的情况，当然，这是小问题。
【 在 rc256 (ΜΟΛΩΝ ΛΑΒΕ) 的大作中提到: 】
: Use bitmask makes great sense. If we assume at most 32 stations, then a
: single uint32_t (unsigned) can represent one seat availability. A single
: train seatmap is just an array of unsigned. Assume 4096 seats per train,
: then the entire one train seatmap is only 16KB.
: The reserve function would look like this:
: unsigned _seatmap[NSEATS];
: int Train::reserve(int start, int length)
: {
: //return seat index reserved, -1 if not available
: unsigned mask = ((1 << length)-1) << start;
: ...................
发信人: rc256 (ΜΟΛΩΝ ΛΑΒΕ), 信区: Programming
标 题: RE: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 07:11:50 2015, 美东)
1. 中途换座 probably is not a requirement. If really in need, this probably
should be a ticket exchange or reissue.
2. Not sure if I understand "每一站的seatmap都是不同". My definition of one
seat bitmap word is vertical (availability throughout stations for one
particular seat) not horizontal (a snapshot of seat availability at
particular station) if you think entire train seat bitmap is a matrix, the
layout is column major indexes first. It is important because one bitwise
AND operation can check if this seat is a match for the trip riding mask.
【 在 nanxiang7 (zz) 的大作中提到: 】
这个做法没有考虑每一站的seatmap都是不同的而且中途不换座。另外，这个函数没有
处理跨word边界的情况，当然，这是小问题。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 10:18:44 2015, 美东)
还是代码说话吧：
增加了一个函数： allocate2
其目的是，找到所有符合条件的座位空间，放到一个数组里。数组大小是座位数（3000）
剩下的，愿意怎么找相邻座位都简单了。至于优化也很简单，就是找sum(碎片）最小的
相邻座位。
注意，allocate和reserve可以优化到不同的core上做pipeline。也就是机行代码的事
情。
void TrainTicketMap::allocate2(int start, int length, Ticket **seats) {
length--; // normalize to [0, 9]
for (Offsets::iterator it = offsets.begin(); it != offsets.end(); ++it) {
register int curStart = start + it->start;
register int curLength = length - it->start + it->length;
if (curStart >= 0 && curLength < SEGMENTS) {
//printf("Searching %d %d\n", curStart, curLength);
size_t index = curStart + curLength * SEGMENTS;
Ticket *cur = _map[index];
while (cur) {
seats[cur->_seat] = cur;
cur = cur->_next;
}
}
}
}
这个allocate2性能如何呢？
下面的代码基本上是worst case，每次都会收集满3000座位，而且促进最大cache miss。
static void benchmark() {
double t1 = getTime();
printf("start benchmark\n");
Ticket *seats[SEATS];
for (size_t i=0; i<10000000LL; i++) {
int train = rand() % TRAINS;
int start = rand() % SEGMENTS;
int length = rand() % (SEGMENTS - start);
if (length == 0) {
length = 1;
}
memset(seats, 0, sizeof(Ticket *) * SEATS);
trains[train]->allocate2(start, length, seats);
}
double t2 = getTime();
printf("Total time = %f\n", t2 - t1);
}
结果：1000万张票大约34秒。
所以如果支持无限连座，worst case大约30万票/s。Best case可以多核并行，仍然能
超过1000万。
注意，allocate2仍然能够无限scalable。所以查询的throughput基本是无限的。
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: RE: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 10:59:45 2015, 美东)
My bad. I misunderstood seatmap as one bit per seat. You actually mean one
bit per station.
So, it is just scanning the array of seats with complexity of O(seats).
TrainTicketsMap is not used. Right?
【 在 rc256 (ΜΟΛΩΝ ΛΑΒΕ) 的大作中提到: 】
: There is no word boundary problem because at most 32 stations therefore a
: 32bit unsigned represents one seat availability throughout all stations.
: As for adjacent seat issue, we can extend to 64(2 seats) or 128 bit(four
: seats in a row) If no adjacent seats available you can also try to find
: available seats with minimal distance after first scan.
: Like teacher Wei said if you optimize for sse/avx, it is possible to check
: 512bits in a cycle, or 16 seats per cycle. For 4096 seats, you only need
256
: cycles, approaching 85ns (at 3GHz) in worst case.
: The key here is to minimize memory footprint to have sequential cache
memory
: access most of the time. This should be able to achieve an order of
: ...................
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 11:02:18 2015, 美东)
谢谢老魏！确实用代码说话是最清楚的。：）
理解你的做法了。每次memset清空seat数组，找出所有的范围，排出所有seats，然后
找连座和优化碎片就容易了。我没往这个方向想是因为以为这样会慢(O(n) complexity
)，现在看你的benchmark确实performance也还不错。
多谢多谢！
【 在 TeacherWei (TW) 的大作中提到: 】
: 还是代码说话吧：
: 增加了一个函数： allocate2
: 其目的是，找到所有符合条件的座位空间，放到一个数组里。数组大小是座位数（
3000）
: 剩下的，愿意怎么找相邻座位都简单了。至于优化也很简单，就是找sum(碎片）最小的
: 相邻座位。
: 注意，allocate和reserve可以优化到不同的core上做pipeline。也就是机行代码的事
: 情。
: void TrainTicketMap::allocate2(int start, int length, Ticket **seats) {
: length--; // normalize to [0, 9]
: for (Offsets::iterator it = offsets.begin(); it != offsets.end(); ++it
) {
: ...................
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 11:28:04 2015, 美东)
其实还有很多可以讨论的。比如，复杂搜索例如连座之类，是否放在外围机比较好？这
样，核心机出票保证>1000万/s没有问题。
还有，我开始确实考虑每个座位block用bitmap，这样3000要375 bytes。当然OR操作要
用AVX加速。memory带宽需求显著增加，但是实际上不见得比我的allocate2慢。当然需
要实际测才知道。
至于3000数据库并行，我还真希望qxc写个query出来，别的不说，先把单张票优化一下
给我看看？
另外，这个worst case实际上是不会发生的。即使10%请求都是连座的，性能依然远超
1M/s。
至于12306用的gemfire内存数据库，gemfire还是靠Bear Stearns发家的。那时期我还
在Bear Stearns prop desk做Associate Director。具体情况我还是比较了解的。我不
认为gemfire在系统中能够起到任何关键作用。
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 13:08:57 2015, 美东)
reserve() 是应该在一个dedicated的core上以保证速度。复杂搜索可以offload到其它
cores上。你说的外围机是这些cores，还是真正的机子？如果是真正的机子，memory不
在一个系统内，还需要一些message queue的设计吧？
bitmap有可能更快。既然支持AVX，memory带宽应该够吧。
12306的瓶颈估计还是在IO，而不是这些内存操作。
我还有一个不清楚的地方，就是如何处理退票。如果付款出错，就需要把票返回到
TrainTicketsMap里，另外还需要合并原来被此票分裂的范围。这是不是也对称地分两
步，先搜索被此票分裂的范围，再进transaction写进map里？
【 在 TeacherWei (TW) 的大作中提到: 】
: 其实还有很多可以讨论的。比如，复杂搜索例如连座之类，是否放在外围机比较好？这
: 样，核心机出票保证>1000万/s没有问题。
: 还有，我开始确实考虑每个座位block用bitmap，这样3000要375 bytes。当然OR操作要
: 用AVX加速。memory带宽需求显著增加，但是实际上不见得比我的allocate2慢。当然需
: 要实际测才知道。
: 至于3000数据库并行，我还真希望qxc写个query出来，别的不说，先把单张票优化一下
: 给我看看？
: 另外，这个worst case实际上是不会发生的。即使10%请求都是连座的，性能依然远超
: 1M/s。
: 至于12306用的gemfire内存数据库，gemfire还是靠Bear Stearns发家的。那时期我还
: ...................
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 13:38:23 2015, 美东)
单机内，不相关搜索可以offload到多核，所以实际性能应该远远超过1M/s。除非像
goodbug和zhaoce那样专门选最恶劣的sequence来测试。
外围机是真正的机子，本来就需要message queue设计，这个我说过多次了，机制和hot
standby recovery一样。其实，设计中，任何外围机都能当hot standby使用的。
这种load，多机间multicast sync状态基本能够达到latency微秒级别。
退票反正也不多。是一个worst case O(SEATS)的过程。实际性能最差应该在单核每秒
20万-30万票。平均应该远超。
【 在 nanxiang7 (zz) 的大作中提到: 】
: reserve() 是应该在一个dedicated的core上以保证速度。复杂搜索可以offload到其它
: cores上。你说的外围机是这些cores，还是真正的机子？如果是真正的机子，memory不
: 在一个系统内，还需要一些message queue的设计吧？
: bitmap有可能更快。既然支持AVX，memory带宽应该够吧。
: 12306的瓶颈估计还是在IO，而不是这些内存操作。
: 我还有一个不清楚的地方，就是如何处理退票。如果付款出错，就需要把票返回到
: TrainTicketsMap里，另外还需要合并原来被此票分裂的范围。这是不是也对称地分两
: 步，先搜索被此票分裂的范围，再进transaction写进map里？
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 14:08:33 2015, 美东)
懂了，多谢！
多机间multicast sync状态真能达到latency微秒级别吗？throughput是没问题的。但
是，就单个ticket的latency来说，上下两边的protocal stack就要花不少时间吧，再
加上处理message queue的延迟(到queue里也不一定能马上处理），能压缩到微秒级
吗？我没实际测过，不知道。能否说说在实际HFT系统里的message，除去网络的
延迟，在机子里传递过程需要多少时间？
【 在 TeacherWei (TW) 的大作中提到: 】
: 单机内，不相关搜索可以offload到多核，所以实际性能应该远远超过1M/s。除非像
: goodbug和zhaoce那样专门选最恶劣的sequence来测试。
: 外围机是真正的机子，本来就需要message queue设计，这个我说过多次了，机制和
hot
: standby recovery一样。其实，设计中，任何外围机都能当hot standby使用的。
: 这种load，多机间multicast sync状态基本能够达到latency微秒级别。
: 退票反正也不多。是一个worst case O(SEATS)的过程。实际性能最差应该在单核每秒
: 20万-30万票。平均应该远超。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 14:47:10 2015, 美东)
上kernel bypass的10G网卡。我的一个系统，如果进来的market data tick恰好
trigger一个order，用corvil分光测wire-to-wire的速度（half round trip），
median在10us以内，最大的outlier也在20us以内。
实测ping-pong，median 5us左右吧。
我们这种load，latency控制在20us以内没问题。
注意，我现在的实现，针对1G网卡的throughput做了些优化。比如尽量pool输出到一个
MTU以上(1400 bytes)。如果用10G网卡，可以用不同的优化方案。
【 在 nanxiang7 (zz) 的大作中提到: 】
: 懂了，多谢！
: 多机间multicast sync状态真能达到latency微秒级别吗？throughput是没问题的。但
: 是，就单个ticket的latency来说，上下两边的protocal stack就要花不少时间吧，再
: 加上处理message queue的延迟(到queue里也不一定能马上处理），能压缩到微秒级
: 吗？我没实际测过，不知道。能否说说在实际HFT系统里的message，除去网络的
: 延迟，在机子里传递过程需要多少时间？
: hot
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 18:28:06 2015, 美东)
很有用的数据，谢谢！希望这里多些这样实用的信息，比吵架有意义多了。:)
优化到这个数量级差不多是到头了。在这点时间里跑不了多少business logic。
发信人: yuestar (yuestar), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Tue Dec 29 19:56:46 2015, 美东)
这是上了solarflare以后的数据？
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 10:23:02 2015, 美东)
我用了很多年solarflare。这个pc12306还真没上solarflare。性能足够了。
【 在 yuestar (yuestar) 的大作中提到: 】
: 这是上了solarflare以后的数据？
发信人: yuestar (yuestar), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 10:45:32 2015, 美东)
谢谢回答，我是说你5-20微秒的测试是不是solarflare/openonload 之后的数据。
【 在 TeacherWei (TW) 的大作中提到: 】
: 我用了很多年solarflare。这个pc12306还真没上solarflare。性能足够了。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 10:46:41 2015, 美东)
是。Solarflare卖这么贵就是因为latency低。
【 在 yuestar (yuestar) 的大作中提到: 】
: 谢谢回答，我是说你5-20微秒的测试是不是solarflare/openonload 之后的数据。
发信人: yuestar (yuestar), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 10:49:50 2015, 美东)
从send（）到wire大概多少延时？谢谢。
【 在 TeacherWei (TW) 的大作中提到: 】
: 是。Solarflare卖这么贵就是因为latency低。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 10:54:23 2015, 美东)
3-5us吧。
【 在 yuestar (yuestar) 的大作中提到: 】
: 从send（）到wire大概多少延时？谢谢。
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 11:52:12 2015, 美东)
这3-5us是不是主要在加每层header,每加一层要把payload memcpy一下？
如果追究一下极限，在两个直接连接的机子上，用proprietary protocol，不用支持通
常的protocol，所以不用一层层加header，网卡直接DMA数据到cache里，不知道这样的
物理极限是多少。
【 在 TeacherWei (TW) 的大作中提到: 】
: 3-5us吧。
发信人: yuestar (yuestar), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 12:21:18 2015, 美东)
但前面说ping pong 是5微秒？
【 在 TeacherWei (TW) 的大作中提到: 】
: 3-5us吧。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 12:35:33 2015, 美东)
极限就是PCI-E Latency。Solarflare号称half round trip最低3.X us。根据我的经验
偶尔能够达到。当然我多少有点business logic在里面。
infiniband latency更低，但是没有轮子用它。
【 在 nanxiang7 (zz) 的大作中提到: 】
: 这3-5us是不是主要在加每层header,每加一层要把payload memcpy一下？
: 如果追究一下极限，在两个直接连接的机子上，用proprietary protocol，不用支持通
: 常的protocol，所以不用一层层加header，网卡直接DMA数据到cache里，不知道这样的
: 物理极限是多少。
发信人: TeacherWei (TW), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 12:37:11 2015, 美东)
half round trip.
【 在 yuestar (yuestar) 的大作中提到: 】
: 但前面说ping pong 是5微秒？
发信人: madmonk (madmonk), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Wed Dec 30 22:47:25 2015, 美东)
:假设第一个请求是
:起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］从［
:0，9］变为［0，2］和［4，5］。
为啥不是 ［0，3］和［4，5］?
:它是一个二维数组，
: 两个indices分别是起始站和（站数 - 1)
这样有何妙处啊？
【 在 nanxiang7 (zz) 的大作中提到: 】
: 放假，终于有时间run GDB，才对老魏的程序有些理解了。仍然有些疑问。想向老魏和
: 大家请教。
: 先陈述一下基本的理解：
: TrainTicketMap 是关键的数据库，表征对应车次当前所有空座. 它是一个二维数组，
: 两个indices分别是起始站和（站数 - 1). 它的值是一个stack（由单向链实现）。
: stack上每一元素对应一个座位的站次间的空座范围，表示此座位从该起始站开始数该
: 站数范围内是空的。该元素的next指针指向stack上下一个对应不同座位的元素。
: 在初始状态，每个座位从起始站0开始10站都空，所以这个二维数组只在index［0，9］
: 有非空stack，里面压了对应所有座位的3000个元素，座位1在最上。假设第一个请求是
: 起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］从［
: ...................
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Thu Dec 31 19:48:57 2015, 美东)
我曾经测过PCIe latency. 用CPU back to back读写PCIe device 同一个32-bit
register, 每次需要500ns。你看到3-5us时你的packet有多少bytes？不知道是
不是同一个cacheline的数据都能在同一个500ns里完成，不然很难解释一个packet
（假设64 bytes）能在几个us内完成。
【 在 TeacherWei (TW) 的大作中提到: 】
: 极限就是PCI-E Latency。Solarflare号称half round trip最低3.X us。根据我的经验
: 偶尔能够达到。当然我多少有点business logic在里面。
: infiniband latency更低，但是没有轮子用它。
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Thu Dec 31 19:58:49 2015, 美东)
: 为啥不是 ［0，3］和［4，5］?
站数是3，站数－1是2， 所以是［0，2］
: 这样有何妙处啊？
就是个记录空座范围的方式，在stack 里O(1)找到空座。
【 在 madmonk (madmonk) 的大作中提到: 】
: :假设第一个请求是
: :起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］
从［
: :0，9］变为［0，2］和［4，5］。
: :它是一个二维数组，
: 这样有何妙处啊？
发信人: madmonk (madmonk), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Fri Jan 1 17:54:10 2016, 美东)
多谢回复，
用个例子来说吧，
假如只有一次车，从北京到广州，共4站，
s0(北京)， s1(天津)， s2(上海)， s3(广州)，s表示station
车上只有两个座位： seat1, seat2
初始状态：
arr[0,0] 表示s0 到 s1的空座位集合，空Stack
...
arr[0,1] 表示s0 到 s2的空座位集合，空Stack
...
arr[0,2] 表示s0 到 s3的空座位集合，a Stack { seat1 , seat2}，
...
没出票时，只有arr[0,2] 有非空值 { seat1 , seat2}，
我的理解对吗？
【 在 nanxiang7 (zz) 的大作中提到: 】
: 为啥不是 ［0，3］和［4，5］?
站数是3，站数－1是2， 所以是［0，2］
: 这样有何妙处啊？
就是个记录空座范围的方式，在stack 里O(1)找到空座。
【 在 madmonk (madmonk) 的大作中提到: 】
: :假设第一个请求是
: :起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］
从［
: :0，9］变为［0，2］和［4，5］。
: :它是一个二维数组，
: 这样有何妙处啊？
发信人: nanxiang7 (zz), 信区: Programming
标 题: Re: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Fri Jan 1 22:58:16 2016, 美东)
你的理解是对的。
code中的变量名ticket有点misleading。这其实是某座在站之间的空座范围。这个数组
＋stack存着所有范围。如果有一个空座，它必然在某个范围之内。所有范围的集合表
征所有空座。数组是这些范围的存储和索引方式。
【 在 madmonk (madmonk) 的大作中提到: 】
: 多谢回复，
: 用个例子来说吧，
: 假如只有一次车，从北京到广州，共4站，
: s0(北京)， s1(天津)， s2(上海)， s3(广州)，s表示station
: 车上只有两个座位： seat1, seat2
: 初始状态：
: arr[0,0] 表示s0 到 s1的空座位集合，空Stack
: ...
: arr[0,1] 表示s0 到 s2的空座位集合，空Stack
: ...
: ...................
Subscribe to:
Posts (Atom)