[meta] Adopt a new cross-process state invalidation strategy

[Hywan]

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 #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, #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”, #4874.

Sadly, we recently found a design flow. It sounds obvious now it's written down, but we didn't foresee it. The problem is described in #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:

matrix-rust-sdk/crates/matrix-sdk-sqlite/src/event_cache_store.rs

Lines 601 to 629 in ef565f1

	// Learn about the `excluded` keyword in https://sqlite.org/lang_upsert.html.
	let generation = self
	.write()
	.await?
	.with_transaction(move |txn| {
	txn.query_row(
	"INSERT INTO lease_locks (key, holder, expiration)
	VALUES (?1, ?2, ?3)
	ON CONFLICT (key)
	DO
	UPDATE SET
	holder = excluded.holder,
	expiration = excluded.expiration,
	generation =
	CASE holder
	WHEN excluded.holder THEN generation
	ELSE generation + 1
	END
	WHERE
	holder = excluded.holder
	OR expiration < ?4
	RETURNING generation
	",
	(key, holder, expiration, now),
	|row| row.get(0),
	)
	.optional()
	})
	.await?;

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 Crypto must refresh its state when the cross-process lock is dirty #6404