Epic: scalable metadata key-value store in pageserver

[jcsp]

The pageserver is good at storing pages referenced by a block number, but not so good at generic key-value data.

There are two places we have large key-value maps without a good place to store them:

• "aux files", which store data that in vanilla postgres is stored as small files on local disk (see https://github.com/neondatabase/neon/pull/6613, which discusses a broader range of possible solutions for storing these)
• Relation metadata, especially logical size, which we currently store in one page per relation (see rel_size_to_key)

A more scalable store will enable:

• Robust deployment of logical replication features that require potentially huge numbers of aux files (100k+)
• Support for very high relation counts, e.g. more than 1 million.

This epic assumes:

• that the same underlying data structure will serve both purposes, and also be reusable in future: for example if we wanted to store an index of LSN to timestamp or some other pageserver-internal index, we could use it there too.
• that our KV store will be layered on top of our existing page store, rather than inventing some totally separate storage stack.
• that the values in the KV store will be of bounded size that reasonably fits inside a page (i.e. we will not have a layer that spreads values across pages)
• that while the KV store might be large in terms of value counts, it will be small enough to fit in memory.

Goals:

• Calculating logical size for N relations should not require reading N pages
• Writing N aux files should not require writing N pages
• Writing N aux files should not scale the size of a single page as O(N)

Possible implementation

We could write a hash table that uses a page for each slot.

Scale: 1 million relation sizes at ~16 bytes per relation -> use about 2000 pages.

Writes to pages will typically be repetitive: e.g. the logical size of a relation may be re-written very many times.

A single page per table can be used as a "superblock" that describes the number of slots that exist and the range of block numbers which contain them. This may be used to implement re-sharding of the table, as an optimization to avoid using a large page count for small databases (a very common case).

For storage, hash table slots will have a delta and value format. Runtime state will be used to bound the depth of deltas for each slot: the image value for the slot will be periodically written to enforce this bound. This will result in some I/O amplification for logical sizes compared with the current scheme of simply writing each size as an image every time, to a different page. We can control this I/O amplification by choosing the page count.

Where a particular KV collection requires larger values than typical (e.g. pg_stat can be multiple megabytes), we should use separate KV collections for the "big" values to avoid incurring heavy write amplification from mixing them with more frequently updated smaller values.

So within each timeline, we would have three instances of this new hash table:

• Relation metadata
• Small Aux Files
• Large Aux Files

[skyzh]

After a short discussion with John, two more design choices in my mind:

• Reuse the current architecture: maybe we can have a third value type for storing AUX values (we have delta + image for now); an alternative design is to have a separate LSM tree.
• Keep the current write path: for all data we want to write to the pageserver, the easiest design could be that we still write them into the safekeeper and apply them at the pageserver; an alternative design is to allow the compute node to directly write to the pageserver.

[skyzh]

an early draft of the proposal -> https://www.notion.so/neondatabase/DRAFT-Generic-Key-Value-Storage-on-Page-Server-fbe03ae11d4a4eb7b60ef800f89f0fa3

[jcsp]

Aux file part is:

• https://github.com/neondatabase/neon/issues/7462