Post-processing global deduplication algorithm for scaled-out deduplication file system
A method, apparatus, and system for redistributing files in a multi-node storage system to improve global deduplication storage savings is disclosed. A plurality of file cluster candidates are generated for a plurality of files stored at a multi-node storage system comprising a plurality of data nodes. A similarity index is determined for each of the plurality of file cluster candidates based on similarity of the files comprised in the file cluster candidate. A ranked recipe list comprising a plurality of recipes is generated. Each recipe is associated with one of the plurality of file cluster candidates, comprises a destination data node for the associated file cluster candidate, and is associated with a deduplication space savings. At least some of the plurality of files are moved between the plurality of data nodes based on the recipes in the ranked recipe list to improve deduplication space savings in the multi-node storage system.
1. A computer-implemented method, comprising:
generating a plurality of file cluster candidates for a plurality of files stored at a multi-node storage system comprising a plurality of data nodes, each of the plurality of file cluster candidates comprising some of the plurality of files;
determining, for each of the plurality of file cluster candidates, a similarity index based on similarity of the files comprised in the file cluster candidate;
generating a ranked recipe list comprising a plurality of recipes, wherein each recipe is associated with one of the plurality of file cluster candidates, and each recipe comprises a destination data node for the associated file cluster candidate, and is associated with a deduplication space savings determined based on a total file size and the similarity index of the associated file cluster candidate, a tag to node mapping table comprising a mapping between a tag and each of the plurality of data nodes;
ranking the plurality of recipes in the ranked recipe list according to a data movement cost adjusted deduplication space savings associated with each recipe that is determined based on the deduplication space savings associated with a respective recipe and an amount of data or a quantity of files that is to be moved for the respective recipe, wherein a ranking of each recipe in the ranked recipe list increases with an increase in the deduplication space savings, or a decrease in the amount of data or the quantity of files; and the ranking of each recipe decreases with a decrease in the deduplication space savings, or an increase in the amount of data or the quantity of files; and
moving at least some of the plurality of files between the plurality of data nodes based on performing the recipes in the ranked recipe list according to the ranking, to improve deduplication space savings in the multi-node storage system, including determining an incompatibility between a first recipe in the ranked recipe list and a second recipe in the ranked recipe list, the incompatibility being determined in response to each of the first recipe and the second recipe being associated with a respective file cluster candidate that comprise at least one same file, and ignoring the first recipe in response to the second recipe being ranked higher than the first recipe in the ranked recipe list.
2. The method of claim 1 , wherein each of the plurality of files is associated with the tag indicative of a source of the file, and wherein each file cluster candidate comprises all files associated with one or more tags.
3. The method of claim 1 , wherein the similarity index comprises a Jaccard index.
4. The method of claim 1 , wherein determining the data movement cost-adjusted deduplication space savings associated with each recipe comprises dividing the deduplication space savings associated with the recipe by the quantity of files that need to be moved.
5. The method of claim 1 , wherein determining the data movement cost-adjusted deduplication space savings associated with each recipe comprises dividing the deduplication space savings associated with the recipe by the amount of data that need to be moved.
6. The method of claim 1 , wherein the first recipe in the ranked recipe list is further invalidated or removed from the ranked recipe list in response to determining the incompatibility between the first recipe and the second recipe and in response to determining that the second recipe is ranked higher than the first recipe.
7. The method of claim 1 , wherein each of the plurality of data nodes is associated with a storage size limit, and wherein a third recipe in the ranked recipe list is ignored, invalidated, or removed when moving all files in the file cluster candidate associated with the third recipe to the destination node of the third recipe would cause a violation of the storage size limit of the destination node.
8. The method of claim 1 , wherein the generating of the plurality of file cluster candidates, the determining of the similarity indexes, and the generating of the ranked recipe list are performed within a self-contained environment separate from an operating system of the multi-mode storage system.
9. The method of claim 8 , wherein the ranked recipe list is stored at a shared database, and wherein the operating system of the multi-node storage system polls the shared database to read the ranked recipe list prior to the moving of at least some of the plurality of files.
10. The method of claim 1 , wherein one or more of the plurality of file cluster candidates whose similarity indexes are below a threshold are discarded, and are not included in the ranked recipe list.
11. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations, the operations comprising:
generating a plurality of file cluster candidates for a plurality of files stored at a multi-node storage system comprising a plurality of data nodes, each of the plurality of file cluster candidates comprising some of the plurality of files;
determining, for each of the plurality of file cluster candidates, a similarity index based on similarity of the files comprised in the file cluster candidate;
generating a ranked recipe list comprising a plurality of recipes, wherein each recipe is associated with one of the plurality of file cluster candidates, and each recipe comprises a destination data node for the associated file cluster candidate, and is associated with a deduplication space savings determined based on a total file size and the similarity index of the associated file cluster candidate, a tag to node mapping table comprising a mapping between a tag and each of the plurality of data nodes;
ranking the plurality of recipes in the ranked recipe list according to a data movement cost adjusted deduplication space savings associated with each recipe that is determined based on the deduplication space savings associated with a respective recipe and an amount of data or a quantity of files that is to be moved for the respective recipe, wherein a ranking of each recipe in the ranked recipe list increases with an increase in the deduplication space savings, or a decrease in the amount of data or the quantity of files; and the ranking of each recipe decreases with a decrease in the deduplication space savings, or an increase in the amount of data or the quantity of files; and
moving at least some of the plurality of files between the plurality of data nodes based on performing the recipes in the ranked recipe list according to the ranking, to improve deduplication space savings in the multi-node storage system, including determining an incompatibility between a first recipe in the ranked recipe list and a second recipe in the ranked recipe list, the incompatibility being determined in response to each of the first recipe and the second recipe being associated with a respective file cluster candidate that comprise at least one same file, and ignoring the first recipe in response to the second recipe being ranked higher than the first recipe in the ranked recipe list.
12. The non-transitory machine-readable medium of claim 11 , wherein each of the plurality of files is associated with the tag indicative of a source of the file, and wherein each file cluster candidate comprises all files associated with one or more tags.
13. The non-transitory machine-readable medium of claim 11 , wherein the similarity index comprises a Jaccard index.
14. The non-transitory machine-readable medium of claim 11 , wherein determining the data movement cost-adjusted deduplication space savings associated with each recipe comprises dividing the deduplication space savings associated with the recipe by the quantity of files that need to be moved.
15. The non-transitory machine-readable medium of claim 11 , wherein determining the data movement cost-adjusted deduplication space savings associated with each recipe comprises dividing the deduplication space savings associated with the recipe by the amount of data that need to be moved.
16. The non-transitory machine-readable medium of claim 11 , wherein the first recipe in the ranked recipe list is further invalidated or removed from the ranked recipe list in response to determining the incompatibility between the first recipe and the second recipe and in response to determining that the second recipe is ranked higher than the first recipe.
17. The non-transitory machine-readable medium of claim 11 , wherein each of the plurality of data nodes is associated with a storage size limit, and wherein a third recipe in the ranked recipe list is ignored, invalidated, or removed when moving all files in the file cluster candidate associated with the third recipe to the destination node of the third recipe would cause a violation of the storage size limit of the destination node.
18. The non-transitory machine-readable medium of claim 11 , wherein the generating of the plurality of file cluster candidates, the determining of the similarity indexes, and the generating of the ranked recipe list are performed within a self-contained environment separate from an operating system of the multi-mode storage system.
19. The non-transitory machine-readable medium of claim 18 , wherein the ranked recipe list is stored at a shared database, and wherein the operating system of the multi-node storage system polls the shared database to read the ranked recipe list prior to the moving of at least some of the plurality of files.
20. A data processing system, comprising:
a processor; and
a memory coupled to the processor to store instructions, which when executed by the processor, cause the processor to perform operations, the operations including generating a plurality of file cluster candidates for a plurality of files stored at a multi-node storage system comprising a plurality of data nodes, each of the plurality of file cluster candidates comprising some of the plurality of files;
determining, for each of the plurality of file cluster candidates, a similarity index based on similarity of the files comprised in the file cluster candidate;
generating a ranked recipe list comprising a plurality of recipes, wherein each recipe is associated with one of the plurality of file cluster candidates, and each recipe comprises a destination data node for the associated file cluster candidate, and is associated with a deduplication space savings determined based on a total file size and the similarity index of the associated file cluster candidate, a tag to node mapping table comprising a mapping between a tag and each of the plurality of data nodes;
ranking the plurality of recipes in the ranked recipe list according to a data movement cost adjusted deduplication space savings associated with each recipe that is determined based on the deduplication space savings associated with a respective recipe and an amount of data or a quantity of files that is to be moved for the respective recipe, wherein a ranking of each recipe in the ranked recipe list increases with an increase in the deduplication space savings, or a decrease in the amount of data or the quantity of files; and the ranking of each recipe decreases with a decrease in the deduplication space savings, or an increase in the amount of data or the quantity of files; and
moving at least some of the plurality of files between the plurality of data nodes based on performing the recipes in the ranked recipe list according to the ranking, to improve deduplication space savings in the multi-node storage system, including determining an incompatibility between a first recipe in the ranked recipe list and a second recipe in the ranked recipe list, the incompatibility being determined in response to each of the first recipe and the second recipe being associated with a respective file cluster candidate that comprise at least one same file, and ignoring the first recipe in response to the second recipe being ranked higher than the first recipe in the ranked recipe list.