1. A method, performed by a processor, for managing data in a data storage having data deduplication, comprising: to efficiently recover or reclaim failed data in the data storage, in response to a portion of the data storage determined to be inaccessible: querying, by the processor, an identifier of a user data segment by examining a corresponding back reference data structure to determine if the user data segment references a particular storage block, the storage block being associated with both a reference counter and the identifier of the back reference data structure; wherein: if the outcome of the query is negative, the user data segment is determined not associated with the particular storage block, and if the outcome of the query is positive, the user data segment is warranted be examined further to determine if the user data segment is associated with the particular storage block; wherein further examining the user data segment includes performing: inspecting metadata of the back reference data structure associated with the inaccessible portion of the data storage, inspecting the identifier of the user data segment in the data storage, and inspecting metadata of user data segments whose identifiers returned a positive query outcome for at least one of the back reference data structures associated with the inaccessible portion of the data storage, and wherein the metadata and the identifier of the user data segment is inspected to determine the association with the particular storage block in lieu of scanning all metadata of all user objects in the data storage thereby efficiently identifying the failed data for reclamation.