以C++为核心语言的高频交易系统是如何做到低延迟的？
C++开发高频交易测试是非常必要的选择，我们的程序的响应时间是10us（从收到行情到发出报单的响应时间），但是ping期货公司的交易前置机需要大约30us【这个数值会变化，见注释4】，所以网络延时占据了大量时间。我所有的性能测试都是在一台DELL r630机器上运行的，这台机器有2个NUMA结点，CPU型号是E5 2643 v4（3.4GHz 6核）。所有的测试都是用rdtsc指令来测量时间，Intel官网上有一篇pdf文档[Gabriele Paoloni, 2010]，讲述了如何精准地测量时间（要用cpuid来同步）。我自己做的性能测试的结果会写成“100(sd20)ns”的形式，代表平均值是100ns，标准差是20ns。我在算均值和标准差的时候会去掉最大的0.1%的数据再算，因为那些数据似乎并不是程序延时，而是cpu被调度执行别的任务了【原因见注释3】。有些性能测试在网上有现成的测试结果，我就没自己测，直接拿来用了，但是以后我会重新在我的机器上测一遍。一些我们比较注意的点：1.限制动态分配内存相关的知识背景：glibc默认的malloc背后有复杂的算法，当堆空间不足时会调用sbrk()，当分配内存很大时会调用mmap()，这些都是系统调用，似乎会比较慢，而且新分配的内存被first touch时也要过很久才能准备好。可取的做法：尽量使用vector或者array（初始化时分配足够的空间，之后每次使用都从里面取出来用）。尽量使用内存池。如果需要二叉树或者哈希表，尽量使用侵入式容器（boost::intrusive）。性能测试：我测试的分配尺寸有64和8128两种。首先，我测试了glibc malloc的性能，分配64字节耗时98(sd247)ns，分配8128字节需要耗时1485(sd471)ns。其次，我写了一个多进程安全的内存池，分配64字节需要29(sd15)ns，分配8128字节需要22(sd12)ns。【内存池的细节见注释6】。最后，我单独测试了sbrk()和first touch的性能，但是数据不记得了。2.使用轮询，尽量避免阻塞相关的知识背景：上下文切换是非常耗时的，其中固定的消耗包括（cpu流水线被冲掉、各种寄存器需要被保存和恢复、内核中的调度算法要被执行），此外，缓存很有可能出现大量miss，这属于不固定的时间消耗。可取的做法：使用带有内核bypass功能的网卡。每个进程或者线程都独占一个cpu核【isolcpus和irqbalance的细节见注释3】，并且不停地轮询，用以保证快速响应。尽量避免任何可能导致阻塞的事件（如mutex），某些注定很慢的活动（比如把log写到磁盘上）应该被独立出来放到别的cpu上，不能影响主线程。性能测试：网上有一篇博客[tsunanet, 2010]测试了mode switch、thread switch、process switch的耗时，但是这篇文章太早了，以后我要用我的新cpu重新测一下。这篇博客里面，系统调用只需要<100ns，线程/进程切换需要>1us（不包括缓存miss的时间）。3.使用共享内存作为唯一的IPC机制相关的知识背景：共享内存只有在初始化的时候有一些系统调用，之后就可以像访问正常内存一样使用了。其他IPC机制（管道、消息队列、套接字）则是每次传输数据时都有系统调用，并且每次传输的数据都经历多次拷贝。因此共享内存是最快的IPC机制。可取的做法：使用共享内存作为唯一的IPC机制。当然，可能需要手动实现一些东西来保证共享的数据在多进程下是安全，我们是自己实现了无锁内存池、无锁队列和顺序锁【关于seqlock的疑点见注释1】。性能测试：我使用了boost中的Interprocess库和Lockfree库，在共享内存上建立了一个spsc队列，然后用这个队列来传送数据，代码参考了stackoverflow上的一个答案[sehe, 2014]。我传送的数据是一个8字节整数，延时是153(sd61)ns。至于其他IPC机制，我在[cambridge, 2016]看到了一些性能测试结果，通常是要几微秒到几十微秒不等。4.传递消息时使用无锁队列相关的知识背景：我只关注基于数组的无锁队列，其中：spsc队列是wait-free的，不论是入队出队都可以在确定的步数之内完成，而且实现时只需要基本的原子操作【为什么这很重要见注释7】；mpmc队列的实现方式则多种多样，但都会稍微慢一点，因为它们需要用一些比较重的原子操作（CAS或者FAA），而且有时它们需要等待一段不确定的时间直到另一个线程完成相应操作；另外，还有一种multi-observer的『广播队列』，多个读者可以收到同一条消息广播，这种队列也有sp和mp类型的，可以检查或者不检查overwrite；最后，还有一种队列允许存储不定长的消息。可取的做法：总的来说，应该避免使用mp类型的队列，举例：如果要用mpsc队列，可以使用多个spsc来达成目的，并不需要mp队列；同理，如果是消息广播，也可以使用多个sp队列来取代一个mp队列；如果广播时observer只想订阅一部分消息，那么可以用多个spsc+有计数功能的内存池【具体做法见注释2】；如果要求多个观察者看到多个生产者的消息，并且顺序一致，那只能用mp队列了。总结一下，mp类型的队列应该尽量避免，因为当多个生产者同时抢占队列的时候，延时会线性增长。性能测试：我写了一个mp类型的广播队列，传输的数据是8字节int，当只有一个生产者时，传输的延时是105(sd26)ns。增加观察者会使延时略微变大，增加生产者会使延时急剧变大（我用rdtsc指令控制不同生产者同时发送消息）。对于这个队列来说，它的延时只略高于跨核可视延时【测试结果见注释8】，所以应该算是不错了。5.考虑缓存对速度的影响相关的背景知识：现在的机器内存是十分充足的，但是缓存还是很小，因此所有节省内存的技巧都还有用武之地。可取的做法：尽量让可能被同时使用的数据挨在一起；减少指针链接（比如用array取代vector，因为链接指向的地方可能不在缓存里）；尽量节省内存（比如用unique_ptr<Data[]>取代vector<Data>，比如成员变量按照从大到小排序，比如能用int8的地方就不用int16）；指定cpu affinity时考虑LLC缓存（同核的两个超线程是共享L1，同cpu的两个核是共享L3，不同NUMA核是通过QPI总线）；会被多个核同时读写的数据按照缓存行对齐（避免false sharing）。【注释1】：有一篇惠普的论文[Hans-J.Boehm, 2012]大致叙述了顺序锁的实现方法，但是那里面有两点让我感到困惑。一是需要用到thread_fence，这在某些cpu上可能会影响性能(x86似乎没影响)；二是被保护的内容也必须是原子变量(可以是多个原子变量，所以被保护的内容可以很长)。但这是我见过的唯一一个符合C++标准的SeqLock的实现。【注释2】：如果有M个生产者要发消息给N个观察者，可以建M*N个spsc队列和M个内存池，观察者只能读内存池里的数据，只有对应的那一个生产者可以修改内存池。我感觉这样应该会更快，但我没测过。【注释3】：isolcpus可以隔离出一些cpu，避免其他线程被调度到这些cpu上执行。此外，设置irq affinity可以让一些cpu尽量避免响应中断，但在/proc/interrupts里面仍然有一些项目是避免不了的，而cpu处理中断时，用户程序会有一段时间（有时高达几十微秒）无法响应，我们没法解决这个问题。【注释4】：在不同的时间点，ping的结果会有很大差异。交易时间段内ping出来的结果是30us，其它时间段ping出来的结果可能是几百微秒。我不知道这是什么原因，可能是期货公司为了省电关掉了某些东西？【注释6】：我们要在共享内存上使用内存池，所以不得不自己写一个。我写的内存池只能分配固定尺寸的内存块，但是用户可以建立好几个内存池，用来分配不同的尺寸。实现的过程中有两个要点。一是用无锁链表来保存空闲的内存块；二是每个线程内部有一个缓冲区，所以真正取内存块的时候是没有CAS操作的。【注释7】：在Intel x86的cpu上，如果C++中的内存顺序只用了acquire和release，那么编译出来的汇编代码里面不会有任何内存栅栏指令；如果同时也没有RMW（读-改-写）指令的话，无锁的代码编译出来就会像是普通的代码一样了。事实上，spsc队列的延时几乎等于跨核可视延时。【注释8】：跨核可视延时：对于一个共享变量来说，如果有一个核上面的进程或者线程修改了这个变量，另一个核需要过一段时间才能看到这个修改，这段时间被称作跨核可视延时。我不确定在这段时间内，第二个核是会看到旧的数据还是这条指令会执行很久。在我的机器上，对于同一个cpu上的不同核心，这个值是96(sd14)ns。另外，对于同一个核心上的不同超线程，这个值应该会更小；对于同一台机器上的不同cpu，这个值应该会更大。[cambridge, 2016]：Computer Laboratory[Gabriele Paoloni, 2010]：Code Execution Times: IA-32/IA-64 Instruction Set Architecture[Hans-J.Boehm, 2012]：[url]http://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf[/url][sehe, 2014]：Shared-memory IPC synchronization (lock-free)[tsunanet, 2010]：[url]http://blog.tsunanet.net/2010/11/how-long-does-it-take-to-make-context.html[/url]高频 交易
量化交易的核心 最大的延时来自账户席位和网络延时，一席的账户成交优先级高于二席，二席又高于散户。怎样做倒一席呢？只要账户上有足够多的钱就可以。网络延时是最大的，因此在物理位置上离交易所核心机房越近越好，能直接放进去当然最好，如果不能，也要放到ping交易前置机在1ms以内的地方。证券公司会有资源，这要求动用你的一切力量争取到最满意的位置。早年间，这是场内交易和场外交易的区别。接下来就是算法的效率了，这个可以抽象出来跟语言没关系，大多跟数学/统计模型有关系，然后是算法的实现，c/c++/fortran/汇编的效率确实很好，而且优化的空间很大，但是如果很复杂的算法matlab可能会优化得比自己写得好，那就用matlab实现。这还没完，操作系统也可以调优，交易接口也可以不用交易所或者证券公司给的，自己分析通信协议重新实现；如果模型很复杂，计算量超大，那么就用并行计算架构，MPI, CUDA什么的用上。如果还要求绝对的速度，就用硬件实现算法， 这时候就轮到DSP芯片， FPGA什么的上阵，最后做一个专用的黑盒子。总之呢，就是所有能提高效率的地方，都是可以想办法做的。但是，其实你要考虑的首先是，你的速度要求有多高，或者问你的交易策略是否真的需要那么高的速度吗？其次是投入产出比，你的算法是否真的能够挣足够的钱来支持你做各层面的优化。以上很多虽然只有一句话，但是做起来东西很多，好多我现在也只知道概念，还不会做，提供个思路供参考。
最大的延时来自账户席位和网络延时，一席的账户成交优先级高于二席，二席又高于散户。怎样做倒一席呢？只要账户上有足够多的钱就可以。网络延时是最大的，因此在物理位置上离交易所核心机房越近越好，能直接放进去当然最好，如果不能，也要放到ping交易前置机在1ms以内的地方。证券公司会有资源，这要求动用你的一切力量争取到最满意的位置。早年间，这是场内交易和场外交易的区别。接下来就是算法的效率了，这个可以抽象出来跟语言没关系，大多跟数学/统计模型有关系，然后是算法的实现，c/c++/fortran/汇编的效率确实很好，而且优化的空间很大，但是如果很复杂的算法matlab可能会优化得比自己写得好，那就用matlab实现。这还没完，操作系统也可以调优，交易接口也可以不用交易所或者证券公司给的，自己分析通信协议重新实现；如果模型很复杂，计算量超大，那么就用并行计算架构，MPI, CUDA什么的用上。如果还要求绝对的速度，就用硬件实现算法， 这时候就轮到DSP芯片， FPGA什么的上阵，最后做一个专用的黑盒子。总之呢，就是所有能提高效率的地方，都是可以想办法做的。但是，其实你要考虑的首先是，你的速度要求有多高，或者问你的交易策略是否真的需要那么高的速度吗？其次是投入产出比，你的算法是否真的能够挣足够的钱来支持你做各层面的优化。以上很多虽然只有一句话，但是做起来东西很多，好多我现在也只知道概念，还不会做，提供个思路供参考。
作者：Sean Go
来源：知乎 问题中限定语言是C++，可讨论的范围就比较精简了。现有的答案都在谈系统架构层次上的东西，略显跑题。我对C++了解不多，但我尝试以一名C++程序员的视角，从基本思路出发做一个分析，抛砖引玉。首先我们要明确系统的需求。所谓交易系统，从一个应用程序的角度来说，有以下几个特点：一定是一个网络相关的应用，假如机器没联网，肯定什么交易也干不了。所以系统需要通过TCP/IP连接来收发数据。数据要分两种，一种从交易所发过来的市场数据，流量很大，另一种是系统向交易所发出的交易指令，相比前者流量很小，这两种数据需要在不同的TCP/IP连接里传输。因为是自动化交易系统，人工干预的部分肯定比较小，所以图形界面不是重点。而为了性能考虑，图形界面需要和后台分开部署在不同的机器上，通过网络交互，以免任何图形界面上的问题导致后台系统故障或者被抢占资源。这样又要在后台增加新的TCP/IP连接。高频交易系统对延迟异常敏感，目前（2014）市面上的主流系统（可以直接买到的大众系统）延迟至少在100微秒级别，顶尖的系统（HFT专有）可以做到10微秒以下。其他答案里提到C++随便写写延迟做到几百微秒，是肯定不行的，这样的性能对于高频交易来说会是一场灾难。系统只需要专注于处理自己收到的数据，不需要和其他机器合作，不需要担心流量过载。有了以上几点基本的认识，我们可以看看用C++做为开发语言有哪些需要注意的。首先前两点需求就决定了，这种系统一定是一个多线程程序。虽然对于图形界面来说，后台系统相当于一个服务端，但这部分的性能不是重点，用常用的模式就能解决（也许这里你可以介绍一下常用的C++ Client/Server库，或者内嵌Web Server之类，相信应该有丰富的选择，这里不展开讨论）。而重要的面向交易所那端，系统其实是一个客户端程序，只需要维护好固定数量的连接就可以了。为延迟考虑，一定要选择异步I/O（阻塞的同步I/O会消耗时间在上下文切换），这里有两点需要注意：是否可以在单线程内完成所有处理？考虑市场数据的流量远远高于发出的交易指令，在单线程内处理显然是不行的，否则可能收了一大堆数据还没开始处理，错过了发指令的最佳时机。有答案提到要压低平时的资源使用率，这是完全错误的设计思路。问题同样出在上下文切换上，一旦系统进入IDLE状态，再重新切换回处理模式是要付出时间代价的。正确的做法是在线程同步代码中保持对共享变量/内存区的疯狂轮询，一旦有消息就立刻处理，之后继续轮询，这样是最快的处理方式。（顺带一提现在的CPU一般会带有环保功能，使用率低了会导致CPU进入低功耗模式，同样对性能有严重影响。真正的低延迟系统一定是永远发烫的！）现在我们知道核心的模块是一个多线程的，处理多个TCP/IP连接的模块，接下来就可以针对C++进行讨论。因为需要对接受到的每个TCP或UDP包进行处理，首先要考虑的是如何把包从接收线程传递给处理线程。我们知道C++是面向对象的语言，一般情况下最直观的思路是创建一个对象，然后发给处理线程，这样从逻辑上看是非常清晰的。但在追求低延迟的系统里不能这样做，因为对象是分配在堆上的，而堆的内存结构对我们来说是完全不透明的，没办法控制一个对象会具体分到内存的什么位置上，这直接导致的问题是本来连续收到的网络包，在内存里的分布是分散的，当处理线程需要读取数据时就会发生大量的cache miss，产生不可控的延迟。所以对C++开发者来说，第一条需要谨记的应该是，不要随便使用堆（用关键字new）。核心的数据要保证分配在连续内存里。另一个问题在于，市场数据和交易指令都是结构化的，包含了股票名称，价格，时间等一系列信息。如果使用C++ class来对数据进行建模和封装，同样会产生不可知的内存结构。为了严格控制内存结构，应该使用struct来封装。一方面在对接收到的数据解析时可以直接定义名称，一方面在分配新对象（比如交易指令）时可以保证所有数据都分配在连续的内存区域。以上两点是关于延迟方面最重要的注意事项（如果真正做好这两点，大概剩下的唯一问题是给系统取个好名字吧：TwoHardThings）。除此之外，需要考虑的是业务逻辑的编写。高频交易系统里注定了业务逻辑不会太复杂，但重要的是要保证正确性和避免指针错误。正确性应该可以借助于C++的特性比如强类型，模板等来加强验证，这方面我不熟悉就不多说了。高频系统往往运行时要处理大量订单，所以一定要保证系统运行时不能崩溃，一旦coredump后果很严重。这个问题也许可以多做编译期静态分析来加强，或者需要在系统外增加安全机制，这里不展开讨论了。以下是几点引申思考：如何存储系统日志？如何对系统进行实时监控？如果系统coredump，事后如何分析找出问题所在？如何设计保证系统可用性，使得出现coredump之类的情况时可以及时切换到备用系统？这些问题相信在C++框架内都有合适的解决方案，我对此了解不多，所以只列在这里供大家讨论。注：从开发语言角度上说，C++只是一种选择，并不是唯一的解决方案。简单的认为低延迟就等同于用C++开发，是不正确的。其他语言同样有可能做出高性能的设计，需要根据语言特性具体分析。关于整体的软硬件架构，可以看我的另一个回答：高频交易软硬件是怎么架构的？关于C++在性能方面的一些最新发展，包括内存结构的一些分析，可以参看：Modern C++: What You Need to Know 只搞过 sell side，没搞过 buy side，只能算“实时交易”，算不上“高频交易”。工作以来一直在跟延迟做斗争，勉强可以说上几句。要控制和降低延迟，首先要能准确测量延迟，因此需要比较准的钟，每个机房配几个带GPS和/或原子钟primary standard的NTP服务器是少不了的。而且就算用了NTP，同一机房两台机器的时间也会有毫秒级的差异，计算延迟的时候，两台机器的时间戳不能直接相减，因为不在同一时钟域。解决办法是设法补偿这个时差。另外，不仅要测量平均延迟，更重要的是要测量并控制长尾延迟，即99百分位数或99.9百分位数的延迟，就算是sell side，系统偶尔慢一下被speculator利用了也是要亏钱的。普通的C++服务程序，内部延迟（从进程收到消息到进程发出消息）做到几百微秒（即亚毫秒级）是不需要特殊的努力的。没什么忌讳，该怎么写就怎么写，不犯低级错误就行。我很纳闷国内流传的写 C++ 服务程序时的那些“讲究”是怎么来的（而且还不是 latency critical 的服务程序）。如果瓶颈在CPU，那么最有效的优化方式是“强度消减”，即不在于怎么做得快，而在于怎么做得少。哪些可以不用做，哪些可以不提前做，哪些做一次就可以缓存起来用一阵子，这些都是值得考虑的。网络延迟分传输延迟和惯性延迟，通常局域网内以后者为主，广域网以前者为主。前者是传送1字节消息的基本延迟，大致跟距离成正比，千兆局域网单程是近百微秒，伦敦到纽约是几十毫秒。这个延迟受物理定律限制，优化办法是买更好的网络设备和租更短的线路（或者想办法把光速调大，据说 Jeff Dean 干过）。惯性延迟跟消息大小成正比，跟网络带宽成反比，千兆网TCP有效带宽按115MB/s估算，那么发送1150字节的消息从第1个字节离开本机网卡到第1150个字节离开本机网卡至少需要 10us，这是无法降低的，因此必要的话可以减小消息长度。举例来说，要发10k的消息，先花20us CPU时间，压缩到3k，接收端再花10us解压缩，一共“60us+传输延迟”，这比直接发送10k消息花“100us+传输延迟”要快一点点。（广域网是否也适用这个办法取决于带宽和延迟的大小，不难估算的。）延迟和吞吐量是矛盾的，通常吞吐量上去了延迟也会跟着飚上去，因此控制负载是控制延迟的重要手段。延迟跟吞吐量的关系通常是个U型曲线，吞吐量接近0的时候延迟反而比较高，因为系统比较“冷”；吞吐量上去一些，平均延迟会降到正常水平，这时系统是“温”的；吞吐量再上去一些，延迟缓慢上升，系统是“热”的；吞吐量过了某个临界点，延迟开始飙升，系统是“烫”的，还可能“冒烟”。因此要做的是把吞吐量控制在“温”和“热”的范围，不要“烫”，也不要太冷。系统启动之后要“预热”。延迟和资源使用率是矛盾的，做高吞吐的服务程序，恨不得把CPU和IO都跑满，资源都用完。而低延迟的服务程序的资源占用率通常低得可怜，让人认为闲着没干什么事，可以再“加码”，要抵住这种压力。就算系统到了前面说的“发烫”的程度，其资源使用率也远没有到 100%。实际上平时资源使用率低是为了准备应付突发请求，请求或消息一来就可以立刻得到处理，尽量少排队，“排队”就意味着等待，等待就意味着长延迟。消除等待是最直接有效的降低延迟的办法，靠的就是富裕的容量。有时候队列的长度也可以作为系统的性能指标，而不仅仅是CPU使用率和网络带宽使用率。另外，队列也可能是隐式的，比如操作系统和网络设备的网络输入输出 buffer 也算是队列。延迟和可靠传输也是矛盾的，TCP做到可靠传输的办法是超时重传，一旦发生重传，几百毫秒的延迟就搭进去了，因此保持网络随时畅通，避免拥塞也是控制延迟的必要手段。要注意不要让batch job抢serving job的带宽，比方说把服务器上的日志文件拷到备份存储，这件事不要在繁忙交易时段做。QoS也是办法；或者布两套网，每台机器两个网口，两个IP。最后，设法保证关键服务进程的资源充裕，避免侵占（主要是CPU和网络带宽）。比如把服务器的日志文件拷到别的机器会占用网络带宽，一个办法是慢速拷贝，写个程序，故意降低拷贝速度，每50毫秒拷贝50kB，这样用时间换带宽。还可以先压缩再拷贝，比如gzip压缩100MB的服务器日志文件需要1秒，在生产服务器上会短期占满1个core的CPU资源，可能造成延迟波动。可以考虑写个慢速压缩的程序，每100毫秒压缩100kB，花一分半钟压缩完100MB数据，分散了CPU资源使用，减少对延迟的影响。千万不要为了加快压缩速度，采用多线程并发的办法，这就喧宾夺主了。
作者：陈硕
页:
[1]