So in some cases, when we do a query, the results of one
part of the query are innately shared-across-nodes; for
instance, a hypothetical Distinct query. More generally,
we allow cross-index queries; calls can have "index=foo"
in them.
This patch lets us handle that without duplicating that
query all over. Before we actually start doing the
separate calls, we run the query once from the coordinating
node, then patch the results in, and send relevant subsets
over to each client, etcetera. Also provides slightly
friendlier (and I hope faster) support for converting
bitmaps to/from sets of rows.
We also add an extension interface, and some fancy stuff
to let us define new calls, which use this. They're sort
of tied together because the first extension I wanted to
implement needed precomputed calls. The extension API
lets us create extensions using `pkg/plugin` (with all its
associated limitations, unfortunately), then query them
at load time for functionality.
This also implies some revamping of the argument
validation for PQL, like verifying that functions exist
and knowing things about their argument types.
So basically this is an overly intrusive patch, and would
be better as separate patches, but they're hard to detangle.
add trivial execution-time profiling
What if you could ?profile=true on a query and get some
numbers back? That'd be really cool.
We already have tracing/spans, but right now, those only generate
any data if you have something set up for them to trace to. Add a
fancy wrapper that lets us generate our own tracing data, and dump
it into the request response, if ?profile=true.
add a sample extension, add missing features to extension interface
Implement a naive probabilistic filter extension as an example of
what an extension looks like. In the process, discover multiple
omissions in the bitmap API. Well, I did *say* it was experimental.
This code represents an attempt at providing reliable tracking
of whether any bitmaps still in use have access to a given block
of mmapped data, allowing us to unmap the data when nothing is using
it anymore.
The basic approach is as follows: Each mmap is associated with
a new object, called a "generation". A generation reflects
a particular instance of a given file being mapped. When a
bitmap is built from an mmapped data source, the bitmap is
given a pointer to the generation as its Source. When bitmap
operations combine containers from other bitmaps, they
produce new bitmaps that are tagged with the combined set of
sources.
When we snapshot a file, or for some other reason wish to remap
it, the corresponding bitmap has all its containers updated to
use the new storage, and the bitmap's source is changed. However,
previously-handed-out containers might still have references to the
old storage. Those containers would be in bitmaps with the old
source.
After a bunch of study of trying to reference-count and track
this, I realized: We don't actually need to do that, because we
already have something suitable for determining whether anything
can reach a given object. It's the garbage collector.
So we set a finalizer on the generation object, which handles
unmapping. There's additional sanity-checks here to confirm things
like "we thought this generation should be expiring", and we
track timestamps. We could also have things check whether a
given bitmap's source was marked as obsolete "a while ago", but
that isn't implemented yet.
There's a debug version of this which tracks finalization, creation,
and ending timestamps, and has a call to provide diagnostics for
this. Identical generation IDs get separated out with random
suffixes in this case -- there's sometimes a second or third
instance of the same name due to a holder closing and reopening,
but this basically only happens in testing.
Note that generations are still used even when there's no mmapping,
but unless debugging is turned on, they shouldn't propagate much --
we don't consider a generation to be the source of a bitmap unless
the bitmap actually mapped things from that generation's mmapped
storage, or debugging is on.
There's a couple of other, possibly more subtle, changes and
bug fixes that got caught by the testing on this:
* If a fragment is partially opened and then opening some later
part fails, we close the earlier parts before returning the
error so we aren't leaving it partially open.
* Several operations on segments which were requesting that a
frozen copy of a bitmap be created are now actually *replacing*
their bitmap with the frozen bitmap, rather than discarding it.
* intersectRunRun, if it decides to create an array or bitmap,
will yield that container instead of discarding it.
And why all of this? Why, so we can actually implement the thing
where when a fragment has a valid roaring bitmap, but the ops log
is corrupt, we can truncate the corrupt part of the ops log and
reopen it. Which I did.
When the generationdebug build tag is in use, every generation
has a finalizer all the time. When it's not, they only get finalizers
when we expect them to be done -- say, when closing a fragment.
This is because finalizers appear to be possibly-expensive.
There's some logical cleanup to openStorage here, dividing part
of its work into applyStorage and importStorage, which have a common
case for handling "there's no data in this file".
Which is to say don't actually implement it, because openStorage
is too messy right now, but this is the rest of the framework,
and now I'm going to digress into fixing openStorage.
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.
Addressing various lint.
incrementOpN no longer returns errors, because it no longer waits for
the snapshot, so checking those errors is unnecessary.
Several fields in a common embedded structure were "unused" according
to a naive checker.
Other tiny style things, and one actual unchecked error. Yay linters!
The Pilosa roaring format uses two bytes of its
header, next to the magic number, for a version. The
official roaring format uses them for a container
count, if and only if it's the version of the format
that uses run-length containers.
But if it is, it really does need those bits. Also,
since we never use the official format in our internals
or snapshots, we don't have any reason to support
reading flag bits in it, since the flag bits are used
only for internals of fragments and snapshots. So
we revert the change to support flags with official
roaring bitmaps.
A couple of the fuzz tests happened to rely on this,
and we may find more issues with more fuzzing.
I didn't think of this, because we don't use it much in the
client. This is a bit hairy because really official roaring
is two fairly different formats, one with runs and one without.
As the size of a fragment grows, the cost of snapshots
increases; with a large fragment getting a lot of large writes,
every write will trigger a snapshot, while any other writes have
to wait for that snapshot before they, too, can trigger a snapshot.
To address this, we introduce a background queue of snapshots.
In general, operations which were omitting their ops log writes
and just snapshotting no longer do; they emit an ops log. This does
mean that, in some cases, the ops log is written and then a snapshot
takes place essentially immediately, which costs us some performance.
However, that only actually happens under very light load; under
heavier load, there's generally going to be multiple writes coalesced
into each snapshot, and the ops log writes for them will be much
cheaper than a full snapshot.
When we do a snapshot, we may end up with containers which are
mmapped to the old file, and containers which have allocated storage
identical to the contents of the new file. It would be nicer if they
were mapped to it. But unmarshalling the entire file is expensive.
Instead, we remap it. (Or, if we couldn't mmap it, just make sure
the old stuff is no longer using the old storage space before we
munmap it.)
The new op type code changed the failure mode for
one of the fuzz test issues -- and the fuzz test revealed a
bug in the code. Fixed the code, updated the test to expect
the newer, better, message.
Also fixed capitalization on the old message.
We add a new ops log type(pair), AddRoaring and RemoveRoaring,
which set and clear the bits from a provided roaring bitmap.
This also compels us to consider additional sanity checking
during tests.
This patch replaces a lot of circumstances in which containers
were being copied with circumstances in which they are shared,
using copy-on-write semantics.
To achieve this, we emulate somewhat the design of go's
native `append` function. Operations on a container may optionally
yield a new container. A container can be marked "frozen",
after which no operation should ever write to it in any way;
that applies both to the container itself and the backing store
it refers to, if any. So for instance, instead of:
c.arrayToBitmap()
we now write:
c = c.arrayToBitmap()
Operations which need to modify a container in any way
need to be able to return a new container, which is a modified
copy of the previous container. This applies to operations
like add/remove, but also to things like unmapping memory-mapped
storage, or changing a container's type.
Bitmaps do not support the same copy-on-write semantics,
currently, but "copying" a bitmap and sharing the containers
instead of duplicating them is *much* cheaper than copying
the containers.
Bitmaps do support a .Freeze method, which currently copies
the previous bitmap, making a new one with the same container
pointers, and freezes the individual containers. Use this
if you need a writeable copy of a bitmap -- the resulting
bitmap can safely have its set of containers modified, and
bitmap operators that would want to modify the containers
will use copy-on-write for that.
The primary motivation of this is to reduce the cost of the
row cache used by fragments. As a secondary issue, the row cache
is no longer updated on writes -- that update was actually a
race condition waiting to happen. Rather, writes to a row
invalidate the cache entry for that row. The row cache is
created by creating a new bitmap, and freezing the relevant
containers from the fragment's storage. In the case where
nothing is being written, the row cache grows to contain
bitmaps containing all those containers, but never copies
any containers. If nothing's being read, the row cache is
never created, and the containers are in general not getting
frozen. The only circumstance where copies have to happen is
when things are read (and thus stored in the row cache) and
later modified. In that case, each read freezes objects, and
the first write to a container after it's been frozen will
create a new copy.
We drop the enterprise/b btree implementation, because we
don't really need it anymore -- we now provide that
implementation by default in the open source product anyway.
Along with this, there's a lot of other changes which
improve support for nil containers, as a cheaper representation
for empty containers. Operations which we know will provide
an empty container can always short-circuit and just yield
a nil *Container. Similarly, operations which would provide
a full container can return a single shared full container
object (which is frozen). The higher-level (non type-specific)
container ops are now using that logic to short-circuit
operations for empty and full containers. (For instance,
difference of anything minus an empty container is the
original thing, union of anything and empty is the original
thing, and so on.)
The Containers interface adds "Update" and "UpdateEvery"
methods, based in part on the "Put" interface provided
by the underlying btree implementation; Update performs
a possible update in-place of a container for a given
key, bypassing the need to replicate the search for that
key in the container. UpdateEvery loops through all the
containers.
Containers do not strictly guarantee that they won't
return nil `*Container` objects. However, the container
iterators won't return those -- empty containers aren't
interesting. Some tests are updated to reflect this.
Some of the container internals, like N(), or the isArray()
and related functions, accept nil container pointers. Some,
like Thaw(), do not. For the array(), bitmap(), and runs()
methods, roaringparanoia enables an explicit panic on a nil
container explaining the problem, but the intent is that those
should never be called unless you already know you have the
right kind of container, so by default they don't perform
the extra checks. In most cases, this is already covered
because a nil container is empty, and there's no operation
we can perform that requires us to inspect the contents of
an empty container. This is passing a fair amount of testing,
but the testing may not be comprehensive enough.
The overall impact of this is pretty trivial performance-wise.
In our default roaring/ benchmarks, a few things get a few
percent faster, or slower. The advantage is that, with
read-heavy workloads, the row cache no longer eats up incredible
amounts of memory.
For a smallish test case, pilosa's memory usage (RES in top) after
startup was ~2.5GB. Without this patch, simply reading every
row a few times got memory usage to about 9GB, which seemed
reasonably stable. With this patch, memory usage went to about
3GB. This will be less noticeable in mixed read/write loads,
but it should be consistently significantly lower.
In addition to dropping things from the rowCache on modifications,
we also stopped performing a full count on a modified row when
not using a cache of a kind that would use that count, and don't
repopulate the rowCache regardless. We don't want every write
to imply a corresponding read after it.
There's a lot of room for possible future optimizations in
terms of things like in-place operations, and some of the
row/rowSegment code is a little suspicious to me, but I don't
think it should be *worse* in any cases.
This commit implements BSI with variable bit depth using a
sign magnitudeto indicate whether a value is positive or negative.
This also rearranges the existence bit to be the first bit instead
of the last bit.
