This commit adds a fast path for optimizing queries that only
have `SetBitmapAttrs()` calls in them. It does this by grouping
the calls into a single Bolt transaction and also by merging
multiple attribute updates per ID into one update.
This commit changes the `roaring.Bitmap` to use a 40/24 split in
the high and low bits. This change also requires the low bits
to use `uint32` instead of `uint16`.
This commit moves bitmap intersection into the `roaring` package
in order to reduce allocations.
Benchmarks against real world datasets show a speed improvement of
353%. Previously, intersection operated at approximately 5.6M
bits/sec against two 60K bit bitmaps with 30% overlap. The new
intersection operates at approximately 20M bits/sec.
This commit changes the fragment allocation algorithm in the cluster
to make use of the `DB` name. This allows each database to use a
different slice distribution.
Initially, the `frame` was going to be used for allocation, however,
this was problematic since queries can span multiple frames so it's
impossible to choose a single frame to use.
This commit moves the computation of the intersection count to
the `roaring` package so that no allocations are required. The
implementation operates at the roaring container level and has
specialized functions for array-array, array-bitmap, and
bitmap-bitmap container pairs.
This commit changes the underlying storage for `Bitmap` from a
red-black tree to a roaring bitmap. It also removes bitmaps from
the cache and only stores the bitmap count.
This commit refactors the anti-entropy system to fetch data from
all replicated blocks and only set/clear bits which deviate from
the consensus between all blocks.
An example of this is if 3 nodes had the following bits set for
a single bitmap:
Node A: 1 2 3
Node B: 2 4
Node C: 1 2 4
Then only bits which are set on a majority will be set. In this
case bits 1, 2, & 4 are set but 3 only exists on a single node.
The node performing the merge would then determine the following
set/clear diffs for each node:
Node A: clear(3), set(4)
Node B: set(1)
Node C: none
Once the merge is performed and all nodes receive their diff
instructions then the nodes will be in sync:
Node A: 1 2 4
Node B: 1 2 4
Node C: 1 2 4
There still exists situations where bits can be reset. If Node A
is up and Node B & C are down then Node A's bits will be reset
once B & C come back online. We should add write consistency
settings for incoming writes so that we can ensure that a quorum
is written to before returning a success. This is outside the
scope of this commit though.
This commit re-adds the `testdata` folder that godeps strips and
also updates the `Makefile` to add a `vendor` target that will
handle this in the future.
