Как определить, существует ли элемент в данных миллиардного уровня?

интервью задняя часть база данных алгоритм
Как определить, существует ли элемент в данных миллиардного уровня?

предисловие

Друг недавно задал мне этот вопрос интервью:

Сейчас есть очень большие данные, скажем, все типа int. Теперь, когда я даю вам число, вы должны сказать мне, существует ли оно в нем (как можно эффективнее).

Требования на самом деле очень четкие, просто чтобы определить, существуют ли данные.

Но вот важная предпосылка:очень большие данные.

Регулярная реализация

Если оставить это условие в стороне, какое первое решение приходит нам на ум?

Я думаю, что большинство из того, что приходит на ум, это использоватьHashMapДля хранения данных, потому что его эффективность запросов на запись относительно высока.

Запись и оценка того, существует ли элемент, имеют соответствующиеAPI, поэтому его относительно просто реализовать.

Я написал для этого один тест, используяHashSetдля хранения данных (нижний слой такжеHashMap); при этом память кучи записывается до смерти для следующего сравнения:

-Xms64m -Xmx64m -XX:+PrintHeapAtGC -XX:+HeapDumpOnOutOfMemoryError

Добавлено для легкой отладкиGCПечать логов и после переполнения памятиDumpОЗУ.

    @Test
    public void hashMapTest(){
        long star = System.currentTimeMillis();

        Set<Integer> hashset = new HashSet<>(100) ;
        for (int i = 0; i < 100; i++) {
            hashset.add(i) ;
        }
        Assert.assertTrue(hashset.contains(1));
        Assert.assertTrue(hashset.contains(2));
        Assert.assertTrue(hashset.contains(3));

        long end = System.currentTimeMillis();
        System.out.println("执行时间：" + (end - star));
    }

Там нет проблем, когда я пишу только 100 штук данных.

Исходя из этого, попробуйте записать данные на 1000 Вт:

Сразу после выполнения происходит переполнение памяти.

Видно, что мы не можем использовать этот метод в случае ограниченной памяти.

То же самое верно и на практике: поскольку необходимо судить о том, существуют ли данные в наборе, эффективность и точность рассматриваемого алгоритма должны определяться всеми данными.loadв память.

Bloom Filter

Исходя из условий, проанализированных выше, самое важное, что нужно решить для достижения этого требования, это如何将庞大的数据 load 到内存中。

И можем ли мы изменить образ мышления, потому что нужно только судить о том, существуют ли данные, и не нужно запрашивать данные, поэтому нет необходимости хранить в них настоящие данные.

Великие ученые помогли нам задуматься о такой необходимости.

Burton Howard BloomВ 1970 году появилась концепцияBloom Filter(китайский перевод: фильтр Блума) алгоритм.

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

Так что в данном случае это уместно.

Принцип фильтра Блума

Проанализируем принцип его реализации.

Официальное утверждение: это двоичный вектор, который был сохранен в течение длительного времени и реализован в сочетании с функцией хешей.

Звучит запутанно, но проще понять через картинку.

как показано на рисунке:

  • Во-первых, двоичный массив необходимо инициализировать, установить длину L (8 на рисунке), а начальное значение — все 0.
  • при написанииA1=1000данные, он должен выполнить H разhashРабота функции (здесь 2 раза); чем-то похожа на HashMap, через вычисляемыйHashCodeВзяв модуль с L, найдите позиции 0 и 2 и установите значение в этой позиции на 1.
  • A2=2000После такого же расчета4、7Позиция установлена ​​на 1.
  • когда естьB1=1000Когда необходимо судить, существует ли он, он также выполняет две операции хеширования и размещает в 0 и 2. В это время все их значения равны 1, поэтому считается, чтоB1=1000есть в коллекции.
  • когда естьB2=3000, то же самое справедливо. Первый хэш находитindex=4Когда значение в массиве равно 1, поэтому выполняется вторая операция хеширования, и результат находится вindex=5равно 0, поэтому предполагается, чтоB2=3000в коллекции нет.

Весь процесс написания и запросов выглядит следующим образом:

Выполните H хеш-операций над записанными данными, чтобы найти позицию в массиве, и одновременно измените данные на 1. Когда есть запрос данных, он точно так же располагается в массиве. Однажды один из них0рассмотреть данныев наборе точно нет, иначе данныеможет существовать в наборе.

Таким образом, фильтрация Блума имеет следующие характеристики:

  1. Пока возвращаемые данные не существуют, их определенно не существует.
  2. Возвращаемые данные существуют, но только с высокой вероятностью.
  3. При этом данные в нем нельзя очистить.

Первый пункт должен быть понятен, и я сосредоточусь на объяснении пунктов 2 и 3.

Почему можно вернуть существующие данные, которые фактически совпадают сHashMapпохожий.

Храните большой объем данных в массиве ограниченной длины, даже идеальный алгоритм хеширования будет конфликтовать, поэтому могут быть два совершенно разныхA、BОкончательное расположение двух данных точно такое же.

В настоящее время при запросе с B это, естественно, ложное срабатывание.

То же самое верно и для удаления данных.Когда я удаляю данные B, это фактически эквивалентно удалению данных A, что также приведет к последующим ложным срабатываниям.

На основании вышеизложенногоHashконфликтующие предпосылки, поэтомуBloom FilterСуществует определенный процент ложных срабатываний, этот показатель ложных срабатываний иHashСтепень H алгоритма и длина L массива имеют значение.

Реализуйте фильтр Блума самостоятельно

Алгоритм на самом деле очень прост и не сложен для понимания, поэтому используйтеJavaРеализован простой прототип.

public class BloomFilters {

    /**
     * 数组长度
     */
    private int arraySize;

    /**
     * 数组
     */
    private int[] array;

    public BloomFilters(int arraySize) {
        this.arraySize = arraySize;
        array = new int[arraySize];
    }

    /**
     * 写入数据
     * @param key
     */
    public void add(String key) {
        int first = hashcode_1(key);
        int second = hashcode_2(key);
        int third = hashcode_3(key);

        array[first % arraySize] = 1;
        array[second % arraySize] = 1;
        array[third % arraySize] = 1;

    }

    /**
     * 判断数据是否存在
     * @param key
     * @return
     */
    public boolean check(String key) {
        int first = hashcode_1(key);
        int second = hashcode_2(key);
        int third = hashcode_3(key);

        int firstIndex = array[first % arraySize];
        if (firstIndex == 0) {
            return false;
        }

        int secondIndex = array[second % arraySize];
        if (secondIndex == 0) {
            return false;
        }

        int thirdIndex = array[third % arraySize];
        if (thirdIndex == 0) {
            return false;
        }

        return true;

    }


    /**
     * hash 算法1
     * @param key
     * @return
     */
    private int hashcode_1(String key) {
        int hash = 0;
        int i;
        for (i = 0; i < key.length(); ++i) {
            hash = 33 * hash + key.charAt(i);
        }
        return Math.abs(hash);
    }

    /**
     * hash 算法2
     * @param data
     * @return
     */
    private int hashcode_2(String data) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < data.length(); i++) {
            hash = (hash ^ data.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return Math.abs(hash);
    }

    /**
     *  hash 算法3
     * @param key
     * @return
     */
    private int hashcode_3(String key) {
        int hash, i;
        for (hash = 0, i = 0; i < key.length(); ++i) {
            hash += key.charAt(i);
            hash += (hash << 10);
            hash ^= (hash >> 6);
        }
        hash += (hash << 3);
        hash ^= (hash >> 11);
        hash += (hash << 15);
        return Math.abs(hash);
    }
}
  1. Сначала инициализируется массив int.
  2. Три раза при записи данныхhashоперации и одновременно установите соответствующую позицию на 1.
  3. То же самое три раза при запросеhashОперация, получить соответствующее значение, если значение равно 0, считается, что данные не существуют.

Логика реализации фактически такая же, как описано выше.

Давайте протестируем те же параметры ниже:

-Xms64m -Xmx64m -XX:+PrintHeapAtGC

    @Test
    public void bloomFilterTest(){
        long star = System.currentTimeMillis();
        BloomFilters bloomFilters = new BloomFilters(10000000) ;
        for (int i = 0; i < 10000000; i++) {
            bloomFilters.add(i + "") ;
        }
        Assert.assertTrue(bloomFilters.check(1+""));
        Assert.assertTrue(bloomFilters.check(2+""));
        Assert.assertTrue(bloomFilters.check(3+""));
        Assert.assertTrue(bloomFilters.check(999999+""));
        Assert.assertFalse(bloomFilters.check(400230340+""));
        long end = System.currentTimeMillis();
        System.out.println("执行时间：" + (end - star));
    }

Результат выполнения следующий:

Потребовалось всего 3 секунды, чтобы записать 1000 Вт данных и сделать точное суждение.

Когда я уменьшил длину массива до 100Вт, появилось ложное срабатывание,400230340Этого числа явно нет в наборе, но оно возвращается к существованию.

Это также отражаетBloom Filterчастота ложных тревог.

Мы также увеличиваем длину массиваhashКоличество вычислений может уменьшить количество ложных срабатываний, но соответствующееCPU、内存потребление увеличится, это необходимо взвесить в соответствии с потребностями бизнеса.

Реализация гуавы

Хотя метод только сейчас достигает функции, он также удовлетворяет большому количеству данных. Но на самом деле наблюдатьGCЛог очень частый, да и старое поколение тоже используется на 90%, что близко к грани краха.

В общем, с использованием памяти не все в порядке.

Фактически, алгоритм также был реализован в библиотеке Google Guava, Давайте посмотрим на реализацию отраслевого авторитета.

-Xms64m -Xmx64m -XX:+PrintHeapAtGC 

    @Test
    public void guavaTest() {
        long star = System.currentTimeMillis();
        BloomFilter<Integer> filter = BloomFilter.create(
                Funnels.integerFunnel(),
                10000000,
                0.01);

        for (int i = 0; i < 10000000; i++) {
            filter.put(i);
        }

        Assert.assertTrue(filter.mightContain(1));
        Assert.assertTrue(filter.mightContain(2));
        Assert.assertTrue(filter.mightContain(3));
        Assert.assertFalse(filter.mightContain(10000000));
        long end = System.currentTimeMillis();
        System.out.println("执行时间：" + (end - star));
    }

Он также записывает 1000 Вт данных, и с выполнением проблем нет.

Просмотрите журнал GC и обнаружите, что там никого нет.fullGC, в то время как уровень использования пожилого возраста очень низок. По сравнению с предыдущим здесь явно намного лучше, да и данных можно записать больше.

Анализ исходного кода

тогда взглянитеGuavaКак это достигается.

В методе построения есть два важных параметра: один — ожидаемый объем данных для хранения, а другой — приемлемая частота ложных срабатываний. Моя тестовая демонстрация здесь составляет 1000 Вт и 0,01 соответственно.

Guavaпоможет вам рассчитать размер массива, который вы должны использовать, на основе ожидаемого числа и частоты ложных срабатываний.numBitsи хэш-функцию, которую нужно вычислить несколько разnumHashFunctions.

Правила расчета этого алгоритма можно найти в Википедии.

поставить функцию записи

реальные данныеputФункция выглядит следующим образом:

  • в соответствии сmurmur3_128метод до 128-битной длиныbyte[].
  • Возьмите два старших и младших 8 бита соответственноhashценность.
  • Затем по выполнению инициализацииhashколичество разhashоперация.
bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);

На самом деле этоhash取模получитьindexЗатем перейдите к присвоению значения 1.

Дело в томbits.set()метод.

На самом деле метод setBitArrayфункция в ,BitArrayЭто базовая структура данных, которая фактически хранит данные.

использовалlong[] dataдля хранения данных.

такset()время для этогоdataсделать обработку.

  • существуетsetпройти раньшеget()Определить, существуют ли данные в коллекции, и если они уже есть, то они напрямую вернутся, чтобы сообщить клиенту, что запись не удалась.
  • Следующим шагом будет выполнение побитовых операций位或赋值.
  • get()Логика вычислений метода аналогична логике set, если он оценивается как 0, он будет напрямую возвращать существование значения.

есть ли функция mayContain

Логика предыдущих шагов аналогична, просто вызовите предыдущийget()метод, чтобы определить, существует ли элемент или нет.

Суммировать

Есть еще довольно много применений фильтрации Блума, таких как базы данных, сканеры и антикэш-пробой.

Особенно, когда вам нужно точно знать, что делать, когда некоторых данных не существует, это очень подходит для фильтрации Блума.

Исследования, проведенные в этот период, показали, что алгоритм также весьма интересен, и мы должны продолжать делиться подобным контентом в будущем.

Поделитесь, если это поможет вам.

Пример кода для этого вопроса находится здесь:

GitHub.com/crossover J я…

Ваши лайки и репост - лучшая поддержка для меня

Категории