Adding a method to MapHandle to retrieve the last version a key was modified

[Eddy Ashton (eddyashton)]

This is a feature we want both for internal features (rekey ledger entries should point to the version where the previous key was written, so we can traverse the chain of all secrets) and as an external request for use in apps.

Given a handle and a target key, we want to retrieve the last time this was written to. This is supported by the underlying data structures - we already store this, we just don't expose it at all. So the question is how it should be exposed.

Some important details:

1. Writes from the current transaction do not have a version. You cannot ask when you will be applied, only when the last change was applied.
2. This needs to introduce a read-dependency on that last change, as though you had read the value itself, so that if someone else writes to it before you commit you conflict and are retried.
3. If a key is removed, it should look the same as a key which never existed. We don't want to be tied into supporting deleted key metadata forever. So we need at least a special value to indicate this case (either nullopt or kv::NoVersion).

I see 2 possible approaches here:

1. Getting a version is always associated with the current value you can read. Either std::pair<Version, Value> get_versioned_value(Key), or if they're separate methods then if you call them straight after each other they would return the same as above. This entails exposing a special Version for this transaction's own writes - luckily we already have kv::NoVersion for this. This works fine if you're writing this historic version to the same table its read from, ie - it assumes version, value = foo->get_versioned_value(k); foo->put(k, {version', value'};. But its non-modular - if an earlier part of this transaction has already written to the key you wanted to query, you can no longer get its last-written-version.
2. Getting a version always returns the previous written version. We'd need a good name for this, perhaps Version get_stored_version(Key). I was wary that this semantics could lead to confusion (after a write, get_version refers to fundamentally different state than get/has), but I think we can get around this with naming. This lets you do some logic with the previously written version (if not value), anywhere in the transaction flow. In particular, if you're storing these in another table that's fine - you can divide the work and do it in any order. This means we don't need a special value for "the version of your writes".

I have a draft implementing option 1, but after some more thought I think we should do option 2.

[Amaury Chamayou (achamayou)]

I do prefer option 2 as well, it seems more natural. Perhaps get_version_of_last_put() or get_version_of_last_write()?

Adding Soren Bleikertz (@soren-da) to the discussion, since he has expressed interest in the feature.

[Julien Maffre (jumaffre)]

get_version_of_last_put seems a little confusing to me, e.g.:

auto handle = tx.rw(map);
handle.put(key, value);
auto version = handle.get_version_of_last_put(key);

I would expect version to refer to the put on the second line above, but it doesn't.

[Amaury Chamayou (achamayou)]

Well that's the semantics for option 2. It's really get_version_of_last_put_before_this_tx(), but that's pretty long. Maybe get_version_of_last_committed_put()?

[Eddy Ashton (eddyashton)]

I don't want to refer to this as committed - we're trending towards "committed means its been through consensus" (which we used to call global commit). This state that was "locally committed" we generally haven't needed to describe in the public API, but I like "applied" (and maybe one day we'll change Tx::commit to Tx::apply). I had get_version_of_last_put but see Julien Maffre (@jumaffre)'s point. I'm now back to get_previous_version or get_stored_version?

Anyway, there's now a PR at #2137.

[Amaury Chamayou (achamayou)]

get_last_applied_version(), get_version_of_last_applied_put()?

I personally find get_previous_version() a little misleading, because I would expect to receive the value at the previous version, considering what get() does. But maybe that's just me?

[Eddy Ashton (eddyashton)]

Maybe we can't encode the precise semantics of this in the name, and need people to read the docs, so get_version() is sufficient?

[Julien Maffre (jumaffre)]

Option 2. seems more appealing because it is simpler and it avoid the cost of deserialising the value when this one isn't needed. I'm assuming that get_stored_version(key) would have to return a std::optional<Version> to cover the case of the key not existing (ever) in the store (I don't think we ever use/return kv::NoVersion in the KV API)?

[Amaury Chamayou (achamayou)]

Using std::optional<Version> is safer/more explicit, but means we can only have a single semantic "no version". We can for example never expose "we happen to know this was deleted at version N, because it's not been compacted yet" distinctly from "we have no record for this value but it may have existed and been deleted since".

I think that's fine though, and so I would favour an optional.

[Eddy Ashton (eddyashton)]

I agree we want to avoid exposing deleted (negative) Versions, and preferably also the distinction between never-existed and known-deleted.

I'm not sure if we use kv::NoVersion externally already - its definitely in the docs but I don't think we currently expect apps to use it for anything?

So yes I think std::optional<Version> is a good wrapper for now.

[Amaury Chamayou (achamayou)]

Link #2137