Method and system for detecting and correcting data errors using data permutations

• US 7,281,188 B1
• Filed: 05/26/2004
• Issued: 10/09/2007
• Est. Priority Date: 05/26/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Ahrens, Matthew A., Bonwick, Jeffrey S.
• Primary Examiner(s): Lamarre; Guy
• Assistant Examiner(s): Alphonse; Fritz
• Application Number:
  US10/853,870
• Time in Patent Office: 1,231 Days
• Field of Search: 714/752, 714/758, 714/755, 714/785, 714/6, 714/788, 714/799
• US Class Current: 714/752
• CPC Class Codes: H03M 13/096 Checksums
• CPC Class Codes: H03M 13/3746 with iterative decoding
• CPC Class Codes: H03M 13/3753 using iteration stopping criteria

Abstract

A method for correcting an error in a first block including detecting an error in the first block, generating a first permutation of the first block, calculating a first permutation checksum for the first permutation of the first block, and replacing the first block with the first permutation of the first block, if a first block checksum matches the first permutation checksum.

Claims

1. A method for correcting an error in a first block comprising:

detecting an error in the first block;

generating a first permutation of the first block, wherein generating the first permutation of the first block comprises flipping a first bit of the first block, wherein flipping the first bit comprises one selected from a group consisting of changing the first bit from a zero to a one, when the first bit is a zero, and changing the first bit from a one to a zero, when the first bit is a one;

calculating a first permutation checksum for the first permutation of the first block; and

replacing the first block with the first permutation of the first block, when a first block checksum matches the first permutation checksum.

2. The method of claim 1, further comprising:

generating a second permutation of the first block, when the first block checksum does not match the first permutation checksum, wherein generating the second permutation of the first block comprises flipping a second bit of the first block, wherein flipping the second bit comprises one selected from a group consisting of changing the second bit from a zero to a one, when the second bit is a zero, and changing the second bit from a one to a zero, when the second bit is a one;

calculating a second permutation checksum for the second permutation of the first block; and

replacing the first block with the second permutation of the first block, when a first block checksum matches the second permutation checksum.

3. The method of claim 1, further comprising:

storing the first block in a storage pool;

obtaining the first block location;

calculating the first block checksum for the first block; and

storing a second block in the storage pool, wherein the second block comprises the first block location and the first block checksum.

4. The method of claim 3, further comprising:

assembling the first block.

5. The method of claim 4, wherein assembling the first block comprises

storing the first block checksum in a checksum field within a block pointer, and

storing the first block location in the block pointer, wherein storing the data location comprises storing a metaslab ID and offset.

6. The method of claim 5, further comprising:

storing a birth value in a birth field within the block pointer.

7. The method of claim 4, wherein the first block is assembled using a data management unit.

8. The method of claim 3, wherein the storage pool comprises at least one disk.

9. The method of claim 3, wherein the storage pool is divided into a plurality of metaslabs.

10. The method of claim 9, wherein each of the plurality of metaslabs is associated with a metaslab ID.

11. The method of claim 9, wherein the data block location comprises the metaslab ID and an offset.

12. The method of claim 1, wherein storing the data block comprises using a storage pool allocator.

13. The method of claim 1, wherein detecting the error in the block comprises:

calculating a checksum for the block; and

determining whether the checksum for the block equals the block checksum.

14. The method of claim 1, wherein the block is one selected from the group consisting of a data block and an indirect block.

15. A method for retrieving data in a data block, comprising:

obtaining an indirect block comprising a stored checksum and a data block location;

obtaining the data block using the data block location;

calculating the checksum for the data block to obtain a calculated checksum;

retrieving the data from the data block, if the stored checksum equals the calculated checksum; and

performing error correction, if the stored checksum is not equal to the calculated checksum, wherein performing error correction comprises;

generating a permutation of the data block, wherein generating the permutation of the data block comprises flipping at least one bit of the data block, wherein flipping the at least one bit comprises one selected from a group consisting of changing the at least one bit from a zero to a one, when the at least one bit is a zero, and changing the at least one bit from a one to a zero, when the at least one bit is a one;

calculating a permutation checksum for the permutation of the data block; and

replacing the data block with the permutation of the data block, when the stored checksum matches the permutation checksum.

16. The method of claim 15, wherein the calculated checksum is calculated using a storage pool allocator.

17. A system for correcting an error in a first block, comprising:

a storage pool comprising the first block and a second block, wherein the second block comprises a first block checksum and a first block location;

a storage pool allocator configured to store the first block and the second block in the storage pool; and

a data management unit configured to correct the error in the first block, if the error is detected,

wherein the error in the first block is corrected by generating a permutation of the first block, wherein generating the permutation of the first block comprises flipping at least one bit of the first block, wherein flipping the at least one bit comprises one selected from a group consisting of changing the at least one bit from a zero to a one, when the at least one bit is a zero, and changing the at least one bit from a one to a zero, when the at least one bit is a one, calculating a permutation checksum for the permutation of the first block, comparing the permutation checksum to the first block checksum, and replacing the first block with the permutation of the first block, when the permutation checksum matches the first block checksum.

18. The system of claim 17, wherein the first block is one selected from the group consisting of a data block and an indirect block.

19. The system of claim 17, wherein the storage pool comprises at least one disk.

20. The system of claim 17, wherein the error in the first block is corrected by:

storing the first block in a storage pool;

obtaining the first block location;

calculating the first block checksum for the first block; and

storing a second block in the storage pool, wherein the second block comprises the first block location and the first block checksum.

21. The system of claim 17, wherein the storage pool is divided into a plurality of metaslabs.

22. A computer system for correcting an error in a first block, comprising:

a processor;

a memory;

a storage device; and

software instructions stored in the memory for enabling the computer system under control of the processor, to;

detect an error in the first block;

generate a permutation of the first block, wherein generating the permutation of the first block comprises flipping a first bit of the first block, wherein flipping the first bit comprises one selected from a group consisting of changing the first bit from a zero to a one, when the first bit is a zero, and changing the first bit from a one to a zero, when the first bit is a one;

calculate a permutation checksum for the permutation of the first block; and

replace the first block with the permutation of the first block, when a first block checksum matches the permutation checksum.

23. A network system having a plurality of nodes, comprising:

a storage pool comprising the first block and a second block, wherein the second block comprises a first block checksum and a first block location;

a storage pool allocator configured to store the first block and the second block in the storage pool; and

a data management unit configured to correct the error in the first block, if the error is detected,

wherein the error in the first block is corrected by generating a permutation of the first block, wherein generating the permutation of the first block comprises flipping at least one bit of the first block, wherein flipping the at least one bit comprises one selected from a group consisting of changing the at least one bit from a zero to a one, when the at least one bit is a zero, and changing the at least one bit from a one to a zero, when the at least one bit is a one, calculating a permutation checksum for the permutation of the first block, comparing the permutation checksum to the first block checksum, and replacing the first block with the permutation of the first block when the permutation checksum matches the first block checksum,

wherein the storage pool is located on any one of the plurality of nodes, and wherein the storage pool allocator is located on any one of the plurality of nodes.