# US 2014/0156713 A1 · Deadline-Based Scheduling in a Distributed File System

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

- Number: US 2014/0156713 A1
- Document ID: US20140156713A1
- Status: Published application
- Kind: A1
- Application number: 13/705,715
- Filed: 2012-12-05
- Published: 2014-06-05
- Earliest claimed: 2012-12-05
- Assignees: HGST Netherlands B.V.
- Applicants: Hgst Netherlands B.V.
- Inventors: Zvonimir Bandic; Filip Blagojevic; Cyril Guyot; Timothy Tsai; Qingbo Wang
- Web page: https://patentgrep.com/patent/US20140156713A1

## CPC

- G06F 16/1844: {Management specifically adapted to replicated file systems}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Approaches for retrieving files from a replicated file system. A component receives, from a requestor, a request for a copy of a data unit. The component identifies a plurality of storage nodes that each stores a complete copy of the data unit. The component sends, to the plurality of storage nodes, an instruction to retrieve a copy of the data unit within a specified period of time. At each storage node receiving an instruction, a determination of whether the copy of the data unit may be retrieved within the specified period of time is made, and if so, the copy of the data unit is provided to the component only if the copy of the data unit was actually retrieved within the specified period. The component provides the first copy of the data unit it receives to the requestor and discards any subsequently received copies of the data unit.

## Claims

### Claim 1

A system for retrieving a file from a replicated file system, comprising:
one or more processors; and
one or more machine-readable mediums storing one or more sequences of instructions, which when executed by the one or more processors, causes:
in response to a software component receiving, from a requestor, a request for a copy of a data unit, identifying a plurality of storage nodes that each stores a complete copy of the data unit;
the software component sending, in parallel to each of the plurality of storage nodes, an instruction to retrieve a copy of the data unit within a specified period of time;
at each of the plurality of storage nodes, performing:
determining whether the copy of the data unit may be retrieved within the specified period of time, and
upon determining that the copy of the data unit may be retrieved within the specified period of time, (a) retrieving the copy of the data unit, and (b) providing the copy of the data unit to the software component only if the copy of the data unit was actually retrieved within the specified period of time; and
at the software component, providing the first copy of the data unit received to the requestor and discarding any subsequently received copies of the data unit.

### Claim 2 (depends on 1)

The system of claim 1, wherein the data unit is a chunk.

### Claim 3 (depends on 1)

The system of claim 1, wherein the data unit is a file.

### Claim 4 (depends on 1)

The system of claim 1, wherein the software component is a Hadoop client or any component capable of storing data units using a replicated file system on the plurality of storage nodes.

### Claim 5 (depends on 1)

The system of claim 1, wherein a single file system replicates the data unit on each of the plurality of storage nodes.

### Claim 6 (depends on 1)

The system of claim 1, wherein the specified period of time t is calculated using the expression t=F−1(1−n√p), where n is the number of the plurality of locations, F is a cumulative distribution function of the completion time to retrieve data units at each of the plurality of storage nodes, and p is probability that at least one location will provide a copy of the data unit within the specified period of time.

### Claim 7 (depends on 6)

The system of claim 6, wherein the function F is estimated by modeling an observed percentage of commands, issued to a set of storage nodes which include the plurality of storage nodes, which complete within a plurality of different time intervals.

### Claim 8 (depends on 1)

The system of claim 1, wherein the specified period of time is a first period of time, and wherein execution of the one or more sequences of instructions further causes:
upon the software component failing to receive the copy of the data unit from any of the plurality of storage nodes after a predetermined amount of time, the software component sending, in parallel to each of the plurality of storage nodes, an instruction to retrieve the copy of the data unit within a second specified period of time of greater length than the first period of time.

### Claim 9

A method for retrieving a file from a replicated file system, comprising:
in response to a software component receiving, from a requestor, a request for a copy of a data unit, identifying a plurality of storage nodes that each stores a complete copy of the data unit;
the software component sending, in parallel to each of the plurality of storage nodes, an instruction to retrieve a copy of the data unit within a specified period of time;
at each of the plurality of storage nodes, performing:
determining whether the copy of the data unit may be retrieved within the specified period of time, and
upon determining that the copy of the data unit may be retrieved within the specified period of time, (a) retrieving the copy of the data unit, and (b) providing the copy of the data unit to the software component only if the copy of the data unit was actually retrieved within the specified period of time; and
at the software component, providing the first copy of the data unit received to the requestor and discarding any subsequently received copies of the data unit.

### Claim 10 (depends on 9)

The method of claim 9, wherein the data unit is a chunk.

### Claim 11 (depends on 9)

The method of claim 9, wherein the data unit is a file.

### Claim 12 (depends on 9)

The method of claim 9, wherein the software component is a Hadoop client or any component capable of storing data units using a replicated file system on the plurality of storage nodes.

### Claim 13 (depends on 9)

The method of claim 9, wherein a single file system replicates the data unit on each of the plurality of storage nodes.

### Claim 14 (depends on 9)

The method of claim 9, wherein the specified period of time t is calculated using the expression t=F−1(1−n√p), where n is the number of the plurality of locations, F is a cumulative distribution function of the completion time to retrieve data units at each of the plurality of storage nodes, and p is probability that at least one location will provide a copy of the data unit within the specified period of time.

### Claim 15 (depends on 14)

The method of claim 14, wherein the function F is estimated by modeling an observed percentage of commands, issued to a set of storage nodes which include the plurality of storage nodes, which complete within a plurality of different time intervals.

### Claim 16 (depends on 9)

The method of claim 9, wherein the specified period of time is a first period of time, and wherein the method further comprises:
upon the software component failing to receive the copy of the data unit from any of the plurality of storage nodes after a predetermined amount of time, the software component sending, in parallel to each of the plurality of storage nodes, an instruction to retrieve the copy of the data unit within a second specified period of time of greater length than the first period of time.