Bloom filter

Bloom filter is a confusing but powerful data structure that could save you memory, time, and maybe a career. What the heck is probabilistic data structure? It’s a structure that allows you to ensure that the element is not existing (for sure) but doesn’t guarantee that element exists.

Let’s say you have to serve some data from slow storage. You also have much smaller but faster storage for the cache. Access to the cache is not immediate but faster than a slow one.
If you can put all the keys of your cache in Hashmap, you are lucky. But if you can’t, you can take a look at Bloom filter structure.
You put cached keys in bloom filter, and every time users request data, you check the key in the bloom filter. If an item not in the bloom filter, you are retrieving the data from slow storage and put it into the cache. If an element exists, then you look at the cache but can expect that element is missing. That’s it. If you would like to decrease the probability of missing cache you can use multiple different Bloom filters.

If my explanation is confusing you can check out this short video.

More detailed explanation in wikipedia article.

Comments

comments

Leave a reply:

Site Footer

Sliding Sidebar

About Me

About Me

Для кого этот блог?

Для тех кого интересуют современные интернет технологи, IT бизнес, стартапы, менеджмент, контроль качества, личная эффективность, мотивация. Здесь я буду писать о том, что в первую очередь будет интересно мне, о проблемах и решениях. О том что пригодилось мне, и возможно будет интересно Вам.

Что заставило меня создать его?

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

Немного о себе.

Мой первый серьезный опыт в IT это работа над desktop приложениями в компании «Эксперт-Софт». У истоков её стояли несколько амбициозных и талантливых молодых людей, с огнем в глазах и желанием работать «как майкрософт». То чем мы там занимались вполне могли бы сегодня назвать «стартапом». Рук было откровенно мало, поэтому приходилось заниматься всем: кодированием на Delphi, написанием скриптов на VBA, дизайном, вёрсткой и поддержкой вебсайта, работой над рекламной полиграфией, проектированием интерфейсов и БД. Работы было много, но запал был велик, команда очень разношерстная, гармонично дополняя друг-друга в решении нетривиальных задач. Благодаря тому что пришлось попробовать многое, постепенно вырисовалось понимание того чем хочется заниматься, и как. Софтверным программированием я был сыт по горло. Массы проблем десктопного софта в вебе просто не было, по определению. Зато был четкий фокус на дизайне, юзабилити, скорости. Поэтому когда пришла пора уходить из «Эксперт-Софт», я без всякого сожаления стал искать работу как разработчик для web. Поскольку городишко у нас не очень большой, выбор был практически предопределен. Так я стал работать в «Оникс-Системз», где и продолжаю работать поныне. За время работы в компании я как разработчик принимал участие в работе над несколькими десятками проектов. Несколько десятков проектов было сделано мною как фрилансером. Самым большим проектом в котором я сыграл роль менеджера, считаю свою семью. Также довольно большой проект мы сейчас поднимаем с командой разработчиков (на данный момент команда состоит из четырех php разработчиков, одного flex кодера и тестировщика). Отсюда, большой интерес к современным практикам и методологиям, разным подходам в управлении командой, повышению эффективности и качества работы. По мере сил, вдохновения и свободного времени, я буду писать об этом.

Если у Вас возникли какие-то вопросы ко мне лично, буду рад если Вы свяжетесь со мной:

e-mail:
skype: denis.sheremetov
Старый сайт, с музычкой и флешом

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