Repairing database on the fly for millions of users

This is a story of a messaging app used by billions of users. The app followed an extremely strong model of privacy. The app never persisted the user’s data on the servers. All the communication is end-to-end encrypted. A lot of users of this app, especially, on Android would regularly uninstall and...