A messaging system uses a cloud storage backup system for messages and a temporary storage for messages that are not deliverable to offline devices at the time that the messages are sent by one or more messaging servers. The messages are backed up through a synchronization process that transfers a batch of a plurality of messages rather than a single message or an entire database of messages. A conversation state can be synchronized first before synchronizing messages through the transfer of one or more batches of messages.