EP4550148A1 - Verfahren und vorrichtung zur lokalen datenwiederherstellung und speichermedium - Google Patents

Verfahren und vorrichtung zur lokalen datenwiederherstellung und speichermedium Download PDF

Info

Publication number
EP4550148A1
EP4550148A1 EP23830152.7A EP23830152A EP4550148A1 EP 4550148 A1 EP4550148 A1 EP 4550148A1 EP 23830152 A EP23830152 A EP 23830152A EP 4550148 A1 EP4550148 A1 EP 4550148A1
Authority
EP
European Patent Office
Prior art keywords
data
matrix
blocks
block
rows
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
EP23830152.7A
Other languages
English (en)
French (fr)
Other versions
EP4550148A4 (de
Inventor
Liang Chen
Shuzhan WEI
Junqing GU
Yafei ZHAO
Yuanyuan Dong
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Cloud Intelligence Singapore Holding Pvt Ltd
Original Assignee
Cloud Intelligence Singapore Holding Pvt Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Cloud Intelligence Singapore Holding Pvt Ltd filed Critical Cloud Intelligence Singapore Holding Pvt Ltd
Publication of EP4550148A1 publication Critical patent/EP4550148A1/de
Publication of EP4550148A4 publication Critical patent/EP4550148A4/de
Pending legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1008—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices
    • G06F11/1048—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices using arrangements adapted for a specific error detection or correction feature
    • G06F11/1056—Updating check bits on partial write, i.e. read/modify/write
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/14—Error detection or correction of the data by redundancy in operations
    • G06F11/1479—Generic software techniques for error detection or fault masking
    • G06F11/1489—Generic software techniques for error detection or fault masking using recovery blocks
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1076—Parity data used in redundant arrays of independent storages, e.g. in RAID systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/14—Error detection or correction of the data by redundancy in operations
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2201/00—Indexing scheme relating to error detection, to error correction, and to monitoring
    • G06F2201/84—Using snapshots, i.e. a logical point-in-time copy of the data

Definitions

  • the present application relates to the field of computer technologies and, in particular, to a data local recovery method, a device, and a storage medium.
  • Erasure code is an encoding fault tolerance technology, and is used to recover original data when some data is lost.
  • the erasure code can occupy less storage space while ensuring reliability, and is thus widely applied to distributed storage systems. Compared to traditional replication-type data recovery methods, the erasure code has a problem of read amplification during data reconstruction.
  • LRC Local Self-recovery erasure code
  • Various aspects of the present application provide a data local recovery method, a device, and a storage medium, which are used for performing local recovery on a global parity block, and improving the fault tolerance capability of the data local recovery method.
  • An embodiment of the present application further provides a data local recovery method, including: determining multiple data groups included in a data set, where object blocks in any data group include: a data block, a global parity block and a local parity block; in response to a recovery request for any target object block in the data group, recovering the target object block according to remaining readable object blocks in the data group; where in the data group, the global parity block and the local parity block are obtained by encoding the data block, the local parity block includes encoding information of the global parity block, and a sum of local parity blocks in the data set is linearly independent of global parity blocks in the data set.
  • the method further includes: in response to a recovery request for a first number of object blocks in the data set, recovering the first number of object blocks according to remaining readable object blocks in the data set; where the first number is greater than a number of the global parity blocks in the data set.
  • the method before responding to the recovery request for any target object block in the data group, according to the remaining readable object blocks in the data group, the method further includes: determining a first matrix of r+1 dimensions, where r is a positive integer; correspondingly generating r derived rows according to any r data rows in the first matrix, where the r derived rows are used for encoding to obtain r local parity blocks, and any derived row includes elements in a data row used to generate the derived row; replacing a data row other than the any r data rows in the first matrix with the r derived rows to obtain a second matrix; connecting an identity matrix behind the second matrix to obtain an encoding matrix; encoding data blocks in the data set by using the encoding matrix to obtain the global parity blocks and the local parity blocks corresponding to the multiple data groups.
  • any r+1 columns are a column full rank matrix.
  • the first matrix is a Cauchy matrix.
  • correspondingly generating the r derived rows according to any r data rows in the first matrix includes: adding, according to a correspondence between elements of different columns in the r data rows and the data groups during matrix calculation, additional items to the elements of different columns in the r data rows to obtain the r derived rows; where in a same derived row, the additional items are added to elements of columns corresponding to any one data group, and in different derived rows, data groups corresponding to elements to which the additional items are added are different.
  • a result of summation of elements in the r derived rows is equal to a result of summation of elements in a (r+1) th row in the first matrix, where the summation includes an exclusive OR operation of elements.
  • LRC Local Self-recovery erasure code
  • global parity blocks P are obtained by operation on all data blocks D
  • local parity blocks L are obtained by operation on data blocks within groups.
  • the local parity block L can be recovered in a local manner.
  • the global parity block has no local recovery property, that is, all data blocks D need to be read to recover the global parity block P.
  • global parity blocks P are obtained by operation on all data blocks D
  • local parity blocks L are obtained by operation on data blocks within groups.
  • a sum of all local parity blocks is required to be consistent with a sum of all global parity blocks, in terms of results.
  • this approach sacrifices the fault tolerance capability of LRC. That is, only any r blocks may be tolerated to be lost. In other words, when the number of lost blocks is less than or equal to r, the lost blocks can be recovered, where r is the number of global parity blocks, and r is a positive integer.
  • FIG. 1 is a schematic flowchart of a data local recovery method provided by an exemplary embodiment of the present application, and the method may include the steps shown in FIG. 1 .
  • Step 101 determining multiple data groups included in a data set, where object blocks in any data group include: a data block, a global parity block and a local parity block, where in the data group, the global parity block and the local parity block are obtained by encoding the data block, the local parity block includes encoding information of the global parity block.
  • Step 102 in response to a recovery request for any target object block in the data group, recovering the target object block according to remaining readable object blocks in the data group, where a sum of local parity blocks in the data set is linearly independent of global parity blocks in the data set.
  • An executive entity of this embodiment may be a server storing data, and the server may be a conventional server, a cloud server, an elastic computing instance on a cloud, or a virtualized data center, etc., which is not limited in this embodiment.
  • the server runs a data storage application that is configured to store and manage received data.
  • the data storage application on the server can perform local repair on lost data based on erasure code, so as to reduce the cost required for data repair.
  • the data set includes multiple data groups, used to perform local calculation during data failure recovery.
  • the number of data blocks included in each data group may be obtained by dividing according to requirements, which is not limited in this embodiment.
  • Each data group may include multiple object blocks, and the multiple object blocks may include the data block(s), the global parity block(s), and the local parity block(s) (local repair parity).
  • Any target object block to be recovered may be any one of a data block, a global parity block, or a local parity block.
  • the lost object block can be recovered through remaining data blocks.
  • the global parity block is obtained by encoding all data blocks (i.e. global data blocks) in the data set, and can be used to recover any global data block when the global data block is lost. That is, for any data group, when any data block in the data group is lost, local recovery may be implemented for the lost data block through the global data block in the data group.
  • the local parity block in any data group is obtained by encoding according to the data block in the data group.
  • the local parity block includes the encoding information of the global parity block.
  • the global parity block may be recovered through the data block and the local parity block in the data group where the global parity block is located.
  • the multiple data groups may correspond to multiple global parity blocks, and the sum of multiple local parity blocks is linearly independent of the global parity blocks in the data set. That is, the sum of the multiple local parity blocks may be regarded as a new global parity block, and the new global parity block is linearly independent of the original global parity blocks in the data set. Therefore, when there are originally r global parity blocks in the data set, the sum of the multiple local parity blocks may be used as the (r+1) th global parity block, so that when any r+1 object blocks in the data set are lost, remaining object blocks can be used to perform data recovery on the r+1 object blocks.
  • the server may, in response to a recovery request for a first number of object blocks in the data set, recover the first number of object blocks according to remaining readable object blocks in the data set, where the first number is greater than the number of the global parity blocks in the data set.
  • the first number is the number of the global parity blocks plus one. That is, when there are r global parity blocks in the data set, it can be tolerated that when any r+1 object blocks in the data set are lost, data recovery on the r+1 object blocks is performed by using remaining object blocks.
  • the target object block when the recovery request for any target object block in any data group in the data set exists, the target object block can be recovered according to the remaining readable object blocks in the data group.
  • the any target object block may be the data block, the global parity block or the local parity block in the data group.
  • the global parity block and the local parity block are obtained by encoding the data block, and when any data block within the data group is lost, the data block can be recovered according to the remaining data blocks, the global parity block, and the local parity block.
  • the local parity block includes the encoding information of the global parity block, and when the global parity block is lost, the global parity block can be recovered according to the data block and the local parity block.
  • the local parity block When the local parity block is lost, the local parity block can be recovered according to the data block within the data group. Thus, local recovery for any object block within the data group is achieved.
  • the sum of the local parity blocks in the data set is linearly independent of the global parity blocks in the data set, so the lost object blocks can be recovered when the number of the lost object blocks in the data set is greater than the number of the global parity blocks.
  • the fault tolerance capability of the data local recovery method can be improved.
  • the server may generate the global parity blocks and the local parity blocks based on a principle of erasure code.
  • the global parity blocks and the local parity blocks are obtained by encoding the data blocks in the data set through an encoding matrix. An optional generation manner of the encoding matrix will be described below.
  • the server may determine a first matrix of r+1 dimensions, where the number of rows in the first matrix is r+1 and the number of columns is k.
  • the encoding matrix may be constructed according to the first matrix, where the encoding matrix is used to describe, in the form of a matrix, a process of obtaining parity blocks by encoding.
  • r derived rows may be generated correspondingly according to any r data rows in the first matrix, where the r derived rows are used for encoding to obtain r local parity blocks, and any derived row includes elements in a data row used to generate the derived row, so that the local parity block obtained by encoding includes the encoding information of the global parity block.
  • a data row other than the any r data rows in the first matrix may be replaced with the r derived rows to obtain a second matrix.
  • first and second are used to define the described matrices, which is merely used for ease of description and distinction, and does not constitute any other limitations on the matrices.
  • an identity matrix may be connected behind the second matrix to obtain the encoding matrix. All elements on a diagonal (referred to as a main diagonal) from an upper left corner to a lower right corner of the identity matrix are 1, all other elements are 0, and the identity matrix is a full rank matrix.
  • an element of 1 in the identity matrix is used to represent a parity block to be encoded.
  • an element of 1 in the same row as an original data row in the first matrix is used to calculate the global parity block
  • an element of 1 in the same row as a derived data row is used to calculate the local parity block.
  • the data blocks in the data set may be encoded by using the encoding matrix to obtain the global parity blocks and the local parity blocks corresponding to the multiple data groups, which will be described in detail below.
  • the first matrix may be implemented as a Cauchy matrix (Cauchy matrix), and when an identity matrix of r*r dimensions is connected behind a Cauchy matrix of r*g dimensions, it may enable that a matrix formed by any r+1 columns is a column full rank matrix.
  • a Cauchy matrix (Cauchy matrix)
  • any r data rows may be used to calculate r global parity blocks, and the remaining 1 data row may be used to calculate respective local parity blocks of g data groups.
  • r derived rows can be generated according to the remaining 1 data row, and the r derived rows correspond to the g data groups. Based on the r data rows and the r derived rows, an adjusted second matrix may be obtained.
  • additional items may be added to the elements of different columns in the r data rows to obtain the r derived rows.
  • the additional items are added to elements of columns corresponding to any one data group, and in different derived rows, data groups corresponding to elements to which the additional items are added are different.
  • the additional items need to make the sum of the elements in the r derived rows the same as the sum of the remaining 1 data row.
  • elements corresponding to a data group g1 may be locally adjusted to obtain a derived data row corresponding to the data group g1.
  • elements corresponding to a data group g2 in another data row may be locally adjusted to obtain a derived data row corresponding to the data group g2.
  • the r derived data rows are used to calculate the respective local parity blocks corresponding to the g data groups, respectively, to obtain the r local parity blocks.
  • the first to the r th rows in the first matrix are used to calculate the r global parity blocks, and the (r+1) th row is used to calculate the r local parity blocks.
  • the additional items may be added on the basis of each row in the first matrix, so as to obtain the r derived rows.
  • the additional items may be added to elements, corresponding to the first data group, in the first row of the first matrix, and the other elements remain unchanged, to obtain the second row of the second matrix.
  • the second row may be used to encode a local parity block corresponding to the first data group.
  • the additional items may be added to elements, corresponding to the second data group, in the second row of the first matrix, and the other elements remain unchanged, to obtain the fourth row of the second matrix.
  • the fourth row may be used to encode a local parity block corresponding to the second data group.
  • the additional items may be added to elements, corresponding to the g th data group, in the (2r-1) th row of the first matrix, and the other elements remain unchanged, to obtain the (2r) th row of the second matrix.
  • the (2r) th row may be used to encode a local parity block corresponding to the g th data group.
  • a first matrix of (r+1) *k dimensions is determined as: a ij : 1 ⁇ i ⁇ r + 1 , 1 ⁇ j ⁇ k r + 1 ⁇ k , which is expanded to: a 1 , 1 . . a 1 , g a 2 , 1 . . a 2 , g a 3 , 1 . . a 3 , g . . . . a r + 1 , 1 . . a r + 1 , g a 1 , g + 1 . . a 1 , 2 g . . a 1 , r ⁇ 1 g + 1 . . .
  • the first to the r th rows in the first matrix may be used for encoding to generate r global parity blocks, and the (r+1) th row may be used for encoding to generate r local parity blocks.
  • a second matrix of 2r*k dimensions may be generated.
  • the second matrix includes the first to the r th rows in the first matrix and the r derived rows, where the derived rows are distributed in the second row, the fourth row..., and the (2r) th row of the second matrix.
  • an identity matrix of 2r*k may be added behind the second matrix to obtain an encoding matrix H, and any r+1 columns in the encoding matrix H are a row full rank matrix.
  • H a 1 , 1 . .
  • d j is an additional item used to locally adjust the first to the r th rows in the first matrix to obtain the r derived rows.
  • d 1 ⁇ d g are added to elements, corresponding to the first data group, in the first row of the first matrix.
  • d g +1 ⁇ d 2 g are added to elements, corresponding to the second data group, in the second row of the first matrix.
  • d ( r -1) g +1 ⁇ d r g are added to elements, corresponding to the g th data group, in the r th row of the first matrix. That is, it is satisfied that in the same derived row, the additional items are added to elements corresponding to any one data group, and in different derived rows, data groups corresponding to elements to which the additional items are added are different.
  • a summation operation may be designed as an exclusive OR operation, and according to elements of the same column in the r data rows, an additional item corresponding to this column is calculated.
  • an additional item of the element of the j th column in the i th data row may be determined according to elements of the j th column in r+1 rows of the first matrix.
  • the additional item is added to the element of the j th column in the i th data row to obtain a derived row corresponding to the i th data row.
  • Corresponding additional items are added to elements corresponding to different data groups in the first matrix to generate the r derived rows corresponding to the local parity blocks.
  • this result of summation is equal to the result of summation of the elements in the (r+1) th row in the first matrix. Therefore, the sum of the local parity blocks calculated by the r derived rows has a linearly independent relationship with the r global parity blocks.
  • the sum of the local parity blocks encoded by the r derived rows may be regarded as a new global parity block.
  • the new global parity block is linearly independent of the r global parity blocks, and thus the loss of any r+1 data blocks can be tolerated.
  • P 1 , P 2 , P 3 ..., P r may be determined and used as global parity blocks.
  • L 1 , L 2 , L 3 ..., L r correspond to the derived rows, and may be used as local parity blocks.
  • the lost data block may be recovered according to remaining data blocks.
  • High reliability means that, an encoding result can satisfy that when any r+1 blocks are lost, data can be recovered.
  • High performance means that, when any single block in a group is lost, recovery can be performed through local data blocks, thereby reducing read amplification in a data recovery process.
  • Parameter flexibility means that, it can be satisfied that the number of data blocks is divisible by the number of global parity blocks, and when the number of data blocks changes, an accurate encoding matrix structure can be provided, thereby satisfying the encoding requirements in multiple situations.
  • a data set includes data blocks D 1 , D 2 , D 3 and D 4 .
  • the data set is grouped to obtain a data group G 1 including D 1 and D 2 , and a data group G 2 including D 3 and D 4 .
  • a first matrix is determined as: a 11 a 12 a 13 a 14 a 21 a 22 a 23 a 24 a 31 a 32 a 33 a 34 .
  • a second matrix is constructed by using the first matrix and a calculation result from Formula 1, and an identity matrix is connected behind the second matrix to obtain an encoding matrix: a 1 , 1 a 1 , 2 a 1 , 3 a 1 , 4 a 1 , 1 + d 1 a 1 , 2 + d 2 a 1 , 3 a 1 , 4 a 2,1 a 2 , 2 a 2 , 3 a 2 , 4 a 2 , 1 a 2 , 2 a 2 , 3 + d 3 a 2 , 4 + d 4 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 .
  • the sum of the second row and the third row in the second matrix is equal to a sum of the third row in the first matrix, so that any three columns in the encoding matrix satisfy linear independence characteristics.
  • the global parity blocks and the local parity blocks can be obtained by performing matrix operation on the data blocks D 1 , D 2 , D 3 and D4 and the encoding matrix mentioned above.
  • data recovery may be performed through the other three data blocks within the group. For example, when D 1 is lost, D 1 can be recovered through D 2 , L 1 and P 1 .
  • An addition of the local parity blocks L 1 and L 2 may be regarded as a new global parity block P 3 .
  • P 1 , P 2 , P 3 are linearly independent of each other due to a linear independent relationship between the sum of L 1 and L 2 and P 1 , P 2 . Therefore, when any three data blocks in D 1 , D 2 , D 3 , D 4 , P 1 , P 2 , L 1 , L 2 are lost, the lost data blocks may be recovered according to remaining data blocks.
  • a data set includes data blocks D 1 , D 2 , D 3 , D 4 , D 5 , D 6 , D 7 , D 8 , D 9 .
  • the data set is grouped to obtain a data group G 1 including D 1 , D 2 and D 3 , a data group G 2 including D 4 , D 5 and D 6 , and a data group G 3 including D 7 , D 8 and D 9 .
  • a first matrix is determined as: a 1 , 1 a 1 , 2 a 1 , 3 a 1 , 4 a 1 , 5 a 1 , 6 a 1 , 7 a 1 , 8 a 1 , 9 a 2 , 1 a 2 , 2 a 2 , 3 a 2 , 4 a 2 , 5 a 2 , 6 a 2 , 7 a 2 , 8 a 2 , 9 a 3 , 1 a 3 , 2 a 3 , 3 a 3 , 4 a 3 , 5 a 3 , 6 a 3 , 7 a 3 , 8 a 3 , 9 a 4 , 1 a 4 , 2 a 4 , 3 a 4 , 4 a 4 , 5 a 4 , 6 a 3 , 7 a 3 , 8 a 3 , 9 a 4 , 1 a 4 , 2 a 4 , 3 a 4 , 4 a 4 , 5
  • a second matrix is constructed by using the first matrix and a calculation result from Formula 1, and an identity matrix is connected behind the second matrix to obtain an encoding matrix: a 1 , 1 a 1 , 2 a 1 , 3 a 1 , 4 a 1 , 5 a 1 , 6 a 1 , 7 a 1 , 8 a 1 , 9 a 1 , 1 + d 1 a 1 , 2 + d 2 a 1 , 3 + d 3 a 1 , 4 a 1 , 5 a 1 , 6 a 1 , 7 a 1 , 8 a 1 , 9 a 2 , 1 a 2 , 2 a 2 , 3 a 2 , 4 a 2 , 5 a 2 , 6 a 2 , 7 a 2 , 8 a 2 , 9 a 2 , 1 a 2 , 2 a 2 , 3 a 2 , 4 + a 2 , 5 a 2 , 6 a 2 , 7
  • h 2 + h 4 + h 6 a 4 , 1 + a 4 , 2 + a 4 , 3 + a 4 , 4 + a 4 , 4 .
  • the sum of the second row, the fourth row and the sixth row in the second matrix is equal to a sum of the third row in the first matrix, so that any three columns in the encoding matrix satisfy linear independence characteristics.
  • the global parity blocks and the local parity blocks can be obtained by performing matrix operation on the data blocks D 1 , D 2 , D 3 , D 4 , D 5 , D 6 , D 7 , D 8 , D 9 and the encoding matrix mentioned above.
  • data recovery may be performed through the other four data blocks within the group. For example, when D 1 is lost, D 1 can be recovered through D 2 , D 3 , L 1 and P 1 .
  • An addition of the local parity blocks L 1 , L 2 , L 3 may be regarded as a new global parity block P 4 .
  • P 1 , P 2 , P 3 , P 4 are linearly independent of each other due to a linear independent relationship between the sum of L 1 , L 2 , L 3 and P 1 , P 2 , P 3 . Therefore, when any four data blocks in D 1 , D 2 , D 3 , D 4 , D 5 , D 6 , D 7 , D 8 , D 9 , P 1 , P 2 , P 3 , L 1 , L 2 , L 3 are lost, the lost data blocks may be recovered according to remaining data blocks.
  • executive entities of steps of the methods provided in the above embodiments may be the same device, or the methods may also be executed by different devices.
  • an executive entity of steps 101 to 104 may be device A.
  • an executive entity of steps 101 and 102 may be device A, and an executive entity of step 103 may be device B, etc.
  • FIG. 5 illustrates a schematic structural diagram of a server provided by an exemplary embodiment of the present application, the server is applicable to the information processing system provided in the aforementioned embodiments.
  • the server includes: a memory 501, a processor 502, and a communication component 503.
  • the memory 501 is configured to store a computer program and may be configured to store various other data to support operations on the server. Examples of such data include instructions for any application program or method operating on the server.
  • the processor 502 is coupled to the memory 501, and is configured to execute the computer program in the memory 501, so as to: determine multiple data groups included in a data set, where object blocks in any data group include: a data block, a global parity block and a local parity block; in response to a recovery request for any target object block in the data group, recover the target object block according to remaining readable object blocks in the data group; where in the data group, the global parity block and the local parity block are obtained by encoding the data block, the local parity block includes encoding information of the global parity block, and a sum of local parity blocks in the data set is linearly independent of global parity blocks in the data set.
  • the processor 502 is further configured to: in response to a recovery request for a first number of object blocks in the data set, recover the first number of object blocks according to remaining readable object blocks in the data set; where the first number is greater than a number of the global parity blocks in the data set.
  • the processor 502 before responding to the recovery request for any target object block in the data group, according to the remaining readable object blocks in the data group, the processor 502 is further configured to: determine a first matrix of r+1 dimensions, where r is a positive integer; correspondingly generate r derived rows according to any r data rows in the first matrix, where the r derived rows are used for encoding to obtain r local parity blocks, and any derived row includes elements in a data row used to generate the derived row; replace a data row other than the any r data rows in the first matrix with the r derived rows to obtain a second matrix; connect an identity matrix behind the second matrix to obtain an encoding matrix; encode data blocks in the data set by using the encoding matrix to obtain the global parity blocks and the local parity blocks corresponding to the multiple data groups.
  • any r+1 columns are a column full rank matrix.
  • the first matrix is a Cauchy matrix.
  • the processor 502 when correspondingly generating the r derived rows according to any r data rows in the first matrix, is specifically configured to: add, according to a correspondence between elements of different columns in the r data rows and the data groups during matrix calculation, additional items to the elements of different columns in the r data rows to obtain the r derived rows; where in a same derived row, the additional items are added to elements of columns corresponding to any one data group, and in different derived rows, data groups corresponding to elements to which the additional items are added are different.
  • the processor 502 when adding, according to the correspondence between the elements of different columns in the r data rows and the data groups during matrix calculation, the additional items to the elements of different columns in the r data rows, the processor 502 is specifically configured to: for an element of a j th column in an i th data row of the r data rows, determine an additional item of the element of the j th column in the i th data row according to elements of a j th column in r+1 rows of the first matrix; add the additional item to the element of the j th column in the i th data row to obtain a derived row corresponding to the i th data row, where i and j are positive integers.
  • a result of summation of elements in the r derived rows is equal to a result of summation of elements in a (r+1) th row in the first matrix, where the summation includes an exclusive OR operation of elements.
  • the server further includes other components such as a power supply component 504.
  • FIG. 5 only schematically shows some components, which does not mean that the server includes only the components shown in FIG. 5 .
  • the memory 501 may be implemented by any type of volatile or non-volatile storage devices or a combination thereof, such as a static random access memory (SRAM), an electrically erasable programmable read-only memory (EEPROM), an erasable programmable read-only memory (EPROM), a programmable read-only memory (PROM), a read-only memory (ROM), a magnetic storage, a flash memory, a magnetic disk or an optical disk.
  • SRAM static random access memory
  • EEPROM electrically erasable programmable read-only memory
  • EPROM erasable programmable read-only memory
  • PROM programmable read-only memory
  • ROM read-only memory
  • magnetic storage a magnetic storage
  • flash memory a magnetic disk or an optical disk.
  • the communication component 503 is configured to facilitate wired or wireless communication between a device where the communication component is located and other devices.
  • the device where the communication component is located may access a wireless network based on a communication standard, such as WiFi, 2G, 3G, 4G, or 5G, or a combination thereof.
  • the communication component receives a broadcast signal or broadcast related information from an external broadcast management system via a broadcast channel.
  • the communication component may be implemented based on near field communication (NFC) technology, radio frequency identification (RFID) technology, infrared data association (IrDA) technology, ultra wideband (UWB) technology, Bluetooth (BT) technology, and other technologies.
  • NFC near field communication
  • RFID radio frequency identification
  • IrDA infrared data association
  • UWB ultra wideband
  • Bluetooth Bluetooth
  • the power supply component 504 is configured to supply power to various components of a device where the power supply component is located.
  • the power supply component may include a power management system, one or more power supplies, and other components associated with generating, managing, and distributing power for the device where the power supply component is located.
  • the target object block when the recovery request for any target object block in any data group in the data set exists, the target object block can be recovered according to the remaining readable object blocks in the data group.
  • the any target object block may be the data block, the global parity block or the local parity block in the data group.
  • the global parity block and the local parity block are obtained by encoding the data block, and when any data block within the data group is lost, the data block can be recovered according to the remaining data blocks, the global parity block, and the local parity block.
  • the local parity block includes the encoding information of the global parity block, and when the global parity block is lost, the global parity block can be recovered according to the data block and the local parity block.
  • the local parity block When the local parity block is lost, the local parity block can be recovered according to the data block within the data group. Thus, local recovery for any object block within the data group is achieved.
  • the sum of the local parity blocks in the data set is linearly independent of the global parity blocks in the data set, so the lost object blocks can be recovered when the number of the lost object blocks in the data set is greater than the number of the global parity blocks.
  • the fault tolerance capability of the data local recovery method can be improved.
  • an embodiment of the present application further provides a computer-readable storage medium storing a computer program, and when the computer program is executed, steps that can be performed by the server in the above method embodiments can be implemented.
  • embodiments of the present invention may be provided as a method, a system, or a computer program product. Therefore, the present invention may take a form of an embodiment entirely in hardware, an embodiment entirely in software, or an embodiment combining software and hardware aspects. Moreover, the present invention may take a form of a computer program product implemented on one or more computer usable storage media (including but not limited to a disk memory, a CD-ROM, an optical memory, etc.) including computer usable program code.
  • computer usable storage media including but not limited to a disk memory, a CD-ROM, an optical memory, etc.
  • each flow and/or block in the flowcharts and/or block diagrams, and combinations of flows and/or blocks in the flowcharts and/or block diagrams may be implemented by computer program instructions.
  • These computer program instructions may be provided to a processor of a general-purpose computer, a special-purpose computer, an embedded processor, or other programmable data processing devices to generate a machine, so that the instructions executed by the processor of the computer or the other programmable data processing devices generate an apparatus for implementing functions specified in one or more flows of the flowcharts and/or one or more blocks of the block diagrams.
  • These computer program instructions may also be stored in a computer-readable memory that can guide the computer or the other programmable data processing devices to work in a specific manner, so that the instructions stored in the computer-readable memory generate a manufactured product including an instruction apparatus, and the instruction apparatus implements functions specified in one or more flows of the flowcharts and/or one or more blocks of the block diagrams.
  • These computer program instructions may also be loaded onto the computer or the other programmable data processing devices, so that a series of operation steps are executed on the computer or the other programmable devices to generate computer-implemented processing, and thus the instructions executed on the processor of the computer or the other programmable devices provide steps for implementing functions specified in one or more flows of the flowcharts and/or one or more blocks of the block diagrams.
  • a computing device includes one or more processors (CPUs), an input/output interface, a network interface, and a memory.
  • the memory may include forms such as a non-permanent memory, a random access memory (RAM), and/or a non-volatile memory, such as read-only memory (ROM) or a flash memory (flash RAM), in computer-readable media.
  • RAM random access memory
  • ROM read-only memory
  • flash RAM flash memory
  • the memory is an example of a computer-readable medium.
  • the computer-readable media may implement information storage by any method or technology.
  • Information may be computer-readable instructions, data structures, modules of programs, or other data.
  • Examples of storage media for computers include, but are not limited to, a phase change memory (PRAM), a static random access memory (SRAM), a dynamic random access memory (DRAM), other types of random access memory (RAM), a read-only memory (ROM), an electrically erasable programmable read-only memory (EEPROM), a flash memory or other memory technologies, a read-only compact disk read-only memory (CD-ROM), a digital versatile disk (DVD) or other optical storage, a magnetic cartridge, a magnetic disk storage or other magnetic storage devices, or any other non-transmission medium that may be used to store information that can be accessed by computing devices.
  • the computer-readable media do not include transitory computer-readable media (transitory media), such as modulated data signals and carriers.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Quality & Reliability (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Error Detection And Correction (AREA)
  • Techniques For Improving Reliability Of Storages (AREA)
EP23830152.7A 2022-06-29 2023-06-25 Verfahren und vorrichtung zur lokalen datenwiederherstellung und speichermedium Pending EP4550148A4 (de)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN202210764325.1A CN115098295A (zh) 2022-06-29 2022-06-29 数据局部恢复方法、设备及存储介质
PCT/CN2023/102218 WO2024001974A1 (zh) 2022-06-29 2023-06-25 数据局部恢复方法、设备及存储介质

Publications (2)

Publication Number Publication Date
EP4550148A1 true EP4550148A1 (de) 2025-05-07
EP4550148A4 EP4550148A4 (de) 2025-11-12

Family

ID=83295604

Family Applications (1)

Application Number Title Priority Date Filing Date
EP23830152.7A Pending EP4550148A4 (de) 2022-06-29 2023-06-25 Verfahren und vorrichtung zur lokalen datenwiederherstellung und speichermedium

Country Status (4)

Country Link
US (1) US20250217238A1 (de)
EP (1) EP4550148A4 (de)
CN (1) CN115098295A (de)
WO (1) WO2024001974A1 (de)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN115098295A (zh) * 2022-06-29 2022-09-23 阿里巴巴（中国）有限公司 数据局部恢复方法、设备及存储介质
CN115642987B (zh) * 2022-10-13 2025-05-13 上海哔哩哔哩科技有限公司 编码方法、装置、计算设备及计算机存储介质
CN115454712B (zh) * 2022-11-11 2023-02-28 苏州浪潮智能科技有限公司 一种校验码恢复方法、系统、电子设备及存储介质
CN120406856B (zh) * 2025-07-01 2025-10-28 山东云海国创云计算装备产业创新中心有限公司 一种数据处理方法、装置、存储介质及电子设备

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10187083B2 (en) * 2015-06-26 2019-01-22 Microsoft Technology Licensing, Llc Flexible erasure coding with enhanced local protection group structures
US10545826B2 (en) * 2017-05-25 2020-01-28 Scality, S.A. Layered error correction encoding for large scale distributed object storage system
KR102109015B1 (ko) * 2018-10-23 2020-05-11 네이버 주식회사 부분 접속 복구가 가능하고 중복 인코딩이 용이한 데이터 저장 방법 및 시스템
CN111240597B (zh) * 2020-01-15 2024-05-17 书生星际(北京)科技有限公司 存储数据的方法、装置、设备和计算机可读存储介质
CN113296695A (zh) * 2021-02-08 2021-08-24 阿里巴巴集团控股有限公司 多az环境下纠删码数据的写入方法以及装置
CN113687975B (zh) * 2021-07-14 2023-08-29 重庆大学 数据处理方法、装置、设备及存储介质
CN114048061B (zh) * 2021-10-09 2026-01-02 阿里云计算有限公司 校验块的生成方法及装置
CN114385409B (zh) * 2021-12-21 2026-02-27 阿里巴巴（中国）有限公司 基于纠删码的编码方法、分布式系统、设备及存储介质
CN115098295A (zh) * 2022-06-29 2022-09-23 阿里巴巴（中国）有限公司 数据局部恢复方法、设备及存储介质

Also Published As

Publication number Publication date
EP4550148A4 (de) 2025-11-12
CN115098295A (zh) 2022-09-23
WO2024001974A1 (zh) 2024-01-04
US20250217238A1 (en) 2025-07-03

Similar Documents

Publication Publication Date Title
EP4550148A1 (de) Verfahren und vorrichtung zur lokalen datenwiederherstellung und speichermedium
Rashmi et al. A piggybacking design framework for read-and download-efficient distributed storage codes
US9141679B2 (en) Cloud data storage using redundant encoding
Cui et al. Balanced reliability systems under Markov processes
US12566666B2 (en) Encoding method based on erasure code, and distributed system, device and storage medium
US20190205212A1 (en) Method and apparatus for storing data and method and apparatus for recovering data
US12524299B2 (en) Parity block generation method and apparatus
US20200026426A1 (en) Method, apparatus and computer program product for managing storage system
US20210273654A1 (en) Erasure code calculation method
US20190114213A1 (en) Streaming data distributed processing method and device
AU2019101559A4 (en) Method and apparatus for generating random character string
US9600559B2 (en) Data processing for database aggregation operation
US12222807B2 (en) Check data generation method and apparatus, device, and storage medium
US11249846B2 (en) Erasure code-based data processing method and apparatus
Ma et al. Optimal binary linear locally repairable codes with disjoint repair groups
Xing et al. Construction of optimal (r, δ)-locally recoverable codes and connection with graph theory
US20240143495A1 (en) Method and apparatus for updating raid 5 check value, and medium
US20160285476A1 (en) Method for encoding and decoding of data based on binary reed-solomon codes
Kong et al. New bounds on the field size for maximally recoverable codes instantiating grid-like topologies
CN106649210B (zh) 一种数据转换方法及装置
US11888973B2 (en) Secure joining system, method, secure computing apparatus and program
CN104765775A (zh) 一种日志保存方法及装置
US20210124490A1 (en) Method, device, and computer program product for managing storage system
Yuan et al. Generalized piggybacking codes for distributed storage systems
CN109697234B (zh) 实体的多属性信息查询方法、装置、服务器和介质

Legal Events

Date Code Title Description
STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE INTERNATIONAL PUBLICATION HAS BEEN MADE

PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: REQUEST FOR EXAMINATION WAS MADE

17P Request for examination filed

Effective date: 20250117

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): AL AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HR HU IE IS IT LI LT LU LV MC ME MK MT NL NO PL PT RO RS SE SI SK SM TR

DAV Request for validation of the european patent (deleted)
DAX Request for extension of the european patent (deleted)
A4 Supplementary search report drawn up and despatched

Effective date: 20251010

RIC1 Information provided on ipc code assigned before grant

Ipc: G06F 11/10 20060101AFI20251006BHEP