US 2015/0178162 A1Published application

Method for Recovering Recordings in a Storage Device and System for Implementing Same

AssigneeRaidix Corporation

InventorsAlexey V. MAROV, Alexey Y. UTESHEV

Life of this patent

Estimating the term…

Loading patent…

Abstract

The memory of the storage device is divided into information areas of identical size selected from different parts of the storage device, and control zones are selected from different parts of the device. Each group of data is a set of code words written to a corresponding information zone. Three reference control sums S0, S1, S2, each according to a corresponding preset formula, are established by a computation unit. The reference control sums are written as a code word with the same number to a corresponding control zone. If a part of the storage device fails and data becomes corrupted, the current control sums are calculated with the aid of the computation unit. The values of the stored reference control sums and the current control sums are used for recovering lost data. The number of equations depends on the number of failed or faulty zones in the storage device.

Claims10

Dependent claims

A method of recovery of records in a storage device in case of failure or damage of a part of the storage device or data corruption of the storage device, the method comprising:

dividing an area of memory of the storage device into information zones of a same size selected from different parts of the storage device, and into control zones selected from different parts of the storage device;
recording each group of data to be stored in a form of a set of code words into the corresponding information zone;
finding three reference checksums S0, S1, S2 using a corresponding computing unit while writing the data into the storage device, every checksum being calculated by a corresponding predetermined formula:
S
~
0
=
∑
i
=
0
n
-
1

D
i
=
D
0
+
D
1
+
…
+
D
n
-
1
S
~
1
=

∑
i
=
0
n
-
1

D
i

a
n
-
i
-
1
=

D
0

a
n
-
1
+
D
1

a
n
-
2
+
…
+
D
n
-
1
=

(
(
(
D
0

a
+
D
1
)

a
+
D
2
)

a
+
…
+
D
n
-
1
)
S
~
2
=

∑
i
=
0
n
-
1

D
i

a
2

(
n
-
i
-
1
)
=

D
0

a
2

(
n
-
1
)
+
D
1

a
2

(
n
-
2
)
+
…
+
D
n
-
1
=

(
(
(
D
0

a
2
+
D
1
)

a
2
+
D
2
)

a
2
+
…
+
D
n
-
1
)
where Di is an i-information area wherein code words di,1, di,2, . . . , di,s-1;
i=0, . . . , n−1 are recorded, the code words being elements of the Galois field;
n is a number of the information zones;
s is a number of the code words in one information zone;
a is a primitive element of the Galois field;
writing each of the reference checksum in the form of the code words with the same number in the corresponding control zone, wherein each of the three checksums is stored in a separate zone of the storage device;
using the computing unit to calculate the current checksums by the predetermined formula for each set of code words with the same numbers in all information zones while using the storage device in case of failure or damage of a part of the storage device or data corruption;
and
using the reference and the current checksum to perform data recovery by solving systems of equations obtained from the formulas of calculating checksums, the number of equations in the system being dependent on the number of failed or damaged areas of the storage device.

201 more elements

A system of recovery of records in a storage device in case of failure or damage of a part of the storage device or data corruption of the storage device, the system comprising:

a memory device comprising n equal size information zones selected from different parts of the storage device and three control zones selected from different parts of the storage device, each of the n information zones of the storage device being adapted to write groups of data to be recorded as a set of code words, and each of the three control zones of the storage device being adapted to record a corresponding checksum;
and
a computing unit defining current checksums by formulas for each set of code words with the same numbers in all said n information zones in case of failure or damage of a part of memory of the storage device, values of stored reference checksums serving to recover lost data;
wherein the computing unit defines reference checksums by using a predetermined formula, for each set of code words, where i=0, . . . , n−1 in all said n information zones with every record of data in the storage device, and wherein S0, S1, S2 checksums are calculated according to the following formulas:
S
~
0
=
∑
i
=
0
n
-
1

D
i
=
D
0
+
D
1
+
…
+
D
n
-
1
S
~
1
=

∑
i
=
0
n
-
1

D
i

a
n
-
i
-
1
=

D
0

a
n
-
1
+
D
1

a
n
-
2
+
…
+
D
n
-
1
=

(
(
(
D
0

a
+
D
1
)

a
+
D
2
)

a
+
…
+
D
n
-
1
)
S
~
2
=

∑
i
=
0
n
-
1

D
i

a
2

(
n
-
i
-
1
)
=

D
0

a
2

(
n
-
1
)
+
D
1

a
2

(
n
-
2
)
+
…
+
D
n
-
1
=

(
(
(
D
0

a
2
+
D
1
)

a
2
+
D
2
)

a
2
+
…
+
D
n
-
1
)
where Di is an i-information area wherein code words di,1, di,2, . . . , di,s-1;
i=0, . . . , n−1 are recorded, the code words being elements of the Galois field;
n is a number of the information zones;
s is a number of the code words in one information zone;
a is a primitive element of the Galois field;
and wherein the lost data can be recovered using the reference and the current checksums by solving a system of equations obtained by the formula for calculating the checksums, the number of equations in the system depending on the number of failed or damaged areas of the storage device.

199 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/643,238Filed 10 Mar 2015
Priority: RU 201214067912 Sep 2012
Published: 25 Jun 2015
Term ends: Not estimatedThe source records don’t support an estimate.

Classification11 codes

G06F 11/1096
Parity data used in redundant arrays of independent storages, e.g. in RAID systems: parity calculation or recalculation after configuration or…
G06F 11/1004
Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's: to protect a block of data words, e.g. CRC or…
G06F 11/1068
In individual solid state devices: in sector programmable memories, e.g. flash disk
G06F 11/1076
Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's: parity data used in redundant arrays of…