Badger: Is it safe to store different values under the same key?

[JeanMertz]

I am using Badger for a stream sorting implementation. I use a timestamp-based byte array as the cache key when storing a value in Badger. This allows me to easily retrieve a set of keys from Badger at a later point in time, and have them sorted as expected.

Obviously, using a timestamp as key means duplicate entries can occur.

I can either implement some logic to append some incremental counter at the end of the key for duplicate entries, but that requires knowledge of this structure in several different locations, and also hurts performance as I have to deconstruct the key back to its original timestamp if I want to do anything with it.

Right now, I see that all duplicate entries are still stored, they just are stored as different _versions_ of the same key. Obviously in this case, it's not really different versions of the same key, it's actually entirely different values that happen to have the same timestamp key.

If I set AllVersions in my queries, and make sure I don't purge old keys, would this work as expected, or are there any gotchas I need to watch out for in this situation?

[manishrjain]

If you use AllVersions, it could be made to work, you just have to be careful.

By default, NumVersionsToKeep is set to 1, which means older versions would be removed during compactions. You need to set this option to max int. If you do, then your keys won't get removed, which means your value log GC would not GC anything. So, then, you'd need to delete the versions at some point (unless you're OK with keeping every write forever). Now the complexity increases. See, Badger sees the versions as representing one key. If you say Delete(key), it would also automatically delete all lower versions of that key, which most likely you don't want.

I'd recommend having them as different keys, with some prefixes or suffixes to differentiate among them. It's the cleanest approach with least issues.

[JeanMertz]

One more question about AllVersion, as I'm still a bit confused as to _what_ "all versions" means.

I now have a test running where unique keys are inserted, and periodically deleted in batches. I log the number of messages removed, and the "unique keys" in the cache (an iteration, _without_ AllVersion), and those values match perfectly.

However, if I also count the keys with AllVersions set to true, I get a number that's almost three times as high as the count without AllVersions, even though I am positive that currently no duplicate keys are being written.

Digging through the code, I did notice this comment:

https://github.com/dgraph-io/badger/blob/7af00762e98cf59c2ca6a774b49487b8903257c6/iterator.go#L438-L446

So does this mean that AllVersions doesn't really/only mean "show me all versions of currently existing keys, including duplicate values of the same key", but it also means "show me any versions that have already been marked as deleted, but which haven't actually been removed from the cache yet".

Is that correct?

I also saw this method in the code:

https://github.com/dgraph-io/badger/blob/7af00762e98cf59c2ca6a774b49487b8903257c6/iterator.go#L133-L136

So right now I'm assuming, if I use AllVersions and _only_ want to see non-expired, non-deleted versions of all existing keys, I should combine that with IsDeletedOrExpired(), is that correct?

If so, then thanks for the pointers 👍 I do want to note that the documentation surrounding this part of the API is a bit lacking though. AllVersions is somewhat ambiguous (since it also returns "invalid" versions) and there's no mention of it being closely related to IsDeletedOrExpired().

[manishrjain]

AllVersions would show you whatever we have in the LSM tree. Now, as I mentioned before, during LSM tree compactions, these versions might be removed. So, don't count on them being present in your next iteration with AllVersions.

These settings are meant for advanced usage of Badger (Managed DB), and not typically recommended. That's why they're under-documented.

I should combine that with IsDeletedOrExpired(), is that correct?

Yes. If you're using SetWithDiscard, then you'd want to use the DiscardEarlierVersions API as well.

Still, I'd not recommend relying upon the versions for your use case, because your versions are technically distinct keys. You're relying too much on the internal workings of Badger.

[JeanMertz]

Thank you for the further explanation. And I should have clarified that I am indeed no longer pursuing this solution, as per your warning/advice. However, I still used AllVersions for logging/debugging purposes and to verify that no key collision occurs anymore with a high volume of data passing through the cache.

In relation to that; I did notice that with this pseudo-code:

it = txn.NewIterator(badger.IteratorOptions{})
for it.Rewind(); it.Valid(); it.Next() {
  uniqueCount++
}
it.Close()

it = txn.NewIterator(badger.IteratorOptions{AllVersions: true})
for it.Rewind(); it.Valid(); it.Next() {
  if it.Item().IsDeletedOrExpired() {
    continue
  }

  allCount++
}
it.Close()

(this code runs in a "stop the world" situation, so there should be no difference in actual records in the cache between the first iteration, and the second, unless of course triggered internally by a Badger-managed goroutine)

At some point, while the cache is at rest (no records being added or being deleted), the uniqueCount and allCount values match up perfectly. But as soon as messages are being deleted, the uniqueCount decreases as expected, while the allCount does not.

An example from our logs shows:

2018-05-30 08:51:52.000 [all:2143599] [unique:441725] Collected cache statistics.
2018-05-30 08:57:45.000 Received interrupt signal. Exiting.
2018-05-30 09:05:26.000 Configured caching database.
2018-05-30 09:25:58.000 [all:441725] [unique:441725] Collected cache statistics.
2018-05-30 09:35:11.000 [deleted:441672] Produced messages.
2018-05-30 09:44:08.000 [all:441725] [unique:53] Collected cache statistics.
2018-05-30 09:54:11.000 [all:441725] [unique:53] Collected cache statistics.
2018-05-30 10:04:07.000 [all:441725] [unique:53] Collected cache statistics.

Some interesting things here:

• the first log line is from when this application had already been running for some time, storing records, and deleting (some of) them again.
• the all and unique counts widely differ
• at some point, the application is terminated (meaning Badger is properly closed), and then started again
• now, the all and unique counts match up again, even though nothing actually changed in the database itself, other than closing and opening it.
• then, the application deletes 441672 records from the cache
• immediately, without having to close the Badger DB, the unique count is correct again (441725-441672=53), but the all count is out-of-sync
• this stays that way, until eventually the database is closed and opened again, at which point the two counts stay in sync until another batch of messages gets deleted.

Are there some internal optimisations at play here that make this "as expected", or could this be indicative of a problem?

Is there some more filtering I need to do, besides IsDeletedOrExpired(), to only get "valid" records, including records with the same key?

Note I am not using SetWithDiscard, but only Set, and if everything is working as expected (which it seems it is), then every key should only have one version, so all and unique should always match up.

[manishrjain]

This is as expected -- those numbers might or might not match, because Badger only marks keys as deleted. All the LSM tables on disk are immutable. The actual removal of those keys happens during compactions, which run in the background. We also force compact level 0 during close, and looks like all your data is in Level 0 - Level 1, which is why you're able to perfectly match these numbers. If your data grows, these numbers might never match up.

You wouldn't need to worry about IsDeletedOrExpired if you don't use AllVersions.

[JeanMertz]

Thanks again for the elaboration.

The only thing unclear to me is:

those numbers might or might not match, because Badger only marks keys as deleted.

I _am_ using IsDeletedOrExpired() as you can see in the code snippet above, but it's (apparently) still counting those records, is that expected behaviour?

[manishrjain]

Once a version is deleted or expired, all versions below it must also be discarded. Your iteration loop is just skipping the version that is deleted, not discarding lower versions.