search

RoaringBitmap / RoaringFormatSpec

Specification of the compressed-bitmap Roaring format
http://roaringbitmap.org/
Apache License 2.0
152 stars 15 forks source link

readme

RoaringFormatSpec : specification of the compressed-bitmap Roaring formats

Standard 32-bit Roaring Bitmap

Roaring bitmaps are used by several important systems:

Many of these systems use the following interoperable format.

This specification assumes that you are familiar with Roaring bitmaps. Please refer to the following paper for details on the design rationale:

Let us recap that Roaring bitmaps are designed to store sets of 32-bit (unsigned) integers. Thus a Roaring bitmap can contain up to 4294967296 integers. They are made of three types of 16-bit containers: array, bitset and run containers. There are between 1 and 65536 (inclusively) containers. Each container has a cardinality (value in [1, 65536]), and it has a 16-bit most significant value (also called "key") in [0,65536). All containers are non-empty.

General layout

All words are written using little endian encoding.

The layout is designed so that random access to the data is possible without materializing the bitmap in memory while being storage efficient.

Throughout, we use the following constants :

The below diagram represents a storage file containing both run containers and the offset header.

Format diagram

1. Cookie header

The cookie header spans either 64 bits or 32 bits followed by a variable number of bytes.

  1. If the first 32 bits take the value SERIAL_COOKIE_NO_RUNCONTAINER, then no container part of the Roaring bitmap can be of type "run" (only array and bitset containers are allowed). When the cookie has this particular value, the next 32 bits are used to store an integer representing the number of containers. If the bitmap is empty (i.e., it has no container), then you should choose this cookie header. In this scenario, the cookie header uses 64 bits.
  2. The 16 least significant bits of the 32-bit cookie have value SERIAL_COOKIE. In that case, the 16 most significant bits of the 32-bit cookie are used to store the number of containers minus 1. That is, if you shift right by 16 the cookie and add 1, you get the number of containers. Let size be the number of containers. Then we store (size + 7) / 8 bytes, following the initial 32 bits, as a bitset to indicate whether each of the containers is a run container (bit set to 1) or not (bit set to 0). The first (least significant) bit of the first byte corresponds to the first stored container and so forth. In this scenario, the cookie header uses 32 bits followed by (size + 7) / 8 bytes.

Thus it follows that the least significant 16 bits of the first 32 bits of a serialized bitmaps should either have the value SERIAL_COOKIE_NO_RUNCONTAINER or the value SERIAL_COOKIE. In other cases, we should abort the decoding.

After scanning the cookie header, we know how many containers are present in the bitmap.

2. Descriptive header

The cookie header is followed by a descriptive header. For each container, we store the key (16 most significant bits) along with the cardinality minus 1, using 16 bits for each value (for a total of 32 bits per container).

Thus, if there are x containers, the descriptive header will contain 32 x bits or 4 x bytes.

After scanning the descriptive header, we know the type of each container. Indeed, if the cookie took value SERIAL_COOKIE, then we had a bitset telling us which containers are run containers; otherwise, we know that there are no run containers. For the containers that are not run containers, then we use the cardinality to determine the type: a cardinality of up and including 4096 indicates an array container whereas a cardinality above 4096 indicates a bitset container.

3. Offset header

If and only if one of these is true

  1. the cookie takes value SERIAL_COOKIE_NO_RUNCONTAINER
  2. the cookie takes the value SERIAL_COOKIE and there are at least NO_OFFSET_THRESHOLD containers,

then we store (using a 32-bit value) the location (in bytes) of the container from the beginning of the stream (starting with the cookie) for each container.

4. Container storage

The containers are then stored one after the other.

Testing

At a minimum, all Roaring implementations should be able to parse the two files in the testdata directory, see the associated README.md file found in the directory.

Reference implementations

Sample Java source code


    int startOffset = 0;
    boolean hasrun = hasRunContainer();
    if (hasrun) {
      out.writeInt(Integer.reverseBytes(SERIAL_COOKIE | ((size - 1) << 16)));
      byte[] bitmapOfRunContainers = new byte[(size + 7) / 8];
      for (int i = 0; i < size; ++i) {
        if (this.values[i] instanceof RunContainer) {
          bitmapOfRunContainers[i / 8] |= (1 << (i % 8));
        }
      }
      out.write(bitmapOfRunContainers);
      if (this.size < NO_OFFSET_THRESHOLD) {
        startOffset = 4 + 4 * this.size + bitmapOfRunContainers.length;
      } else {
        startOffset = 4 + 8 * this.size + bitmapOfRunContainers.length;
      }
    } else { // backwards compatibility
      out.writeInt(Integer.reverseBytes(SERIAL_COOKIE_NO_RUNCONTAINER));
      out.writeInt(Integer.reverseBytes(size));
      startOffset = 4 + 4 + 4 * this.size + 4 * this.size;
    }
    for (int k = 0; k < size; ++k) {
      out.writeShort(Short.reverseBytes(this.keys[k]));
      out.writeShort(Short.reverseBytes((short) (this.values[k].getCardinality() - 1)));
    }
    if ((!hasrun) || (this.size >= NO_OFFSET_THRESHOLD)) {
      // writing the containers offsets
      for (int k = 0; k < this.size; k++) {
        out.writeInt(Integer.reverseBytes(startOffset));
        startOffset = startOffset + this.values[k].getArraySizeInBytes();
      }
    }
    for (int k = 0; k < size; ++k) {
      values[k].writeArray(out);
    }

Sample C source code


    char *initbuf = buf;
    uint32_t startOffset = 0;
    bool hasrun = ra_has_run_container(ra);
    if (hasrun) {
        uint32_t cookie = SERIAL_COOKIE | ((ra->size - 1) << 16);
        memcpy(buf, &cookie, sizeof(cookie));
        buf += sizeof(cookie);
        uint32_t s = (ra->size + 7) / 8;
        uint8_t *bitmapOfRunContainers = (uint8_t *)calloc(s, 1);
        assert(bitmapOfRunContainers != NULL);  // todo: handle
        for (int32_t i = 0; i < ra->size; ++i) {
            if (get_container_type(ra->containers[i], ra->typecodes[i]) ==
                RUN_CONTAINER_TYPE_CODE) {
                bitmapOfRunContainers[i / 8] |= (1 << (i % 8));
            }
        }
        memcpy(buf, bitmapOfRunContainers, s);
        buf += s;
        free(bitmapOfRunContainers);
        if (ra->size < NO_OFFSET_THRESHOLD) {
            startOffset = 4 + 4 * ra->size + s;
        } else {
            startOffset = 4 + 8 * ra->size + s;
        }
    } else {  // backwards compatibility
        uint32_t cookie = SERIAL_COOKIE_NO_RUNCONTAINER;

        memcpy(buf, &cookie, sizeof(cookie));
        buf += sizeof(cookie);
        memcpy(buf, &ra->size, sizeof(ra->size));
        buf += sizeof(ra->size);

        startOffset = 4 + 4 + 4 * ra->size + 4 * ra->size;
    }
    for (int32_t k = 0; k < ra->size; ++k) {
        memcpy(buf, &ra->keys[k], sizeof(ra->keys[k]));
        buf += sizeof(ra->keys[k]);

        uint16_t card =
            container_get_cardinality(ra->containers[k], ra->typecodes[k]) - 1;
        memcpy(buf, &card, sizeof(card));
        buf += sizeof(card);
    }
    if ((!hasrun) || (ra->size >= NO_OFFSET_THRESHOLD)) {
        // writing the containers offsets
        for (int32_t k = 0; k < ra->size; k++) {
            memcpy(buf, &startOffset, sizeof(startOffset));
            buf += sizeof(startOffset);
            startOffset =
                startOffset +
                container_size_in_bytes(ra->containers[k], ra->typecodes[k]);
        }
    }
    for (int32_t k = 0; k < ra->size; ++k) {
        buf += container_write(ra->containers[k], ra->typecodes[k], buf);
    }

Unsigned integers in Java

Java lacks native unsigned integers, but integers are still considered to be unsigned within Roaring, and ordered according to  Integer.compareUnsigned.

For 32-bit integers in [0,2147483647], the unsigned and signed integers are undistinguisable since Java relies a 32-bit two's complement format for its int type.

Extension for 64-bit implementations

Some Roaring bitmap implementations may offer a 64-bit implementation. This section proposes a portable format, compatible with some (but not all) 64-bit implementations. This format is naturally compatible with implementations based on a conventional red-black-tree (as the serialization format is similar to the in-memory layout). The keys would be 32-bit integers representing the most significant 32~bits of elements whereas the values of the tree are 32-bit Roaring bitmaps. The 32-bit Roaring bitmaps represent the least significant bits of a set of elements.

General layout

All words are written using little endian encoding.

Unsigned longs in Java

Java lacks native unsigned longs, but longs are still considered to be unsigned within Roaring, and ordered according to Long.compareUnsigned.

For 64-bit integers in [0,18446744073709551616], the unsigned and signed longs are undistinguisable since Java relies a 64-bit two's complement format for its long type.

Alternative 64-bit implementations

Java Roaring bitmaps implementation offers an ART-based 64-bit implementation. It may reach better performances (compression and/or computation). But as of 2022-11, it is not compatible with this Serialization format.

Java Roaring bitmaps implementation offers an Map-based 64-bit implementation handling signed longs. It is not compatible with this serialization format (which does not handle signed keys).