ТЕХНИЧЕСКОЕ ЗАДАНИЕ: Реализовать WAL для векторной БД

1. Цель задачи

Разработать и встроить механизм Write-Ahead Log (WAL) в прототип векторной базы данных, гарантирующий атомарность операций вставки и удаления векторов. Основной фокус — обеспечить возможность восстановления состояния БД после аварийного сбоя (recovery|crash recovery) за время, не превышающее 1 минуту, без потери уже подтверждённых данных.

Ключевой результат Векторная БД, поведение которой корректно восстанавливается после намеренного «убийства» процесса, при этом время восстановления ≤ 60 секунд.

2. Исходные данные

Если нет реального инструмента — симулируем:

1. Взять реализацию HNSW из библиотеки hnswlib (например, hnswlib.Index).
2. Обернуть её в простой слой persistence (сохранение на диск через index.save_index / index.load_index).
3. Добавить «точку отказа» — например, прерывать процесс после записи вектора в WAL, но до вызова add_items.

3. Технологический стек

4. Этапы выполнения

Этап 1: Проектирование WAL (2 часа)

Действия

1. Определить формат записи WAL — каждая запись должна содержать:

   • тип операции (INSERT / DELETE / CHECKPOINT)
   • уникальный ID операции (sequence number, монотонный)
   • данные вектора (float-массив для INSERT)
   • векторный ID (строка или int)
   • метку времени и CRC32 для контроля целостности.

   Предлагаемый бинарный формат (пример на Python):

   # Структура одной записи (64 байт заголовок + данные)
   struct = struct.Struct('>BQI32s')  # type, seq, len, crc
   # далее для INSERT: ID (int64) + вектор (float32 * dim)
   

2. Выбрать стратегию контрольных точек (checkpoint):

   • Каждый N-й чекпоинт (например, каждые 1000 операций) сбрасывать текущее состояние индекса на диск и очищать WAL.
   • Атомарная смена «активного» WAL-файла при чекпоинте (идея: два файла wal_0.log, wal_1.log + файл меток).

3. Определить способ гарантии atomic append

   • Использовать os.fsync после каждой записи.
   • При падении WAL-файл не должен быть повреждён — записывать длину записи в конец, а при чтении проверять CRC.

Ожидаемый результат этапа Документированная спецификация WAL (формат, файлы, стратегия чекпоинтинга).

Этап 2: Реализация записи в WAL (4 часа)

Действия

1. Написать класс WalWriter

   • Открывает/создаёт бинарный файл с именем wal_{generation}.log.
   • Метод append(op_type, vector_id, vector_data) — сериализует запись, пишет в файл, вызывает fsync.
   • Поддерживает переключение поколения при чекпоинте.

2. Реализовать log rotation и инварианты

   • При старте проверять, есть ли предыдущий WAL; если да — запускать recovery.
   • Чекпоинт: создать новый WAL-файл, старый закрыть, на следующем чекпоинте удалить старый после успешного сохранения индекса.

3. Интегрировать WAL в операции добавления/удаления векторов:

   # Псевдокод
   def add_vector(vector_id, vector):
       wal.append('INSERT', vector_id, vector)     # сначала WAL
       index.add_items(np.array([vector]), [vector_id])  # потом индекс
   

4. Добавить обработку случая сбоя после WAL, но до индекса:

   • Сделать так, чтобы метод add_items был идемпотентным (проверять duplicate IDs).

Ожидаемый результат этапа Работающий WAL, записывающий все операции в файл до их применения к индексу.

Этап 3: Реализация crash recovery (4 часа)

Действия

1. Написать класс WalRecovery

   • Читает все записи из WAL-файла (проверяя CRC).
   • Сортирует по sequence number.
   • Воспроизводит все операции в том же порядке, игнорируя дубликаты (уже применённые во время падения).
   • После восстановления делает чекпоинт.

2. Разработать сценарий тестирования recovery

   • Наполнить БД 10K векторов.
   • Вставить ещё 500 векторов, намеренно убить процесс на середине (например, после записи 250-й записи в WAL).
   • Перезапустить процесс — он должен автоматически запустить recovery.
   • Проверить, что все 500 векторов (с учётом идемпотентности) оказались в индексе.

3. Измерить время восстановления

   • Создать БД с 1M векторов и WAL с 10K незакоммиченных операций.
   • Запустить recovery, засечь time.time() до и после.
   • Цель — менее 60 секунд.

4. Реализовать оптимизации для скорости

   • Использовать параллельное применение операций (если позволяет HNSW).
   • Подгружать WAL в память и применять пакетами, избегая частых fsync.

Ожидаемый результат этапа Восстановление корректного состояния БД после crash, время < 1 мин для 10K записей.

Этап 4: Написание тестов и интеграция с нагрузкой (3 часа)

Действия

1. Написать pytest-тесты

   • Тест на пустой WAL (recovery не требуется, время ~0).
   • Тест на частично записанную запись (повреждённый CRC) — запись игнорируется, но не блокирует восстановление.
   • Тест на одновременную вставку и параллельный kill в цикле (10 раундов).
   • Тест на большой WAL (100K записей) — проверка времени < 60 сек.

2. Провести нагрузочное тестирование

   • Запустить скрипт, который непрерывно добавляет векторы (100 ops/sec).
   • Через 30 секунд убить процесс.
   • Замерить время восстановления и проверить состояние БД (количество векторов + выборочный поиск ближайших соседей).

3. Документировать процесс восстановления в коде и README:

   • Как запустить recovery вручную (если нужно).
   • Как проверить целостность после восстановления.

Ожидаемый результат этапа Набор автоматических тестов, подтверждающих корректность и производительность восстановления.

Этап 5: Финальная отладка и измерение (2 часа)

Действия

1. Провести серию замеров времени восстановления при разных размерах WAL:

   Кол-во записей в WAL	Время восстановления (среднее)
   1,000	< 1 сек
   10,000	< 5 сек
   100,000	< 30 сек
   1,000,000	< 60 сек (цель)

2. Оптимизировать узкие места

   • Убедиться, что чтение WAL лимитировано размером буфера (не грузить в память > 256 МБ).
   • Использовать memory-mapped file (mmap) для ускорения чтения.

3. Проверка durability после краша

   • Выключить питание (эмуляция VM suspend) — если есть доступ к виртуалке.
   • Вместо этого: kill -9, затем sync не вызывается, затем fsck не проверяет — только CRC.

Ожидаемый результат этапа Все метрики удовлетворяют критериям: recovery < 60 сек, потеря данных отсутствует.

5. Критерии приемки (Definition of Done)

• Формат WAL-записей полностью спроектирован и задокументирован.
• Реализован метод append, синхронно записывающий каждую операцию с fsync.
• Реализована функция recovery, которая восстанавливает все незакоммиченные операции.
• Тест с crash (kill -9) + recovery проходит без ошибок (10 раундов).
• После восстановления количество векторов в индексе совпадает с ожидаемым (все подтверждённые операции + возможно последняя частично записанная игнорируется).
• Время восстановления для WAL из 10 000 записей не превышает 1 минуты.
• Код покрыт модульными тестами (pytest) на краевые случаи: пустой WAL, повреждённый CRC, дублирующиеся операции.
• Добавлен автоматический чекпоинт (после каждых N операций или по таймеру), и WAL-файлы корректно ротируются.
• Документация в README описывает архитектуру WAL и процесс восстановления.
• Реализован мониторинг размера WAL (можно через простой подсчёт записей).

6. Ожидаемый результат

Основной артефакт

• Исходный код на Python/C++, содержащий классы WalWriter, WalRecovery, интегрированные с HNSW-индексом.
• Тестовый скрипт, симулирующий crash recovery (test_crash_recovery.py).

Содержание кода

1. wal.py — логика WAL (append, read, crc, sequence numbers).
2. checkpoint.py — стратегия чекпоинтов и ротации файлов.
3. vector_db.py — обёртка над hnswlib с поддержкой WAL.
4. tests/ — pytest-тесты и скрипт нагрузочного теста.

Дополнительные результаты

• График времени восстановления от размера WAL (опционально).
• Postmortem (короткий) на случай неудачного теста.

7. Возможные сложности и их решение

8. Бюджет времени (оценка)

Примечание Для первого выполнения задачи рекомендуется заложить дополнительно 5 часов на отладку и изучение работы HNSW. При наличии опыта с WAL и HNSW время может сократиться до 10 часов.

9. Связанные вопросы из базы знаний

10. Чек-лист самопроверки

• Я спроектировал формат записи WAL и описал его в спецификации.
• Каждая операция записи в WAL завершается fsync, и я проверил, что это не вызывает пропуска операций.
• Реализован сценарий crash + recovery, который я запустил локально не менее 3 раз без ошибок.
• Время восстановления для WAL с 10 000 записей не превышает 60 секунд (замерял секундомером).
• Я написал хотя бы 3 теста (пустой WAL, повреждённый WAL, crash после частичного добавления).
• Я проверил, что после восстановления число векторов в индексе совпадает с числом всех подтверждённых операций.
• Документация содержит команды для запуска recovery и пример вызова.
• Я добавил чекпоинт через каждые N операций, и после него старый WAL удаляется (или помечается как неактивный).