# US 8,543,761 B2 · Zero rebuild extensions for raid > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,543,761 B2 - Document ID: US8543761B2 - Status: Granted - Kind: B2 - Application number: 13/083,301 - Filed: 2011-04-08 - Published: 2012-10-11 - Granted: 2013-09-24 - Earliest claimed: 2011-04-08 - Assignees: LSI Corporation - Applicants: Jonathan S. Goldick - Inventors: Jonathan S. Goldick - Web page: https://patentgrep.com/patent/US8543761B2 ## CPC - G06F 11/1092: {Rebuilding, e.g. when physically replacing a failing disk} - G06F 11/2094: {Redundant storage or storage space (G06F11/2056 takes precedence)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Disclosed is a method of reliably operating a RAID storage system. A first block of data is striped across a plurality of drives following a CRUSH algorithm. The first block of data is again striped across a second plurality of drives to a D′+P′ stripe and placed on free drive space following the CRUSH algorithm. The data is written in an asynchronous fashion and possibly at a time when system utilization is low. ## Claims ### Claim 1 A method for reliably storing data in a computer system comprising: selecting a first plurality of drives from a total pool of drives to handle primary Redundant Array of Independent Disks (RAID) Data and Parity (D+P) striping according to Controlled Replication Under Scalable Hashing (CRUSH) algorithms; writing a first block of data in said primary RAID D+P striping to said first plurality of drives in accord with said CRUSH algorithm; selecting a second plurality of drives from a remainder pool of drives to handle redundant RAID Data plus Parity (D′+P′) striping according to said CRUSH algorithm, said remainder pool of drives being said total pool of drives excluding said first plurality of drives selected from said total pool of drives, said second plurality of drives having free space not already used by other applications; and writing at least a portion of said first block of data in said redundant RAID D′+P′ striping to said second plurality of drives in said free space of said second plurality of drives in accord with said CRUSH algorithm as at least a partial redundant copy of said primary RAID D+P striping such that said redundant RAID D′+P′ striping as well as standard RAID rebuild algorithms for exclusive or (XOR) data and parity striping are available to rebuild said first data block when a drive in said first plurality of drives fails, and such that said free space used by said redundant RAID D′+P′ striping is still available for primary application usage. ### Claim 2 (depends on 1) The method of claim 1 wherein said process of writing at least a portion of said first block of data in said redundant RAID D′+P′ striping to said second plurality of drives further comprises said writing to said second plurality of drives being performed asynchronously during system idle time when extra Input/Output Operations (IOPS) are available without impact on primary application performance. ### Claim 3 (depends on 1) The method of claim 1 further comprising: selecting at least one additional plurality of drives from a second remainder pool of drives to handle additional redundant RAID Data plus Parity (D′+P′) striping according to said CRUSH algorithm, said second remainder pool of drives being said total pool of drives excluding said first and said second plurality of drives selected from said total pool of drives, said at least one additional plurality of drives having free space not already used by other applications; and writing at least a portion of said first block of data in said at least one additional redundant RAID D′+P′ striping to said at least one additional plurality of drives in said free space of said at least one additional plurality of drives in accord with said CRUSH algorithm as at least a partial redundant copy of said primary RAID D+P striping such that said at least one additional redundant RAID D′+P′ striping and said redundant RAID D′+P′ striping, as well as standard RAID rebuild algorithms for exclusive or (XOR) data and parity striping, are available to rebuild said first data block when a drive in said first plurality of drives fails, and such that said free space used by said at least one additional redundant RAID D′+P′ striping is still available for primary application usage. ### Claim 4 (depends on 1) The method of claim 1 further comprising reclaiming at least a portion of storage space used for said redundant RAID D′+P′ striping when said primary application usage requires space that is otherwise unavailable. ### Claim 5 (depends on 1) The method of claim 1 wherein said process of writing at least a portion of said first block of data in said redundant RAID D′+P′ striping to said second plurality of drives further comprises writing all of said first block of data in said redundant RAID D′+P′ striping to said second plurality of drives when space utilization across said total pool of drives is 50% or less. ### Claim 6 (depends on 1) The method of claim 1 further comprising scheduling said process of writing at least a portion of said first block of data in said redundant RAID D′+P′ striping to said second plurality of drives while said first block of data is still in Dynamic Random Access Memory (DRAM). ### Claim 7 (depends on 1) The method of claim 1 further comprising improving read performance of said first block of data from said total pool of drives, said improvement of read performance being accomplished by at least one of a group consisting of: reading data from said primary RAID D+P striping or redundant RAID D′+P′ from drives with lightest loading, and reading data from said primary RAID D+P striping or redundant RAID D′+P′ from drives where data is located closest to a drive arm of said drives in order to reduce latency. ### Claim 8 (depends on 1) The method of claim 1 wherein said redundant RAID D′+P′ striping is different than said primary RAID D+P striping. ### Claim 9 (depends on 1) The method of claim 1 further comprising: rebuilding said primary RAID D+P striping when there are failed disks in said first plurality of drives by changing addressing to equivalent portions of said redundant RAID D′+P′ striping; and recreating said portions of said redundant RAID D′+P′ striping readdressed to said primary RAID D+P striping on different non-overlapping drives of said total pool of drives in order to restore said redundant RAID D′+P′ striping. ### Claim 10 (depends on 1) The method of claim 1 further comprising rebuilding said primary RAID D+P striping when there are failed disks in said first plurality of drives by copying equivalent portions of said redundant RAID D′+P′ striping to new non-overlapping drives in said total pool of drives and addressing said new non-overlapping drives as said primary RAID D+P striping. ### Claim 11 A zero-rebuild redundant array of independent disks (RAID) storage system, comprising: a total pool of drives; a first plurality of drives selected from said total pool of drives; a second plurality of drives from a remainder pool of drives, said remainder pool of drives being said total pool of drives excluding said first plurality of drives selected from said total pool of drives, said second plurality of drives having free space not already used by other applications; and a RAID storage controller that selects said first plurality of drives from said total pool of drives to handle primary RAID Data and Parity (D+P) striping according to Controlled Replication Under Scalable Hashing (CRUSH) algorithms, writes a first block of data in said primary RAID D+P striping to said first plurality of drives in accord with said CRUSH algorithm, selects said second plurality of drives from said remainder pool of drives to handle redundant RAID Data plus Parity (D′+P′) striping according to said CRUSH algorithm, and writes at least a portion of said first block of data in said redundant RAID D′+P′ striping to said second plurality of drives in said free space of said second plurality of drives in accord with said CRUSH algorithm as at least a partial redundant copy of said primary RAID D+P striping such that said redundant RAID D′+P′ striping as well as standard RAID rebuild algorithms for exclusive or (XOR) data and parity striping are available to rebuild said first data block when a drive in said first plurality of drives fails, and such that said free space used by said redundant RAID D′+P′ striping is still available for primary application usage. ### Claim 12 (depends on 11) The system of claim 11 wherein said RAID storage controller writes to said second plurality of drives asynchronously during system idle time when extra Input/Output Operations (IOPS) are available without impact on primary application performance. ### Claim 13 (depends on 11) The system of claim 11 further comprising: at least one additional plurality of drives selected from a second remainder pool of drives, said second remainder pool of drives being said total pool of drives excluding said first and said second plurality of drives selected from said total pool of drives, said at least one additional plurality of drives having free space not already used by other applications; and wherein said RAID storage controller further selects at least one additional plurality of drives from a second remainder pool of drives to handle additional redundant RAID Data plus Parity (D′+P′) striping according to said CRUSH algorithm, and writes at least a portion of said first block of data in said at least one additional redundant RAID D′+P′ striping to said at least one additional plurality of drives in said free space of said at least one additional plurality of drives in accord with said CRUSH algorithm as at least a partial redundant copy of said primary RAID D+P striping such that said at least one additional redundant RAID D′+P′ striping and said redundant RAID D′+P′ striping, as well as standard RAID rebuild algorithms for exclusive or (XOR) data and parity striping, are available to rebuild said first data block when a drive in said first plurality of drives fails, and such that said free space used by said at least one additional redundant RAID D′+P′ striping is still available for primary application usage. ### Claim 14 (depends on 11) The system of claim 11 wherein said RAID storage controller further reclaims at least a portion of storage space used for redundant RAID D′+P′ striping when said primary application usage requires space that is otherwise unavailable. ### Claim 15 (depends on 11) The system of claim 11 wherein said RAID storage controller writes all of said first block of data in said redundant RAID D′+P′ striping to said second plurality of drives when space utilization across said total pool of drives is 50% or less. ### Claim 16 (depends on 11) The system of claim 11 wherein said RAID storage controller schedules said writes of at least a portion of said first block of data in said redundant RAID D′+P′ striping to said second plurality of drives while said first block of data is still in Dynamic Random Access Memory (DRAM). ### Claim 17 (depends on 11) The system of claim 11 further comprising said RAID storage controller improved read performance of said first block of data from said total pool of drives, said improved read performance being accomplished by said RAID storage that operates by at least one of a group consisting of read data from said primary RAID D+P striping or redundant RAID D′+P′ from drives with lightest loading, and read data from said primary RAID D+P striping or redundant RAID D′+P′ from drives where data is located closest to a drive arm of said drives in order to reduce latency. ### Claim 18 (depends on 11) The system of claim 11 wherein said redundant RAID D′+P′ striping is different than said primary RAID D+P striping. ### Claim 19 (depends on 11) The system of claim 11 wherein said RAID storage controller further rebuilds said primary RAID D+P striping when there are failed disks in said first plurality of drives by changing addressing to equivalent portions of said redundant RAID D′+P′ striping, and recreates said portions of said redundant RAID D′+P′ striping readdressed to said primary RAID D+P striping on different non-overlapping drives of said total pool of drives in order to restore said redundant RAID D′+P′ striping. ### Claim 20 (depends on 11) The system of claim 11 wherein said RAID storage controller further rebuilds said primary RAID D+P striping when there are failed disks in said first plurality of drives by copying equivalent portions of said redundant RAID D′+P′ striping to new non-overlapping drives in said total pool of drives and addressing said new non-overlapping drives as said primary RAID D+P striping. ### Claim 21 A non-transitory computer readable medium having instructions stored thereon for operating a redundant array of independent disks (RAID) storage system that, when executed by a computer, at least direct said computer to: select a first plurality of drives from a total pool of drives to handle primary Redundant Array of Independent Disks (RAID) Data and Parity (D+P) striping according to Controlled Replication Under Scalable Hashing (CRUSH) algorithms; write a first block of data in said primary RAID D+P striping to said first plurality of drives in accord with said CRUSH algorithm; select a second plurality of drives from a remainder pool of drives to handle redundant RAID Data plus Parity (D′+P′) striping according to said CRUSH algorithm, said remainder pool of drives being said total pool of drives excluding said first plurality of drives selected from said total pool of drives, said second plurality of drives having free space not already used by other applications; and write at least a portion of said first block of data in said redundant RAID D′+P′ striping to said second plurality of drives in said free space of said second plurality of drives in accord with said CRUSH algorithm as at least a partial redundant copy of said primary RAID D+P striping such that said redundant RAID D′+P′ striping as well as standard RAID rebuild algorithms for exclusive or (XOR) data and parity striping are available to rebuild said first data block when a drive in said first plurality of drives fails, and such that said free space used by said redundant RAID D′+P′ striping is still available for primary application usage. ### Claim 22 (depends on 21) The computer readable medium of claim 21, wherein said computer instructions for writing at least a portion of said first block of data in said redundant RAID D′+P′ striping to said second plurality of drives further comprise directing said write to said second plurality of drives to be performed asynchronously during system idle time when extra Input/Output Operations (IOPS) are available without impact on primary application performance. ### Claim 23 (depends on 21) The computer readable medium of claim 21, wherein said computer is further directed to: select at least one additional plurality of drives from a second remainder pool of drives to handle additional redundant RAID Data plus Parity (D′+P′) striping according to said CRUSH algorithm, said second remainder pool of drives being said total pool of drives excluding said first and said second plurality of drives selected from said total pool of drives, said at least one additional plurality of drives having free space not already used by other applications; and write at least a portion of said first block of data in said at least one additional redundant RAID D′+P′ striping to said at least one additional plurality of drives in said free space of said at least one additional plurality of drives in accord with said CRUSH algorithm as at least a partial redundant copy of said primary RAID D+P striping such that said at least one additional redundant RAID D′+P′ striping and said redundant RAID D′+P′ striping, as well as standard RAID rebuild algorithms for exclusive or (XOR) data and parity striping, are available to rebuild said first data block when a drive in said first plurality of drives fails, and such that said free space used by said at least one additional redundant RAID D′+P′ striping is still available for primary application usage. ### Claim 24 (depends on 21) The computer readable medium of claim 21, wherein said computer is further directed to: reclaim at least a portion of storage space used for said redundant RAID D′+P′ striping when said primary application usage requires space that is otherwise unavailable. ### Claim 25 (depends on 21) The computer readable medium of claim 21, wherein said computer instructions for writing at least a portion of said first block of data in said redundant RAID D′+P′ striping to said second plurality of drives further comprise directing said computer to write all of said first block of data in said redundant RAID D′+P′ striping to said second plurality of drives when space utilization across said total pool of drives is 50% or less. ### Claim 26 (depends on 21) The computer readable medium of claim 21, wherein said computer instructions for writing at least a portion of said first block of data in said redundant RAID D′+P′ striping to said second plurality of drives further comprise directing said computer to schedule said write of at least a portion of said first block of data in said redundant RAID D′+P′ striping to said second plurality of drives while said first block of data is still in Dynamic Random Access Memory (DRAM). ### Claim 27 (depends on 21) The computer readable medium of claim 21, wherein said computer is further directed to: improve read performance of said first block of data from said total pool of drives, said improvement of read performance being accomplished by directing said computer to perform at least one of a group consisting of: read data from said primary RAID D+P striping or redundant RAID D′+P′ from drives with lightest loading, and read data from said primary RAID D+P striping or redundant RAID D′+P′ from drives where data is located closest to a drive arm of said drives in order to reduce latency. ### Claim 28 (depends on 21) The computer readable medium of claim 21, wherein said redundant RAID D′+P′ striping is different than said primary RAID D+P striping. ### Claim 29 (depends on 21) The computer readable medium of claim 21, wherein said computer is further directed to: rebuild said primary RAID D+P striping when there are failed disks in said first plurality of drives by changing addressing to equivalent portions of said redundant RAID D′+P′ striping; and recreate said portions of said redundant RAID D′+P′ striping readdressed to said primary RAID D+P striping on different non-overlapping drives of said total pool of drives in order to restore said redundant RAID D′+P′ striping. ### Claim 30 (depends on 21) The computer readable medium of claim 21, wherein said computer is further directed to rebuild said primary RAID D+P striping when there are failed disks in said first plurality of drives by copying equivalent portions of said redundant RAID D′+P′ striping to new non-overlapping drives in said total pool of drives and addressing said new non-overlapping drives as said primary RAID D+P striping.