Что такое хороший алгоритм для проверки того, существует ли число в нескольких наборах без поиска их всех?

Question

Сценарий

Допустим, у вас есть несколько баз данных в 3 зонах. Зона A, B и C. Каждая зона в разных географических точках. В то же время у вас есть приложение, которое будет маршрутизировать имя пользователя и пароль на основе географического местоположения пользователя. Например, пользователь A будет перенаправлен в базу данных в Зоне A. Пользователь B Зона B и так далее.

Теперь, скажем, пользователь A переходит в зону B. Зона запроса приложения B и ничего не найдет. Зона запроса A и зона C могут занять некоторое время из-за того, что зоны находятся далеко, и вам придется запрашивать все базы данных во всех зонах.

Мой вопрос

Как вы можете проверить, если строка/число существует в нескольких наборах?

или

Как вы можете проверить строку существует в базе данных еще до отправки запроса?

Мой алгоритм

Это не идеально, но даст вам некоторое представление о том, что я пытаюсь сделать

Если мы имеем базу данных со следующими 3-х пользователей

• foo
• бар
• foobar

Мы принимаем хеш всех трех пользователей и ищем следующее простое число, если хеш не является простым.

sum = hash(foo).nextPrime() * hash(bar).nextPrime() * hash(foobar).nextPrime() 

Эта сумма разделяется между всеми зонами. Если я хочу проверить foo, я могу просто взять хэш foo и искать следующее правое, а затем взять gcd(foo,sum). Если он не равен одному. Это означает, что foo существует в некоторой базе данных. Если он равен единице, значит, foo вообще не существует. Если я хочу добавить новое имя пользователя. Я могу просто сделать sum = sum * hash(newUserName).nextPrime().

Сумма будет расти до такой степени, что будет быстрее запрашивать все базы данных.

Вы знакомы с аналогичным алгоритмом для решения этой проблемы?

Answer 1

Одна структура данных, подходящая для этого приложения, представляет собой Bloom filter.

Фильтр Bloom - это вероятностная структура данных, которая позволяет вам проверить, находится ли элемент уже в наборе. Если тест возвращает false, то элемент определенно не входит в набор (0% ложных негативов), если true, то он может быть в наборе, но не гарантируется (возможны ложные срабатывания).

Фильтр реализован как бит-массив с m битами и набором k хэш-функций. Чтобы добавить элемент в массив (например, имя пользователя), хеш элемент, используя каждую из хеш-функций, а затем взять по модулю m каждого хэш-значения для вычисления индексов для установки в битовом массиве. Чтобы проверить, находится ли элемент в наборе, вычислить все хэши и индексы и проверить, что все соответствующие биты в массиве установлены равными 1. Если любой из них равен нулю, элемент определенно не входит в набор, если все 1, то элемент, скорее всего, будет установлен в наборе, но есть небольшой шанс, которого он не может быть, процент ложных срабатываний может быть уменьшен с помощью более крупного m.

Для реализации х хэш-функций можно использовать один и тот же алгоритм хеширования (например, CRC32, MD5 и т. Д.), Но при этом добавлять разные соли в строку имени пользователя для каждого, прежде чем перейти к хэш-функции, хеш-функции для каждой соли. Для заданных m и n (количество добавляемых элементов) оптимальное количество хэш-функций k = (m/n) ln 2

Для вашего приложения бит-бит-бит бит-бит будет разделяться по всем зонам ABC и т. д. Когда пользователь пытается войти в систему, вы можете сначала проверить базу данных локальной зоны, а если есть, тогда запишите их как обычно. Если в локальной базе данных нет, проверьте фильтр Bloom, и если результат отрицательный, вы точно знаете, что они не существуют в другой зоне. Если это положительно, вам все равно необходимо проверить базы данных в других зонах (из-за возможности ложного позитива), но, по-видимому, это не большая проблема, потому что вы в любом случае будете обращаться к другим зонам, чтобы передать данные в том случае, если он был истинным положительным.

Одна из сторон использования фильтра Bloom состоит в том, что трудно удалить (хотя not impossible) элементы из набора после их добавления.