Bloomfilter и Cassandra = Почему использовали и почему хэшировали несколько раз?

Question

Я прочитал это: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html

Мои вопросы:

1.) Верно ли, что Кассандра использует только фильтр Блума, чтобы узнать SST (Sorted String Table)который, скорее всего, содержит ключ?Поскольку может быть несколько SST, и Кассандра не знает, в каком SST может быть ключ?Таким образом, чтобы ускорить поиск во всех SST, используются bloomfilters.Это правильно?(Я пытаюсь понять, как работает Кассандра ...)

2.) Почему (как описано в ссылке выше) ключи хэшируются несколько раз?Верно ли, что ключи должны хешироваться с разными хэш-функциями несколько раз, чтобы получить лучшее «случайное распределение» битов?Если это не так, почему ключ нужно хешировать несколько раз?Это будет стоить циклов процессора?Если у меня есть выходные данные нескольких хэш-функций, то, что делается с результатами, являются они ANDed или XORded.Имеет ли это какое-то значение?

3.) Насколько велика разница между «Fales позитивами с использованием Bloomfilter» при использовании MD5 и SHA1 (который согласно статьям распределяется случайным образом)?Почему MD5 не распределен случайным образом?

Спасибо большое !!Jens

Answer 1

1) Да, смотрите это в cassandra wiki,

Cassandra использует фильтры Блума для сохранения ввода-вывода при выполнении поиска ключа: каждый SSTable имеет связанный с ним фильтр Блума, который Cassandra проверяет перед выполнением поиска диска, делая запросы для ключей, которые не существуют, почти бесплатными

Столбцы ключа могут быть разбиты на несколько таблиц. Если бы не фильтры Блума, при каждом чтении ключа пришлось бы читать каждый sstable, что непомерно дорого. Используя фильтры Блума, Кассандре почти всегда приходится искать только в sstables, которые содержат данные для этого ключа.

2) Это может дать вам лучшее понимание фильтров Блума. Вы хешируете k раз, чтобы получить независимые позиции в массиве размером m. Например, если A и B являются элементами в наборе, и у вас есть k = 2, ваши хеш-функции - md5 и sha1, а m = 16, вы можете сделать

md5(A) % m = 7
sha1(A) % m = 12

md5(B)  % m = 15
sha1(B)  % m = 12

Это дает вам m [7], m [12] и m [15] для фильтра.

Чтобы увидеть, есть ли C в наборе, вы делаете

md5(C)  % m = 8
sha1(C) % m = 12

Поскольку m [8] равно false, вы знаете, что C не входит в набор, однако для D

md5(D)  % m = 7
sha1(D)  % m = 15

И m [7], и m [15] имеют значение true, но D не входит в набор, поэтому D является ложноположительным.

Это стоит циклов ЦП, но вы торгуете циклами ЦП для уменьшенного ввода-вывода, что имеет смысл для Кассандры.

3) В статье не упоминается md5. md5 распределяется случайным образом, и я предполагаю, что разница между md5 и sha-1 для фильтров Блума невелика.

Answer 2

Как дополнение к 3-му пункту ответа по мостикам.

MD5 и SHA-1 распределены случайным образом, но являются криптографическими хеш-функциями. При реализации любого типа фильтра Блума единственным узким местом в производительности является время, необходимое для хеширования. Вот почему криптографические функции при их использовании снижают производительность приложения.

Рекомендуется использовать некриптографические хеш-функции, такие как хэш Murmur. Эта статья , рекомендует создавать и хэш-функции, такие как:

g(x) = h1(x) + i * h2(x) 

где g (x) - новая хеш-функция, h1 и h2 - стандартные хеш-функции, а i - число итераций в диапазоне от 0 до k.

Используя эту технику, ту же производительность можно достичь с помощью двух хеш-функций (при условии, что k> 2).