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

    Однажды, в качестве тестового задания на позицию 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.
    Исходный код доступен в репозитории.

    Средняя зарплата в IT

    120 000 ₽/мес.
    Средняя зарплата по всем IT-специализациям на основании 6 430 анкет, за 1-ое пол. 2021 года Узнать свою зарплату
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 84

      +3
      Забавно, порылся у себя в репах 5 летней давности, ничего не меняется в этом мире.
      реализация на haskell
      реализация на clojure
      и там и там просто бинарный поиск, roaring bitmaps на тот момент в готовых либах не было, а
      писать самому было лень ))

      Сама задачка всплывала на хабре в коментах. Там кстати на php решение вроде тоже ссылка была.
        0

        Да, популярная задача. На самом деле очень интересна цель конкретно в случае с php, а вообще я люблю более-менее практические задачи которые можно решить используя те или иные алгоритмы, они показательны.
        Вот к примеру решение автора с редисом, вроде все хорошо придумал, но в реальности сетевая задержка между кластером с редисом и приложением будет ~1ms и то, если все будет в одном ДЦ, а он так увлёкся размером индекса, что и не учел этого. Вот тут то и кроется причина спора ниже в комментариях, у него есть четкое ограничение по времени и аптайму, но нет ограничение по памяти, в этом и есть ключ.

      • НЛО прилетело и опубликовало эту надпись здесь
          +1

          Известны ли ресурсы ведущие историю этой базы данных? Так чтобы можно было определить время попадания номера документа в перечень недействительных?

            +2
            номер серии из 4 цифр и номер паспорта из 9 цифр

            А том видим 6 цифр.

            по 4 байта, т.е 520 миллионов байт (что как раз и даёт наверно около 42 мб)

            Тут все тыкают на -тся и -ться. Пора в вычисления тыкать. Чем вы считаете?

            log2(10^(4+9))=43.19 => 44 бит * 140e6 = 735Mbyte
            log2(10^(4+6))=33.22 => 34 бит * 140e6 = 568Mbyte

            log2(10^(4+9))=43.19 => 44 бит * 10e6 = 53Mbyte
            log2(10^(4+6))=33.22 => 34 бит * 10e6 = 41Mbyte
            64 бит * 10e6 = 77Mbyte

            ps: Вот тут еще новый вид самообучающихся индексов реализовали.
              0
              Это опечатка, автору уже написал в личку, поправит.
              +1

              А вот ещё вариант, местный, хабровский.

                +3
                А не проще использовать Фильтр Блума?
                  0
                  Об этом есть в статье:
                  Для всего множества возможных серий и номеров потребуется 9999 х 999999 ~ 10^10 бит ~ 1.25ГБ. Это сопоставимо с размером исходного файла, но уже с поиском за O(1).
                    +1
                    неа
                      0
                      Да, вы правы, это было просто про битовый массив, не про Блума.
                    +2
                    Фильтр Блума можно использовать как дополнение, но не как замену, т.к. в случае ложноположительного результата задача снова сведется к поиску в исходном датасете.
                      0
                      Можно подсчитать какая будет вероятность ложноположительного срабатывания для фильтра Блума размером 42MiB. По простой формуле p = (1-e^⁻kn/m)^k получаем
                      p = (1-e^⁻² 130M/42MiB)² = 0.272 (≈ каждый четвёртый)
                      что довольно много, потому что количество элементов в множестве велико. Чтобы достичь 99 перцентиля в 1мс потребуется около 150MiB фильтр. Хотя тут всё же можно использовать фильтр Блума для предпроверки, если проверять по серии, их уникальных в базе около трёх тысяч. Что с ничтожно малой вероятностью ложноположительного срабатывания займёт какие-то жалкие 20KiB объёма. А уже потом проверять по нашей сжатой базе.
                      Довольно интересный вывод можно сделать что в базе уже есть 130 миллионов недействительных паспортов, что составляет более 1% от всей мощности множества, и даже больше если учесть что регион и год потребляют лишние биты. Каждый тридцатый паспорт недействительный!
                        0
                        А ещё можно пробежать весь диапазон и добавить по фильтру Блума ложноположительные, но там тоже есть ложноположительные, которые для исходной задачи выльются уже в ложноотрицательные, что не есть хорошо, но уверен, что эту проблему можно решить чуть ли не прямым учётом
                    –1
                    Зашел сюда, чтобы увидеть очевидное решение, был сильно удивлен реализацией автора.
                    Имеем «Пользовательская база 10 миллионов», для каждого пользователя нужно хранить 1 бит информации (включен в список или нет). Итого 10 000 000 бит или 1.25 мб. Такой объем можно запросто хранить в памяти.
                      +1
                      А можно пойти ещё дальше и учитывая, что состояния всего два — включен или нет — только их и хранить. Тогда вообще в два бита уложимся.
                        +6
                        Дано 10 000 000 чисел по 34 бита каждое, числа от 0 до 9 999 999 999
                        для любого 10 значного числа нужен ответ, входит оно в эти 10 миллионов чисел или нет.
                        В общем вы немного не поняли условия задачи.
                          0

                          Хештаблица int64 на 10 000 000 элементов займёт меньше гигабайта памяти.

                            +1
                            Ну если внимательней прочитать статью «Всего в списке около 130 миллионов записей»
                            С этого момента становится интересней?
                            А 10 миллионов влезет.
                            Сорри, не 10 000 000 а 130 000 000 по 34 бита из 10 миллиардов.
                            Думаю на этой ноте про хэш таблицы разговор стоит закончить.
                              –1
                              130 млн — это всего лишь в 10 раз больше. То есть влезет в 10ГБ.
                                +2
                                Что в 200 раз больше чем в статье, тоесть на 2 порядка. Так то нынче и машины с терабайтом памяти не редкость, только с таким подходом…
                                  –1
                                  Всегда надо знать, нужна ли дальнейшая оптимизация или нет. В данном случае — не нужна. Хештаблица на 10ГБ полностью решает поставленную задачу. И не надо делать никаких допущений про правильный формат номера паспорта.

                                  В офисе в 2 км от меня час работы программиста стоит куда дороже планки памяти на 16ГБ.
                                    0
                                    Какая дальнейшая оптимизация? Вы о чем?
                                    Я эту задачу решал 5 лет назад, первое решение это вечер за компом, 120 строк кода. Потом по необходимости добавил веб + прочие плюшки в итого выросло до 400 строк.
                                    Без хэш таблиц, просто сортированный массив, 5 лет назад кстати оперативная память была сильно дороже, если быть точным, то на сервере где крутился фронт от сервиса было 8 гигов оперативы (это весь сервис, паспорта там 0.001% функционала), на бэкэнде было 16 гигов.
                                    Если бы писал сейчас, тоже бы взял разреженные битмассивы, либы потому что сейчас есть, тогда их просто на том языке на котором писал не было.
                                      +1
                                      5 лет назад, вечер за компом
                                      2-3 часа, $100/час — $250
                                      2015, DDR3 16GB — $116

                                      Хештаблица из стандартной библиотеки — 1 строка кода. Шансов на баги нет. Поддержка ничего не стоит.

                                      Это то, что называют overengineering. Тех, кто задаёт такие задачки на собеседованиях, и отказывается принимать решение с хештаблицей надо разжаловать в должности, где они не будут принимать продуктовых решений.
                                        0
                                        Если программист получает 100$ в час, то есть (после налогов?) 16k в месяц, тупо не знает алгоритмов и просто решает задачу всегда в лоб (16k в месяц это явно не аутсорсинг с Индии) Его руководителей, как и его, надо просто гнать.
                                        2 — 3 часа это заняло у меня, я не профессиональный программист, для меня это просто хобби.

                                        Ну и еще раз по комментарию выше:
                                        0.001% это проверка паспортов ~ 10 гигов по вашим словам, памяти которая дешевле чем подумать.
                                        с такой логикой как у вас, 1% это уже 10 * 1000 = 10TB оперативы
                                        весь сервис с таким подходом, спокойно уместится в 1000TB оперативной памяти.
                                        упс… Остапа понесло…
                                          0
                                          На практике даже хеш таблица в памяти не нужна в типичном случае. РПС не настолько высок и критерии по производительности не так высоки. Сгодится просто табличка на любом sql сервере. В режиме kv по pk они все хорошо работают.

                                          Если рпс слишком высок, то выделенный контейнер с хеш таблицей в памяти и примитивным АПИ на который все ходят. Или Редис какой. Храним одну копию. 10 гигов памяти по сравнения с сотней ходящих в нее серверов это копейки.

                                          Программист должен знать когда надо оптимизировать код, а когда хватит просто правильной архитектуры. И как правило хорошей архитектуры хватает.
                                            0
                                            Парни, вы статью то прочитайте, паспорта положили в redis, там есть встроенная поддержка Roaring Bitmaps, из коробки, данный алгоритм в общем то скорей всего является оптимальным для этой задачи. И rps и тд все практически идеально.
                                            И это в 40 мегабайтах, а вы все со своими хэштаблицами на 10 гигов…
                                            Если убрать весь нефункциональный код типа скачать распарсить и тд., останется вызов двух команд redis:
                                            «Используем команды SETBIT/GETBIT»
                                            ну я уж не знаю…
                                              –1
                                              Мы и говорим что практики просто взяли бы int64 ключ и не парились бы с битами. Расходы на железо настолько маленькие выходят что оно того не стоит.
                                              А экономия на поддерже любого усложненного решения многократно окупит все эти расходы.

                                              Куда положить таблицу в Редис или в sql зависит от РПС. Скорость и так и так будет достаточной для любого практического применения.
                                                0
                                                Мне сильно любопытно, почему при таких маленьких расходах на железо процветает hetzner...)

                                                Я вот не знаю кто в вашем понимании практики, последние лет 5 в основном сталкивался с большими данными, и там постоянная проблема, на одну машину не влезает (ну есть ограничения по памяти, тупо материка больше не поддерживает, никакая.)
                                                а хадупы и тд уже сильно дороже, тупо аренда железа под хадуп на 700 терабайт реплицированного диска уже гдет по 50 — 70 к $ в месяц.
                                                И вот слушаю я все эти память дешёвая, и нет слов у меня.
                                                  0
                                                  Шардирование и уж тем более перешардирование данных это большая проблема. С бигдатой вообще много проблем.

                                                  Но тут мы говорим всего о 130 миллионах лонгов. Без тенденции на рост. Это очень далеко от бигдата. Это просто табличка. Не особо мутирующая при этом.
                                                  И работать с ней надо как с просто табличкой.
                                                  Силы лучше вон на те терабайты потратить. Там экономия и скорость работы заметнее будут.

                                                  Чтобы тут было интересно надо увеличить размер до Гугла и их id пользователей. У них их наверно миллиардов под 10. С тенденцией на рост. И просто так в память класть все уже больно.
                                                    0
                                                    Тут есть забавная штука, эти «паспорта» в реальной жизни и в бигдате встречаются очень часто, зовутся по другому, объемы сильно другие, а сама задача звучит так же. Только цифры на несколько порядков больше.

                                                    Вот эти 130 миллионов int64 можно рассматривать как 10 массивов с int32, и уже кратный разрыв по памяти и объему, а можно как разреженный битмэп, и там уже много порядков.

                                                    Реальный кейс:
                                                    есть N категорий, есть поток данных по этим категориям, в каждом сообщении есть идентификатор(уникальный), и поле с набором категорий
                                                    скорость потока 200k rps в секунду
                                                    сервис соответственно должен формировать для каждой категории множество идентификаторов
                                                    Далее нужно иметь возможность формировать множества по разным категориям, собственно все операции со множествами.
                                                    И хочется это иметь в разрезе времени, шаг 5 минут.
                                                    Типовой идентификатор int128

                                                    По сути та же задача, только цифры немного другие.
                                                      0
                                                      Так надо формулировать сразу правильно. А не 130 миллионов с атомарной заменой одной таблички на другую раз в день.

                                                      200к рпс это прям серьезно. Аналитика по таким потокам это еще серьезнее. Из плюсов аналитика совсем простая и за короткое время.

                                                      200к рпс, 5 минут. итого 60 миллионов событий. не хватает цифры с количеством уникальных id, но не важно пусть все уникальное. Надо держать окно в которое влазят эти 60 миллионов.

                                                      Итого мапа на 60 миллионов int128 без проблем. Держим данные для окна, все типично. Все старое сбрасываем в любое хранилище по вкусу. Оно уже рассчитанно, пожато и пусть себе лежит.

                                                      Обратные индексы по категориям тоже без проблем. У нас указатели, на размер id тут уже все равно.

                                                      Базы на таком потоке в реалтайме наедятся. Пишем велосипед инмемори.

                                                      Мапа гигов 10. Каждый обратный индекс это всего лишь массив указателей. 60 миллионов int64 это всего полгига памяти. Требования вроде выполняются. Есть небольшие накладные расходы на временные метки, но это все мелочи.

                                                      Итого в типичный сервер влезет пара сотен категорий. На 5 минутном окне. Хватит?

                                                      На практике, конечно, сразу пишем шардирование. Все равно пригодится рано или поздно.

                                                      Основные данные можно по всем шардам дублировать чтобы на сеть не тратится, категории храним по разным шардам. Координатор раздает кто что из категорий записывает. Все о чем координатор не знает на отдельный шард. Можно накрутить автоматику перешардирования. На 5 минутном окне она не очень страшная. Настройка по дефолту 3 шарда. 2 для категорий пополам и третий для всего что в них не попало.

                                                      Даже с двойным резервированием выглядит не очень страшно. Железа для долговременного хранения истории уйдет заметно больше чем для обработки входящего потока данных.
                                                        0
                                                        Так о том и речь, что если бы эта задачка была с четырёхзначными цифрами вместо десяти, вы же не стали бы спорить, что битовая карта или хештаблица вполне сработали бы. Если есть определённые ожидания, то и задачи надо ставить такие, для которых эти требования будут необходимы.
                                                        0
                                                        Ну и чтоб быть честными, 9 999 999 999
                                                        размерность как раз на 10 милиардов. Это не много, у гугла на несколько порядков больше размерность id.
                                                    0
                                                    Не совсем верно. Redis не умеет Roaring Bitmaps из коробки, там честные нули. 40 мегабайт — это в Pilosa, там с битмапами всё хорошо. Но не ясно, что со стабильностью работы. Может кто-то расскажет, кто имел опыт?
                                                      0
                                                      Ну не redis, а pilosa.
                                                      По факту готовое хранилище. Хотя кстати redis тоже умеет, но не из коробки.
                                          0

                                          А чего вы память в битах мерите то, там файл со строками умещается в 1.5гБАЙТА и хеш Мапы выкинули :( можно во первых разбить по серии (первый уровень) и уже номера второй ~500мб

                                  0
                                  Пока мой комментарий проходил модерацию понял, что 10 млн это похоже опечатка в условии. На самом деле пользовательская база 10 миллиардов. Тогда статья обретает смысл, хотя я бы поэкспериментировал с вариантами хранения бинарного дерева — по опыту коллег данные такого типа хорошо ужимаются до размеров, которые можно хранить в памяти.
                                    0
                                    Ну на самом деле выбор разреженных битовых массивов под эту задачу весьма не плох, думаю бинарное дерево больше места займет.
                                    5 лет назад я делал просто сортированные массивы, по скорости таже константа, по месту 200 — 300 мегабайт, только там без внешних хранилищ.
                                      +1
                                      10 миллиардов паспортов… Недействительных. При населении планеты в 7.5 млрд.
                                      И поиск за 1 мс…
                                        0
                                        Не знаю как насчет реализации в redis, но в оригинальных либах еще и операции со множествами поддерживаются, и тоже за константное?(не помню) время. Как пример использовал это в задачках вида: есть группа от 18 до 34 лет, есть группа любителей попкорна, есть группа любителей домашнего порно, есть группа мужчин нужно получить целевую аудиторию мужчин от 18 до 34 лет, которые любят домашнее порно и попкорн.
                                        Собственно каждый субъект в группе это кука ))

                                        В итого с кластера на 3 машинах с терабайтными ssd + полтерабайтными кусками оперативы перешли на 1 машину со 128 гигами. Ну и операции из разряда запустить на ночь стали реалтайм.
                                          0

                                          Ну, если считать паспорта — у человека 30 лет есть уже два номера (действительный и прошлый), 50 лет — уже три-четыре (был период обязательной смены паспортов, не привязанный к возрасту). И это не считая утерянных, смен фамилий/имени и т.д.

                                            0
                                            Даже десять паспортов человека за сто лет не дадут и трёх миллиардов записей для РФ.
                                      0
                                      Может быть я пишу глупость, но мне кажется, алгоритм Bloom Filter так и напрашивается сюда в качестве решения задачи поиска.
                                        0
                                        1.25 Гб не такой большой объем чтобы хранить непосредственно сразу все допустимые варианты в памяти и иметь чтение и записать за O(1). И в условии про ограничения на память ничего нет.
                                          0
                                          Фильтр Блума даёт ложноположительные результаты (но не даёт ложноотрицательных) и с этим придётся что-то делать
                                            0
                                            Если множество всех серийных номеров паспортов конечное (10 млрд. всего), то есть способ построить фильтр блума без ложноположительных, перечислив их всех наперёд. Либо вот ещё подход, но я не вникал: medium.com/orbs-network/constructing-bloom-filters-without-false-positives-7aaf50b92f3b
                                              0
                                              Фильтр Блума так устроен, что для всех его элементов существует такой набор содержимого множества, который даёт ложноположительное срабатывание (если же это не так, это лишь значит, что шеш-функции выбраны неудачно и для некоторых элементов ложноположительные резальтаты уже будет давать катастрофически большое подмножество генерального множества) — если пытаться что-то хранить, что могло бы попасть в ложноположительные — то проще само множество хранить непосредственно без фильтра
                                                0
                                                Вы не стали читать статью по ссылке выше, верно?
                                                  0
                                                  Мой комментарий был про
                                                  перечислив их всех наперёд
                                                  а судя по
                                                  но я не вникал
                                                  Вы тоже не читали, верно же?

                                                  P.S. в моём комментарии выше текст «шеш-функции» следует читать как «хеш-функции», но, кто хотел, конечно же, и сам догадался
                                            0
                                            Да, всё так. Только щас уже есть более эффективные cuckoo filter и xor filter. Учитывая, что множество всех запрашиваемых серийников паспортов конечно, можно и от ложноположительных избавиться, перечислив их все наперёд. Либо вот ещё подход, как сделать фильтр блума без ложноположительных срабатываний: medium.com/orbs-network/constructing-bloom-filters-without-false-positives-7aaf50b92f3b
                                            +1

                                            Для решения задачи отлично подойдёт префиксное дерево https://ru.m.wikipedia.org/wiki/Префиксное_дерево

                                              0
                                              10 000 000 строк, каждая это 10 int8
                                              я бы сказал, что я сильно сомневаюсь, что на основе префиксного дерева получится построить более эффективное решение этой задачи чем на основе разреженных битмассивов.
                                              Я далеко не спец по алгоритмам, это скорей хобби, но было бы очень любопытно увидеть код и показатели стоимости данного алгоритма на этой задаче.

                                              Текущие лучшие решения в статье и комментариях:
                                              размер от 40 до 300 мегабайт
                                              время доступа константа
                                              количество строк кода (вместе с тривиальной веб мордой) от 400 строк кода.
                                              память и cpu смысла нет расписывать, там копейки.
                                                0
                                                Не в чистом виде: число узлов превысит число паспортов.

                                                У меня получился гибрид: первые 8 символов — в префиксном дереве, остальные 2 — в битовых массивах в листьях.

                                                normalize.rb
                                                #!/bin/ruby
                                                
                                                STDERR.puts Time.now
                                                
                                                b = []
                                                
                                                while s = gets
                                                    s.gsub! /\D/, ''
                                                    b << s.to_i if s.size == 10
                                                end
                                                
                                                STDERR.puts Time.now
                                                
                                                b.sort!
                                                
                                                STDERR.puts Time.now
                                                
                                                b.each do | i |
                                                    print '%010d' % [i]
                                                end
                                                
                                                STDERR.puts Time.now
                                                $ ./normalize.rb < list_of_expired_passports.csv > normalized.txt
                                                2021-02-06 03:37:34 +0300
                                                2021-02-06 03:46:05 +0300
                                                2021-02-06 03:47:08 +0300
                                                2021-02-06 03:49:32 +0300
                                                build_tree.rb
                                                #!/bin/ruby
                                                
                                                b = File.read 'normalized.txt'
                                                
                                                N = Struct.new :digit, :first_child, :next_sibling
                                                T = N.new
                                                count = 0
                                                
                                                Insert = -> t, c do
                                                    if t.first_child == nil
                                                        count += 1
                                                        return (t.first_child = N.new c)
                                                    end
                                                    t = t.first_child
                                                    while t.digit != c && t.next_sibling != nil
                                                        t = t.next_sibling
                                                    end
                                                    return (t.digit == c) ? t : (count += 1; t.next_sibling = N.new c)
                                                end
                                                
                                                STDERR.puts Time.now
                                                
                                                (0...b.size).step 10 do | i |
                                                    t = T
                                                    b[i, 8].each_char do | c |
                                                        t = Insert.(t, c)
                                                    end
                                                    puts count if i % 1e8.to_i == 0
                                                end
                                                
                                                STDERR.puts Time.now
                                                
                                                puts count
                                                $ ./build_tree.rb
                                                2021-02-06 04:01:04 +0300
                                                2021-02-06 04:49:37 +0300
                                                3106435
                                                Промежуточная C-структура:
                                                typedef struct Tmp {
                                                    char digit;
                                                    Tmp *first_child;
                                                    Tmp *next_sibling;
                                                    uint8_t[16]
                                                } Tmp;
                                                Компактная финальная:
                                                typedef struct Node {
                                                    uint8_t[16]; // 100 bitarray +
                                                                 //   4 digit +
                                                                 //   1 is_sibling_exists_flag +
                                                                 //  23 index_in_Node_array
                                                } Node;

                                                Над преобразованием Tmp -> Node придётся подумать самостоятельно.

                                                3_106_435 * sizeof(Node) == 49_702_960 байт
                                                  0
                                                  Над преобразованием Tmp -> Node придётся подумать самостоятельно.
                                                  github.com/alantudyk/Trie
                                                  0
                                                  Да, причем его построение наиболее оптимально, на мой взгляд, следующий образом:
                                                  1) сортируются по числу вхождений серии
                                                  2) по ним строится дерево и маппинг битов на серии
                                                  3) по номерам создаем массив и в нем элементом будет битовая маска с записями всех серий с таким же номером
                                                  4) итого массив из 1000000 элементов
                                                  И уже по нему производим поиск.

                                                  Если не ошибаюсь, то в исходном файле есть записи хотя бы с одной серией для всех номеров от 000000 до 999999
                                                  0
                                                  Можете подсказать, что это за значения O(1)?
                                                  0
                                                  Либо я неверно понял условие, либо задача вполне решается следующим образом:

                                                  -Принимаем формат паспорта за YYYY NNNNNN. При этом YYYY — это не абы что, а цифры примерно соответствующие году выдачи, то есть можно вычесть, скажем, 2000 и хранить только оставшиеся 6 бит (от 2000 до 2063 года). NNNNNN не сократить, это 20 бит.

                                                  -Итого имеем 26 бит, однозначно идентифицирующих документ. Для хранения всех паспортов одного года требуется 2^20 бит то есть 128 Кбайт. Таких массивов у нас 64 (по годам), то есть всего 64 * 128 Кбайт = 8 Мегабайт (это наши итоговые требования по памяти).

                                                  -Однажды делаем предварительный проход по базе паспортов и выставляем соответствующие биты.

                                                  -Приходит запрос. Вычисляем смещение умножением двух чисел, читаем один бит — получаем результат. На всё про всё вряд ли и микросекунда уйдёт.

                                                  Может я всё-таки неверно понял условие?
                                                    0
                                                    Про серию вы ошибаетесь.
                                                    Год там и, правда, некоторым образом прослеживается — посмотрел на нескольких паспортах: последние две цифры серии соответствуют году выдачи, либо на единицу меньше или больше.
                                                    Но вот первые две цифры серии скорей всего связаны с регионом выдачи.
                                                    В разных регионах они разные, но при этом совпадают, если паспорта выданы в одном регионе.
                                                      0
                                                      В самом деле, две первые — регион. Две вторые — примерно год (± 1). Значит придётся ещё 7 бит заложить под регион, а это увеличивает требования по памяти до 1 Гб.
                                                        0

                                                        Нет, у меня первые две цифры — не регион.

                                                          0
                                                          По-моему, разбор формата серий паспортов был на Хабре.
                                                          Серия характеризует бланк паспорта, год создания бланка и регион, к которому бланк относится.
                                                          Соответственно, если несколько лет бланк дожидался выдачи — год в серии не совпадает.
                                                          Если в одном регионе закончились бланки, их подвезли из другого — регион в серии не совпадает.
                                                          И да, регионы закодированы иначе, чем на автомобильных номерах и тому подобном.
                                                            0

                                                            Да, вот здесь подробности https://habr.com/post/478538/

                                                              0
                                                              Когда заканчивается бланки, если это известно заранее, «заимствуют» не из других регионов, а «из будущего», из других же регионов заимствуют для оперативного разрешения нехватки. Если верить статье и если я правильно понял её текст, «залежаться» бланк может года на 3, а «телепортироваться в прошлое» лет на 5
                                                            0

                                                            Первые две — это первые две цифры кода ОКАТО

                                                        +3
                                                        За час наговнокодить базу в Редисе и апишку к ней вообще не вариант?
                                                          0

                                                          Такая апишка не вернёт ответ за 1мс. Можете проверить.

                                                            +1
                                                            Я естесвенно проверил перед тем как писать.
                                                            От 1 от 2 миллисекунд. cli. Из кода значит можно быстрее и с гарантией в одну уложится.
                                                            bugm@bugmpk:~$ time redis-cli get var
                                                            «1»

                                                            real 0m0.001s
                                                            user 0m0.001s
                                                            sys 0m0.000s
                                                              –1
                                                              Да, я не спорю, что redis вполне способен отдать ответ за 1-2мс.
                                                              Но вы же предложили еще над redis апишку сделать.
                                                              Так вот на на сетевой проброс запроса из вашей апишки в redis вы потеряете еще ~1-2мс и в итоге не уложитесь в условия задачи.
                                                                0
                                                                С такими таймингами ничего никуда не пробрасываем. Все на одном хосте локально разворачиваем.
                                                                Какое условие, такое и решение.
                                                          0

                                                          Отсортировать, записать в файл и искать бинарным поиском. Почему нет ?

                                                            0
                                                            Мой первый комент, 2 разных языка, под капотом просто отсортированные массивы.
                                                            Время доступа константа, размер массивов на тот момент было около 300 мегов ( тогда список не валидных паспортов был всего 90 миллионов).
                                                            10 знаков это 10 массивов с int32 внутри.
                                                            Без битмэпов, тогда либ не было готовых.
                                                            Так что да ))
                                                            Но если бы писал сейчас реализовывал бы тоже на разреженных битмэпах, оно и эффективно да и алгоритм красивый )) Да и либы почти на всех языках есть, они уже даже способ хранения стандартизировали. В статье используется redis, там эта реализация битмэпов под капотом.
                                                            +1
                                                            10-гигабайтный битмап в оперативной памяти. Очень неэкономно и очень быстро.
                                                              +1
                                                              Странный вопрос, но как докер улучшит итоговый результат и по каким критериям?
                                                                0
                                                                Удобством использования результата.
                                                                +2
                                                                На днях тоже наткнулся на это тестовое задание. Оно было менее лаконичное.
                                                                Более полный текст задания
                                                                **Задача:** есть приложение с базой клиентов, порядка 10 млн. У всех заполнены данные паспортов, которые могут просрочиться, быть утеряны и т.д. В связи с этим нужна система для проверки валидности этих паспортов на основе данных ФМС.

                                                                Задание по сути — создание микросервиса. Не библиотеки, а именно самостоятельного сервиса.

                                                                **Требования:** время ответа на запрос 1ms, uptime 99%. Больше требований нет, остальное на своё усмотрение.

                                                                Если мы с автором поста решали одно и то же задание, то, на мой взгляд, это решение не полное решение задачи.
                                                                В тексте указано, что необходим самостоятельный сервис, который будет отвечать за 1мс. То есть этим сервисом предполагается пользоваться не только в рамках тех 10 млн пользователей. Иначе можно было бы распаковать файл, положить в хэш таблицу, пробежаться по своей базе, сделать проверки и profit.

                                                                Чтобы сервис отдавал ответ за 1мс, необходимо не только алгоритм определения валидности продумать, но и остальные расходы. В первую очередь сеть. Если вы развернёте на локальной машине почти любой веб сервер, то самый простой GET запрос с этой же машины будет выполняться больше 1мс. Это связано с тем, что мы неизбежно будем тратить время на тройное рукопожатие. Тем более в предложенном решении предлагается еще и ходить в редис, что по той же причине только удвоит затраты на сеть.
                                                                На мой взгляд, в задаче необходимо отказаться от промежуточного веб сервера, реализовав обработку подключений внутри своего сервиса, использовать персистентное HTTP подключение, а данные хранить в памяти процесса. При этом я согласен с автором в части структуры хранения данных.
                                                                  0
                                                                  Если мы с автором поста решали одно и то же задание, то, на мой взгляд, это решение не полное решение задачи.

                                                                  +1, из текста статьи:


                                                                  Однажды, в качестве тестового задания на позицию PHP разработчика была предложена задача реализации сервиса проверки номеров паспортов граждан РФ на предмет нахождения в списке недействительных.

                                                                  А в итоге была реализована библиотека, которая общается с редисом.


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

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


                                                                  P.S. В статье ничего не написано про то, отдаёт ли реализация ответ за 1 ms, а это одно из основных требований.


                                                                  P.P.S. Про экономию памяти было интересно :)

                                                                    0
                                                                    Имхо, http очень дорого в данном случае, и стоит использовать соединение на сокетах и какой-нибудь лёгкий бинарный протокол.

                                                                    Главное в прод такое не тащить. Пока у вас не онлайн игры и прочее подобное с требованием к миллисекундам надо использовать только http.

                                                                    Стандартность, удобность и фичастость окупится многократно при эксплуатации.
                                                                      0
                                                                      Главное в прод такое не тащить. Пока у вас не онлайн игры и прочее подобное с требованием к миллисекундам надо использовать только http.

                                                                      Я писал про данный случай — где требование 1мс и вроде речь шла про язык php.

                                                                        0
                                                                        Лучше такое писать. А потом такое в проде видишь…

                                                                        Надо переложить небольшой джейсон с любой приемлимой скоростью, а внутри чуть-ли не ассемблер. Ведь так же быстрее.

                                                                        Или как тут. Надо хранить в памяти сервера (Одного сервера, не 100, не 1000 серверов. Может 2-3 для отказоустойчивости) что-то небольшое. В гигабайт влезет, если нормально сделать. Нет, надо применить битовую магию и ужать до 100 мегабайт. И в итоге код проще выкинуть и написать заново чем добавить новую нужную фичу.
                                                                      +1
                                                                      Так ведь и статья про мегабайты, а не про миллисекунды. О них как-нибудь в другой раз (спойлер: keep-alive и persistent connection творят чудеса).
                                                                      Но даже в таком виде оно может 1мс.
                                                                    0
                                                                    Всё верно. Но это тема для отдельной статьи, первым комментарием к которой будет: «На Go это можно сделать проще/быстрее».

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

                                                                  Самое читаемое