matrix-org / matrix-org/matrix-rust-sdk
[meta] Adopt a new cross-process state invalidation strategy
- Dominant language
- Rust
- Stars
- 2.3k
- Forks
- 500
- Avg merge
- 1d 16h
- Merged PRs (30d)
- 106
Description
The `CrossProcessLock` has been introduced to deal with the following problem:
- a process $P_1$ uses the SDK, starts syncing, starts updating data here and there
- process $P_1$ is suspended
- a process $P_2$ starts and does similar things, such as the notification process on iOS for example (called NSE)
- then later, process $P_1$ is resumed, and keeps going
- there is a problem now: $P_1$ is not aware that the data has changed: it can be dramatic!
The initial PR to implement the premise of the `CrossProcessLock` was https://github.com/matrix-org/matrix-rust-sdk/pull/2140. The goal was to forbid access to the store to $P_2$ until the lock acquired by $P_1$ has not expired: It is lease-based lock.
Then, way later, we've introduced the concept of _generation_ inside this lock to detect when the lock is _dirty_, https://github.com/matrix-org/matrix-rust-sdk/pull/5672. It helped $P_1$ to know that $P_2$ has rightfully and successfully acquired the lock, and has made modification on the data, and thus, $P_1$ has to reload its data/state.
This work was a robuster, generalized implementation of a similar idea tailored to the crypto store. We wanted to generalize it to apply this technique to all the stores using this lock, because we want all stores to be “cross-process friendly”, https://github.com/matrix-org/matrix-rust-sdk/issues/4874.
Sadly, we recently found a design flaw. It sounds obvious now it's written down, but we didn't foresee it. The problem is described in https://github.com/matrix-org/matrix-rust-sdk/issues/6404, but I'll repeat it here:
- process $P_1$ acquires the lock
- process $P_1$ is suspended
- lock's lease expires
- process $P_2$ acquires the lock
- process $P_2$ modifies the `OlmMachine`
- process $P_2$ stops
- process $P_1$ is resumed
- process $P_1$ keeps modifying the `OlmMachine` without having refreshed it!
This scenario by-passes the _generation_ technique we've introduced because the lock was rightfully acquired by $P_1$ and $P_2$, and the generation was checked correctly. We've a flow here 🙂. The biggest problem is that the process can be suspended at any time, and we don't now about it.
## Solution
The solution is to remove the `CrossProcessLock` entirely. We don't need it. What we need is the _generation_ technique we've introduced but applied differently. Instead of:
1. check the generation
2. if dirty:
- reload the data
- jump to 4
3. if clean:
- jump to 4
4. work on the data
we must do **the opposite**:
1. start a transaction
2. work on the data
3. check the generation
4. if dirty:
- rollback the transaction (so without any commit)
- reload the state
- jump to 1
5. if clean:
- commit the transaction
Where to implement the transaction is yet undecided: on Rust side, on database side? On the Rust side, it can still be suspended but we can use mutex. On the SQLite side, it's harder to be suspended I suppose, but no lock easily available as far as I know.
### Looping
This version introduces a loop, similar to a CAS (compare and swap). We must be careful and introduce a threshold to not enter an infinite loop: even if very unlikely in practice, in case of special starvation, we could create a loop with many iterations, which can have a non-negligible impacts on resources.
We could also check the generation between 1 and 2 to preemptively avoid step 2 in case the generation is already dirty.
### Atomicity: the Big Unknown
We must ensure that the following operations:
- compare and update generation
- commit the transaction
are atomic, otherwise it's still possible to have a race condition here. One transaction can detect it's clean, another concurrent transaction from a different holder can also detect it's clean, but it's not okay to have two concurrent transactions from different holders to detect it's clean at the same time.
The generation mechanism, as implemented in `matrix-sdk-sqlite`, is “atomic” from the SQLite point of view. It has resolved a bug compared to the old similar implementation in the crypto store, by the way, see #5672:
https://github.com/matrix-org/matrix-rust-sdk/blob/ef565f18b5bb4efbfc7b5f95e7ce023d743e05a6/crates/matrix-sdk-sqlite/src/event_cache_store.rs#L601-L629
However, if we mix that with a transaction, it's no longer atomic. We must ensure it can be the case:
- either by finding a way to detect a conflict in SQLite
- or by ensuring the atomicity of these 2 operations (just this sentence alone make me nervous: how to make _two_ operations atomic without a lock…)
### Bonus
This approach would make `CrossProcessLock` obsolete, and would remove the _lease renewal_ task, that was a source of _busy errors_ in SQLite. This _lease renewal_ task was implying too much writes and was creating slowness, up to errors sometimes. Something we're chasing for a long time now.
### Next
Once we've found a way to resolve the problem raised in the previous section, we must update the code:
1. Implement this _generation_ + clean and dirty mechanism in all the stores: in-memory, SQLite and IndexedDB (we discussed dropping the support for IndexedDB entirely, and replace it by SQLite compiled to Wasm)
2. Remove `CrossProcessLock`
3. Update all codes that use the `CrossProcessLock` to use the new API: this is possible if and only if states/data are correctly isolated
We may want to find the correct abstraction between an API in `matrix-sdk-common` and the database-end implementation for each stores we support.
---
- Close https://github.com/matrix-org/matrix-rust-sdk/issues/6404
Contributor guide
Research direction
Start with the generation implementation in crates/matrix-sdk-sqlite/src/event_cache_store.rs, especially the linked section, and trace CrossProcessLock users across the stores. Determine how transaction commit and generation comparison can be made atomic for the supported backends; done means an agreed design and an implementation plan covering the new API, lock removal, and store migrations.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust, sqlite, wasm
- Domain
- databases, distributed-systems
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100