Кольцевой буфер (circular buffer, ring buffer) хранит поток элементов в массиве фиксированной длины и при заполнении перезаписывает самые старые данные. Память под массив выделяется один раз, а запись и чтение выполняются за O(1): элементы не сдвигаются, потому что индексы зациклены.
Практический эффект: структура хранит последние N элементов потока и не даёт памяти расти, когда производитель данных обгоняет потребителя. Логи демона, телеметрия с датчиков, буфер сетевого драйвера, очередь между быстрым продюсером и медленным консьюмером решаются одним массивом и двумя индексами.
Дальше: определение и свойства, пошаговая трассировка head и tail на массиве из четырёх ячеек, два способа отличать полный буфер от пустого, рабочий код на C и Python, разбор ошибок и границы применимости.
Что такое кольцевой буфер и зачем он нужен
Кольцевой буфер - структура данных, использующая единственный буфер фиксированного размера так, как будто после последнего элемента сразу снова идёт первый (Кольцевой буфер — Википедия). Он создаётся пустым, с заранее определённой длиной, и работает по принципу FIFO (first in, first out): при продолжении записи в заполненный буфер новые данные начинают перезаписывать старые.
Три свойства определяют поведение: массив фиксированной длины, запись и чтение за O(1), потеря самых старых элементов при переполнении. Перезапись - договорённость, а не сбой: буфер хранит не весь поток, а его последний отрезок длиной N.
Фиксированный размер критичен там, где динамическое выделение памяти недопустимо или рискованно: обработчики прерываний, драйверы устройств, встраиваемые платформы с килобайтами ОЗУ, сервисы, где рост очереди приводит к OOM. Буфер на 4096 записей занимает предсказуемый объём всегда, а очередь на динамическом массиве при задержке потребителя растёт до исчерпания памяти.
Ключевые свойства и отличия от обычной очереди
Очередь на массиве при извлечении головного элемента сдвигает остальные к началу: O(n) и постоянное копирование. Динамический массив избавляет от сдвига, но при исчерпании ёмкости запускает реаллокацию и копирует все элементы (рост динамических массивов и цена копирования). Кольцевой буфер не платит ни за то, ни за другое: освободившуюся ячейку в начале массива займёт очередная запись.
Цифры для наглядности. Буфер на 10 000 элементов при сдвиге очереди на массиве перемещает около 10 000 значений на каждое извлечение, кольцевой буфер тратит одно сравнение и одно приращение индекса. При тысяче операций в секунду речь идёт о миллионах копирований в секунду против единиц инструкций.
Ёмкость, равная степени двойки, даёт дополнительный выигрыш: деление с остатком превращается в побитовую AND с маской (MAX_SIZE - 1), то есть вместо (index + 1) % capacity можно писать (index + 1) & (capacity - 1) (Структуры данных на практике. Глава 6: Стеки и очереди). Причина в том, что на многих процессорах, особенно встраиваемых, деление и деление с остатком выполняются медленно - порядка 10-40 тактов, тогда как побитовая операция укладывается в один такт. В примере с буфером приёма UART инкремент индекса выглядит как head = (head + 1) & (UART_BUFFER_SIZE - 1), где размер буфера - степень двойки. Выигрыш заметен в горячих циклах драйверов и сетевых обработчиков. Заметим, что степень двойки - не обязательное требование к кольцевому буферу, а оптимизация: без неё достаточно деления по модулю.
Логика указателей head и tail: как работает перезапись
head указывает на ячейку для следующей записи, tail - на ячейку для следующего чтения. Оба значения - индексы в массиве, не адреса памяти: сравнивать и проверять целые числа проще, чем указатели. После каждой операции индекс сдвигается по формуле next = (current + 1) % capacity, и это единственная арифметика, которая нужна буферу.
Массив никогда не перестраивается. Запись всегда идёт в data[head], чтение всегда из data[tail]. Когда head догоняет tail, свободных ячеек не остаётся; когда tail догоняет head, все записанные элементы прочитаны. Порядок чтения совпадает с порядком записи, пока ёмкости хватает.
Отсюда парадокс: равенство head == tail описывает и полный, и пустой буфер. Разрешить его можно двумя способами - счётчиком элементов или одной зарезервированной ячейкой. В режиме перезаписи добавляется третье правило: если буфер полон, перед записью сдвигается tail, иначе будет затёрт ещё не прочитанный элемент.
Пошаговый пример: запись и чтение в буфере на 4 элемента
Массив из четырёх ячеек (индексы 0-3), счётчик count, последовательность из шести записей и двух чтений. Столбец «Содержимое» показывает элементы в порядке чтения, от tail к head.
| Шаг | Операция | head | tail | count | Содержимое |
|---|---|---|---|---|---|
| 0 | init | 0 | 0 | 0 | пусто |
| 1 | write A | 1 | 0 | 1 | A |
| 2 | write B | 2 | 0 | 2 | A, B |
| 3 | write C | 3 | 0 | 3 | A, B, C |
| 4 | read -> A | 3 | 1 | 2 | B, C |
| 5 | write D | 0 | 1 | 3 | B, C, D |
| 6 | read -> B | 0 | 2 | 2 | C, D |
| 7 | write E | 1 | 2 | 3 | C, D, E |
| 8 | write F | 2 | 2 | 4 | C, D, E, F |
| 9 | write G (перезапись C) | 3 | 3 | 4 | D, E, F, G |
На шаге 5 видно, как работает кольцо: после чтения A освободилась ячейка 0, и запись D заняла именно её, хотя head уже прошёл дальше. На шаге 8 head и tail совпали (оба равны 2), но буфер полон, а не пуст: count равен 4. На шаге 9 запись G перезаписала C, и tail сдвинулся с 2 на 3, чтобы чтение продолжилось с самого старого из оставшихся элементов. Если бы tail не сдвинулся, читатель получил бы только что записанный G вне очереди.
Три состояния, которые нужно различать в коде: пустой (count == 0), частично заполненный (0 < count < capacity), полный (count == capacity). Переход из полного в частично заполненный происходит только при чтении, из частично заполненного в полный - только при записи.
Проверка переполнения и опустошения: как не потерять данные
Проверка состояния - место, где чаще всего ломается буфер. Ошибка вида «если head == tail, считаем буфер пустым» приводит к тому, что при полном буфере чтение возвращает мусор, а запись затирает данные, которые ещё не забрал потребитель. Ниже два рабочих способа различать состояния.
Способ 1: счётчик элементов
В структуру добавляется поле count. Запись увеличивает его, чтение уменьшает. Буфер пуст при count == 0, полон при count == capacity. Проверки становятся однозначными, и никакая комбинация индексов не вводит в заблуждение.
Плюсы: простота, явность, дополнительные метрики (заполненность в процентах, число потерянных при перезаписи элементов). Минус один: в многопоточной среде count становится общим изменяемым полем, и его нужно защищать синхронизацией вместе с индексами. Для однопоточных скриптов и обработчиков в одном потоке это ограничение не мешает.
Способ 2: одна свободная ячейка
Буфер считается полным, когда (head + 1) % capacity == tail, и пустым, когда head == tail. Ячейка, на которую указывает tail при полном буфере, остаётся незанятой: именно она отделяет состояние «полон» от «пуст».
Плюсы: не нужен счётчик, достаточно двух индексов, что удобно в коде драйверов и в структурах, которые читаются конкурентно. Минусы: полезная ёмкость на единицу меньше объявленной (массив на 1024 ячейки хранит 1023 элемента), проверки читаются хуже, а условие легко перепутать при переходе между состояниями. По этой схеме работает часть буферов в ядрах ОС и встраиваемых библиотеках.
Ещё одна ошибка, которая встречается в обеих схемах: запись в полный буфер без сдвига tail. В режиме перезаписи порядок обязателен - сначала сдвинуть tail, потом писать в head. Если поменять шаги местами, читатель потеряет элемент из середины очереди, а не самый старый.
Рекомендация: для потоковой обработки с перезаписью берите счётчик. Он даёт однозначные проверки, упрощает метрики и не требует держать в голове соглашение о пустой ячейке.
Реализация кольцевого буфера на C
В C массив под буфер выделяется один раз: либо статически, либо через malloc. Статический массив живёт в сегменте данных или на стеке и не требует освобождения, динамический позволяет выбрать размер во время выполнения (выбор между стеком и кучей). Для встраиваемых систем чаще подходит статический вариант: предсказуемое потребление памяти и отсутствие фрагментации.
Структура и инициализация
#include <stdlib.h>
typedef struct {
int *data;
size_t capacity;
size_t head; /* индекс следующей записи */
size_t tail; /* индекс следующего чтения */
size_t count; /* сколько элементов доступно для чтения */
} ring_t;
int ring_init(ring_t *r, size_t capacity) {
if (capacity == 0) return -1;
r->data = malloc(capacity * sizeof(int));
if (r->data == NULL) return -1;
r->capacity = capacity;
r->head = 0;
r->tail = 0;
r->count = 0;
return 0;
}
void ring_free(ring_t *r) {
free(r->data);
r->data = NULL;
r->capacity = 0;
r->head = 0;
r->tail = 0;
r->count = 0;
}
Проверка capacity == 0 обязательна: при нулевой ёмкости вычисление (head + 1) % capacity приводит к делению на ноль. Возврат -1 вместо аварийного завершения оставляет решение вызывающему коду.
Запись с перезаписью и чтение
/* запись: при полном буфере самый старый элемент теряется */
void ring_write(ring_t *r, int value) {
r->data[r->head] = value;
r->head = (r->head + 1) % r->capacity;
if (r->count == r->capacity) {
r->tail = (r->tail + 1) % r->capacity; /* сдвиг на самый старый */
} else {
r->count++;
}
}
/* чтение: 0 при успехе, -1 если буфер пуст */
int ring_read(ring_t *r, int *out) {
if (r->count == 0) return -1;
*out = r->data[r->tail];
r->tail = (r->tail + 1) % r->capacity;
r->count--;
return 0;
}
int ring_is_full(const ring_t *r) { return r->count == r->capacity; }
int ring_is_empty(const ring_t *r) { return r->count == 0; }
Пример использования: буфер логов на 1024 записи. Каждый вызов ring_write добавляет идентификатор события, ring_read забирает события в порядке поступления. Когда приходит 1025-е событие, первое исчезает, а объём памяти остаётся неизменным. Для строк вместо int удобнее хранить указатели на строки или фиксированные буферы символов, но арифметика индексов не меняется.
В C нет встроенной защиты от выхода за границы массива, поэтому каждая операция с индексом требует уверенности в том, что head и tail всегда меньше capacity. Значения после операции по модулю гарантированно лежат в диапазоне 0..capacity-1, если capacity не равен нулю.
Реализация кольцевого буфера на Python
В Python две разумные стратегии: написать класс на списке, чтобы контролировать логику, или взять collections.deque с параметром maxlen, где кольцевое поведение уже встроено.
Собственная реализация на списке
class CircularBuffer:
def __init__(self, capacity):
if capacity <= 0:
raise ValueError("capacity must be positive")
self._data = [None] * capacity
self._capacity = capacity
self._head = 0
self._tail = 0
self._count = 0
def write(self, value):
self._data[self._head] = value
self._head = (self._head + 1) % self._capacity
if self._count == self._capacity:
self._tail = (self._tail + 1) % self._capacity
else:
self._count += 1
def read(self):
if self._count == 0:
raise IndexError("buffer is empty")
value = self._data[self._tail]
self._tail = (self._tail + 1) % self._capacity
self._count -= 1
return value
def is_full(self):
return self._count == self._capacity
def is_empty(self):
return self._count == 0
Список создаётся один раз через [None] * capacity, поэтому память под него не перераспределяется. Логика совпадает с версией на C: те же head, tail и count, только выход за границы состояния превращается в исключение, а не в чтение чужой памяти.
Использование collections.deque с maxlen
from collections import deque
last_events = deque(maxlen=100)
for line in stream:
last_events.append(line)
print(len(last_events)) # не больше 100
print(last_events[0]) # самое старое из сохранённых
deque принимает необязательный аргумент maxlen - максимальный размер deque или None, если размер не ограничен; атрибут maxlen доступен только для чтения (collections — Container datatypes — Python documentation). Когда длина превышает лимит, элемент с противоположного конца удаляется автоматически: для append это первый элемент, для appendleft - последний. Отдельный счётчик не нужен, проверок на переполнение тоже. Deque поддерживает потокобезопасные и эффективные по памяти добавления и извлечения с обоих концов с производительностью примерно O(1) в любом направлении. Ограничение maxlen=0 означает, что буфер отбрасывает всё; None снимает ограничение длины.
Если данные приходят с внешних источников и регистрируются в журнале, пригодится буферизация логов в Python без потери скорости: кольцевой буфер держит последние события в памяти, а запись на диск идёт пакетами.
Практические сценарии: логирование, очереди сообщений, потоковая обработка
Общий признак задач, где кольцевой буфер уместен: поток данных бесконечен, а ценность имеет последний его участок. Во всех сценариях ниже выигрыш даёт фиксированный размер и перезапись.
Буферизация логов без роста памяти
Демон пишет 5000 строк в секунду. Хранить их все в памяти нельзя, а для разбора падения нужны события за последние секунды. Буфер на 10 000 записей удерживает примерно двухсекундное окно и занимает несколько мегабайт независимо от времени работы процесса. При перезаписи старые строки исчезают, и это осознанный компромисс. Если нужна полная история, кольцевой буфер дополняют записью на диск с ротацией файлов, а сам буфер оставляют для быстрого доступа к последним событиям.
На уровне контейнеров ту же задачу решает ротация в драйвере логирования. В Docker драйвер json-file принимает опцию max-size - максимальный размер журнала до его ротации; это положительное целое число с модификатором единицы измерения, по умолчанию -1 (неограниченно). Опция max-file задаёт максимальное число файлов журнала: если ротация создаёт лишние файлы, самый старый удаляется; по умолчанию 1 (Learn how to use the json-file logging driver with Docker Engine). Docker сохраняет драйвер json-file без ротации по умолчанию для обратной совместимости со старыми версиями и для случаев, когда Docker используется как runtime для Kubernetes, поэтому ротацию нужно включать явно. Учтите: изменение драйвера логирования по умолчанию или его опций в конфигурации демона влияет только на контейнеры, созданные после изменения; существующие контейнеры сохраняют прежние опции (Learn how to configure logging driver for the Docker daemon).
В Kubernetes kubelet отвечает за ротацию логов и управление структурой их директории: он передаёт данные среде исполнения контейнера CRI, а та сохраняет логи в указанное место. С помощью параметров можно настроить максимальный размер каждого лог-файла и максимальное число таких файлов для каждого контейнера соответственно (Архитектура для сбора логов | Kubernetes). Параметры containerLogMaxFiles и containerLogMaxSize задаются в конфигурации kubelet, например в /var/lib/kubelet/config.yaml, где им можно присвоить значения вида 2 и 10Mi (Настройка Kubernetes).
Сглаживание нагрузки в очередях сообщений
Продюсер отправляет 20 000 сообщений в секунду, потребитель обрабатывает 15 000. Разница накапливается, и очередь растёт, пока не закончится память. Кольцевой буфер фиксирует верхнюю границу: при заполнении самые старые сообщения отбрасываются, а система продолжает работать. Такой режим подходит для телеметрии с датчиков, где потеря одного замера допустима, и не подходит для платёжных операций, где терять нельзя ничего.
Второй эффект - сглаживание всплесков. Буфер накапливает данные во время пиковой нагрузки и отдаёт их, когда потребитель освободился. Если разрыв в скоростях постоянный, буфер задачу не решает: он переносит точку отказа с нехватки памяти на потерю данных. Здесь помогут метрики числа перезаписей: их рост сигнализирует, что потребитель не успевает.
Третий сценарий близок к первым двум: передача данных между этапами конвейера. Когда потребителю нужен доступ к уже существующим данным без дублирования, применяют срезы и представления (общий буфер без копирования). Кольцевой буфер хранит собственные копии значений, поэтому выбирайте инструмент по задаче: представления для доступа к одному буферу, кольцо для ограниченного окна последних записей.
Типичные ошибки и подводные камни
Пять дефектов покрывают большинство проблем, которые встречаются при работе с кольцевыми буферами.
- Проверка только head == tail. Пустой и полный буфер неразличимы, чтение возвращает мусор, запись затирает непрочитанное. Решение: счётчик count или зарезервированная ячейка.
- Неверный сдвиг tail при перезаписи. Если сдвигать tail после записи в head вместо шага до неё, из очереди выпадает не самый старый элемент. Решение: порядок «сдвинуть tail, затем писать в head» и тест на полном буфере.
- Выход за границы массива. Индекс, полученный без операции по модулю, уводит запись за пределы массива и портит соседние данные. Решение: приводить индекс к диапазону после каждого изменения и проверять capacity == 0.
- Гонки при доступе из нескольких потоков. Индексы и count меняются неатомарно, поэтому читатель может увидеть промежуточное состояние. Решение: мьютекс вокруг операций либо схема single producer / single consumer с атомарными индексами.
- Потеря данных там, где она недопустима. В режиме перезаписи старые элементы исчезают молча. Решение: считать число перезаписей, отдавать его в метрики и включать режим блокировки записи, когда потеря недопустима.
Потокобезопасность: мьютексы и атомарные операции
Если один поток пишет, а другой читает, изменения head, tail и count должны быть согласованы. Самый простой вариант - мьютекс на обе операции: предсказуемо, но каждая запись и чтение получают накладные расходы на захват блокировки. Второй вариант применим, когда производитель ровно один и потребитель ровно один: индексы делают атомарными (в C подойдёт atomic_size_t с моделью памяти в стиле release/acquire), и тогда блокировка не нужна. Он быстрее, но требует точного понимания барьеров памяти.
Lock-free схемы с несколькими производителями сложны: гонки возникают уже на этапе резервирования слота и сдвига tail. Для прикладных задач, включая обработку логов и очередей в сервисах, мьютекс решает вопрос с меньшим риском ошибки. Перед выбором стоит измерить нагрузку: если захват блокировки не виден в профиле, усложнять код не нужно.
Когда кольцевой буфер не подходит
Структура теряет смысл в трёх случаях.
- Нужно хранить все данные без потерь. Перезапись уничтожает историю, поэтому для полного журнала, аудита или транзакций берите структуру с неограниченным ростом: динамический массив, связный список или внешнее хранилище.
- Нужен произвольный доступ к элементам. Кольцевой буфер отдаёт данные в порядке поступления, с головы. Поиск по середине окна требует перебора всех count элементов.
- Элементы имеют переменный размер. Массив фиксированных ячеек подойдёт только для значений одного типа и длины. Для строк и сообщений храните указатели либо ограничивайте размер записи.
Для сравнения: collections.deque в Python при maxlen=None растёт неограниченно и допускает вставку с обоих концов, а std::deque в C++ даёт доступ по индексу за O(1), но занимает больше памяти из-за блочной структуры. Кольцевой буфер выигрывает там, где нужны фиксированный объём, предсказуемое время операции и допустима потеря старых записей.
Проверить свою сборку можно тремя сценариями: записать ровно capacity элементов и прочитать их без потерь; записать capacity + 1 и убедиться, что первый элемент исчез; выполнить чтение на пустом буфере и получить ожидаемый код ошибки вместо мусора. Эти три теста закрывают проверки переполнения, перезаписи и опустошения, то есть основную часть ошибок в кольцевом буфере.