US 10,242,020 B2 · Placement of data fragments generated by an erasure code in distributed computational devices based on a deduplication factor

Abstract

A file division and erasure code application executing in a controlling computational device generates data fragments and parity fragments of a file. Each of the generated data fragments and parity fragments are distributed in a different distributed computational device of a plurality of distributed computational devices, where distributing of a generated data fragment comprises determining whether any distributed computational device already stores a duplicate copy of the generated data fragment, and if any distributed computational device already stores the duplicate copy of the generated data fragment, placing the generated data fragment in the distributed computational device if no other data or parity fragment of the file has already been placed in the distributed computational device.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims18

Dependent claims

A method, comprising:

generating, via a file division and erasure code application executing in a controlling computational device, data fragments and parity fragments of a first file;
and
distributing each of the generated data fragments and parity fragments of the first file in a different distributed computational device of a plurality of distributed computational devices, wherein distributing of a generated data fragment of the first file comprises:
determining whether any distributed computational device already stores a duplicate copy of the generated data fragment of the first file, wherein the duplicate copy is a data fragment of a second file;
in response to determining that a distributed computational device already stores the duplicate copy that is a data fragment of the second file, then in response to the distributed computational device already storing another data fragment of the first file besides the generated data fragment of the first file, removing the already stored another data fragment of the first file from the distributed computational device for placement in another distributed computational device;
and
subsequent to removing the another data fragment of the first file from the distributed computational device, placing the generated data fragment of the first file in the distributed computational device in which the duplicate copy that is a data fragment of the second file is already stored.

4 more elements

A system comprising a controlling computational device, wherein the controlling computational device is coupled to a plurality of distributed computational devices, the system comprising:

a memory;
and
a processor coupled to the memory, wherein the processor performs operations, the operations comprising:
generating, via a file division and erasure code application executing in the controlling computational device, data fragments and parity fragments of a first file;
and
distributing each of the generated data fragments and parity fragments of the first file in a different distributed computational device of the plurality of distributed computational devices, wherein distributing of a generated data fragment of the first file comprises:
determining whether any distributed computational device already stores a duplicate copy of the generated data fragment of the first file, wherein the duplicate copy is a data fragment of a second file;
in response to determining that a distributed computational device already stores the duplicate copy that is a data fragment of the second file, then in response to the distributed computational device already storing another data fragment of the first file besides the generated data fragment of the first file, removing the already stored another data fragment of the first file from the distributed computational device for placement in another distributed computational device;
and
subsequent to removing the another data fragment of the first file from the distributed computational device, placing the generated data fragment of the first file in the distributed computational device in which the duplicate copy that is a data fragment of the second file is already stored.

7 more elements

A computer program product, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code configured to perform operations on a processor, the operations comprising:
generating, via a file division and erasure code application executing in a controlling computational device, data fragments and parity fragments of a first file;
and
distributing each of the generated data fragments and parity fragments of the first file in a different distributed computational device of a plurality of distributed computational devices, wherein distributing of a generated data fragment of the first file comprises:
determining whether any distributed computational device already stores a duplicate copy of the generated data fragment of the first file, wherein the duplicate copy is a data fragment of a second file;
in response to determining that a distributed computational device already stores the duplicate copy that is a data fragment of the second file, then in response to the distributed computational device already storing another data fragment of the first file besides the generated data fragment of the first file, removing the already stored another data fragment of the first file from the distributed computational device for placement in another distributed computational device;
and
subsequent to removing the another data fragment of the first file from the distributed computational device, placing the generated data fragment of the first file in the distributed computational device in which the duplicate copy that is a data fragment of the second file is already stored.

5 more elements

Dependencies are inferred from the claim text.

Description6,483 words

Summary865 words

#1. Field

#Embodiments relate to the placement of data fragments generated by an erasure code in distributed computational devices based on a duplication factor.

#2. Background

Brief description of the drawings9 figures

#Referring now to the drawings in which like reference numbers represent corresponding parts throughout:

#FIG. 1 illustrates a block diagram of a distributed computing environment comprising a controlling computational device and a plurality of distributed computational devices, in accordance with certain embodiments;

#FIG. 2 illustrates a block diagram that how data and parity fragments of a file are distributed among distributed computational devices, in accordance with certain embodiments;

Detailed description5,378 words

#In the following description, reference is made to the accompanying drawings which form a part hereof and which illustrate several embodiments. It is understood that other embodiments may be utilized and structural and operational changes may be made.

#Often there is redundancy in large data sets of “Big Data” and deduplicated data may be stored to reduce the amount of storage capacity needed. Additionally large data sets may have to be stored redundantly so that in case of failure of computational nodes, data recovery is possible.

#Certain embodiments provide a distributed data storage environment for large data sets, using erasure codes where deduplication is employed at each distributed computational devices where data fragments are stored. The erasure code provides redundancy by breaking objects up into smaller fragments and storing the fragments in different computational devices. The data is recoverable from combinations of a smaller number of those fragments when certain fragments have been lost. In certain embodiments, the computational node for storing a given file erasure code fragment is selected based on the already present data contents so as to facilitate deduplication.

Facts

Application

14/307,395Filed 17 Jun 2014

Published

US 2015/0363419 A117 Dec 2015

Granted

26 Mar 2019

Term ends

21 Dec 2036

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment, including 918 days of adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification2 codes

G06F 16/1748
Redundancy elimination performed by the file system: de-duplication implemented within the file system, e.g. based on file segments
G06F
Computing and data processing

Timeline

17 Jun 2014Application filedUS 14/307,395
18 Jun 2014Assigned to International Business Machines Corporationassignment of assignor's interest
17 Dec 2015PublishedUS 2015/0363419 A1
26 Mar 2019GrantedUS 10,242,020 B2
12 Oct 2026TodayWithin its term
21 Dec 2036Term endsEstimated, includes 918 days of adjustment

Placement of data fragments generated by an erasure code in distributed computational devices based on a deduplication factor

Life of this patent

Placement of data fragments generated by an erasure code in distributed computational devices based on a deduplication factor

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims18

Description6,483 words

Drawings

Classification2 codes

Life of this patent

Description6,483 words