Các mẫu C++ cho ứng dụng độ trễ thấp, bao gồm giao dịch tần suất cao

 (arxiv.org)
1 điểm bởi GN⁺ 2024-07-09 | 1 bình luận | Chia sẻ qua WhatsApp
  • Trong các lĩnh vực nơi độ trễ chính là lợi thế cạnh tranh, như giao dịch tần suất cao (HFT), bài viết tổng hợp kiến thức tối ưu hóa C++ vốn ít được công khai, tập trung vào thử nghiệm và triển khai
  • Kết quả được chia thành ba phần: Low-Latency Programming Repository, tối ưu hóa chiến lược giao dịch cặp trung lập thị trường, và thư viện mẫu Disruptor bằng C++
  • Benchmark xem xét đồng thời tốc độ, mức sử dụng cache và ý nghĩa thống kê; Cache Warming và Constexpr cho thấy lợi ích lớn trong việc giảm độ trễ
  • Chiến lược giao dịch cặp đã tối ưu hóa cải thiện cả tốc độ thực thi lẫn khả năng sinh lời, còn triển khai Disruptor cho hiệu năng tốt hơn cách dùng queue truyền thống
  • Các nhiệm vụ tiếp theo gồm mở rộng repository, thử nghiệm trong môi trường giao dịch thực tế, tích hợp Disruptor với thuật toán giao dịch rồi benchmark toàn bộ hệ thống

Mục tiêu của tối ưu hóa độ trễ thấp trong HFT

  • Mục tiêu là tối ưu hóa mã nhạy cảm với độ trễ để tăng tốc độ thực thi
  • Trọng tâm đặt vào chiến lược lập trình và cấu trúc dữ liệu dùng trong giao dịch tần suất cao
  • Ngành tài chính, đặc biệt là các công ty buy-side xử lý thị trường công khai, không công bố nhiều kiến thức liên quan do tính bảo mật và lợi thế cạnh tranh
  • Để thu hẹp khoảng trống này, một Low-Latency Programming Repository tùy biến chứa nhiều kỹ thuật khác nhau được xây dựng và được kiểm chứng bằng benchmark thống kê

Ba kết quả chính

  • Low-Latency Programming Repository

    • Không chỉ là tập hợp lý thuyết, mà đóng vai trò như một hướng dẫn thực dụng có kèm benchmark thống kê
    • Tuyển chọn các kỹ thuật lập trình, design pattern và best practice nhằm giảm độ trễ trong hệ thống HFT

  • Tối ưu hóa chiến lược giao dịch cặp chênh lệch thống kê trung lập thị trường

    • Tích hợp các kỹ thuật giảm độ trễ và tối ưu hóa ở cấp CPU
    • Cho thấy cải thiện về tốc độ thực thi và khả năng sinh lời

  • Thư viện mẫu Disruptor bằng C++

    • Cho thấy hiệu năng cải thiện so với cách dùng queue truyền thống
    • Minh họa khả năng áp dụng cấu trúc dữ liệu này vào Order Management System (OMS) của hệ thống HFT

Vì sao thiếu kiến thức công khai

  • Kiến thức tối ưu hóa hệ thống HFT chủ yếu đến từ các chuyên gia trong ngành, nhưng do tính bảo mật và lợi thế cạnh tranh, các nghiên cứu mới nhất và chi tiết triển khai khó được công khai
  • Các lĩnh vực như cải thiện độ trễ, hiệu quả mã và tối ưu hóa cache đặc biệt có ít tài liệu công khai
  • Dù có các nghiên cứu HFT từ góc độ kinh tế·tài chính và nghiên cứu mô hình toán học cho giao dịch thuật toán, hiếm khi chúng đi sâu đến các kỹ thuật chi tiết về tối ưu hóa mã hay giảm độ trễ
  • Tài liệu liên quan đến C++ tương đối nhiều, nhưng số tài liệu kết nối trực tiếp với bối cảnh hệ thống HFT siêu độ trễ thấp còn hạn chế
  • Blog và bài đăng trực tuyến thường chỉ cung cấp dữ liệu độ trễ trung bình ở mức bề mặt, thiếu phân tích chi tiết về hành vi truy cập cache hay độ trễ thực thi lệnh

Đánh giá và cải thiện hiệu năng

  • Chỉ số đánh giá bao gồm tốc độ, mức sử dụng cache, ý nghĩa thống kê, v.v.
  • Trong các kỹ thuật của Low-Latency Programming Repository, Cache Warming và Constexpr cho thấy lợi ích lớn nhất trong việc giảm độ trễ
  • Triển khai mẫu Disruptor sử dụng ring buffer, số thứ tự sequence và các chiến lược chờ chuyên biệt để đạt hiệu năng tốt hơn cách dùng queue truyền thống về độ trễ và tốc độ
  • Chiến lược giao dịch cặp trung lập thị trường cải thiện tốc độ thực thi và khả năng sinh lời thông qua tối ưu hóa ở cấp CPU và các kỹ thuật giảm độ trễ

Repository công khai và công việc tiếp theo

  • Repository, chiến lược giao dịch và thư viện Disruptor nằm tại https://github.com/0burak/imperial hft
  • Công việc tiếp theo bao gồm mở rộng repository
  • Vẫn còn nhiệm vụ thử nghiệm thuật toán giao dịch đã tối ưu hóa trong môi trường giao dịch thực tế
  • Một hướng khác là tích hợp mẫu Disruptor với thuật toán giao dịch và thực hiện benchmark ở cấp toàn bộ hệ thống

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-07-09
Ý kiến trên Hacker News

  • Bài này có vẻ là phần nhập môn khá cơ bản về chủ đề này
    Theo kinh nghiệm của tôi khi từng dạy sinh viên đại học, ngay cả sinh viên cũng nhìn chung đã biết những nội dung như thế này. Trong các môn kiến trúc máy tính, họ học những yếu tố nền tảng của hiệu năng như dự đoán nhánh, tính nhất quán bộ nhớ đệm và bộ nhớ đệm lệnh
    Tôi khá ngạc nhiên vì bài không hề đề cập đến false sharing — một nguyên nhân suy giảm hiệu năng kinh điển — và có vẻ chủ yếu tập trung vào độ trễ của luồng đơn. Cũng bất ngờ khi thiếu các gợi ý tối ưu hóa “miễn phí” như fat LTO, PGO, [[likely]], [[unlikely]]
    Các vấn đề hiệu năng sâu hơn cần đi vào cả cách dùng các API I/O cụ thể, các primitive đồng bộ hóa, giao tiếp liên tiến trình, và những compiler intrinsic khó nhằn
    Điều thiếu nhất và cũng khó dạy nhất cho lập trình viên độ trễ thấp là một dạng hoang tưởng. Cần có nỗi sợ và sự tức giận thật sự trước các phép cấp phát, sao chép và những nguyên nhân làm giảm hiệu năng không cần thiết. Đó là cảm giác ám ảnh chạy benchmark bằng callgrind chỉ để tìm ra một lần cache đối tượng trượt ngay giữa hot loop khiến chương trình phải gọi xuống allocator
    Với cá nhân tôi, khoảnh khắc quan trọng là khi làm máy chủ độ trễ thấp và nhận ra rằng thay vì ghép các thao tác vector I/O, việc sao chép các đối tượng nhỏ vào một buffer liên tục rồi thực hiện một lệnh write duy nhất lại nhanh hơn về tổng thể. Không có phép sao chép nào là miễn phí, và fat pointer cũng không ngoại lệ

    • Có thể vậy, nhưng C++ độ trễ thấp là một lĩnh vực riêng biệt mà thông tin thì gần như khan hiếm như sa mạc
      Ngay cả những tài liệu tốt nhất hiện có cũng chỉ cỡ vài bài nói chuyện ở hội nghị C++, và vẫn còn rất đáng tiếc
      Nếu gạt sang một bên cám dỗ muốn thể hiện, thì tài liệu này là một đóng góp xuất sắc cho lĩnh vực này và có lẽ là tài liệu tham khảo có thẩm quyền đầu tiên. Những lời nói mơ hồ kiểu có thể ghép thông tin tương tự từ các bài giảng khác không phải là đóng góp, và cũng không giúp được ai
    • Tôi mừng vì giờ không còn làm việc đó nữa, nhưng sự hoang tưởng thật sự nằm ở kiểu bất tín Heisenberg. Không thể gạt bỏ cảm giác nghi ngờ rằng chương trình hoạt động khác đi khi đang bị đo so với khi không bị đo
    • Tôi khá tò mò không biết có tài liệu nào đáng để giới thiệu không
    • Nếu là tôi thì có lẽ sẽ tiếp cận như thế này. Tôi muốn nghe phản hồi từ những người gần với lĩnh vực này hơn
      Trước hết, để có tốc độ thô tối đa, dùng FPGA ở frontend để chia tải thành các luồng dữ liệu đơn giản theo từng tài sản. Tuy nhiên, vì ma sát từ việc phát triển lặp, nhân lực, chuỗi cung ứng... quá lớn, nên tránh cám dỗ cố triển khai thực tế ngay từ đây. Đầu vào sẽ là thứ như luồng FIX, còn đầu ra sẽ được tách thành các luồng sự kiện nhị phân theo từng tài sản dọc theo bus độ trễ thấp, rồi đi vào các phân đoạn theo tài sản của một cụm mở rộng dùng các MCU giá rẻ
      Thứ hai, trên nền tảng thực thi dựa trên MCU theo từng tài sản, loại bỏ các giả định của hệ điều hành đa dụng để cho phép chuyển đổi nhanh hơn sang mã mức thấp mà con người có thể viết được trên phần cứng thật sự mua được. Thứ ba, lợi nhuận? Trong kiểu kiến trúc này, một bộ giám sát chạy trên hệ điều hành đa dụng sẽ cần theo dõi toàn bộ trạng thái và tái lập trình từng thành phần khi cần để dừng hoặc thay đổi chiến lược
      Điểm mấu chốt là độ trễ thực tế có thể giảm được đến đâu. Từ một ngưỡng nào đó, có lẽ sẽ hợp lý hơn nếu trả chi phí đưa phần cứng đến gần lõi hơn thay vì tiếp tục kỹ thuật hóa. Điều này có lẽ phụ thuộc rất lớn vào quy định, trung tâm dữ liệu và hạ tầng liên kết mà sàn giao dịch hoặc pool đó cung cấp
      Nhiều hoạt động đang sinh lời dường như không công khai họ kết nối với pool nào, và cũng có thể họ coi front-running là mô hình kinh doanh trong khi phớt lờ quy định hay điều khoản dịch vụ. Trong những trường hợp đó, độ trễ địa lý mạng tương đối giữa hai điểm thực thi còn quan trọng hơn độ trễ tuyệt đối đến một điểm duy nhất
    • Nếu đã làm PGO thì tôi nghĩ các thuộc tính gợi ý có khi còn phản tác dụng
      Thực tế, quan niệm thường thấy từ phía những người làm compiler là ngay cả khi không có PGO, các gợi ý kiểu này trong đa số trường hợp cũng phản tác dụng. Compiler hiện đại tin vào các pass phân tích nội bộ của chính nó hơn những gợi ý như vậy và thường bỏ qua chúng
      Nhân tiện, tôi chỉ từng thấy các gợi ý kiểu này trong mã thực tế ở đúng những chỗ mà compiler cũng dễ tự chèn vào. Ví dụ như kiểm tra null sau lời gọi malloc

  • Phần tôi muốn nhấn mạnh là chỗ này
    “Đầu ra của bài kiểm tra này là thống kê kiểm định (t-statistic) và p-value liên quan. t-statistic, còn gọi là điểm số, là kết quả của phép kiểm định nghiệm đơn vị trên phần dư. t-statistic càng âm thì càng cho thấy phần dư có khả năng là dừng. p-value cung cấp một thước đo xác suất mà giả thuyết không của bài kiểm tra — tức giả thuyết không có đồng liên kết — là đúng. Kết quả kiểm tra cho ra p-value khoảng 0,0149 và t-statistic là -3,7684.”
    Đoạn này có vẻ như do LLM viết
    Ví dụ cũng thật sự rất kỳ lạ. Nó xem tương quan giá đóng cửa mỗi ngày một lần trong suốt 5 năm, rồi viết mã tính spread với độ trễ 65 micro giây. Đây không phải thứ hợp lý để làm trong thực tế. Bạn cũng sẽ không tính thống kê spread trong inner loop, và 65 micro giây thì quá chậm để gọi là inner loop
    Có thể ý chính chỉ là luyện các kỹ thuật tối ưu hóa, nhưng với tư cách đối tượng để tối ưu thì nó khá thiếu tính đại diện

  • Đã tạo một bản triển khai sàn giao dịch chứng khoán dùng mẫu LMAX Disruptor bằng C++
    https://github.com/sneilan/stock-exchange
    Cũng đã làm sẵn phần triển khai cơ bản của LMAX Disruptor chỉ bằng vài file C++
    https://github.com/sneilan/lmax-disruptor-tutorial
    Tuy vậy, giờ đang xem xét viết lại nó bằng Rust. Đã đi tới mức tự triển khai giao thức WebSocket riêng, hệ thống xác thực, SSL, v.v., nhưng rồi nhận ra Rust dễ xử lý quản lý bộ nhớ và phụ thuộc hơn nhiều. Đặc biệt là với dự án phần mềm một người làm thì càng đúng như vậy

    • Không dễ để triển khai đúng kiểu cấu trúc dữ liệu như thế này bằng C++. Có vài vấn đề trong phần cài đặt queue
      Truy cập bộ nhớ có thể bị sắp xếp lại cả ở phía compiler lẫn CPU, nên để có được hàng rào như mô tả trong bài báo gốc về LMAX Disruptor thì cần dùng std::atomic cho vị trí producer và consumer
      Trong phương thức get, mã tăng vị trí consumer trước, tức là giải phóng slot cho producer, rồi mới trả về con trỏ tới phần tử bên trong queue. Vì vậy dữ liệu có thể bị ghi đè trong lúc người dùng đang truy cập
      Ngoài ra, vị trí producer và vị trí consumer rất có thể nằm trên cùng một cache line, gây ra false sharing
    • Thay vì viết kiểu này
      T *item = &this->shared_mem_region->entities[this->shared_mem_region->consumer_position];
      this->shared_mem_region->consumer_position++;
      this->shared_mem_region->consumer_position %= this->slots;
      có thể làm như sau
      uint64_t mask = slot_count - 1; // tất cả bit đều là 1 ở dạng nhị phân
      item = &slots[ pos & mask ];
      pos ++;
      Tức là có thể thay phép chia/modulo bằng bit AND để giảm bớt một ít chi phí tính toán. Tuy nhiên, kích thước ring buffer phải là lũy thừa của 2
      Tiến thêm một bước nữa, có thể dùng số thứ tự toàn dải như uint64_t. Việc wrap sẽ được xử lý tự động. Khi trừ hai số thứ tự, nó vẫn hoạt động đúng kể cả có wrap. Cũng không còn phải chừa trống một slot theo cách ngớ ngẩn chỉ để phân biệt buffer đầy hay rỗng
      Tất nhiên vẫn phải cẩn thận để cửa sổ các số thứ tự “đang sống” không bao giờ vượt quá kích thước cửa sổ của ring buffer
    • Tôi có xem lướt qua mã của sàn giao dịch chứng khoán
      Có thể cân nhắc chuyển quản lý bộ nhớ sang std::shared_ptr. Nó loại bỏ hoàn toàn nỗi lo đó mà không làm chậm tốc độ
      Với socket, có những thư viện tự do nguồn mở cho hiệu năng tốt hơn code tự viết và cũng giảm bớt các trường hợp ngoại lệ đau đầu. Ví dụ, cách duyệt bằng FD_ISSET chậm hơn epoll hay kqueue
      Quản lý phụ thuộc trong C++ rõ ràng là thô ráp hơn các ngôn ngữ khác. Thậm chí việc tìm ra phụ thuộc còn khó hơn việc quản lý chúng. Có những thư viện dùng được nằm rải rác khắp nơi, một số còn ẩn trong những góc bị lãng quên của Internet. Bản thân việc tìm ra chúng đã là một kỹ năng, và nếu làm tốt thì phần thưởng rất lớn
    • LMAX Disruptor là một cấu trúc dữ liệu rất tuyệt khi thread được ghim vào core và phần lớn hoặc toàn bộ không có tranh chấp. Nếu không dùng mẫu này thì độ trễ đuôi có thể xuất hiện những bệnh lý rất tệ. Nếu thread bị scheduler đẩy ra đúng lúc xấu thì tác động sẽ rất lớn
      Với hệ thống tôi đang nghĩ tới, có lẽ khó mà vượt qua được SPSC ring buffer, và nếu cần thì cũng có thể triển khai work stealing bằng lock kiểu cổ điển
    • Thông tin thú vị: LMAX ban đầu được thiết kế cho Java và viết bằng Java
      https://martinfowler.com/articles/lmax.html

  • https://github.com/CppCon/CppCon2017/blob/master/Presentatio... làm tôi nhớ tới tài liệu này

    • Slide rất xuất sắc
      Những slide về việc một server giả phát lại dữ liệu lệnh, server thứ hai tính thời gian thực thi, và server đang được kiểm thử cùng hardware switch đo thời gian gói tin thật sự “hardcore” đến mức thấy đã mắt
      Tôi không muốn làm trong ngành tài chính, nhưng việc xử lý các hệ thống hiệu năng tới ngưỡng mà người ta có thể biện minh kinh tế cho việc mua phần cứng nguyên cả rack chỉ để benchmark nghe rất thú vị

  • Tôi đã làm một thư viện logging C++ có khá nhiều điểm giống LMAX Disruptor, và có vẻ cũng được dùng ở mức nào đó trong cộng đồng HFT
    Mục tiêu ban đầu là cho phép ghi lại log cực kỳ chi tiết trong môi trường production để debug sau sự cố mà không bị giảm hiệu năng. Trước đây có những đồng nghiệp phản đối việc đưa thông tin quan trọng cho xử lý sự cố vào log vì sợ ảnh hưởng hiệu năng, nhưng với thư viện này thì cuộc tranh luận đó chấm dứt
    [1] https://github.com/mattiasflodin/reckless

  • Một ưu điểm khác của dispatch tại thời điểm biên dịch là khi trình biên dịch có thể xác định tĩnh hàm nào sẽ được gọi, nó có thể inline trực tiếp mã của hàm được gọi vào vị trí gọi
    Khi đó có thể loại bỏ toàn bộ overhead của việc gọi hàm, đồng thời mở ra thêm các tối ưu hóa như loại bỏ mã chết và lan truyền hằng số

    • Theo tôi biết thì hiếm khi nguyên nhân tăng tốc thực sự là do overhead gọi hàm. Như đã nói ở phần cuối, điểm mấu chốt là liệu các tối ưu hóa của trình biên dịch có thể nhìn xuyên qua các nhánh động hay không
      Một JIT tốt hỗ trợ inlining đa hình. Kinh nghiệm của tôi với C++ đã khá cũ, nhưng giải pháp cho vấn đề này từng là PGO. Chỉ là nó không được dùng rộng rãi. Thay vào đó, trong mã nhạy cảm về hiệu năng, người ta có xu hướng tránh chính bản thân dynamic dispatch
      Bài học tổng quát hơn là, trong bất kỳ ngôn ngữ nào, ở những đoạn mã nóng hãy tránh các nhánh động không cần thiết trừ khi bạn thực sự tin tưởng rằng trình biên dịch hoặc JIT có thể nhìn thấu chúng
    • Hiệu năng thực tế không chỉ phụ thuộc vào tối ưu hóa của trình biên dịch mà còn vào hành vi runtime của máy. Về chủ đề này, bài nói chuyện này rất thú vị
      https://youtu.be/i5MAXAxp_Tw
    • Ngược lại, nếu instruction cache mới là giới hạn thì về mặt độ trễ đây có thể là một sự đánh đổi ròng bất lợi. Tất nhiên điều này còn phụ thuộc vào pattern truy cập v.v.

  • Có lý do chính đáng nào để giao dịch tần suất cao tồn tại không? Mọi người thường chỉ trích Bitcoin vì lãng phí năng lượng, nhưng cái này cũng có vẻ là tổn thất ròng rõ ràng cho xã hội, vậy mà dường như lại được bỏ qua

    • Chênh lệch giá mua/bán hiện đã hẹp hơn rất nhiều so với trước đây. Nếu nhìn vào tổng lợi nhuận của toàn ngành HFT thì nó không lớn đến vậy, ở mức vài tỷ USD, trong khi giá trị giao dịch là hàng nghìn tỷ USD
      Khó có thể nói ngành này cực kỳ có ích cho xã hội, nhưng việc thu hẹp spread đúng là làm giảm lượng tiền chảy vào tay trung gian
    • Chắc là vì nó không bị cấm một cách rõ ràng
      HFT là một lĩnh vực khá tập trung nhưng quy mô tự thân lại tương đối nhỏ. Xét về lãng phí năng lượng thì nó nhỏ hơn Bitcoin vài bậc độ lớn
      Tác động tích cực duy nhất của HFT là thanh khoản và spread hẹp hơn, nhưng điều đó cũng còn tùy người ta định nghĩa HFT thế nào. Ví dụ, Robinhood và giao dịch miễn phí có lẽ đã không tồn tại nếu không có điều này
      Họ đang lấy phần vốn trước đây thuộc về các broker và ngân hàng. HFT không phải là ngành đi “móc túi” nhà đầu tư nhỏ lẻ
      Theo quan điểm của tôi, tác động tiêu cực của nó lên xã hội là rất ít hoặc không có. Nếu bạn là người đầu tư dài hạn vào thị trường chứng khoán thì hầu như không có lý do gì để bận tâm đến HFT
    • Warren Buffett từng đề xuất rằng thị trường chứng khoán nên mở cửa thưa hơn, chẳng hạn mỗi quý một lần. Như vậy có thể khuyến khích đầu tư dài hạn thay vì đầu cơ
      Dù sao thì cũng không có sự kiện tự nhiên nào đòi hỏi giao dịch tần suất cao. Giá trị nền tảng hiếm khi thay đổi cực nhanh, và ngay cả khi có thì đó thường gần với một sự chuyển đổi đã được xác lập hơn là biến động
    • Giao dịch không phải Bitcoin chỉ là ghi vài mục vào nhiều cơ sở dữ liệu. Còn đào Bitcoin là một công việc tính toán số học nặng
      HFT giải quyết các sai lệch, ví dụ như khi ba cặp tiền tệ bị lệch nhau hoặc có định giá sai “rõ ràng”, nhờ đó làm cho thị trường tài chính chính xác hơn một chút
    • Tôi tò mò không biết bạn đã tìm hiểu đến đâu và đã từng mua bán cổ phiếu chưa
      Khi bạn cố giao dịch một thứ gì đó, luôn có ai đó ở phía đối diện. Thông thường rất có thể tôi sẽ giao dịch với một bên tham gia HFT ở đúng mức giá tôi muốn. Nếu tôi nhận được mức giá tốt hơn thì đó là số tiền tôi giữ lại được
      Tôi cũng khó đồng ý với ý rằng nó “bị bỏ qua”. HFT cũng bị chỉ trích khá thường xuyên ở đây

  • Nếu là lập trình viên chuyên nghiệp thì đáng để xem toàn bộ
    https://github.com/CppCon/CppCon2017/tree/master/Presentatio...
    Và cả thư mục cấp trên của nó nữa

  • Tôi có một câu hỏi. Vì sao trong lĩnh vực này người ta lại dùng hoặc từng dùng C++ cho logic thay vì C? C++ có lợi thế gì hơn C trong mảng này? Tôi thành thạo C/assembly nhưng hoàn toàn không biết thực tiễn HFT, nên mong được giải thích đơn giản

    • C++ giàu sức biểu đạt hơn C và cho phép nhiều dạng trừu tượng hóa hơn hẳn. Trong thời gian dài, C++ là ngôn ngữ chủ đạo duy nhất vừa mang lại hiệu năng cấp độ C vừa có các cơ chế trừu tượng phong phú, nên nó trở nên phổ biến ở các lĩnh vực cần mô hình hóa miền phức tạp như HFT, phát triển game và đồ họa
      Tất nhiên vẫn có thể tranh luận liệu mức độ biểu đạt này có đáng để đánh đổi lấy sự phức tạp khổng lồ của ngôn ngữ hay không, nhưng trên thực tế mọi người đã chọn C++ theo kinh nghiệm thực tiễn

  • Cấu trúc và giọng điệu của bài này vẫn có mùi LLM khá rõ