Чат на PHP: узкое место БД — как решить?
Во-первых, надо уточнить, что за VDS. Если мастерхост, то сразу предупредите, т.к. это отдельная песня.

Во-вторых, нужно понять, из-за чего тупит mySQL. Выше правильно писали про lock на время записи.
Так же может не успевать диск (из-за ограничений VDS).

Я бы попробовал перевести в бд innodb и commit в 0 выставить (сброс раз в секунду на диск).

Далее есть такая штука как представления. И у них есть режим с кэшем в памяти. А SQL запросы уже к нему делать. К тому же их можно наплодить на разные случаи.

Ещё хорошо бы не забыть про memory таблицы. Скажем, писать ещё и в не memory, но читать массово только из неё.

Попутно стоит помнить про индексы. Их отсутствие делает select долгим, а чрезмерное присутствие долгим insert. Да и сами индексы новички обычно неправильно делают.

Ещё бы я вернулся к настройкам VDS, потому что они режут среднюю нагрузку по процу, памяти и дисковым операциям. Вас тупо может это резать. И заодно ещё вспомнил про объём БД в памяти. Если там уже много данных, а кэши не большие, то резать по диску будет.
ну если хочется именно БД то я-б думал в сторону промежуточного слоя — т.е. данные из него в БД пишутся асинхронно при определенном заполнении а чтение только из него, из бд в него данные заливаются только в слычае тотального краша, П.С. это мысли не более, тему про «невозможность кеширования запросов» не осилил