Test-and-set and other atomic operations?

[pchickey]

I am working on a project which needs to access a key-value store from a Wasi component, but I need an atomic test-and-set operation for my application. Just as an example, the native code in my project currently uses DynamoDB's TransactWriteItems to implement TAS on a single value in the database by guarding on a value at the start of the transaction.

Test-and-set is just one of a large number of atomic operations offered across the field of key-value stores. The only atomic operation provided by this interface at this time is atomic increment. I expect that most key-value store users will end up needing some more atomic primitives than just increment - TAS or some other primitive for a fallible transaction is required for a broad range of applications. What are the plans in this proposal for serving those needs?

[thomastaylor312]

Hey @pchickey perfect timing! I was actually just bringing this up with @kate-goldenring yesterday since Spin and wasmCloud have been the ones working on many of the implementations. We have heard this as well from our users. We originally got rid of compare and swap because the intricacies were a little complex, but seems like that was a mistake. Basically what we need to do is figure out a portable way to do this. Each KV store does it a bit differently so that is what was causing problems initially

I would love to try and get this in before the RC, but since both spin and wasmcloud have actual implementations out, I wonder if it would be better to add in a 0.2.1 so we can use @since to add it in in a non-breaking way.

[pchickey]

Glad this is something you are working on. Exactly how to introduce it is up to you: if you have an interface you are ready to commit to, then putting it into the spec without any gates and it becomes part of the RC and then whatever the initial release is. You also have the option of putting it in behind an unstable gate for now, and making it part of a later release.

[Mossaka]

As @thomastaylor312 said, we used to have a compare-and-swap operation, and then we removed the operation and left an open question about the cas_id (see this discussion). This was the compare-and-swap operation Taylor designed:

compare-and-swap: func(key: string, value: list<u8>, cas-id: u64) -> result<bool, error>;

Will this operation be useful in your use cases?

[thomastaylor312]

Ok, finally got back around to this. I did some digging across a wide range of things used as KV stores and this is what I found:

Redis: Transactions TiKV: CAS with comparing value Dynamo: Transactions NATS KV: CAS with revision number CosmosDB: CAS using an etag value with if-match Google Firebase: Transactions MongoDB: Atomic operations (findAndModify) RocksDB: Transactions Memcached: CAS with a CAS token Cassandra and ScyllaDB: Transactions (with the IF clause) Aerospike: Generation number or transactions Etcd: Transactions Bbolt (golang): Transactions Sled (Rust): CAS with value comparison

So things basically boil down to 3 possible ways of doing compare and swap:

1. Transactions
2. CAS ID/Token
3. Value comparison (often in form of a transaction)

So here is my thinking for what we should do for CAS operations in a way that doesn't add the need for a new API (i.e. needing to fetch a CAS ID):

compare-and-swap: func(key: string, old: option<list<u8>>, new: option<list<u8>>) -> result<bool, error>;

To insert a new value, you'd pass a none for old. For deletion, you'd pass none for new. This should be doable for any of these KV stores. For example, if you had a CAS ID, you can fetch the current value with the CAS ID, compare it to the given old value, and then use your CAS ID to update. For a transaction based system, you can map that to a comparison within the transaction. This might have some inefficiencies for larger values, but does lead to the simplest API. Any thoughts @pchickey @Mossaka?

[Mossaka]

For example, if you had a CAS ID, you can fetch the current value with the CAS ID, compare it to the given old value, and then use your CAS ID to update.

Are you saying if CAS ID is used, then the key will be regarded as the CAS ID?

Looks good to me. A compare-and-swap operation is definitely needed

[thomastaylor312]

Are you saying if CAS ID is used, then the key will be regarded as the CAS ID?

Sorry I think I wrote something confusingly. I was just referring to implementation details for different systems. Basically most systems will have to adapt their method of doing CAS to follow this. The whole point was just to say that I think it is doable

[pchickey]

Thanks for working through this, your design looks good to me. I don't have enough expertise in that range of KV stores to be certain all of them support these semantics, but I trust your research.