Эффективность фильтра Блума в памяти

В предыдущей статье был рассмотрен расчет оптимальных параметров фильтра Блума и его реализация.

Со статьей можно ознакомиться здесь: Фильтр Блума

Для оценки эффективности будем рассматривать сколько оперативной памяти потребляют различные структуры данных в Java 11.

Для примера будем размещать в памяти информацию о 20 миллионах ИИН и делать наблюдения через VisualVM.

ИИН представляет собой строку из 12 символов.

Хранение в ArrayList<String>

Хранение 20 миллионов ИИН в ArrayList:

Создается 20 миллионов объектов String, каждый объект String ссылается на массив байт из 12 элементов.

ЭлементРазмерКол-воОбщий размер
String20 B20 000 000553 MB
byte[12]36 B20 000 000687 MB

Суммарно данный способ занимает в памяти примерно 1240 MБ.

Хранение в HashSet<String>

Хранение 20 миллионов ИИН в HashSet<String>:

Создается 20 миллионов объектов таких же как и для ArrayList, дополнительно хранятся узлы корзины HashMap.Node (под капотом HashSet находится HashMap).

ЭлементРазмерКол-воОбщий размер
String20 B20 000 000553 MB
byte[12]36 B20 000 000687 MB
HashMap.Node44 B20 000 000839 MB

Суммарно данный способ занимает в памяти примерно 2079 MБ.

Хранение в HashSet<Long>

Хранение 20 миллионов ИИН в HashSet<Long>:

Создается 20 миллионов объектов Long и HashMap.Node.

ЭлементРазмерКол-воОбщий размер
Long24 B20 000 000458 MB
HashMap.Node44 B20 000 000839 MB

Суммарно данный способ занимает в памяти примерно 1297 MБ.

Хранение в ArrayList<Long>

Создается 20 миллионов объектов Long.

ЭлементРазмерКол-воОбщий размер
Long24 B20 000 000458 MB

Суммарно данный способ занимает в памяти примерно 458 MБ.

Хранение в long[]

Создается массив из 20 миллионов элементов типа long.

ЭлементРазмерКол-воОбщий размер
long8 B20 000 000152 MB

Суммарно данный способ занимает в памяти примерно 152 MБ.

Хранение в MyBloomFilter

В реализации MyBloomFilter используется BitSet, BitSet в свою очередь хранит биты в виде массива long, поэтому основную память забирает этот массив.

В нашей реализации BitSet хранит информацию о 268 435 456 битах.

В один long помещается 64 бит.

268 435 456 / 64 = 4 194 304 (кол-во элементов в массиве)

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

268 435 456 бит / 8 = 33 554 432 байт

Суммарно данный способ занимает в памяти примерно 32 MБ.

Хранение в GoogleBloomFilter

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

Для 20 миллионов ИИН с вероятностью ошибок 1% оптимальное кол-во бит составляет 191 701 168.

BloomFilter из набора guava для хранения бит использует AtomicLongArray, который в свою очередь использует для хранения бит также long массив (long[]).

Рассчитаем кол-во элементов в массиве:

⌈191 701 168 / 64⌉  = ⌈2 995 330.75⌉ =  2 995 331

Теперь рассчитаем размер в байтах:

191 701 168 бит / 8 = 23 962 646 байт

Суммарно данный способ занимает в памяти примерно 23 MБ.

Итоговая сравнительная таблица

Структура данныхПотребляемая памятьПримечание
HashSet<String>2079 MБОптимальные операции добавления и поиска, но высокое потребление памяти
HashSet<Long>1297 MБДополнительная работа с Long, из-за наличия у ИИН ведущих нулей
ArrayList<String>1240 MБСписок должен быть отсортирован, что была возможность поиска
ArrayList<Long>458 MБСписок должен быть отсортирован. Дополнительная работа с Long, из-за наличия у ИИН ведущих нулей.
long[]152 MБФиксированный размер.
MyBloomFilter32 MБНеоптимальная реализация
Bloom Filter (Google Guava)23 MБОптимальная реализация

Заключение

В данной статье было рассмотрено несколько вариантов хранения информации о 20 миллионах ИИН, где вместо 1-2 гигабайт, можно обойтись 20-30 мегабайтами (экономия на порядок) при допущении заданной вероятности ошибок.

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

Фильтр Блума имеет достаточно специфические варианты использования, и есть небольшая вероятность, что он вам пригодится.

Поделиться данной статьей через:  

Добавить комментарий

Ваш адрес email не будет опубликован.

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.