DEDUPLICATION AWARE SCHEDULING OF REQUESTS TO ACCESS DATA BLOCKS

• US 20130091102A1
• Filed: 10/11/2011
• Published: 04/11/2013
• Est. Priority Date: 10/11/2011
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Nayak, Manoj
• Granted Patent: US 8,825,605 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Systems and methods for scheduling requests to access data may adjust the priority of such requests based on the presence of de-duplicated data blocks within the requested set of data blocks. A data de-duplication process operating on a storage device may build a de-duplication data map that stores information about the presence and location of de-duplicated data blocks on the storage drive. An I/O scheduler that manages the access requests can employ the de-duplicated data map to identify and quantify any de-duplicated data blocks within an access request. The I/O scheduler can then adjust the priority of the access request, based at least in part, on whether de-duplicated data blocks provide a large enough sequence of data blocks to reduce the likelihood that servicing the request, even if causing a head seek operation, will not reduce the overall global throughput of the storage system.

Claims

1. A storage system for accessing storage objects stored on a storage device having de-duplicated data, comprising

a de-duplication data map having information that identifies a de-duplicated data block on the storage device and identifies a location on the storage of the de-duplicated data block, and

an I/O scheduler for scheduling a plurality of query requests to access data stored on the storage device, and having

a dispatch processor for comparing data blocks in one or more query requests to de-duplicated data blocks identified in the de-duplication data map and for prioritizing the order of servicing the query requests as a function of the number of sequential de-duplicated data blocks within the respective query requests.

2. A storage system according to claim 1, further comprising

a de-duplication process having a mapping process for generating the de-duplication data map from data generated by a process for reducing duplicate data blocks from the storage device.

3. A storage system according to claim 1, wherein

the de-duplication data map stores, for a respective de-duplicated data block entry, a status flag indicating whether the block is a single block entry or a sequence of de-duplicated data blocks, a reference count indicating a number of file blocks referencing the de-duplicated data block and a physical disk location of the respective blocks or sequence of blocks.

4. A storage system according to claim 1, further comprising

a threshold processor for comparing a set of requested data blocks in a query request to the de-duplication data map to identify a number representing a number of sequential de-duplicated blocks within the query request.

5. A storage system according to claim 4, wherein the dispatch processor compares the number of identified de-duplicated data blocks in a request to a minimum threshold number representative of a minimum number of sequential data blocks to trigger a data de-duplication operation.

6. A storage system according to claim 1, further comprising

a disk analysis processor for selecting a set of model workloads, each having one or more query requests, and for comparing the one or more query requests to the de-duplication data map to determine characteristics representative of a typical number of de-duplicated sequential data blocks for query requests in the model workloads.

7. A storage system according to claim 6, wherein the dispatch processor prioritizes a query request as a function of a comparison between the number of de-duplicated sequential data blocks in a query request and the typical number of de-duplicated sequential data blocks.

8. A storage system according to claim 1, wherein the file system provides the dispatch processor with a relative priority value representative of a number of requests made by the file system for a particular data block.

9. A storage system according to claim 1, further comprising

a request timer for providing the dispatch processor with a measure of the amount of time a request has been pending.

10. A method for accessing storage objects on a storage device having de-duplicated data, comprising

providing a de-duplication data map having information that identifies a de-duplicated data block and identifies a storage location of the de-duplicated data block, and

scheduling a query request to read data blocks from the storage device by comparing data blocks in the query request to the de-duplicated data blocks identified in the de-duplication map and prioritizing the order of servicing the query request as a function of the number of sequential de-duplicated data blocks within the query request.

11. The method according to claim 10, further comprising

generating the de-duplication data map by applying a de-duplication process to the storage device and recording the storage location of de-duplicated data blocks as the de-duplication process removes duplicate data blocks from the storage device.

12. The method according to claim 10, further comprising

storing in the de-duplication data map, for a respective de-duplicated data block, a status flag indicating whether the block is a single entry or a sequence of de-duplicated blocks, a reference count indicating the number of data blocks referencing the de-duplicated block and a physical location of a block or sequence of blocks.

13. The method according to claim 10, further comprising

selecting a set of model workloads, each having one or more query requests, and comparing the one or more query requests to the de-duplication data map to determine characteristics representative of a typical number of de-duplicated sequential data blocks in a request made by a model workload.

14. The method according to claim 10, further comprising determining a relative priority value representative of a number of times a de-duplicated data block has been requested within a set period of time.

15. A storage system for accessing storage objects of a storage system stored on a storage device, comprising

a de-duplication processor for removing duplicate data blocks on the storage device and for generating a de-duplication data map having information that identifies a de-duplicated data block and a location of the de-duplicated data block on the storage device, and

an I/O scheduler for scheduling a plurality of query requests to read data blocks from the storage device, and having

a dispatch processor for analyzing the de-duplicated data blocks in a query request and for scheduling the respective query requests for dispatch as a function of the de-duplicated data blocks in the query request.

16. The storage system according to claim 15, further comprising

a file system configured for comparing data blocks in a query request with de-duplicated data blocks in the de-duplication data map and for making data blocks in the query request that match de-duplicated data blocks in the map.

17. The storage system according to claim 16, wherein the file system is further configured to

detect a file being deleted, and

edit data in the de-duplication data map to remove from the de-duplication data map references to data blocks of the deleted file.

18. The storage system according to claim 17, wherein removing references includes reducing a number representative of a number of file data blocks that reference a de-duplicated data block in the map.

19. The storage system according to claim 15, wherein the storage device includes a disk drive and the de-duplication data map stores data representative of a physical location of the disk of a de-duplicated data block.

20. The storage system according to claim 15, wherein the de-duplication process applies a minimum threshold to de-duplicated sequences of data blocks being larger than a minimum number of data blocks.

21. The storage system according to claim 20, wherein the dispatch processor schedules a query request for earlier dispatch if the respective query request includes a set of sequential de-duplicated data blocks that is larger than the minimum threshold of data blocks.