A suggestion of SST compaction for better space reclaim.

[wangleiin]

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

$ go version
go version go1.11.4 linux/amd64

What version of Badger are you using?

v1.6

Does this issue reproduce with the latest master?

Yes

Recently I saw a increasing memory usage as well as data accumulation of WAL in dgraph raft progress. Then I export KVs and find most of which are deleted records. As dgraph raft record all entities and delete older ones during snapshot, most of these should be removed during SST table compaction.
After a view of Badger compaction strategy, I realize keys can only be removed when compact to a non-overlay next level.
Review func compactBuildTables in file github.com/dgraph-io/badger/levels.go

func (s *levelsController) compactBuildTables(
	lev int, cd compactDef) ([]*table.Table, func() error, error) {
	topTables := cd.top
	botTables := cd.bot

	var hasOverlap bool
	{
		kr := getKeyRange(cd.top...)
		for i, lh := range s.levels {
			if i <= lev { // Skip upper levels.
				continue
			}
			lh.RLock()
			left, right := lh.overlappingTables(levelHandlerRLocked{}, kr)
			lh.RUnlock()
			if right-left > 0 {
				hasOverlap = true
				break
			}
		}
	}
...

There's hasOverlap check that works.
As preserved keys like !badger!head write to every single level0 table and inherited by all lower levels, there tends to be hasOverlap, even for neighborhoods that are being compacted with empty lower levels.
For example:
L0: sst5 sst6 sst7
L1:sst4
L2:empty
...
We want to compact sst5, sst6 and sst7 in level0 to level1, as sst4 in L1 overlap with tables in L0, the result will be:
L0: empty
L1:sst8, sst9
L2:empty
...
Assuming that there are some deleting records in sst5/sst6/sst7, those records will write back to sst8/sst9 and it's hard to remove these records.

I think it could be improved by check like codes below.

func (s *levelsController) checkOverlap(lev int, tables []*table.Table) bool {
	var hasOverlap bool
	kr := getKeyRange(tables)
	for i, lh := range s.levels {
		if i <= lev { // Skip upper levels.
			continue
		}
		lh.RLock()
		left, right := lh.overlappingTables(levelHandlerRLocked{}, kr)

		lh.RUnlock()
		if right-left > 0 {
			hasOverlap = true
			break
		}
	}
	return hasOverlap
}

func (s *levelsController) compactBuildTables(
	lev int, cd compactDef) ([]*table.Table, func() error, error) {
	topTables := cd.top
	botTables := cd.bot

	var hasOverlap bool
	hasOverlap = s.checkOverlap(lev+1, cd.top) || s.checkOverlap(lev+1, cd.bot)
...

Here we check if L0 and L1 overlap with L2 etc. while omitting overlap between L0 and L1, as they will compact later.
Please let me know if it works or any unknown faults.

Thank you!

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[stale]

This issue was marked as stale and no activity has occurred since then, therefore it will now be closed. Please, reopen if the issue is still relevant.

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[jarifibrahim]

I wonder if we're actually keeping keys when they have overlap as mentioned in the original post. I'll verify this with a test and get back.

[jarifibrahim]

I wrote a bunch of test to verify this and it seems like you were correct @wangleiin . I've raised #1166 to fix this. Thank you :)

[wangleiin]

@jarifibrahim I'm glad to know that and thanks for your replying :)