There are 16 containers in a row in a shard with the default shard
width of 2^20, but since you can change the shard width at compile
time, everything should be computed off that.
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.
The intent of these lines was "if there's no filter, return
immediately rather than doing operations".
But actually we didn't write that, so we were calling intersectionCallback
on empty filters, which didn't matter since it failed out quickly, but
it's still a waste of effort.
Except we shouldn't get to these anyway because ConsiderKey already
correctly rejected these cases. I think. But still.
In fact, we *do* want to skip ahead sometimes to the next thing, and
only call our callback for things that match our filter. I was thinking
that we needed to call the callback for all data regardless, because
what if you're writing to a mutex and adding new data.
But even if you're adding new data, it's still in the filter, because
it has to be, because we don't start out knowing there's no existing
data. So the mutex actually works fine.
So the rule for BitmapBitmapTrimmer is that your filter doesn't have
any meaning other than (1) it tells us which containers you need
to see, (2) we provide it to your callback function. Maybe you want
to subtract those. Maybe you want to add them. That's up to you to
decide.
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.
This in a parallel to ApplyFilter/BitmapFilter which allows writebacks
while it's running. It's a write operation, so it needs a write lock
on the Tx, and needs to create bitmaps if they don't already exist.
The semantics are a bit messy and need better documentation still.
We frequently want to grab the set of values from a []uint64
that correspond to a given key, and make a container from them, but
sometimes we only want to do one of these. This implementation
lets us do that the same way every time, and do in-place
container creation without extra allocs.
The test for bitmap-to-array succeeding doesn't work with roaringParanoia,
which *does* intentionally panic at that point. Possibly we should also
drop the corresponding logic that tries to prevent it from panicing,
since it won't work with the paranoia flag on anyway.
We don't really need to fully extract every row, we just need counts.
This naive approach uses logic similar to BitmapBitmapFilter, but tweaks
it so that we can intercept the existence and sign bit rows, work with
an optional filter, and yield a sum. We accumulate the statistics
internally, rather than using a callback, because I tried to make it
work with a callback and it was a complete mess.
Note the fancy check for container reuse in the BSI Count filter.
This is because intersection(full container, X) is just the original
X, *not* a copy, but in this case we need a copy because RBF
ApplyFilter will in fact reuse a single container's storage for
each consecutive container.
it was somewhat difficult to avoid ripping this out without also
touching some of the stuff that supports roaring backend. That's going
soon too, so no worries :)
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
```
These commits are hard to disentagle, and doing them separately means
re-modifying the same chunks of code several times before removing it,
and similar things.
Basically:
(1) Drop the bolt backend storage.
(2) Drop the blue-green wrapper that compares two backends.
(3) Drop unused or barely-used Tx API components from all the
remaining backends.
(4) Minor related cleanup to simplify things related to these.
The boltdb backend existed only to verify RBF. The blue-green wrapper
was mostly used to verify RBF, but in practice we had to do a lot
of working around that, and it introduced a lot of special cases.
Types removed:
IteratorFinder: Used only to implement the roaring iterator
on top of boltdb, and to complicate the way it worked in roaring.
Reverted the complications. Also unexport NewSliceContainers
which is used only for that outside of roaring's internals.
PortMapper from cluster_internal_test.go: Used only for a test
we removed early this year. Never used for anything else.
RawRoaringData: Totally unused.
TxStore: Totally unused.
Functions removed from Tx API, and sometimes corresponding
members were removed from structs:
* Dump: debugging code, I don't think I found any actually reachable
paths to it.
* Group: only used for debugging TxGroup stuff
* IncrementOpN: only used by fragment, fragment can increment its
own opN.
* Options: unused?
* Pointer: debugging only
* Readonly: used only to decide how to handle Tx in a TxGrp,
but we never add a non-readonly Tx to a TxGrp. Removed also all
the corresponding write-aware stuff.
* RoaringBitmapReader: Used exactly once, can just be a bm.WriteTo.
* Sn (and OpenSnList): Unused
* UnionInPlace: unused and conceptually-invalid; it didn't write
to storage and shouldn't have, and was just "create a bitmap
then call union-in-place", which we can do directly.
* UseRowCache: just checked storage.UseRowCache.
Other things removed:
The SetRequiredForAtomicWriteTx and ClearRequiredForAtomicWriteTx
functions go away, since nothing now seems to be using them? Same
for holder_internal_test's `testHasBit` and `testMustNotHaveBit`,
which were unused.
The DBPerShard "DeleteDBPath" and "HasData" functions and related
parts were mostly unused; took out the parts that were never
actually being reached.
Changed the API of one function to simplify special cases and
remove things:
* ImportRoaringBits had a special "data" argument which gave it
subtly different semantics for RBF and roaring (for roaring, it
could produce a roaring bitmap *with ops log*), didn't seem to
be adding much. Removed corresponding "readStorageFromArchive"
which is not otherwise used.
Also took out various debugging/dumping functions that were unused
and may have bitrotted.
Dropped a test from txfactory_internal_test, and the "pjobs"
code, because those two were the only things that needed Barrier
and thus idem, which lets us drop two more dependencies. We already
have errgroup for grouping things which want to terminate as
soon as one of them errors, approximately. To do better we'd have
to have context-threading, really.
Unbroke the WriteFragment test for non-roaring tests and made it
not roaring-only.
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.
We support query parameters for details (default false) which
request additional data, and for a limit (default 0/MaxInt32)
on number of results returned to limit the amount of spam
produced if there's a lot of results. The simpler default
output should reduce load and runtime significantly, and the
ability to specify limits makes it easier to get reasonably
small responses.
There's some context support here, but the underlying filters
don't take contexts or check for them, which is probably
a flaw but might be a bit large to correct for this.
Despite being large, this set of changes is actually
fairly well contained within the mutex-checking code.
This implements a fairly straightforward sanity-check for mutexes,
implemented as a bitmapfilter at the fragment level, and with higher
levels combining results. There's two endpoints, an internal endpoint
which only checks the local node's shards, and an external one which
forwards requests (using the internal endpoint) to all the other nodes.
The internal endpoint does not do key translation, the external one
does.
The transmission format is a probably-inefficient JSON blob, and
returns data separated per-shard so we don't have as much merging
work to do.
This introduces a horrifying monstrosity function which tries to
sneakily corrupt mutex fields and which has to be exported (EWWWWW)
but which is only present in _test code (!??!! THIS WORKS WHY).
Also one typo fix in unrelated code caused by not wanting to keep
fighting with gofmt about this.
Two of the intersectionCallback functions were broken.
In intersectionCallbackArrayArray, when checking to see whether we can
skip ahead 8, we need to check whether that last value is lower than
the one we're looking for, not whether the first value is.
For intersectionCallbackArrayBitmap, actually implement it at all;
it had never gotten modified significantly from the original
intersectionCount, so it still counted and returned intersections, but
never called the callback at all.
This partially-implemented prototype of the ingest API is based on our
programmatic ingest API reference. It has noticable limitations, most
crucially that it doesn't handle multi-node clusters right now. However,
it basically implements the expected semantics.
There's some noticeable performance issues to do with the high overhead
of sorting bits in order to import them efficiently, but this is fixable.
We also add the hooks to the internal client, and make the finisher logic
a bit smarter.
Much of this code was originally by Nia Weiss, but it's been merged
and restructured a bit to get things broken into logical commits.
When searching for a small array in a large array, scanning ahead
is productive. The switch from counting indexes to reslicing the
slice appears to improve performance in this case. The fairly arbitrary
value `na << 2` is like `nb / 4 > na` except that it computes faster,
and lets us avoid the expensive overhead unless we have reason to
expect that there's significantly more items in b than in a.
Improvements: Not huge in some cases, but sometimes quite noticeable,
especially as the frequency of overlap increases, which is also
the expensive case in other ways.
name old time/op new time/op delta
ImportMutexSampleData/64K/2Kr/40/none/write-0-8 501ms ± 4% 486ms ± 2% ~ (p=0.052 n=6+5)
ImportMutexSampleData/64K/2Kr/40/none/write-1-8 756ms ± 5% 698ms ± 5% -7.62% (p=0.002 n=6+6)
ImportMutexSampleData/64K/2Kr/80/none/write-0-8 292ms ± 3% 276ms ± 4% -5.46% (p=0.002 n=6+6)
ImportMutexSampleData/64K/2Kr/80/none/write-1-8 511ms ± 6% 482ms ± 4% -5.72% (p=0.015 n=6+6)
ImportMutexSampleData/64K/2Kr/240/none/write-0-8 153ms ± 3% 132ms ± 5% -13.91% (p=0.008 n=5+5)
ImportMutexSampleData/64K/2Kr/240/none/write-1-8 354ms ± 2% 215ms ± 6% -39.41% (p=0.004 n=5+6)
ImportMutexSampleData/1K/2Kr/40/none/write-0-8 565ms ± 3% 543ms ± 3% -3.89% (p=0.015 n=6+6)
ImportMutexSampleData/1K/2Kr/40/none/write-1-8 807ms ± 6% 778ms ± 3% ~ (p=0.180 n=6+6)
ImportMutexSampleData/1K/2Kr/80/none/write-0-8 317ms ± 3% 300ms ± 1% -5.40% (p=0.002 n=6+6)
ImportMutexSampleData/1K/2Kr/80/none/write-1-8 462ms ± 3% 437ms ± 4% -5.31% (p=0.009 n=6+6)
ImportMutexSampleData/1K/2Kr/240/none/write-0-8 141ms ± 1% 119ms ± 2% -15.85% (p=0.004 n=5+6)
ImportMutexSampleData/1K/2Kr/240/none/write-1-8 213ms ± 3% 171ms ± 3% -19.70% (p=0.002 n=6+6)
In BitmapBitmapFilter.ConsiderData, we intersect things solely in order
to perform callbacks on them. Creating these intermediate arrays is
actually somewhat expensive, and all we're going to do with them is
make callbacks anyway.
So, we add a new `intersectCallback`, which behaves similarly to
`intersectionCount`, but which dramatically reduces the amount of memory
allocation associated with doing the callbacks; in some test cases
on mutex data, this code was >90% of all memory allocations, and
getting rid of that helps a lot.
At that point, we no longer need the separate intersectAny check,
because it doesn't save us any time anymore.
When unmarshalling ops, we weren't adding a meaningful OpN to them,
resulting in misleading reports from `pilosa inspect`. Also, we were
mistakenly reporting things as "mapped" when they were actually
using their internal storage (as with small array containers).
Add the "sanity check" to `pilosa inspect` so that errors like the
above get noticed more easily and corrected. Also, to make that work,
have roaring.InspectBinary actually put containers in the bitmap
it creates rather than just creating info entries for them.
bitmap.BitwiseEqual had a couple of subtle bugs, and the net result
is that if the bitmap you were comparing to had an empty container after
the original bitmap ran out of containers, we'd spuriously report
the container as existing and being... the last container in the original,
actually.
Issues are both that we were grabbing the value from the wrong iterator,
and also that we were iterating twice per loop, and thus could also
have missed a non-empty container immediately following an empty one.
The remake container logic (used to avoid allocating extra containers while
applying filters) relied on roaring recomputing N, which it did for bitmaps
but didn't do for runs. Fix this both ways; it would now do that for runs,
but also we add "with explicit N" variants and use those since we have a
correct count already, and don't need it. This means fewer popcounts on
bitmaps, and working at all on runs.
