Thaw() is supposed to always provide writable storage, which it does
by ensuring that containers aren't frozen, but also by cloning or
copying their data if the data is marked as being memory-mapped.
But only the roaring backend had the ability to mark data as memory-mapped,
because that wasn't exported. Fixed this, and added corresponding code
to badger, lmdb, and rbf.
- blue_green for doing migration. Called before Holder.Open finishes.
- holdbkg.go added for index lookup. Less wedging between a deadlock and a race.
- fix fault under read-only map under lmdb at
TestExecutor_Execute_Row_Range/RowIDColumnID by doing cow in roaring.
- roaring -tags gofuzz builds again
- roaringparanoia build tag added to make test targets in Makefile
- add rbf.NewDBWithAllocZero for out-of-bounds memory checks
- .circleci/config.yml test-shardwidth-22 with large run container, kept OOM-ing we suspect.
Fixes#819
After documenting the semantics, I noticed an arguable hole in them,
which is that you could Freeze() a dirty container, and then Repair()
wouldn't work on it. On further study, I added a roaringparanoia
check for attempts to access the N of dirty containers.
It turns out there's several such. But also, it turns out, there's
circumstances where unionInPlace is relying on the assumption that
N is valid, which it isn't always for dirty containers. Also, there's
at least one case where we rely on the assumption that forcibly
thawing a container, then calling unionInPlace on it, always modifies
that container. But that's not supposed to be true for an empty
container -- an empty container might be better handled by just
returning the container it's being unioned with. So, we drop the
unnecessary thaw (all the *InPlace ops are already thawing if/when
they need to), but we use the return from unionInPlace.
The copy-on-write semantics were previously documented only in
the 125-line commit log from the patch which introduced them. Add
documentation for them in a few likely places.
not overflow two big arrays into an invalid array.
recreate badloader from git history, at 85fa67e8. Could not
reproduce this, but lots of container usage
also got updated in the meantime.
Fixes#683
- lmdb as a backend (lmdb.go)
(lmdb is the fastest known transactional storage backend)
- per Tx call statics report enabled with PILOSA_CALLSTAT=true (stattx.go)
- framework for per-shard db (dbshard.go)
- txfactory handles any pair under blue-green testing (txfactory.go)
- enable CGO in Dockerfiles for lmdb
- 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.
- all tests green on RoaringTx
- RoaringTx on by default
- blueGreenTx testing framework available for A-vs-B comparison
of Tx implementations
- flag -tx added to server command line but not wired to
change NewIndex() selection yet.
- 918 green tests, 14 tests red on BadgerTx.
A full list of the 14 red tests on BadgerTx follows.
Note that these red tests represent not defects in BadgerDB
or BadgerTx but rather failures of the pre-existing pilosa infrastructure to yet
be fully adapted from files to using a transactional storage engine.
As such these are tests that RBF should not be expected to
pass yet either.
Fixing the pilosa infrastructure to allow these tests
to go green under Badger is the next and highest priority
order of business, but RBF can get much testing benefit
from the 918 green tests we do have, and hence we merge
as much as we have today.
The 14 red tests when NewIndex() is set to use
BadgerTx are as follows. Note in particular
that pilosa cluster resizing is not working yet under a
transactional store.
TestCluster_ResizeStates/Multiple_nodes,_with_data
TestImportClearRestart/0MaxOpN10000
TestImportClearRestart/1MaxOpN10000
TestImportClearRestart/2MaxOpN10000
TestImportClearRestart/3MaxOpN10000
TestExecutor_Execute_Existence/Row
TestExecutor_ForeignIndex
TestExecutor_Execute_CountDistinct/Distinct
TestExecutor_Execute_CountDistinct/Count(Distinct)
TestExecutor_Execute_CountDistinct/GroupBy(Distinct)
TestExecutor_BareDistinct
TestExecutor_Execute_TopNDistinct/TopN
TestHolderSyncer_IntField/BasicSync
TestHolderSyncer_IntField/MultiShard
This is sort of large, but it's annoyingly difficult to
separate out.
The basic idea is to allow us to have a single holder-iterating
block of code, which is associated with the holder, that can be used
for various things, like the snapshot queue background scan, or
for inspect operations.
We invent the concept of a HolderFilter, which is a thing that
can decide what things in a holder it cares about, and a HolderOperator,
which can also process those things selectively.
In the process, we fix up a couple of subtle bugs in the
inspect logic; specifically, the assumption that the mapped flag could
tell you whether a container was modified by the ops log doesn't
work with mmap, so we have a shiny new flag which is used to track
that, internal to the roaring/container code.
All of this leads to the actual *point* of this exercise, which is
making it easier to create an /inspect endpoint which produces almost
the same data we'd have gotten from `pilosa inspect` on a data directory;
the distinction is that it doesn't try to identify the distinction
between data from disk and data from operations since the file was
loaded. Possibly it should, but it doesn't yet.
The snapshot queue is now implemented using the HolderOperator
design, which requires some subtle changes to how it works, but
overall makes it easier to follow the snapshot queue logic,
and also shares that logic with the way Inspect works.
The holder's snapshot queue is now provided by the server, in
a default environment.
The queueless snapshot queue no longer triggers snapshots on
enqueue -- it turns out that breaks badly, because a key
point about enqueueing a snapshot is that it's safe to do it
*during* a transaction on that fragment, and triggering a
snapshot during a transaction actually causes horrible errors
as the ops log ends up being the old file, which we close.
Related to this, we also need to prevent closed fragments from
trying to snapshot, so we track fragment openness when opening
or closing, and bail on trying to snapshot a fragment which is closed.
We also stop using the queueless snapshot queue during tests,
because that's a horrible idea.
We copy a little bit of the partition logic from the cluster code so
we don't have to expose it all, this lets us check whether the node
we're looking at is the one which should be primary for a given shard,
and if not, identify which node would be. This works only when
pointed at a data directory, for now.
The test cases for the holder have to be internal, because pilosa
doesn't export view/fragment, just Index/Field. This means that the
holder test cases can't just use the test/* package, so they duplicate
some of its logic, approximately.
This is logically two separate things, but the individual changes
are thoroughly intertwined in the code.
The first change is a logical change to the design of the snapshot
queue, which is that it now adjusts the maxOpN the background scan
targets, allowing it to lower that value over time when things are
quiet. We do this because it turns out that on large data sets,
this can make a factor-of-four difference in memory usage!
So, in general, on a quiet system, each pass through the holder
aims for about 1/4 of the existing fragments to get snapshotted.
When there's more load, we adjust those values up.
We also make the snapshot queue a bit less chatty, to make testing
less annoying -- we only print stats if the queue enqueues at least
two snapshots, or skips any.
The second change is threading the holder through things. We've
always threaded the logger through, and then added the snapshot
queue, and some of the Inspect-related work led to wanting to
have a way to thread options through, so what if we just threaded
the holder itself through, and removed the direct copying around
of the logger, snapshot queue, and so on. Similarly, everything
can now use holder.PartitionN instead of having to get its own
copy of PartitionN handed out to each index.
This does imply ensuring that test cases always get a reasonable
default holder.
This is a precursor to adding additional information to the holder,
such as whether it's in a special read-only mode, which would imply
not modifying on-disk files. This is already semi-supported for
the specific case of the background snapshot queue and cache flushing,
which are attached to the (created in a previous commit) new
holder Activate method, instead of being automatic on holder Open.
The change to a snapshot queue can also cause races in tests, because
the fragment.Clean method's "sanity check" accesses a fragment without
a lock. Fix that. Since there's a couple of t.Fatalf(), but we need
to release the lock before closing, we use an anonymous function
with a defer to handle that. Whee!
At some point the code changeover to use roaring iterators for
unmarshal got dropped, but the old unmarshal code is way harder to
make work for inspect, so this change is back.
This exports some of the names from the things returned by Info,
but also adds a roaring function to use the unmarshalling logic on
arbitrary data, allowing us to get more insight into a file -- in
particular, letting us distinguish between the bitmaps specified by
the roaring data and the bitmaps resulting from applying the ops log.
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.
The generation of slices from things, and use of reflect.DeepEqual to compare
the slices, is a lot more expensive than it needs to be. Omitting it removes most
of the runtime of the marshal tests.
We only have 4 bytes for offsets, but what if a file is
over 4GB? Someone came to us with a file with 265 *million* containers,
in a single fragment, which means that over 3GB of their 4.7GB file
is actually just the container headers alone. But we can't easily make
the offsets larger, or change the file format.
So we don't. We just track how many 4GB hunks of the file we've
been through and bump that every time the 32-bit offset wraps. And this
appears to... just work.
This is fixed for both the roaring iterator and the old unmarshalBinary
logic. The logic to handle this will work on 32-bit hosts in the sense
that it will correctly error out for excessively large file sizes or
container counts, but it doesn't actually handle the large files since
it can't.
We avoid using bitmapContains so often because that turns out to be expensive.
Also, if we produce more than runMaxSize runs, we're going to convert to
a bitmap container (or possibly an array container if there were over
2048 items, but they're all singletons), and we can streamline that by just
converting the source to bitmap and returning differenceBitmapBitmap, which
is faster in this case.
This appears to overall take about half as long in the workload I was
looking at.
differenceInPlace wasn't checking for nil containers, which are
theoretically valid empty containers. Also added a couple of other
N==0 checks to streamline the higher-level operation.
- Remove YAML magic
- Remove a lot of duplication
- Update linter
- Use parameterized jobs and matrix build
- Update Docker Hub CD to produce versioned and "latest" images
- Add custom shard width test to workflow
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>
Two changes:
1. Don't write batch/roaring adds or removes when N is 0, because
a write of no bits is not a meaningful write.
2. When unmarshalling roaring things, if a roaring bitmap didn't
change many bits, treat it as having changed at least 1 bit per 8 bytes,
so an 8KB hunk of roaring data counts as 1K changes, which will
nudge us towards snapshotting. This should keep us from having
Large Files show up so much.
This was particularly noticeable on the existence field, which
tends to a steady state of "completely full" very quickly in a lot
of cases.
We might have a problem with a stale mmap, and to try to narrow it down
a bit, we add some sanity-checking features and panic recovery to the
generation Transaction code.
This is pretty experimental.
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.
