[PHP, Анализ и проектирование систем, NoSQL] Паспортный контроль, или Как сжать полтора гигабайта до 42 мегабайт
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Однажды, в качестве тестового задания на позицию 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/.
===========
Источник:
habr.com
===========
Похожие новости:
- [Microsoft Azure, DevOps, Облачные сервисы] Основы сервиса Microsoft Azure Blueprints
- [PHP, Разработка под e-commerce, Magento] Неочевидные факты о коллекциях в Magento 2
- [Программирование, Анализ и проектирование систем, Хакатоны] Группа «М.Видео-Эльдорадо» приглашает на онлайн-контест для аналитиков
- Microsoft опубликовал код движка хранения Extensible Storage Engine
- [Интернет-маркетинг, Контекстная реклама, Поисковая оптимизация] 25+ сервисов, которых боятся ваши конкуренты
- [Разработка веб-сайтов, PHP, Проектирование и рефакторинг, API] Хьюстон, у нас проблема с интерпретацией ошибок
- [Настройка Linux, Серверное администрирование] Почему линукс использует swap-файл
- [Системное администрирование, Серверная оптимизация, Хранение данных, Хранилища данных] Тестируем СХД OceanStor Dorado V6: Hyper и Smart
- [Веб-дизайн, Разработка веб-сайтов, PHP, 1С-Битрикс] Фреймворки против Битрикс
- [PHP, Карьера в IT-индустрии] Что должен знать Junior PHP Developer
Теги для поиска: #_php, #_analiz_i_proektirovanie_sistem (Анализ и проектирование систем), #_nosql, #_pasportnye_dannye (паспортные данные), #_optimizatsija (оптимизация), #_redis, #_pilosa, #_php, #_php, #_analiz_i_proektirovanie_sistem (
Анализ и проектирование систем
), #_nosql
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 17:44
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
Однажды, в качестве тестового задания на позицию 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/. =========== Источник: habr.com =========== Похожие новости:
Анализ и проектирование систем ), #_nosql |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 17:44
Часовой пояс: UTC + 5