The anti-entropy feature has never actually worked. We've been
talking about removing it or replacing it for ages, but haven't
had a concrete motivation.
But the anti-entropy interface is the sole user of several components
of the Tx interface, and now that we're trying to replace that
interface, being able to drop those components has some appeal, so
let's remove the one thing that used them, in the hopes that this
will simplify life.
This also lets us drop ForEach and ForEachRange, which were
barely used at all. The one surviving usage (CSV export) can be
handled by using the container iterator we already have, and
making ContainerCallback exported so we can use it to just call
things for every bit.
The comment says "convert to each type and compare", but it
doesn't convert, it just compares the given container result to
three different forms of the same result. That's neat for testing
BitwiseEqual but doesn't actually give us more information, and
it takes nearly 3x as long.
This adds a shard-based import endpoint which takes bitmap data for
all field types and imports data for the whole shard transactionally.
It uses the BitmapRewriter interface to try to intelligently allow for
setting and clearing bits simultaneously without multiple writes which
is especially helpful when ingesting into int-like fields, but also
allows clear-and-then-set behavior for set fields.
We don't need to manually copy each individual item and keep
checking for the second index being out of bounds for every
item, we know it can't change at this point, so we can just bump
it over. We want this operation because BitmapRewriter can
use it to simplify trimming in some cases.
i used this script, a little clunky but it got the job done
```bash
for file in `find . -type f -print | grep '\.go'`; do
sed '1,/^\/\/ limitations under the License.$/d' $file > $file.tmp;
result=`cat $file.tmp`
if [[ result != "" ]]; then
gofmt $file.tmp &> /dev/null;
if [[ $? == 0 ]]; then
mv $file.tmp $file && gofmt -w $file;
else
rm $file.tmp;
fi
else
rm $file.tmp;
fi
done
```
This takes our reasonably broad selection of predefined container
types and tries intersectionCallback on each pair of them, comparing
results against the results of plain old intersect(). We've had
several intersectionCallback fixes recently; every one of them
produces test failures here if reverted or broken, so I have at
least some confidence in this coverage.
Similarly, test everything on containerCallback, verifying that
we get the same set of values called back that we get from Slice().
Both of these were verified with -coverprofile to actually be
hitting all the lines of code that aren't insane edge case
checks like "what if a run is in the wrong order".
The inner loop of intersectionCallbackArrayArray's "fast"
case has
for len(ca) > 0 && ca[0] < va {
}
so we do not leave that loop unless len(ca) is 0, or
ca[0] >= va.
We then return from the whole function if len(ca) is 0,
so the only way we finish one iteration of the outer for
loop is if ca[0] >= va. Thus, this can be an `if` rather
than a `for`.
We also fix the logic for ArrayRun to make it require fewer
tests and be clearer about why the tests work and clearer about
always making progress.
And, finally, the bitmap/range callback logic, and the underlying
"callback per bit in word" logic, were both badly broken. In
particular, if a range started and ended in the same word, it would
hit the values in that word twice, once with them incorrectly
shifted, but then it would further garble any offsets past the first
in a word. Eww.
CountRange for RBF had a subtle bug which wasn't noticed, so, let's
have some CountRange testing and also a benchmark.
We also fix a couple of subtle bugs caught in the process of developing
and testing this.
SliceContainers will allow nil containers, but doesn't return them when
iterating because there's various things that can panic if called on a nil
container. Since countEmptyContainers() has to traverse the whole bitmap
anyway, it doesn't matter which it counts, so we replace it with
countNonEmptyContainers(), and adjust test cases accordingly. This fixes
an issue where if roaring is smart enough to insert a nil container
into a SliceContainers, trying to write it to a file produces an invalid
bitmap with offsets off by 16 and one container fewer than its header predicts.
RBF: don't try to count 0 bits in a container
If we're to the "last container", and we'd be counting all the bits less than
zero, we can skip that. This avoids hitting a bug, which is that c.countRange
doesn't handle BitmapPtr.
In rare cases, RBF can produce containers which have a recorded N value which
is incorrect. This rarely affects anything, but on some particular queries,
this can result in very strange outcomes, like array containers with more
than 1<<16 entries.
To fix this, we have toContainer specify that it doesn't know the correct
N for the bitmap containers it's creating, which costs extra time for counting,
and should be considered a temporary workaround.
Also, we add a CheckN() function which is controlled by the
roaringparanoia flag, and add a number of calls to it, for instance, as
deferred calls after every container operation when roaringparanoia is
enabled. This means that we get improved confidence that we've caught
the relevant errors, but is not suitable for production use.
The copy-on-write/rowCache changes require that functions that
modify containers be able to generate new containers. Once that
became possible, some significant pool of other operations
started relying on it -- for instance, operations might return
a new container even though they're in theory "in place" operations.
I developed a tool for checking for unused function return
values (github.com/molecula/noticeme), and ran it on this, and
picked out the places where `*Container` values were generated
but not used, and some of them seem to be potentially-real
bugs, and a few are probably harmless. Updated code to make
those diagnostics go away.
- log Debugf when we repair a fragment block
- better run-run roaring testing for over-sized containers
- add which fragment path to panic on container too big
- include container contents in roaring hash for pilosa-chk/pilosa-check-backup
If you just stash the results of the function when defining the test cases, the
outcome is in part that you are reusing the same slices for multiple things. So,
for instance, if you perform a union on the OddBitsSet slice, with the EvenBitsSet
slice, the result is to overwrite the first entry in that slice with the 0-ffff
run... But the original slice still exists, and then we reuse it and get a slice
with a bit count of around 98,000. The underlying issue is that doContainer()
is calling NewContainerRun(), which is simply using the provided slice, not
copying it -- which is intentional, but the test has to be careful about it.
We call repair on the one we think should be a bitmap. Theoretically
maybe we should also repair the other one in case unionRunRun some day
starts returning unrepaired bitmaps, which in principle it's allowed to
do...
- rbf had races around the new rootRecords cache in tx
- rbf tx needed a write lock on the db now that rootRecords are written
- added a global registry for rbfDB to correctly dedup instances
- implement DeleteFragment, DeleteIndex for rbf
- use badger style keys for rbf to allow content checksumming to be list
containers in the same order
- lots of other integration of rbf into pilosa layer.
back to github.com/dgraph-io/badger/v2 v2.0.1-rc1.0.20200709123515-8e896a7af361 b/c github.com/dgraph-io/badger/v2 v2.0.1-rc1.0.20200718033852-37ee16d8ad1c had issues with CI on 386 and arm
We have a "deadcode" bitmapsEqual which is actually used in testing but
probably shouldn't be, and we don't have a good container equality test.
Problem is, equality tests are sort of slow in the things-are-equal case,
which is the most common case, so we've got some moderately-specialized
code here; specifically, special comparison code that takes advantage
of knowing that if two containers have the same number of bits, you only
have to check whether all the bits from one are present in the other,
because that can't be true for differing containers with the same number
of bits. This reduces the runtime for the ContainerCombinations case
from about 24 seconds to a bit under 2 on my laptop, or from around
10 minutes to about 37 seconds with the race detector on.
Also simplify the InPlaceWrapper functions not to invoke bitmaps, because
it's not really necessary.
In addition to adding some tests, this commit moves the
`GenerateUint64Slice()` helper function into a new `generator` package
so that it can be used in both internal and non-internal tests.
When the interval is a proper superset of the range with start equal to
interval start, the range must be considered a superset or it will be
completly ignored (since it neither a subset nor it overlaps)
Co-authored-by: Pierre Fersing <pierre.fersing@bleemeo.com>
The new roaring iterator used for the remap and importroaring
things could also be used for unmarshalling roaring streams,
and it's a slightly simpler design that doesn't need two passes
through the data. This patch cleans that up a bit, makes it work
better with ops logs, and uses that instead. It appears to
noticably but not immensely reduce the time imports take, but it
also gets us back down to one thing parsing roaring formats.
There are a couple of subtle changes to errors we were testing
for in various tests, and one of the fuzz tests goes away because
it was actually itself an erroneous error message -- it was reporting
the header of a roaring file as an invalid op because the op log
reader was running on the header for roaring files with zero
containers. Oops.
