Case Study: LMAX Disruptor — Ring buffer thắng BlockingQueue 10x

TL;DR: LMAX Disruptor đạt 25 triệu+ ops/s trên một JVM bằng bốn kỹ thuật cộng dồn: (1) ring buffer pre-allocated loại bỏ GC pressure — không alloc object trong steady state; (2) sequence counter tăng đơn điệu thay int index — single producer không cần CAS; (3) cache-line padding 7 long trước và sau mỗi Sequence tránh false sharing giữa producer và consumer trên các CPU core; (4) wait strategy không dùng lock — BusySpin cho HFT, Yielding cho balance throughput/CPU. Multi-consumer pipeline dùng một ring buffer duy nhất với SequenceBarrier thay thế queue giữa stage.

LMAX Exchange (London, 2010) xây dựng hệ thống khớp lệnh tài chính yêu cầu xử lý hơn 6 triệu order mỗi giây với p99 latency dưới 1 millisecond — hard real-time constraint không thể thương lượng. Nếu latency vượt ngưỡng, lệnh coi như thất bại.

Họ thử LinkedBlockingQueue chuẩn JDK: throughput chỉ khoảng 5 triệu ops/s và — quan trọng hơn — p99 latency spike khó lường vì lock contention và GC pause. Không đạt mục tiêu 6 triệu ops/s với p99 ổn định dưới 1ms. Thay vì dùng message broker ngoài, team LMAX (Martin Thompson, Dave Farley, Michael Barker) tự thiết kế Disruptor: đạt 25 triệu+ ops/s, p99 latency khoảng 50 nanosecond, zero GC pressure trong steady state.

Bài này phân tích kết hợp ring buffer (bài 05) + cache locality (bài 04) + amortized pre-allocation (bài 03 + bài 07) thành một design quyết định production-grade — capstone của Module 2.

1. Tech profile

Project: LMAX Disruptor (open-source) Repo: https://github.com/LMAX-Exchange/disruptor (Apache License 2.0) Paper: "Disruptor: High performance alternative to bounded queues" — Martin Thompson, Dave Farley, Michael Barker, Patricia Gee, Andrew Stewart (LMAX, 2011). https://lmax-exchange.github.io/disruptor/disruptor.html

Industry adoption: Log4j 2 async appender, Apache Storm internal messaging, ASOS e-commerce event pipeline, nhiều MQTT broker và HFT system.

2. Vấn đề LinkedBlockingQueue không giải được

LinkedBlockingQueue là lựa chọn mặc định cho producer-consumer pattern trong Java — thread-safe, bounded, đủ API. Nhưng thiết kế bên trong có bốn nguồn overhead cộng dồn:

Lock contention: put() và take() đều dùng ReentrantLock. Khi nhiều thread producer-consumer chạy đồng thời, lock trở thành bottleneck serialization — chỉ một thread được vào critical section tại một thời điểm. Trên CPU nhiều core, phần lớn thời gian thread chờ lock thay vì làm việc thực sự.

GC pressure: mỗi put() tạo một Node object mới trên heap. Với 6 triệu ops/s, hệ thống tạo 6 triệu object mỗi giây — GC phải liên tục thu hồi. Young generation GC pause ngắn nhưng xảy ra thường xuyên; mỗi pause là một khoảng thời gian latency spike không kiểm soát được.

Pointer chasing và cache miss: LinkedList là linked structure — mỗi Node là một object heap riêng biệt. Khi consumer đọc các node liên tiếp, CPU phải fetch từng địa chỉ bộ nhớ khác nhau, phá vỡ prefetcher. Bài 04 đã đo: traverse linked structure chậm hơn array liên tiếp khoảng 25 lần dù cùng O(n).

False sharing: producer và consumer đọc-ghi trên các biến nằm gần nhau trong bộ nhớ — có thể cùng cache line 64-byte. Khi producer write head, CPU invalidate cache line đó trên core consumer dù consumer chỉ cần đọc tail trên cùng line. Đây là false sharing: hai biến không liên quan nhau về logic nhưng tranh chấp cùng cache line.

Tổng kết: mỗi operation tốn khoảng 2 microsecond trên modern x86 trong high-contention scenario. Cần xuống khoảng 50 nanosecond — giảm 40 lần.

3. Bốn trụ cột thiết kế của Disruptor

3.1 Ring buffer pre-allocated — zero GC trong steady state

Disruptor dùng ring buffer (circular array) với kích thước cố định là lũy thừa của 2. Khác với LinkedBlockingQueue, toàn bộ N slot được pre-allocated khi khởi tạo — không có object creation mới trong quá trình chạy.

-- Khởi tạo Disruptor: pre-allocate N EventObject upfront
Disruptor(factory, bufferSize, threadFactory, ProducerType.SINGLE, YieldingWaitStrategy):
    -- factory được gọi đúng bufferSize lần khi startup
    -- Sau đó không có object creation nào trong steady state
    ringBuffer <- array[bufferSize]  -- pre-allocated
    for i <- 0 đến bufferSize-1:
        ringBuffer[i] <- factory.newInstance()   -- tạo sẵn slot

Khi producer muốn publish một event, thay vì tạo object mới, nó mutate in-place vào slot đã có:

-- Publish event: không alloc, chỉ mutate slot sẵn có
publish(orderId, price, quantity):
    seq <- ring.next()           -- claim sequence kế tiếp
    try:
        event <- ring.get(seq)   -- lấy pre-allocated object tại slot
        event.orderId  <- orderId   -- mutate in-place
        event.price    <- price
        event.quantity <- quantity
    finally:
        ring.publish(seq)        -- make slot visible cho consumer
        -- finally đảm bảo publish luôn xảy ra dù có exception

Slot object tồn tại suốt vòng đời ring buffer và được tái sử dụng mỗi vòng. Đây là amortized pre-allocation: chi phí tạo N object trải đều ra vô số lần publish — amortized cost per publish tiến về 0. Cross-link: bài 03 (amortized analysis) và bài 07 (ArrayList grow amortized).

3.2 Sequence counter thay int index

Disruptor không dùng int index đơn giản. Thay vào đó, cả producer và consumer track sequence number tăng đơn điệu mãi mãi (không wrap về 0). Slot thực tế trong ring buffer được tính bằng sequence & (bufferSize - 1) — bit trick từ bài 05.

-- Sequence: bao bọc một volatile long, tăng đơn điệu
Sequence:
    volatile value <- 0
    -- (padding bọc quanh — xem section 3.3)

-- Single producer: increment thuần, không cần CAS
claimSequence_single():
    next <- producerSequence.value + 1
    producerSequence.value <- next
    return next

-- Multi producer: CAS để nhiều producer không claim trùng
claimSequence_multi():
    loop:
        current <- producerSequence.value
        next    <- current + 1
        if producerSequence.compareAndSet(current, next):
            return next   -- claim thành công
        -- thử lại nếu thua race

Consumer đọc khi sequence sẵn sàng: SequenceBarrier gating consumer lại cho đến khi producer sequence đạt đủ giá trị cần thiết. Không có lock nào tham gia vào quá trình này.

3.3 Cache-line padding tránh false sharing

CPU x86 dùng cache line 64 byte. Nếu hai biến nằm trong cùng 64 byte, write vào biến này invalidate cache entry của biến kia trên core khác — dù hai biến hoàn toàn độc lập về logic.

Disruptor fix bằng cách padding mỗi Sequence với 7 long (56 byte) ở hai phía:

-- Sequence với manual cache-line padding
-- Mỗi long = 8 byte. 7 long trước + value + 7 long sau = 120 byte
-- Đảm bảo value nằm trên cache line riêng của nó

Sequence:
    p1, p2, p3, p4, p5, p6, p7 <- 0L   -- pre-padding: 56 byte
    volatile value              <- 0L   -- sequence thực: 8 byte
    p9, p10, p11, p12, p13, p14, p15 <- 0L  -- post-padding: 56 byte

Với padding này, mỗi Sequence chiếm riêng một cache line — write từ producer không ảnh hưởng đến cache line của consumer sequence.

3.4 Wait strategy — không lock, không block

Thay vì dùng LockSupport.park() hay Object.wait() như BlockingQueue, Disruptor cung cấp bốn wait strategy với trade-off latency vs CPU usage:

YieldingWaitStrategy là mặc định phù hợp cho hầu hết use case: throughput cao mà không tốn 100% CPU. BusySpinWaitStrategy chỉ nên dùng khi có dedicated CPU core và latency là ưu tiên tuyệt đối — thường trong HFT trading systems.

4. Sơ đồ data flow và sequence barrier

sequenceDiagram
    participant P as Producer
    participant RB as Ring Buffer<br/>[slot 0..N-1]
    participant SB as SequenceBarrier
    participant C as Consumer

    P->>RB: claim seq k (next())
    P->>RB: mutate event tại slot[k & mask]
    P->>RB: publish seq k
    RB-->>SB: producerSequence = k
    SB-->>C: chờ đến khi producerSequence >= k
    C->>RB: đọc slot[k & mask]
    C->>C: xử lý event
    C->>C: event.clear()
    C-->>SB: consumerSequence = k

Consumer không bao giờ đọc slot cho đến khi producer publish sequence tương ứng. Không có lock — consumer spin hoặc yield theo wait strategy đã chọn.

5. Multi-consumer pipeline pattern

-- Pipeline nhiều stage với một ring buffer duy nhất
-- Không có queue giữa các stage

Producer --> [Ring Buffer] --> Consumer A (validation)
                                    |
                              SequenceBarrier A
                                    |
                                    v
                              Consumer B (risk check)
                                    |
                              SequenceBarrier B
                                    |
                                    v
                              Consumer C (persistence)

Consumer B chỉ đọc event sau khi Consumer A đã xử lý xong. Disruptor express dependency qua SequenceBarrier chaining — không queue riêng giữa các stage.

-- Khai báo pipeline (pseudocode của Disruptor API):
disruptor.handleEventsWith(validator)
         .then(riskChecker)
         .then(persister, replicator)  -- persister và replicator chạy song song

Ý nghĩa:

• Stage 1 — validator: validate order fields.
• Stage 2 — riskChecker: kiểm tra risk limit. Chỉ chạy sau validator xong.
• Stage 3 — persister và replicator: ghi xuống storage và replicate sang standby node. Cả hai chạy song song (không phụ thuộc nhau), nhưng đều phải chờ riskChecker xong.

Toàn bộ pipeline dùng một ring buffer duy nhất — không có queue nào giữa các stage. Disruptor track sequence của từng consumer; event chỉ bị "consumed" (slot sẵn sàng để producer ghi đè) khi consumer chậm nhất đã xử lý xong.

6. Skeleton sử dụng Disruptor

-- Cấu trúc event (slot pre-allocated)
OrderEvent:
    orderId  <- 0
    price    <- 0.0
    quantity <- 0

    -- Consumer PHẢI gọi sau khi xử lý xong
    clear():
        orderId  <- 0
        price    <- 0.0
        quantity <- 0

-- Khởi tạo và chạy
main():
    bufferSize <- 1024   -- phải là lũy thừa của 2

    disruptor <- Disruptor(
        factory    = OrderEvent::new,      -- pre-allocate 1024 slot
        bufferSize = bufferSize,
        threadFactory,
        ProducerType.SINGLE,               -- single producer: không CAS
        YieldingWaitStrategy               -- spin + yield: low latency
    )

    -- Đăng ký consumer
    disruptor.handleEventsWith((event, sequence, endOfBatch) ->
        xử lý event.orderId tại sequence
        event.clear()   -- PHẢI clear sau khi xử lý
    )

    disruptor.start()
    ring <- disruptor.getRingBuffer()

    -- Publish 1 triệu event — không alloc object trong vòng lặp
    for i <- 0 đến 999_999:
        seq <- ring.next()       -- claim sequence (block nếu consumer quá chậm)
        try:
            event <- ring.get(seq)  -- lấy pre-allocated slot
            event.orderId  <- i
            event.price    <- 100.0 + i * 0.01
            event.quantity <- 10
        finally:
            ring.publish(seq)    -- PHẢI trong finally — tránh deadlock nếu exception

    disruptor.shutdown()

Giải thích từng điểm quan trọng:

• ring.next() claim sequence kế tiếp. Nếu consumer quá chậm và ring buffer đầy, lời gọi này block producer cho đến khi consumer giải phóng slot. Đây là backpressure tự nhiên.
• ring.get(seq) trả về object pre-allocated tại slot — không phải copy, không phải alloc mới.
• ring.publish(seq) trong finally quan trọng: nếu exception xảy ra khi mutate event mà không publish, producer sequence bị "stuck" và ring buffer deadlock mãi mãi. finally đảm bảo publish luôn xảy ra.

7. Benchmark thực tế

Số liệu từ LMAX Disruptor paper (2011) và community benchmark trên modern hardware, Java 21:

Disruptor single-producer mode đạt khoảng 110 triệu ops/s — gấp 22 lần LinkedBlockingQueue và gấp 11 lần ArrayBlockingQueue. p99 latency khoảng 50 nanosecond so với 20.000 nanosecond — giảm 400 lần.

Multi-producer mode thấp hơn single vì cần CAS để nhiều producer không claim trùng sequence — CAS có overhead khi contention cao. Nhưng 50 triệu ops/s vẫn gấp 5 lần ArrayBlockingQueue.

8. Production gotcha

Pitfall 1 — Slow consumer làm producer block

Ring buffer có kích thước cố định. Nếu consumer xử lý chậm hơn producer, ring buffer đầy và ring.next() block mãi. Đây là backpressure đúng đắn — nhưng nếu không monitor, producer thread bị stall không có alert.

-- Thay vì ring.next() block vô hạn, dùng tryNext với timeout:
try:
    seq <- ring.tryNext(1000)  -- throw nếu đầy sau 1000 spin
    try:
        event <- ring.get(seq)
        event.orderId <- orderId
    finally:
        ring.publish(seq)
catch InsufficientCapacityException:
    -- ring buffer đầy -- alert, drop, hoặc apply backpressure lên upstream
    metrics.increment("disruptor.producer.rejected")

Monitor metric quan trọng: delta giữa producerSequence và consumerSequence — khi gap lớn lên liên tục, slow consumer cần được phát hiện sớm.

Pitfall 2 — Quên event.clear() sau consume

Slot được tái sử dụng sau mỗi vòng. Nếu consumer không clear field, event mới kế tiếp sẽ có field cũ từ vòng trước — silent data corruption.

-- SAI: consumer không clear
handleEvent(event, sequence, endOfBatch):
    process(event.orderId)
    -- quên event.clear() -- lần sau slot này được dùng, orderId vẫn có giá trị cũ

-- ĐÚNG: luôn clear sau khi xử lý
handleEvent(event, sequence, endOfBatch):
    process(event.orderId)
    event.clear()   -- reset tất cả field

Pitfall 3 — Config SINGLE producer khi thực tế có nhiều thread publish

ProducerType.SINGLE không dùng CAS — nhanh hơn nhưng không an toàn khi nhiều thread gọi ring.next() đồng thời.

-- SAI: hai thread publish đồng thời với SINGLE mode
-- Không có CAS, không đồng bộ hoá
-- Hai thread có thể claim cùng sequence -> data corruption, không có exception

-- ĐÚNG: nhiều publisher thread phải dùng MULTI mode
disruptor <- Disruptor(
    ...,
    ProducerType.MULTI,    -- CAS-based claim: an toàn cho concurrent producers
    ...
)

Lỗi từ SINGLE mode với nhiều producer là silent corruption — không exception, không warning, chỉ thấy data sai ở consumer. Loại bug này rất khó reproduce trong test vì timing-dependent.

Pitfall 4 — Chọn wait strategy không phù hợp

BusySpinWaitStrategy tốn 100% CPU trên core consumer. Nếu deploy lên container với CPU limit (ví dụ --cpus=2 trên Docker) và dùng BusySpin cho 4 consumer thread, các thread tranh nhau CPU limit → throughput giảm, latency tăng — ngược tác dụng mong muốn.

Rule: BusySpinWaitStrategy chỉ dùng khi có dedicated physical core cho consumer, không chia sẻ với process khác. Trong môi trường cloud containerized, YieldingWaitStrategy hoặc SleepingWaitStrategy phù hợp hơn.

9. Alternative — high-throughput queue khác

Disruptor không phải lựa chọn duy nhất trong space high-performance queue:

• JCTools (github.com/JCTools/JCTools) — collection lock-free queue của Nitsan Wakart: SPSC, MPSC, SPMC, MPMC. Nhẹ hơn Disruptor, không có pipeline model, phù hợp khi chỉ cần một queue đơn giản thay thế ConcurrentLinkedQueue hay ArrayBlockingQueue.
• Aeron (Real Logic) — messaging library qua UDP với latency cực thấp, dùng tư tưởng tương tự Disruptor cho on-wire transport. Phù hợp cho distributed system cần sub-microsecond messaging.
• Chronicle Queue — persistent journaled queue: dùng memory-mapped file, data survive process restart. Dùng khi cần durability mà vẫn muốn throughput cao.

Khi nào chọn Disruptor thay vì các alternative:

• Pipeline processing với nhiều stage dependent consumer.
• Java/JVM environment, muốn mature library với good documentation.
• Cần fine-grained control over wait strategy và producer type.

10. Deep Dive tài liệu gốc

11. Tóm tắt

• LinkedBlockingQueue chậm vì bốn nguồn overhead cộng dồn: lock contention, GC pressure từ Node allocation per op, cache miss do linked structure, và false sharing giữa producer-consumer variables.
• Disruptor ring buffer pre-allocated loại bỏ GC pressure: N slot được tạo một lần khi startup, tái sử dụng mãi — amortized allocation cost về zero trong steady state.
• Sequence counter tăng đơn điệu thay int index: single-producer không cần CAS (increment thuần), multi-producer dùng CAS. Consumer gating qua SequenceBarrier mà không cần lock.
• Cache-line padding 7 long trước và sau mỗi Sequence đặt variable trên cache line riêng — tránh false sharing giữa producer sequence và consumer sequence trên các CPU core khác nhau.
• Wait strategy thay thế Object.wait(): BusySpin cho latency cực thấp (100% CPU), Yielding cho balance throughput/CPU, Blocking cho workload không cần throughput cao.
• Multi-consumer pipeline dùng một ring buffer duy nhất với dependent SequenceBarrier — không queue giữa stage, slow consumer tự động slow down producer qua backpressure.
• Production pitfall: quên event.clear() sau consume dẫn đến stale data leak; ProducerType.SINGLE với nhiều publisher thread gây silent corruption; slow consumer không được monitor có thể stall toàn bộ pipeline.

12. Tự kiểm tra

Bài tiếp theo: Module 2 — Tổng kết & cheat sheet