Паспортный контроль, или Как сжать полтора гигабайта до 42 мегабайт

Однажды, в качестве тестового задания на позицию PHP разработчика была предложена задача реализации сервиса проверки номеров паспортов граждан РФ на предмет нахождения в списке недействительных. Текст задания был лаконичным: «Пользовательская база 10 миллионов, время ответа 1 миллисекунда, аптайм 99%».

Входные данные

Для начала посмотрим, в каком виде представлены записи в списке недействительных паспортов. На сайте МВД РФ ^[1] можно скачать bzip2-архив размером около 460 МБ, внутри которого CSV-файл с двумя колонками PASSP_SERIES,PASSP_NUMBER. Размер распакованного файла примерно 1.5 ГБ. Всего в списке около 130 миллионов записей. Стоит отметить, что не все записи в файле имеют правильный формат — номер серии из 4 цифр и номер паспорта из 6 цифр. Встречаются буквенные серии, номера из 5 и меньше цифр, либо номера с символами 3,+,] — артефакты распознавания. Итого около 10 тыс. записей имеют неправильный формат. Их можно игнорировать при условии проверки входных данных будущего сервиса — не пытаться искать в списке заведомо неправильные номера.

Способ хранения

Требуемое время ответа сервиса в 1 мс накладывает ограничение на возможные способы хранения и поиска по списку. Данные нужно проиндексировать, а индекс хранить в оперативной памяти.

Первое очевидное решение — создать таблицу в SQL базе данных с индексом по двум колонкам. В качестве индекса под условия задачи больше подойдет Hash Table со средней сложностью поиска O(1) против O(log n) для B-Tree индекса. Но у такого подхода есть существенный минус — избыточность хранимых данных. Например, MEMORY таблица в MySQL занимает 5 ГБ (2 ГБ данные и 3 ГБ индекс).

Для решения исходной задачи необходим только факт наличия или отсутствия записи в списке и не обязательно хранить саму запись. Закодируем серию и номер бинарными значениями: 1 — паспорт присутствует в списке, 0 — отсутствует. Для всего множества возможных серий и номеров потребуется 9999 х 999999 ~ 10^10 бит ~ 1.25ГБ. Это сопоставимо с размером исходного файла, но уже с поиском за O(1). Но всё множество хранить не обязательно. Заметим, что в исходном списке около 3 тысяч уникальных серий, их можно сделать ключом для секционирования записей — хранить номера паспортов с одинаковой серией в одном битовом массиве. Номер паспорта будет соответствовать отступу в массиве. Длина массива будет зависеть от максимального номера в серии. Другими словами, если в серии 3382 встречается только один паспорт с номером 000032, то для всей серии потребуется 4 байта. Однако, если в этой же серии будет ещё паспорт с номером 524288, то размер вырастет до 64 килобайт, при этом почти весь массив будет состоять из нулей. Проанализировав распределение максимальных номеров в сериях, можно приблизительно рассчитать требуемый объем памяти. 3389 серий, среднее максимальное значение номера паспорта — 567750. Что даст около 229 мегабайт (в Redis полный список занял 236 МБ). Таким образом мы получим возможность за константное время проверить, присутствует ли конкретный паспорт в списке недействительных, используя объем памяти, в два раза меньший исходного bzip2-архива.

Еще большей экономии можно добиться, воспользовавшись методом сжатия разреженных битовых массивов, например, библиотекой Roaring Bitmaps ^[2]. Рассчитать занимаемый объем в таком случае уже сложнее, поэтому воспользуемся эмпирическими данными, загрузив список в сервер Pilosa ^[3]. В итоге получим 42 мегабайта.

Реализация

Соблюдая баланс между эффективным и простым, выберем в качестве хранилища Redis. Используем команды SETBIT/GETBIT для работы с бинарными строками, в качестве имени ключа возьмем серию паспорта, номер паспорта — отступ в строке. Чтобы упростить процесс обновления, новый список будем загружать во временную логическую базу Redis-а, а после окончания поменяем местами с активной (команда SWAPDB).

Архив со списком на сервере МВД РФ обновляется раз в сутки. С помощью HTTP запроса HEAD и заголовка ответа Last-Modified можно узнать время последнего обновления и не загружать большой файл без необходимости. Сам файл можно распаковывать и загружать в Redis в потоковом режиме, не сохраняя на диск и используя фильтр потока 'bzip2.decompress'.

Проверку паспортов на вхождение в список недействительных будем осуществлять в пакетном режиме, принимая до 500 номеров в одном запросе. Это позволит проверить всю базу 10 миллионов пользователей при 8 параллельных потоках меньше чем за 5 секунд.

Развёртывание

Осталось выполнить последнее требование задания — аптайм 99%. Это означает, что сервис может быть недоступен 3,5 дня в течение года, либо по 14 минут каждый день. Такой доступности можно добиться, разместив сервис у провайдера с соответствующим SLA, добавив репликацию и балансировку.

Следуя современным методикам развёртывания приложений, упакуем сервис в контейнер Docker.

Исходный код

Сервис реализован на PHP 8.0 с использованием библиотек Guzzle, PHP-DI, Workerman ^[4].
Исходный код доступен в репозитории ^[5].

Автор: BlackBox

Источник ^[6]