Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Какое-то время назад появилась возможность уделить внимание языку Go и удачно на глаза попалась публикация «Паспортный контроль, или Как сжать полтора гигабайта до 42 мегабайт» . В статье кратко, но информативно, рассказывается о тестовой задаче по разработке сервиса проверки номеров российских паспортов на предмет наличия их в списке недействительных паспортов. Среди основных требований к реализации – это скорость проверки и доступность сервиса.
После прочтения статьи для себя решил, что именно на этой практической задаче можно построить свое обучение Go. Действительно, задача c проверкой недействительных паспортов, хоть и избитая, но интересная, а раз уж требования по производительности здесь в приоритете, то реализация на Go здесь будет вполне уместна.
Кроме того, в упомянутой выше статье затронуты вопросы эффективной, с точки зрения памяти, организации битовых массивов (bitmap). И эта тема достаточно актуальна и востребована в разных прикладных решениях, например, в виде bitmap-индексов для СУБД.
В итоге следующее: есть желание посмотреть на новый для себя язык Go, есть интересная проблематика в виде организации и использования bitmap (естественно на Go), есть практическая задача, на которой эти две цели можно отработать. Если интересно, то вперед.
Что в качестве исходных данных
Сама задача проверки паспортов построена вокруг первичного списка недействительных паспортов, представленного на сайте МВД РФ, там же можно сделать ручную проверку номера паспорта. С сайта можно скачать весь список в виде запакованного архива размером 460 МБ, распакованном же виде получаем список размером около 1.5 ГБ, представленном в виде единственного CSV-файл c двумя колонками: серия и номер паспорта.
На сегодняшний день в этом CSV-файле около 132 миллионов номеров паспортов. Но файл также содержит ошибочные номера, которые нельзя идентифицировать однозначно, например, не указаны все 4 цифры для серии или все 6 цифр для номера, могут присутствовать буквенные серии.
Так как на сегодня действительными считаются только российские паспорта с 4-мя цифрами для серии и 6-ю цифрами для номера, то все остальные данные, не вписывающиеся в этот формат, будем рассматривать как недействительные. Не будем принимать во внимание дополнительный контроль по формату серии, код региона РФ, год выдачи, т.к. не уверен, что это еще в силе.
Что будем релизовывать
Для более интенсивного изучения Go решил, что будем делать сервис, реализующий три варианта организации хранения данных списка недействительных паспортов.
Вариант первый – прямой и простой
Будем хранить данные в памяти в виде простого разряженного битового массива. Получается большая, ну или относительно большая битовая матрица. В качестве строк у этой матрицы будут серии паспортов, в качестве столбцов – номера паспортов. Таким образом, строк у нас будет 10 000 (от 0 до 9999), а столбцов 1 000 000 (от 0 до 999998, т.к. нумерация самих номеров идет с 000001). Фактически, имеем массив массивов (или срезы срезов, в терминологии Gо), т.е. будет 10 000 bitmap, каждый такой bitmap реализуется в виде среза из 15 625 элементов uint64.
Почему 15 625?
А потому что, 1 000 000 битов умещаются в 125 000 байт, а те, в свою очередь, в 15 625 слов (для архитектуры x86-64)
В худшем случае, памяти здесь потребуется много, а точнее примерно 1.25 ГБ, для размещения необходимых 10 000 bitmap. Будем реализовывать этот вариант в расчете на скорость доступа, т.к. теоретически скорость поиска для любого элемента нашей битовой матрицы должна быть константой. В реальности у этого варианта есть пространство для оптимизации по памяти – сейчас не все серии паспортов задействованы, поэтому вместо инициализации 10 000 bitmap можем ограничиться созданием немногим более 3 300 (именно столько уникальных серий паспортов сейчас в списке недействительных).
Вариант второй – рациональный
Второй вариант концептуально не отличается от первого – так же имеем битовую матрицу, но с важным отличием, что каждый bitmap будет с компрессией, и на эту компрессию возлагаем большие надежды. Например, если в серии всего только один номер попал в список недействительных, то в первом варианте для всей серии выделяется срез на всю необходимую длину, т.е.15 625 элементов сразу для всех 1 000 000 бит. И из этого миллиона бит только один будет выставлен в единицу, а все остальные будут нулями. Очевидно, что здесь присутствует большая избыточность.
Реализацию сжатия bitmap возьмем готовую – это будет roaring bitmap.
Вариант третий – искушённый
Если в первом и втором варианте реализация хранилища собственная, и эта реализация решает задачу только задачу организации и работы с битовой матрицы и не более, то третий вариант предполагает использования готового решения. И в качества такого готового решения остановим выбор на Pilosa.
Pilosa – это система для создания индексов для большого объема структурированных данных. Называть Pilosa базой данных, в привычном понимании, будет не корректно. Цели и задачи этой системы – именно создание индекса(ов) для управления и доступа к данным.
Этот вариант, применительно к выбранной задаче, немного надуманный и избыточный, т.к. размер данных задачи явно не дотягивает до оправданного использования Pilosa. С другой стороны, сама структура данных списка недействительных паспортов очень удачно ложится на архитектуру Pilosa, т.к. основной идеей архитектуры как раз являются бинарные матрицы (binary matrices).
Выбор пал на Pilosa также по причине, что сама система написана Go, а среди небольшого количества «родных» библиотек подключения к ней есть библиотека для Go, что логично. Поэтому при необходимости можно будет «заглянуть под капот». Здесь больше интересно посмотреть на Pilosa.
В независимости от варианта организации хранилища, основная функциональность разрабатываемого приложения будет следующая:
Создание хранилище списка недействительных паспортов. Хранилище для первого и второго вариантов реализации - это внутренняя структура в памяти, третий вариант – это внешнее хранилище в Pilosa.
Уметь принимать http запросы. Для запроса GET серия и номер паспорта указываются в параметрах запроса, если POST, то данные паспортов идут в теле запроса в виде json. Выдавать ответы в зависимости от типов поступивших запросов.
Автоматически и с заданной регулярностью выкачивать обновленные списки недействительных паспортов с сайта МВД РФ и выполнять обновление данных.
Для возможности управления вынесем настройки приложения в отдельный конфигурационный файл, определяющий вариант реализации хранилища, регулярность обновления и т.д.
Дополнительно к функциональным требованиям, определяем, что приложение функционирует как независимый сервис, поэтому завернем все в Docker контейнер.
Собственно, с такими вводными и приступаем к реализации. Но сам процесс реализации остается за рамками статьи.
Что получилось
Сначала немного лирики. С одной стороны, Go простой и не перегруженный «синтаксическим сахаром» язык, а с другой стороны, привычные концепции ООП или отсутствуют или реализованы несколько иным способом, например, отличия в реализации интерфейсов. Ясно, что за две недели идеологию нового языка программирования трудно прочувствовать достаточно глубоко, но субъективно показалось, что порог вхождения в Go выше среднего. Приятное удовольствие доставила простота реализации многозадачности на Go или, например, факт того, что один и тот же код приложения работает под Linux, Mac OS и Windows, после компиляции на соответствующей платформе конечно. Но иногда раздражали сильные требования статической типизации, например, без явного приведения нельзя uint16 передать в uint64.
По мере продвижения в изучении Go, новые полученные знания приводили к тому, что как архитектура приложения, так и структура самого кода подвергалась ревизии на живую несколько раз.
Весь код приложения, скрипты с примерами использования, и небольшое описание выложены по этой ссылке на GitHub. Так как одной из основных целей была задача познакомиться с Go, то использовались только родные библиотеки Go из «коробки». И только для roaring bitmap и для подключения Pilosa использовались внешние пакеты, со своими зависимостями.
После компиляции и запуска приложения на выбранной платформе, в зависимости от установленных настроек, создается хранилище списка недействительных паспортов. Если файла с первичными данными нет, а это, как правильно, при первом запуске, то приложения самостоятельно выкачивает файл с сайта МВД РФ и импортирует данные в хранилище. После импорта данных, запускается веб-сервер и API сервиса готово обрабатывать запросы. Отдельной горутиной реализована задача автоматического обновления дынных –приложение с заданной регулярностью проверяет необходимость обновления, и если файл на сайте МВД РФ изменился, то он скачивается и запускается обновление. хранилища. Само обновление выполняется на действующем хранилище, т.е. оно не останавливается, не создается никакой временной копии. Другими словами, каждое обновление списка применяется на предыдущую версию списка.
Как выглядит API
Вот как выглядит, например, GET запрос
http://localhost:8080/passport?series=8003&number=011384
Такой запрос выполняет проверку по единственному паспорту и отправляет ответ в виде html или в виде json в теле ответа, в зависимости от того, есть ли заголовок ContentType со значением "application/json" в исходном запросе.
Вот так выглядит тело ответа для варианта "application/json":
[{
"series": "8003",
"number": "011384",
"status": "non-valid"
}]Поле status может принимать значение “valid” или “non-valid”
Примерно такое же наполнение json будет в теле запроса POST метода, но без поля status:
для вызова http://localhost:8080/passport
[
{
"series": "4050",
"number": "039589"
},
{
"series": "5203",
"number": "257719"
},
{
"series": "5000",
"number": "347024"
},
{
"series": "2507",
"number": "857721"
},
{
"series": "2507" ,
"number": "857728"
}
]В качестве ответа будет такой же список, но с добавленным полем status. Ограничение на кол-во номеров паспортов, одновременно запрашиваемых в одном запросе, установлено в конфигурационном файле (по умолчанию 100) номеров
Тестировалось все на ноутбуке i7 7-го поколения с 16 Gb памяти, Windows Pro с WSL2(Windows Subsystem for Linux), а также с использованием Docker Desktop For Windows. Надо принимать во внимание что и сам сервис, и тестирующие скрипты запускались на одной машине, хоть и в разных окружениях: в основном сервис под Windows, а тесты под WSL с помощью Сurl и ApacheBench с 1000-ю запросами, разделенных на 100 конкурентных потоков. Да, можно было с и помощью Go сделать бенчмарки (benchmark), но решил сделать так, как сделал.
Оценивались следующие основные показатели:
скорость импорта первичных данных из файла (предварительно выгруженного с сайта МВД);
объем необходимой памяти для хранения данных;
средняя скорость доступа к сервису при запросе с одним номером паспорта.
Результаты с хранилищем в виде разряженного bitmap
Импорт 1.5 ГБ данных исходного списка с проверкой корректности формата в хранилище сервиса выполнилась в среднем 30 секунд, что очень хорошо. Еще раз отмечу, что это скорость импорта из файла во хранилище приложения, и сам файл уже скачан.
Как и ожидалось, этот вариант организации хранилища достаточно «жадный» на память, но вместе 1.25 Gb (верхняя граница оценки), хранилище потребовало около 440 МБ. Где-то такие цифры и ожидались, т.к. всего около трети диапазона допустимых серий паспортов и присутствуют в списке недействительных. В принципе, неплохой результат.
Если исходить из общего времени выполнения и количество запросов(1000 запросов в 100 потоках), то время одного запроса, а это второй параметр «Time per request» со значением 0.1 ms выглядит, на мой взгляд, очень достойно.
Таким образом, здесь имеем:
30 секунд на загрузку и инициализацию хранилища;
440 МБ на само хранилище;
среднее время доступа в 0.10 ms.
Но надо понимать, что здесь отсутствуют накладные расходы на передачу по сети.
Результаты с хранилищем в виде roaring bitmap
В среднем загрузка данных выполнялась около 1.5 минут, что объясняется необходимостью дополнительной работой с сжатыми bitmap. А вот само хранилище потребовало 44 МБ(!) памяти, и это действительно, на мой взгляд, поразительный результат. Среднее время доступа 0.18ms, медленнее, чем первый вариант, и это объяснимо, но тоже очень достойно.
Результат тестирования по скорости доступа roaring bitmap:
В итоге, для варианта bitmap с компрессией имеем:
90секунд на загрузку и инициализацию хранилища;
44 МБ на само хранилище;
среднее время доступа в 0.18 ms.
Размер необходимой памяти для организации хранилища перекрывает с лихвой и время на импорт и даже на скорость доступа. В принципе, можно было побороться за скорость, т.к. в текущей реализации приложения используется стандартная версия roaring bitmap, а можно было бы посмотреть 64-х битную реализацию или версию на основе языка C (Croaring).
Результаты с внешним хранилищем в Pilosa
Pilosa относительно новая система, но быстро набирающая популярность. И как у любого нового продукта, есть свои проблемы. Например, нет версии Pilosa под Windows, поэтому первое, что приходит на ум, это взять готовый контейнер. И здесь пришлось столкнуться с неожиданным поведением стандартных процедур импорта данных, и для выяснения причин которого пришлось «заглянуть под капот». В общем, пока что Pilosa в docker-контейнере под Windows – не самая удачная идея.
Так как сделать импорт файла с первого подхода средствами Pilosa не получилось, то решил загружать данные непосредственно построчно, т.е. номер за номером из файла.
Для Pilosa это оказалось дорогим удовольствием – в среднем 1 секунда на 1000 номеров паспортов. С такими результатами думать о загрузке 132 млн записей даже и не надо начинать.
Поэтому дальше работал с Pilosa непосредственно установленной в WSL2, где проблем никаких не встретил.
В этом случае импорт всего файла стандартными средствами Pilosa занимал около 4 минут С учетом того, что это полноценная система организации индекса с большими возможностями, и в процессе импорта, у этой системы есть определенные накладные расходы, то на мой взгляд, это неплохой результат, но важно отметить, что этот файл для импорта требует предварительной подготовки, т.к. импорт крайне чувствителен к чистоте данных.
Не замерял сколько именно памяти Pilosa требует для хранения загруженных данных списка паспортов, но подозреваю, что не существенно больше чем, во втором варианте, т.к. сама Pilosa для хранения bitmap использует ту же самую технологию roaring bitmap.
По скорости доступа здесь существенное отставание от первых двух вариантов – до 0.5 ms в среднем для простого запроса с одним номером паспорта.
Для варианта создания хранилища в Pilosa:
240 загрузку и инициализацию хранилища;
не данных;
среднее время доступа в 0.5 ms.
Конечно, все преимущество Pilosa проявится, как только объем данных, с которыми надо будет работать, будет на порядок больше чем в этой задаче или же сложность структуры организации данных будет отличаться от тривиальных номеров паспортов. Например, если вдруг понадобится хранить и обрабатывать запросы с временными метками(timestamp), что хорошо умеет делать Pilosa.
Заключение
Конечно, делать заключение по первому и одному единственному написанному на Go приложению будет самоуверенно. Но первые впечатления от языка вполне оправдали ожидания. Писать приложения можно достаточно быстро, скорость работы скомпилированного кода впечатляющая. Да и сама скорость компиляции очень быстрая – Go можно просто использовать как скриптовый язык.
Но надо подружиться или просто принять как данность идеологию языка, где-то перестроить свои привычные шаблоны и концепции, например, что ООП это не про Go.
Кроме самого языка еще хотелось бы отдельно отметить технологию roaring bitmap за впечатляющие результаты сжатия и скорости доступа. Если вдруг появится задача с bitmap или задача может быть сведена к bitmap, то обязательно исследуйте вопрос о возможности применения roaring bitmap.
