Circular buffer — Ring queue cho hot path & log buffer

Hệ thống nhận 100.000 event mỗi giây từ user — nhưng chỉ cần giữ 10.000 event gần nhất cho audit trail. Dùng ArrayList thì mỗi khi đầy phải shift toàn bộ phần tử một slot — O(n) cho mỗi enqueue, bottleneck rõ ràng ở throughput cao. Dùng LinkedList thì mỗi event tạo một Node object, cache miss liên tục khi iterate, GC pressure tăng dần theo tần suất.

Cần một cấu trúc dữ liệu có kích thước cố định, O(1) enqueue, tự động đẩy ra event cũ nhất khi đầy — không alloc, không shift, không pointer chasing. Bài này giải thích ring buffer (circular buffer) — cấu trúc xương sống của log system, audio DSP, lock-free pattern, và LMAX Disruptor (case study Module 2 cuối).

1. Analogy — Đường vòng tròn một chiều

Hình dung một đường vòng tròn một chiều có 8 ô vé, đánh số 0 đến 7. Một chiếc xe chạy quanh vòng theo một chiều duy nhất và ghi vé vào ô tiếp theo trống.

• Khi xe ghi hết ô 7, nó quay lại ô 0 — không dừng, không chờ.
• Ô cũ nhất bị ghi đè — đây là "evict oldest" tự động.
• Một con trỏ thứ hai (tail) đánh dấu ô cũ nhất chưa đọc, luôn đi sau head đúng k ô (k là số dữ liệu hiện có trong buffer).

2. Định nghĩa và cấu trúc

Ring buffer gồm ba thành phần cốt lõi:

• T[] buffer — array kích thước N cố định, alloc một lần duy nhất.
• head — index ô tiếp theo sẽ ghi vào.
• tail — index ô cũ nhất chưa đọc (hoặc ô tiếp theo sẽ đọc từ đó).

Hai operation cơ bản:

offer(x) — enqueue:

buffer[head] = x
head = (head + 1) % N

poll() — dequeue:

item = buffer[tail]
tail = (tail + 1) % N
return item

2.1 Phân biệt full vs empty khi head == tail

Đây là điểm tinh tế nhất của circular buffer. Khi head == tail, có hai khả năng: buffer rỗng hoặc buffer đầy. Hai cách giải quyết phổ biến:

Cách 1 (size counter) được trình bày trong section tiếp theo. Cách 2 dùng trong một số lock-free implementation vì tránh shared mutable counter giữa producer và consumer.

3. Implement Java đầy đủ — cách 1: size counter

public class RingBuffer<T> {
    private final Object[] buffer;
    private int head = 0;      // next write position
    private int tail = 0;      // next read position (oldest element)
    private int size = 0;
    private final int capacity;

    public RingBuffer(int capacity) {
        this.capacity = capacity;
        this.buffer = new Object[capacity];
    }

    // O(1): enqueue -- returns false if full (reject-on-full mode)
    public boolean offer(T item) {
        if (size == capacity) return false;
        buffer[head] = item;
        head = (head + 1) % capacity;
        size++;
        return true;
    }

    // O(1): dequeue -- returns null if empty
    @SuppressWarnings("unchecked")
    public T poll() {
        if (size == 0) return null;
        T item = (T) buffer[tail];
        buffer[tail] = null;  // help GC -- clear reference so object can be reclaimed
        tail = (tail + 1) % capacity;
        size--;
        return item;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (size == 0) return null;
        return (T) buffer[tail];
    }

    // O(1): overwrite oldest when full (no reject -- log/audit use case)
    public void offerOverwrite(T item) {
        buffer[head] = item;
        head = (head + 1) % capacity;
        if (size < capacity) {
            size++;
        } else {
            // Buffer was full: advance tail to drop oldest element
            tail = (tail + 1) % capacity;
        }
    }

    public boolean isEmpty() { return size == 0; }
    public boolean isFull()  { return size == capacity; }
    public int size()        { return size; }
    public int capacity()    { return capacity; }
}

Lưu ý offerOverwrite: khi buffer đầy, head và tail đều tăng — buffer vẫn đầy nhưng "cửa sổ" dữ liệu trượt sang phải một ô, loại bỏ event cũ nhất. Đây là mode đúng cho audit trail: luôn giữ N event gần nhất, không bao giờ reject.

4. Bit trick — power-of-2 capacity

Modulo % là phép chia và có thể chậm trong tight loop khi compiler không thể optimize. Với capacity là lũy thừa của 2, có thể thay bằng bitwise AND:

// Standard modulo -- division-based, slower in tight loop
head = (head + 1) % capacity;          // slow path

// Bit trick -- single AND instruction, ~10x faster on tight loop
// Requires: capacity must be a power of 2 (8, 16, 32, 64, ...)
head = (head + 1) & (capacity - 1);    // fast path

Tại sao & (capacity - 1) hoạt động? Khi N là lũy thừa của 2, N - 1 là bitmask với tất cả bit thấp bằng 1. Ví dụ N = 8 (binary 1000), thì N - 1 = 7 (binary 0111). AND với 0111 giữ lại 3 bit thấp nhất — tương đương % 8 nhưng là một instruction đơn.

// Assert capacity is power of 2 -- fail fast in constructor
public RingBuffer(int capacity) {
    assert (capacity & (capacity - 1)) == 0 : "capacity must be power of 2";
    this.capacity = capacity;
    this.buffer = new Object[capacity];
}

ArrayDeque trong JDK dùng chính pattern này — capacity luôn là power of 2, index arithmetic dùng bitwise AND. Cross-link: bài 04 Module 2 đã trình bày bit trick này trong phần ArrayDeque internals.

5. ASCII state diagram

Trace chuỗi operation với capacity = 4:

Initial -- all empty:
buffer: [_,  _,  _,  _]
         0   1   2   3
head=0, tail=0, size=0

offer(A):
buffer: [A,  _,  _,  _]
head=1, tail=0, size=1

offer(B), offer(C):
buffer: [A,  B,  C,  _]
head=3, tail=0, size=3

offer(D):
buffer: [A,  B,  C,  D]
head=0  <-- wrap!, tail=0, size=4 (full)

poll() returns A:
buffer: [_,  B,  C,  D]
         0   1   2   3
head=0, tail=1, size=3

offer(E)  -- slot 0 is free now:
buffer: [E,  B,  C,  D]
head=1, tail=1, size=4 (full again, E wrapped into slot 0)

offerOverwrite(F) on full buffer -- evict oldest (B at tail=1):
buffer: [E,  F,  C,  D]
head=2, tail=2, size=4 (full, window slid: C,D,E,F)

Quan sát: sau offerOverwrite(F), buffer vẫn đầy nhưng phần tử cũ nhất (B) đã bị đẩy ra và F chiếm vị trí đó. head và tail đều bằng 2 — buffer đầy, không phải rỗng (phân biệt nhờ size == capacity).

6. Lock-free SPSC pattern

SPSC (Single Producer Single Consumer) là trường hợp đặc biệt quan trọng: một thread ghi, một thread đọc. Không cần lock nếu dùng volatile đúng cách.

public class SpscRingBuffer<T> {
    private final Object[] buffer;
    private final int mask;           // capacity - 1, for bit trick
    private volatile int head = 0;    // written only by producer
    private volatile int tail = 0;    // written only by consumer

    public SpscRingBuffer(int capacity) {
        // capacity must be power of 2
        assert (capacity & (capacity - 1)) == 0;
        this.buffer = new Object[capacity];
        this.mask = capacity - 1;
    }

    // Called by producer thread only
    public boolean offer(T item) {
        int h = head;
        if (h - tail == buffer.length) return false; // full
        buffer[h & mask] = item;
        head = h + 1;  // volatile write -- visible to consumer
        return true;
    }

    // Called by consumer thread only
    @SuppressWarnings("unchecked")
    public T poll() {
        int t = tail;
        if (head == t) return null;   // empty -- volatile read of head
        T item = (T) buffer[t & mask];
        buffer[t & mask] = null;      // help GC
        tail = t + 1;  // volatile write -- visible to producer
        return item;
    }
}

Tại sao SPSC không cần lock? Producer chỉ write head, consumer chỉ write tail — không có hai thread nào write cùng một biến. volatile đảm bảo memory ordering: khi producer write head, consumer thấy giá trị mới ngay lần đọc tiếp. Không có race condition.

7. Pitfall tổng hợp

Pitfall 1 — Quên xử lý head == tail có hai nghĩa

// WRONG: no size counter, no waste-1-slot -- ambiguous full vs empty
public class BrokenRingBuffer<T> {
    private final Object[] buffer;
    private int head = 0;
    private int tail = 0;

    public boolean isEmpty() { return head == tail; } // true khi empty VA khi full!
    public boolean isFull()  { return head == tail; } // same condition -- always returns same as isEmpty!
}

Kết quả: isEmpty() và isFull() luôn bằng nhau. Khi buffer đầy, code tưởng rỗng nên tiếp tục đọc — trả về stale data. Khi buffer rỗng, code tưởng đầy nên reject offer. Fix bằng size counter hoặc waste-1-slot như mô tả ở section 2.

Pitfall 2 — Concurrent access không có synchronization

// WRONG: shared head/tail without volatile or lock -- visible to multi-thread
private int head = 0;  // non-volatile: CPU may cache in register, other thread sees stale

// CORRECT for SPSC:
private volatile int head = 0;

// CORRECT for MPMC: use AtomicInteger or java.util.concurrent structures
// AtomicInteger head = new AtomicInteger(0);

Non-volatile integer trong multi-thread có thể bị CPU cache trong register — một thread update, thread kia vẫn thấy giá trị cũ. Kết quả: producer và consumer cùng write vào một slot (data corruption) hoặc consumer đọc slot chưa có data. Với MPMC production, ưu tiên LinkedBlockingQueue hoặc LMAX Disruptor thay vì tự implement.

Pitfall 3 — poll() quên null out slot — memory leak

// WRONG: keeps reference alive after poll
public T poll() {
    if (size == 0) return null;
    T item = (T) buffer[tail];
    // buffer[tail] = null;  <-- missing!
    tail = (tail + 1) % capacity;
    size--;
    return item;
}

Backing array vẫn giữ reference đến object đã "dequeue" — GC không thể reclaim. Với buffer capacity 10.000 và mỗi element là large object (image byte array, HTTP response body, stream), đây là memory leak thực sự: heap tăng liên tục mặc dù logic code không còn dùng các object đó. Pattern đúng: buffer[tail] = null ngay sau khi đọc giá trị, trước khi tăng tail.

8. Applied to tech

LMAX Disruptor (case study cuối Module 2) — ring buffer là core data structure của Disruptor. Thay vì dùng int counter thông thường, Disruptor dùng Sequence object với padding 64 byte xung quanh để tránh false sharing giữa các CPU core. Producer ghi vào slot theo sequence, consumer đọc khi sequence available. Throughput đạt tới hàng chục triệu message/giây trên một JVM process.

Audio DSP buffer — circular buffer giữ N sample gần nhất của audio stream. Effect delay/echo đọc sample tại offset k so với head (sample k bước trước), mix với signal hiện tại. Buffer cứ liên tục ghi sample mới — không bao giờ pause, không alloc mới. Latency của effect phụ thuộc trực tiếp vào capacity N của buffer.

Linux kernel kfifo — <linux/kfifo.h> là circular buffer dùng trong kernel cho character device và IPC. Dùng unsigned integer cho head/tail — khi tràn tự nhiên về 0 (wrapping behavior của unsigned int), modulo với capacity vẫn đúng. Tránh special-case check cho wrap-around. Code kernel C, không OOP, không lock nếu SPSC.

JDK ArrayBlockingQueue — blocking circular buffer trong java.util.concurrent. Dùng ReentrantLock + hai Condition (notFull, notEmpty) thay vì lock-free. offer block khi full (hoặc return false nếu dùng timeout), poll block khi empty. Phù hợp cho bounded producer-consumer trong multi-thread mà không cần throughput tối đa.

Bounded log retention (Sentry breadcrumb, Loki, application audit trail) — ring buffer giữ N event gần nhất, tự động drop oldest khi đầy. Sentry SDK (src/instrumentation-client.ts trong project này) dùng breadcrumb buffer: ghi lại tối đa 100 sự kiện gần nhất trước khi error xảy ra — cung cấp context cho debugging mà không tốn bộ nhớ không giới hạn.

9. Deep Dive

10. Tóm tắt

• Ring buffer là array kích thước cố định với hai con trỏ head/tail chạy vòng tròn — O(1) enqueue và dequeue, không alloc, không shift.
• head == tail có hai nghĩa (full hoặc empty) — phải dùng size counter hoặc waste-1-slot để phân biệt.
• offerOverwrite — chế độ evict-oldest khi full: cả head và tail đều tăng, buffer vẫn đầy nhưng window trượt sang event mới hơn. Dùng cho audit trail và log retention.
• Power-of-2 capacity cho phép dùng (i + 1) & (capacity - 1) thay (i + 1) % capacity — một AND instruction, nhanh hơn đáng kể trong tight loop.
• SPSC lock-free: volatile head và volatile tail đủ vì producer chỉ write head, consumer chỉ write tail — không contention. MPMC cần CAS.
• Quên null out slot sau poll giữ reference trong backing array — GC không thể reclaim, memory leak trong production.
• Ứng dụng thực tế: LMAX Disruptor, audio DSP delay buffer, Linux kfifo, ArrayBlockingQueue, Sentry breadcrumb buffer.

11. Tự kiểm tra

Bài tiếp theo: PriorityQueue intro