21.08.2021 02:09
skivsoft 30 6600 Источник

Постановка задачи

Имеется ежедневно обновляемый архив со списком недействительных российских паспортов в формате csv: http://сервисы.гувм.мвд.рф/info-service.htm?sid=2000. Размер архива list_of_expired_passports.csv.bz2 — 506 MB, размер распакованного csv-файла — 1,6 GB.

Требуется реализовать вспомогательный REST-сервис, для использования внутри компании, со следующими возможностями:

  • Проверка наличия паспорта (Серия + Номер) в списке недействительных паспортов.

  • Возможность обновления данных без прерывания работы сервиса.

Исследуем содержимое csv-файла

Исходный csv-файл содержит более 137 148 000 записей, большинство из которых записаны в одинаковом формате ^\d{4},\d{6}$, но также встречаются и буквенные серии (~10000 записей).

PASSP_SERIES,PASSP_NUMBER
6004,270563
6004,270579
6004,270611
...
ХЕР6,37039
ХИБА,601006
ХУЕР,685239
ЯГ01,3332

Возможно ли сжать данный csv-файл, чтобы было приемлемо работать с ним в памяти?

Да! Используя то, что большинство записей представлены в числовом виде, а также что для задачи проверки наличия паспорта в списке не имеет значения, в каком порядке расположены строки, данный csv-файл можно запаковать значительно лучше, чем это делают популярные архиваторы. А точнее – до 42 MB, что в 38 раз компактнее исходного csv-файла и в 11 раз компактнее csv-файла сжатого bzip2.

Данные в таблице на 16.08.2021.

Формат

Размер в байтах

list_of_expired_passports.csv.bz2

506,340,184

list_of_expired_passports.csv

1,649,037,938

list_of_expired_passports.csv.pdata

42,876,427

Предлагаемый алгоритм сжатия .pdata (passport data)

Хочу сразу оговориться, что этот алгоритм не является универсальным и применим только в рамках данной задачи сжатия csv-файла, в котором много записей паспортов представлено в числовом виде.

Возьмем для примера первую запись из csv-файла: 6004,270563.

  1. Удалим запятую между серией и номером паспорта.

  2. Далее разобьем строку на 2 части по 7 и 3 символа соответственно и представим в виде чисел: 6004270 и 563.

  3. Первое число будем хранить в формате Int32 и использовать в качестве ключа Dictionary<int, byte[]> для фильтра чисел у которых совпадают первые 7 цифр.

  4. Второе 3-значное число может принимать значения от 0 до 999. Однако нам не надо сохранять данное число целиком, достаточно знать есть ли оно в файле или нет. Поэтому все числа от 0 до 999 будем кодировать массивом из 1000 бит, что соответствует массиву из 125 байт.

Реализация алгоритма сжатия

PassportDataStorage.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace FileFormat.PassportData
{
    public class PassportDataStorage
    {
        private const int PART1_LENGTH = 7;
        private const int PART2_LENGTH = 3;
        public const int PART2_NUM_VALUES = 1000;

        private readonly IBitMatrix _numbers;
        private readonly ISet<string> _strings;

        public PassportDataStorage()
        {
            _numbers = new BitMatrix(PART2_NUM_VALUES);
            _strings = new HashSet<string>();
        }

        public PassportDataStorage(IBitMatrix numbers, IEnumerable<string> strings)
        {
            _numbers = numbers;
            _strings = new HashSet<string>(strings);
        }
        
        public string Header { get; set; }

        public ISet<string> Strings => _strings;

        public IBitMatrix Numbers => _numbers;
        
        public void Add(string value)
        {
            if (string.IsNullOrEmpty(value))
            {
                return;
            }

            if (IsOnlyNumbers(value))
            {
                var (row, column) = SplitNumbersValue(value);
                _numbers[row, column] = true;
            }
            else
            {
                _strings.Add(value);
            }
        }

        public bool Contains(string value)
        {
            if (string.IsNullOrEmpty(value))
            {
                throw new ArgumentNullException(nameof(value));
            }

            bool result;
            if (IsOnlyNumbers(value))
            {
                var (row, column) = SplitNumbersValue(value);
                result = _numbers[row, column];
            }
            else
            {
                result = _strings.Contains(value);
            }

            return result;
        }

        private bool IsOnlyNumbers(string value)
        {
            if (value.Length == 11 && value[4] == ',')
            {
                var numbers = value.Substring(0, 4) + value.Substring(5, 6);
                return numbers.All(char.IsDigit);
            }

            return false;
        }

        private (int, int) SplitNumbersValue(string value)
        {
            var onlyNumbers = value.Substring(0, 4) + value.Substring(5, 6);
            var part1 = onlyNumbers.Substring(0, PART1_LENGTH);
            var part2 = onlyNumbers.Substring(PART1_LENGTH, PART2_LENGTH);
            return (int.Parse(part1), int.Parse(part2));
        }
    }
}

protobuf-описание формата файла .pdata (passportdata.proto)

syntax = "proto3";

message PassportDataMessage
{
    string csv_header = 1;
    repeated NumbersMap numbers_only_map = 2;
    repeated string other_lines = 3;
}

message NumbersMap
{
    int32 seven_digits_key = 1;
    bytes three_digits_bits_value = 2;
}

Решение исходной задачи

Идея решения исходной задачи — держать сжатые данные в памяти в объекте PassportDataStorage. Обновление данных происходит по расписанию 1 раз в сутки. Мое решение представлено в виде docker-контейнера на Docker Hub. Реализовано на .NET Core, исходники доступны на GitHub.

Запуск сервиса локально

  1. docker pull skivsoft/expired-passport-checker

  2. docker run -it --rm -p 8000:80 --name expiredpassportchecker skivsoft/expired-passport-checker

  3. Окрываем Swager UI http://localhost:8000/swagger/

После старта контейнера происходит следующее:

  • начальное скачивание архива bzip2

  • распаковка csv-файла из bzip2 архива

  • конвертирование csv-файла в сжатый формат PassportData и сохранение его в памяти

Последующие обновления запускаются по расписанию, которое задается параметром CronSchedule в appsettings.json.

Лог запуска сервиса

UPD: 21.08.2021

[23:44:05 INF] Step 1 of 4: DownloadBzip2
[23:44:05 INF] Downloading file https://проверки.гувм.мвд.рф/upload/expired-passports/list_of_expired_passports.csv.bz2
[██████████████████████████████████████████████████] 00:00:00
[23:47:17 INF] Downloaded 506.64 MB (506639004 bytes) 2.64 MB/s
[23:47:17 INF] Elapsed time: 00:03:12.2394834
[23:47:17 INF] --------------------------------------------------------------------------------
[23:47:17 INF] Step 2 of 4: UnpackFromBzip2
[23:47:17 INF] Unpacking list_of_expired_passports.csv.bz2 into list_of_expired_passports.csv
[23:48:52 INF] Unpacked 1,650.19 MB (1650187286 bytes)
[23:48:52 INF] Elapsed time: 00:01:34.3357428
[23:48:52 INF] --------------------------------------------------------------------------------
[23:48:52 INF] Step 3 of 4: PackCsvToPassportData
[23:48:52 INF] Reading and compressing list_of_expired_passports.csv
[23:49:44 INF] Number of processed records: 137514593
[23:49:44 INF] Number of lines with letters: 10094
[23:49:44 INF] Elapsed time: 00:00:52.2790392
[23:49:44 INF] --------------------------------------------------------------------------------
[23:49:44 INF] Step 4 of 4: SavePassportData
[23:49:44 INF] Packed passport data saved into list_of_expired_passports.csv.pdata (40.15 MB)
[23:49:44 INF] Elapsed time: 00:00:00.2261993
[23:49:44 INF] --------------------------------------------------------------------------------
[23:49:44 INF] Total elapsed time: 00:05:39.0804647
[23:49:44 INF] --------------------------------------------------------------------------------

Ссылки

Комментарии (30)


  1. RetroStyle
    21.08.2021 02:25
    #23394794
    +3

    Что-то линк на GH не работает.

    Хотелось бы узнать, как реализовано требование "возможности обновления данных без прерывания работы сервиса".


    1. skivsoft Автор
      21.08.2021 22:12
      #23397412

      Так как данные хранятся в памяти, обновление не требует прерывания работы сервиса.


  1. Firsto
    21.08.2021 03:10
    #23394820
    +3

    Популярная задача однако https://habr.com/ru/post/538358/


    1. Stecenko
      21.08.2021 08:20
      #23395034
      +2

      В копилочку:
      habr.com/ru/post/307568
      habr.com/ru/post/547350


    1. skivsoft Автор
      21.08.2021 22:31
      #23397460
      +1

      Познавательно. Дополнил алгоритм оптимизацией из этой статьи:

      Длина массива будет зависеть от максимального номера в серии. Другими словами, если в серии 3382 встречается только один паспорт с номером 000032, то для всей серии потребуется 4 байта.

      В итоге сжатие улучшилось на 10%.


  1. garex
    21.08.2021 08:00
    #23395012
    +2

    Письмо на Балабановскую спичечную фабрику:

    «Я 11 лет считаю спички у вас в коробках - их то 59, то 60, а иногда и 58. Вы там сумасшедшие что ли все???»

    А в чём выгоды подобного решения? Какой смысл экономить на спичках? Просто в базу csv-шку залить и читать оттуда запретили? Этот наносервис один? Инстанс базы стоит миллион?

    С т.з. абстрактной конечно интересно. И даже м.б. в других местах может пригодиться, но вот под эту конкретную задачу гложат сомненья.


    1. mihteh
      21.08.2021 10:42
      #23395352

      Так и есть, мы в БД у себя положили и проблем с этим местом вообще никаких.


    1. SpiderEkb
      21.08.2021 17:56
      #23396706
      +1

      Да, тут просится БД с загрузкой в нее данных при их поступлении.

      Для поиска лучше иметь "нормированное" поле sernum - серия+номер без пробелов.

      У нас много таких таблиц. Причем, в общем случае - ДУЛ (документ, удостоверяющий личность). Там не только паспорта могут быть. И содержится там тип ДУЛ, серия, номер, нормализованый номер.

      А таблиц много - ДУЛы клиентов, ДУЛы подозреваемых в экстримизме, пособничестве терроризму, распостранении оружия массового уничтожения (эти списки тоже извне приходят и регулярно обрабатываются, раскладываются по базе с последующей проверкой всех клиентов на совпадения по разным параметрам).


      1. SpiderEkb
        21.08.2021 19:08
        #23396906

        [зануда mode]

        И если докапываться до терминологии, то у паспорта РФ нет серии. Есть "номер бланка паспорта" в формате NN NN NNNNNN.

        А "серия паспорта" - это наследие паспортов СССР. Там да - серия в формате две римских цифры - пробел - две буквы кирилицы и номер в формате NNNNNN

        [/зануда mode]


        1. Gengenid
          22.08.2021 07:28
          #23398190

          Нет, первые четыре цифры это именно серия бланка. См положение о паспорте РФ


          1. SpiderEkb
            22.08.2021 07:33
            #23398194

            Да, был неправ. Спасибо.


    1. skivsoft Автор
      21.08.2021 22:44
      #23397530

      Не пробовал решение с базой, но могу предположить, что в моем варианте обновление данных будет работать быстрее. Учтите что данные могут как добавляться в csv так и удаляться из него. Исходный серивис имеет возможность сообщить об ошибке с внесением последующих корректировок. Таким образом для бд надо предусмотреть синхронизацию данных. В моем варианте этого не требуется.


      1. garex
        22.08.2021 07:35
        #23398200
        +1

        Если нужен зеро-даунтайм, то просто импортите в таблицу паспорта2, а потом в одну операцию переименовываете старую паспорта1 в мусор, а паспорта2 в паспорта1 и дропаете мусор. Без всяких проверок, сравнений и мерджей сложных. Переименование -- мгновенная операция.


        1. SpiderEkb
          22.08.2021 14:15
          #23399074

          А если в момент переименования по удаляемой таблице SQL запрос выполняется?


          1. garex
            22.08.2021 17:47
            #23399506

            Он до конца дойдёт, но по данным переименовываемой таблицы.


            1. SpiderEkb
              22.08.2021 20:15
              #23399856

              А не залочит он старый файл, не дав его удалить при переименовании?

              Вот возьмет и переключится моментально на новый не меняя плана запроса?

              Как-то сомнительно это мне... Сколько пробовал - если на индексе висит открытый запрос, пересоздать его не удается - object lock error

              Поробуйте на досуге сделать зацикленный запрос по таблице (чтобы оно фетчило в замкнутом цикле по кругу) и в это время удалить эту таблицу и подсунуть новую вместо нее переименованием.

              Сдается мне что не выдет.


              1. Vinchi
                24.08.2021 02:33
                #23405768

                Выйдет


      1. SpiderEkb
        22.08.2021 11:05
        #23398612

        Что Вы понимаете под "синхронизацией данных"?

        При хранении в памяти вам придется все равно учитывать возможность обращения к данным в момент их обновления. Т.е. использовать какие-то объекты синхронизации (мьютексы, семафоры).


        1. skivsoft Автор
          22.08.2021 16:57
          #23399436

          Под синхронизацией в бд я понимаю сравнение двух наборов данных, затем вставку недостающих записей и удаление лишних.

          Потоковая синхронизация была бы нужна, когда одновременно меняются данные в объекте-хранилище и читаются из него. В моем случае хранилище заменяется целиком на новое.


          1. Vinchi
            24.08.2021 02:32
            #23405766

            А просто подготовить таблицу в бд и одной транзакцией поменять имена у обоих?


  1. KvanTTT
    21.08.2021 12:45
    #23395742
    +1

    Лучше минимизировать количество аллокаций, вынести индекс запятой в константы и избавиться от LINQ. Метод IsOnlyNumbers превратиться в следующее:


    private bool IsOnlyNumbers(string value)
{
    if (value.Length == PART1_LENGTH + PART2_LENGTH && value[COMMA_INDEX] == ',')
    {
        for (int index = 0; index < value.Length; index++)
        {
            if (index != COMMA_INDEX && !char.IsDigit(value[index]))
            {
                return false;
            }
        }
        return true;
    }
    return false;
}

    Вишенка на торте — использовать спаны:


    private (int, int) SplitNumbersValue(string value)
{
    var onlyNumbers = value.Substring(0, COMMA_INDEX) + value.Substring(COMMA_INDEX + 1);
    var onlyNumbersSpan = onlyNumbers.AsSpan();
    return (int.Parse(onlyNumbersSpan.Slice(0, PART1_LENGTH)), int.Parse(onlyNumbersSpan.Slice(PART1_LENGTH)));
}

    Возможно этот метод можно оптимизируется еще больше, но я не занимался низкоуровневыми манимуляциями со спанами.


    Остальное нужно смотреть по полному коду, но ссылка на GitHub невалидная.


    1. skivsoft Автор
      21.08.2021 23:25
      #23397658
      +1

      Спасибо, полезные замечания! Сжатие ускорилось на 19 секунд (25%).


  1. el777
    21.08.2021 13:05
    #23395822
    +2

    Уточните требования к задаче:

    Что надо делать со строковыми сериями паспортов? Игнор?

    Самое интересное - нефункциональные требования:

    1. Ожидаемый RPS. Какое кол-во запросов должен тянуть сервис? Пробовали делать нагрузочное тестиование? Сколько тянет ваше решение на 1 поде?

    2. Скорость обновления? (Как вы его вообще будете обновлять?)

    3. Нужны ли инкрементальные обновления?

    4. Какой даунтайм допускается?

    5. Максимальное время запуска новой версии сервиса?

    6. Ограничения по CPU, Mem, HDD?

    7. Требования по горизонтальному масштабированию? Например, возможность горизонтального масштабирования до Х подов?

    8. Вообще, требования к масшабированию?


    1. RetroStyle
      21.08.2021 23:08
      #23397616
      +2

      Это называется: "...и тут появляется архитектор".

      Поздно, батенька, такие умные вопросы задавать - все уже закодировано :-).

      Программеру же было интересно с битиками поиграться. А вы к не нему с неприятными вопросами...


    1. skivsoft Автор
      22.08.2021 00:14
      #23397796

      Паспорта со строковыми сериями также должны проверяться на наличие в списке.

      1. Нагрузочное тестирование не делал. Можно расширить сервис, добавив проверку списка паспортов. Должно работать быстро, т.к. поиск идет в памяти и сложность близка к O(1).

      2. Сейчас (после некоторых оптимизаций) обновление занимает менее 6 минут и запускается по расписанию раз в сутки. Обновляется обьект в памяти.

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


  1. nvv
    21.08.2021 20:09
    #23397064

    При использовании подобных баз часто сталкиваются с выявлением ошибок (неточностей). От некорректный записей (не соответствие формату) до логических ошибок. Если проверка разделена на 2 этапа (быстрая проверка на вхождение + подробная проверка), для быстрой проверки записи только пополняется, а не затираются с новой выгрузкой.

    @skivsoft после фильтрации и сжатия значений, в случае успешного результата поиска, вы, вероятно, идёте в базу с более полными данными и проверяете причину включения в список, историю (некоторые записи то появляются то исчезают, выявлялись ли ложные срабатывания, пересечения с другими источниками), уровень доверия записи. Это поинтереснее сжатия. Расскажете?


    1. skivsoft Автор
      22.08.2021 00:32
      #23397826

      Не совсем понял для чего разделять на 2 этапа. Сейчас в csv файле присутствуют следующие наборы данных:

      • в формате ^\d{4},\d{6}$ (таких записей большинство)

      • в формате ^[A-Za-zА-Яа-я\d\s-]+,\d+$

      • ошибочные данные, например З вместо 3 в номере паспорта

      Проверять на соответствие формату не требуется, достаточно проверить присутствует ли комбинация Серия + Номер в csv-файле.

      У меня нет истории записей и других источников, только этот csv-файл из открытого доступа. В данной реализации нет ложных срабатываний, сжатые данные эквивалентны исходному csv-файлу с точностью до порядка строк. Т.е. выполняется условие:

      SORT(original.csv) = SORT(Unpack(Pack(original.csv)))


      1. nvv
        22.08.2021 00:55
        #23397872

        Ложные срабатывания - ошибочное включение в базу, а не ошибки при сжатии. Такие значения то появляются, то исчезают. Если не хранить историю, в т.ч. доп.проверок и отметок о ложных срабатываниях, качество применения данных (для скоринга?) снижается.


  1. koreychenko
    21.08.2021 20:34
    #23397120

    Это чье-то тестовое, но не помню чье. Тестовое было на позицию архитектора кажись или PHP разраба.

    В итоге, в порядке извращения я сделал это все на связке nginx, который выполняет код на lua, который то ли грепает по этому файлу то ли ещё чего, не помню.

    А обновление без даунтайма кажись через wget/rsync + изменение симлинка.

    В общем, вообще без программирования.


  1. Vinchi
    24.08.2021 02:30
    #23405760

    Не проще было просто в parquet перевести и дергать каким нибудь drill у которого еще и кеширование есть?