Thesql_connect() system error :111

You can use a database such as mySQL just fine. Especially if the table structure is simple and indexed well. I would presume a record for each message would create a need for inserts, but not updates, which would keep index rebuilding needs low too.

If you wanted to scale, just create a read-replica for the querying of the messages and send the write queries to the master server.

Want to scale even more, I suppose you could implement some sort of memcached intermediate level, but this would help more on expanding performance on the read side, not the write side particularly (since you'd have to write them eventually, and you could lose them in memcached in the interim potentially).

In short - mySQL is fine. Other options include cloud options from amazon like DynamoDB and/or nosql options, but not essential.

Your primary key is fine. I don't see a reason to change it.

The issue you are having is because you are basing your query on the messsage_id and it being without gaps. You could base your queries on the message_time column (I suppose this holds the datetime that the message was sent).

Even if you keep using the messsage_id for the queries (assuming that biggest id means the latest message - which may not always be correct), you can still write a query that returns always 20 messages, gaps or not - just change ORDER BY message_time DESC to ORDER BY messsage_id DESC in the 3 places it appears:

SELECT *
FROM
  (   ( SELECT message_id, message_time,
               'U <- F' AS direction
               message_read, message_body
        FROM member_messages AS msg
        WHERE message_to = :userId
          AND message_from = :friendId
     --   AND message_deleted = 0
        ORDER BY message_time DESC
            LIMIT 20 
      )
    UNION ALL
      ( SELECT message_id, message_time,
               'U -> F' AS direction
               message_read, message_body
        FROM member_messages AS msg
        WHERE message_to = :friendId
          AND message_from = :userId
          AND message_deleted = 0
        ORDER BY message_time DESC
            LIMIT 20 
      )
    ORDER BY message_time DESC
        LIMIT 20 
  ) AS tmp 
ORDER BY message_time ASC;

Other issues:

You probably meant to have the deleted = 0 check on both cases (message sent by me to friend and sent by friend to me). If yes, undelete the commented line above - and note that AND has higher precedence than OR in SQL. The condition you probably wanted to use was (note the removed pair of parenthesis):

WHERE (    MSG.message_to = :userId
       AND MSG.message_from = :friendId
      OR 
           MSG.message_to = :friendId
       AND MSG.message_from = :userId
      )
  AND ...

So, you could write the query like this:

SELECT *
FROM member_messages AS msg
WHERE (    MSG.message_to = :userId
       AND MSG.message_from = :friendId
      OR 
           MSG.message_to = :friendId
       AND MSG.message_from = :userId
      )
      AND message_deleted = 0
ORDER BY message_time DESC
    LIMIT 20 ;

I used UNION for efficiency reasons. Complicated conditions with OR may not be optimized very well. You could also add an index on (deleted, message_from, message_to, message_time).