A method, computer program product, and system for maintaining referential integrity is described. A method may comprise migrating a migration document in a migration shard from a first location to a second location. The method may further comprise adding a first location identifier associated with the first location of the migration document to metadata associated with the migration shard. The method may also comprise adding a second location identifier associated with the second location of the migration document to the metadata associated with the migration shard. The method may additionally comprise adding one or more shard identifiers to the metadata associated with the migration shard, each of the one or more shard identifiers corresponding to a shard that includes a document that may be referenced by one or more documents in the migration shard.