Фильтры Блума в распределенной среде

У меня есть система, состоящая из нескольких экземпляров приложений, написанных на Java. Запросы к ним балансируются по нагрузке для обеспечения высокой доступности. Каждую секунду этот «кластер» получает сотни небольших фрагментов данных (каждый из которых состоит из нескольких простых строк), которые хранятся в базе данных, хранятся в течение нескольких дней, а затем отбрасываются. Помимо хранения этих данных, главное требование - быстро определить, хранится ли данное значение в базе данных или нет. Соответствующим образом проиндексированная и секционированная таблица базы данных кажется подходящей для этой проблемы и хорошо справляется со своей задачей, по крайней мере, на данный момент.

Проблема в том, что около 80% искомых значений не обнаруживаются, потому что их нет в базе данных. Поэтому хотелось бы немного ускорить процесс и сделать поиск более быстрым и менее ресурсоемким. Фильтр цветения был бы очевидным выбором, если бы не тот факт, что разные экземпляры приложения получают разные части данных, и если каждый экземпляр приложения имеет только часть данных в своем фильтре цветения, тогда эти фильтры цветения бесполезны.

У вас есть предложения / идеи, как решить эту проблему?


java search distributed-system bloom-filter
person zgguy    schedule 19.05.2018    source источник
comment
Эй, вы нашли обходные пути?   -  person Nawras    schedule 23.07.2019

Ответы (1)


arrow_upward
4
arrow_downward

держали пару дней, а затем выбросили

Фильтр Блума не поддерживает удаление объектов, а только вставку.
Если у вас несколько фильтров Блума, вы должны запросить их все, чтобы проверить, содержит ли один из них нужный вам объект.

Фильтры Блума можно эффективно объединить, если сыворотка имеет одинаковую структуру (одинаковый размер, одинаковая хеш-функция и т. Д.).

Вы можете использовать этот фильтр Блума: https://github.com/odnoklassniki/apache-cassandra/blob/master/src/java/org/apache/cassandra/utils/BloomFilter.java

И объедините два фильтра вот так:

BloomFilter merge(BloomFilter dstFilter, BloomFilter srcFilter) {
    OpenBitSet dst = dstFilter.bitset;
    OpenBitSet src = srcFilter.bitset;

    for (int i = 0; i < src.getPageCount(); ++i) {
        long[] dstBits = dst.getPage(i);
        long[] srcBits = src.getPage(i);

        for (int j = 0; j < srcBits.length; ++j) {
            dstBits[j] |= srcBits[j];
        }
        dst.setPage(i, dstBits);
    }
    return dstFilter;
}
person Viacheslav Shalamov    schedule 19.05.2018
comment
Да, но поскольку старые данные удаляются только один раз в день, я подумал, что имеет смысл перестраивать фильтр цветения каждый раз, когда старые данные удаляются. - person zgguy; 19.05.2018
comment
Это ответило на ваш вопрос? - person Viacheslav Shalamov; 20.05.2018
comment
Примечание: если вы используете подсчетный фильтр цветения, вы можете удалить отдельные ключи: hadoop.apache.org/docs/current/api/org/apache/hadoop/util/bloom/ - person Erwin Bolwidt; 20.05.2018
comment
Спасибо за комментарии. Возможно, мой вопрос немного неверен; речь идет не о самих фильтрах цветения, а о том, как эффективно поддерживать синхронизацию фильтров в нескольких экземплярах. Но в любом случае ваши комментарии полезны, спасибо. - person zgguy; 20.05.2018