Tìm hiểu về Lmax Disruptor trong hệ thống trading hiệu năng cao

1. Từ CPU, Memory đến bài toán giao tiếp giữa các Thread.#

1.1. Tổng quan về cách CPU xử lý Thread#

Một thread khi chạy thực chất là đang được hệ điều hành (OS) lên lịch đưa vào một CPU core nào đó để thực thi. Và khi xử lý, CPU không phải mỗi lần đọc dữ liệu đều phải chạy xuống RAM, mà nó sẽ có một số tầng cache. Và CPU sẽ thường cố gắng tối ưu việc sử dụng tầng cache này vì tốc độ của nó cao hơn việc chọc xuống RAM rất nhiều. Luồng có thể nhìn kiểu:

CPU Core -> Cache L1 -> Cache L2 -> Shared Cache L3 -> RAM

Cache càng gần tầng Core thì tốc độ sẽ càng nhanh, và Cache L3 có "shared" vì thường nó sẽ là phần cache được sử dụng chung giữa nhiều CPU, còn L1 và L2 thường sẽ là tầng nằm gần từng core hơn.

Chẳng hạn khi một thread đang xử lý 1 object:

transaction.getAmount();
transaction.getStatus();
transaction.getFromWalletId();
...

CPU sẽ thường cố đưa vùng nhớ chứa object này (transaction) lên tầng Cache để những lần xử lý sau không cần chọc xuống ram. Nếu không có ở L1 thì phải tìm ở L2, L2 không có lại xuống L3, L3 không có thì xuống RAM. Mỗi bước sẽ tăng dần cost, và từ đây sẽ có cụm từ cache-friendly có thể dùng khi nói về một đoạn code. Và ghi nhớ: "Disruptor sau này tận dụng rất mạnh chuyện này bằng cách sử dụng 1 vùng memory được cấp phát sẵn và truy cập tuần tự."

1.2. Cache Line#

Ở đoạn trên, có nhắc đến việc "CPU sẽ thường cố đưa vùng nhớ chứa object lên tầng Cache". Và ở đây sẽ nhắc lại, CPU đưa cả một vùng nhớ chứ (block memory) không phải load từng biến riêng lẻ lên Cache. Và block memory được đưa lên cache này được gọi là Cache Line. Có thể coi 1 cache line = 64 bytes. Ví dụ, trong RAM đang có 1 dãy các biến như sau:

[a][b][c][d][e][f]...

Ở một thao tác, chẳng hạn CPU chỉ đọc biến [c], nhưng sau đó nó sẽ có thể cache cả một vùng [a][b][c][d][e][f]. Vì thế, việc này thường rất hiệu quả nếu chương trình truy cập memory 1 cách tuần tự. Ví dụ truy cập lần lượt từng phần tử của 1 mảng sẽ tốt hơn là nhảy lung tung. Và đây cũng là lý do Ring Buffer của Disruptor trở nên có lợi thế.

1.3. Về việc cách hai thread giao tiếp với nhau.#

Không phải là kiểu Thread A trực tiếp gửi data cho Thread B, mà chúng sẽ giao tiếp và chia sẻ dữ liệu với nhau thông qua một vùng nhớ chia sẻ chung (Shared Memory).

Tuy nhiên, trong trường hợp 2 thread chạy trên 2 core khác nhau, và mỗi core có cache riêng, thì lúc này sẽ bắt đầu xuất hiện vấn đề liên quan tới concurrency.

CPU có cơ chế cache coherence để cập nhật lại giá trị trong cache khi giá trị đã bị thay đổi. Chẳng hạn Core 1 thay đổi cache line -> Core 2 sẽ được báo là cache line của nó đã cũ, và core 2 sẽ buộc phải lấy dữ liệu mới khi cần sử dụng. Tuy nhiên, cần phải nhớ cơ chế này giúp xử lý việc đồng bộ dữ liệu giữa các core, nhưng không bao gồm tránh được race condition do độ trễ của quá trình đồng bộ

1.4. Thread scheduling và context switching#

Java là thằng tạo thread, nhưng OS mới là thằng quyết định thread nào chạy trên core nào. Lúc đầu, có thể core 1 đang chạy thread A, core 2 xử lý thread B, lúc sau lại có thể core 1 xử lý thread C, core 2 đang chạy thread A. Đó là thread scheduling. Và khi số lượng thread nhiều hơn CPU core, ví dụ có 8 core mà 200 thread được tạo, thì OS sẽ phải phân chia luân phiên CPU time dành cho mỗi thread.

Khi CPU đang chạy thread A, rồi phải chuyển sang thread B, nó sẽ phải chuyển ngữ cảnh (context switch). Ở bước này, CPU phải lưu lại hiện trạng của thread A, và restore trạng thái của thread B. Ngoài cost trực tiếp của việc switch context này, còn có 1 cost quan trọng ở việc cache. Kiểu thread A sau quá trình xử lý đang có data rất đẹp trong cache, khi chuyển sang B thì CPU cần data khác, sau đó khi quay lại A sẽ cần phải warm cache lại.

Với hệ thống low latency, quá nhiều block/warmup/context switching sẽ thực sự không tốt. Và đây cũng chính là cái mà Disruptor muốn giảm.

1.5. Lock và CAS (Compare and Swap)#

Khi nhiều thread chạy song song/cùng lúc cùng có thao tác thay đổi giá trị 1 phần tử, cần đảm bảo không xảy ra race condition. Cách phổ biến là chỉ cho 1 thread thay đổi 1 lúc, đảm bảo bằng việc thằng nào đang vào sửa thì lock luôn biến đang sửa lại, thằng sau muốn vào phải chờ. Đây là cơ chế rất hữu ích, nhưng khi contention cao, 10 thread tranh chấp 1 biến chẳng hạn thì throughput tất nhiên sẽ giảm và kém ổn định hơn. Lúc này, một trong những giải pháp có thể kể đến là CAS.

Như tên gọi CAS = So sánh (compare) rồi mới thay đổi giá trị (swap). Cụ thể, một thread khi muốn thay đổi giá trị, sẽ "so sánh xem biến này có còn đang ở giá trị như tao nghĩ không, nếu có thì sửa đổi, nếu không - nghĩa là đã có thằng khác update trước, thì tao sẽ tạm thời không tác động, và retry sau". Và việc compare và swap này chắc chắn phải được thực hiện trong 1 toán tử atomic, không phải từng bước rời rạc.

Vậy có thể thấy CAS giúp cho lock-free, tránh được việc sử dụng khoá biến kiểu truyền thống. Tuy nhiên, dĩ nhiên khi quá nhiều thread cùng tác động vào một biến, nó vẫn sẽ có cost ở việc tranh chấp tài nguyên, retry khi fail,...

1.6. Vậy phần 1 này liên quan gì đến Lmax Disruptor?#

Với những vấn đề gây giảm hiệu năng trong việc 2 thread giao tiếp với nhau đã kể trên, muốn làm nhanh thì sẽ cần giảm ảnh hưởng của những thứ như memory allocation, cache miss, context switching, thread blocking, lock contention,... mà chúng ta đã đề cập ở trên. Queue thông thường vốn cũng đã giải quyết các chi phí này ở một mức độ nào đó. Tuy nhiên, khi cần hiệu năng lên cực cao (có thể đến mức cực đoan hàng triệu message/giây), thì những chi phí ở dưới queue vẫn sẽ bắt đầu trở nên đáng kể. Và phần 2 sẽ nói về những gì mà Lmax cho rằng các queue truyền thống chưa đủ tốt để sử dụng cho các hệ thống hiệu năng cao thế này, cũng như đó là lý do Lmax Disruptor được thiết kế ra đời.

2. Queue truyền thống và paint point của nó nằm ở đâu?#

Vốn dĩ queue truyền thống đã giải quyết tốt bài toán giữa producer và consumer.

Producer
   │
  put()
   ▼
 Queue
   │
 take()
   ▼
Consumer

Queue kiểu này vốn dĩ đã lo cho chúng ta rất nhiều vấn đề, thay vì để mình tự quản lý lock, CAS, wait/notify giữa các thread, memory visibility:

• thread-safe khi nhiều thread cùng đọc ghi
• đảm bảo visibility giữa các thread
• xử lý race condition
• block producer khi queue đầy, block consumer khi queue rỗng
• đánh thức thread khi có dữ liệu

Vì vậy, với đa số hệ thống backend, BlockingQueue là đủ tốt. Lmax Disruptor chỉ xuất hiện khi có yêu cầu khắt khe hơn, kiểu throughput rất cao, latency rất thấp. Khi đó, các chi phí nhỏ như lock, CAS contention, thread block, context switch, cache miss bị nhân lên hàng triệu lần thì điểm quan trọng là latency không chỉ bị chậm hơn trung bình, mà vấn đề là nó còn bị giật. Kiểu:

event 1   2 µs
event 2   2 µs
event 3   3 µs
event 4   50 µs  <- context switch / contention
event 5   2 µs

Vì thế, Disruptor có gắng giảm thiểu các ảnh hưởng này bằng việc kết hợp các yếu tố như:

• Phân bổ trước bộ nhớ (pre-allocated memory)
• Truy cập dữ liệu ô nhớ tuần tự, tuyến tính (sequential access)
• hạn chế lock, contention, blocking
• Thiết kế luồng đọc dữ liệu cache-friendly

3. Lmax Disruptor thay đổi cách nhìn queue như thế nào?#

Ý tưởng của Lmax Disruptor không phải tạo ra một queue nhanh hơn. Nó thay đổi cách producer và consumer phối hợp với nhau.

3.1. Memory được cấp phát trước, thay vì tạo mới thường xuyên#

Thay vì mỗi lần có dữ liệu mới lại tạo lại new MarketEvent(), Disruptor tạo sẵn một vùng chứa Event, cấp phát trước một kích thước nhất định, gọi là Ring Buffer.

Ví dụ từ đầu tạo 1 Ring Buffer có 8 slot Event:

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ E0  │ E1  │ E2  │ E3  │ E4  │ E5  │ E6  │ E7  │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
   0     1     2     3     4     5     6     7

Khi producer có dữ liệu mới, nó không tạo mới thêm một object Event, nó chỉ claim 1 slot đang trống, ghi dữ liệu vào Event có sẵn, sau đó publish slot này.

Code ví dụ:

long sequence = ringBuffer.next();

try {
    MarketEvent event = ringBuffer.get(sequence);

    event.setPrice(price);
    event.setQuantity(quantity);
} finally {
    ringBuffer.publish(sequence);
}

Chốt lại điểm quan trọng là sử dụng quan trọng là tái sử dụng các Event đã được tạo sẵn, thay vì tạo mới liên tục, nhờ đó giảm được chi phí cho việc cấp phát mới và Garbage Collector.

3.2. Nói kỹ hơn về Ring Buffer #

Hình dung cho dễ là Ring Buffer là 1 mảng được cấp phát cố định được sử dụng theo vòng tròn, sau khi đi 1 vòng hết các slot sẽ quay về slot ban đầu. Ví dụ có 8 slot, sau khi dùng hết slot 7 sẽ quay lại slot 0.

0 → 1 → 2 → 3 → 4 → 5 → 6 → 7
↑                               │
└───────────────────────────────┘

Nhưng Disruptor không quản lý vị trí = một biến đếm từ 0 đến 7, mà nó xử lý bằng một sequence tăng dần liên tục. Và sequence được ánh xạ vào slot vật lý, có thể hình dung kiểu sequence % size = vị trí slot tương ứng.

0 1 2 3 4 5 6 7 | 8 9 10 11 ...
│ │ │ │ │ │ │ │   │ │
▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼   ▼ ▼
0 1 2 3 4 5 6 7   0 1
      Ring Buffer

Và Sequence cũng chính là phần linh hồn Disruptor.

Nếu queue truyền thống quan tâm đến việc queue hiện tại đang có bao nhiều phần tử, head ở đâu, tail ở đâu, thì disruptor lại quan tâm đến việc publish đến sequence nào rồi, xử lý đến sequence nào rồi.

Tư tưởng quan trọng ở đây là event không được đẩy từ producer sang consumer, mà producer và consumer phối hợp với nhau thông qua sequence. Producer sẽ nói nó đã publish đến sequence nào, và consumer sẽ nói nó đã xử lý đến sequence nào.

3.3. Một số vấn đề với Ring Buffer ở đây.#

Ghi đè dữ liệu khi Ring Buffer quay vòng

Nếu không kiểm soát cẩn thận, Producer hoàn toàn có thể quay lại một slot cũ chưa được xử lý và ghi đè dữ liệu lên nó. Đó là lý do luôn cần kiểm soát dựa vào "sequence đã publish tới" và "sequence đang xử lý tới". Và producer không thể chạy quá xa sequence. Và producer luôn phải để ý consumer chậm nhất trước khi tái sử dụng một slot cũ (gọi là Gating Sequence).

Nhiều consumer cùng xử lý một lúc

Ví dụ 1 transaction cần được xử lý bởi 2 consumer A và B, A chậm hơn B, thì sequence của A đang xử lý đến phải được coi là giới hạn A an toàn. Producer không được phép ghi đè Event lên sequence >= sequence mà A đang xử lý.

Sequence Barier

Ở chiều ngược lại, consumer cũng cần phải biết producer đã publish đến sequence nào, hay nói cách khác, sequence tiếp theo đã được producer publish chưa. Nếu chưa, thì consumer sẽ cần có cơ chế chờ.

3.4. Vậy Disruptor tối ưu ở đâu?#

Khi quay lại các kiến thức CPU và Thread ở phần trước, có thể thấy Disruptor được thiết kế theo hướng:

• Cấp phát trước bộ nhớ (pre-allocated memory), giảm chi phí của việc cấp phát mới
• tái sử dụng Event
• cố gắng truy cập memory tuần tự => tối ưu việc sử dụng CPU cache tốt hơn
• Giảm chi phí Garbage Collector của Java
• Giảm lock contention

Chốt lại điểm quan trọng nhất là:

Event nằm sẵn trong Ring Buffer. Producer và Consumer không truyền object trực tiếp cho nhau, mà phối hợp với nhau bằng Sequence.

Chính cách tổ chức này giúp Disruptor giảm được chi phí overhead của Queue truyền thống khi cần throughput rất cao và latency rất thấp.

4. Vibe code một chương trình đo benchmark giữa Disruptor và Queue truyền thống#

4.1. Ba WaitStrategy#

WaitStrategy là cơ chế chờ khi chưa có Event mới. Với Lmax Disruptor, có 3 loại, cụ thể như sau:

• BlockingWaitStrategy
• • Consumer không có event thì block/chờ signal
  • CPU thấp
  • latency cao hơn và dễ có context switch
  • hợp với workload thông thường
• YieldingWaitStrategy
• • Consumer spin một lúc và gọi Thread.yield()
  • CPU cao hơn
  • latency thấp hơn Blocking
  • cân bằng cho low-latency workload
• BusySpinWaitStrategy
• • Consumer liên tục check: while (...) {}
  • gần như không nhường CPU
  • latency thấp nhất trong điều kiện phù hợp
  • tốn hẳn một CPU core

5. Trade off, và khi Disruptor thực sự đáng dùng#

Dĩ nhiên, disruptor không tạo ra hiệu năng miễn phí. Để có các yếu tố như througput cao hơn, latency thấp và ổn định hơn, mình phải chấp nhận một số trade off.

Điểm đầu tiên dễ thấy nhất đó là code phức tạp hơn. Thay vì chỉ cần put() và take() với queue, với Disruptor, người code cần phải hiểu thêm Ring Buffer, Sequence, WaitStrategy, SequenceBarier,...

Việc debug tất nhiên cũng sẽ khó khăn hơn. Một pipeline có thể chạy trên nhiều thread với dependency dựa trên Sequence. Và khi một handler chậm hoặc bị block, ảnh hưởng có thể lan ngược lại toàn bộ Ring Buffer. Và việc debug xem consumer nào chậm, sequence đang đứng ở đâu, producer bị block vì gì cũng sẽ phức tạp hơn việc sử dụng queue thông thường.

Thứ 3, vì Ring Buffer có kích thước cố định, capacity cũng phải được tính toán cho hợp lý từ đầu. Nếu consumer chậm hơn producer đủ lâu, thì cuối cùng backpressure vẫn sẽ xảy ra.

Ring Buffer nằm memory, vì thế nếu process chết, chẳng hạn JVM crash, server bị restart hay mất điện :v, thì Event trong Ring Buffer cũng sẽ biến mất. Do đó, Disruptor không thể hoàn toàn thay thế Kafka, database, transaction log,...nếu hệ thống yêu cầu luồng đó durability.

Có thể thấy Lmax Disruptor rất mạnh, tuy nhiên, không phải lúc nào cũng nên đem nó ra thay thế queue. Nó sẽ phù hợp với những hệ thống có đặc điểm như độ trễ thấp, thông lượng cao, giao tiếp chỉ gồm trong nội bộ nhỏ và thực sự yêu cầu xử lý event một cách real-time. Chẳng hạn như các hệ thống trading, xử lý dữ liệu real-time từ thị trường, luồng ghi log hay phân tích dữ liệu real-time,..

Tóm lại, điểm chung của các bài toán nên áp dụng lmax-disruptor là "Event được xử lý với tốc độ cao, chủ yếu chạy trong 1 process, và chi phí giao tiếp của các thread thực sự trở thành một phần đáng kể của latency tổng thể."

Với một luồng xử lý chạy qua nhiều thành phần, ví dụ Producer -> Queue -> Consumer -> Call API -> Database, thì nếu muốn tối ưu, nên tập trung xử lý bottleneck kiểu network, database, các external services, những thứ thường chiếm thời gian xử lý tính bằng ms trước khi tính đến µs như queue.

Theo mình điều đáng học nhất ở Disruptor có lẽ chính là tư duy đứng sau nó. Rằng phần mềm cuối cùng vẫn sẽ chạy trên nền tảng vật lý, CPU, cache, memory, thread. Nên nếu thực sự hiểu cách phần cứng hoạt động thế nào, ta sẽ có thể thiết kế phần mềm thuận theo nó thay vì chống lại nó.