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
```
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.
This can cause incredibly weird and hard-to-debug problems if the previous
container value is still in the cache after an update, and in particular,
can result in having a stale container value cached after a roaring import
that modified the container. Coupled with another bug which could corrupt
containers on a delete, this produces a very strange bug where a value is
present in a fragment, but an attempt to delete it reports failure.
- 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
UpdateEvery can change every key, and I think it strongly suggests no
reasonable expectation of repeated access to a previously-accessed key,
but also it can change the containers and replace them.
We were avoiding caching mapped containers in some but not all cases,
and that was causing segfaults. But really, the *problem* is that
the remap operation wasn't clearing (or updating) the cache. Cleaning
that up allows us to take advantage of the caching performance advantage
even when working with read-only/mapped bitmaps.
The only way to hit this:
* Have mmapped containers to begin with.
* Do reads so those containers get frozen.
* Access, either reading or writing, a specific container with key K.
* Snapshot, so the bitmap gets its containers replaced.
* Remember, they have to be frozen -- if they aren't frozen,
we'll update the containers in place.
* Now have GC run so it actually unmaps the data.
* Now try to write to the container with key K *before reading or
writing any other key*. You have to get through the whole snapshot
and GC process without any other reads or writes.
* You get the cached value. You try to use it. You explode.
The sliceContainers code was also setting lastKey to 0 in some cases,
but also setting lastContainer to nil, so this wouldn't have caused
problems, but just to be careful, I've standardized on ^uint64(0)
for everything.
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.
So with the switch to a new linter, we get a lot of new warnings,
and the majority of them are harmless probably, but a few might be
real. Variously just use _ to suppress warnings, or report errors.
There's probably things here that deserve better fixes, but we can
always revisit it.
Since we always use the same cmp function, we don't need to
actually *call* a function -- we can just inline it. Or, in
fact, omit the computation entirely; comparing the result of
the subtraction to zero is (very slightly) more expensive than
comparing the magnitudes of two numbers.
Also fix a spurious comment and gofmt issues.
This implementation, controlled by the build flag "container24s",
is similar to the single-slice container implementation, but goes
a bit further. First, instead of using a native slice as its internal
storage, it uses pointer/len/cap as distinct values, and only int32
ranges for len and cap. Second, it has a small region of additional
storage which it uses as a backing store by default for arrays or
runs. The idea is that, if you request a new empty array container,
you get one with a pre-allocated virtual slice big enough for five
values, actually stored in the Container. This is useful because
Go's allocator has size classes for 16 and 32 bytes, and the
Container comes in at 24 bytes worth of storage -- meaning that if
you allocate a container, you're allocating 32 bytes anyway, so we
might as well use that space to avoid extra allocations.
This includes some test fixups because DeepEqual was testing
too much equality in some tests.
Also, we simplify unionArrayArray to postpone creating a Container
until we're ready.
On a 64-bit machine, the slices in a Container consume 72
bytes, and the Container itself is 80. But we only use one
slice at a time! This patch shifts us to keeping a single
slice in the Container, and converting provided slices to
and from that type when we want to update it. (It is not
safe to access the slice through the wrong type.)
We also add some new tests, conditional on a build tag
called `roaringparanoia`. These tests will be optimized
away entirely by the compiler when the tag isn't
present, because the conditionals use a const. These catch
possible errors like trying to access the bitmap slice
of a non-bitmap container.
We also eliminate all direct creation of Container literals,
so we can mess with the internals more. (On reflection
and study, we decided not to go to the fancier design where
references to .n and .typ were also converted to function
calls, which would have allowed packing those attributes
more tightly, because it was a lot more overhead and a lot
of work to keep track of.)
There's some circumstances where we appear to have been
relying on incorrect guesses about the nature of containers.
For instance, in xorBitmapRun, there's logic that makes sense
only if the output's a run container, but it's not, it's a
bitmap container. This creates strange behavior sometimes,
though. Several of these are corrected now.
