Flatten leaves behind 2 or more versions

[hpucha]

What version of Go are you using (go version)?

$ go version
go version go1.13.1 darwin/amd64

What version of Badger are you using?

release/1.6

What did you do?

We are experiencing an issue with badger GC (release 1.6) not being aggressive enough, and was hoping to get some help.

We start with an ingest phase of loading ~17GB of data (unique keys) and then receive updates for about 50% of the keys over time (same set of keys are updated mostly, every few hours). The total size of the data despite the updates stays around the same (17G).

When we run such a workload for several hours, we see that the size of vlog files steadily keeps growing. We see periods of value log gc but it doesn't recover enough space to keep the data with in some bounded percentage of 17G. We experimented with different gc thresholds, but that was not helpful. In fact a very low threshold of 0.01 done very frequently resulted in #1031.

Tracking down the problem led me to investigate LSM compaction since I do see that we keep multiple versions of keys there without discarding and hence I believe that vlog GC correctly claims that there is nothing to GC.

One issue was #767 related to WriteBatch. However, even when I call Flatten I see that we have at least two versions of keys when the tables have overlap (In our case, num versions to keep is 1 and both with L0/L1 and L0/L1/L2 configs I see this behavior). I am able to repro this with a synthetic workload.

My guess is that the overlap check over here
https://github.com/dgraph-io/badger/blob/master/levels.go#L575

is only applicable to the Deleted/Expired case and should not be applicable for the numVersions case (similar to the lastValidVersion check).

Fix as in here https://gist.github.com/hpucha/a5168affa99248fd69f69b0c5f723c72/revisions?diff=unified seems to work, but I am not confident since I am not familiar with all the possibilities. It would be great to get feedback if this is plausible or if there are some correctness issues with this. Or other pointers on how to debug and why we are seeing 2 versions even after Flatten would also be very helpful.

What did you expect to see?

Flatten leaves behind one version per key.

What did you see instead?

Flatten leaves behind multiple versions (2 or more)

[hpucha]

Here is a test to reproduce this issue.

https://gist.github.com/hpucha/b080bbbe3fefacaf8852596cc19753cb

[jarifibrahim]

Hey @hpucha , Flatten is supposed to consolidate all tables on a level, it doesn't give any guarantee about the number of version/keys.
In your case, you're seeing two or more version because all those versions might not be below the discard timestamp (think of discard timestamp as a point in time before which all data can be deleted and it wouldn't affect the current state of the database)

badger/levels.go

Lines 498 to 501 in 1b0c074

	// Pick a discard ts, so we can discard versions below this ts. We should
	// never discard any versions starting from above this timestamp, because
	// that would affect the snapshot view guarantee provided by transactions.
	discardTs := s.kv.orc.discardAtOrBelow()

So if you have 4 versions (t4, t3, t2, t1) and discard timestamp is 3, we'll discard t2, t1. Which means the database still has t4 and t3.

badger/levels.go

Lines 559 to 567 in 1b0c074

	if version <= discardTs && vs.Meta&bitMergeEntry == 0 {
	// Keep track of the number of versions encountered for this key. Only consider the
	// versions which are below the minReadTs, otherwise, we might end up discarding the
	// only valid version for a running transaction.
	numVersions++
	lastValidVersion := vs.Meta&bitDiscardEarlierVersions > 0
	if isDeletedOrExpired(vs.Meta, vs.ExpiresAt) ||
	numVersions > s.kv.opt.NumVersionsToKeep ||
	lastValidVersion {

[hpucha]

Thank you so much for taking a look @jarifibrahim

That does make sense wrt the discard timestamp. However, when I logged what was happening, I observed that in a large majority of cases it was below the discard timestamp but was still being retained because of the overlap check. This is the change I am running locally with
https://gist.github.com/hpucha/a5168affa99248fd69f69b0c5f723c72/revisions?diff=unified

So in the above example, assuming a discardTs of 2 (since the check is <=) t2 will be considered in L563. numVersions will be 1. Since numVersions is not greater than 1 (NumVersionsToKeep), skipKey won't be populated. The next time around for t1, we will pass the numVersions check, but if the table being compacted has overlap with a lower level, we will add t1 back too. And hence we accumulate multiple versions.

[jarifibrahim]

@hpucha I understand what you're trying to say but even if there is an overlap for a key, the skip key will be set and all the following versions will be discarded. If the number of versions is set to 1, there will be only one version of the key. This might not happen after the first compaction because keys can be on multiple levels but they will be cleaned up eventually.

Here's a test to prove it.
https://gist.github.com/jarifibrahim/1dc1736a0122f93d25799cd5724f3859#file-db_test-go
The test creates 6 tables. All tables have single key foo
Level 0 => foo5, foo4, foo3, foo2
Level 1 => foo1
Level 2 => foo0

Since the number of versions is set to 1, all the other versions except foo5 should be dropped after compactions (not first compaction, but multiple compactions)

=== RUN   TestCompactionVersions
badger 2019/12/18 15:22:45 INFO: All 0 tables opened in 0s
Before compaction
k: foo v: 5 
k: foo v: 4 
k: foo v: 3 
k: foo v: 2 
k: foo v: 1 
k: foo v: 0 
badger 2019/12/18 15:22:45 DEBUG: LOG Compact. Added 2 keys. Skipped 3 keys. Iteration took: 52.92µs
badger 2019/12/18 15:22:45 DEBUG: Discard stats: map[]
badger 2019/12/18 15:22:45 INFO: LOG Compact 0->1, del 5 tables, add 1 tables, took 5.014664ms
After level 0 compaction
k: foo v: 5 
k: foo v: 4 
k: foo v: 0 
badger 2019/12/18 15:22:45 DEBUG: LOG Compact. Added 2 keys. Skipped 1 keys. Iteration took: 51.33µs
badger 2019/12/18 15:22:45 DEBUG: Discard stats: map[]
badger 2019/12/18 15:22:45 INFO: LOG Compact 1->2, del 2 tables, add 1 tables, took 5.265063ms
After level 1 compaction
k: foo v: 5 
k: foo v: 4 
badger 2019/12/18 15:22:45 DEBUG: LOG Compact. Added 1 keys. Skipped 1 keys. Iteration took: 63.03µs
badger 2019/12/18 15:22:45 DEBUG: Discard stats: map[]
badger 2019/12/18 15:22:45 INFO: LOG Compact 2->3, del 1 tables, add 1 tables, took 4.998396ms
After level 2 compaction
k: foo v: 5 
--- PASS: TestCompactionVersions (0.05s)
PASS

[jarifibrahim]

This should be fixed by #1166

[jarifibrahim]

This has been fixed via #1166