Performing deduplication in a distributed filesystem

• US 9,679,040 B1
• Filed: 02/15/2013
• Issued: 06/13/2017
• Est. Priority Date: 05/03/2010
• Status: Active Grant

• Current Assignee: Panzura, Inc.
• Original Assignee: Panzura, Inc.
• Inventors: Taylor, John Richard, Davis, Andrew P., Chou, Randy Yen-pang
• Primary Examiner(s): Rahman, Sm
• Application Number:
  US13/769,200
• Time in Patent Office: 1,579 Days
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/2089 Redundant storage control functionality
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 11/3006 where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems multiprogramming arrangements G06F9/46; allocation of resources G06F9/50
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: G06F 16/1827 Management specifically adapted to NAS management of storage area networks [SAN] G06F3/067
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: G06F 2201/85 Active fault masking without idle spares active fault masking without idle spare hardware where processing functionality is redundant G06F11/2035

Abstract

The disclosed embodiments provide techniques for performing deduplication for a distributed filesystem. Two or more cloud controllers collectively manage distributed filesystem data that is stored in one or more cloud storage systems; the cloud controllers cache and ensure data consistency for the stored data. During operation, a cloud controller receives an incremental metadata snapshot that references new data that was added to the distributed filesystem by a remote cloud controller. The cloud controller extracts a set of deduplication information from this incremental metadata snapshot. Upon receiving a subsequent client write request (e.g., a file write that includes one or more data blocks), the cloud controller uses the extracted deduplication information to determine that one or more data blocks in the client write request have already been written to the distributed filesystem.

Claims

1. A computer-implemented method for performing distributed deduplication in a distributed filesystem, the method comprising:

collectively managing the data of the distributed filesystem using two or more cloud controllers, wherein collectively managing the data comprises;

storing the data for the distributed filesystem in one or more cloud storage systems, wherein the cloud controllers cache and ensure data consistency for data stored in the cloud storage systems; and

maintaining in each cloud controller a metadata hierarchy that reflects the current state of the distributed filesystem, wherein changes to the metadata for the distributed filesystem are synchronized across the cloud controllers, wherein synchronizing metadata includes synchronizing deduplication information across the cloud controllers, wherein each cloud controller maintains a deduplication table that tracks deduplicated data for the distributed filesystem; and

receiving at a cloud controller an incremental metadata snapshot from a remote cloud controller, wherein the incremental metadata snapshot comprises deduplication information for a file that was received by the remote cloud controller, wherein the cloud controller, the remote cloud controller and the cloud storage system are all distinct computing devices;

adding the deduplication information from the incremental metadata snapshot to the deduplication table on the cloud controller;

receiving at the cloud controller a client write request that comprises new file data;

using the deduplication table on the cloud controller to determine that one or more data blocks in the new file data have previously been written to the distributed filesystem by the remote cloud controller;

updating the metadata hierarchy and the deduplication table for the cloud controller to link the metadata for these duplicate new data blocks with the location of the deduplicated data blocks in the cloud storage system and cache of the cloud controller; and

distributing a subsequent incremental metadata update from the cloud controller to the other cloud controllers for the distributed filesystem that notifies the other cloud controllers of the new file data and includes deduplication updates related to the new file data that enable the other cloud controllers to update the reference counts and entries in their own respective deduplication tables to reflect the addition of the new file data to the distributed filesystem.

2. The computer-implemented method of claim 1, wherein the method further comprises:

adding the deduplication information to the deduplication table stored in the cloud controller;

calculating a hash value for a data block in the client write request;

accessing the deduplication table using the hash value to determine that the data block was previously written to the distributed filesystem; and

accessing a block entry in the hash table that is associated with the previously written data block to determine a storage address for the previously written data block.

3. The computer-implemented method of claim 2, wherein the method further comprises:

collectively presenting a unified namespace for the distributed filesystem to the clients of the distributed filesystem via the two or more cloud controllers, wherein the clients can only access the distributed filesystem via the cloud controllers, wherein the file data for the distributed filesystem is stored in the cloud storage system, wherein each cloud controller caches a subset of the file data from the remote cloud storage system that is being actively accessed by that cloud controller'"'"'s respective clients, wherein new file data received by each cloud controller from its clients is written to the remote cloud storage system via the receiving cloud controller;

maintaining at each cloud controller a copy of the metadata for the files stored in the distributed filesystem, wherein each cloud controller communicates any changes to the metadata for the distributed filesystem to the full set of cloud controllers for the distributed filesystem to ensure that the clients of the distributed filesystem share a consistent view of each file in the distributed filesystem; and

writing new metadata for the distributed filesystem to reflect filesystem changes associated with the client write request, wherein a new metadata entry for the data block references the storage address for the previously written data block, wherein the new metadata entry comprises additional deduplication information associated with the data block from the client write request received by the cloud controller, wherein the additional deduplication information comprises references to and reference counts for one or more deduplicated data blocks in the client write request.

4. The computer-implemented method of claim 2,

wherein the incremental metadata snapshot comprises metadata for two or more data blocks;

wherein the deduplication table comprises multiple temporal deduplication structures that group the lookup information for deduplicated data blocks from a contiguous source contiguously into the same temporal deduplication structure to improve locality in subsequent contiguous lookups;

wherein adding the deduplication information to the deduplication table further comprises;

determining hash values for the two or more data blocks from the metadata of the incremental metadata snapshot;

determining that the hash values for the two or more data blocks are not currently included in the deduplication table; and

writing new block entries for each of the two or more data blocks into a temporal deduplication structure in the deduplication table;

wherein the new block entries for the two or more data blocks are written contiguously into the same temporal deduplication structure;

wherein the multiple hash entries for the two or more data blocks link to the same temporal deduplication structure; and

wherein grouping hash values that are spatially- and temporally-related into common temporal deduplication structures facilitates reducing disk accesses when subsequently looking up spatially- and temporally-related data blocks using the deduplication table.

5. The computer-implemented method of claim 4,

wherein each block entry in the temporal deduplication structure includes a pointer to the next block entry that was written in the temporal deduplication structure;

and

wherein using pointers to link block entries in the temporal deduplication structure facilitates reducing the number of disk reads required to look up related block entries in the temporal deduplication structure during a subsequent deduplication operation.

6. The computer-implemented method of claim 4,

wherein the cloud controller simultaneously receives updated deduplication information from two distinct sources, wherein a first source is the incremental metadata update and a second source comprises multiple new data blocks to be added to the deduplication table from the client write request;

and

wherein the method further comprises performing a sort operation that ensures that deduplication entries for the first source and the second source of deduplication are written as two separate, contiguous blocks, and that deduplication entries for the first source and the second source are not interleaved in the temporal deduplication structure.

7. The computer-implemented method of claim 6,

wherein performing the sort operation comprises reordering the order in which block entries are written to ensure that block entries are temporally grouped in the temporal deduplication structure based on the source of their associated data blocks;

and

wherein grouping block entries temporally based on the source of their associated data blocks facilitates reducing the number of disk reads during subsequent deduplication operations when duplicate data is written in a write order that matches the write order of the grouped block entries.

8. The computer-implemented method of claim 7,

wherein a given data block in the distributed filesystem is associated with a cloud virtual address and an offset;

wherein the cloud virtual address specifies a cloud file containing the given data block and the offset specifies the location of the given data block in the cloud file;

wherein the cloud virtual address identifies a source cloud controller for the given data block; and

wherein the sort operation comprises ordering the write of block entries into the temporal deduplication structure based on the cloud virtual addresses and the offsets of the block entries'"'"' associated data blocks.

9. The computer-implemented method of claim 2,

wherein the incremental metadata snapshot comprises metadata for two or more data blocks;

and

wherein adding the deduplication information to the deduplication table further comprises;

determining hash values for the two or more data blocks from the metadata of the incremental metadata snapshot;

determining that the hash values for the two or more data blocks are currently included in the deduplication table;

using a temporal deduplication structure to access a temporally grouped set of block entries for the two or more data blocks in the incremental metadata snapshot; and

incrementing reference counts in the block entries for each of the two or more data blocks.

10. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for performing distributed deduplication in a distributed filesystem, the method comprising:

collectively managing the data of the distributed filesystem using two or more cloud controllers, wherein collectively managing the data comprises;

storing the data for the distributed filesystem in one or more cloud storage systems, wherein the cloud controllers cache and ensure data consistency for data stored in the cloud storage systems; and

maintaining in each cloud controller a metadata hierarchy that reflects the current state of the distributed filesystem, wherein changes to the metadata for the distributed filesystem are synchronized across the cloud controllers, wherein synchronizing metadata includes synchronizing deduplication information across the cloud controllers, wherein each cloud controller maintains a deduplication table that tracks deduplicated data for the distributed filesystem; and

receiving at a cloud controller an incremental metadata snapshot from a remote cloud controller, wherein the incremental metadata snapshot comprises deduplication information for a file that was received by the remote cloud controller, wherein the cloud controller, the remote cloud controller and the cloud storage system are all distinct computing devices;

adding the deduplication information from the incremental metadata snapshot to the deduplication table on the cloud controller;

receiving at the cloud controller a client write request that comprises new file data;

using the deduplication table on the cloud controller to determine that one or more data blocks in the new file data have previously been written to the distributed filesystem by the remote cloud controller;

updating the metadata hierarchy and the deduplication table for the cloud controller to link the metadata for these duplicate new data blocks with the location of the deduplicated data blocks in the cloud storage system and cache of the cloud controller; and

distributing a subsequent incremental metadata update from the cloud controller to the other cloud controllers for the distributed filesystem that notifies the other cloud controllers of the new file data and includes deduplication updates related to the new file data that enable the other cloud controllers to update the reference counts and entries in their own respective deduplication tables to reflect the addition of the new file data to the distributed filesystem.

11. The non-transitory computer-readable storage medium of claim 10, wherein the method further comprises:

adding the deduplication information to the deduplication table stored in the cloud controller;

calculating a hash value for a data block in the client write request;

accessing the deduplication table using the hash value to determine that the data block was previously written to the distributed filesystem; and

accessing a block entry in the hash table that is associated with the previously written data block to determine a storage address for the previously written data block.

12. The non-transitory computer-readable storage medium of claim 11, wherein the method further comprises

writing new metadata for the distributed filesystem to reflect filesystem changes associated with the client write request, wherein a new metadata entry for the data block references the storage address for the previously written data block.

13. The non-transitory computer-readable storage medium of claim 11,

wherein the incremental metadata snapshot comprises metadata for two or more data blocks;

wherein adding the deduplication information to the deduplication table further comprises;

determining hash values for the two or more data blocks from the metadata of the incremental metadata snapshot;

determining that the hash values for the two or more data blocks are not currently included in the deduplication table; and

writing new block entries for each of the two or more data blocks into a temporal deduplication structure in the deduplication table; and

wherein the new block entries for the two or more data blocks are written contiguously into the temporal deduplication structure to improve the efficiency of subsequent deduplication operations.

14. The non-transitory computer-readable storage medium of claim 13,

wherein each block entry in the temporal deduplication structure includes a pointer to the next block entry that was written in the temporal deduplication structure;

and

wherein using pointers to link block entries in the temporal deduplication structure facilitates reducing the number of disk reads required to look up related block entries in the temporal deduplication structure during a subsequent deduplication operation.

15. The non-transitory computer-readable storage medium of claim 13,

wherein the client write request includes two or more additional data blocks with hash values that are not currently included in the deduplication table;

and

wherein the method further comprises;

writing new block entries for each of the two or more additional data blocks; and

performing a sort operation to ensure that the block entries for the two or more additional data blocks from the client write request and the block entries for the two or more data blocks from the incremental metadata snapshot are not interleaved in the temporal deduplication structure.

16. The non-transitory computer-readable storage medium of claim 15,

wherein performing the sort operation comprises reordering the order in which block entries are written to ensure that block entries are temporally grouped in the temporal deduplication structure based on the source of their associated data blocks;

and

wherein grouping block entries temporally based on the source of their associated data blocks facilitates reducing the number of disk reads during subsequent deduplication operations when duplicate data is written in a write order that matches the write order of the grouped block entries.

17. The non-transitory computer-readable storage medium of claim 16,

wherein a given data block in the distributed filesystem is associated with a cloud virtual address and an offset;

wherein the cloud virtual address specifies a cloud file containing the given data block and the offset specifies the location of the given data block in the cloud file;

wherein the cloud virtual address identifies a source cloud controller for the given data block; and

wherein the sort operation comprises ordering the write of block entries into the temporal deduplication structure based on the cloud virtual addresses and the offsets of the block entries'"'"' associated data blocks.

18. The non-transitory computer-readable storage medium of claim 11,

wherein the incremental metadata snapshot comprises metadata for two or more data blocks;

and

wherein adding the deduplication information to the deduplication table further comprises;

determining hash values for the two or more data blocks from the metadata of the incremental metadata snapshot;

determining that the hash values for the two or more data blocks are currently included in the deduplication table;

using a temporal deduplication structure to access a temporally grouped set of block entries for the two or more data blocks in the incremental metadata snapshot; and

incrementing reference counts in the block entries for each of the two or more data blocks.

19. A cloud controller that performs distributed deduplication for a distributed filesystem, comprising:

a processor;

a storage mechanism that stores metadata for the distributed filesystem; and

a storage management mechanism;

wherein two or more cloud controllers collectively manage the data of the distributed filesystem, wherein collectively managing the data comprises;

storing the data for the distributed filesystem in one or more cloud storage systems, wherein the storage management mechanisms of the cloud controllers are configured to cache and ensure data consistency for data stored in the cloud storage systems; and

maintaining in each cloud controller a metadata hierarchy that reflects the current state of the distributed filesystem, wherein changes to the metadata for the distributed filesystem are synchronized across the cloud controllers, wherein synchronizing metadata includes synchronizing deduplication information across the cloud controllers, wherein each cloud controller maintains a deduplication table that tracks deduplicated data for the distributed filesystem; and

wherein the storage management mechanism is further configured to;

receive an incremental metadata snapshot distributed by a remote cloud controller, wherein the incremental metadata snapshot comprises deduplication information for a file that was received by the remote cloud controller, wherein the cloud controller, the remote cloud controller and the cloud storage system are all distinct computing devices;

add the set of deduplication information from the incremental metadata snapshot to the deduplication table on the cloud controller;

receive at the cloud controller a client write request that comprises new file data;

use the deduplication table on the cloud controller to determine that one or more data blocks in the client write request have previously been written to the distributed filesystem by the remote cloud controller;

update the metadata hierarchy and the deduplication table for the cloud controller to link the metadata for these duplicate new data blocks with the location of the deduplicated data blocks in the cloud storage system and cache of the cloud controller; and

distribute a subsequent incremental metadata update from the cloud controller to the other cloud controllers for the distributed filesystem that notifies the other cloud controllers of the new file data and includes deduplication updates related to the new file data that enable the other cloud controllers to update the reference counts and entries in their own respective deduplication tables to reflect the addition of the new file data to the distributed filesystem.