Пошук недійсних паспортів або вчимося готувати двійкові файли

У коментарях до публікації Чому Go перевершує посередність, один з хабраюзеров запропонував в якості прикладу написати алгоритм пошуку за списком недійсних паспортів.
Однією з умов завдання було — не використовувати для цієї мети СУБД. Також рішення повинна по мінімуму використовувати пам'ять, місце на диску і ЦП.

На свій подив виявив, що більшість коментаторів пропонували все ж використовувати СУБД, незважаючи на те, що рішення, використовує стандартні бази даних буде досить громіздким (крім того, що для самих даних потрібно використовувати мінімум 5 байт на запис, так ще і майже стільки ж місця на індекси).

Маючи досвід роботи над бінарними базами для Sypex Geo, я вирішив спробувати накидати формат бінарного файлу і алгоритм пошуку по ньому.

Аналіз даних

Насамперед, для того, щоб створити спеціальний формат файлу потрібно проаналізувати самі дані.
Вихідні дані являють собою CSV файл, в якому знаходиться список недійсних паспортів (серія і номер, розділені комою), за завданням нас цікавлять тільки російські паспорти (4 цифри серія та 6 цифр номер).

У bz2 архіві цей список займає 359 МБ, в розпакованому вигляді 1,13 ГБ. Близько 102 млн записів.

Я завантажив дані в MySQL (там є зручна завантаження CSV файлу з допомогою LOAD DATA), і вже в ньому провів аналіз даних.
Без індексів таблиця з наступною структурою заважила на 680 МБ.

CREATE TABLE `pass` (
`seria` SMALLINT(5) UNSIGNED NOT NULL,
`num` MEDIUMINT(8) UNSIGNED NOT NULL
) ENGINE=MyISAM ROW_FORMAT=FIXED

Якщо додати індекс стовпця num, включена буде 1,5 ГБ, а якщо зробити індекс за двома стовпчиками, то вже буде 1,7 ГБ.

З'ясувалося, що:
  1. Для однієї серії може бути до 600 000 номерів.
  2. У той час, як для одного номера максимум 200 серій.
Звідси робимо висновок, що шукати відразу за номером більш вигідно, так як це сильно скоротить подальший пошук. Значить, робимо індекс за номером паспорта.

Створюємо свій формат

Наш бінарний файл буде складатися з двох частин, перша частина буде являти собою індекс, у якому буде постійна кількість елементів, а саме мільйон значень-від 000 000 до 999 999. Кожен елемент індексу займає 4 байти і містить зміщення у другій частині файлу, де розташовані списки серій для відповідного номера. Самі серії зберігаються у другій частині файлу у вигляді двобайтових значень. Кількість елементів у списку серій для певного номера – це різниця зсувів (Шуканий номер) і (Шуканий номер + 1).

Схематичне відображення структури бінарного файлу для пошуку недійсних паспортів.

Щоб дізнатися, чи є паспорт у списку недійсних, потрібно виконати наступні прості дії.
Для прикладу візьмемо номер 2365 000002.

  1. За номером паспорта визначаємо зміщення в індексі, для цього номер множимо на 4 (розмір елемента індексу). 4 * 000002 = 8 байт (червоний блок на малюнку)
  2. Виконуємо зміщення і читаємо 2 елемента індексу (2*4 байт), щоб знати початок списку серій і кінець. Перетворимо їх у 2 десятеричных 32-бітних числа. У нашому випадку виходить 7 і 11 (для наочності відображення, показані не зсуву в байтах, а 1 одиниця зміщення = 1 серія)
  3. Читаємо дані щодо зміщення початку списку серій до кінця списку серій шуканого номери, пам'ятаємо, що записуються серії 2 байтами.
  4. Тепер шукаємо серед двобайтових послідовностей потрібну нам серію.
  5. Якщо знайшли – паспорт недійсний, інакше – в базі недійсних не значиться.
Оскільки серій для кожного номера не більше 200, можна шукати серію простим перебором. Для прискорення процесу можна використовувати бінарний пошук, попередньо відсортувавши серії. Але про всяких додаткових оптимізацію, напевно, в іншій публікації напишу, якщо буде цікаво.

А тепер тестування

Для прикладу накидав пару тестових скриптиков на PHP. Один для конвертації CSV файлу в наш бінарний формат. Другий-для пошуку потрібного паспорта. Архів зі скриптами можна завантажити тут.

Також порівняємо отримане рішення з варіантом, в якому дані в MySQL. Дані зберігаються на SSD (у випадку з зберіганням на HDD показники будуть гірше), крім того на сервері достатньо пам'яті, щоб кешувати всі таблиці в пам'яті, тобто оптимальний для MySQL варіант.

Тестування проводилося на улюбленій тестової майданчику — Vultr. Улюблена тому, що можна швидко підняти потужну VPS-ку з погодинною оплатою і зберігання снапшотов безкоштовне (тобто можна видаляти, а потім, коли потрібно швидко відновлювати тестове оточення).
БонусБажаючі отримати $20 на рахунок, для оплати послуг Vultr, можуть скористатися реф-посиланням (стосується тільки нових юзерів).
Для VPS обраний план 6 CPU, 8 ГБ, 150 ГБ SSD, MariaDB 10.1.16, PHP 7.0.9.

Отже, до цифр.


Для кожного типу зберігання даних перевірили два режими: одинарний режим (коли відкриття файлу і коннект до БД робиться для кожного номера) і пакетний режим (відкриття файлу і коннект до БД однократні).
DAT-файл MySQL
без індексів
MySQL
індекс за номерами
MySQL
індекс по номерах і серіях
Розмір БД (включаючи індекс) 198 МБ 680 МБ 1,5 ГБ 1,7 ГБ
Розмір індексу 4 МБ 0 МБ 893 МБ 1,07 ГБ
Завантаження CSV в БД (мм: сс) 3:54* 0:31 3:38 3:42
Швидкість пошуку одинарна (п/с) 91 198 0,2** 3 711 3 760
Швидкість пошуку пакетна (п/с) 212 116 0,2 44 137 44 822
* Швидкість не дуже, так як створення dat-файлу робилося максимально просто і примітивно, лише б працювало. Якщо буде цікаво — напишу, як можна значно прискорити час парсинга CSV.
** Для всіх методів здійснювався прогін по 300 тисячам паспортів, крім MySQL без індексу, так як, там на пошук одного паспорта йде до 10 секунд.


Висновки

Як бачимо за результатами тестування, кастомное рішення заточене під потрібну задачу, може працювати значно швидше, ніж СУБД загального призначення, окрім того формат у 7-8 разів компактніше, ніж таблиця MySQL.

А сам скрипт для пошуку файлу займає менше 10 рядків (без коментів).
$pass = '0307,000000'; // Шуканий паспорт
$fn = fopen('passports.dat', 'rb');
// Здійснюємо пошук
// Конвертуємо серію в 2-байтовий формат, краще це зробити один раз, ніж конвертувати списки серій
$seria = pack('n', substr($pass, 0, 4)); 
$num = substr($pass, 5);
// Зміщуємося до шуканого номером в індексі
fseek($fn, $num * 4);
// Читаємо по 2 зсуву по 4 байти
$seek = unpack('Nbegin/Nend', fread($fn, 8));
// Читаємо серії по знайденим зміщень
fseek($fn, $seek['begin']);
$series = fread($fn, $seek['end'] - $seek['begin']);
// Пошук в списку серій
echo ($pos = strpos($series, $seria)) !== false && $pos % 2 == 0 ? 'INVALID' : 'VALID';

P. S. скрипт природно максимально спрощений, і призначений для навчальних цілей, а не для продакшену (але це стосується не стільки логіка, скільки обробки помилок).

Вітається переклади на інші мови програмування, можна буде помірятися :)
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.