Granted Patent B2

US 10,275,309 · App. 15/497,879 · Granted Apr 30, 2019

Inventor: Satoshi Yamamoto (San Jose, CA)

Assignee: Western Digital Technologies, Inc.

G06F11/1076G06F11/1435H03M13/1148H03M13/616

Abstract

Claims (96)

1. A method comprising:

dividing a data band into a plurality (M) of sub-data bands (D s _ i ) each having a size defined by a number of virtual tracks (T s ) each having a number of virtual sectors (N), where i=1 to M;

generating a respective 1 st -layer sub-data band error correction parity matrix (P E _ i ) for each said sub-data band (D s _ i ) of said plurality of sub-data bands, by:

generating a respective i th sub-data band cross-track matrix (D B _ i ) by multiplying a respective i th sub-matrix (I i ) of an integration matrix (I) by a respective sub-data band (D s _ i ), and

multiplying a transpose of a respective 1 st encoding sub-matrix (C 1 ) of an encoding matrix (C) by said i th sub-data band cross-track matrix (D B _ i ), thereby producing said respective 1 st -layer parity matrix (P E _ i );

generating an association between each said respective 1 st -layer parity matrix (P E _ i ) and each corresponding said sub-data band (D s _ i );

generating a respective (q th >1)-layer error correction parity matrix (P Eq _ k ), where k=1 to M/2 (q−1) , by:

generating a q th -layer sub-data band cross-track matrix (D Bq _ k ) by performing an exclusive or (XOR) operation on two adjacent (q−1) th -layer sub-data band cross-track matrices (D Bq−1 _ 2k−1 ) and (D Bq−1 _ 2k ), and

multiplying a transpose of a respective q th encoding sub-matrix (C q ) of said encoding matrix (C) by said respective q th -layer sub-data band cross-track matrix (D Bq _ k ), thereby producing said respective qth-layer parity matrix (P Eq _ k );

generating an association between each said respective q th -layer parity matrix (P Eq _ k ) and each corresponding said sub-data bands from (D s _ (k−1)*2 (q−1) +1 ) to (D s _ k*2 (q−1) );

writing at least a portion of the following to one or more data storage devices:

said data band,

each said respective 1 st -layer sub-data band parity matrix (P E _ i ) for each said sub-data band (D s _ i ),

each said association between each said respective 1 st -layer parity matrix (P E _ i ) and said corresponding sub-data band (D s _ i ),

each said respective (q th >1)-layer parity matrix (P Eq _ k ), and

each said association between each said respective (q th >1)-layer parity matrix (P Eq _ k ) and each corresponding said sub-data bands from (D s _ (k−1)*2 (q−1) +1 ) to (D s _ k*2 (q−1) );

in response to receiving, from said one or more data storage devices, an indication of uncorrected errors associated with corrupt data from at least one sector corresponding to at least one sub-data band (D s _ i ) of said data band, determining how much of said 1 st -layer sub-data band parity matrix (P E _ i ) and/or said (q th >1)-layer parity matrix (P Eq _ k ) is needed to recover said corrupt data; and

requesting a read of less than the entire said data band but including said at least one sub-data band (D s _ 1 ) containing said corrupt data and at least some of said 1 st -layer sub-data band parity matrix (P E _ i ) and/or said (q th >1)-layer parity matrix (P Eq _ k ) based on said determining.

2. The method of claim 1 , wherein said writing includes:

writing said data band to a first data storage device of said one or more data storage devices; and

writing at least some of said 1 st -layer sub-data band parity matrix (P E _ i ) and said (q th >1)-layer parity matrix (P Eq _ k ) to a second data storage device that is different from said first data storage device.

3. The method of claim 1 , further comprising:

recovering said corrupt data based on said at least one sub-data band (D s _ 1 ) containing said corrupt data and at least some of said 1 st -layer sub-data band parity matrix (P E _ i ) and/or said (q th >1)-layer parity matrix (P Eq _ k ).

4. A data storage system comprising:

one or more data storage devices; and

a system controller embodying one or more sequences of instructions which, when executed by one or more processors, cause performance of:

with a data band having a size defined by a number of virtual tracks (T) each having a number of virtual sectors (N), dividing said data band into a plurality (M) of sub-data bands (D s _ i ) each having a size defined by a number of virtual tracks (T s ) each having said number of virtual sectors (N),

generating a first first-layer sub-data band error correction parity matrix (P E _ 1 ) for a first sub-data band (D s _ 1 ) of said plurality of sub-data bands by:

generating a first sub-data band cross-track matrix (D B _ 1 ) by matrix multiplying a first sub-matrix (I 1 ) of an integration matrix (I i ) by said first sub-data band (D s _ 1 ), and

matrix multiplying a transpose of a first encoding sub-matrix (C 1 ) of an encoding matrix (C) by said first sub-data band cross-track matrix (D B _ 1 ), thereby producing said first first-layer sub-data band error correction parity matrix (P E _ 1 ),

storing an association of said first first-layer sub-data band error correction parity matrix (P E _ 1 ) with said first sub-data band (D s _ 1 ),

generating a second first-layer sub-data band error correction parity matrix (P E _ 2 ) for a second sub-data band (D s _ 2 ) of said plurality of sub-data bands by:

generating a second sub-data band cross-track matrix (D B _ 2 ) by matrix multiplying a second sub-matrix (I 2 ) of said integration matrix (I i ) by said second sub-data band (D s _ 2 ), and

matrix multiplying said transpose of said first encoding sub-matrix (C 1 ) by said second sub-data band cross-track matrix (D B _ 2 ), thereby producing said second first-layer sub-data band error correction parity matrix (P E _ 2 ),

storing an association of said second first-layer sub-data band error correction parity matrix (P E _ 2 ) with said second sub-data band (D s _ 2 ),

generating a first second-layer error correction parity matrix (P E2 _ 1 ) by:

generating a first second-layer sub-data band cross-track matrix (D B2 _ 1 ) by performing an exclusive or (XOR) operation on said first sub-data band cross-track matrix (D B _ 1 ) and said second sub-data band cross-track matrix (D B _ 2 ), and

matrix multiplying a transpose of a second encoding sub-matrix (C 2 ) of said encoding matrix (C) by said first second-layer sub-data band cross-track matrix (D B2 _ 1 ), thereby producing said first second-layer error correction parity matrix (P E2 _ 1 ), and

storing an association of said first second-layer error correction parity matrix (P E2 _ 1 ) with each of said first sub-data band (D s _ 1 ) and said second sub-data band (D s _ 2 ).

5. The data storage system of claim 4 , wherein said one or more data storage devices comprise shingled magnetic recording (SMR) hard disk drives.

6. The data storage system of claim 4 , wherein said one or more sequences of instructions cause further performance of:

writing at least the following to one or more of said one or more data storage devices:

said first sub-data band (D s _ 1 ),

said first first-layer sub-data band error correction parity matrix (P E _ 1 ),

said association of said first first-layer sub-data band error correction parity matrix (P E _ 1 ) with said first sub-data band (D s _ 1 ),

said second sub-data band (D s _ 2 ),

said second first-layer sub-data band error correction parity matrix (P E _ 2 ),

said association of said second first-layer sub-data band error correction parity matrix (P E _ 2 ) with said second sub-data band (D s _ 2 ), and

said association of said first second-layer error correction parity matrix (P E2 _ 1 ) with each of said first sub-data band (D s _ 1 ) and said second sub-data band (D s _ 2 ).

7. The data storage system of claim 6 , wherein said writing includes:

writing said first sub-data band (D s _ 1 ) and said second sub-data band (D s _ 2 ) to a first data storage device of said one or more data storage devices; and

writing said first first-layer sub-data band error correction parity matrix (P E _ 1 ), said second first-layer sub-data band error correction parity matrix (P E _ 2 ), and said first second-layer error correction parity matrix (P E2 _ 1 ) to a second data storage device of said one or more data storage devices that is different from said first data storage device.

8. The data storage system of claim 6 , wherein said writing includes writing all of said sub-data bands and parity matrices to a single data storage device of said one or more data storage devices.

9. The data storage system of claim 6 , wherein said one or more sequences of instructions cause further performance of:

requesting a read of said data band; and

in response to receiving, from said one or more data storage devices, an indication of uncorrected errors associated with at least one sector corresponding to said first sub-data band (D s _ 1 ), requesting a read of less than the entire said data band but including said first sub-data band (D s _ 1 ) and said first first-layer sub-data band error correction parity matrix (P E _ 1 ).

10. The data storage system of claim 6 , wherein said one or more sequences of instructions cause further performance of:

requesting a read of said data band; and

in response to receiving, from said one or more data storage devices, an indication of uncorrected errors associated with said first sub-data band (D s _ 1 ) and/or said second sub-data band (D s _ 2 ), requesting a read of less than the entire said data band but including said first sub-data band (D s _ 1 ), said second sub-data band (D s _ 2 ), said first first-layer sub-data band error correction parity matrix (P E _ 1 ), said second first-layer sub-data band error correction parity matrix (P E _ 2 ), and said first second-layer error correction parity matrix (P E2 _ 1 ).

11. The data storage system of claim 6 , wherein said one or more sequences of instructions cause further performance of:

requesting a read of said data band; and

in response to receiving an indication of uncorrected errors associated with one or more sectors of said first sub-data band (D s _ 1 ) and/or said second sub-data band (D s _ 2 ), and wherein each of said one or more sectors is returned with a respective null, recovering data from said one or more sectors based on:

said first sub-matrix (I 1 ) and said second sub-matrix (I 2 ) of said integration matrix (I),

said transpose of said first encoding sub-matrix (C 1 ) and said transpose of said second encoding sub-matrix (C 2 ) of said encoding matrix (C), and

said first first-layer sub-data band error correction parity matrix (P E _ 1 ), said second first-layer sub-data band error correction parity matrix (P E _ 2 ), and said first second-layer error correction parity matrix (P E2 _ 1 ).

12. The data storage system of claim 6 , wherein:

said one or more data storage devices comprise shingled magnetic recording (SMR) hard disk drives; and

said writing includes writing without a corresponding write verify operation.

13. The data storage system of claim 4 , wherein said system controller comprises an application-specific integrated circuit (ASIC).

14. An electronic data storage system controller manufacture embodying one or more sequences of instructions which, when executed by one or more processors, cause performance of:

dividing a data band into a plurality (M) of sub-data bands (D s _ i ) each having a size defined by a number of virtual tracks (T s ) each having a number of virtual sectors (N), where i=1 to M,

generating a respective 1 st -layer sub-data band error correction parity matrix (P E _ i ) for each said sub-data band (D) of said plurality of sub-data bands, by:

generating a respective i th sub-data band cross-track matrix (D B _ i ) by multiplying a respective i th sub-matrix (I i ) of an integration matrix (I) by a respective sub-data band (D s _ i ), and

multiplying a transpose of a respective 1 st encoding sub-matrix (C 1 ) of an encoding matrix (C) by said 1 th sub-data band cross-track matrix (D B _ i ), thereby producing said respective 1 st -layer parity matrix (P E _ i );

generating an association between each said respective 1 st -layer parity matrix (P E _ i ) and each corresponding said sub-data band (D s _ i );

generating a respective (qth>1)-layer error correction parity matrix (P Eq _ k ), where k=1 to M/2 (q−1) , by:

generating a q th -layer sub-data band cross-track matrix (D Bq _ k ) by performing an exclusive or (XOR) operation on two adjacent (q−1) th -layer sub-data band cross-track matrices (D Bq−1 _ 2k−1 ) and (D Bq−1 _ 2k ), and

multiplying a transpose of a respective q th encoding sub-matrix (C q ) of said encoding matrix (C) by said respective q th layer sub-data band cross-track matrix (D Bq _ k ), thereby producing said respective q th -layer parity matrix (P Eq _ k ); and

generating an association between each said respective q th -layer parity matrix (P Eq _ k ) and each corresponding said sub-data bands from (D s _ (k−1)*2 (q−1) ) to (D s _ k*2 (q−1) ).

15. The electronic data storage system controller manufacture of claim 14 , wherein said one or more sequences of instructions cause further performance of:

writing at least a portion of the following to one or more data storage devices:

said data band,

each said respective 1 st -layer sub-data band parity matrix (P E _ i ) for each said sub-data band (D s _ i ),

each said association between each said respective 1 st -layer parity matrix (P E _ i ) and said corresponding sub-data band (D s _ i ),

each said respective (q th >1)-layer parity matrix (P Eq _ k ), and

each said association between each said respective (q th >1)-layer parity matrix (P Eq _ k ) and each corresponding said sub-data bands from (D s _ (k−1)*2 (q−1) ) to (D s _ k*2 (q−1) ).

16. The electronic data storage system controller manufacture of claim 15 , wherein said one or more sequences of instructions cause further performance of:

in response to receiving, from said one or more data storage devices, an indication of uncorrected errors associated with corrupt data from at least one sector corresponding to at least one sub-data band (D s _ i ) of said data band, determining how much of said 1 st -layer sub-data band parity matrix (P E _ i ) and/or said (q th >1)-layer parity matrix (P Eq _ k ) is needed to recover said corrupt data; and

requesting a read of less than the entire said data band but including said at least one sub-data band (D s _ 1 ) containing said corrupt data and at least some of said 1 st -layer sub-data band parity matrix (P E _ i ) and/or said (q th >1)-layer parity matrix (P Eq _ k ) based on said determining.

17. The electronic data storage system controller manufacture of claim 15 , wherein said one or more sequences of instructions cause further performance of:

in response to receiving, from said one or more data storage devices, an indication of uncorrected errors associated with corrupt data from at least one sector corresponding to at least one sub-data band (D s _ i ) of said data band, determining how much of said 1 st -layer sub-data band parity matrix (P E _ i ) and/or said (q th >1)-layer parity matrix (P Eq _ k ) is needed to recover said corrupt data;

requesting a read of less than the entire said data band but including said at least one sub-data band (D s _ 1 ) containing said corrupt data and at least some of said 1 st -layer sub-data band parity matrix (P E _ i ) and/or said (q th >1)-layer parity matrix (P Eq _ k ) based on said determining; and

recovering said corrupt data based on said at least one sub-data band (D s _ 1 ) containing said corrupt data and at least some of said 1 st -layer sub-data band parity matrix (P E _ i ) and/or said (q th >1)-layer parity matrix (P Eq _ k ).

18. The electronic data storage system controller manufacture of claim 15 , wherein:

said electronic data storage system controller manufacture comprises an application-specific integrated circuit (ASIC); and

said writing includes writing without a corresponding write verify operation.

Assignments (10)

Continuity (1)