A method of performing a file system consistency check in a distributed, segmented file system, includes: analyzing primary objects of a first segment of the file system to determine if a first primary object points to a second primary object of a second segment separate from the first segment, storing, if the first primary object points to the second primary object of the second segment, a first indication indicating that the first primary object points to the second primary object of the second segment, the first indication indicating an expected location of the second primary object; analyzing a shadow directory of the selected segment to determine an expected location of a third primary object, and an expected pointer of the third primary object indicative of a location and a name of a fourth primary object, the third primary object being contained in a segment other than the first segment; and storing a second indication indicating the expected location of the third primary object and the expected pointer of the third primary object.