APPLYING DEDUPLICATION DIGESTS TO AVOID SAME-DATA WRITES

• US 20200133547A1
• Filed: 10/31/2018
• Published: 04/30/2020
• Est. Priority Date: 10/31/2018
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Armangau, Philippe, Chaudhary, Monica, Karri, Ajay, Daniel, Alexander
• Granted Patent: US 11,216,199 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0683 Plurality of storage devices

Abstract

A technique for managing write requests in a data storage system checks whether newly-arriving data match previously-stored data that have been recorded in a deduplication database. If a match is found, the technique compares mapping metadata for the newly-arriving data with mapping metadata for the matching data. If both sets of metadata point to the same storage location, then the newly-arriving data is a same-data write and a new write to disk is avoided.

Claims

1. A method of managing write requests in a data storage system, the method comprising:

receiving an I/O (Input/Output) request that specifies a current extent of data to be written to a specified logical address;

collecting mapping metadata that maps the specified logical address to a corresponding storage location;

performing a dedupe-match test on the current extent, the dedupe-match test configured to (i) produce a first result in response to the current extent matching an entry in a deduplication database, and (ii) produce a second result otherwise, the deduplication database having multiple entries for respective extents of previously stored data, each entry including a reference to metadata that maps the respective extent to a respective storage location;

in response to detecting that the dedupe-match test has produced the first result, performing a metadata-match test for the current extent, the metadata-match test configured to (i) produce a Match result in response to the metadata referenced by the matching entry and the mapping metadata of the current extent pointing to a same storage location, and (ii) produce a No-Match result otherwise; and

in response to the metadata-match test producing the Match result, completing the I/O request without performing any write of the current extent to persistent storage.

2. The method of claim 1, wherein the deduplication database provides a digest for each entry, each digest computed as hash of contents of the respective extent, and wherein performing the dedupe-match test includes matching a hash of contents of the current extent with one of the digests in the deduplication database.

3. The method of claim 2, further comprising:

receiving a second I/O request that specifies a second extent of data to be written to a second logical address in the data storage system;

performing the dedupe-match test on the second extent; and

in response to the dedupe-match test on the second extent producing the second result, creating a second entry in the deduplication database, the second entry including a digest computed from the second extent and a reference to metadata that maps the second logical address to a corresponding storage location in the data storage system where the second extent is persistently stored.

4. The method of claim 3, further comprising:

receiving a third I/O request that specifies a third extent of data to be written to a third logical address;

collecting mapping metadata that maps the third logical address to a corresponding storage location in the data storage system;

performing the dedupe-match test on the third extent, the deduplication operation producing the first result by matching the third extent to the second entry in the deduplication database; and

in response to confirming that both the metadata referenced by the second entry and the mapping metadata that maps the third logical address point to the same storage location, completing the third I/O request without performing any write of the third extent to persistent storage, the third logical address being equal to the second logical address.

5. The method of claim 3, further comprising:

receiving a fourth I/O request that specifies a fourth extent of data to be written to a fourth logical address;

collecting mapping metadata that maps the fourth logical address to a corresponding storage location in the data storage system;

performing the dedupe-match test on the fourth extent, the deduplication operation producing the first result by matching the fourth extent to the second entry in the deduplication database; and

in response to detecting that the metadata referenced by the second entry and the mapping metadata that maps the fourth logical address point to different storage locations, (i) configuring metadata for mapping the fourth logical address to the storage location to which the second logical address is mapped and (ii) completing the fourth I/O request without performing any write of the fourth extent to persistent storage, the fourth logical address being different from the second logical address.

6. The method of claim 5, further comprising:

receiving a fifth I/O request that specifies a fifth extent of data to be written to a fifth logical address;

collecting mapping metadata that maps the fifth logical address to a corresponding storage location in the data storage system;

performing the dedupe-match test on the fifth extent, the deduplication operation producing the first result by matching the fifth extent to the second entry in the deduplication database; and

in response to detecting that the metadata referenced by the second entry and the mapping metadata that maps the fifth logical address point to the same storage location, completing of the fifth I/O request without performing any write of the fifth extent to persistent storage, the fifth logical address being equal to the fourth logical address.

7. The method of claim 2, wherein the current extent is a block-sized extent, and wherein the matching entry is provided for a block stored in the data storage system.

8. The method of claim 2, further comprising:

aggregating a set of data received in I/O (Input/Output) requests into a batch of data in a data log, the batch of data including multiple extents, each extent directed to a respective logical address in the data storage system;

collecting mapping metadata that maps the logical address of each extent to a corresponding storage location in the data storage system;

performing the dedupe-match test on each of the extents in the batch;

for each extent for which the dedupe-match test produces the first result, performing the metadata-matching test, and

for an extent for which the dedupe-match test produces the first result and the metadata-matching test produces the Match result, marking the extent for no action in a batch-flush table, the batch-flush table associating each extent in the batch with a respective action, or no action, to be performed when flushing the batch from the data log.

9. The method of claim 8, further comprising:

for an extent for which the dedupe-match test produces the first result and the metadata-matching test produces the No-Match result, marking the extent for deduplication in the batch-flush table.

10. The method of claim 8, further comprising:

for an extent for which the dedupe-match test produces the second result, marking the extent for one of (i) an overwrite or (ii) an allocating write.

11. The method of claim 8,

wherein collecting the mapping metadata includes associating each of a set of extents in the batch with a respective metadata element that uniquely identifies a storage location of the respective extent, and

wherein performing the metadata-match test on an extent includes (i) comparing the respective metadata element with the metadata referenced by the matching entry for that extent and (ii) producing the Match result in response to the respective metadata element and the metadata referenced by the matching entry being identical.

12. The method of claim 2, further comprising, in response to the metadata-match test producing the Match result, completing the I/O request without performing any updates to mapping metadata for mapping the current extent to persistent storage.

13. A data storage system, comprising control circuitry that includes a set of processing units coupled to memory, the control circuitry constructed and arranged to:

receive an I/O (Input/Output) request that specifies a current extent of data to be written to a specified logical address;

collect mapping metadata that maps the specified logical address to a corresponding storage location;

perform a dedupe-match test on the current extent, the dedupe-match test configured to (i) produce a first result in response to the current extent matching an entry in a deduplication database, and (ii) produce a second result otherwise, the deduplication database having multiple entries for respective extents of previously stored data, each entry including a reference to metadata that maps the respective extent to a respective storage location;

in response to detecting that the dedupe-match test has produced the first result, perform a metadata-match test for the current extent, the metadata-match test configured to (i) produce a Match result in response to the metadata referenced by the matching entry and the mapping metadata of the current extent pointing to a same storage location, and (ii) produce a No-Match result otherwise; and

in response to the metadata-match test producing the Match result, complete the I/O request without performing any write of the current extent to persistent storage.

14. A computer program product including a set of non-transitory, computer-readable media having instructions which, when executed by control circuitry of a data storage system, cause the control circuitry to perform a method for managing write requests, the method comprising:

receiving an I/O (Input/Output) request that specifies a current extent of data to be written to a specified logical address;

collecting mapping metadata that maps the specified logical address to a corresponding storage location;

performing a dedupe-match test on the current extent, the dedupe-match test configured to (i) produce a first result in response to the current extent matching an entry in a deduplication database, and (ii) produce a second result otherwise, the deduplication database having multiple entries for respective extents of previously stored data, each entry including a reference to metadata that maps the respective extent to a respective storage location;

in response to detecting that the dedupe-match test has produced the first result, performing a metadata-match test for the current extent, the metadata-match test configured to (i) produce a Match result in response to the metadata referenced by the matching entry and the mapping metadata of the current extent pointing to a same storage location, and (ii) produce a No-Match result otherwise; and

in response to the metadata-match test producing the Match result, completing the I/O request without performing any write of the current extent to persistent storage.

15. The computer program product of claim 14, wherein the method further comprises, in response to the metadata-match test producing the Match result, completing the I/O request without performing any updates to mapping metadata for mapping the current extent to persistent storage.

16. The computer program product of claim 15, wherein the method further comprises:

receiving a second I/O request that specifies a second extent of data to be written to a second logical address in the data storage system;

performing the dedupe-match test on the second extent; and

in response to the dedupe-match test on the second extent producing the second result, creating a second entry in the deduplication database, the second entry including a digest computed from the second extent and a reference to metadata that maps the second logical address to a corresponding storage location in the data storage system where the second extent is persistently stored.

17. The computer program product of claim 15, wherein the current extent is a block-sized extent, and wherein the matching entry is provided for a block stored in the data storage system.

18. The computer program product of claim 15, wherein the method further comprises:

aggregating a set of data received in I/O (Input/Output) requests into a batch of data in a data log, the batch of data including multiple extents, each extent directed to a respective logical address in the data storage system;

collecting mapping metadata that maps the logical address of each extent to a corresponding storage location in the data storage system;

performing the dedupe-match test on each of the extents in the batch;

for each extent for which the dedupe-match test produces the first result, performing the metadata-matching test, and

for an extent for which the dedupe-match test produces the first result and the metadata-matching test produces the Match result, marking the extent for no action in a batch-flush table, the batch-flush table associating each extent in the batch with a respective action, or no action, to be performed when flushing the batch from the data log.

19. The computer program product of claim 18, wherein the method further comprises:

for an extent for which the dedupe-match test produces the first result and the metadata-matching test produces the No-Match result, marking the extent for deduplication in the batch-flush table.

20. The computer program product of claim 18, wherein the method further comprises:

for an extent for which the dedupe-match test produces the second result, marking the extent for one of (i) an overwrite or (ii) an allocating write.