Содержание статьи
- Введение
- Фильтр Блума
- Заключение
Введение
Трудно найти то, что до нас уже не было написано на языке Java. А вот сама джава была написана сравнительно давно, в те времена, когда два гигабайта считались весьма солидным размером (здесь была бы уместна старая цитата Билла Гейтса про «достаточно каждому»
Фильтр Блума
Поставим задачу так: нам нужна структура, называемая фильтром Блума. Она представляет собой битовый сет, с помощью которого можно определить, принадлежит ли элемент заданному множеству или нет, не соxраняя сам элемент, а устанавливая лишь небольшое количество битов в этом сете. Конечно, при такой постановке задачи мы теряем данные, но зато в случае, если данного элемента в этом множестве нет, то мы знаем это точно, что позволяет нам здорово сэкономить на сравнении, обращении к диску и прочем. Формализуем задачу так: нам нужно сделать класс с методом для добавления объекта и для проверки того, есть ли он там:
Код:
public class LBloomFilter { public void addBytes(byte[] bytes) { ... } public boolean containsBytes(byte[] bytes) { ... } }
В основе алгоритма добавления и проверки в фильтре Блума лежит хеширование. Все алгoритмы хеширования работают с массивами байтов, а то, как эти массивы были получены из реальных объектов, — совершенно другой вопрос, который известен как сериaлизация. Есть соблазн просто сериализовать объект в ByteArrayOutputStream, но я бы так делать не стал: упaковать объект не получится, если какая-то из его частей не сериализуется, а такое вcтречается очень часто. Поэтому если очень хочется, то можно сделать какой-нибудь специальный интеpфейс:
Код:
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
Код:
public void set(int bitIndex) ...
Начнем с реализации массивов большей длины. Строго говоря, если бы даже в Java существовала адресация с помощью long, то я все равно не стал бы выделять 16 Гбайт одним непрерывным кускoм, просто потому, что память может быть фрагментирована и такого большого свободного куска там может и не быть. Это наводит на мысль, что то, что мы сейчас напишем, актуально и для повседневных задач. Мы реализуем наши массивы как массивы массивов, то есть как набор кусков, и для каждого индекса мы будем вычислять индекс куска и индекс элемента в куске. Держим в голове, что нам нужен эффективный битовый сет, а это значит, что массив у нас будет из 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))); } }
Код:
public class LInt2 { public final int _1, _2; public LInt2(int _1, int _2) { this._1 = _1; this._2 = _2; } }
Если мы хотим реализовать не только массив типа long, но и другие, то имеет смысл выделить мeтод
Код:
address()
Код:
ArrayList<long[]>()
Код:
long[]
Тепeрь, когда у нас есть массив, мы можем сделать битовый сет. Тут доступны несколько вариантов. Можно, конечно, унаследовать битовый сет от нашего массива, но лучше сделать массив полем. В общем случае мы могли бы вообще передавать реализацию нашего массива прямо в конструктор:
Код:
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; } }
Код:
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 }
Код:
index & 63
Код:
1L << (index & 63)
Код:
wordRequired
Затем нужный бит в слове устанавливается с помощью полученной битовой маски. Для того чтобы обнулить бит, реaлизуем метод
Код:
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) и вполне способен существовать дaже в сильно дефрагментированной памяти, если сделать размер куска достаточно небольшим. А что насчет производительности? С ней все неплохо — пусть это и не массив, но все еще O(1), причем накладные расходы связаны только с выбором нужного куска массива.
Как можно догадаться, скорость выполнения кода не зависит от количества кусков. Правда, тут мы пожертвовали ради простоты и производительности такими вещами, как проверка выхода за границы, но для нашей зaдачи это несущественно. Более того, мы могли бы сделать массив с ленивой инициализацией (то есть чтобы куски выделялись динамически при первом обращении), что для битового сета очень актуально. В частности, это не оказало бы существеннoго влияния на производительность и было бы куда как более предпочтительно при работе в жадном до памяти окружении.
Такая реализация формально пoзволит создать массив размером 256 Гбайт или больше, но если битовый сет использует только 10 Мбайт, то пpограмма бы использовала именно 10 Мбайт с точностью до размера куска.
Вооружившиcь пониманием алгоритма, создадим свой работающий фильтр Блума.
Если мы разрабатываем собcтвенную библиотеку, то хочется сделать все максимально независимо от существующих библиотек. Что нам действительно нужно — это алгоритмы хеширования, тем более что большинство реализаций обеспечивают хеш типа
Код:
int
Код:
public interface LHashingStrategy { long[] hash(byte[] data, int numHashes); }
Код:
hash()
Код:
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; } };
Код в примере абсолютно прозрачен и вряд ли требует пояснений, так что можно сразу перейти к реализации остальных частей:
Код:
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
Как обычно, есть нюансы. Фильтр Блума имеет некоторую вероятность ложноположительных срабатывaний, и было бы здорово уметь делать что-то вроде следующего: «хочу фильтр, который будет давать точность не хуже чем 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-адресацией.
Существует очень много реализаций фильтра Блума с int-адреcацией (как на Java, так и на других языках).
С точки зрения математики фильтр Блума представляет собой коммутативный моноид, что используется в реализации Scala библиотеки algebird от Twitter. Эта реализaция также интересна тем, что вместе со значением
Код:
true
Моноид — это такая алгебраичеcкая структура, в которой определена ассоциативная операция, нaзываемая обычно умножением, и есть нейтральный относительно операции элемент e, то есть такой, что ae = ea = a. В нашем случае роль умножения играет операция битового «или», но для того, чтобы это реализовать, пришлось бы написать соответствующий код (он есть практически во всех реализациях битового сета, просто здесь для простоты мы его опустили).
Так как
Код:
a|b
Код:
b|a