Deduplication-aware load balancing in distributed storage systems

Patent metadata

Field	Value
Publication number	US-11461027-B2
Application number	US-201715653249-A
Country	US
Kind code	B2
Filing date	Jul 18, 2017
Priority date	Jul 18, 2017
Publication date	Oct 4, 2022
Grant date	Oct 4, 2022

Abstract

Techniques for enabling deduplication-aware load balancing in a distributed storage system are provided. In one set of embodiments, a node of the distributed storage system can receive an I/O (Input/Output) request pertaining to a data block of a storage object stored on a local storage component of the node. The node can further determine whether the I/O request requires insertion of a new entry into a deduplication hash table associated with the local storage component or deletion of an existing entry from the deduplication hash table. If the I/O request requires insertion of a new hash table entry, the node can add an identifier of the data block into a probabilistic data structure associated with the local storage component, where the probabilistic data structure is configured to maintain information regarding distinct data blocks that are likely present in the local storage component. Alternatively, if the I/O request requires deletion of an existing hash table entry, the node can remove the identifier of the data block from the probabilistic data structure.

First claim

What is claimed is:

1. A method for enabling deduplication-aware load balancing in a distributed storage system comprising a plurality of nodes, the method comprising, for a storage object stored on a local storage component of a first node in the plurality of nodes:
transmitting, by a user-level background process running on the first node, a message to each other node in the plurality of nodes requesting a count of a total number of deduplicated data blocks of the storage object that are stored on a local storage component of said each other node, the message including identifiers for the deduplicated data blocks of the storage object;
receiving, by the user-level background process, the counts of deduplicated data blocks from the other nodes;
determining, by the user-level background process, a second node in the plurality of nodes that returned the highest count of deduplicated data blocks for the storage object;
updating, by the user-level background process, a data structure maintained on the first node with an entry that includes an identifier of the storage object and an identifier of the second node; and
at a time of performing a load balancing operation with respect to the storage object:
retrieving the entry from the data structure;
determining whether the second node identified in the entry is available; and
if the second node is available, moving the storage object from the first node to the second node.

2. The method of claim 1 wherein, upon, receiving the message, said each other node queries a probabilistic data structure local to the node using the identifiers in order to generate the count.

3. The method of claim 1 wherein the user-level background process performs the transmitting in response to being invoked by a deduplication scanner task that periodically collects statistics regarding a plurality of storage objects stored on the local storage component.

4. The method of claim 1 wherein the entry added to the data structure identifies the second node as a preferred target node for receiving the storage object during the load balancing operation.

5. The method of claim 1 further comprising:
receiving, by the first node, an I/O (Input/Output) request pertaining to a first storage object stored on the local storage component of the first node; and
for each data block of the first storage object affected by the I/O request:
determining whether the I/O request requires insertion of a new entry into a deduplication hash table associated with the local storage component or deletion of an existing entry from the deduplication hash table;
if the I/O request requires insertion of the new entry, adding an identifier of the data block into a probabilistic data structure associated with the local storage component, the probabilistic data structure maintaining information regarding deduplicated data blocks that are likely present in the local storage component; and
if the I/O request requires deletion of the existing entry, removing, by the node, the identifier of the data block from the probabilistic data structure.

6. The method of claim 5 wherein the identifier of the data block comprises a predefined number of least significant bits of a fingerprint calculated from the data block's content.

7. The method of claim 5 wherein the probabilistic data structure is a bloom filter.

8. The method claim 5 further comprising:
receiving, by the first node, a request from a third node in the plurality of nodes for a count of deduplicated data blocks for the first storage object that are stored in the local storage component of the first node;
in response to the request from the third node, querying the probabilistic data structure to generate the count; and
upon generating the count, transmitting the count to the third node.

9. A non-transitory computer readable storage medium having stored thereon program code executable by a first node in a distributed storage system comprising a plurality of nodes, the program code embodying a method for enabling deduplication-aware load balancing in the distributed storage system, the method comprising, for a storage object stored on a local storage component of the first node:
transmitting, by a user-level background process running on the first node, a message to each other node in the plurality of nodes requesting a count of a total number of deduplicated data blocks of the storage object that are stored on a local storage component of said each other node, the message including identifiers for the deduplicated data blocks of the storage object;
receiving, by the user-level background process, the counts of deduplicated data blocks from the other nodes;
determining, by the user-level background process, a second node in the plurality of nodes that returned the highest count of deduplicated data blocks for the storage object;
updating, by the user-level background process, a data structure maintained on the first node with an entry that includes an identifier of the storage object and an identifier of the second node; and
at a time of performing a load balancing operation with respect to the storage object:
retrieving the entry from the data structure;
determining whether the second node identified in the entry is available; and
if the second node is available, moving the storage object from the first node to the second node.

10. The non-transitory computer readable storage medium of claim 9 wherein, upon, receiving the message, said each other node queries a probabilistic data structure local to the node using the identifiers in order to generate the count.

11. The non-transitory computer readable storage medium of claim 9 wherein the user-level background process performs the transmitting in response to being invoked by a deduplication scanner task that periodically collects statistics regarding a plurality of storage objects stored on the local storage component.

12. The non-transitory computer readable storage medium of claim 9 wherein the entry added to the data structure identifies the second node as a preferred target node for receiving the storage object during the load balancing operation.

13. The non-transitory computer readable storage medium of claim 9 wherein the method further comprises:
receiving, by the first node, an I/O (Input/Output) request pertaining to a first storage object stored on the local storage component of the first node; and
for each data block of the first storage object affected by the I/O request:
determining whether the I/O request requires insertion of a new entry into a deduplication hash table associated with the local storage component or deletion of an existing entry from the deduplication hash table;
if the I/O request requires insertion of the new entry, adding an identifier of the data block into a probabilistic data structure associated with the local storage component, the probabilistic data structure maintaining information regarding deduplicated data blocks that are likely present in the local storage component; and
if the I/O request requires deletion of the existing entry, removing, by the node, the identifier of the data block from the probabilistic data structure.

14. The non-transitory computer readable storage medium of claim 13 wherein the identifier of the data block comprises a predefined number of least significant bits of a fingerprint calculated from the data block's content.

15. The non-transitory computer readable medium of claim 13 wherein the probabilistic data structure is a bloom filter.

16. The non-transitory computer readable storage medium of

Assignees

• Vmware Inc

Inventors

• Gupta Abhishek
• Delgado Jorge Guerra
• Rangaswamy Sandeep
• Premachandran Srinath
• Renauld Pascal

Classifications

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F16/217

  Database tuning (G06F16/2282 takes precedence; database performance monitoring G06F11/3409) · CPC title

• G06F3/0608

  Saving storage space on storage systems · CPC title

• G06F3/0635

  by changing the path, e.g. traffic rerouting, path reconfiguration · CPC title

• G06F16/215 Primary

  Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors · CPC title