File system metadata deduplication
File metadata structures of a file system are analyzed. At least one metadata element that is duplicated among the analyzed file metadata structures is identified. The at least one identified metadata element is deduplicated including by modifying at least one of the file metadata structures to reference a same instance of the identified metadata element that is referenced by another one of the file metadata structures.
1 . A method, comprising:
analyzing file metadata structures of a file system, wherein each of the file metadata structures includes a plurality of metadata elements;
identifying a portion of the file metadata structures that is duplicated among the analyzed file metadata structures, wherein instances of the identified portion of the file metadata structures are associated with a common sequence of values, wherein the instances of the identified portion of the file metadata structures include a first instance that at least includes a first leaf node of a first file metadata structure of the file metadata structures and a second leaf node of the first file metadata structure, and a second instance that at least includes a first leaf node of a second file metadata structure of the file metadata structures and a second leaf node of the second file metadata structure; and
deduplicating the instances of the identified portion of the file metadata structures at least in part by updating a node of the second file metadata structure to include a reference to an intermediate node associated with the first instance of the identified portion of the file metadata structures and deleting at least part of a node of the identified portion of the file metadata structures, wherein the intermediate node associated with the first instance of the identified portion of the file metadata structures is a child node of a root node of the first instance of the identified portion of the file metadata structures and is a parent node to the first leaf node of the first instance of the identified portion of the file metadata structures.
2 . The method of claim 1 , wherein analyzing the file metadata structures of the file system comprises scanning a bottom level of the file metadata structures and a level above the bottom level of the file metadata structures.
3 . The method of claim 1 , wherein at least one of the first file metadata structure and the second file metadata structure corresponds to a file generated by a storage system.
4 . The method of claim 1 , wherein at least one of first file metadata structure and the second file metadata structure corresponds to a file backed up from a primary system to a storage system.
5 . The method of claim 1 , wherein identifying the portion of the file metadata structures that is duplicated among the analyzed file metadata structures further comprises identifying the first instance of the identified portion of the file metadata structures and the second instance of the identified portion of the file metadata structures from the file metadata structures of the file system.
6 . The method of claim 1 , wherein the plurality of metadata elements are configured to store a corresponding value, wherein at least the first leaf node of the first file metadata structure and the second leaf node of the first file metadata structure store a corresponding sequence of values that is the same as a corresponding sequence of values stored by the first leaf node of the second file metadata structure and the second leaf node of the second file metadata structure.
7 . The method of claim 1 , wherein deduplicating the instances of the identified portion of the file metadata structures includes determining that a first reference count of the node associated with the first instance of the identified portion is greater than a second reference count of a node associated with a second instance of the identified portion.
8 . The method of claim 7 , wherein the first reference count of a common node associated with the first instance of the identified portion indicates more metadata elements reference the node associated with the first instance of the identified portion than the node associated with the second instance of the identified portion.
9 . The method of claim 7 , wherein deduplicating the instances of the identified portion of the file metadata structures further includes deleting, responsive to the determination that the first reference count of the node associated with the first instance of the identified portion is greater than the second reference count of the node associated with the second instance of the identified portion, the node associated with the second instance of the identified portion.
10 . The method of claim 9 , wherein deduplicating the instances of the identified portion of the file metadata structures further includes deleting one or more nodes directly referenced by the node associated with the second instance of the identified portion.
11 . The method of claim 9 , wherein deduplicating the instances of the identified portion of the file metadata structures further includes deleting one or more nodes indirectly referenced by the node associated with the second instance of the identified portion.
12 . The method of claim 9 , wherein the node associated with the second instance of the identified portion is deleted from a solid state disk of a storage system.
13 . The method of claim 1 , wherein the instances of the identified portion of the file metadata structures are deduplicated as a background process of a storage system.
14 . The method of claim 13 , wherein the storage system is comprised of a plurality of storage nodes, wherein the metadata associated with a plurality of files is stored across the plurality of storage nodes.
15 . The method of claim 1 , wherein deduplicating the instances of the identified portion of the file metadata structures includes determining that a first reference count of the node associated with the first instance of the identified portion is the same as a second reference count of a node associated with a second instance of the identified portion.
16 . The method of claim 15 , wherein deduplicating the instances of the identified portion of the file metadata structures includes selecting, responsive to the determination that the first reference count of the node associated with the first instance of the identified portion is greater than the second reference count of the node associated with the second instance of the identified portion, to reference the node associated with the first instance of the identified portion of the file metadata structures.
17 . A computer program product, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions that configure a processor to:
analyze file metadata structures of a file system, wherein each of the file metadata structures includes a plurality of metadata elements;
identify a portion of the file metadata structures that is duplicated among the analyzed file metadata structures, wherein instances of the identified portion of the file metadata structures are associated with a common sequence of values, wherein the instances of the identified portion of the file metadata structures include a first instance that at least includes a first leaf node of a first file metadata structure of the file metadata structures and a second leaf node of the first file metadata structure, and a second instance that at least includes a first leaf node of a second file metadata structure of the file metadata structures and a second leaf node of the second file metadata structure; and
deduplicate the instances of the identified portion of the file metadata structures at least in part by updating a node of the second file metadata structure to include a reference to an intermediate node associated with the first instance of the identified portion of the file metadata structures and deleting at least part of a node of the identified portion of the file metadata structures, wherein the intermediate node associated with the first instance of the identified portion of the file metadata structures is a child node of a root node of the first instance of the identified portion of the file metadata structures and is a parent node to the first leaf node of the first instance of the identified portion of the file metadata structures.
18 . The computer program product of claim 17 , wherein to analyze the file metadata structures of the file system the computer instructions configure the processor to scan a bottom level of the file metadata structures and a level above the bottom level of the file metadata structures.
19 . The computer program product of claim 17 , wherein the plurality of metadata elements are configured to store a corresponding value, wherein at least the first leaf node of the first file metadata structure and the second leaf node of the first file metadata structure store a corresponding sequence of values that is the same as a corresponding sequence of values stored by the first leaf node of the second file metadata structure and the second leaf node of the second file metadata structure.
20 . A system, comprising:
a processor coupled to a memory, the memory storing instructions to configure the processor to:
analyze file metadata structures of a file system, wherein each of the file metadata structures includes a plurality of metadata elements;
identify a portion of the file metadata structures that is duplicated among the analyzed file metadata structures, wherein instances of the identified portion of the file metadata structures are associated with a common sequence of values, wherein the instances of the identified portion of the file metadata structures include a first instance that at least includes a first leaf node of a first file metadata structure of the file metadata structures and a second leaf node of the first file metadata structure, and a second instance that at least includes a first leaf node of a second file metadata structure of the file metadata structures and a second leaf node of the second file metadata structure; and
deduplicate the instances of the identified portion of the file metadata structures at least in part by updating a node of the second file metadata structure to include a reference to an intermediate node associated with the first instance of the identified portion of the file metadata structures and deleting at least part of a node of the identified portion of the file metadata structures, wherein the intermediate node associated with the first instance of the identified portion of the file metadata structures is a child node of a root node of the first instance of the identified portion of the file metadata structures and is a parent node to the first leaf node of the first instance of the identified portion of the file metadata structures.