Systems and methods for sequential resilvering

• US 10,671,501 B2
• Filed: 05/31/2017
• Issued: 06/02/2020
• Est. Priority Date: 06/09/2014
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Taylor, Eric Carl, Xiao, Zhu
• Primary Examiner(s): Leibovich, Yair
• Application Number:
  US15/610,140
• Publication Number:
  US 20170329682A1
• Time in Patent Office: 1,098 Days
• Field of Search: 714 381
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/2069 Management of state, configuration or failover
• CPC Class Codes: G06F 11/2071 using a plurality of controllers
• CPC Class Codes: G06F 11/2082 Data synchronisation
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064

Abstract

A method of reconstructing data from a failed storage device in a storage pool includes identifying a plurality of data blocks that are stored on the failed storage device, and sorting the plurality of data blocks in an order in which the plurality of data blocks are located on the failed storage device. Each of the plurality of data blocks may be associated with an I/O operation. The method may also include grouping the I/O operations for the plurality of data blocks into sequential I/O operations based on the order in which the plurality of data blocks are located on the failed storage device, and executing the sequential I/O operations to resilver a new storage device replacing the failed storage device.

Claims

1. A method of reconstructing data from a failed storage device in a storage pool, the method comprising:

identifying a plurality of data blocks that are stored on the failed storage device;

locating the plurality of data blocks on one or more redundant storage devices;

sorting and storing the plurality of data blocks from the one or more redundant storage devices into a plurality of temporary objects in a first order in which the plurality of data blocks are located on the failed storage device, wherein a second order in which the plurality of data blocks are stored on the one or more redundant storage devices is different from the first order of the plurality of data blocks after sorting, wherein each of the plurality of data blocks is associated with an I/O operation, and wherein sorting the plurality of data blocks comprises;

sorting the plurality of data blocks into one or more buckets by performing a first sorting operation that coarsely sorts data blocks into each of the one or more buckets based on disk address, such that blocks within each of the one or more buckets are not required to be in disk address order; and

performing a second sorting operation that sorts the blocks within each of the one or more buckets according to disk address order;

grouping the I/O operations for the plurality of data blocks into sequential I/O operations based on the order in which the plurality of data blocks are located on the failed storage device; and

executing the sequential I/O operations to resilver a new storage device replacing the failed storage device.

2. The method of claim 1, wherein the storage pool comprises a Redundant Array of Independent Disks (RAID).

3. The method of claim 1, wherein identifying the plurality of data blocks that are stored on the failed storage device comprises traversing a file system to discover a physical location of each leaf node.

4. The method of claim 1, wherein the blocks within each of the one or more buckets are sorted into Adelson-Velsky Landis (AVL) tree.

5. The method of claim 1, wherein a number of the one or more buckets is based on an amount of memory on the failed storage device.

6. A non-transitory, computer-readable medium comprising instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:

identifying a plurality of data blocks that are stored on a failed storage device in a storage pool;

sorting the plurality of data blocks in an order in which the plurality of data blocks are located on the failed storage device, wherein each of the plurality of data blocks is associated with an I/O operation, and wherein sorting the plurality of data blocks comprises sorting the plurality of data blocks into a plurality of temporary objects;

grouping the I/O operations for the plurality of data blocks into sequential I/O operations based on the order in which the plurality of data blocks are located on the failed storage device; and

executing the sequential I/O operations to resilver a new storage device replacing the failed storage device.

7. The non-transitory computer-readable medium according to claim 6 wherein executing the sequential I/O operations to resilver a new storage device comprises:

sequentially traversing the plurality of data blocks in logical block order to reconstruct data for which the I/O operations were not successfully completed for the failed storage device.

8. The non-transitory computer-readable medium according to claim 6, wherein executing the sequential I/O operations to resilver the new storage device comprises deleting each temporary object after the data blocks therein are resilvered before moving on to a subsequent temporary object.

9. The non-transitory computer-readable medium according to claim 6, wherein identifying the plurality of data blocks that are stored on the failed storage device comprises traversing a file system to discover a physical location of each leaf node.

10. The non-transitory computer-readable medium according to claim 6, wherein sorting the plurality of data blocks comprises sorting the plurality of data blocks into one or more buckets by performing a first sorting operation that coarsely sorts data blocks into each of the one or more buckets based on disk address, such that blocks within each of the one or more buckets are not required to be in disk address order.

11. The non-transitory computer-readable medium according to claim 10, wherein sorting the plurality of data blocks further comprises performing a second sorting operation that sorts the blocks within each of the one or more buckets according to disk address order.

12. A system comprising:

one or more hardware processors; and

one or more memory devices comprising instructions that, when executed by the one or more hardware processors, cause the one or more hardware processors to perform operations comprising;

identifying a plurality of data blocks that are stored on a failed storage device in a storage pool;

sorting the plurality of data blocks in an order in which the plurality of data blocks are located on the failed storage device, wherein each of the plurality of data blocks is associated with an I/O operation;

grouping the I/O operations for the plurality of data blocks into sequential I/O operations based on the order in which the plurality of data blocks are located on the failed storage device; and

executing the sequential I/O operations to resilver a new storage device replacing the failed storage device, wherein executing the sequential I/O operations comprises sequentially traversing the plurality of data blocks in logical block order to reconstruct data for which the I/O operations were not successfully completed for the failed storage device.

13. The system of claim 12 wherein:

the storage pool comprises a Redundant Array of Independent Disks (RAID); and

identifying a plurality of data blocks that are stored on the failed storage device comprises traversing a file system to discover a physical location of each leaf node.

14. The system of claim 12 wherein:

sorting the plurality of data blocks comprises performing a first sorting operation that coarsely sorts data blocks into each of one or more buckets based on disk address, such that blocks within each of the one or more buckets are not required to be in disk address order;

sorting the plurality of data blocks into one or more buckets comprises performing a second sorting operation that sorts the blocks within each of the one or more buckets according to disk address order; and

the blocks within each of the one or more buckets are sorted into Adelson-Velsky Landis (AVL) tree.

15. The system of claim 12, wherein sorting the plurality of data blocks comprises sorting the plurality of data blocks into a plurality of temporary objects.

16. The system of claim 15, wherein executing the sequential I/O operations to resilver the new storage device comprises deleting each temporary object after the data blocks therein are resilvered before moving on to a subsequent temporary object.