Apparatus and method for updating map structures in an object storage system. A server communicates with users of an object storage system over a network. A plurality of data storage devices are arranged into locations to store and retrieve data objects of the users. A storage controller is associated with each location to direct data object transfers between the data storage devices of the associated location and the server using an existing map structure that describes the data objects in each location. A management module is adapted to generate a new map structure, migrate at least one data object from an existing location described by the existing map structure to a new location described by the new map structure, and to distribute the new map structure to each of the storage controllers after the migration of the at least one data object.