Дедупликация: проблема и масштаб

Дедупликация — одна из самых частых операций в Data Engineering. «Уникальные события», «уникальные пользователи», «уникальные URL», «уникальные хеши файлов». Везде один вопрос: «видели ли мы это раньше?».

На малых данных всё просто:

seen = set()
unique = []
for x in items:
    if x not in seen:
        seen.add(x)
        unique.append(x)

O(n) по времени, O(unique) по памяти. На миллионе event_id с 800 тысячами уникальных — 80 МБ на set (160 байт на каждую запись в set из 64-битных int).

Но что если уникальных — миллиард? Это 160 ГБ только на set. Уже не вписывается в RAM. И вот тут начинается интересное.

Set: точная дедупликация

Set отвечает на вопрос «есть ли x в наборе?» точно: либо да, либо нет. Никаких ошибок.

Стоимость точности:

• Память. Каждый элемент хранится целиком. Для строк-хешей по 32 байта это 100+ байт на элемент (overhead Python). На миллиарде — 100 ГБ.
• Distribution. Set одного процесса хранится в одной RAM. На миллиардных данных нужен distributed set (Redis Cluster, hash-сегментирование).

Set отлично работает до сотен миллионов уникальных значений. Дальше — нужны другие подходы.

Bloom filter: вероятностная дедупликация

Bloom filter — это вероятностная структура. Она отвечает на «возможно есть» и «точно нет», но не на «точно есть». То есть:

• «Точно нет» — гарантированный ответ.
• «Возможно есть» — может быть как «есть», так и «нет» (false positive).

Никогда не выдаёт false negative. Если Bloom сказал «нет» — точно нет.

Как Bloom работает

Структура: массив m бит (изначально все нули) и k хеш-функций.

Добавление элемента x:

1. Вычислить k хешей: h1(x), h2(x), ..., hk(x).
2. Установить биты по этим индексам в 1.

Проверка элемента x:

1. Вычислить те же k хешей.
2. Если все k бит равны 1 -> возможно есть.
3. Если хоть один бит 0 -> точно нет.

False positive rate (FPR)

Вероятность ложноположительного срабатывания — главная характеристика Bloom filter. Формула:

FPR = (1 - e^(-k*n/m))^k

где n — число добавленных элементов, m — размер фильтра в битах, k — число хешей.

Оптимальное k для заданных n и m: k = (m/n) * ln(2).

На практике:

• m/n = 10 (10 bits per element) -> FPR ~1%
• m/n = 14 -> FPR ~0.1%
• m/n = 20 -> FPR ~0.01%

Хорошее соотношение «память против качества». 1% FPR при 1 миллиарде элементов — это 1.2 ГБ памяти. Set на тех же данных — 100 ГБ.

Реализация на Python

Простой Bloom filter:

import hashlib
import math

class BloomFilter:
    def __init__(self, expected_n, fpr=0.01):
        self.n = expected_n
        self.m = int(-(expected_n * math.log(fpr)) / (math.log(2) ** 2))
        self.k = int((self.m / expected_n) * math.log(2))
        self.bits = bytearray((self.m + 7) // 8)   # m bits in bytes

    def _hashes(self, item):
        """k хешей через double-hashing."""
        h = hashlib.sha256(str(item).encode()).digest()
        h1 = int.from_bytes(h[:8], 'big')
        h2 = int.from_bytes(h[8:16], 'big')
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item):
        for pos in self._hashes(item):
            self.bits[pos // 8] |= (1 << (pos % 8))

    def contains(self, item):
        return all(
            self.bits[pos // 8] & (1 << (pos % 8))
            for pos in self._hashes(item)
        )

bf = BloomFilter(1_000_000, fpr=0.01)
bf.add("user_123")
print(bf.contains("user_123"))   # True (точно)
print(bf.contains("user_456"))   # обычно False, иногда True (FP)

Для production используйте pybloom-live или bloomberg-bloom — оптимизированные реализации.

Где Bloom применяется в production

Apache Cassandra. Каждый SSTable имеет Bloom filter. При SELECT сначала проверяется фильтр: «возможно есть запись с таким ключом?». Если «точно нет» — пропустить файл, не читать. Это критично, потому что seek на диске — миллисекунды.

HBase. То же самое — Bloom на каждом store file для оптимизации read.

Spark. При shuffle join Bloom filter может быть использован для pre-filtering, чтобы уменьшить объём данных, передаваемых через сеть.

Bitcoin SPV-клиенты. Light-кошельки используют Bloom для запроса только нужных транзакций у full-nodes, не выдавая полную приватность.

CDN кеши. Веб-кеши используют Bloom для быстрого ответа «этого URL точно нет в кеше».

Email anti-spam. Bloom от хешей известных спам-писем — мгновенная проверка миллионов записей.

Когда Bloom НЕ подходит

1. Нужны точные ответы. Финансовые транзакции, ID документов в legal-системах — false positive недопустим.
2. Нужно удалять элементы. Стандартный Bloom не поддерживает удаление (нельзя «обнулить» биты, не сломав других элементов). Есть варианты — counting Bloom, но они дороже.
3. Очень мало уникальных значений. При n=100 set — это 16 КБ. Bloom — overhead на k хешей и FPR ради экономии 15 КБ — не стоит.
4. Очень много значений и память не проблема. Если distributed set (Redis) уже есть — может быть проще использовать его, чем городить Bloom.

Сравнение

HyperLogLog не для membership-проверки, а для оценки числа уникальных значений. Иногда — лучшая альтернатива.

Замеры

Сравним set и Bloom на 1 миллионе строк:

import sys
import time
from pybloom_live import BloomFilter   # pip install pybloom-live

n = 1_000_000

# set
s = set()
t0 = time.time()
for i in range(n):
    s.add(f"id_{i}")
t1 = time.time()
print(f"set: {t1-t0:.2f} s, memory ~{sys.getsizeof(s) / 1024 / 1024:.0f} MB")

# Bloom
bf = BloomFilter(capacity=n, error_rate=0.01)
t0 = time.time()
for i in range(n):
    bf.add(f"id_{i}")
t1 = time.time()
print(f"bloom: {t1-t0:.2f} s, memory ~{n * 10 // 8 // 1024 // 1024} MB approx")

Типичные числа: set ~80 МБ и быстрее на add, Bloom ~1.2 МБ и медленнее (k хешей за op). Для 1 миллиона разница не критична. Для миллиарда — Bloom единственное решение.

Попробуй сам

Используйте Bloom для быстрой фильтрации:

from pybloom_live import BloomFilter

# imagine: blacklist 10 миллионов IP
blacklisted = BloomFilter(capacity=10_000_000, error_rate=0.001)

# заполнили один раз
for i in range(10_000_000):
    blacklisted.add(f"10.0.{i // 256 % 256}.{i % 256}")

# теперь проверка одного IP — O(k) с малой константой
def is_safe(ip):
    if ip in blacklisted:
        # возможно в blacklist — делаем дорогую проверку через БД
        return slow_db_check(ip)
    # точно нет в blacklist — быстро пропускаем
    return True

Этот паттерн — мгновенный фильтр + дорогая точная проверка только для подозрительных — применяется повсеместно.