BTW. The websocket thing is something I wonder about often. In a use-case with reasonably frequent updates, is it better to have clients hold an active but mostly idle tcp connection (like websocket), or make them do polling, or some long polling?

A proper async IO runtime can probably handle tons of connections at once anyway. 10k, 100k, maybe 1M.

Also with a gossip-like note fetching, it should be feasible to have lots moderately sized relays, without a loss to usability, so maybe worrying too much about scaling vertically a single relay is unnecessary.

Otherwise some client&application level load balancing might fix the problem. Eg when connecting to a relay it answers with a list of keyspace "shards" (possibly overlapping for redundancy), and then connects/queries to the actually node that holds the data. That would allow reasonably simple and flexible scaling of the relays without complex server side load balancing.