Data fingerprint distribution on a data storage system
Fingerprints of data portions are distributed in a balanced manner across active controllers of a data storage system, and may be done so in such a manner that, when a new active controller is added to the system, fingerprint ownership and movement between pre-existing active controllers, and active controllers overall, is minimized When a new active controller is added to the system and fingerprints are redistributed, no fingerprint ownership may be re-assigned between pre-existing active controllers and no fingerprints may be moved between pre-existing active controllers, for example, between local memories of the active controller.
1. For a data storage system in which fingerprints are determined for data portions of a predetermined size, the data storage system including one or more of a potential number of active storage controllers, a method comprising:
grouping potential fingerprints into a plurality of fingerprint groups;
for each of the plurality of fingerprint groups, for each of the potential number of active storage controllers in the data storage system, determining a storage controller that owns the fingerprint group;
determining a number of active storage controllers; and
for at least each fingerprint determined for a data portion stored in the data storage system, storing the fingerprint in a fingerprint table of fingerprints in a local memory of a storage controller determined to own, for the determined number of active controllers, the fingerprint group to which the fingerprint belongs.
2. The method according to claim 1 , further comprising
populating a second table including a plurality of entries, each entry corresponding to one or more fingerprint groups and specifying, for each of the potential number of active storage controllers, the storage controller determined to own the fingerprint group.
3. The method according to claim 2 , wherein the plurality of entries of the second table do not change in response to adding another active storage controller of the potential number of active storage controllers to the data storage system.
4. The method according to claim 2 , further comprising:
receiving a first data portion;
determining a first fingerprint of the data portion;
determining, using the second table, a first active storage controller of the plurality of storage controllers that owns the first fingerprint; and
using a first fingerprint table in the local memory of the first active storage controller to perform deduplication processing of the first data portion.
5. The method according to claim 1 , further comprising:
in response to adding an active storage controller of the potential number of active storage controllers to the data storage system, moving one or more of the at least each fingerprint determined for a data portion from the first table to a second table of fingerprints in a local memory of the added storage controller determined to own the one or more fingerprints,
wherein no fingerprints are moved between any storage controllers that already were active prior to the adding of the active storage controller.
6. The method according to claim 1 , further comprising:
in response to adding an active storage controller of the potential number of active storage controllers to the data storage system, moving one or more of the at least each fingerprint determined for a data portion from the first table to a second table of fingerprints in a local memory of the added storage controller determined to own the one or more fingerprints,
wherein a maximum percentage of fingerprints that are moved between any active storage controllers as a result of the adding of the active storage controller is: 100/x, wherein x is a number of active storage controllers on the data storage system after the adding of the active controller.
7. The method according to claim 1 , further comprising:
determining a quantity of fingerprint groups to be a lowest common multiple of each potential number of active storage controllers or a multiple thereof.
8. The method according to claim 1 , wherein the fingerprints are generated for the data portions using a hash function that produces a random distribution of fingerprint values in a space of possible fingerprint values.
9. The method according to claim 1 , wherein fingerprints are generated using SHA-2.
10. A data storage system in which fingerprints are determined for data portions of a predetermined size, the data storage system comprising:
one or more of a potential number of active storage controllers;
one or more processors; and
a memory comprising code stored thereon that, when executed, performs a method comprising:
grouping potential fingerprints into a plurality of fingerprint groups;
for each of the plurality of fingerprint groups, for each of the potential number of active storage controllers in the data storage system, determining a storage controller that owns the fingerprint group;
determining a number of active storage controllers; and
for at least each fingerprint determined for a data portion stored in the data storage system, storing the fingerprint in a fingerprint table of fingerprints in a local memory of a storage controller determined to own, for the determined number of active controllers, the fingerprint group to which the fingerprint belongs.
11. The system according to claim 10 , the method further comprising
populating a second table including a plurality of entries, each entry corresponding to one or more fingerprint groups and specifying, for each of the potential number of active storage controllers, the storage controller determined to own the fingerprint group.
12. The system according to claim 11 , wherein the plurality of entries of the second table do not change in response to adding another active storage controller of the potential number of active storage controllers to the data storage system.
13. The system according to claim 11 , the method further comprising:
receiving a first data portion;
determining a first fingerprint of the data portion;
determining, using the second table, a first active storage controller of the plurality of storage controllers that owns the first fingerprint; and
using a first fingerprint table in the local memory of the first active storage controller to perform deduplication processing of the first data portion.
14. The system according to claim 10 , the method further comprising:
in response to adding an active storage controller of the potential number of active storage controllers to the data storage system, moving one or more of the at least each fingerprint determined for a data portion from the first table to a second table of fingerprints in a local memory of the added storage controller determined to own the one or more fingerprints,
wherein no fingerprints are moved between any storage controllers that already were active prior to the adding of the active storage controller.
15. The system according to claim 10 , the method further comprising:
in response to adding an active storage controller of the potential number of active storage controllers to the data storage system, moving one or more of the at least each fingerprint determined for a data portion from the first table to a second table of fingerprints in a local memory of the added storage controller determined to own the one or more fingerprints,
wherein a maximum percentage of fingerprints that are moved between any active storage controllers as a result of the adding of the active storage controller is: 100/x, wherein x is a number of active storage controllers on the data storage system after the adding of the active controller.
16. A non-transitory computer-readable medium having software stored thereon for a data storage system in which fingerprints are determined for data portions of a predetermined size, the data storage system including one or more of a potential number of active storage controllers, the software comprising:
executable code that groups potential fingerprints into a plurality of fingerprint groups;
executable code that, for each of the plurality of fingerprint groups, for each of the potential number of active storage controllers in the data storage system, determines a storage controller that owns the fingerprint group;
executable code that determines a number of active storage controllers; and
executable code that, for at least each fingerprint determined for a data portion stored in the data storage system, stores the fingerprint in a fingerprint table of fingerprints in a local memory of a storage controller determined to own, for the determined number of active controllers, the fingerprint group to which the fingerprint belongs.
17. The non-transitory computer-readable medium according to claim 16 , the software further comprising
executable code that populates a second table including a plurality of entries, each entry corresponding to one or more fingerprint groups and specifying, for each of the potential number of active storage controllers, the storage controller determined to own the fingerprint group.
18. The non-transitory computer-readable medium according to claim 17 , the software further comprising:
executable code that receives a first data portion;
executable code that determines a first fingerprint of the data portion;
executable code that determines, using the second table, a first active storage controller of the plurality of storage controllers that owns the first fingerprint; and
executable code that uses a first fingerprint table in the local memory of the first active storage controller to perform deduplication processing of the first data portion.
19. The non-transitory computer-readable medium according to claim 16 , the software further comprising:
executable code that, in response to adding an active storage controller of the potential number of active storage controllers to the data storage system, moves one or more of the at least each fingerprint determined for a data portion from the first table to a second table of fingerprints in a local memory of the added storage controller determined to own the one or more fingerprints,
wherein no fingerprints are moved between any storage controllers that already were active prior to the adding of the active storage controller.
20. The non-transitory computer-readable medium according to claim 16 , the software further comprising:
executable code that, in response to adding an active storage controller of the potential number of active storage controllers to the data storage system, moves one or more of the at least each fingerprint determined for a data portion from the first table to a second table of fingerprints in a local memory of the added storage controller determined to own the one or more fingerprints,
wherein a maximum percentage of fingerprints that are moved between any active storage controllers as a result of the adding of the active storage controller is: 100/x, wherein x is a number of active storage controllers on the data storage system after the adding of the active controller.