Sled: Subscription events are not consistent with the order of operations inside transactions

[D1plo1d]

Note to the maintainers: I'm hoping this is helpful in determine where to take the implementation next but please let me know if it's becoming too much about subscriptions at once.

This is two subscription issues that are both cause by the TransactionalTree writes HashMap's arbitrary iteration order and the fact that it only stores the final IVVec value for each key:

1. Subscription events are not ordered by writes inside transactions

Scenario:

1. watch_prefix "thing"
2. start a transaction
3. insert at key "thing_1"
4. insert at key "thing_2"
5. commit

Outcome

As I understand it the subscription will now have an arbitrary event order for the inserts of thing_1 and thing_2.

Preferred Outcome

It would be useful to me as a developer to be able to modify two things in a specific order with the atomic guarantees of a transaction and have those effects come out of the subscription in the same order as well.

For example, if I wish to add two items to a single threaded work queue such that thing_1 gets executed before thing_2 I cannot do this atomically at the moment.

The work queue could of course be rewritten to be entirely stored in a single key but this looses some benefit of subscriptions as I have to then write my own logic to determine which item(s) changed and also the work queue would risk becoming arbitrarily large and slow to deserialize.

2. Subscriptions receive only a single event for multiple writes to a key in a transaction

Scenario:

1. watch_prefix "thing"
2. start a transaction
3. insert at key "thing_1"
4. insert at key "thing_1"
5. commit

Outcome

This one I expect to be controversial but I wanted to at least start the conversation. If I make two changes to a single key in a transaction I think I'd expect to see two events in the subscription as if they were made non-transactionally (serialized?) however at present AFAIK the subscription will AFAIK only ever see the final state.

This second scenario is more of an observation that might not be congruent with expectations - I was at least surprised to see it but I'm not 100% sure how this plays in with transaction atomicity or if I'd prefer something else. What do y'all think - what would be your expected behaviour here?

[spacejam]

The way I've imagined addressing this is to create a new Event type for Batch writes, and any transaction or writebatch will be sent to subscribers as the whole writeset at once, avoiding any ordering issues. All writes from a transaction appear atomically, so strictly speaking there is no ordering between them, from the perspective of a transaction which occurs "instantaneously".

[D1plo1d]

I like this solution a lot. It sounds like it's stands to solve a bunch of my concerns quite cleanly all at once.

[D1plo1d]

Would it be possible to store the set of Events in the Batch in a data structure that maintains iteration order? Then not only do I have atomicity but also a clear ordering for times like my job queue example above?

[spacejam]

1178

[spacejam]

@D1plo1d I'm not sure about insertion order, because it's something that has some significant consequences for the ordering of non-overlapping keys in the entire system, which imposes a bottleneck on multithreaded workloads, as everything would need to be serialized through a single mutable sequencer of some sort. Right now the extent that I want to go in term of ordering is guaranteeing order for updates on a single key, and updates for transactions (which write all of their writes at a single atomic moment, and don't have any logical order within the transaction).