Patent ID: 9405761
Filing Date: 2016-08-02
CPC Classification: G06F

Claim Text:
1. A computer-implemented method for verifying data integrity for garbage collection with limited memory, the method comprising: traversing, by a garbage collector executed by a processor, a namespace of a file system of a storage system to verify data integrity of segments arranged in a plurality of levels in a hierarchy, wherein an upper level segment includes one or more references to one or more lower level segments, wherein each file of the file system includes one or more of the segments, wherein traversing the namespace comprises: maintaining a data structure, wherein the data structure includes a plurality of entries, each storing states of a group of a predetermined number of the plurality of segments compressed therein, in response to receiving a request for transitioning a first of the plurality of segments from a first state to a second state, retrieving a first entry value of a first of the plurality entries associated with the first segment, generating a second entry value based on the first entry value, the first state, the second state, and a value obtained from a first lookup table based on the first segment, and writing back the second entry value to the first entry of the data structure; and in response to determining all entries of the data structure reach a predetermined final state, performing a garbage collection process on the segments stored in the storage system.