Sqlite writes limit parallel scaling

[JukkaL]

I measured time spent in sqlite operations when running the mypy_parallel benchmark. When using 8 workers, sqlite writes were over 10x slower compared to using just 1 worker, likely because only one worker can be writing at any time. This seems to be one of the main sources of limited parallel scaling on macOS at least.

Here are some ideas which might help:

1. Instead of writing cache files in each worker, send them via IPC and have the main process write everything.
2. Use a separate extra cache file per worker, and the main process will copy per-worker cached data to the main database. Every worker reads from the main database.
3. Use a separate extra cache file per worker, and somehow allow each worker to read from the right database but always write to their own database.
4. Shard the database -- have 1 (non-exclusive) database per worker, and use module name based hash to choose the target database for both reading and writing.

Next steps:

• Measure on Linux as well
• Prototype some of the ideas and measure impact (at least ones that are easy enough to implement)

cc @ilevkivskyi

[JukkaL]

I could reproduce the issue on Linux as well (in a VM), though the regression was only about half as bad compared to macOS when using 8 workers instead of 1.

[ilevkivskyi]

TBH I don't understand how sending everything back to coordinator will help things. I guess we may need to figure out what exactly happens: is the problem that writers block each other, or that writes are blocking readers until commit, or something else?

Also one simple idea to try is to set isolation_level=None.

[JukkaL]

A quick prototype of idea 4 (sharded db) improved mypy_parallel performance by ~1.5x on macOS and by ~1.2x on Linux. it's a bit fiddly since we need to be careful to avoid deadlocks.

I'll also try isolation_level=None.

TBH I don't understand how sending everything back to coordinator will help things.

If writing cache files sequentially, performance is good (the same cache files will be written). There seems to be contention between writers. Possibly write transactions are left open for too long.

[ilevkivskyi]

A quick prototype of idea 4 (sharded db) improved mypy_parallel performance by ~1.5x on macOS and by ~1.2x on Linux.

This is interesting. Also sharding is a nice abstraction, i.e. caching logic will stay ~completely hidden inside metasore IIUC, and we don't need to complicate coordinator <-> workers communication protocol.

[ilevkivskyi]

One possible (minor) downside however, is that changing number of workers will invalidate the cache IIUC. We however may simply have fixed number of shards (say 16), instead of 1 per worker.

[ilevkivskyi]

Another random question: do writers block the database, or do they block the table? If it is the latter, we may also play with sharding the files2 table inside a single DB.

Anyway, @JukkaL I see you are already into this, so I will leave this up to you, I will work on the splitting PR follow-ups for now.

[JukkaL]

isolation_level=None only helps slightly, if at all. However, it might help together with the sharded db, and it would make it easier to avoid deadlocks, so it seems worth considering.

After a more careful measurement, macOS was ~1.3x faster with the sharded db (using 8 workers).

Another random question: do writers block the database, or do they block the table?

AFAIK, writers block the entire database.

[hauntsaninja]

This is a little surprising to me. Prior to enabling WAL, shouldn't we have been seeing "database is locked" errors from concurrent writes (assuming we tested on some type check that took more than the default five seconds)?

[ilevkivskyi]

@hauntsaninja In the parallel mode we commit after processing each SCC, and since writing cache is ~last thing that happens during SCC processing, the DB was locked for very short time even without WAL.