A reference counter corresponding to a base chunk of a plurality of chunks of a deduplicated data object is maintained, where the reference counter is incremented in response to an insertion of any chunk that references the base chunk, and where the reference counter is decremented, in response to a deletion of any chunk that references the base chunk. A queue is defined for processing dereferenced chunks of the plurality of chunks. The dereferenced chunks in the queue are processed in a predefined order, to free storage space.