US Patent 9578120 Messaging with key-value persistence

Techniques are described for providing a messaging service that employs a distributed key-value store for message persistence. On receiving a message to be enqueued for subsequent delivery, a message identifier is generated and employed as a key to store the message in the key-value store. The message identifier may be generated based on an available location in a message tracking data structure. In some cases, the message tracking data structure may be an append tree data structure that is substantially self-balancing as an increasing number of messages are tracked using the append tree data structure. The message tracking data structure may be further employed to determine a message identifier for a message to be vended from the key-value store.