Проверка фильтра Блума iOS: ложные срабатывания и снимки

При синхронизации офлайн-списка клиенту нужно определить, встречалась ли ему запись раньше. Поиск каждой записи на диске может создавать лишнюю нагрузку. Фильтр Блума позволяет сразу отсеять ключи, которых точно нет, но если принять «возможно, существует» за «уже обработано», новые записи будут незаметно пропускаться. Проверять эту логику регулярным тестовым заданием на облачном Mac проще, чем искать причину потери данных после выпуска.

Сначала решите, нужен ли вероятностный индекс

У точного множества, индекса базы данных и фильтра Блума свои задачи. Если данных немного и нужен однозначный ответ, используйте точное множество. Если данные уже хранятся на диске, а стоимость запросов приемлема, отдайте предпочтение индексу базы данных. Дополнительный фильтрующий слой стоит рассматривать лишь тогда, когда множество отсутствующих ключей приводит к дорогостоящим запросам.

Фильтр Блума отмечает ключ в нескольких позициях битового массива, вычисленных с помощью хеширования. Если при проверке хотя бы один из этих битов равен нулю, ключа нет. Если все биты равны единице, ключ лишь может присутствовать. Фильтр не позволяет перечислить исходные ключи и не заменяет основное хранилище данных.

Гарантия «без ложноотрицательных результатов» действует при условии, что ключ уже вставлен, битовый массив не повреждён, при проверке используется тот же алгоритм и обновления не терялись. Это не безусловная гарантия для всей прикладной системы.

В этом примере проверяется только фильтр, поддерживающий добавление. При удалении записи нельзя просто сбросить её биты: ими могут пользоваться другие ключи. Если требуется удаление, нужно перестроить фильтр или выбрать структуру данных с поддержкой удаления.

Зафиксируйте кодировку ключей и алгоритм вычисления битовых позиций

Для сохраняемого фильтра нельзя напрямую использовать Swift Hasher: он не гарантирует одинаковых результатов в разных процессах. Сначала определите представление ключа в UTF-8, затем зафиксируйте алгоритм вычисления хеша и битовых позиций. Прикладные правила, например смену регистра или удаление пробелов по краям, нужно единообразно применять на входе, а не оставлять на усмотрение вызывающего кода.

Ниже приведена фиксированная учебная конфигурация: 1024 бита и четыре битовые позиции. Сохраните код в bloom-check.swift. Четыре части хеша отдельно отображаются на позиции битового массива. Эти параметры не являются производственной конфигурацией, оптимизированной для произвольного объёма данных.

import Foundation
import CryptoKit

enum SnapshotError: Error {
    case invalidLength
}

struct Bloom {
    private var bytes: [UInt8]

    init() {
        bytes = [UInt8](repeating: 0, count: 128)
    }

    init(snapshot: Data) throws {
        guard snapshot.count == 128 else {
            throw SnapshotError.invalidLength
        }
        bytes = Array(snapshot)
    }

    var snapshot: Data {
        Data(bytes)
    }

    private func positions(_ key: String) -> [Int] {
        let digest = Array(SHA256.hash(data: Data(key.utf8)))
        return stride(from: 0, to: 32, by: 8).map { start in
            let value = digest[start..<(start + 8)].reduce(UInt64(0)) {
                ($0 << 8) | UInt64($1)
            }
            return Int(value % 1024)
        }
    }

    mutating func insert(_ key: String) {
        for bit in positions(key) {
            bytes[bit / 8] |= UInt8(1 << (bit % 8))
        }
    }

    func mightContain(_ key: String) -> Bool {
        positions(key).allSatisfy { bit in
            bytes[bit / 8] & UInt8(1 << (bit % 8)) != 0
        }
    }
}

Пустая строка здесь является допустимым ключом. Если приложение не допускает пустые ключи, отклоняйте их на входе прикладного слоя, а не заставляйте фильтр молча их игнорировать. Стратегия нормализации строк тоже должна иметь версию: иначе визуально одинаковый текст может давать разные последовательности байтов.

Проверьте базовый контракт детерминированными проверками

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

var filter = Bloom()
precondition(!filter.mightContain(""))

let keys = (0..<80).map { "record-\($0)" } + [""]
for key in keys {
    filter.insert(key)
}
for key in keys {
    precondition(filter.mightContain(key))
}

let before = filter.snapshot
for key in keys {
    filter.insert(key)
}
precondition(filter.snapshot == before)

let restored = try Bloom(snapshot: before)
for key in keys {
    precondition(restored.mightContain(key))
}

do {
    _ = try Bloom(snapshot: Data(repeating: 0, count: 127))
    preconditionFailure("Invalid snapshot accepted")
} catch SnapshotError.invalidLength {
}

let saturated = try Bloom(
    snapshot: Data(repeating: 255, count: 128)
)
precondition(saturated.mightContain("never-inserted"))

xcrun swift bloom-check.swift

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

Тесты также должны охватывать длинные ключи, ключи с китайскими символами и разные представления Unicode. Не требуйте, чтобы каждый невставленный ключ давал отрицательный результат: так допустимое ложное срабатывание будет ошибочно признано дефектом реализации.

Разделяйте измерение ложных срабатываний и проверку совместимости снимков

Частота ложных срабатываний зависит от числа битов, числа хеш-функций и количества вставленных ключей. Для проверки зафиксируйте набор вставляемых ключей, затем подсчитайте положительные ответы на заведомо непересекающемся с ним наборе запросов. Сохраните размер выборки и версию алгоритма. Отсутствие ложных срабатываний в одном небольшом эксперименте не означает, что их реальная вероятность равна нулю.

В рабочей системе недостаточно сохранять в снимок только показанный выше битовый массив. Внешний формат должен содержать как минимум версию, число битов, число хеш-функций, правила кодирования ключей и поколение набора данных, а также предусматривать проверку целостности полезной нагрузки. Правильная длина позволяет исключить усечение, но не обнаружит, что какой-то бит изменился с единицы на ноль.

Добавьте тестовый снимок для проверки между процессами

Экспорт и восстановление в пределах одного процесса проверяют лишь часть логики. Сохраните в репозитории тестовый снимок, созданный по фиксированному набору ключей. Другой процесс должен прочитать его и проверить все вставленные ключи. Только так можно обнаружить нарушения совместимости из-за обновления алгоритма или изменения кодировки. Если формат несовместим, перестройте фильтр по основным данным, а не пытайтесь угадать старые параметры.

При подключении к конвейеру предусмотрите корректный обход фильтра

Эту реализацию на основе типа-значения нельзя напрямую совместно использовать для параллельных вставок: операции «чтение — изменение — запись» могут приводить к потере установленных битов. Используйте единственного владельца с последовательным доступом или блокировку и исключите параллельную запись во время создания снимка. Порядок обновления битового массива и основных данных тоже необходимо закрепить в протоколе восстановления.

Если фильтр отстаёт от базы данных, отрицательным результатам больше нельзя доверять. На время перестроения обходите фильтр и обращайтесь непосредственно к основному хранилищу. Включайте его снова только после согласованного переключения, а не направляйте запросы в новый, ещё неполный битовый массив.

Итоговая проверка должна подтверждать, что все вставленные ключи находятся, повторная вставка не меняет снимок, повреждённый формат отклоняется, старые тестовые снимки по-прежнему читаются, а приложение при положительном ответе действительно выполняет точную проверку в основном хранилище. Сбой фильтра может замедлить запросы, но не должен приводить к исчезновению новых записей.

Часто задаваемые вопросы