HashTag codes for reduced repair bandwidth

Patent metadata

Field	Value
Publication number	US-12393484-B2
Application number	US-202418417961-A
Country	US
Kind code	B2
Filing date	Jan 19, 2024
Priority date	Jan 19, 2024
Publication date	Aug 19, 2025
Grant date	Aug 19, 2025

Abstract

A system can determine to generate error correction codes for a storage system that comprises computing nodes. The system can logically divide the computing nodes into disjunctive subsets. The system can, for each disjunctive subset, create a partition, and identify a group of elements that comprises sub-strips of the disjunctive subset. The system can add a first element from each disjunctive subset of the disjunctive subsets to the partition, and removing the first element from the group of elements. The system can, for each disjunctive subset, add a second element from the group of elements along with elements stored in parity notes of a sub-strip where the second element is located. The system can, in response to determining that a number of elements of the disjunctive subset is at least as large as a number of the computing nodes, create the error correction codes based on the elements.

First claim

What is claimed is:

1. A system, comprising:
at least one processor; and
at least one memory that stores executable instructions that, when executed by the at least one processor, facilitate performance of operations, comprising:
determining to generate error correction codes for a storage system that comprises computing nodes;
logically dividing the computing nodes into disjunctive subsets;
for each disjunctive subset of the disjunctive subsets,
creating a partition, with an initial empty state, and
identifying a group of elements that comprises sub-strips of the disjunctive subset;

adding a first element from each disjunctive subset of the disjunctive subsets to the partition, and removing the first element from the group of elements;
for each disjunctive subset, adding a second element from the group of elements to the disjunctive subset along with elements stored in parity notes of a sub-strip where the second element is located;
in response to determining that a number of elements of the disjunctive subset is at least as large as a number of the computing nodes, creating the error correction codes based on the elements; and
storing the error correction codes on parity nodes of the computing nodes.

2. The system of claim 1 , wherein the operations further comprise:
determining that there is lost data that was stored on the computing nodes; and
recovering the lost data to the computing nodes based on the error correction codes.

3. The system of claim 1 , wherein the operations further comprise:
before the determining that the number of elements of the disjunctive subset is at least as large as the number of the computing nodes,
and in response to determining that the number of elements of the disjunctive subset less than the number of the computing nodes,
adding additional elements for parity nodes in the sub-strip where the second element is located.

4. The system of claim 3 , wherein the operations further comprise:
in response to the determining that the number of elements of the disjunctive subset less than the number of the computing nodes after adding the additional elements, performing an iteration of adding at least one element from each disjunctive subset to the partition, and removing the at least one element from the group of elements.

5. The system of claim 1 , wherein respective sub-strips of the sub-strips comprise respective contiguous sub-portions of respective storage devices of the computing nodes.

6. The system of claim 1 , wherein the computing nodes comprise a first group of systemic nodes, and a second group of parity nodes.

7. The system of claim 1 , wherein the operations further comprise:
before creating the error correction codes, determining that at least one disjunctive subset of the disjunctive subsets comprises a portion of elements that corresponds to a first ratio of a number of the sub-strips and a number of parity nodes of the computing nodes,
wherein the portion of elements comprises runs having at least a length that corresponds to a second ratio of the number of the sub-strips and a product of a number of the disjunctive subsets and the number of parity nodes, and
wherein a distance between indices of the portion of elements comprises a step that corresponds to a third ratio of the number of the sub-strips and the number of parity nodes minus a value of the length of the runs.

8. The system of claim 1 , wherein the operations further comprise:
before creating the error correction codes, determining that an amount of bandwidth associated with performing data recovery on the storage system using the disjunctive subsets satisfies a performance criterion.

9. The system of claim 1 , wherein the operations further comprise:
for the partition, maintaining a neighborhood matrix that identifies the sub-strips; and
while the number of elements in a disjunctive subset of the disjunctive subsets is less than a portion of elements that corresponds to a ratio of a number of the sub-strips and a number of parity nodes of the computing nodes, performing iterations of,
adding a least occurring sub-strip to the partition, and
updating the neighborhood matrix based on adding the least occurring sub-strip to the partition.

10. The system of claim 9 , wherein the neighborhood matrix identifies how many times respective sub-strips of the sub-strips have neighbored with other respective sub-strips of the sub-strips.

11. A method, comprising:
logically dividing, by a system comprising at least one processor, computing nodes of a storage system into disjunctive subsets;
for each disjunctive subset of the disjunctive subsets,
creating, by the system, a partition that is initially empty, and
identifying, by the system, a group of elements that comprises sub-strips of the disjunctive subset;

adding, by the system, a first element from each disjunctive subset of the disjunctive subsets to the partition, and removing the first element from the group of elements;
for each disjunctive subset, adding, by the system, a second element from the group of elements to the disjunctive subset along with elements stored in parity notes of a sub-strip where the second element is located;
in response to determining that a number of elements of the disjunctive subset is at least as large as a number of the computing nodes, creating, by the system, error correction codes based on the elements; and
storing, by the system, the error correction codes on the computing nodes.

12. The method of claim 11 , further comprising:
before the determining that the number of elements of the disjunctive subset is at least as large as the number of the computing nodes, and in response to determining that the number of elements of the disjunctive subset less than the number of the computing nodes, adding, by the system, additional elements for parity nodes in the sub-strip where the second element is located.

13. The method of claim 12 , further comprising:
in response to the determining that the number of elements of the disjunctive subset less than the number of the computing nodes after adding the additional elements, performing, by the system, an iteration of adding at least one element from each disjunctive subset to the partition, and removing the at least one element from the group of elements.

14. The method of claim 11 , further comprising:
before creating the error correction codes, determining, by the system, that at least one disjunctive subset of the disjunctive subsets comprises a portion of elements that corresponds to a ratio of a number of the sub-strips and a number of parity nodes of the computing nodes,
wherein the portion of elements comprises runs having at least a length that corresponds to a ratio of the number of the sub-strips and a product of a number of the disjunctive subsets and the number of parity nodes, and
wherein a distance between indices of the portion of elements comprises a step that corresponds to a ratio of the number of the sub-strips and the number of parity nodes minus a value of the length of the runs.

15. The method of claim 11 , further comprising:
before creating the error correction codes, determining, by the system, that an amount of bandwidth associated with performing data recovery on the storage system using the disjunctive subsets satisfies a performance criterion.

16. A non-transitory computer-readable medium comprising instructions that, in response to execution, cause a system comprising a processor to perform operations, comprising:
for each disjunctive subset of disjunctive subsets of computer nodes

Assignees

• Dell Products Lp

Inventors

• Armangau Philippe
• Kang Jamin Jianbin
• Zhuo Baote

Classifications

• G06F11/1435

  using file system or storage system metadata · CPC title

• G06F11/3409

  for performance assessment · CPC title

• G06F11/1004 Primary

  to protect a block of data words, e.g. CRC or checksum (G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00) · CPC title