Не пытайтесь сделать что то мегаоптимальное сразу, это как выше сказали сложно... но можно подойти к вопросу творчески.
Во первых, храните не сообщения пользователей, а чаты, соответственно и шардинг делайте не по пользователям а по чатам. Тогда сообщения одного пользователя будут размазаны сразу по нескольким серверам но сгруппированы по чатам, как раз чтобы сам чат (с любым количеством пользователей, обычно их количество в чате значительно меньше общего количества пользователей проекта) задействовал только один сервер.
Во вторых, разделяйте оперативную и архивную информацию, для чатов это окно сообщений, видимое пользователям по умолчанию при открытии чата (не все же вы загружаете, всегда это происходит порциями), но не делайте правило переноса между этими группами как аксиому, пусть это будет некий системный процесс, который на основе нагрузки и статистики перемещает данные. Если ограничить пользователей по редактированию и удалению старых сообщений, то возможно использовать разные подходы по хранению оперативной и архивной информации, разные технологии индексации или даже самого хранения, в т.ч. оптимизации по буферизации... грубо говоря хранить readonly архивные данные можно где угодно, ведь для доступа к ним не требуется синхронизация и блокировки.
Не обязательно городить прослойку, дающую информацию по тому где что хранится, например место размещения архивных сообщений чата можно хранить там же где оперативная, ее все равно будут запрашивать , мало того нужно везде стараться делать так, чтобы сразу было ясно, на каком сервере хранятся данные, самый простой способ это хеш от идентификатора (простой остаток от деления на количество серверов более чем подходит).
Оперативные данные будут генирировать самую высокую нагрузку, всеми силами делайте так, чтобы эти данные были как можно дольше в оперативной памяти, т.е. сервера, обрабатывающие их должны быть настроены отлично от архивных.
p.s. массовые рассылки от проекта или партнеров (не кривитесь, все это хотят делать) не делайте обычными чатами, а то будут получаться странные выверты с мегадублированием информации и огромной нагрузкой в момент их проведения, пусть это будет отдельная сущность (остальное разрулите в интерфейсе). С другой стороны, если вам нужна обратная связь, в тот момент, когда пользователь вдруг решает ответить в такой недочат - конвертировать его в обычный.
