All committers have signed the CLA.

@manishrjain movekeys are only deleted once it is determined a vlog file satisfies the discard ratio and is rewritten.

However, the discard calculation includes movekey entry size in the total number of bytes (not the discard bytes) in the discard ratio calculation even if that movekey is for a key that has been deleted.

If your discard ratio is 50% and half of a file is used by movekey entries for deleted keys, it will never satisfy the discard ratio allowing it to be rewritten and subsequent movekey deletion.

There are only two approaches I can think of to solve the problem.

Always check if underlying key for each movekey has been deleted to determine if an entry should be discarded.

Or, automatically write a delete movekey entry every time a delete key entry is written. Although that approach will not cleanup existing DB vlog files already in that state and would require a routine similar to the first approach to perform an initial cleanup.

I added db_test.go BenchmarkDbGrowth to demonstrate the size growth problem with badgerMove keys.

If you update value.go discardEntry line 1628 to return false, it will cause the DB size to continue to grow for that test.

The deleteMoveKeysFor function is supposed to delete the move keys but right now it doesn't work

because the current implementation of iterators does not return duplicates (keys with same version).
So if the existing state was

level 1 => MoveKeyFoo{version:1, vlog:x}

After rewriting value log file x we will have

Memtable => MoveKeyFoo{version:1, vlog:y}
level 1 => MoveKeyFoo{version:1, vlog:x}

The deleteMoveKeysFor function will never see the key with vlog:x because the iterator skips duplicates keys.

Even if the iterator were to not skip this key, we will end up losing data if deleteMoveKeysFor function reinserts an old move key with delete marker. Let's assume deleteMoveKeysFor function worked. The new state of the system would be

Memtable/Level 0 => MoveKeyFoo{version:1, vlog:x, DELETE} 
Memtable/Level 0 => MoveKeyFoo{version:1, vlog:y}
level 1 => MoveKeyFoo{version:1, vlog:x}

Compaction would drop all the keys except the one with the delete marker and a Get(foo) would return the wrong value.

Thanks for fixing this @ou05020 🎉