Как правильно организовать очереди?
я конечно мимокрокодил с другого стека, но как вариант:

запрос идет на какую-то проксю, откуда по по sha1 от идентификатора сессии перекидывает на нужный сервер. т.к эта логика будет отрабатывать только на момент хендшейка - она не станет боттлнеком. а если будет упиратся в потолок то вертикальное маштабирование тут будет стоить копейки (в сравнении с ценой всей остальной инфраструктуры). Если пинг важен - можно еще L4 (спереди) и раскидывать на разные регионы.

в этот момент мы уже получаем равномерное распределение пользователей по серверам И возможность гарантировано по идшнику понять на каком с серверов висит коннекшн. самая очевидная проблема - автоматический скейлинг этого всего в обе стороны. бо прийдется много жонглировать. условиях не идеального коннекта/загруженой сетке тут будут обрывы (но возможно это и допустимый компромисс).

как узнать какой сервис на каких пользователей подписан
по идентификатору мы сразу понимаем на какой конкретно инстанс идти. если обрыв коннекшена - сходить куда-то в окестратор уточнить куда теперь слать данные. 

хранить эту связь в redis можно и в редис. по сути прийдется хранить только маски какой диапазон на какой сервер идут. и при скейлинге - обновлять.

Или на каждого пользователя создавать по очереди? Или это все одна очередь и каждое сообщение должно быть вычитано каждым инстансом сервиса_1 а затем отфильтровано?
если честно выглядит как оверхед, не вижу проблемы чтоб все пихать в 1 очередь, с которой воркеры будут разгребать работу. только перепроверьте что ваша очередь действительно гарантирует что сообщение прочитают именно 1 раз, у того-же амазоновского скса формулировка про "точно 1 раз".
Если клиент не закрывает соединение с конкретным инстансом (или если закрыл, то ответ не должен получить), то посмотрите в сторону RPC, вот с помощью чего оно работает, вот примеры.
Если результат требует много вычислительных ресурсов и повторять нежелательно, то либо создавать очереди под каждого клиента, либо где-то кэшировать результат (например, в СУБД).