compare and swap design

[pchickey]

A resource cas has two methods: a constructor, and a method current: func -> result<option<list<u8>>, error> for reading a value of a key, with an implicit borrow of the resource as its first argument. Calling this prior to a swap doesn't seem useful - it is either a duplicate of store.get, which incurs another database operation, or it must error. Then swap: func(cas: cas, value<list<u8>>) -> result<_, cas-error> takes ownership of the resource cas, which means the method current can't be called after it - the passed in resource will no longer be available to the caller, but some new one might be given in the cas-error variant. So I don't think the constructor of cas is actually what we want, if the point is to put an optional accessor in the error.

If you switched swap to just take the borrow<bucket> and key:string instead or a cas, it wouldn't entirely solve the problem, which is that implementors need to know at the time the swap call is made whether the value from the operation will be read - otherwise they have to transfer it from the database to the implementation unconditionally, and store it until the cas resource is dropped.

Instead, we could eliminate a lot of complexity by eliminating cas-error and resource cas and just having two functions:

swap: func(bucket: borrow<bucket>, key: string, value: list<u8>) -> result<bool, store.error>;
swap-with-read: func(bucket: borrow<bucket>, key: string, value: list<u8>) -> result<tuple<bool, list<u8>>, store.error>;

[ogghead]

Jumping in here as I have just created a draft implementation of CAS for AWS on the Spin platform, and the CAS interface seems like it could be modified to encourage correct usage.

I wonder if this could use a form of "TypeState" pattern to ensure that users must call current before calling swap to guarantee atomicity -- e.g. UnlockedCas with current: func -> result<(option<list<u8>>, LockCas), error> and LockedCas with swap would ensure users call current first, then swap

I perhaps am not seeing the use-case for calling swap without fetching the existing data first -- but as some databases only support optimistic locking, the current interface leads to subtle differences in implementation behavior across providers that could frustrate users when they swap implementation -- Redis provides atomic transactions and can guarantee that no other operation runs on data after a current call but before a swap call, while many other implementations cannot guarantee an exclusive lock during that window

[thomastaylor312]

I perhaps am not seeing the use-case for calling swap without fetching the existing data first

Based on the research I did before working on this, several key value stores use a CAS ID of some kind to perform an atomic swap operation. The point of the design was so that you didn't have to call store.get, then create a CAS, and then do the operation.current was to allow you to fetch the value if you did want to do the compare part and then swap to actually insert the data. Some KVs allow you to read and write as part of a transaction and others just let you get a CAS ID and use that when inserting to make sure you're not overriding. My whole point was to avoid the read in transactional contexts. Could have been premature optimization on my part though!

but as some databases only support optimistic locking, the current interface leads to subtle differences in implementation behavior across providers that could frustrate users when they swap implementation -- Redis provides atomic transactions and can guarantee that no other operation runs on data after a current call but before a swap call, while many other implementations cannot guarantee an exclusive lock during that window

This is the trade off of being generic. The only guarantee of this CAS operation of this interface is that if you swap, you're not going to mangle any data that may have been changed since you started the CAS operation. I should have documented this, but there are no guarantees that current is the absolute latest.

I do like the idea of current -> swap but I would like to do a comparison for implementing this across other types of KVs to make sure it can map properly. I think my only feedback for your suggestion is that the constructor for a CAS fetches the value and what you called a LockCas, so there would be no current function, just a swap for the CAS. This would also mean we'd change the error variant that returns a new CAS to also return the new value along with it.

[ogghead]

Based on the research I did before working on this, several key value stores use a CAS ID of some kind to perform an atomic swap operation. The point of the design was so that you didn't have to call store.get, then create a CAS, and then do the operation.current was to allow you to fetch the value if you did want to do the compare part and then swap to actually insert the data. Some KVs allow you to read and write as part of a transaction and others just let you get a CAS ID and use that when inserting to make sure you're not overriding. My whole point was to avoid the read in transactional contexts. Could have been premature optimization on my part though!

That's fair, I think (my personal) confusion lay in what is expected behavior here in stores that do require a CAS ID when you don't call current -- should implementations make an API call to get a CAS ID when CAS is created?

Currently, in the Spin AWS and Azure implementations, a CAS ID is only fetched when users call current, and the implementations fall back to a less atomic behavior (failing only if multiple concurrent writes happen at the exact same time, but open to staggered writes overwriting each other) if swap is called without current. Even in transactional implementations, there is currently no transaction created until current is invoked.

Alternatively (and perhaps more in line with the design), we could make necessary idempotency calls when the CAS is created? If we go that route of making necessary idempotency API calls on CAS creation, then current loses much of its function though. Users would incur the cost of current even if they do not intend to read the current value. But, it would ensure that users are always getting the idempotency guarantees expected from atomic operations.

This is the trade off of being generic. The only guarantee of this CAS operation of this interface is that if you swap, you're not going to mangle any data that may have been changed since you started the CAS operation. I should have documented this, but there are no guarantees that current is the absolute latest.

I do like the idea of current -> swap but I would like to do a comparison for implementing this across other types of KVs to make sure it can map properly. I think my only feedback for your suggestion is that the constructor for a CAS fetches the value and what you called a LockCas, so there would be no current function, just a swap for the CAS. This would also mean we'd change the error variant that returns a new CAS to also return the new value along with it.

Exactly this! It sounds like we're tentatively aligned on approach. I will dig into how this would work for all the stores implemented in Spin and report back if I see any hiccups in mapping the interface to each KV. Assuming that maps cleanly, should I create a PR here to update the WIT?

[ogghead]

I mapped the reworked interface to several of the implementations in Spin -- my only concern is that this rework would be a breaking change to the interface, but that might be unavoidable. We can get the best of both behaviors by having two functions (and this is more in line with what @pchickey proposed):

new and new-with-read where in both functions, the implementation is expected to start a transaction/optimistic lock, but only new-with-read returns the value

[Mossaka]

I think the new interface makes sense as long as it maps clearnly across all implementation.

should I create a PR here to update the WIT?

Yes, that would be nice :) Could you please create a PR here to update the WITs and markdown files to reflect this new change, @ogghead ?

[thomastaylor312]

Yep, sorry for the delay here. Thank you @ogghead! Breaking changes are fine here as we can rev

[ogghead]

Sounds good, I will aim to create a PR for these changes this week when I have some free time

Update: Got this out locally with Spin implementations, will clean it up and make a PR this weekend.