Detecting missing segments and identifying files impacted by the missing segments using a single pass distributed scan
A method for managing data in a storage system includes: partitioning segments to generate buckets; assigning a portion of the buckets to a first storage node; collecting a partition of the segments assigned as child segments; identifying: a first set of child segments that maps to the portion of the buckets, and a second set of child segments that maps to a bucket of a second storage node; storing: each of the first set of child segments to an LSM tree of the first storage node, the second set of child segments to a buffer; sending the second set of child segments to the second storage node; receiving a third set of child segments from the second storage node; comparing the first set of child segments and third set of child segments of the LSM tree against second child segments; and making a determination that a mismatch is occurred.
1 . A method for managing data in a storage system, the method comprising:
partitioning Level 0 (L0) segments of a segment tree to generate buckets;
assigning a portion of the buckets to a first storage node of the storage system;
collecting a partition of the L0 segments assigned to the first storage node as child segments;
identifying:
a first set of child segments of the child segments that maps to the portion of the buckets of the first storage node, and
a second set of child segments of the child segments that maps to a bucket of a second storage node of the storage system;
storing:
each of the first set of child segments to a log-structured merge (LSM) tree of the first storage node by following a child-segment: parent-segment pair format,
the second set of child segments to a buffer that is mapped to the second storage node;
sending, once the buffer is filled, the second set of child segments to the second storage node;
receiving a third set of child segments that maps to the portion of the buckets from the second storage node;
storing the third set of child segments to the LSM tree by following the format;
comparing the first set of child segments and the third set of child segments of the LSM tree against second child segments of a key-value store (KVS) listed for an L0 of the segment tree;
making, based on the comparing, a determination that a mismatch occurred, wherein, because a fourth set of child segments of the LSM tree could not be found in the KVS, the mismatch occurred; and
logging, based on the determination, the fourth set of child segments as missing segments.
2 . The method of claim 1 , further comprising:
after logging the fourth set of child segments as the missing segments:
identifying, based on the format, parent segments in the segment tree that reference the missing segments;
logging the parent segments to the LSM tree as the parent segments that track the missing segments;
identifying, by moving one level up in the segment tree and based on the parent segments, a grandparent segment of the missing segments;
making, based on identifying the grandparent segment, a second determination that the grandparent segment is a highest-level segment in the segment tree,
wherein the grandparent segment is a Level 6 (L6) segment in the segment tree;
identifying, based on the grandparent segment, a list of files impacted by the missing segments; and
initiating, using a graphical user interface (GUI), display of the list of files to a user.
3 . The method of claim 1 ,
wherein the storage system is a distributed dedupe storage system,
wherein a file system of the distributed dedupe storage system uses a segregated architecture to store metadata of files to the KVS and to store the data of the files to a plurality of storage nodes of the distributed dedupe storage system, and
wherein the plurality of storage nodes comprises the first storage node and the second storage node.
4 . The method of claim 3 ,
wherein the files are stored as the segment tree,
wherein segments of the data are assigned as the L0 segments in the segment tree,
wherein the L0 segments are the lowest level segments in the segment tree,
wherein remaining segments of the segment tree are assigned as metadata segments,
wherein the files are associated with the metadata segments and the L0 segments.
5 . The method of claim 4 ,
wherein, when two or more L0 segments are accumulated, a Level 1 (L1) segment is generated in the segment tree,
wherein the L1 segment is a metadata segment and the L1 segment comprises cryptographic hash values of the L0 segments,
wherein the distributed dedupe storage system supports generation of the metadata segments up to a Level 6 (L6) segment, and
wherein each file of the data is represented with the L6 segment and corresponding lower level segments in the segment tree depending on a size of each file.
6 . The method of claim 5 ,
wherein the metadata segments of the segment tree comprise segments from an L6 of the segment tree to an L1 of the segment tree,
wherein the metadata segments of the segment tree are stored to the KVS, and
wherein a key in the KVS represents a parent segment and a value associated with the key represents a plurality of child segments hosted by the parent segment.
7 . The method of claim 1 , wherein the L0 segments are data segments of the segment tree.
8 . The method of claim 7 ,
wherein the L0 segments are partitioned using at least N bits of cryptographic hash values of the L0 segments to generate the buckets.
9 . A non-transitory computer readable medium comprising computer readable program code, which when executed by a computer processor enables the computer processor to perform a method for managing data in a storage system, the method comprising:
partitioning Level 0 (L0) segments of a segment tree to generate buckets;
assigning a portion of the buckets to a first storage node of the storage system;
collecting a partition of the L0 segments assigned to the first storage node as child segments;
identifying:
a first set of child segments of the child segments that maps to the portion of the buckets of the first storage node, and
a second set of child segments of the child segments that maps to a bucket of a second storage node of the storage system;
storing:
each of the first set of child segments to a log-structured merge (LSM) tree of the first storage node by following a child-segment: parent-segment pair format,
the second set of child segments to a buffer that is mapped to the second storage node;
sending, once the buffer is filled, the second set of child segments to the second storage node;
receiving a third set of child segments that maps to the portion of the buckets from the second storage node;
storing the third set of child segments to the LSM tree by following the format;
comparing the first set of child segments and the third set of child segments of the LSM tree against second child segments of a key-value store (KVS) listed for an L0 of the segment tree;
making, based on the comparing, a determination that a mismatch occurred,
wherein, because a fourth set of child segments of the LSM tree could not be found in the KVS, the mismatch occurred; and
logging, based on the determination, the fourth set of child segments as missing segments.
10 . The non-transitory computer readable medium of claim 9 , further comprising:
after logging the fourth set of child segments as the missing segments:
identifying, based on the format, parent segments in the segment tree that references the missing segments;
logging the parent segments to the LSM tree as the parent segments that track the missing segments;
identifying, by moving one level up in the segment tree and based on the parent segments, a grandparent segment of the missing segments;
making, based on identifying the grandparent segment, a second determination that the grandparent segment is a highest-level segment in the segment tree,
wherein the grandparent segment is a Level 6 (L6) segment in the segment tree;
identifying, based on the grandparent segment, a list of files impacted by the missing segments; and
initiating, using a graphical user interface (GUI), display of the list of files to a user.
11 . The non-transitory computer readable medium of claim 9 ,
wherein the storage system is a distributed dedupe storage system,
wherein a file system of the distributed dedupe storage system uses a segregated architecture to store metadata of files to the KVS and to store the data of the files to a plurality of storage nodes of the distributed dedupe storage system, and
wherein the plurality of storage nodes comprises the first storage node and the second storage node.
12 . The non-transitory computer readable medium of claim 11 ,
wherein the files are stored as the segment tree,
wherein segments of the data are assigned as the L0 segments in the segment tree,
wherein the L0 segments are the lowest level segments in the segment tree, and
wherein remaining segments of the segment tree are assigned as metadata segments.
13 . The non-transitory computer readable medium of claim 12 ,
wherein, when two or more L0 segments are accumulated, a Level 1 (L1) segment is generated in the segment tree,
wherein the L1 segment is a metadata segment and the L1 segment comprises cryptographic hash values of the L0 segments,
wherein the distributed dedupe storage system supports generation of the metadata segments up to a Level 6 (L6) segment, and
wherein each file of the data is represented with the L6 segment and corresponding lower level segments in the segment tree depending on a size of each file.
14 . The non-transitory computer readable medium of claim 13 ,
wherein the metadata segments of the segment tree comprise segments from an L6 of the segment tree to an L1 of the segment tree,
wherein the metadata segments of the segment tree are stored to the KVS, and
wherein a key in the KVS represents a parent segment and a value associated with the key represents a plurality of child segments hosted by the parent segment.
15 . The non-transitory computer readable medium of claim 9 , wherein the L0 segments are data segments of the segment tree.
16 . The non-transitory computer readable medium of claim 15 ,
wherein the L0 segments are partitioned using at least N bits of cryptographic hash values of the L0 segments to generate the buckets.
17 . A system for managing data in a storage system, the system comprising:
a processor comprising circuitry;
memory comprising instructions, which when executed by the processor perform a method, the method comprising:
partitioning Level 0 (L0) segments of a segment tree to generate buckets;
assigning a portion of the buckets to a first storage node of the storage system;
collecting a partition of the L0 segments assigned to the first storage node as child segments;
identifying:
a first set of child segments of the child segments that maps to the portion of the buckets of the first storage node, and
a second set of child segments of the child segments that maps to a bucket of a second storage node of the storage system;
storing:
each of the first set of child segments to a log-structured merge (LSM) tree of the first storage node by following a child-segment:parent-segment pair format,
the second set of child segments to a buffer that is mapped to the second storage node;
sending, once the buffer is filled, the second set of child segments to the second storage node;
receiving a third set of child segments that maps to the portion of the buckets from the second storage node;
storing the third set of child segments to the LSM tree by following the format;
comparing the first set of child segments and the third set of child segments of the LSM tree against second child segments of a key-value store (KVS) listed for an L0 of the segment tree;
making, based on the comparing, a determination that a mismatch occurred,
wherein, because a fourth set of child segments of the LSM tree could not be found in the KVS, the mismatch occurred; and
logging, based on the determination, the fourth set of child segments as missing segments.
18 . The system of claim 17 , further comprising:
after logging the fourth set of child segments as the missing segments:
identifying, based on the format, parent segments in the segment tree that references the missing segments;
logging the parent segments to the LSM tree as the parent segments that track the missing segments;
identifying, by moving one level up in the segment tree and based on the parent segments, a grandparent segment of the missing segments;
making, based on identifying the grandparent segment, a second determination that the grandparent segment is a highest-level segment in the segment tree,
wherein the grandparent segment is a Level 6 (L6) segment in the segment tree;
identifying, based on the grandparent segment, a list of files impacted by the missing segments; and
initiating, using a graphical user interface (GUI), display of the list of files to a user.
19 . The system of claim 17 ,
wherein the storage system is a distributed dedupe storage system,
wherein a file system of the distributed dedupe storage system uses a segregated architecture to store metadata of files to the KVS and to store the data of the files to a plurality of storage nodes of the distributed dedupe storage system, and
wherein the plurality of storage nodes comprises the first storage node and the second storage node.
20 . The system of claim 19 ,
wherein the files are stored as the segment tree,
wherein segments of the data are assigned as the L0 segments in the segment tree,
wherein the L0 segments are the lowest level segments in the segment tree, and
wherein remaining segments of the segment tree are assigned as metadata segments.