Для начала вспомним, что такое битовые карты — (wiki) Би́товая ка́рта (англ. bitmap, bitset, bit array) — набор последовательно записанных двоичных разрядов, то есть последовательность (массив) битов.
Начну с задачи: есть выгрузка недействительных, просроченных и утерянных паспортов граждан РФ. Выгрузка представляет из себя csv файл, следующего содержания:
SERIAL,NUMBER
4213,123456
9212,654321
1031,001234
....
Данные в файле не отсортированы, их много (2Gb, ~150 000 000 записей) и обновления происходят ежедневно. Появилась необходимость в быстром обновлении и поиске по файлу.
-
Сортировка файла с помощью утилиты sort и поиск по отсортированному файлу. Сортировка заняла минимум час, поэтому этот вариант сразу не подошел, не говоря уже и о поиске.
-
Построчное чтение файла с записью в sqllite — 20 минут c индексированием. Поиск достаточно быстрый, но файл базы sqllite занимает 6Gb.
-
Запись файла в Postgres, тоже прошла довольно быстро, но данные и индекс так же занимали больше, чем исходный файл.
Но чувствовало мое сердечко, что можно добиться лучшего результата в использовании жесткого диска. И в какой-то момент я вспомнил про битовые карты, ведь серия и номер паспорта можно закодировать положением бита в файле. Для оптимизации поиска и возможности последовательного обновления я решил для каждой серии создавать свою битовую карту.
Получается, что для каждой серии паспорта будет создаваться битовая карта, которая может хранить информацию о 999 999 паспортах (=125 000 байт). Один байт хранит информацию о 8 паспортах, если бит в нужной позиции равен 1 — паспорт недействителен
Например:
Если мы захотим найти паспорт: 3456, 354407, то:
-
Вычислим байт, в котором хранится информация о паспорте 354407 div 8 = 44300
-
Вычислим бит, в котором хранится информация о паспорте 354407 mod 8 = 7
-
Откроем битовую карту для нужной серии, 3456.bitmap
-
Откроем файл в режиме чтения и прочитаем только 1 байт в нужной нам позиции.
"Инфографика" по битовой карте
- byte — номер байта
- bit_pos_in_file — номер бита в файле
- bit_pos_in_byte — номер бита в байте
- bit_value — значение бита
Получается поиск по времени ограничен скоростью чтения с диска (на самом деле нет, поиск одного паспорта занимает меньше 1ms и в настоящее время чтение с диска — дешевая операция), а все битовые карты для исходного файла занимают 600Mb (т.к. я не генерирую карту для серий, которых нет в файле).
Хочу отметить плюс этого решения: csv файл со временем будет занимать все больше и больше, а битовые карты будут занимать константное максимальное значение, вычисляемое по формуле:
Количество серий паспортов * Размер битовой карты = 9999 * 125Kb = 1.3Gb
Тесты проводились на MacBook:
- CPU: 2,3 GHz 2‑ядерный процессор Intel Core i5
- RAM: 8 ГБ 2133 MHz LPDDR3