Представьте, что вам нужно сохранить миллионы записей в базе данных, но при этом получить скорость записи, близкую к работе с обычным файлом. Обычные реляционные базы (как PostgreSQL или MySQL) часто тормозят из-за постоянного поиска и обновления индексов. Здесь на помощь приходит архитектура BitCask - это подход к построению ключевого хранилища данных (key-value store), который использует последовательную запись в лог-файлы и периодическую компакцию для достижения высокой производительности. В этой статье мы разберем, как реализовать такое хранилище на Python, используя простую, но эффективную логику.
Как работает BitCask
Архитектура BitCask была разработана компанией Riak (на тот момент под названием Basho Technologies) для создания распределенной базы данных. Ключевая идея заключается в разделении данных на два типа файлов: активные (active) и неактивные (inactive).
- Активный файл: Все новые записи пишутся сюда последовательно. Это очень быстро, потому что диск не приходится «прыгать» по секторам.
- Неактивные файлы: Когда активный файл достигает определенного размера (например, 10 МБ), он переименовывается в неактивный. Система начинает писать в новый пустой активный файл.
- Компакция: Периодически система читает все неактивные файлы, удаляет устаревшие версии ключей и пишет только актуальные данные в один новый файл. Старые файлы удаляются.
Поиск данных происходит так: сначала проверяется активный файл (через индекс в памяти). Если ключа нет там, система сканирует неактивные файлы от самого нового к самому старому. Как только найден первый экземпляр ключа, поиск останавливается, так как более старые копии считаются устаревшими.
Структура проекта
Для реализации нам понадобятся несколько основных компонентов:
- Индекс в памяти: Словарь Python, где ключом является имя ключа, а значением - идентификатор файла и смещение (offset) внутри него.
- Управление файлами: Логика переключения активного файла и запуска компакции.
- Методы CRUD: Функции для добавления (
put), получения (get) и удаления (delete) данных.
Реализация класса KeyStore
Давайте напишем базовый класс. Мы будем использовать стандартную библиотеку os для работы с файлами и struct для сериализации данных, чтобы они были бинарными и компактными.
import os
import struct
import time
class BitCaskStore:
def __init__(self, data_dir='data', max_active_size=10 * 1024 * 1024):
self.data_dir = data_dir
self.max_active_size = max_active_size
if not os.path.exists(data_dir):
os.makedirs(data_dir)
# Индекс: {key: (file_id, offset)}
self.index = {}
# Список неактивных файлов (от новых к старым)
self.inactive_files = []
self.active_file_id = self._get_next_file_id()
self.active_file_path = os.path.join(self.data_dir, f"active_{self.active_file_id}.log")
self.active_file_size = 0
self._load_index_from_disk()
def _get_next_file_id(self):
"""Возвращает следующий ID файла на основе текущего времени."""
return int(time.time())
def _load_index_from_disk(self):
"""Загружает индекс из существующих файлов при старте."""
# Для простоты здесь предполагается, что индекс строится заново
# или хранится отдельно. В реальном проекте лучше сохранять метаданные.
pass
def put(self, key, value):
"""Добавляет или обновляет пару ключ-значение."""
record = self._serialize(key, value)
with open(self.active_file_path, 'ab') as f:
offset = f.tell()
f.write(record)
self.active_file_size += len(record)
self.index[key] = (self.active_file_id, offset)
if self.active_file_size >= self.max_active_size:
self._rotate_active_file()
def get(self, key):
"""Получает значение по ключу."""
if key in self.index:
file_id, offset = self.index[key]
# Если ключ в активном файле
if file_id == self.active_file_id:
return self._read_from_file(self.active_file_path, offset)
else:
# Ищем в неактивных файлах
for inactive_id in self.inactive_files:
if inactive_id == file_id:
path = os.path.join(self.data_dir, f"inactive_{inactive_id}.log")
val = self._read_from_file(path, offset)
if val is not None:
return val
return None
def delete(self, key):
"""Логически удаляет ключ, записывая маркер удаления."""
if key in self.index:
del self.index[key]
# Записываем запись с пустым значением, чтобы затереть старые версии
self.put(key, None)
def _serialize(self, key, value):
"""Сериализует ключ и значение в байты."""
key_bytes = key.encode('utf-8')
if value is None:
value_bytes = b''
else:
value_bytes = str(value).encode('utf-8')
# Формат: [len_key(4)] [key] [len_value(4)] [value]
return struct.pack('>I', len(key_bytes)) + key_bytes + \
struct.pack('>I', len(value_bytes)) + value_bytes
def _read_from_file(self, path, offset):
"""Читает запись из файла по смещению."""
try:
with open(path, 'rb') as f:
f.seek(offset)
len_key = struct.unpack('>I', f.read(4))[0]
key = f.read(len_key).decode('utf-8')
len_val = struct.unpack('>I', f.read(4))[0]
val_bytes = f.read(len_val)
if len_val == 0:
return None
return val_bytes.decode('utf-8')
except Exception as e:
print(f"Error reading from {path}: {e}")
return None
def _rotate_active_file(self):
"""Переименовывает активный файл в неактивный и создает новый."""
old_path = self.active_file_path
new_inactive_path = os.path.join(self.data_dir, f"inactive_{self.active_file_id}.log")
os.rename(old_path, new_inactive_path)
self.inactive_files.insert(0, self.active_file_id)
self.active_file_id = self._get_next_file_id()
self.active_file_path = os.path.join(self.data_dir, f"active_{self.active_file_id}.log")
self.active_file_size = 0
def compact(self):
"""Объединяет неактивные файлы, удаляя дубликаты."""
if not self.inactive_files:
return
all_keys = set(self.index.keys())
new_compact_file_id = self._get_next_file_id()
compact_path = os.path.join(self.data_dir, f"compact_{new_compact_file_id}.log")
with open(compact_path, 'wb') as out_f:
for key in all_keys:
# Получаем самое свежее значение
val = self.get(key)
if val is not None: # Пропускаем удаленные
record = self._serialize(key, val)
out_f.write(record)
self.index[key] = (new_compact_file_id, out_f.tell() - len(record))
# Удаляем старые неактивные файлы
for fid in self.inactive_files:
path = os.path.join(self.data_dir, f"inactive_{fid}.log")
if os.path.exists(path):
os.remove(path)
self.inactive_files.clear()
# Теперь компактный файл становится частью истории, но для простоты
# мы можем оставить его как единственный источник истины до следующего ротации
Особенности и подводные камни
При разработке такого хранилища важно учитывать несколько аспектов:
- Блокировки: В примере выше мы используем простые операции с файлами. В многопоточном окружении вам понадобятся механизмы блокировок (например,
threading.Lockили файловые блокировки черезflock), чтобы избежать гонок при записи. - Устойчивость к сбоям: Если программа упадет посреди записи, активный файл может быть поврежден. Обычно решают это путем записи контрольных сумм (checksums) в конец каждой записи или использованием WAL (Write-Ahead Logging).
- Память: Индекс хранится в оперативной памяти. Если база данных огромная, словарь Python может занять слишком много места. В таких случаях используют структуры данных вроде LRU-кешей или выносят часть индекса на диск.
Когда использовать BitCask?
Этот подход идеален для задач, где важны высокая скорость записи и хранение больших объемов данных, но при этом не требуется сложная транзакционная целостность. Примеры использования:
- Хранение логов событий.
- Кэширование результатов вычислений.
- База данных профилей пользователей, где частые чтения компенсируются кэшированием.
Если вам нужна строгая ACID-соответственность и сложные запросы, лучше посмотреть в сторону RDBMS или специализированных NoSQL решений вроде Cassandra или HBase, которые также используют идеи LSM-Tree, но реализованы значительно сложнее.