Case Study: LMAX Disruptor — Vì sao ring buffer thắng BlockingQueue 10x

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: chỉ đạt khoảng 250 nghìn ops/s trong benchmark internal vì lock contention và GC pressure. Không đủ — chậm hơn mục tiêu hơn 24 lần. 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.

// Factory creates N OrderEvent objects upfront -- all slots pre-allocated
Disruptor<OrderEvent> disruptor = new Disruptor<>(
    OrderEvent::new,   // EventFactory: called N times at startup
    bufferSize,        // must be power of 2: 1024, 4096, ...
    threadFactory,
    ProducerType.SINGLE,
    new YieldingWaitStrategy()
);

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

long seq = ring.next();          // claim next slot
try {
    OrderEvent event = ring.get(seq);  // get pre-allocated object at slot
    event.orderId = orderId;           // mutate in-place -- no alloc
    event.price   = price;
    event.quantity = quantity;
} finally {
    ring.publish(seq);           // make slot visible to consumers
}

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.

// Simplified Sequence -- wraps a volatile long
class Sequence {
    volatile long value;
    // ...padding omitted here, shown in section 3.3
}

Producer claim sequence kế tiếp:

• Single producer: increment đơn giản, không cần CAS — cực nhanh.
• Multi producer: dùng CAS (compareAndSet) để nhiều producer cạnh tranh claim sequence không trùng nhau.

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.

Thiết kế này cho phép consumer detect "gap" — nếu producer claim sequence 5 nhưng chỉ publish đến 4, consumer biết phải chờ sequence 5. 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.

Ví dụ: producer liên tục write producerSequence, consumer liên tục read consumerSequence. Nếu hai sequence nằm gần nhau trong bộ nhớ (cùng cache line), mỗi lần producer write sẽ force consumer phải reload cache line — cache miss không cần thiết, thường gọi là false sharing.

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

// Simplified Sequence with manual cache-line padding
// Each long = 8 bytes. 7 longs before + value (8 bytes) + 7 longs after = 128 bytes
// Guarantees value is on its own 64-byte cache line.
class Sequence {
    long p1, p2, p3, p4, p5, p6, p7;  // pre-padding: 56 bytes
    volatile long value;               // the actual sequence: 8 bytes
    long p9, p10, p11, p12, p13, p14, p15; // post-padding: 56 bytes
}

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() / 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. Data flow và sequence barrier

Producer(s)                   Ring Buffer                    Consumer(s)
    |                  [slot 0][slot 1]...[slot N-1]               |
    |  claim seq k  -->  write event into slot[k & mask]           |
    |  publish seq k -->  producerSequence = k                     |
    |                                                              |
    |                  SequenceBarrier: wait until                 |
    |                  producerSequence >= k before read           |
    |                                      <-- read slot[k & mask] |

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.

Multi-consumer dependent barrier:

Producer --> [Ring Buffer] --> Consumer A (validation)
                                     |
                                     v (dependent barrier: wait A)
                               Consumer B (risk check)
                                     |
                                     v (dependent barrier: wait B)
                               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.

5. Code skeleton — minimal Disruptor usage

public class OrderEvent {
    long orderId;
    double price;
    int quantity;

    // Must be called by consumer after processing -- reused slot, old data must be cleared
    public void clear() {
        orderId = 0;
        price = 0.0;
        quantity = 0;
    }
}

public class DisruptorDemo {
    public static void main(String[] args) throws Exception {
        int bufferSize = 1024;  // must be power of 2
        ThreadFactory tf = Executors.defaultThreadFactory();

        Disruptor<OrderEvent> disruptor = new Disruptor<>(
            OrderEvent::new,           // factory: pre-allocates 1024 OrderEvent objects
            bufferSize,
            tf,
            ProducerType.SINGLE,       // single producer mode: no CAS, fastest path
            new YieldingWaitStrategy() // spin + yield: low latency, shared core friendly
        );

        // Register event handler (consumer)
        disruptor.handleEventsWith((event, sequence, endOfBatch) -> {
            System.out.println("Process order " + event.orderId
                + " at seq=" + sequence);
            event.clear(); // clear after processing -- prevent stale data leak
        });

        disruptor.start();
        RingBuffer<OrderEvent> ring = disruptor.getRingBuffer();

        // Publish 1 million events -- no object allocation in this loop
        for (int i = 0; i < 1_000_000; i++) {
            long seq = ring.next(); // claim next sequence (blocks if consumer too slow)
            try {
                OrderEvent event = ring.get(seq); // get pre-allocated slot
                event.orderId  = i;
                event.price    = 100.0 + i * 0.01;
                event.quantity = 10;
            } finally {
                ring.publish(seq); // always publish in finally -- prevent deadlock on exception
            }
        }

        disruptor.shutdown();
    }
}

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

• OrderEvent::new là factory, được gọi đúng bufferSize lần khi disruptor.start() — sau đó không có object creation nào nữa trong steady state.
• 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.

6. Multi-consumer pipeline pattern

Đây là pattern production phổ biến nhất với Disruptor: pipeline nhiều stage xử lý một event.

OrderValidator validator      = new OrderValidator();
RiskChecker    riskChecker    = new RiskChecker();
Persister      persister      = new Persister();
Replicator     replicator     = new Replicator();

disruptor.handleEventsWith(validator)
         .then(riskChecker)
         .then(persister, replicator); // persister and replicator run in parallel

Ý 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.

So sánh với traditional pipeline dùng queue giữa stage: nếu stage persistence chậm, queue giữa risk check và persistence đầy → backpressure phải lan ngược → phức tạp hơn nhiều để implement và monitor. Disruptor model đơn giản hơn: slow consumer tự động slow down producer qua ring buffer full.

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.

// Instead of ring.next() which blocks indefinitely, use tryNext with timeout
try {
    long seq = ring.tryNext(1000); // throws InsufficientCapacityException if full after 1000 spins
    try {
        OrderEvent event = ring.get(seq);
        event.orderId = orderId;
    } finally {
        ring.publish(seq);
    }
} catch (InsufficientCapacityException e) {
    // ring buffer full -- alert, drop, or apply back-pressure to 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.

// WRONG: consumer does not clear
disruptor.handleEventsWith((event, sequence, endOfBatch) -> {
    process(event.orderId); // orderId processed
    // forgot: event.clear() -- next time this slot is used, orderId still has old value
});

// CORRECT: always clear after processing
disruptor.handleEventsWith((event, sequence, endOfBatch) -> {
    process(event.orderId);
    event.clear(); // reset all fields -- prevent stale data in next cycle
});

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.

// WRONG: two threads publish concurrently with SINGLE mode
// ProducerType.SINGLE -- no CAS, no synchronization
// Two threads can claim the same sequence --> data corruption, no exception thrown
Disruptor<OrderEvent> disruptor = new Disruptor<>(
    OrderEvent::new, 1024, tf,
    ProducerType.SINGLE,   // DANGER if more than one thread calls ring.next()
    new YieldingWaitStrategy()
);

// CORRECT: multiple publisher threads require MULTI mode
Disruptor<OrderEvent> disruptor = new Disruptor<>(
    OrderEvent::new, 1024, tf,
    ProducerType.MULTI,    // CAS-based claim: safe for concurrent producers
    new YieldingWaitStrategy()
);

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: Hash function — uniform, avalanche, hashCode contract