Паспорта

Недавно узнал, что сервис проверки российских паспортов на недействительность является очень популярным. 😊

Самым актуальным вариантом является сервис МВД, но он закрыт капчей, что не всегда бывает удобно пользователям. Поэтому многие организации скачивают с сайта МВД файл с данными и работают уже с ним.

Традиционно программисты, не мудрствуя лукаво, просто сохраняют данные о паспортах в БД, пользуясь тем SQL-сервером, который используют для основного проекта.

Тут правда, возникает проблемка. Дело в том, что данные о недействительных паспортах достаточно часто обновляются (в среднем пару раз в неделю), а загрузка их в БД занимает время, причем достаточно значительное. Ну просто потому, что сейчас в России имеется более 110 млн. недействительных паспортов.

Меня этот момент заинтересовал, особенно если вспомнить, какой курс я читал, занимаясь преподаванием в СибГИУ.😉

Естественно, я захотел попробовать, с учетом особенности задачи, реализовать ее более оптимально. Идея тут очень простая: объем данных хоть и большой, но оперативная память  сейчас относительно дешевая. Поэтому надо попытаться воспользоваться этой особенностью.

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

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

Одна из самых быстрых структур для поиска (да и добавления)  данных является хэш-таблицы. Правда, только в том случае, когда ключевое поле данных имеет небольшой размер. Недостатком же хэш-таблиц является коллизии, а также связанная с этим некоторая избыточность памяти. Когда память очень хочется сэкономить (а это именно наш случай), то хэш-таблицы могут быть не самым подходящим вариантом.

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

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

Еще больше усугубит проблему памяти необходимость разрешения коллизий, так как выделить массив, покрывающий все пространство возможных значений ключей нереально. Он потребует под себя 5e10 байт, или 46 Гбайт ОЗУ, что несколько многовато для такой простой задачи.

При использовании меньшего размера хэш-таблицы потребуется место для разрешения коллизий. В случае использовании открытой адресации для сохранения приемлемой скорости работы потребуется размер хэш-таблицы примерно на 25% больший количества ключей. Таким образом, потребуется примерно 5*110e6*1.25 байт, или 655 Мбайт ОЗУ. Однако если сформируется достаточно длинная очередь проб для какого-либо подмножества ключей (а скорее всего так и произойдет), то в некоторых случаях производительность будет не очень высокой.

В случае использования закрытой адресации можно ограничиться хэш-таблицей размером в два раза меньше общего количества элементов, но потребуется дополнительная память для связи элементов в линейный список. Таким образом, общий объем памяти можно оценить на текущий момент так: 8*55e6+5*110e6 байт или 944 Мбайт ОЗУ. Т. е. закрытая адресация потребует больше памяти, но даст в среднем несколько более высокую производительность. А нам надо стараться экономить память, особенно в случае закрытой адресации. Во-первых, на вырост, а во-вторых, что бы как можно дольше оставаться в рамках 32-разрядной адресации.

Лирическое отступление. Чем плоха 64-разрядная адресация? Тем, что при активном использовании указателей, на их непродуктивное хранение используется в два раза больше памяти, чем в 32-разрядных системах. Например, если хэш-таблицу с закрытой адресацией перенести в 64-разрядную среду, то на хранение тех же самых данных потребуется уже 16*55e6+5*110e6 байт или 1363 Мбайта ОЗУ. Активное использование длинных указателей также дополнительно загружает шину данных, что немножко снижает производительность.

Поэтому, если объем обрабатываемых данных не превышает 2 Гбайт, то лучше оставаться в рамках 32-разрядного приложения.

Почему 2 Гбайт, а не 4? Этот вопрос лучше задать архитекторам Microsoft. Думаю, ответ имеет ту же природу, что и стародавнее утверждение, что 640 Кбайт хватит всем на всю оставшуюся жизнь.

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

Главное, что в этом  случае легко получить идеальную хэш-таблицу, в которой совсем нет коллизий, а поэтому практически не требуется лишняя память.

Номер паспорта отлично укладывается в массив [0..999999], а серия - в массив [0..9999].

Какой же из вариантов взять в качестве первого ключа? Для этого надо понять, какую структуру данных использовать в качестве второго ключа. Очевидно, что обычная хэш-таблица тут будет не очень хороша, так потребует слишком много памяти для реализации. Поэтому в первом приближении лучше использовать обычный сортированный массив, для ускорения операции поиска по вторичному ключу.

Посчитаем требуемый объем памяти. Если в качестве первого ключа взять серию, то объем памяти составит 9999*(4+const)+N*4 (можно ужаться до 3 байт на номер, но сложнее будет реализация, далее увидим, что и так получается неплохо), где const - затраты на организацию 2 ключа, а N - количество паспортов.

Если же в качестве первого ключа использовать номер паспорта, то требуемый объем памяти составит 999999*(4+const)+N*2.

Так как N много больше, чем 999999, то очевидно, что второй вариант гораздо экономичнее использует память. Точнее, при N > (4+const)*495000 будет выгоднее использовать второй вариант. Так как const - число не большее, вряд ли превышающее 20 байт, то второй вариант будет предпочтительным уже при 12 млн. паспортов.

Если рассчитать объем требуемой памяти, то окажется, что для хранения и поиска 110 млн. паспортов потребуется всего 232 Мбайта ОЗУ. В реальности памяти требуется раза так в 2 больше, из-за гранулярности виртуальной памяти и выравнивая границ хранящихся там элементов.

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

В этом случае для хранения информации уже о всех возможных паспортах потребуется 999999*(4+const+9999/8) или 1215 Мбайт. То есть 32-разрядной системы хватит для заданного формата паспортов навсегда.

Теперь о результатах. На тестах на бюджетном, и, теперь уже достаточно стареньком, процессоре AMD выдает примерно 3 млн. операций поиска что при нахождении паспорта в списке, что при его отсутствии. Загрузка новой информации занимает меньше 5 минут. Думаю, что не один SQL сервер не сможет выдать подобную производительность в таких же условиях.

Для интереса сделал веб-интерфейс к своей системе, хоть подобных сайтов сейчас полным-полно.

А вот если в качестве номера и/или серии паспорта будет использоваться не числа, а строки, то от использования такой организации данных придется отказаться. Это приведет как к увеличению объема требуемой памяти, так и существенному замедлению работы.