Computer-implemented techniques for automatically coordinating application schema changes in a distributed data storage system. The techniques improve the operation of a computing system by automating the deployment of application schemas changes to a distributed data storage system in a manner that does not introduce orphaned data inconsistencies or integrity inconsistencies to the application data stored in the distributed data storage system. The techniques include a schema change deployment protocol that ensures that all of the database servers of the distributed data storage system are using no more than two consecutive versions of the application schema at any given time.