pageserver: support 1 million relations

[jcsp]

We do not currently define a maximum number of relations that we support, but it is known that beyond about 10k relations things get dicey. The exact number of issues is unknown, but the primary architectural issue is how we store RelDirectory as a monlithic blob that gets rewritten whenever we add/remove one.

Postgres itself does not define a practical limit on relations per database: the hard limit is approximately one billion, but it is well known that the practical limit is much lower, and dependent on hardware+config:

• https://www.postgresql.org/docs/current/limits.html
• https://www.pgcon.org/2013/schedule/attachments/283_Billion_Tables_Project-PgCon2013.pdf

To pick an arbitrary but realistic goal, let's support+test 1 million tables. This is realistic because:

• Something like an array of relation sizes is only single digit megabytes with a million tables (whereas with a billion tables, such structures would likely need to be disk-based rather than simple in-memory structures)
• If we the can create a few thousand tables per second, then a test that creates a million tables can run in minutes, not hours (i.e. within the envelope of what our CI supports)

A tiny initial step in this direction is #9507, which adds a test that creates 8000 tables (not very many!) to reproduce a specific scaling bug in transaction aborts. That test currently has a relatively long runtime (tens of seconds) because our code for tracking timeline metadata is still very inefficient.

The goal is to make it work "fast enough", in the sense that a database is usable and things don't time out, but not necessarily to implement every possible optimisation. For example, logical size calculations will be expensive with 1 million relations (requiring many megabytes of reads from storage), and that is okay as long as the expense does not cause the system to fail from the user's point of view.

• Replace RelDir with a more scalable alternative, such as using a sparse keyspace a la aux files
  • PoC PR at DNM/PoC feat(pageserver): migrate reldir to sparse keyspace #10316
  • read path migrations feat(pageserver): store reldir in sparse keyspace #10593
  • config item to enable it feat(pageserver): add reldir migration configs #10439
  • index_part persistence to avoid flipping
• Instead of interleaving relation sizes with data, store them in their own region of the keyspace (or even combine them into the new storage for RelDir). Eliminate imitate_logical_size, and update eviction logic to intentionally retain recent layers rather than accidentally through logical size calculation
• Test creating and dropping 1 million relations with this more scalable store. We should see that runtime is reasonable (minutes), and memory+disk space used is O(N) with table count (not O(N^2))
• Implement code for rewriting metadata to the new format on startup. This should run very early during startup so that no other parts of the code need to understand the old format: we can then maintain this for a long time. will have two read paths instead.
• Automated tests that have a snapshot of an old-style tenant and use it to continuously check that our latest code can still load such a tenant (extend test_historic_storage_formats)
• Asymptotic scaling: measure scaling of relation creation/drop & compute startup with relation count, and ensure it is at most O(N)
• A much broader test for high relation counts: ensure that compaction runtimes are as expected, that logical replication works as expected. This will need writing in collaboration with the compute team to cover the appropriate gamut of postgres features. If this encounters unforseen issues, then spin these off into other github issues: this Epic is for the storage support for high table counts.
• pageserver: slow get_rel_exists() during WAL ingestion with many relations #9855
• Benchmark creating many tables and databases #9986

Out of scope:

• High database counts (Neon cloud already limits databases per project to 500 by default)
• Revising pg_stat (Persist pg_stat information in pageserver #6560 ) code to handle large relation counts (current code skips writing pg_stat if the snapshot exceeds a size threshold)
• Any postgres CLI/tooling issues around high relation counts