Methods and systems for coordinating migration for a database of a service are described herein. Multiple releases of the service may be simultaneously implemented, and these multiple releases may access a shared database. As new releases of the service are activated, the database may be incrementally migrated to a new data schema version. The new data schema version may be compatible with each release of the service that is in use. After a migration has begun, instances of the service may be instructed to perform database operations using methods compatible with the new data schema version. Continuation tokens may be returned during the migration, which indicate portions of the shared database that have not yet been migrated. If an error occurs during the migration, the continuation tokens may be discarded, and the migration may be restarted.