Bloom-фильтры
Представьте, что вам нужно принимать решения на основе какого-то набора исторических данных. Пусть вы делаете систему кэширования, которая должна срабатывать только для тех страниц, к которым уже обращались больше 1 раза, чтобы экономить дисковое пространство, но помогать перфомансу. Решение в лоб — хранить список посещённых пользователями страниц, добавить к списку счётчик. Но с таким решением есть две важные проблемы:
1. Сам список в какой-то момент начнёт весить неприлично много.
2. Время поиска по такому списку либо начнёт расти с ростом списка, либо придётся прикручивать какой-то умный индекс, который начнёт тормозить не чтение, а запись.
Сэм Роуз объясняет, как работает интересная структура данных
Если любите интересные структуры данных — статья вам понравится.
https://samwho.dev/bloom-filters/
Представьте, что вам нужно принимать решения на основе какого-то набора исторических данных. Пусть вы делаете систему кэширования, которая должна срабатывать только для тех страниц, к которым уже обращались больше 1 раза, чтобы экономить дисковое пространство, но помогать перфомансу. Решение в лоб — хранить список посещённых пользователями страниц, добавить к списку счётчик. Но с таким решением есть две важные проблемы:
1. Сам список в какой-то момент начнёт весить неприлично много.
2. Время поиска по такому списку либо начнёт расти с ростом списка, либо придётся прикручивать какой-то умный индекс, который начнёт тормозить не чтение, а запись.
Сэм Роуз объясняет, как работает интересная структура данных
BloomFilter, решающая эти проблемы. Если вы готовы принимать ложно-отрицательные решения в 1% случаев, то можно значительно сократить и размер списка, а время поиска по нему. И для примера выше это то, что надо: 1% ложных кэширований не сильно повлияет на затраты на дисковое хранилище, если вы при этом экономите на размере списка больше 80%.Если любите интересные структуры данных — статья вам понравится.
https://samwho.dev/bloom-filters/