Granted Patent B1

US 10,540,341 · App. 15/087,345 · Granted Jan 21, 2020

Inventors: Prasanna Wakhare (Mountain View, CA); Sudhakar Paulzagade (Mountain View, CA); Saurabh Jain (Mountain View, CA)

Assignee: Veritas Technologies LLC

G06F16/2365G06F13/102G06F16/2477H04L47/2441H04L47/2483

Abstract

Claims (116)

1. A method of storage management, comprising:

deduplicating data;

receiving an Input/Output (I/O) request;

detecting a count associated with the deduplicated data for an application; and

scheduling the I/O request associated with a storage unit based upon the detected count, including:

detecting a current clock tick;

calculating a dedupe ratio by dividing the detected count by an assigned bandwidth;

calculating a tag ratio by dividing an I/O size by the assigned bandwidth;

processing, when the detected count is equal to 0, the I/O request when a sum of the current clock tick, and the tag ratio are less than or equal to a next clock tick; and

processing, when the detected count is greater than 0, the I/O request when a sum of the current clock tick, a negative value of the ratio, and the tag ratio are less than or equal to the next clock tick;

wherein bandwidth is assigned to the I/O request based upon the detected count and a Quality of Service (QoS) policy associated with packet flow to account for deduplication.

2. The method of claim 1 , wherein the deduplicating data comprises:

fingerprinting data;

identifying the duplicate data using the fingerprints of data;

mapping a location associated with the duplicate data;

storing the mapping; and

deleting the duplicate data from storage.

3. The method of claim 1 , wherein the detecting the count comprises:

retrieving a map of locations associated with duplicated data;

counting the mapped locations associated with a client; and

setting the detected count to equal the mapped location count.

4. The method of claim 1 , wherein detecting the current clock tick comprises:

setting a virtual clock; and

reading the virtual clock at a predetermined time to generate the current clock tick.

5. A method of storage management, comprising:

deduplicating data;

receiving an Input/Output (I/O) request;

detecting a count associated with the deduplicated data for an application; and

scheduling the I/O request associated with a storage unit based upon the detected count and other I/O requests that have been received, including:

implementing a bucket, by a counter, configured to receive a token corresponding to each of the I/O requests and detect a number of tokens received;

detecting when the number of tokens in the bucket is greater than a predetermined threshold;

setting, in response to the detected number of tokens exceeding the predetermined threshold, a current dock tick equal to a first predetermined value;

setting, in response to the detected number of tokens not exceeding the predetermined threshold, the current clock tick equal to a second predetermined value;

calculating a dedupe ratio by dividing the detected count by an assigned bandwidth;

calculating a tag ratio by dividing an I/O size by the assigned bandwidth;

processing, when the detected count is equal to 0, the I/O request when a sum of the current clock tick, and the tag ratio are less than or equal to a next clock tick; and

processing, when the count is greater than 0, the I/O request when a sum of the current clock tick, a negative value of the dedupe ratio, and the tag ratio are less than or equal to the next clock tick; and

wherein bandwidth is assigned to the I/O request based upon the detected count and a Quality of Service (QoS) policy associated with packet flow to account for deduplication.

6. A storage controller comprising:

a memory; and

a processor configured to:

deduplicate data;

receive an Input/Output (I/O) request;

detect a count associated with the deduplicated data for an application; and

schedule the I/O request in a storage unit based upon the detected count, including:

detect a current clock tick;

calculate a dedupe ratio by dividing the detected count by an assigned bandwidth;

calculate a tag ratio by dividing an I/O size by the assigned bandwidth;

process, when the detected count is equal to 0, the I/O request when a sum of the current clock tick, and the tag ratio are less than or equal to a sum of the current clock tick and 1; and

process, when the detected count is greater than 0, the I/O request when a sum of the current clock tick, a negative value of the dedupe ratio, and the tag ratio are less than or equal to a sum of the current clock tick and 1; and

wherein bandwidth is assigned to the I/O request based upon the detected count and a Quality of Service (QoS) policy associated with packet flow to account for deduplication.

7. The storage controller of claim 6 , wherein the processor for deduplicating data is configured to:

fingerprint data;

identify the duplicate data using the fingerprints of data;

map a location associated with the duplicate data;

store the map; and

delete the duplicate data from storage.

8. The storage controller of claim 6 , wherein the processor for detecting the count is configured to:

retrieve a map of locations associated with duplicated data;

count the mapped locations associated with a client; and

set the detected count to equal the mapped location count.

9. A storage controller comprising:

a memory; and

a processor configured to:

deduplicate data;

receive an Input/Output (I/O) request;

detect a count associated with the deduplicated data for an application; and

schedule the I/O request in a storage unit, based upon the detected count and other I/O requests that have been received, to:

implement a bucket, by a counter, configured to receive a to ken corresponding to each I/O request received and detect a number of tokens received;

detect when the number of tokens in the bucket is greater than a predetermined threshold;

set, in response to the detected number of tokens exceeding the predetermined threshold, the current clock tick equal to a first predetermined value;

set, in response to the detected number of tokens not exceeding the predetermined threshold, a current clock tick equal to a second predetermined value;

calculate a dedupe ratio by dividing the detected count by an assigned bandwidth;

calculate a tag ratio by dividing an I/O size by the assigned bandwidth;

process, when the detected count is equal to 0, the I/O request when a sum of the current clock tick, and the tag ratio are less than or equal to a sum of the current clock tick and 1; and

process, when the detected count is greater than 0, the I/O request when a sum of the current clock tick, a negative value of the dedupe ratio, and the tag ratio are less than or equal to a sum of the current clock tick and 1.

10. A non-transitory computer-readable medium including code for performing a method, the method comprising:

deduplicating data;

receiving an Input/Output (I/O) request;

detecting a dedupe count associated with the deduplicated data for an application; and

scheduling the I/O request in a storage unit based upon the detected dedupe count, including:

detecting a current clock tick;

calculating a dedupe ratio by dividing the dedupe count by an assigned bandwidth;

calculating a tag ratio by dividing an I/O size by the assigned bandwidth;

processing, when the dedupe count is equal to 0, the I/O request when a sum of the current clock tick, and the tag ratio are less than or equal to a next clock tick; and

processing, when the dedupe count is greater than 0, the I/O request when a sum of the current clock tick, a negative value of the dedupe ratio, and the tag ratio are less than or equal to the next clock tick;

wherein bandwidth is assigned to the I/O request based upon the detected dedupe count and a Quality of Service (QoS) policy associated with packet flow to account for deduplication.

11. The non-transitory computer-readable medium of claim 10 , wherein the deduplicating data comprises:

fingerprinting data;

identifying the duplicate data using the fingerprints of data;

mapping a location associated with the duplicate data;

storing the mapping; and

deleting the duplicate data from storage.

12. The non-transitory computer-readable medium of claim 10 , wherein the detecting dedupe count comprises:

retrieving the mapping;

counting mapped locations associated with a client; and

setting the dedupe count to equal the mapped location count.

13. A non-transitory computer-readable medium including code for performing a method, the method comprising:

deduplicating data;

receiving an Input/Output (I/O) request;

detecting a dedupe count associated with the deduplicated data for an application; and

scheduling the I/O request in a storage unit based upon the dedupe count and other I/O requests that have been received, including:

implementing a bucket, by a counter, configured to receive a token corresponding to each I/O request received and detect a number of tokens received;

detecting when the number of tokens in the bucket is greater than a predetermined threshold;

setting, in response to the detected number of tokens exceeding the predetermined threshold, a current clock tick equal to a first predetermined value;

setting, in response to the detected number of tokens not exceeding the predetermined threshold, the current clock tick equal to a second predetermined value;

calculating a dedupe ratio by dividing the dedupe count by an assigned bandwidth;

calculating a tag ratio by dividing an I/O size by the assigned bandwidth;

processing, when the dedupe count is equal to 0, the I/O request when a sum of the current clock tick, and the tag ratio are less than or equal to a sum of the current clock tick and 1; and

processing, when the dedupe count is greater than 0, the I/O request when a sum of the current clock tick, a negative value of the dedupe ratio, and the tag ratio are less than or equal to a sum of the current clock tick and 1;

wherein the deduplicating data comprises:

fingerprinting data;

identifying the duplicate data using the fingerprints of data;

mapping a location associated with the duplicate data;

storing the mapping; and

deleting the duplicate data from storage.

Assignments (10)