Чат на PHP: узкое место БД — как решить?

Есть задача организовать простой чат с веб-интерфейсом и полной историей на действующем сайте на самописном движке (PHP5.3.3/MySQL5.1). Гугление по существующим решениям ничего хорошего не дало, либо избыточно, либо производит ощущение «наколенной поделки» и чаще всего давно не поддерживается, да и хотелось бы иметь одну архитектуру и стиль кодирования. В общем принято решение реализовать самостоятельно. С кодированием особых проблем нет, прототип реализовали, но нагрузочное тестирование с разными вариантами индексов и таблиц показало, что при уже ~20 хостах «читателей» и одним «писателем» в секунду MySQL затыкается (VDS c 1Гб RAM, мускулу половина отдана, и 2ГГц проц, nginx+php-frpm под Debian) даже на денормализованной таблице, т. к. кэшированию средствами БД запросы не поддаются (фильтры у каждого «читателя» свои, ибо приват, фильтрация в серверном приложении вряд ли будет эффективней чем в БД, как мне кажется, а у клиента недопустима). А хотелось бы на этом «железе» хотя бы 40-50 держать помимо основной нагрузки. Что может помочь? Опыта «хайлоад» нет, возникли такие идеи:

— написать демона для чата на субдомене, чтобы читал в основном потоке из БД только при старте (последние N сообщений) или редких специфичных запросах, хранил их у себя в памяти процесса (убивая старые), а писал в БД только «логи» для следующего старта (тогда фильтрация будет эффективна, имхо, плюс её можно будет осуществлять опережающе и инкрементно, храня сами сообщения в едином пуле, а для каждого читателя добавлять в список ссылок на «его» сообщения при поступлении сообщения от «писателя» лично для него или публичного, и удалять их оттуда при прочтении)

— аналогичным образом задействовать мемкэш (хотя пока с трудом представляю как обеспечить целостность, до того только с файловыми кэшами работал, которые сами не «испаряются») для обычного PHP-обработчика (то есть чтобы куча воркеров имела доступ к общему пулу сообщений и инкрементным личным спискам ссылок на них между запросами)

— перевести чат на NoSQL СУБД (какую? главная задача эффективная фильтрация по паре полей последних записей, типа WHERE timestamp > {last_time} (или id>{last_id}) AND (recipient_id IS NULL OR recipient_id={user_id}) ORDER BY timestamp (или id) DESC LIMIT {max_records} )

Что стоит попробовать или ещё какие могут быть варианты? Демона писать не хочется, так как усложнит администрирование и сервера, и собственно чата (аналог IRC команд делать?), опыта работы с кэшем и NoSQL практически нет.