# US 10,372,344 B2 · Read tail latency reduction

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,372,344 B2
- Document ID: US10372344B2
- Status: Granted
- Kind: B2
- Application number: 15/373,456
- Filed: 2016-12-08
- Published: 2018-06-14
- Granted: 2019-08-06
- Earliest claimed: 2016-12-08
- Assignees: Western Digital Technologies, Inc.
- Applicants: Western Digital Technologies, Inc.
- Inventors: James N. Malina; Robert L. Horn; Kent Anderson; James C. Alexander; Albert H. Chen
- Web page: https://patentgrep.com/patent/US10372344B2

## CPC

- G06F 3/0611: {in relation to response time}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/064: {Management of blocks}
- G06F 3/0652: {Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket}
- G06F 3/0653: {Monitoring storage devices or systems}
- G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling}
- G06F 3/0673: {Single storage device}
- G06F 3/0676: {Magnetic disk device}
- G06F 3/0689: {Disk arrays, e.g. RAID, JBOD}
- H03M 13/373: {with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes}
- H03M 13/3761: {using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

A collective latency indicator is determined that is associated with a latency in retrieving multiple erasure coded shards generated from an erasure coding on initial data. The collective latency indicator is compared to a latency limit, and a number of erasure coded shards to retrieve is adjusted based on the comparison of the collective latency indicator to the latency limit.

## Claims

### Claim 1

A data storage system, comprising:
a plurality of Data Storage Devices (DSDs) for storing a plurality of erasure coded shards, each DSD of the plurality of DSDs for storing one or more erasure coded shards of the plurality of erasure coded shards, wherein the plurality of erasure coded shards is generated from an erasure coding on initial data; and
a controller configured to:
set an initial number of the erasure coded shards to retrieve from the plurality of DSDs;
determine a collective latency indicator associated with a latency in retrieving the initial number of erasure coded shards of the plurality of erasure coded shards, wherein the collective latency indicator is based on a predetermined percentage of the slower times to complete a read command for each of a plurality of particular subsets of the initial number of erasure coded shards;
compare the collective latency indicator to a latency limit to determine whether the collective latency indicator is (a) greater than or equal to the latency limit or (b) less than the latency limit; and
adjust the number of erasure coded shards to retrieve to reduce read tail latency based on whether the collective latency indicator is greater than or equal to or is less than the latency limit.

### Claim 2 (depends on 1)

The data storage system of claim 1, wherein the controller is further configured to:
determine an individual latency indicator for each DSD of the plurality of DSDs, wherein each individual latency indicator is associated with a latency in retrieving an erasure coded shard of the initial number of erasure coded shards stored in a respective DSD; and
determine the collective latency indicator using determined individual latency indicators.

### Claim 3 (depends on 1)

The data storage system of claim 1, wherein the controller is further configured to:
send at least one read command to one or more DSDs of the plurality of DSDs to retrieve at least the adjusted number of erasure coded shards;
receive the adjusted number of erasure coded shards from the one or more DSDs; and
initiate recovery of the initial data or unreceived erasure coded shards not received by when the adjusted number of erasure coded shards have been received, wherein the recovery is performed using the erasure coding and the received adjusted number of erasure coded shards.

### Claim 4 (depends on 3)

The data storage system of claim 3, wherein:
the at least one read command is sent to the plurality of DSDs to retrieve the plurality of erasure coded shards, and
the controller is further configured to abort recovery of the initial data or the unreceived erasure coded shards if all of the plurality of erasure coded shards is received before recovery is completed.

### Claim 5 (depends on 3)

The data storage system of claim 3, wherein:
the at least one read command is sent to the plurality of DSDs to retrieve the plurality of erasure coded shards, and
the controller is further configured to delay initiating the recovery of the initial data or the unreceived erasure coded shards to allow additional time for receiving one or more of the unreceived erasure coded shards before initiating recovery of the initial data or the unreceived erasure coded shards.

### Claim 6 (depends on 1)

The data storage system of claim 1, wherein the controller is further configured to:
increase the number of erasure coded shards to retrieve if the collective latency indicator is greater than or equal to the latency limit.

### Claim 7 (depends on 6)

The data storage system of claim 6, wherein the controller is further configured to:
determine whether the increased number of erasure coded shards exceeds the total number of the plurality of erasure coded shards; and
generate an indication that the total number of the plurality of erasure coded shards is insufficient to meet the latency limit.

### Claim 8 (depends on 1)

The data storage system of claim 1, wherein the controller is further configured to:
decrease the number of erasure coded shards to retrieve if the collective latency indicator is less than the latency limit.

### Claim 9 (depends on 8)

The data storage system of claim 8, wherein the controller is further configured to:
determine whether decreasing the number of erasure coded shards would fall below a minimum number of erasure coded shards for recovering the initial data; and
maintain the number of erasure coded shards to retrieve if the decreased number of erasure coded shards would fall below the minimum number of erasure coded shards.

### Claim 10 (depends on 1)

The data storage system of claim 1, wherein the controller is further configured to:
determine whether the collective latency indicator is within a predetermined range below the latency limit; and
increase the number of erasure coded shards to read if the collective latency indicator is within the predetermined range below the latency limit.

### Claim 11 (depends on 1)

The data storage system of claim 1, wherein the controller is further configured to:
determine whether the collective latency indicator is within a predetermined range above a low latency limit that is less than the latency limit; and
decrease the number of erasure coded shards to retrieve if the collective latency indicator is within the predetermined range above the low latency limit.

### Claim 12

A method of reading data in a data storage system including a plurality of Data Storage Devices (DSDs) storing a plurality of erasure coded shards, each DSD of the plurality of DSDs storing one or more erasure coded shards of the plurality of erasure coded shards, wherein the plurality of erasure coded shards is generated from an erasure coding on initial data, the method comprising:
setting an initial number of the erasure coded shards to retrieve from the plurality of DSDs;
determining a collective latency indicator associated with a latency in retrieving the initial number of erasure coded shards of the plurality of erasure coded shards, wherein the collective latency indicator is based on a predetermined percentage of the slower times to complete a read command for each of a plurality of particular subsets of the initial number of erasure coded shards;
comparing the collective latency indicator to a latency limit to determine whether the collective latency indicator is (a) greater than or equal to the latency limit or (b) less than the latency limit; and
adjusting the number of erasure coded shards to retrieve to reduce read tail latency based on whether the collective latency indicator is greater than or equal to or is less than the latency limit.

### Claim 13 (depends on 12)

The method of claim 12, further comprising:
determining an individual latency indicator for each DSD of the plurality of DSDs, wherein each individual latency indicator is associated with a latency in retrieving an erasure coded shard of the initial number of erasure coded shards stored in a respective DSD; and
determining the collective latency indicator using determined individual latency indicators.

### Claim 14 (depends on 12)

The method of claim 12, further comprising:
sending at least one read command to one or more DSDs of the plurality of DSDs to retrieve at least the adjusted number of erasure coded shards;
receiving the adjusted number of erasure coded shards from the one or more DSDs; and
initiating recovery of the initial data or unreceived erasure coded shards not received by when the adjusted number of erasure coded shards have been received, wherein the recovery is performed using the erasure coding and the received adjusted number of erasure coded shards.

### Claim 15 (depends on 14)

The method of claim 14, wherein:
the at least one read command is sent to the plurality of DSDs to retrieve the plurality of erasure coded shards, and
the method further comprises aborting recovery of the initial data or the unreceived erasure coded shards if all of the plurality of erasure coded shards is received before recovery is completed.

### Claim 16 (depends on 14)

The method of claim 14, wherein:
the at least one read command is sent to the plurality of DSDs to retrieve the plurality of erasure coded shards, and
the method further comprises delaying initiating the recovery of the initial data or the unreceived erasure coded shards to allow additional time for receiving one or more of the unreceived erasure coded shards before initiating recovery of the initial data or the unreceived erasure coded shards.

### Claim 17 (depends on 12)

The method of claim 12, further comprising:
increasing the number of erasure coded shards to retrieve if the collective latency indicator is greater than or equal to the latency limit.

### Claim 18 (depends on 17)

The method of claim 17, further comprising:
determining whether the increased number of erasure coded shards exceeds the total number of the plurality of erasure coded shards; and
generating an indication that the total number of the plurality of erasure coded shards is insufficient to meet the latency limit.

### Claim 19 (depends on 12)

The method of claim 12, further comprising:
decreasing the number of erasure coded shards to retrieve if the collective latency indicator is less than the latency limit.

### Claim 20 (depends on 19)

The method of claim 19, further comprising:
determining whether decreasing the number of erasure coded shards would fall below a minimum number of erasure coded shards for recovering the initial data; and
maintaining the number of erasure coded shards to retrieve if the decreased number of erasure coded shards would fall below the minimum number of erasure coded shards.

### Claim 21 (depends on 12)

The method of claim 12, further comprising:
determining whether the collective latency indicator is within a predetermined range below the latency limit; and
increasing the number of erasure coded shards to retrieve if the collective latency indicator is within the predetermined range below the latency limit.

### Claim 22 (depends on 12)

The method of claim 12, further comprising:
determining whether the collective latency indicator is within a predetermined range above a low latency limit that is less than the latency limit; and
decreasing the number of erasure coded shards to retrieve if the collective latency indicator is within the predetermined range above the low latency limit.

### Claim 23

A Data Storage Device (DSD), comprising:
a plurality of memory portions for storing a plurality of erasure coded shards, each memory portion of the plurality of memory portions for storing one or more erasure coded shards of the plurality of erasure coded shards, wherein the plurality of erasure coded shards is generated from an erasure coding on initial data; and
a controller configured to:
set an initial number of the erasure coded shards to retrieve from the plurality of DSDs;
determine a collective latency indicator associated with retrieving the initial number of erasure coded shards in the plurality of erasure coded shards, wherein the collective latency indicator is based on a predetermined percentage of the slower times to complete a read command for each of a plurality of particular subsets of the initial number of erasure coded shards;
compare the collective latency indicator to a latency limit to determine whether the collective latency indicator is (a) greater than or equal to the latency limit or (b) less than the latency limit; and
adjust the number of erasure coded shards to retrieve to reduce read tail latency based on whether the collective latency indicator is greater than or equal to or is less than the latency limit.

### Claim 24

A host, comprising:
an interface for communicating with a data storage system including a plurality of Data Storage Devices (DSDs) storing a plurality of erasure coded shards, each DSD of the plurality of DSDs storing one or more erasure coded shards of the plurality of erasure coded shards, wherein the plurality of erasure coded shards is generated from an erasure coding on initial data; and
a processor configured to:
set an initial number of the erasure coded shards to retrieve from the plurality of DSDs;
determine a collective latency indicator associated with retrieving the initial number of erasure coded shards in the plurality of erasure coded shards, wherein the collective latency indicator is based on a predetermined percentage of the slower times to complete a read command for each of a plurality of particular subsets of the initial number of erasure coded shards;
compare the collective latency indicator to a latency limit to determine whether the collective latency indicator is (a) greater than or equal to the latency limit or (b) less than the latency limit; and
adjust the number of erasure coded shards to retrieve to reduce read tail latency based on whether the collective latency indicator is greater than or equal to or is less than the latency limit.

### Claim 25

A Data Storage Device (DSD) for use in a data storage system including a plurality of DSDs storing a plurality of erasure coded shards, each DSD of the plurality of DSDs storing one or more erasure coded shards of the plurality of erasure coded shards, wherein the plurality of erasure coded shards is generated from an erasure coding on initial data, the DSD comprising:
an interface for communicating with the plurality of DSDs; and
a controller configured to:
set an initial number of the erasure coded shards to retrieve from the plurality of DSDs;
determine a collective latency indicator associated with retrieving the initial number of erasure coded shards in the plurality of erasure coded shards, wherein the collective latency indicator is based on a predetermined percentage of the slower times to complete a read command for each of a plurality of particular subsets of the initial number of erasure coded shards;
compare the collective latency indicator to a latency limit to determine whether the collective latency indicator is (a) greater than or equal to the latency limit or (b) less than the latency limit; and
adjust the number of erasure coded shards to retrieve to reduce read tail latency based on whether the collective latency indicator is greater than or equal to or is less than the latency limit.

### Claim 26 (depends on 6)

The data storage system of claim 6, wherein increasing the number of erasure coded shards to retrieve includes determining the increasing number of shards based on the amount by which the collective latency indicator exceeds the latency limit.

### Claim 27

A Data Storage Device (DSD) comprising:
a plurality of memory portions storing a plurality of erasure coded shards, each memory portion of the plurality of memory portions storing one or more erasure coded shards of the plurality of erasure coded shards, wherein the plurality of erasure coded shards is generated from an erasure coding on initial data;
means for setting an initial number of the erasure coded shards to retrieve from the plurality of DSDs;
means for determining a collective latency indicator associated with retrieving the initial number of erasure coded shards in the plurality of erasure coded shards, wherein the collective latency indicator is based on a predetermined percentage of the slower times to complete a read command for each of a plurality of particular subsets of the initial number of erasure coded shards;
means for comparing the collective latency indicator to a latency limit to determine whether the collective latency indicator is (a) greater than or equal to the latency limit or (b) less than the latency limit; and
means for adjusting the number of erasure coded shards to retrieve to reduce read tail latency based on whether the collective latency indicator is greater than or equal to or is less than the latency limit.