Scaling Asynchronous reclamation of free space in de-duplicate multi-controller storage systems is disclosed. In one example, a set of de-duplicated data segments/blocks organized in a hierarchical data structure is received, the set of de-duplicated data segments/blocks are allocated across a plurality of controllers of the file system, where each de-duplicated data segment is restricted to be co-allocated to the same controller as the reference(s) referencing the de-duplicated data segment/block in the hierarchical data structure. In various embodiments, the file system is traversed, each controller of the file system updates its own local live vector and reclaim storage space that are not marked as alive.