RoaringBitmap
1.3.16
ビットセット (ビットマップとも呼ばれます) は、高速データ構造として一般に使用されます。残念ながら、メモリを過剰に使用する可能性があります。これを補うために、圧縮されたビットマップがよく使用されます。
Roaring ビットマップは、WAH、EWAH、Concise などの従来の圧縮ビットマップよりも優れたパフォーマンスを発揮する傾向のある圧縮ビットマップです。場合によっては、轟音ビットマップは数百倍高速になることがあり、多くの場合、圧縮率が大幅に向上します。非圧縮ビットマップよりも高速な場合もあります。
Roaring ビットマップは、多くの重要なアプリケーションでうまく機能することがわかっています。
ビットマップ圧縮には可能な限り Roaring を使用してください。他のビットマップ圧縮方法は使用しないでください (Wang et al.、SIGMOD 2017)
ソフトウェアを 5 倍高速に実行できるものを作成したことを称賛します (BigML の Charles Parker)
このライブラリを使用しているのは、
このライブラリは成熟しており、長年実稼働環境で使用されてきました。
YouTube SQL エンジンである Google Procella は、インデックス作成に Roaring ビットマップを使用します。 Apache Lucene は Roaring ビットマップを使用しますが、独自の独立した実装があります。 Solr や Elastic などの Lucene の派生製品も Roaring ビットマップを使用します。 Whoosh、Microsoft Visual Studio Team Services (VSTS)、Pilosa などの他のプラットフォームも、独自の実装で Roaring ビットマップを使用します。 Roaring ビットマップは、InfluxDB、Bleve、Cloud Torrent、Redpanda などで見つかります。
実装間の相互運用性のためにシリアル化された形式の仕様があります。相互運用可能な C/C++、Java、Go の実装があります。
(c) 2013-...RoaringBitmap 作者
このコードは、Apache License、バージョン 2.0 (AL2.0) に基づいてライセンスされています。
セットはソフトウェアにおける基本的な抽象化です。これらは、ハッシュ セットやツリーなど、さまざまな方法で実装できます。データベースや検索エンジンでは、多くの場合、セットはインデックスの不可欠な部分です。たとえば、何らかのプロパティを満たすすべてのドキュメントまたは行 (数値識別子で表される) のセットを維持する必要がある場合があります。セットに要素を追加または削除するだけでなく、セット間の共通部分、和集合、差分などを計算する高速関数が必要です。
整数のセットを実装するための特に魅力的な戦略は、ビットマップ (ビットセットまたはビット ベクトルとも呼ばれます) です。 n ビットを使用すると、範囲 [0,n) の整数で構成される任意のセットを表すことができます。整数 i がセット内に存在する場合、i 番目のビットは 1 に設定されます。コモディティプロセッサは、W=32 ビットまたは W=64 ビットのワードを使用します。このような単語を多数組み合わせることで、n の大きな値をサポートできます。交差、和集合、および差分は、ビットごとの AND、OR、および ANDNOT 演算として実装できます。より複雑な集合関数もビット単位の演算として実装できます。
ビットセット手法を適用できる場合、メモリ使用量を数分の 1 に抑えながら、他の可能なセット実装 (ハッシュ セットなど) よりも桁違いに高速になる可能性があります。
ただし、ビットセットは、たとえ圧縮されたものであっても、常に適用できるわけではありません。たとえば、ランダムに見える整数が 1000 個ある場合、単純な配列が最適な表現になる可能性があります。このケースを「スパース」シナリオと呼びます。
非圧縮 BitSet は大量のメモリを使用する可能性があります。たとえば、BitSet を取得し、位置 1,000,000 のビットを true に設定し、100kB を少し超えるとします。 1 ビットの位置を保存するには 100kB を超えます。メモリを気にしない場合でも、これは無駄です。この BitSet と、位置 1,000,001 のビットが true である別の BitSet との交差を計算する必要があるとします。その場合、好むと好まざるとにかかわらず、これらのゼロをすべて調べる必要があります。か否か。それは非常に無駄になる可能性があります。
そうは言っても、圧縮されたビットマップを使用しようとすることが無駄である場合が決定的にあります。たとえば、ユニバースのサイズが小さい場合です。たとえば、ビットマップは [0,n) からの整数のセットを表します。ここで、n は小さいです (たとえば、n=64 または n=128)。非圧縮 BitSet を使用でき、メモリ使用量が大幅に増加しない場合は、圧縮ビットマップはおそらく役に立ちません。実際、圧縮が必要ない場合、BitSet は驚くべき速度を提供します。
スパース シナリオは、圧縮ビットマップを使用すべきではないもう 1 つの使用例です。ランダムに見えるデータは通常、圧縮できないことに注意してください。たとえば、32 ビットのランダムな整数の小さなセットがある場合、整数あたり 32 ビットよりはるかに少ない値を使用することは数学的に不可能であり、圧縮を試みると逆効果になる可能性があります。
Roaring の代替手段のほとんどは、ランレングス エンコードされたビットマップである圧縮ビットマップの大きなファミリーの一部です。 1 または 0 の長い連続を識別し、それらをマーカー ワードで表します。 1 と 0 がローカルに混在している場合は、非圧縮ワードを使用します。
このファミリーには多くの形式があります。
ただし、これらの形式には、場合によっては重大な損害を与える可能性がある大きな問題があります。それは、ランダム アクセスがないことです。指定された値がセット内に存在するかどうかを確認したい場合は、最初から始めて全体を「解凍」する必要があります。これは、大きなセットを大きなセットと交差させたい場合、最悪の場合でも大きなセット全体を圧縮解除する必要があることを意味します...
轟音はこの問題を解決します。それは次のように動作します。データを 2 16 個の整数のチャンクに分割します (例: [0, 2 16 )、[2 16 、2 x 2 16 ]、...)。チャンク内では、非圧縮ビットマップ、整数の単純なリスト、または実行のリストを使用できます。使用する形式が何であれ、それらはすべて、1 つの値の存在を迅速にチェックすることを可能にします (たとえば、二分探索を使用)。最終的な結果として、Roaring は、WAH、EWAH、Concise などのランレングス エンコード形式よりもはるかに高速に多くの演算を計算できるようになります。おそらく驚くべきことに、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 > <repositories>要素 ( pom.xmlファイル) 内に GitHub リポジトリを追加します...
< 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
トークンには read:packages 権限が必要です。トークン識別子は、 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 という 2 つの重要なクラスが含まれています。 MutableRoaringBitmap は ImmutableRoaringBitmap から派生しているため、一定時間で MutableRoaringBitmap を ImmutableRoaringBitmap に変換 (キャスト) できます。
MutableRoaringBitmap のインスタンスではない ImmutableRoaringBitmap は、ある程度のパフォーマンス オーバーヘッドを伴う ByteBuffer によってサポートされますが、データをどこにでも (Java ヒープの外側を含む) 常駐できるという柔軟性が追加されています。
場合によっては、ディスク上に存在するビットマップ (ImmutableRoaringBitmap のインスタンス) や Java メモリ内に存在するビットマップを操作する必要がある場合があります。ビットマップが Java メモリに常駐することがわかっている場合は、MutableRoaringBitmap インスタンスを使用するのが最適です。変更できるだけでなく、処理速度も向上します。さらに、MutableRoaringBitmap インスタンスは ImmutableRoaringBitmap インスタンスでもあるため、コードの多くは ImmutableRoaringBitmap を想定して作成できます。
インスタンスをキャストせずに、ImmutableRoaringBitmap インスタンスを想定してコードを作成すると、オブジェクトは真に不変になります。 MutableRoaringBitmap には、ImmutableRoaringBitmap インスタンスに単純にキャストバックする便利なメソッド (toImmutableRoaringBitmap) があります。言語設計の観点から見ると、ImmutableRoaringBitmap クラスのインスタンスは、ImmutableRoaringBitmap クラスのインターフェイスに従って使用される場合にのみ不変になります。クラスが最終的なものではない場合、他のインターフェイスを通じてインスタンスを変更することができます。したがって、私たちは「不変」という用語を純粋な意味ではなく、実際的な意味で捉えています。
MutableRoaringBitmap インスタンスを ImmutableRoaringBitmap インスタンスにキャストできるこの設計の動機の 1 つは、ビットマップが大きいことが多いか、メモリ割り当てを避けるべきコンテキストで使用されることが多いため、コピーの強制を避けることです。 ImmutableRoaringBitmap インスタンスと MutableRoaringBitmap インスタンスを組み合わせて一致させる必要がある場合、コピーが期待される可能性があります。
次のコード サンプルは、ByteBuffer から ImmutableRoaringBitmap を作成する方法を示しています。このような場合、コンストラクターはメタデータのみを RAM にロードし、実際のデータはオンデマンドで 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 );あるいは、 serialize(ByteBuffer)メソッドを使用してByteBufferに直接シリアル化することもできます。
and、or、xor、flip などの ImmutableRoaringBitmap に対する操作は、RAM 内にある RoaringBitmap を生成します。名前が示すように、ImmutableRoaringBitmap 自体は変更できません。
このデザインは Apache Druid からインスピレーションを得たものです。
完全な動作例は、テスト ファイル TestMemoryMapping.java にあります。
org.roaringbitmap パッケージのクラスと org.roaringbitmap.buffer パッケージのクラスを混合しないでください。それらは互換性がありません。ただし、これらは同じ出力にシリアル化されます。 ByteBuffer インスタンスの使用によるオーバーヘッドがないため、org.roaringbitmap パッケージのコードのパフォーマンスは一般に優れています。
一般に、異なるスレッドを使用して同じビットマップにアクセスするのは安全ではありません。ビットマップはパフォーマンスのために同期されていません。複数のスレッドからビットマップにアクセスしたい場合は、同期を提供する必要があります。ただし、 ImmutableBitmapDataProviderインターフェイスに従っている限り、複数のスレッドから不変ビットマップにアクセスできます。
多くのアプリケーションはシリアル化/逆シリアル化に Kryo を使用します。カスタム シリアライザー (Kryo 5) のおかげで、Kryo で Roaring ビットマップを効率的に使用できます。
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 Bitmap は 32 ビットの場合を念頭に置いて設計されていますが、64 ビット整数への拡張機能もあります。この目的のために、 Roaring64NavigableMapとRoaring64Bitmap 2 つのクラスを提供します。
Roaring64NavigableMap従来の赤黒ツリーに依存しています。キーは要素の最上位 32 ビットを表す 32 ビット整数ですが、ツリーの値は 32 ビット Roaring ビットマップです。 32 ビットの Roaring ビットマップは、要素セットの最下位ビットを表します。
新しいRoaring64Bitmapアプローチは、キーと値のペアを保持するために ART データ構造に依存します。キーは要素の最上位 48 ビットで構成されますが、値は 16 ビットの Roaring コンテナーです。これは、Leis らの『The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases』からインスピレーションを得ています。 (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生成します。ビットマップに追加されるすべての値は個別に保存されるため、値が 2 回追加されると、その値も 2 回保存され、その値が何らかのしきい値より小さい場合、結果として得られるRoaringBitmapには少なくとも 2 つの整数が含まれます。
最大値を提供する方が、時間的にもスペース的にも効率的です。最大値がわからない場合は、 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 、コンソールへの出力中に、クラスTestRoaringBitmap内のテストissue623のみを実行します。
./gradlew bsi:test --tests BufferBSITest.testEQ bsiサブモジュールでテストBufferBSITest.testEQのみを実行します。
RoaringBitmap に貢献する予定がある場合は、お気に入りの IDE にロードできます。
寄付を募集しています。 Google Java スタイルを使用します ( roaring_google_checks.xmlを参照)。 ./gradlew spotlessApplyを使用してコードに自動的に適用できます。
コードを不必要に再フォーマットしないでください (特にコメント/javadoc)。
シリアル化されたファイルでは、最初の 4 バイトの一部がファイル形式を示す「Cookie」専用になります。
認識できない「Cookie」を含むデータからビットマップを逆シリアル化またはマッピングしようとすると、コードはプロセスを中止し、エラーを報告します。
この問題は、0.4.x より前のバージョンを使用して Roaring ビットマップをシリアル化したすべてのユーザーが、バージョン 0.4.x 以降にアップグレードするときに発生します。これらのユーザーはシリアル化されたビットマップを更新する必要があります。
[0,x) に N の整数が指定されている場合、Roaring ビットマップのシリアル化されたサイズ (バイト単位) はこの境界を超えてはなりません。
8 + 9 * ((long)x+65535)/65536 + 2 * N
つまり、ユニバース サイズ (x) の固定オーバーヘッドを考慮すると、ローリング ビットマップは整数あたり 2 バイトを超えることはありません。より正確な推定のために、 RoaringBitmap.maximumSerializedSizeを呼び出すことができます。
常に理想的なデータ構造などというものはありません。 Roaring ビットマップがアプリケーション プロファイルに適合することを確認する必要があります。 Roaring ビットマップが圧縮の観点から優れた代替案に簡単に置き換えられるケースが少なくとも 2 つあります。
大きな間隔にまたがるランダムな値がほとんどない (つまり、非常にまばらなセットがある)。たとえば、セット 0、65536、131072、196608、262144 ... を例に挙げます。これがアプリケーションの典型的なものである場合は、HashSet または単純なソート配列の使用を検討してください。
連続値の連続を決して形成しない、高密度のランダム値のセットがあります。たとえば、セット 0,2,4,...,10000 について考えてみましょう。これがアプリケーションの典型的なものである場合は、従来のビットセット (Java の BitSet クラスなど) を使用した方が適切な場合があります。
要素をランダムに選択するにはどうすればよいですか?
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 によって支援されました。
