forked from mtusi2026/mtusi2026lab2
114 lines
4.6 KiB
Markdown
114 lines
4.6 KiB
Markdown
# Track 2: query plan and recovery
|
|
|
|
Hypothesis: at 300k messages the history index is worth keeping even under a
|
|
tight memory budget, while the membership index is the cheaper one to remove.
|
|
Recovery time should grow linearly with message count, so the dump-loss window
|
|
can be estimated from a few points.
|
|
|
|
## Dataset
|
|
|
|
One PostgreSQL 16.10 database, `messenger_research`:
|
|
|
|
- 5,000 chats, 2,000 users, 72,300 memberships.
|
|
- 100k / 200k / 300k messages, timestamps spread over 90 days.
|
|
- Chat sizes are deliberately skewed (`random()^3`): the largest chat holds
|
|
about 6% of all messages, most chats stay small.
|
|
- Probe user 1 belongs to the ten largest chats and every 100th chat, so the
|
|
chat-list and cross-chat feed queries always return rows.
|
|
- The app database `messenger` is not touched.
|
|
|
|
Schema is applied from `app/internal/database/migrations/0001_init.up.sql`.
|
|
The two compared indexes are:
|
|
|
|
- `chat_members_user_idx (user_id, chat_id)`
|
|
- `messages_chat_created_id_idx (chat_id, created_at, id)`
|
|
|
|
## Index experiment
|
|
|
|
`bench_indexes.sh` rebuilds the dataset at 300k, warms each query, then reports
|
|
the median of five `EXPLAIN (ANALYZE, BUFFERS)` runs. The comparison states have
|
|
exactly one of the two indexes; the script asserts that state and restores both
|
|
indexes at the end.
|
|
|
|
| state | user_chats ms | chat_messages ms | user_feed ms |
|
|
| --- | ---: | ---: | ---: |
|
|
| both indexes | 1.38 | 0.43 | 35.40 |
|
|
| only `messages_chat_created_id_idx` | 7.36 | 0.47 | 35.22 |
|
|
| only `chat_members_user_idx` | 1.40 | 57.63 | 80.40 |
|
|
|
|
Query shapes:
|
|
|
|
- `user_chats`: `chats JOIN chat_members WHERE user_id = $1 ORDER BY created_at, id LIMIT 50`
|
|
- `chat_messages`: keyset page of one chat on `(created_at, id)`
|
|
- `user_feed`: `messages JOIN chat_members WHERE user_id = $1` plus a keyset
|
|
cursor, ordered globally by `(created_at, id)`
|
|
|
|
Index sizes after `REINDEX` (300k messages, both present):
|
|
|
|
- `chat_members_user_idx`: about 3.5 MB
|
|
- `messages_chat_created_id_idx`: about 17 MB
|
|
- `messages` table including indexes: about 75 MB
|
|
|
|
Write cost (pgbench, 4 clients, 10 s, message-like inserts on a clone table):
|
|
2,719 tps with the messages index, 2,640 tps without it. The difference is
|
|
small and within run noise; the read benefit below is much larger.
|
|
|
|
## Recovery experiment
|
|
|
|
`bench_recovery.sh` recreates the database at each size from the migration,
|
|
seeds it, checks that both indexes exist, then runs `pg_dump -Fc` and
|
|
`pg_restore` into a fresh database. It verifies message and membership counts,
|
|
an MD5 fingerprint of every message row, and both indexes in the restored copy.
|
|
|
|
| messages | dump s | restore s | dump MiB | DB MiB | lost msgs at 878 RPS |
|
|
| ---: | ---: | ---: | ---: | ---: | ---: |
|
|
| 100,000 | 1.02 | 1.44 | 4.9 | 45.2 | 896 |
|
|
| 200,000 | 1.92 | 2.36 | 9.3 | 70.8 | 1,686 |
|
|
| 300,000 | 2.66 | 3.28 | 13.8 | 95.0 | 2,335 |
|
|
|
|
Linear fits (`N` = messages in millions):
|
|
|
|
- dump: `t = 0.23 + 8.20 * N` s, R² = 1.00
|
|
- restore: `t = 0.52 + 9.20 * N` s, R² = 1.00
|
|
- dump + restore: `t = 0.75 + 17.4 * N` s, R² = 1.00
|
|
|
|
The loss column uses the closed-loop 878 RPS already measured in
|
|
`REPORT.md`. `pg_dump` takes a consistent snapshot and does not block writers;
|
|
the estimate means "writes committed after that snapshot are lost if the dump
|
|
is the recovery point". Total outage including an offline restore is
|
|
`dump + restore` times the write rate (about 2.2k, 3.7k and 5.2k messages at
|
|
the three sizes).
|
|
|
|
## Decision
|
|
|
|
Keep `messages_chat_created_id_idx`. Without it a chat page goes from 0.43 ms
|
|
to 57.6 ms and the cross-chat feed from 35.4 ms to 80.4 ms. If exactly one of
|
|
the two indexes must be removed, remove `chat_members_user_idx`: it costs about
|
|
3.5 MB and saves about 6 ms on the chat list, while the history index costs
|
|
about 17 MB and prevents a two-order-of-magnitude regression on history reads.
|
|
If the budget allows 21 MB for both, keep both.
|
|
|
|
## Reproduce
|
|
|
|
Requires Docker Compose and the repository `.env` (`cp .env.example .env`,
|
|
then change `POSTGRES_PASSWORD`). Only the `postgres` service is needed.
|
|
|
|
```sh
|
|
docker compose --env-file .env up -d --wait postgres
|
|
./research/bench_indexes.sh
|
|
./research/bench_recovery.sh
|
|
python3 research/analyze.py | tee research/results/recovery.md
|
|
```
|
|
|
|
Outputs: `research/results/indexes.md`, `research/results/recovery.csv`,
|
|
`research/results/recovery.md`.
|
|
|
|
## Limits
|
|
|
|
- Synthetic skewed data, not a production trace.
|
|
- Single PostgreSQL node, warm cache, no concurrent writes during the query
|
|
benchmark.
|
|
- One dump/restore run per size; timings are indicative, not a capacity plan.
|
|
- The 878 RPS figure comes from the closed-loop client in `REPORT.md`; it is
|
|
not a maximum throughput claim.
|