Однажды, в качестве тестового задания на позицию PHP разработчика была предложена задача реализации сервиса проверки номеров паспортов граждан РФ на предмет нахождения в списке недействительных. Текст задания был лаконичным: «Пользовательская база 10 миллионов, время ответа 1 миллисекунда, аптайм 99%».
Входные данные
Для начала посмотрим, в каком виде представлены записи в списке недействительных паспортов. На сайте МВД РФ можно скачать 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. Рассчитать занимаемый объем в таком случае уже сложнее, поэтому воспользуемся эмпирическими данными, загрузив список в сервер 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.
Исходный код доступен в репозитории.
chemistmail
Забавно, порылся у себя в репах 5 летней давности, ничего не меняется в этом мире.
реализация на haskell
реализация на clojure
и там и там просто бинарный поиск, roaring bitmaps на тот момент в готовых либах не было, а
писать самому было лень ))
Сама задачка всплывала на хабре в коментах. Там кстати на php решение вроде тоже ссылка была.
avengerweb
Да, популярная задача. На самом деле очень интересна цель конкретно в случае с php, а вообще я люблю более-менее практические задачи которые можно решить используя те или иные алгоритмы, они показательны.
Вот к примеру решение автора с редисом, вроде все хорошо придумал, но в реальности сетевая задержка между кластером с редисом и приложением будет ~1ms и то, если все будет в одном ДЦ, а он так увлёкся размером индекса, что и не учел этого. Вот тут то и кроется причина спора ниже в комментариях, у него есть четкое ограничение по времени и аптайму, но нет ограничение по памяти, в этом и есть ключ.