返回列表 發帖

以C++為核心語言的高頻交易系統是如何做到低延遲的?

以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]:http://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf[sehe, 2014]:Shared-memory IPC synchronization (lock-free)[tsunanet, 2010]:http://blog.tsunanet.net/2010/11 ... o-make-context.html

高頻 交易
量化交易的核心
十五年期貨從業,十年量化研究,零傭金開戶,交易所保證金,享高比率返傭!期貨量化無門檻返傭,上萬歐美量化策略,100G量化文檔,最新歐美期貨雜志,無論研究或實盤,均可免費獲得!詳情聯系論壇管理員。

最大的延時來自賬戶席位和網絡延時,一席的賬戶成交優先級高于二席,二席又高于散戶。怎樣做倒一席呢?只要賬戶上有足夠多的錢就可以。網絡延時是最大的,因此在物理位置上離交易所核心機房越近越好,能直接放進去當然最好,如果不能,也要放到ping交易前置機在1ms以內的地方。證券公司會有資源,這要求動用你的一切力量爭取到最滿意的位置。早年間,這是場內交易和場外交易的區別。接下來就是算法的效率了,這個可以抽象出來跟語言沒關系,大多跟數學/統計模型有關系,然后是算法的實現,c/c++/fortran/匯編的效率確實很好,而且優化的空間很大,但是如果很復雜的算法matlab可能會優化得比自己寫得好,那就用matlab實現。這還沒完,操作系統也可以調優,交易接口也可以不用交易所或者證券公司給的,自己分析通信協議重新實現;如果模型很復雜,計算量超大,那么就用并行計算架構,MPI, CUDA什么的用上。如果還要求絕對的速度,就用硬件實現算法, 這時候就輪到DSP芯片, FPGA什么的上陣,最后做一個專用的黑盒子。總之呢,就是所有能提高效率的地方,都是可以想辦法做的。但是,其實你要考慮的首先是,你的速度要求有多高,或者問你的交易策略是否真的需要那么高的速度嗎?其次是投入產出比,你的算法是否真的能夠掙足夠的錢來支持你做各層面的優化。以上很多雖然只有一句話,但是做起來東西很多,好多我現在也只知道概念,還不會做,提供個思路供參考。

最大的延時來自賬戶席位和網絡延時,一席的賬戶成交優先級高于二席,二席又高于散戶。怎樣做倒一席呢?只要賬戶上有足夠多的錢就可以。網絡延時是最大的,因此在物理位置上離交易所核心機房越近越好,能直接放進去當然最好,如果不能,也要放到ping交易前置機在1ms以內的地方。證券公司會有資源,這要求動用你的一切力量爭取到最滿意的位置。早年間,這是場內交易和場外交易的區別。接下來就是算法的效率了,這個可以抽象出來跟語言沒關系,大多跟數學/統計模型有關系,然后是算法的實現,c/c++/fortran/匯編的效率確實很好,而且優化的空間很大,但是如果很復雜的算法matlab可能會優化得比自己寫得好,那就用matlab實現。這還沒完,操作系統也可以調優,交易接口也可以不用交易所或者證券公司給的,自己分析通信協議重新實現;如果模型很復雜,計算量超大,那么就用并行計算架構,MPI, CUDA什么的用上。如果還要求絕對的速度,就用硬件實現算法, 這時候就輪到DSP芯片, FPGA什么的上陣,最后做一個專用的黑盒子。總之呢,就是所有能提高效率的地方,都是可以想辦法做的。但是,其實你要考慮的首先是,你的速度要求有多高,或者問你的交易策略是否真的需要那么高的速度嗎?其次是投入產出比,你的算法是否真的能夠掙足夠的錢來支持你做各層面的優化。以上很多雖然只有一句話,但是做起來東西很多,好多我現在也只知道概念,還不會做,提供個思路供參考。
作者:Sean Go

來源:知乎
十五年期貨從業,十年量化研究,零傭金開戶,交易所保證金,享高比率返傭!期貨量化無門檻返傭,上萬歐美量化策略,100G量化文檔,最新歐美期貨雜志,無論研究或實盤,均可免費獲得!詳情聯系論壇管理員。

TOP

問題中限定語言是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
十五年期貨從業,十年量化研究,零傭金開戶,交易所保證金,享高比率返傭!期貨量化無門檻返傭,上萬歐美量化策略,100G量化文檔,最新歐美期貨雜志,無論研究或實盤,均可免費獲得!詳情聯系論壇管理員。

TOP

只搞過 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資源使用,減少對延遲的影響。千萬不要為了加快壓縮速度,采用多線程并發的辦法,這就喧賓奪主了。
作者:陳碩
十五年期貨從業,十年量化研究,零傭金開戶,交易所保證金,享高比率返傭!期貨量化無門檻返傭,上萬歐美量化策略,100G量化文檔,最新歐美期貨雜志,無論研究或實盤,均可免費獲得!詳情聯系論壇管理員。

TOP

返回列表
意甲联赛ac米兰国米