ТЕХНИЧЕСКОЕ ЗАДАНИЕ: Реализовать Bloom filter для retrieval

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

Разработать и внедрить Bloom filter для ускорения обработки часто искомых запросов (cache hit) в системе retrieval. Фильтр позволяет быстро отбрасывать запросы, которые заведомо не приведут к возврату документов (или являются «холодными»), экономя время на полноценный поиск по векторной базе. Дополнительно фильтр может использоваться как быстрый кэш для предварительного отсеивания дублирующихся запросов.

Ключевой результат Ускорение P50 latency retrieval не менее чем в 2 раза при доле cacheable запросов >30%.

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

Если нет реальной retrieval-системы — симулируем:

1. Создать in-memory список из 100 000 фраз (эмбеддинги не нужны — используем хэш строки).
2. Для каждого запроса считать «поиском» проверку в этом списке (O(n) для baseline).
3. Bloom filter будет ускорять эту проверку до O(k) (k — число хэш-функций).
4. Запросы разделить: 40% — есть в списке (found), 60% — нет (not found).
5. Замерить время обработки 10 000 запросов с фильтром и без.

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

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

Этап 1: Проектирование Bloom filter (оценка 1 час)

Действия

1. Определить входные параметры

   • Ожидаемое количество элементов, которые будут добавлены: n = 10 000
   • Допустимая вероятность ложноположительного срабатывания: p = 0.1 (можно уточнить на этапе 5)

2. Рассчитать оптимальный размер битового массива m и число хэш-функций k
   Использовать формулы:
   m = - (n * ln(p)) / (ln(2)^2)
k = (m / n) * ln(2)

   Пример расчёта для n=10 000, p=0.1:
   m ≈ -10 000 * ln(0.1) / 0.48 ≈ 10 000 * 2.3026 / 0.48 ≈ 47 920 бит ≈ 5.86 КБ
k ≈ (47 920 / 10 000) * 0.693 ≈ 3.3 ≈ 4

3. Выбрать хэш-функции

   • Для k хэшей можно либо использовать одно семейство с разными seed, либо двойное хэширование (Kirsch-Mitzenmacker).
   • Предпочтительно: 2 независимых MurmurHash3-128 + комбинация для остальных.

4. Документировать дизайн в виде краткой спецификации.

Ожидаемый результат этапа
Документ с параметрами Bloom filter (m, k, seed), обоснованием выбора, формулами.

Этап 2: Реализация Bloom filter на Python (оценка 1.5 часа)

Действия

1. Написать класс BloomFilter с методами:

   • init(self, capacity, false_positive_rate) — расчёт m, k, инициализация битовой маски (используем bitarray, если нет — байтовый массив bytearray).
   • add(self, item: str) — вычисление k позиций, установка битов.
   • contains(self, item: str) -> bool — проверка всех k битов.

   Код скелета:

   import mmh3
   from math import log, ceil
   
   class BloomFilter:
       def __init__(self, capacity: int, fp_prob: float = 0.1):
           self.capacity = capacity
           self.fp_prob = fp_prob
           self.num_bits = self._optimal_bits(capacity, fp_prob)
           self.num_hashes = self._optimal_hashes(self.num_bits, capacity)
           self.bit_array = bytearray(ceil(self.num_bits / 8))
   
       def _get_positions(self, item: str) -> list[int]:
           # Используем двойное хэширование
           h1 = mmh3.hash(item, seed=0) & 0x7FFFFFFF
           h2 = mmh3.hash(item, seed=1) & 0x7FFFFFFF
           return [(h1 + i * h2) % self.num_bits for i in range(self.num_hashes)]
   
       def add(self, item: str):
           for pos in self._get_positions(item):
               byte_idx = pos // 8
               bit_idx = pos % 8
               self.bit_array[byte_idx] |= 1 << bit_idx
   
       def contains(self, item: str) -> bool:
           for pos in self._get_positions(item):
               byte_idx = pos // 8
               bit_idx = pos % 8
               if not (self.bit_array[byte_idx] & (1 << bit_idx)):
                   return False
           return True
   
       @staticmethod
       def _optimal_bits(n: int, p: float) -> int:
           return int(-n * log(p) / (log(2) ** 2))
   
       @staticmethod
       def _optimal_hashes(m: int, n: int) -> int:
           return int((m / n) * log(2))
   

2. Написать тесты (pytest):

   • Проверка, что все добавленные элементы возвращают True.
   • Проверка, что false positive rate на случайной выборке не превышает заданного порога (например, для 1000 не добавленных элементов счётчик false positives / 1000 ≤ 0.1 + ε).
   • Проверка крайних случаев (пустая строка, добавление дубликата).

3. Протестировать с синтетическим набором из Этапа 1 (симуляция).

Ожидаемый результат этапа
Модуль bloom_filter.py с классом BloomFilter и сопутствующими unit-тестами (покрытие >80%).

Этап 3: Интеграция с retrieval-пайплайном (оценка 1 час)

Действия

1. Создать класс BloomRetrievalCache, который:

   • Инициализирует Bloom filter на основе списка часто искомых запросов (hot queries).
   • Предоставляет метод get(query): если фильтр даёт отрицательный ответ — сразу возвращаем None (или пустой список), иначе вызываем оригинальный retrieval.
   • При обнаружении нового часто повторяющегося запроса (count > threshold) динамически добавляет его в фильтр (с флагом, что он «содержится»).

2. Написать враппер для оригинального retrieval (функция original_retrieve(query)), который может быть:

   • Поиском по эмбеддингам (если есть)
   • Синтетической задержкой (например, time.sleep(0.05)) + возврат случайного документа, если запрос в hot-списке.

3. Симулировать нагрузку:

   • 1000 запросов, из которых 40% — hot (добавлены в фильтр), 60% — cold (не добавлены).
   • Для cold запросов фильтр возвращает False → поиск не выполняется.
   • Замерить общее время выполнения пайплайна.

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

Этап 4: Бенчмаркинг и валидация ускорения (оценка 1 час)

Действия

1. Создать сценарий бенчмарка benchmark.py:

   • Сгенерировать тестовый набор запросов (например, 20 000).
   • Разбить на hot/cold в пропорции 30/70 (согласно задаче).
   • Добавить горячие запросы в Bloom filter.
   • Замерить total_time_with_filter и total_time_without_filter с помощью time.perf_counter().
   • Повторить 5 раз, взять среднее.

2. Рассчитать метрики:

   • Speedup = time_without / time_with
   • False positive rate на cold запросах (фильтр говорит «есть», но в действительности запрос холодный) — не более 10%.
   • Потребление памяти фильтром (в байтах).

3. Построить график зависимости speedup от доли hot запросов (0.1, 0.2 … 0.8).

Ожидаемый результат этапа
Отчёт в формате Markdown (или Jupyter Notebook) с таблицами и графиками, показывающий достижение ускорения ≥ 2x.

Этап 5: Анализ и оптимизация (оценка 0.5 часа)

Действия

1. Проверить влияние false positive на производительность — если FP > 10%, увеличить size фильтра (уменьшить p) и повторить бенчмарк.
2. Оптимизировать хэш-функции — возможно замена на быстрые cityhash или xxhash.
3. Оценить возможность использования нескольких фильтров (например, для разных категорий запросов).
4. Зафиксировать выводы — какой компромисс между памятью, false positive и speedup выбран.

Ожидаемый результат этапа
Итоговый отчёт со сравнением двух версий (базовой и оптимизированной) и рекомендациями для production.

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

• Реализован класс BloomFilter с методами add/contains, расчёт параметров автоматический.
• Написаны unit-тесты (покрытие >80%) для BloomFilter.
• Интеграционный тест показывает, что все добавленные элементы проходят проверку.
• False positive rate на тестовой выборке (1000 холодных запросов) < 0.1.
• Бенчмарк показывает ускорение >= 2x при доле hot запросов 30%.
• Код оформлен в PEP8, добавлены докстринги, README с инструкцией по запуску.
• Документация описывает выбранные параметры (m, k) и их обоснование.

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

• Артефакт репозиторий GitHub с кодом:

  • bloom_filter.py — основная реализация
  • bloom_cache.py — интеграция с retrieval
  • benchmark.py — скрипт бенчмаркинга
  • tests/ — папка с тестами
  • requirements.txt (pybloom-live, mmh3, bitarray, pytest, matplotlib)
  • report.md — отчёт о результатах (таблицы, графики, анализ)

• Содержание отчёта

  • Исходные параметры (n=10 000, p=0.1 → m, k)
  • Результаты теста false positive rate
  • Сравнение latency с/без фильтра (таблица)
  • График speedup vs hot ratio
  • Выводы и рекомендации

• Опционально Jupyter Notebook с детальным анализом.

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

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

Примечание При первом выполнении может потребоваться до 7 часов из-за необходимости изучения библиотек и отладки.

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

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

• Я рассчитал оптимальные m и k для заданных n и p.
• Реализовал класс BloomFilter через битовую маску (bytearray/bitarray) с двойным хэшированием.
• Написал тесты, проверяющие отсутствие false negatives и приемлемый уровень false positives.
• Интегрировал фильтр в симулированный retrieval пайплайн и замерил ускорение.
• Сравнил скорость с baseline и убедился, что ускорение не менее 2x.
• Подготовил отчёт с графиками, выводами и рекомендациями.