Instead of roaring bitmaps...

[jallum]

Have you considered using fdb's keyspace directly?

The approach taken - marshalling them into 100KiB chunks - is really clever, but I wonder if there's a different way to think about this problem. With the current setup, and bitmaps containing hundreds of thousands of values, serialized into chunks and stored as FDB keys, means every modification follows this pattern:

Read entire series of chunks
Deserialize roaring bitmap
Modify bitmap
Serialize into chunks
Write chunks

The issue is that any two transactions touching the same bitmap will conflict, even if they're modifying completely different bits. With high concurrency, that's going to create a lot of aborts due to read-write conflicts.

Sparse bitmaps using the keyspace itself might mesh better into your high-concurrency environment.

Something like: bitmap/{bitmap_id}/{word_index} = 64-bit value
Where word_index = bit_position / 64.

This would give you:

• Much smaller conflict ranges - only transactions actually touching the same 64-bit word would conflict.
• FoundationDB's atomic operations become useful - you could use atomic_or(key, 1 << offset) to set bits without read-modify-write at all.
• Natural sparsity - you only store the words that actually have bits set (everything else is assumed to be zero).
• Range operations work beautifully - counting bits becomes a range read followed by popcount
• Fast Intersection operations - Two range reads consumed together, one for each map, and disjoint? or intersects? can early-out really quickly. No need to read the entirety of both bitmaps.
• Fast set-membership - Checking if an individual value is in the set is one, quick read.

The operations would look something like:

# Set bit N
word_index = N // 64
bit_offset = N % 64
atomic_or(f"bitmap/{bitmap_id}/{word_index}", 1 << bit_offset)

# Test bit N  
word_index = N // 64
value = read(f"bitmap/{bitmap_id}/{word_index}") or 0
return (value >> bit_offset) & 1

# Count bits in range
total = 0
for word_value in range_read(f"bitmap/{bitmap_id}/", start_word, end_word):
    total += popcount(word_value)

You'd lose the compression benefits of roaring bitmaps, but for your use case with high concurrency, the improved transaction success rate might more than make up for it. Plus, for sparse bitmaps, you'd still get natural compression since empty words wouldn't be stored at all.

The word-indexes can be encoded compactly (and still sort correctly!), using the same technique used by fdb's tuple-encoding for integers -- that keeps that part of the key short. Making good use of fdb's "directory layer" can help to keep the prefixes short. With these tricks in play, the keys you send to fdb can be ~6-10 bytes long.

[jallum]

For the problem of allocating bit-indexes to your set members, you might consider using something like the high-contention allocator. It's purpose is to generate short, unique prefixes for the directory layer... but a short byte sequence that's guaranteed to be unique could also just be treated as an integer index into the bitmap. You'd do everything but this.

Instead of allocations being super-sparse across 64-bits (and then requiring roaring compression), this would give you dense bit allocation under high concurrency, meshing better with the techniques described above.

[jallum]

Another thought occurs to me. Roaring bitmaps are composed of several substructures, trees, RLE-blocks, etc. It should be possible to modify the roaring bitmap implementation to store/modify/query the keyspace directly for these substructures. This could make it unnecessary to deal with marshaling / un-marshaling the entire structure to modify or read bits, and would also serve to reduce the conflicts between parallel modifications as well as reduce the amount of traffic between fdb and kvdb.

I wonder, though, if as sparse as the bit-indexes/ids will be within 64-bits (or 48, with recent changes) from your current allocator... it might be better to lean into the sparseness... and just use keys? An encoded key using a common-prefix and tuple of {bitmap_id, bit-index} with an empty value ("") might end up being the simplest, fastest, highest-density, lowest-collision thing you could do here.

Insertions would nearly-never conflict, set-membership checks would be very cheap, and you'd massively decrease the amount of traffic between kvdb and the fdb instance backing it for insertions, deletions, etc.

[hungtit688-cmd]

t