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

we're seeing incredible growth in our real-time features, and we're now approaching 500k concurrent websocket connections to our existing gateway. it's clear we're hitting a bottleneck with a single gateway instance. we need to scale this horizontally, but there are complexities. how do you efficiently route messages to specific users when their websocket connection could be on any of dozens or hundreds of gateway instances? we're thinking about things like a distributed lookup service or even shared state across gateways, but this adds complexity. also, the per-connection memory overhead, even if small, starts to add up significantly at this scale. what architectural patterns and technologies have people successfully used to scale websocket connections to over a million concurrent users?