Выбор БД: MySQL vs MongoDB?

Redis — совсем не простое key-value хранилище. Оно поддерживает более сложные структуры данных, такие как хеши и списки. Насколько я понял условия, оно как раз очень хорошо подойдет для задачи (при этом будет, скорее всего быстрее Mongo). Как-то так:

message:1 => {userId: 10, text: "Сообщение юзеру 10"}
message:2 => {userId: 20, text: "Сообщение юзеру 20"}
...
messagesQueue: [1, 2, ...]

И далее (псевдокод):

$nextMessageId = $redis->lpop("messagesQueue");
list($userId, $text) = $redis->hmget("message:{$nextMessageId}", "userId", "text");
sendNotification($userId, $text);