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

Question

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

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

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

Answer 1

хранится в течение нескольких дней, а затем отбрасывается

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

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

Вы можете использовать этот фильтр Блума: 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;
}