Generally described, aspects of the present application correspond to maintaining a message stream for a network-based data store, which stream includes messages reflecting modifications to the data store. Messages within the stream may be used to revert a state of the data store to a prior point in time reflected within the messages of the stream, such as by “rewinding” operations on the data store by use of the messages within the stream. Messages in the stream may further be used to asynchronously update a replica of the data store.