Circular buffer (ring buffer) là gì và khi nào bạn nên dùng nó?

Question

Accepted Answer

**Circular buffer** (bộ đệm vòng) là một array kích thước cố định được coi như thể hai đầu của nó được nối thành một vòng. Hai index — **head** (đọc) và **tail** (ghi) — tiến lên và quấn vòng (wrap) bằng số học modulo, cho một queue FIFO O(1) với **không cấp phát** sau khi tạo.

## Cách quấn vòng hoạt động

```text
dung lượng 5, sau khi ghi A,B,C,D và đọc A,B:
index:  0   1   2   3   4
      [ . ][ . ][ C ][ D ][ . ]
              head^       tail^   (tail quấn về 0 ở lần ghi tiếp)
```

## Code

```python
class RingBuffer:
    def __init__(self, n):
        self.buf = [None]*n
        self.head = self.tail = self.size = 0
        self.cap = n
    def enqueue(self, x):                  # O(1)
        if self.size == self.cap: raise Exception("full")
        self.buf[self.tail] = x
        self.tail = (self.tail + 1) % self.cap   # quấn vòng
        self.size += 1
    def dequeue(self):                     # O(1)
        x = self.buf[self.head]
        self.head = (self.head + 1) % self.cap    # quấn vòng
        self.size -= 1
        return x
```

| Thao tác | Thời gian |
|---|---|
| enqueue / dequeue | O(1) |
| không gian | O(n) cố định |

## Khi nào dùng

- **Bộ đệm streaming / audio / video** — thông lượng có giới hạn, ổn định.
- Pipeline **producer–consumer** với backpressure (áp lực ngược).
- **Ghi log N sự kiện gần nhất** (ghi đè cái cũ nhất).

## Tại sao điều này quan trọng

Ring buffer cung cấp hành vi FIFO có thể dự đoán, không cấp phát, điều này thiết yếu trong các hệ thống thời gian thực và nhúng nơi cấp phát động quá chậm hoặc rủi ro.

Kích thước có giới hạn của nó cũng đóng vai trò backpressure tự nhiên, ngăn producer nhanh làm cạn kiệt bộ nhớ.