RoaringBitmap
1.3.16
Bitsets, também chamados de bitmaps, são comumente usados como estruturas de dados rápidas. Infelizmente, eles podem usar muita memória. Para compensar, costumamos usar bitmaps compactados.
Roaring bitmaps são bitmaps compactados que tendem a superar os bitmaps compactados convencionais, como WAH, EWAH ou Concise. Em alguns casos, bitmaps barulhentos podem ser centenas de vezes mais rápidos e geralmente oferecem compactação significativamente melhor. Eles podem até ser mais rápidos que bitmaps não compactados.
Descobriu-se que bitmaps incríveis funcionam bem em muitas aplicações importantes:
Use Roaring para compactação de bitmap sempre que possível. Não use outros métodos de compactação de bitmap (Wang et al., SIGMOD 2017)
parabéns por fazer algo que faz meu software rodar 5x mais rápido (Charles Parker do BigML)
Esta biblioteca é usada por
A biblioteca está madura e tem sido usada na produção há muitos anos.
O mecanismo SQL do YouTube, Google Procella, usa bitmaps Roaring para indexação. Apache Lucene usa bitmaps Roaring, embora eles tenham sua própria implementação independente. Derivados de Lucene como Solr e Elastic também usam bitmaps Roaring. Outras plataformas como Whoosh, Microsoft Visual Studio Team Services (VSTS) e Pilosa também usam bitmaps Roaring com suas próprias implementações. Você encontra bitmaps Roaring em InfluxDB, Bleve, Cloud Torrent, Redpanda e assim por diante.
Existe uma especificação de formato serializado para interoperabilidade entre implementações. Temos implementações interoperáveis de C/C++, Java e Go.
(c) 2013-... os autores do RoaringBitmap
Este código está licenciado sob Licença Apache, Versão 2.0 (AL2.0).
Conjuntos são uma abstração fundamental em software. Eles podem ser implementados de várias maneiras, como conjuntos de hash, como árvores e assim por diante. Em bancos de dados e mecanismos de busca, os conjuntos costumam ser parte integrante dos índices. Por exemplo, podemos precisar manter um conjunto de todos os documentos ou linhas (representados por um identificador numérico) que satisfaçam alguma propriedade. Além de adicionar ou remover elementos do conjunto, precisamos de funções rápidas para calcular a intersecção, a união, a diferença entre conjuntos, e assim por diante.
Para implementar um conjunto de inteiros, uma estratégia particularmente atraente é o bitmap (também chamado de bitset ou vetor de bits). Usando n bits, podemos representar qualquer conjunto feito de inteiros do intervalo [0,n): o i-ésimo bit é definido como um se o inteiro i estiver presente no conjunto. Os processadores de commodities usam palavras de W=32 ou W=64 bits. Combinando muitas dessas palavras, podemos suportar valores grandes de n. Interseções, uniões e diferenças podem então ser implementadas como operações AND, OR e ANDNOT bit a bit. Funções de conjunto mais complicadas também podem ser implementadas como operações bit a bit.
Quando a abordagem de conjunto de bits é aplicável, ela pode ser muito mais rápida do que outra implementação possível de um conjunto (por exemplo, como um conjunto hash), usando várias vezes menos memória.
No entanto, um bitset, mesmo compactado, nem sempre é aplicável. Por exemplo, se você tiver 1.000 números inteiros de aparência aleatória, um array simples pode ser a melhor representação. Referimo-nos a este caso como cenário “esparso”.
Um BitSet descompactado pode usar muita memória. Por exemplo, se você pegar um BitSet e definir o bit na posição 1.000.000 como verdadeiro e tiver pouco mais de 100kB. Isso é mais de 100kB para armazenar a posição de um bit. Isso é um desperdício mesmo se você não se importa com a memória: suponha que você precise calcular a interseção entre este BitSet e outro que tenha um bit na posição 1.000.001 como verdadeiro, então você precisa passar por todos esses zeros, quer você goste ou não. Isso pode se tornar um grande desperdício.
Dito isto, definitivamente há casos em que tentar usar bitmaps compactados é um desperdício. Por exemplo, se você tiver um universo pequeno. Por exemplo, seus bitmaps representam conjuntos de inteiros de [0,n) onde n é pequeno (por exemplo, n=64 ou n=128). Se você puder usar um BitSet descompactado e ele não aumentar o uso de memória, os bitmaps compactados provavelmente não serão úteis para você. Na verdade, se você não precisa de compactação, um BitSet oferece uma velocidade notável.
O cenário esparso é outro caso de uso em que bitmaps compactados não devem ser usados. Lembre-se de que dados de aparência aleatória geralmente não são compactáveis. Por exemplo, se você tiver um pequeno conjunto de números inteiros aleatórios de 32 bits, não será matematicamente possível usar muito menos que 32 bits por número inteiro e as tentativas de compactação poderão ser contraproducentes.
A maioria das alternativas ao Roaring faz parte de uma família maior de bitmaps compactados que são bitmaps codificados em comprimento de execução. Eles identificam longas séries de 1s ou 0s e os representam com uma palavra marcadora. Se você tiver uma combinação local de 1s e 0, use uma palavra não compactada.
Existem muitos formatos nesta família:
Porém, há um grande problema com esses formatos que pode prejudicá-lo gravemente em alguns casos: não há acesso aleatório. Se você quiser verificar se um determinado valor está presente no conjunto, você tem que começar do início e "descompactar" tudo. Isso significa que se você quiser cruzar um conjunto grande com um conjunto grande, você ainda terá que descompactar todo o conjunto grande na pior das hipóteses...
Rugir resolve esse problema. Funciona da seguinte maneira. Ele divide os dados em pedaços de 2 16 inteiros (por exemplo, [0, 2 16 ), [2 16 , 2 x 2 16 ), ...). Dentro de um pedaço, ele pode usar um bitmap não compactado, uma lista simples de números inteiros ou uma lista de execuções. Qualquer que seja o formato usado, todos eles permitem verificar rapidamente a presença de qualquer valor (por exemplo, com uma pesquisa binária). O resultado líquido é que o Roaring pode computar muitas operações muito mais rápido do que formatos codificados em comprimento de execução, como WAH, EWAH, Concise... Talvez surpreendentemente, o Roaring também geralmente oferece melhores taxas de compactação.
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 );
}
}
} Consulte a pasta de exemplos para obter mais exemplos, que você pode executar com ./gradlew :examples:runAll ou executar um específico com ./gradlew :examples:runExampleBitmap64 , etc.
http://www.javadoc.io/doc/org.roaringbitmap/RoaringBitmap/
Você pode baixar versões do github: https://github.com/RoaringBitmap/RoaringBitmap/releases
Adicione a seguinte dependência ao seu arquivo pom.xml...
< dependency >
< groupId >com.github.RoaringBitmap.RoaringBitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency >Você pode ajustar o número da versão.
Em seguida, adicione o repositório ao seu arquivo pom.xml:
< repositories >
< repository >
< id >jitpack.io</ id >
< url >https://jitpack.io</ url >
</ repository >
</ repositories >Consulte https://github.com/RoaringBitmap/JitPackRoaringBitmapProject para obter um exemplo completo.
Adicione a seguinte dependência ao seu arquivo pom.xml dentro do elemento <dependencies> ...
< dependency >
< groupId >org.roaringbitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency > Adicione o repositório GitHub dentro do elemento <repositories> (arquivo 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 >Consulte https://github.com/RoaringBitmap/MavenRoaringBitmapProject para obter um exemplo completo.
O acesso ao registo está protegido por uma autorização. Portanto, você deve adicionar suas credenciais do GitHub ao seu settings.xml global: $HOME.m2settings.xml .
Você precisará de um token que pode ser gerado no GitHub.
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
O token precisa da permissão read:packages. O identificador do token é uma string longa como ghp_ieOkN .
Coloque o seguinte em seu arquivo settings.xml , dentro do elemento <servers> .
< server >
< id >github</ id >
< username >lemire</ username >
< password >ghp_ieOkN</ password >
</ server > Substitua lemire pelo seu nome de usuário do GitHub e ghp_ieOkN pelo identificador do token que você acabou de gerar.
Então tudo que você precisa é editar seu arquivo build.gradle assim:
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 '
}Consulte https://github.com/RoaringBitmap/JitPackRoaringBitmapProject para obter um exemplo completo.
Primeiro você precisa de suas credenciais do GitHub. Vá para
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
E crie um token com permissão read:packages.
Se o seu nome de usuário do GitHub for lemire e seu token pessoal do GitHub ghp_ieOkN , você poderá defini-los usando variáveis do sistema. No bash, você pode fazer assim:
export GITHUB_USER=lemire
export GITHUB_PASSWORD=ghp_ieOkN
Se preferir, você pode escrever suas credenciais do GitHub em seu arquivo gradle.properties
# gradle.properties
githubUser=lemire
githubPassword=ghp_ieOkN
Então tudo que você precisa é editar seu arquivo build.gradle assim:
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 '
}Consulte https://github.com/RoaringBitmap/MavenRoaringBitmapProject para obter um exemplo completo.
Java não possui inteiros não assinados nativos, mas os inteiros ainda são considerados não assinados no Roaring e ordenados de acordo com Integer.compareUnsigned . Isso significa que Java ordenará os números assim 0, 1, ..., 2147483647, -2147483648, -2147483647,..., -1. Para interpretar corretamente, você pode usar Integer.toUnsignedLong e Integer.toUnsignedString .
Se quiser que seus bitmaps estejam em arquivos mapeados na memória, você pode usar o pacote org.roaringbitmap.buffer. Ele contém duas classes importantes, ImmutableRoaringBitmap e MutableRoaringBitmap. MutableRoaringBitmaps são derivados de ImmutableRoaringBitmap, para que você possa converter (converter) um MutableRoaringBitmap em um ImmutableRoaringBitmap em tempo constante.
Um ImmutableRoaringBitmap que não é uma instância de um MutableRoaringBitmap é apoiado por um ByteBuffer que vem com alguma sobrecarga de desempenho, mas com a flexibilidade adicional de que os dados podem residir em qualquer lugar (inclusive fora do heap Java).
Às vezes, você pode precisar trabalhar com bitmaps que residem no disco (instâncias de ImmutableRoaringBitmap) e bitmaps que residem na memória Java. Se você sabe que os bitmaps residirão na memória Java, é melhor usar instâncias MutableRoaringBitmap, pois elas não apenas podem ser modificadas, mas também serão mais rápidas. Além disso, como as instâncias MutableRoaringBitmap também são instâncias ImmutableRoaringBitmap, você pode escrever grande parte do seu código esperando ImmutableRoaringBitmap.
Se você escrever seu código esperando instâncias de ImmutableRoaringBitmap, sem tentar converter as instâncias, seus objetos serão verdadeiramente imutáveis. O MutableRoaringBitmap possui um método de conveniência (toImmutableRoaringBitmap) que é uma conversão simples para uma instância ImmutableRoaringBitmap. Do ponto de vista do design da linguagem, as instâncias da classe ImmutableRoaringBitmap são imutáveis apenas quando usadas de acordo com a interface da classe ImmutableRoaringBitmap. Dado que a classe não é final, é possível modificar instâncias, através de outras interfaces. Assim, não tomamos o termo “imutável” de uma forma purista, mas sim de uma forma prática.
Uma de nossas motivações para este design, onde as instâncias MutableRoaringBitmap podem ser convertidas em instâncias ImmutableRoaringBitmap, é que os bitmaps geralmente são grandes ou usados em um contexto onde as alocações de memória devem ser evitadas, portanto, evitamos forçar cópias. Cópias podem ser esperadas se for necessário misturar e combinar instâncias ImmutableRoaringBitmap e MutableRoaringBitmap.
O exemplo de código a seguir ilustra como criar um ImmutableRoaringBitmap a partir de um ByteBuffer. Nesses casos, o construtor carrega apenas os metadados na RAM enquanto os dados reais são acessados a partir do ByteBuffer sob demanda.
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 ); Alternativamente, podemos serializar diretamente para um ByteBuffer com o método serialize(ByteBuffer) .
Operações em um ImmutableRoaringBitmap como and, or, xor, flip, gerarão um RoaringBitmap que fica na RAM. Como o nome sugere, o próprio ImmutableRoaringBitmap não pode ser modificado.
Este design foi inspirado no Apache Druid.
Pode-se encontrar um exemplo funcional completo no arquivo de teste TestMemoryMapping.java.
Observe que você não deve misturar as classes do pacote org.roaringbitmap com as classes do pacote org.roaringbitmap.buffer. Eles são incompatíveis. No entanto, eles serializam para a mesma saída. O desempenho do código no pacote org.roaringbitmap é geralmente superior porque não há sobrecarga devido ao uso de instâncias ByteBuffer.
Em geral, não é seguro acessar os mesmos bitmaps usando threads diferentes – os bitmaps não são sincronizados para desempenho. Caso queira acessar um Bitmap de mais de um thread, você deve fornecer sincronização. No entanto, você pode acessar um bitmap imutável de vários threads, desde que siga a interface ImmutableBitmapDataProvider .
Muitos aplicativos usam Kryo para serialização/desserialização. Pode-se usar bitmaps Roaring com Kryo de forma eficiente graças a um serializador personalizado (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 ;
}
} Embora os Roaring Bitmaps tenham sido projetados tendo em mente o caso de 32 bits, temos extensões para números inteiros de 64 bits. Oferecemos duas classes para essa finalidade: Roaring64NavigableMap e Roaring64Bitmap .
O Roaring64NavigableMap depende de uma árvore vermelha e preta convencional. As chaves são inteiros de 32 bits que representam os 32 bits mais significativos dos elementos, enquanto os valores da árvore são bitmaps Roaring de 32 bits. Os bitmaps Roaring de 32 bits representam os bits menos significativos de um conjunto de elementos.
A abordagem Roaring64Bitmap mais recente depende da estrutura de dados ART para manter o par chave/valor. A chave é composta pelos elementos mais significativos de 48 bits, enquanto os valores são contêineres Roaring de 16 bits. É inspirado em The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases de Leis et al. (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 );A serialização de bitmaps Roaring de 64 bits é especificada: consulte https://github.com/RoaringBitmap/RoaringFormatSpec#extention-for-64-bit-implementations
No entanto, é implementado apenas por Roaring64NavigableMap , alternando:
Roaring64NavigableMap.SERIALIZATION_MODE = Roaring64NavigableMap.SERIALIZATION_MODE_PORTABLE
RangeBitmap é uma estrutura de dados sucinta que suporta consultas de intervalo. Cada valor adicionado ao bitmap é associado a um identificador incremental e as consultas produzem um RoaringBitmap dos identificadores associados aos valores que satisfazem a consulta. Cada valor adicionado ao bitmap é armazenado separadamente, de modo que se um valor for adicionado duas vezes, ele será armazenado duas vezes, e se esse valor for menor que algum limite, haverá pelo menos dois números inteiros no RoaringBitmap resultante.
É mais eficiente – tanto em termos de tempo como de espaço – proporcionar um valor máximo. Se você não souber o valor máximo, forneça Long.MAX_VALUE . A ordem não assinada é usada como em qualquer outro lugar da biblioteca.
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 pode ser gravado em disco e mapeado na memória:
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 );O formato de serialização usa ordem de bytes little endian.
Obtenha java
./gradlew assemble irá compilar
./gradlew build irá compilar e executar os testes de unidade
./gradlew test executará os testes
./gradlew :roaringbitmap:test --tests TestIterators.testIndexIterator4 executa apenas o teste TestIterators.testIndexIterator4 ; ./gradlew -i :roaringbitmap:test --tests TestRoaringBitmap.issue623 executa apenas o teste issue623 na classe TestRoaringBitmap enquanto imprime no console.
./gradlew bsi:test --tests BufferBSITest.testEQ execute apenas o teste BufferBSITest.testEQ no submódulo bsi
Se você planeja contribuir com o RoaringBitmap, você pode carregá-lo em seu IDE favorito.
Contribuições são convidadas. Usamos o estilo Google Java (consulte roaring_google_checks.xml ). Ele pode ser aplicado automaticamente ao seu código com ./gradlew spotlessApply
Por favor, não reformate o código desnecessariamente (especialmente em comentários/javadoc).
Nos arquivos serializados, parte dos primeiros 4 bytes é dedicada a um “cookie” que serve para indicar o formato do arquivo.
Se você tentar desserializar ou mapear um bitmap de dados que possuem um "cookie" não reconhecido, o código abortará o processo e reportará um erro.
Esse problema ocorrerá com todos os usuários que serializaram bitmaps Roaring usando versões anteriores à 0.4.x à medida que atualizam para a versão 0.4.x ou superior. Esses usuários precisam atualizar seus bitmaps serializados.
Dados N inteiros em [0,x), então o tamanho serializado em bytes de um bitmap Roaring nunca deve exceder este limite:
8 + 9 * ((long)x+65535)/65536 + 2 * N
Ou seja, dada uma sobrecarga fixa para o tamanho do universo (x), os bitmaps Roaring nunca usam mais de 2 bytes por inteiro. Você pode chamar RoaringBitmap.maximumSerializedSize para obter uma estimativa mais precisa.
Não existe uma estrutura de dados que seja sempre ideal. Você deve certificar-se de que os bitmaps Roaring se ajustem ao perfil do seu aplicativo. Existem pelo menos dois casos em que bitmaps Roaring podem ser facilmente substituídos por alternativas superiores em termos de compactação:
Você tem poucos valores aleatórios abrangendo um intervalo grande (ou seja, você tem um conjunto muito esparso). Por exemplo, pegue o conjunto 0, 65536, 131072, 196608, 262144... Se isso for típico do seu aplicativo, você pode considerar usar um HashSet ou um array ordenado simples.
Você tem um conjunto denso de valores aleatórios que nunca formam execuções de valores contínuos. Por exemplo, considere o conjunto 0,2,4,...,10000. Se isso for típico de sua aplicação, você poderá se beneficiar melhor com um bitset convencional (por exemplo, a classe BitSet do Java).
Como seleciono um elemento aleatoriamente?
Random random = new Random();
bitmap.select(random.nextInt(bitmap.getCardinality()));
Para executar benchmarks JMH, use os seguintes comandos:
$ ./gradlew jmh::shadowJar
$ java -jar jmh/build/libs/benchmarks.jar
Você também pode executar um benchmark específico:
$ java -jar jmh/build/libs/benchmarks.jar 'org.roaringbitmap.aggregation.and.identical.*'
Se você possui um shell bash, também pode executar nosso script que cria e executa testes específicos automaticamente...
$ ./jmh/run.sh 'org.roaringbitmap.aggregation.and.identical.*'
https://groups.google.com/forum/#!forum/roaringbitmaps
Este trabalho foi apoiado pela concessão NSERC número 26143.
