Data storage services are provided for clients for backup of data objects from the clients. A data object is sent to a first location in a first storage device. A determination is made if the data object was successfully stored at the first location, and if so, meta data corresponding with the data object is stored, wherein the meta data includes first path information on a first data path of the data object to the first location. The data object is migrated from the first location to a second location in a second storage device. A determination is made if the data object was successfully stored at the second location, and if so, second path information on a second data path of the data object is added to the second location to the meta data corresponding with the data object, to update the meta data.