Математика для программиста, часть 3. Создаем вероятностную структуру данных на Java

В своей прошлой «математической» статье я пообещал привести пример реализации того, что, казалось бы, и без нас уже реализовано :). Это будет не совсем игрушечный пример, я взял его из своего реального опыта, адаптировав для статьи. Речь пойдет о том, как реализовать собственную структуру данных, причем не простую, а вероятностную. Постараюсь описать все просто и понятно, не забыв при этом оставить задел для усложнения и модернизации.

Введение

Трудно найти то, что до нас уже не было написано на языке Java. А вот сама джава была написана сравнительно давно, в те времена, когда два гигабайта считались весьма солидным размером (здесь была бы уместна старая цитата Билла Гейтса про «достаточно каждому» :)). Поэтому адресация массивов, а также всех адресуемых коллекций в Java позволяет обращаться только примерно к 2 миллиардам элементов. Теперь представим, что тебе нужно сделать массив из 10 миллиардов элементов... В моем же случае все выглядело еще хуже, мне была нужна вероятностная структура данных с long-адресацией. Здесь я постараюсь «крупными мазками» воспроизвести всю задачу целиком, в результате мы создадим библиотеку для работы с коллекциями, где индексы могут быть больше, чем int.

Фильтр Блума

Поставим задачу так: нам нужна структура, называемая фильтром Блума. Она представляет собой битовый сет, с помощью которого можно определить, принадлежит ли элемент заданному множеству или нет, не сохраняя сам элемент, а устанавливая лишь небольшое количество битов в этом сете. Конечно, при такой постановке задачи мы теряем данные, но зато в случае, если данного элемента в этом множестве нет, то мы знаем это точно, что позволяет нам здорово сэкономить на сравнении, обращении к диску и прочем. Формализуем задачу так: нам нужно сделать класс с методом для добавления объекта и для проверки того, есть ли он там:

public class LBloomFilter {
  public void addBytes(byte[] bytes) {
    ...
  }

  public boolean containsBytes(byte[] bytes) {
    ...
  }
}

Первый вопрос, который возникает: почему массив байтов? Для ответа на него начнем с самого начала — постараемся понять, как это вообще работает.

В основе алгоритма добавления и проверки в фильтре Блума лежит хеширование. Все алгоритмы хеширования работают с массивами байтов, а то, как эти массивы были получены из реальных объектов, — совершенно другой вопрос, который известен как сериализация. Есть соблазн просто сериализовать объект в ByteArrayOutputStream, но я бы так делать не стал: упаковать объект не получится, если какая-то из его частей не сериализуется, а такое встречается очень часто. Поэтому если очень хочется, то можно сделать какой-нибудь специальный интерфейс:

public interface LPackable {
  byte[] pack();
}

Тогда код с дженериками будет выглядеть примерно так:

public class LGenericBloomFilter<T extends LPackable> extends LBloomFilter {
  public void add(T obj) {
    addBytes(obj.pack());
  }

  public boolean contains(T obj) {
    return containsBytes(obj.pack());
  }
}

Теперь алгоритм. В основе добавления и проверки лежит один и тот же прием: для каждого объекта сгенерируем некоторое количество хешей и установим (или проверим) соответствующие биты в битовом сете. Конечно, все это мы берем по модулю размера нашего битового сета. Если более точно, то нужно сделать хеш положительным и взять остаток от деления на длину битового сета. Ясно, что в случае, когда мы не нашли соответствующие биты, такого объекта точно не было добавлено, однако если биты установлены, то это не обязательно наш объект — это может быть результат интерференции хешей других объектов.

Вроде все просто, мы вернемся к деталям реализации чуть позже, а сейчас попробуем разобраться, что именно для реализации вообще нужно. Для начала сообразим, зачем нам большой битовый сет.

Если мы хотим использовать фильтр Блума для большого количества объектов (десятки миллиардов), то нам нужно много битов для того, чтобы обеспечить подходящую точность. Таким образом, мы сталкиваемся со следующей проблемой: в нашем распоряжении есть старый добрый java.util.BitSet, но, как и у всех Java-коллекций, индексирование у него int:

public void set(int bitIndex) ...

Выходит, что для реализации сравнительно простой структуры данных нам нужно написать битовый сет с адресацией на основе long. Это ведет к тому, что нам нужны и массивы с такой адресацией.

Начнем с реализации массивов большей длины. Строго говоря, если бы даже в Java существовала адресация с помощью long, то я все равно не стал бы выделять 16 Гбайт одним непрерывным куском, просто потому, что память может быть фрагментирована и такого большого свободного куска там может и не быть. Это наводит на мысль, что то, что мы сейчас напишем, актуально и для повседневных задач. Мы реализуем наши массивы как массивы массивов, то есть как набор кусков, и для каждого индекса мы будем вычислять индекс куска и индекс элемента в куске. Держим в голове, что нам нужен эффективный битовый сет, а это значит, что массив у нас будет из long:

public class LLongArray {
  private long[][] chunks;
  private static final long serialVersionUID = 1L;

  public LLongArray(long length, int chunkSizeLog2) {
    super(length, chunkSizeLog2);

    chunks = new long[numChunks][];
    for (int i = 0; i < numChunks; i++)
      chunks[i] = new long[chunkSize];
  }

  public long get(long index) {
    LInt2 a = address(index);
    return chunks[a._1][a._2];
  }

  public void set(long index, long value) {
    LInt2 a = address(index);
    chunks[a._1][a._2] = value;
  }

  LInt2 address(long index) {
    // (index / chunkSize, index % chunkSize)
    return new LInt2((int) (index >> chunkSizeLog2), (int) (index & (chunkSize - 1)));
  }
}

Здесь LInt2 — это класс для пары элементов типа int:

public class LInt2 {
  public final int _1, _2;

  public LInt2(int _1, int _2) {
    this._1 = _1;
    this._2 = _2;
  }
}

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

Если мы хотим реализовать не только массив типа long, но и другие, то имеет смысл выделить метод address() в отдельный класс LArray и наследовать уже от него, так как правила адресации будут одинаковы. Такой подход к адресации вообще позволяет нам сделать много интересного: к примеру, если мы хотим иметь массив изменяемой длины, то нам всего лишь нужно использовать что-нибудь вроде ArrayList<long[]>() для chunks вместо long[], тогда мы сможем спокойно добавлять куски к нашему массиву.

Теперь, когда у нас есть массив, мы можем сделать битовый сет. Тут доступны несколько вариантов. Можно, конечно, унаследовать битовый сет от нашего массива, но лучше сделать массив полем. В общем случае мы могли бы вообще передавать реализацию нашего массива прямо в конструктор:

public class LBitSet {
  private final LLongArray words;
  private long numBits;

  public LBitSet(long numBits, int chunkSizeLog2) {
    this.words = new LLongArray(wordsRequired(numBits), chunkSizeLog2);
    this.numBits = numBits;
  }

  static long wordsRequired(long numBits) {
    return numBits >> 6;
  }
}

Для начала требуется определить, сколько нужно элементов в массиве для заданного количества битов. Здесь сдвиг вправо на 6 бит — это просто целочисленное деление на 64, так как мы используем long для хранения битов. Теперь нужно добавить функцию установки бита:

public void set(long index) {
  long bitmask = 1L << (index & 63); // mod 64 and shift
  long wordIndex = index >> 6;
  long w = words.get(wordIndex);
  words.set(wordIndex, w | bitmask); // div by 64 and mask
}

В этом коде тоже нет ничего хитрого, мы просто ставим бит в нужное положение. Для этого нам нужны младшие 6 бит индекса, которые получаются маскированием index & 63. Последнее эквивалентно вычислению остатка от деления на 64. Таким образом, 1L << (index & 63) просто дает нам бит в нужном месте слова. Индекс слова в массиве получается целочисленным делением (для скорости — сдвигом), как и в случае метода wordRequired.

Затем нужный бит в слове устанавливается с помощью полученной битовой маски. Для того чтобы обнулить бит, реализуем метод unset, который отличается от предыдущего только последней строкой:

words.set(wordIndex, w & ~bitmask);

Метод get в таком случае будет также выглядеть тривиально:

public boolean get(long index) {
  long bitmask = 1L << (index & 63);
  return (words.get(index >> 6) & bitmask) != 0;
}

Таким образом, мы имеем следующее: у нас есть битовый сет, который может быть сколь угодно большим (насколько позволяет размер кучи в JVM) и вполне способен существовать даже в сильно дефрагментированной памяти, если сделать размер куска достаточно небольшим. А что насчет производительности? С ней все неплохо — пусть это и не массив, но все еще O(1), причем накладные расходы связаны только с выбором нужного куска массива.

Как можно догадаться, скорость выполнения кода не зависит от количества кусков. Правда, тут мы пожертвовали ради простоты и производительности такими вещами, как проверка выхода за границы, но для нашей задачи это несущественно. Более того, мы могли бы сделать массив с ленивой инициализацией (то есть чтобы куски выделялись динамически при первом обращении), что для битового сета очень актуально. В частности, это не оказало бы существенного влияния на производительность и было бы куда как более предпочтительно при работе в жадном до памяти окружении.

Такая реализация формально позволит создать массив размером 256 Гбайт или больше, но если битовый сет использует только 10 Мбайт, то программа бы использовала именно 10 Мбайт с точностью до размера куска.

Вооружившись пониманием алгоритма, создадим свой работающий фильтр Блума.

Если мы разрабатываем собственную библиотеку, то хочется сделать все максимально независимо от существующих библиотек. Что нам действительно нужно — это алгоритмы хеширования, тем более что большинство реализаций обеспечивают хеш типа int. Подробное рассмотрение этого вопроса и тем более реализация выходит далеко за пределы этой статьи, так что мы просто абстрагируем этот механизм. Все, что нам нужно, — стратегия хеширования:

public interface LHashingStrategy {
  long[] hash(byte[] data, int numHashes);
}

Метод hash() возвращает нужное количество посчитанных хешей для заданного набора байтов. Для тестирования можно реализовать какой-нибудь вариант на основе существующих библиотек, которые тебе нравятся больше, к примеру Guava от Google (там есть 128-битовый murmur-хеш):

private static LBloomFilter.LHashingStrategy mumur3Strategy = new LBloomFilter.LHashingStrategy() {
  int salt = 0xAF;

  public long[] hash(byte[] data, int numHashes) {
    long[] h = new long[numHashes];
    for(int i = 0; i < numHashes; i++)
      h[i] = Hashing.murmur3_128(i + salt).hashBytes(data).asLong();
    return h;
  }
};

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

Код в примере абсолютно прозрачен и вряд ли требует пояснений, так что можно сразу перейти к реализации остальных частей:

public class LBloomFilter {
  private final int numHashes;
  private final long numBits;
  private final LBitSet bits;
  private final LHashingStrategy hashingStrategy;
  private static final long mask = 0x7FFFFFFFFFFFFFFFL;

  public LBloomFilter(int numHashes, long numBits,
                      int chunkSizeLog2,
                      LHashingStrategy hashingStrategy) {
    this.numHashes = numHashes;
    this.numBits = numBits;
    this.bits = new LBitSet(numBits, chunkSizeLog2);
    this.hashingStrategy = hashingStrategy;
  }

  public boolean containsBytes(byte[] bytes) {
    long[] hashes = hashingStrategy.hash(bytes, numHashes);
    for(long h: hashes)
      if (!bits.get((h & mask) % numBits)) return false;
    return true;
  }

  public void addBytes(byte[] bytes) {
    long[] hashes = hashingStrategy.hash(bytes, numHashes);
    for(long h: hashes)
      bits.set((h & mask) % numBits);
  }
}

Это и есть основной код, в котором полностью реализована концепция фильтра Блума. Поле mask используется для того, чтобы делать хеши положительными, если они по какой-то причине таковыми не являются, такая маска просто «забывает» знаковый бит. В остальном это уже известная нам техника — для каждого хеша берем остаток от деления на количество битов и получаем номер бита, который нужно установить. Кажется, работает!

Как обычно, есть нюансы. Фильтр Блума имеет некоторую вероятность ложноположительных срабатываний, и было бы здорово уметь делать что-то вроде следующего: «хочу фильтр, который будет давать точность не хуже чем 95%; какого размера должен быть битовый сет для данного количества элементов, чтобы это работало? И как вообще правильно выбрать количество хешей?»

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

public static LIntLong optimalParameters(double fpProb, long maxNumEntries) {
  long numBits = (long)ceil(maxNumEntries * log(fpProb) / log(1.0 / pow(2.0, log(2.0))));
  int numHashes = (int)round(log(2.0) * numBits / maxNumEntries);
  return new LIntLong(numHashes, numBits);
}

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

Заключение

Ну вот нам и удалось с минимальными усилиями реализовать фильтр Блума, да непростой, а с long-адресацией.

С точки зрения математики фильтр Блума представляет собой коммутативный моноид, что используется в реализации Scala библиотеки algebird от Twitter. Эта реализация также интересна тем, что вместе со значением true она возвращает и вероятность того, что это не ложноположительное срабатывание.

Моноид — это такая алгебраическая структура, в которой определена ассоциативная операция, называемая обычно умножением, и есть нейтральный относительно операции элемент e, то есть такой, что ae = ea = a. В нашем случае роль умножения играет операция битового «или», но для того, чтобы это реализовать, пришлось бы написать соответствующий код (он есть практически во всех реализациях битового сета, просто здесь для простоты мы его опустили).

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