element-hq / element-hq/synapse
synapse allows an infinite number of one-time-keys to be uploaded, leading to inefficient `/keys/claim`
- Dominant language
- Python
- Stars
- 4.6k
- Forks
- 600
- Avg merge
- 5d 22h
- Merged PRs (30d)
- 51
Description
This issue has been migrated from [#15366](https://github.com/matrix-org/synapse/issues/15366).
---
Synapse imposes no limit on the number of one-time-keys which can be uploaded. Apart from the storage, that's a problem because `/keys/claim` isn't terribly efficient when there are lots of matching keys in the database:
```
explain
DELETE FROM e2e_one_time_keys_json
WHERE user_id = '@richvdh:matrix.org' AND device_id = 'KUMOTFKFVU' AND algorithm = 'signed_curve25519'
AND key_id IN (
SELECT key_id FROM e2e_one_time_keys_json
WHERE user_id = '@richvdh:matrix.org' AND device_id = 'KUMOTFKFVU' AND algorithm = 'signed_curve25519'
LIMIT 1
)
RETURNING key_id, key_json;
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
Delete on e2e_one_time_keys_json (cost=1.40..9.47 rows=1 width=37)
-> Nested Loop Semi Join (cost=1.40..9.47 rows=1 width=37)
Join Filter: (e2e_one_time_keys_json.key_id = "ANY_subquery".key_id)
-> Index Scan using e2e_one_time_keys_json_uniqueness on e2e_one_time_keys_json (cost=0.70..4.72 rows=1 width=13)
Index Cond: ((user_id = '@richvdh:matrix.org'::text) AND (device_id = 'KUMOTFKFVU'::text) AND (algorithm = 'signed_curve25519'::text))
-> Subquery Scan on "ANY_subquery" (cost=0.70..4.73 rows=1 width=38)
-> Limit (cost=0.70..4.72 rows=1 width=7)
-> Index Only Scan using e2e_one_time_keys_json_uniqueness on e2e_one_time_keys_json e2e_one_time_keys_json_1 (cost=0.70..4.72 rows=1 width=7)
Index Cond: ((user_id = '@richvdh:matrix.org'::text) AND (device_id = 'KUMOTFKFVU'::text) AND (algorithm = 'signed_curve25519'::text))
(9 rows)
```
it looks like neither of those index scans use the key_id in the index. It can take several seconds for a user with 10K one-time keys.
Replacing the `IN` with `=` fixes that, but I haven't tested on sqlite.
Suggest we fix the query *and* stop users uploading more than 200 or so OTKs per device.
Contributor guide
Research direction
Start at the `/keys/claim` query and the one-time-key upload handling described in the issue. Compare the shown DELETE query with SQLite behavior, then verify that claiming remains efficient with many keys and that uploads are limited to roughly 200 keys per device.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- postgresql, python, sqlite
- Domain
- backend-api-design, databases, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100