Однажды, в качестве тестового задания на позицию PHP разработчика была предложена задача реализации сервиса проверки номеров паспортов граждан РФ на предмет нахождения в списке недействительных. Текст задания был лаконичным: Пользовательская база 10 миллионов, время ответа 1 миллисекунда, аптайм 99%.
Входные данные
Для начала посмотрим, в каком виде представлены записи в списке
недействительных паспортов. На сайте МВД РФ можно скачать
bzip2-архив размером около 460 МБ, внутри которого CSV-файл с двумя
колонками PASSP_SERIES,PASSP_NUMBER. Размер
распакованного файла примерно 1.5 ГБ. Всего в списке около 130
миллионов записей. Стоит отметить, что не все записи в файле имеют
правильный формат номер серии из 4 цифр и номер паспорта из 9 цифр.
Встречаются буквенные серии, номера из 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. Рассчитать занимаемый объем в таком случае уже сложнее, поэтому воспользуемся эмпирическими данными, загрузив список в сервер Pilosa. В итоге получим 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.
Исходный код доступен в репозитории https://github.com/maurokouti/passport-control/.
