RoaringBitmap
1.3.16
Битовые наборы, также называемые растровыми изображениями, обычно используются в качестве быстрых структур данных. К сожалению, они могут использовать слишком много памяти. Чтобы компенсировать это, мы часто используем сжатые растровые изображения.
Ревущие растровые изображения — это сжатые растровые изображения, которые имеют тенденцию превосходить по производительности обычные сжатые растровые изображения, такие как WAH, EWAH или Consized. В некоторых случаях ревущие растровые изображения могут работать в сотни раз быстрее и часто обеспечивают значительно лучшее сжатие. Они могут быть даже быстрее, чем несжатые растровые изображения.
Ревущие растровые изображения хорошо работают во многих важных приложениях:
По возможности используйте Roaring для сжатия растровых изображений. Не используйте другие методы сжатия растровых изображений (Ванг и др., SIGMOD 2017).
спасибо за создание чего-то, что заставляет мое программное обеспечение работать в 5 раз быстрее (Чарльз Паркер из BigML)
Эту библиотеку использует
Библиотека является зрелой и используется в производстве уже много лет.
SQL-движок YouTube, Google Procella, использует для индексации растровые изображения Roaring. Apache Lucene использует растровые изображения Roaring, хотя у них есть своя независимая реализация. Производные Lucene, такие как Solr и Elastic, также используют растровые изображения Roaring. Другие платформы, такие как Whoosh, Microsoft Visual Studio Team Services (VSTS) и Pilosa, также используют растровые изображения Roaring в своих собственных реализациях. Вы найдете растровые изображения Roaring в InfluxDB, Bleve, Cloud Torrent, Redpanda и т. д.
Существует спецификация сериализованного формата для взаимодействия между реализациями. У нас есть совместимые реализации C/C++, Java и Go.
(c) 2013-...авторы RoaringBitmap
Этот код распространяется по лицензии Apache версии 2.0 (AL2.0).
Наборы — это фундаментальная абстракция в программном обеспечении. Их можно реализовать различными способами: в виде хэш-наборов, деревьев и т. д. В базах данных и поисковых системах наборы часто являются неотъемлемой частью индексов. Например, нам может потребоваться сохранить набор всех документов или строк (представленных числовым идентификатором), которые удовлетворяют некоторому свойству. Помимо добавления или удаления элементов из множества, нам нужны быстрые функции для вычисления пересечения, объединения, разницы между множествами и т. д.
Для реализации набора целых чисел особенно привлекательной стратегией является растровое изображение (также называемое битовым набором или битовым вектором). Используя n бит, мы можем представить любой набор целых чисел из диапазона [0,n): i-й бит устанавливается в единицу, если целое число i присутствует в наборе. Товарные процессоры используют слова размером W=32 или W=64 бита. Объединив множество таких слов, мы можем поддерживать большие значения n. Пересечения, объединения и различия могут быть реализованы как побитовые операции И, ИЛИ и И-НЕ. Более сложные функции множества также могут быть реализованы как побитовые операции.
Когда подход с набором битов применим, он может быть на порядки быстрее, чем другая возможная реализация набора (например, в виде хэш-набора), используя при этом в несколько раз меньше памяти.
Однако битовый набор, даже сжатый, не всегда применим. Например, если у вас есть 1000 случайных целых чисел, лучшим представлением может быть простой массив. Мы называем этот случай «разреженным» сценарием.
Несжатый BitSet может использовать много памяти. Например, если вы возьмете BitSet и установите для бита в позиции 1 000 000 значение true, и у вас будет чуть больше 100 КБ. Это более 100 КБ для хранения позиции одного бита. Это расточительно, даже если вы не заботитесь о памяти: предположим, что вам нужно вычислить пересечение этого BitSet с другим, у которого бит в позиции 1 000 001 равен true, тогда вам нужно пройти через все эти нули, нравится вам это или нет. Это может оказаться очень расточительным.
При этом определенно существуют случаи, когда попытка использовать сжатые растровые изображения является расточительной. Например, если у вас небольшой размер вселенной. Например, ваши растровые изображения представляют собой наборы целых чисел из [0,n), где n мало (например, n=64 или n=128). Если вы можете использовать несжатый BitSet и он не увеличивает использование памяти, то сжатые растровые изображения, вероятно, вам не пригодятся. Фактически, если вам не требуется сжатие, BitSet предлагает замечательную скорость.
Разреженный сценарий — это еще один вариант использования, в котором не следует использовать сжатые растровые изображения. Имейте в виду, что данные случайного вида обычно не сжимаются. Например, если у вас есть небольшой набор 32-битных случайных целых чисел, математически невозможно использовать гораздо меньше 32 битов на целое число, и попытки сжатия могут оказаться контрпродуктивными.
Большинство альтернатив Roaring являются частью более крупного семейства сжатых растровых изображений, которые представляют собой растровые изображения, закодированные по длине серии. Они идентифицируют длинные серии единиц или нулей и обозначают их словом-маркером. Если у вас локальная смесь 1 и 0, вы используете несжатое слово.
В этом семействе много форматов:
Однако у этих форматов есть большая проблема, которая в некоторых случаях может вам сильно навредить: в них нет произвольного доступа. Если вы хотите проверить, присутствует ли данное значение в наборе, вам придется начать с самого начала и «распаковать» все это. Это означает, что если вы хотите пересечь большой набор с большим набором, в худшем случае вам все равно придется распаковывать весь большой набор...
Роутинг решает эту проблему. Это работает следующим образом. Он делит данные на фрагменты по 2 16 целых чисел (например, [0, 2 16 ), [2 16 , 2 x 2 16 ), ...). Внутри чанка он может использовать несжатое растровое изображение, простой список целых чисел или список прогонов. Какой бы формат он ни использовал, все они позволяют быстро проверить наличие какого-либо значения (например, с помощью двоичного поиска). Конечным результатом является то, что Roaring может выполнять многие операции намного быстрее, чем форматы с кодированием серий, такие как WAH, EWAH, Concision... Возможно, это удивительно, но Roaring также обычно предлагает лучшие коэффициенты сжатия.
import org . roaringbitmap . RoaringBitmap ;
public class Basic {
public static void main ( String [] args ) {
RoaringBitmap rr = RoaringBitmap . bitmapOf ( 1 , 2 , 3 , 1000 );
RoaringBitmap rr2 = new RoaringBitmap ();
rr2 . add ( 4000L , 4255L );
rr . select ( 3 ); // would return the third value or 1000
rr . rank ( 2 ); // would return the rank of 2, which is index 1
rr . contains ( 1000 ); // will return true
rr . contains ( 7 ); // will return false
RoaringBitmap rror = RoaringBitmap . or ( rr , rr2 ); // new bitmap
rr . or ( rr2 ); //in-place computation
boolean equals = rror . equals ( rr ); // true
if (! equals ) throw new RuntimeException ( "bug" );
// number of values stored?
long cardinality = rr . getLongCardinality ();
System . out . println ( cardinality );
// a "forEach" is faster than this loop, but a loop is possible:
for ( int i : rr ) {
System . out . println ( i );
}
}
} Дополнительные примеры см. в папке примеров, которые вы можете запустить с помощью ./gradlew :examples:runAll или запустить конкретный пример с помощью ./gradlew :examples:runExampleBitmap64 и т. д.
http://www.javadoc.io/doc/org.roaringbitmap/RoaringBitmap/
Вы можете скачать релизы с github: https://github.com/RoaringBitmap/RoaringBitmap/releases.
Добавьте следующую зависимость в ваш файл pom.xml...
< dependency >
< groupId >com.github.RoaringBitmap.RoaringBitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency >Вы можете изменить номер версии.
Затем добавьте репозиторий в файл pom.xml:
< repositories >
< repository >
< id >jitpack.io</ id >
< url >https://jitpack.io</ url >
</ repository >
</ repositories >Полный пример см. на https://github.com/RoaringBitmap/JitPackRoaringBitmapProject.
Добавьте следующую зависимость в файл pom.xml внутри элемента <dependencies> ...
< dependency >
< groupId >org.roaringbitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency > Добавьте репозиторий GitHub внутри элемента <repositories> (файл pom.xml )...
< repositories >
< repository >
< id >github</ id >
< name >Roaring Maven Packages</ name >
< url >https://maven.pkg.github.com/RoaringBitmap/RoaringBitmap</ url >
< releases >< enabled >true</ enabled ></ releases >
< snapshots >< enabled >true</ enabled ></ snapshots >
</ repository >
</ repositories >Полный пример см. на https://github.com/RoaringBitmap/MavenRoaringBitmapProject.
Доступ к реестру защищен авторизацией. Поэтому вам необходимо добавить свои учетные данные GitHub в глобальный файл settings.xml: $HOME.m2settings.xml .
Вам понадобится токен, который вы можете сгенерировать на GitHub.
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
Токену требуется разрешение на чтение: пакеты. Идентификатор токена представляет собой длинную строку, например ghp_ieOkN .
Поместите следующее в свой файл settings.xml в элемент <servers> .
< server >
< id >github</ id >
< username >lemire</ username >
< password >ghp_ieOkN</ password >
</ server > Замените lemire своим именем пользователя GitHub и ghp_ieOkN идентификатором токена, который вы только что сгенерировали.
Тогда все, что вам нужно, это отредактировать файл build.gradle следующим образом:
plugins {
id ' java '
}
group ' org.roaringbitmap ' // name of your project
version ' 1.0-SNAPSHOT ' // version of your project
repositories {
mavenCentral()
maven {
url ' https://jitpack.io '
}
}
dependencies {
implementation ' com.github.RoaringBitmap.RoaringBitmap:roaringbitmap:1.3.16 '
testImplementation ' junit:junit:3.8.1 '
}Полный пример см. на https://github.com/RoaringBitmap/JitPackRoaringBitmapProject.
Сначала вам потребуются учетные данные GitHub. Перейти к
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
И создайте токен с разрешением read:packages.
Если ваше имя пользователя GitHub — lemire и ваш личный токен GitHub ghp_ieOkN , вы можете установить их с помощью системных переменных. В bash это можно сделать так:
export GITHUB_USER=lemire
export GITHUB_PASSWORD=ghp_ieOkN
Если вы предпочитаете, вы можете записать свои учетные данные GitHub в файл gradle.properties.
# gradle.properties
githubUser=lemire
githubPassword=ghp_ieOkN
Тогда все, что вам нужно, это отредактировать файл build.gradle следующим образом:
plugins {
id ' java '
}
group ' org.roaringbitmap ' // name of your project
version ' 1.0-SNAPSHOT ' // version of your project
repositories {
mavenCentral()
maven {
url ' https://maven.pkg.github.com/RoaringBitmap/RoaringBitmap '
credentials {
username = System . properties[ ' githubUser ' ] ?: System . env . GITHUB_USER
password = System . properties[ ' githubPassword ' ] ?: System . env . GITHUB_PASSWORD
}
}
}
dependencies {
implementation ' org.roaringbitmap:roaringbitmap:1.3.16 '
testImplementation ' junit:junit:3.8.1 '
}Полный пример см. на https://github.com/RoaringBitmap/MavenRoaringBitmapProject.
В Java отсутствуют собственные целые числа без знака, но целые числа по-прежнему считаются беззнаковыми в Roaring и упорядочиваются в соответствии с Integer.compareUnsigned . Это означает, что Java упорядочит числа следующим образом: 0, 1, ..., 2147483647, -2147483648, -2147483647,..., -1. Для правильной интерпретации вы можете использовать Integer.toUnsignedLong и Integer.toUnsignedString .
Если вы хотите, чтобы ваши растровые изображения находились в файлах, отображаемых в памяти, вместо этого вы можете использовать пакет org.roaringbitmap.buffer. Он содержит два важных класса: ImmutableRoaringBitmap и MutableRoaringBitmap. MutableRoaringBitmaps являются производными от ImmutableRoaringBitmap, поэтому вы можете преобразовать (привести) MutableRoaringBitmap в ImmutableRoaringBitmap за постоянное время.
ImmutableRoaringBitmap, который не является экземпляром MutableRoaringBitmap, поддерживается ByteBuffer, что приводит к некоторым издержкам производительности, но с дополнительной гибкостью, позволяющей данным находиться где угодно (в том числе за пределами кучи Java).
Иногда вам может потребоваться работать с растровыми изображениями, расположенными на диске (экземпляры ImmutableRoaringBitmap), и растровыми изображениями, расположенными в памяти Java. Если вы знаете, что растровые изображения будут находиться в памяти Java, лучше всего использовать экземпляры MutableRoaringBitmap: они не только смогут быть изменены, но и будут работать быстрее. Более того, поскольку экземпляры MutableRoaringBitmap также являются экземплярами ImmutableRoaringBitmap, вы можете написать большую часть своего кода, ожидая ImmutableRoaringBitmap.
Если вы пишете свой код с ожиданием экземпляров ImmutableRoaringBitmap, не пытаясь приводить экземпляры, тогда ваши объекты будут действительно неизменяемыми. MutableRoaringBitmap имеет удобный метод (toImmutableRoaringBitmap), который представляет собой простой возврат к экземпляру ImmutableRoaringBitmap. С точки зрения языкового дизайна экземпляры класса ImmutableRoaringBitmap являются неизменяемыми только при использовании в соответствии с интерфейсом класса ImmutableRoaringBitmap. Учитывая, что класс не является финальным, его экземпляры можно изменять через другие интерфейсы. Таким образом, мы воспринимаем термин «неизменяемый» не в пуристском смысле, а скорее в практическом.
Одна из наших мотиваций для этой конструкции, в которой экземпляры MutableRoaringBitmap могут быть преобразованы в экземпляры ImmutableRoaringBitmap, заключается в том, что растровые изображения часто имеют большой размер или используются в контексте, где следует избегать выделения памяти, поэтому мы избегаем принудительного копирования. Копии можно ожидать, если нужно смешивать и сопоставлять экземпляры ImmutableRoaringBitmap и MutableRoaringBitmap.
В следующем примере кода показано, как создать ImmutableRoaringBitmap из ByteBuffer. В таких случаях конструктор загружает только метаданные в ОЗУ, в то время как к фактическим данным осуществляется доступ из ByteBuffer по требованию.
import org . roaringbitmap . buffer .*;
//...
MutableRoaringBitmap rr1 = MutableRoaringBitmap . bitmapOf ( 1 , 2 , 3 , 1000 );
MutableRoaringBitmap rr2 = MutableRoaringBitmap . bitmapOf ( 2 , 3 , 1010 );
ByteArrayOutputStream bos = new ByteArrayOutputStream ();
DataOutputStream dos = new DataOutputStream ( bos );
// If there were runs of consecutive values, you could
// call rr1.runOptimize(); or rr2.runOptimize(); to improve compression
rr1 . serialize ( dos );
rr2 . serialize ( dos );
dos . close ();
ByteBuffer bb = ByteBuffer . wrap ( bos . toByteArray ());
ImmutableRoaringBitmap rrback1 = new ImmutableRoaringBitmap ( bb );
bb . position ( bb . position () + rrback1 . serializedSizeInBytes ());
ImmutableRoaringBitmap rrback2 = new ImmutableRoaringBitmap ( bb ); В качестве альтернативы мы можем сериализовать непосредственно в ByteBuffer с помощью метода serialize(ByteBuffer) .
Операции с ImmutableRoaringBitmap, такие как and или xor, переворот, создают RoaringBitmap, который находится в оперативной памяти. Как следует из названия, сам ImmutableRoaringBitmap не может быть изменен.
Этот дизайн был вдохновлен Apache Druid.
Полный рабочий пример можно найти в тестовом файле TestMemoryMapping.java.
Обратите внимание: не следует смешивать классы из пакета org.roaringbitmap с классами из пакета org.roaringbitmap.buffer. Они несовместимы. Однако они сериализуются на один и тот же результат. Производительность кода в пакете org.roaringbitmap обычно выше, поскольку отсутствуют накладные расходы из-за использования экземпляров ByteBuffer.
В общем, небезопасно получать доступ к одним и тем же растровым изображениям с использованием разных потоков — растровые изображения не синхронизированы по производительности. Если вы хотите получить доступ к растровому изображению из нескольких потоков, вам следует обеспечить синхронизацию. Однако вы можете получить доступ к неизменяемому растровому изображению из нескольких потоков, если соблюдаете интерфейс ImmutableBitmapDataProvider .
Многие приложения используют Kryo для сериализации/десериализации. Растровые изображения Roaring можно эффективно использовать с Kryo благодаря специальному сериализатору (Kryo 5):
public class RoaringSerializer extends Serializer < RoaringBitmap > {
@ Override
public void write ( Kryo kryo , Output output , RoaringBitmap bitmap ) {
try {
bitmap . serialize ( new KryoDataOutput ( output ));
} catch ( IOException e ) {
e . printStackTrace ();
throw new RuntimeException ();
}
}
@ Override
public RoaringBitmap read ( Kryo kryo , Input input , Class <? extends RoaringBitmap > type ) {
RoaringBitmap bitmap = new RoaringBitmap ();
try {
bitmap . deserialize ( new KryoDataInput ( input ));
} catch ( IOException e ) {
e . printStackTrace ();
throw new RuntimeException ();
}
return bitmap ;
}
} Хотя Roaring Bitmaps были разработаны с учетом 32-битного случая, у нас есть расширения для 64-битных целых чисел. Для этой цели мы предлагаем два класса: Roaring64NavigableMap и Roaring64Bitmap .
Roaring64NavigableMap основан на обычном красно-черном дереве. Ключи представляют собой 32-битные целые числа, представляющие наиболее значимые 32 бита элементов, тогда как значения дерева представляют собой 32-битные растровые изображения Roaring. 32-битные растровые изображения Roaring представляют собой младшие биты набора элементов.
Новый подход Roaring64Bitmap основан на структуре данных ART для хранения пары ключ/значение. Ключ состоит из старших 48-битных элементов, тогда как значения представляют собой 16-битные контейнеры Roaring. Он основан на книге Лейса и др. «Адаптивное корневое дерево: ARTful индексирование для баз данных в основной памяти». (ICDE '13).
import org . roaringbitmap . longlong .*;
// first Roaring64NavigableMap
LongBitmapDataProvider r = Roaring64NavigableMap . bitmapOf ( 1 , 2 , 100 , 1000 );
r . addLong ( 1234 );
System . out . println ( r . contains ( 1 )); // true
System . out . println ( r . contains ( 3 )); // false
LongIterator i = r . getLongIterator ();
while ( i . hasNext ()) System . out . println ( i . next ());
// second Roaring64Bitmap
bitmap1 = new Roaring64Bitmap ();
bitmap2 = new Roaring64Bitmap ();
int k = 1 << 16 ;
long i = Long . MAX_VALUE / 2 ;
long base = i ;
for (; i < base + 10000 ; ++ i ) {
bitmap1 . add ( i * k );
bitmap2 . add ( i * k );
}
b1 . and ( bitmap2 );Указана сериализация 64-битных растровых изображений Roaring: см. https://github.com/RoaringBitmap/RoaringFormatSpec#extention-for-64-bit-implementations.
Однако это реализуется только Roaring64NavigableMap путем переключения:
Roaring64NavigableMap.SERIALIZATION_MODE = Roaring64NavigableMap.SERIALIZATION_MODE_PORTABLE
RangeBitmap — это краткая структура данных, поддерживающая запросы диапазона. Каждое значение, добавляемое в растровое изображение, связано с инкрементным идентификатором, и запросы создают RoaringBitmap идентификаторов, связанных со значениями, которые удовлетворяют запросу. Каждое значение, добавленное в растровое изображение, сохраняется отдельно, поэтому, если значение добавляется дважды, оно будет сохранено дважды, а если это значение меньше некоторого порога, в результирующем RoaringBitmap будет как минимум два целых числа.
Более эффективно (как с точки зрения времени, так и с точки зрения пространства) обеспечить максимальную ценность. Если вы не знаете максимальное значение, укажите Long.MAX_VALUE . Беззнаковый порядок используется так же, как и везде в библиотеке.
var appender = RangeBitmap . appender ( 1_000_000 );
appender . add ( 1L );
appender . add ( 1L );
appender . add ( 100_000L );
RangeBitmap bitmap = appender . build ();
RoaringBitmap lessThan5 = bitmap . lt ( 5 ); // {0,1}
RoaringBitmap greaterThanOrEqualTo1 = bitmap . gte ( 1 ); // {0, 1, 2}
RoaringBitmap greaterThan1 = bitmap . gt ( 1 ); // {2}
RoaringBitmap equalTo1 = bitmap . eq ( 1 ); // {0, 1}
RoaringBitmap notEqualTo1 = bitmap . neq ( 1 ); // {2} RangeBitmap можно записать на диск и отобразить в памяти:
var appender = RangeBitmap . appender ( 1_000_000 );
appender . add ( 1L );
appender . add ( 1L );
appender . add ( 100_000L );
ByteBuffer buffer = mapBuffer ( appender . serializedSizeInBytes ());
appender . serialize ( buffer );
RangeBitmap bitmap = RangeBitmap . map ( buffer );Формат сериализации использует порядок байтов с прямым порядком байтов.
Получить Java
./gradlew assemble скомпилирует
./gradlew build скомпилирует и запустит модульные тесты.
./gradlew test запустит тесты
./gradlew :roaringbitmap:test --tests TestIterators.testIndexIterator4 запускает только тест TestIterators.testIndexIterator4 ; ./gradlew -i :roaringbitmap:test --tests TestRoaringBitmap.issue623 запускает только тест issue623 в классе TestRoaringBitmap при выводе на консоль.
./gradlew bsi:test --tests BufferBSITest.testEQ запустить только тест BufferBSITest.testEQ в подмодуле bsi
Если вы планируете внести свой вклад в RoaringBitmap, вы можете загрузить его в свою любимую IDE.
Вклады приветствуются. Мы используем стиль Google Java (см. roaring_google_checks.xml ). Его можно автоматически применить к вашему коду с помощью ./gradlew spotlessApply
Пожалуйста, не переформатируйте код без необходимости (особенно в комментариях/javadoc).
В сериализованных файлах часть первых 4 байтов отведена «cookie», который служит для указания формата файла.
Если вы попытаетесь десериализовать или сопоставить растровое изображение из данных, содержащих нераспознанный файл cookie, код прервет процесс и сообщит об ошибке.
Эта проблема возникнет у всех пользователей, которые сериализовали растровые изображения Roaring с использованием версий до 0.4.x, при обновлении до версии 0.4.x или выше. Этим пользователям необходимо обновить свои сериализованные растровые изображения.
Если задано N целых чисел в [0,x), то сериализованный размер в байтах растрового изображения Roaring никогда не должен превышать эту границу:
8 + 9 * ((long)x+65535)/65536 + 2 * N
То есть, учитывая фиксированные накладные расходы на размер юниверса (x), растровые изображения Roaring никогда не используют более 2 байтов на целое число. Вы можете вызвать RoaringBitmap.maximumSerializedSize для более точной оценки.
Не существует такой вещи, как структура данных, которая всегда была бы идеальной. Вы должны убедиться, что растровые изображения Roaring соответствуют профилю вашего приложения. Есть как минимум два случая, когда растровые изображения Roaring можно легко заменить более совершенными альтернативами с точки зрения сжатия:
У вас мало случайных значений, охватывающих большой интервал (т. е. у вас очень разреженный набор). Например, возьмем набор 0, 65536, 131072, 196608, 262144... Если это типично для вашего приложения, вы можете рассмотреть возможность использования HashSet или простого отсортированного массива.
У вас есть плотный набор случайных значений, которые никогда не образуют серии непрерывных значений. Например, рассмотрим набор 0,2,4,...,10000. Если это типично для вашего приложения, возможно, вам лучше использовать обычный набор битов (например, класс BitSet в Java).
Как выбрать элемент случайным образом?
Random random = new Random();
bitmap.select(random.nextInt(bitmap.getCardinality()));
Для запуска тестов JMH используйте следующие команды:
$ ./gradlew jmh::shadowJar
$ java -jar jmh/build/libs/benchmarks.jar
Вы также можете запустить специальный тест:
$ java -jar jmh/build/libs/benchmarks.jar 'org.roaringbitmap.aggregation.and.identical.*'
Если у вас есть оболочка bash, вы также можете запустить наш скрипт, который автоматически создает и запускает определенные тесты...
$ ./jmh/run.sh 'org.roaringbitmap.aggregation.and.identical.*'
https://groups.google.com/forum/#!forum/roaringbitmaps
Работа поддержана грантом NSERC № 26143.
