Знаю, что многие нагруженные сервисы просто делают денормализацию данных (не только для чатов, но и для новостей и т.п.). Как правило, каждое отправленное сообщение в общем чате (или один на один) попадает одновременно каждому участнику чата в его личную ленту/таблицу/плоский файл. Это решает проблемы загруженности (каждый пользователь читает только свой набор отдельных файлов/таблиц/строк и не нагружает общие хранилища данных, где могут быть миллиарды записей при решении задачи "в лоб"). Также это решает проблему с удалением сообщений (один может удалить переписку, а другой - оставить себе на память). А ещё это автоматически решает проблему видимости сообщений в общем чате - если человека пригласили в беседу только что, то он не видит предыдущие сообщения участников. За попадание сообщений в "личную зону" каждого пользователя отвечает не база, а контроллер, который дублирует сообщения всем.
Да, некоторые операции усложнятся, но часто ли вам нужно количество отправленных пользователем личных сообщений, или какая-нибудь статистика по личным перепискам всех пользователей, чтобы ради небольшого выигрыша по скорости доступа к этим данным делать всю систему отправки сообщений с тормозами? Для всех таких редко нужных запросов можно прикрутить отдельный поисковый индексатор и счётчики, map/reduce-алгоритмы и т.п.
Представьте, что вы отправляете копии пригласительные на свадьбу друзьям и родственникам. Каждая копия - это отдельная сущность. И если один приглашение разорвёт - то у остальных оно не должно разорваться автоматически. Кто-то захочет что-то на нём написать, например, телефон сантехника. Кто-то сомнёт и подложит под ножку качающегося стола. Кто-то сделает ксерокопию и пригласит ещё кого-то на вашу свадьбу без вашего ведома. При этом - это будут разные пригласительные, с одинаковым содержанием. То же самое с сообщениями и чатами.
Кстати, необязательно хранить систему личных сообщений в базе. Можно, но необязательно. Для этого даже тупо xml'ы/json'ы подойдут. Ведь что чаще всего нужно от чата собеседнику? Чтобы 1) отправить сообщение, чтобы его прочитали; 2) получить сообщение; 3) заглянуть в историю чата. Это прекрасно ложится на модель "каждому пользователю - по отдельной копии каждого чата". Да, денормализация, но почитайте выше пример про пригласительные и ксерокс. В вашем случае контроллер будет делать "ксерокопии" письма и отправлять их всем адресатам. А что с этим письмом делать дальше - уже дело каждого.
