Scaling WebSocket connections: how do you handle 1M+ concurrent connections?

We're currently dealing with scaling our WebSocket connections and it's becoming a significant bottleneck. We're approaching 500,000 concurrent connections, and a single WebSocket gateway instance is clearly becoming insufficient. The main challenge is not just handling the connections themselves, but efficiently routing messages to specific users or groups of users. We've looked into horizontal scaling of the gateway instances, which helps distribute the connection load. But then, how do you efficiently find which instance a specific `userId` is connected to if you need to send them a targeted message? We're exploring solutions like Redis Pub/Sub combined with service discovery, or even custom routing layers. Memory overhead per connection is also a concern. Each connection, even if idle, consumes some resources. What architectural patterns have you found successful for managing over a million concurrent WebSocket connections, especially when targeted messaging is a core requirement?