Circular buffer — Ring queue cho hot path & log buffer

TL;DR: Circular buffer (ring buffer) là array kích thước cố định với hai con trỏ head và tail chạy vòng theo modulo — O(1) enqueue và dequeue, không alloc, không shift. Khi buffer đầy, offerOverwrite tự động đẩy event cũ nhất ra và cửa sổ trượt sang event mới hơn. Power-of-2 capacity cho phép thay modulo bằng bitwise AND (& (N-1)) nhanh hơn đáng kể trong tight loop. SPSC lock-free chỉ cần volatile vì producer và consumer write hai biến khác nhau. Ứng dụng thực tế: LMAX Disruptor, audio DSP delay buffer, Linux kfifo, ArrayBlockingQueue, Sentry breadcrumb.

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:

• buffer[0..N-1] — 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

Time: O(1) Space: O(1) mỗi thao tác

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. Thuật toán đầy đủ — size counter

-- RingBuffer với capacity N và size counter
-- Khởi tạo:
buffer[0..N-1] <- array N phần tử
head <- 0        -- vị trí ghi tiếp theo
tail <- 0        -- vị trí đọc tiếp theo (phần tử cũ nhất)
size <- 0
capacity <- N

-- offer(x): enqueue, reject khi đầy
offer(x):
    if size = capacity: return false   -- đầy, từ chối
    buffer[head] <- x
    head <- (head + 1) % capacity
    size <- size + 1
    return true

-- poll(): dequeue, trả NIL khi rỗng
poll():
    if size = 0: return NIL
    item <- buffer[tail]
    buffer[tail] <- NIL     -- xoá reference, giúp GC thu hồi
    tail <- (tail + 1) % capacity
    size <- size - 1
    return item

-- peek(): xem phần tử đầu không xoá
peek():
    if size = 0: return NIL
    return buffer[tail]

-- offerOverwrite(x): enqueue, evict oldest khi đầy
offerOverwrite(x):
    buffer[head] <- x
    head <- (head + 1) % capacity
    if size < capacity:
        size <- size + 1
    else:
        -- Buffer đầy: trượt tail theo head, evict phần tử cũ nhất
        tail <- (tail + 1) % capacity

Time: O(1) mỗi thao tác Space: O(N) tổng

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. Sơ đồ vòng tròn — head và tail

graph LR
    S0(["Ô 0<br/>A"]) --> S1(["Ô 1<br/>B"])
    S1 --> S2(["Ô 2<br/>C"])
    S2 --> S3(["Ô 3<br/>D"])
    S3 --> S4(["Ô 4<br/>E"])
    S4 --> S5(["Ô 5<br/>(trống)"])
    S5 --> S6(["Ô 6<br/>(trống)"])
    S6 --> S7(["Ô 7<br/>(trống)"])
    S7 --> S0

    HEAD["head = 5<br/>ghi tiếp vào đây"]
    TAIL["tail = 0<br/>đọc từ đây (cũ nhất)"]

    HEAD -.-> S5
    TAIL -.-> S0

Vòng tròn 8 ô, tail=0 là phần tử cũ nhất (A), head=5 là ô trống tiếp theo sẽ ghi. Khi head tăng đến 7 rồi, lần ghi tiếp theo quay về ô 0.

5. 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:

-- Cách thông thường — modulo, chậm hơn trong tight loop:
head <- (head + 1) % capacity

-- Bit trick — một AND instruction, nhanh hơn đáng kể:
-- Yêu cầu: capacity PHẢI là lũy thừa của 2 (8, 16, 32, 64, ...)
head <- (head + 1) & (capacity - 1)

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.

-- Kiểm tra capacity là lũy thừa 2 trong khởi tạo (fail fast):
RingBuffer(capacity):
    assert (capacity & (capacity - 1)) = 0   -- nếu sai, báo lỗi ngay
    this.capacity <- capacity
    this.buffer <- array[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.

Thử ngẫmcapacity - 1 chỉ thành bitmask đúng khi capacity là lũy thừa 2. Truyền capacity = 100 vào & (capacity - 1) thay vì % capacity, index sai theo kiểu nào?

6. Trace trạng thái — capacity = 4

Khởi tạo — rỗng:
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 -- đầy

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

offer(E) -- slot 0 trống:
buffer: [E,  B,  C,  D]
head=1, tail=1, size=4 -- đầy lại, E vào slot 0

offerOverwrite(F) trên buffer đầy -- evict B (tail=1):
buffer: [E,  F,  C,  D]
head=2, tail=2, size=4 -- đầy, cửa sổ trượt: 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).

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

-- SpscRingBuffer: chỉ đúng cho 1 producer + 1 consumer
-- head: CHỈ producer ghi
-- tail: CHỈ consumer ghi
-- volatile đảm bảo memory visibility giữa 2 thread

SpscRingBuffer(capacity):
    -- capacity phải là lũy thừa của 2
    assert (capacity & (capacity - 1)) = 0
    buffer <- array[capacity]
    mask   <- capacity - 1
    volatile head <- 0   -- chỉ producer write
    volatile tail <- 0   -- chỉ consumer write

-- Gọi từ producer thread
offer(item):
    h <- head
    if h - tail = buffer.length: return false  -- đầy
    buffer[h & mask] <- item
    head <- h + 1     -- volatile write: consumer thấy ngay

-- Gọi từ consumer thread
poll():
    t <- tail
    if head = t: return NIL   -- rỗng (volatile read head)
    item <- buffer[t & mask]
    buffer[t & mask] <- NIL   -- giúp GC
    tail <- t + 1     -- volatile write: producer thấy ngay
    return item

Time: O(1) Space: O(N)

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.

8. Pitfall tổng hợp

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

-- SAI: không có size counter, không waste-1-slot
-- head = tail có thể nghĩa rỗng HOẶC đầy — không phân biệt được

isEmpty(): return head = tail   -- đúng khi rỗng, SAI khi đầy
isFull():  return head = tail   -- cùng điều kiện với isEmpty!

-- Hệ quả:
-- Khi đầy: code tưởng rỗng, tiếp tục đọc → trả stale data
-- Khi rỗng: code tưởng đầy, reject offer

Fix bằng size counter hoặc waste-1-slot như mô tả ở section 2.

Pitfall 2 — Concurrent access không có đồng bộ hoá

-- SAI: head/tail không volatile, CPU cache trong register
--      thread kia thấy giá trị cũ
head <- 0   -- non-volatile

-- ĐÚNG cho SPSC:
volatile head <- 0

-- ĐÚNG cho MPMC: dùng AtomicInteger hoặc CAS
-- atomic_head.compareAndSet(expected, newVal)

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 xoá reference — memory leak

-- SAI: giữ reference sau khi poll
poll():
    if size = 0: return NIL
    item <- buffer[tail]
    -- buffer[tail] <- NIL  -- THIẾU dòng này!
    tail <- (tail + 1) % capacity
    size <- size - 1
    return item

Backing array vẫn giữ strong 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] <- NIL ngay sau khi đọc giá trị, trước khi tăng tail.

Thử ngẫmba pitfall trên đều là lỗi một dòng thiếu — quên set NIL, quên đồng bộ hoá, quên phân biệt full/empty. Đọc code review, dấu hiệu nào giúp bạn soi ra loại bug này nhanh hơn?

9. Ứng dụng thực tế

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 và 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.

10. Deep Dive

11. 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 xoá reference 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.

12. Tự kiểm tra

Bài tiếp theo: PriorityQueue intro