Method or apparatus for scalable file verification in a deduplicated filesystem

Abstract

One example method includes calculating a size of a fingerprint hashtable, calculating a number of verification passes that are needed, partitioning a fingerprint index table into index ranges corresponding to the number of verification passes needed, and during each verification pass for each index range: (1) finding all Ln segments in a namespace, and adding the Ln segments to the fingerprint hashtable and to a walk-vector data structure, (2) scanning a container set and locating any Ln segments in the container set; (3) reading all Ln-1 segments pointed to by the Ln segments and adding the Ln-1 segments to the fingerprint hashtable and to the walk-vector data structure; (4) repeating 1-3 for all levels of the tree structure that include Ln segments; and (5) comparing the fingerprint hashtable with the portion of the fingerprint index table corresponding to the index range to identify any missing Ln segments.