IP Library › Granted Patent US 11,334,279
Granted Patent B2
US 11,334,279 · App. 16/684,147 · Granted May 17, 2022

Hierarchical blacklisting of storage system components

Inventors: Stijn Devriendt (Knesselare, BE); Lien Boelaert (Deinze, BE); Arne De Coninck (Erpe-Mere, BE); Sam De Roeck (Ghent, BE)
Assignee: Western Digital Technologies, Inc.
G06F3/0653G06F3/064G06F3/067G06F3/0617G06F11/3034
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 11,334,279
App. No.
16/684,147
Filed
Nov 14, 2019
Granted
May 17, 2022
Kind
B2
Examiner
DARE, RYAN A
Art Unit
2136
USPC
711/154
Abstract

Example distributed storage systems, controller nodes, and methods provide hierarchical blacklisting of storage system components in response to failed storage requests. Storage elements are accessible through hierarchical storage paths traversing multiple system components. Blacklisted components are aggregated and evaluated against a hierarchy threshold at each level of the hierarchy and all components below the component are blacklisted if the hierarchy threshold is met. Blacklisted components are avoided during subsequent storage requests.

Claims (80)

1. A system, comprising:

a plurality of storage elements configured to store a plurality of data blocks;

a plurality of storage nodes, wherein each storage node of the plurality of storage nodes includes a node group of storage elements from the plurality of storage elements;

a blacklist engine configured to:

identify, based on at least one failed storage request event, blacklisted storage elements among the plurality of storage elements;

aggregate the blacklisted storage elements for the node group of each storage node from the plurality of storage nodes;

perform an evaluation of the aggregated blacklisted storage elements relative to a first level threshold, wherein the first threshold level is less than all storage elements in a selected node group; and

identify, based on the evaluation of the aggregated blacklisted storage elements, the storage elements in the selected node group as blacklisted;

an encoder configured to disassemble a data object into a predetermined number of redundant data blocks comprising an object set for the data object;

a block spreader configured to distribute the predetermined number of redundant data blocks to the plurality of storage elements while excluding blacklisted storage elements;

a block clusterer configured to retrieve a subset of the predetermined number of redundant data blocks while excluding blacklisted storage elements; and

a decoder configured to assemble the data object from the subset of the predetermined number of redundant data blocks.

2. The system of claim 1 , wherein the first level threshold is greater than one storage element in the selected node group.

3. The system of claim 1 , wherein:

the blacklist engine is further configured to identify, using a hierarchical address, each storage element of the plurality of storage elements; and

the hierarchical address includes a plurality of hierarchy level identifiers corresponding to a hierarchical path from at least one controller node to a selected storage element through a plurality of hierarchical system components subject to failure.

4. The system of claim 1 , further comprising:

a plurality of hierarchical system components in a storage path from at least one controller to the plurality of storage elements, wherein:

the blacklist engine is further configured to:

select a hierarchy threshold for each hierarchy level of the plurality of hierarchical system components;

evaluate the aggregated blacklisted storage elements for each hierarchy level relative to the selected hierarchy threshold for that hierarchy level, wherein the selected hierarchy threshold is less than all storage elements configured for access through a corresponding hierarchical system component; and

identify as blacklisted, based on the evaluation of the aggregated blacklisted storage elements for the corresponding hierarchical system component, all storage elements configured for access through the corresponding hierarchical system component.

5. The system of claim 4 , wherein the plurality of hierarchical system components is selected from a storage node, a storage rack, a storage cluster, a storage site, a network switch, a network, a subnetwork, and a storage system.

6. The system of claim 4 , wherein the blacklist engine is further configured to:

identify, at a plurality of hierarchy levels of the plurality of hierarchical system components, failed storage requests directed to the plurality of storage elements configured for access through the corresponding hierarchical system component; and

store, at a distributed set of hierarchical system components, blacklist data for hierarchical system components of a lower level of the hierarchy levels than each hierarchical system component of the distributed set of hierarchical system components.

7. The system of claim 4 , wherein the blacklist engine is further configured to:

identify as blacklisted, based on aggregate blacklisted hierarchical storage components of a lower level of the hierarchy levels than a selected hierarchical system component, the selected hierarchical system component.

8. The system of claim 7 , wherein the blacklist engine is further configured to:

poll blacklisted hierarchical system components;

remove, based on a response from a responding blacklisted hierarchical system component, the responding blacklisted hierarchical system component from blacklist;

compare, responsive to removing the responding blacklisted hierarchical system component from blacklist, a remaining number of blacklisted hierarchical system components configured for access through a higher-level blacklisted hierarchical system component to a removal threshold for the higher-level blacklisted hierarchical system component; and

remove, responsive to the remaining number being below the removal threshold, the higher-level blacklisted hierarchical system component from the blacklist.

9. The system of claim 1 , further comprising:

a storage path estimator configured to calculate at least one system cost value for each storage element of the plurality of storage elements storing an object set of data blocks, wherein the storage path estimator is further configured to modify the at least one system cost value for each blacklisted storage element; and

a storage path selector configured to select, based on a comparison of the at least one system cost value for each storage element, a subset of the object set of data blocks from which a data object is recoverable.

10. A computer-implemented method, comprising:

identifying, based on at least one failed storage request event, blacklisted storage elements among a plurality of storage elements, wherein the plurality of storage elements are configured for access through a plurality of hierarchical system components in a storage path from at least one controller to the plurality of storage elements;

aggregating blacklisted storage elements for each hierarchical system component of the plurality of hierarchical system components;

selecting a hierarchy threshold for each hierarchy level of the plurality of hierarchical system components;

evaluating the aggregated blacklisted storage elements for each hierarchy level relative to a selected hierarchy threshold for that hierarchy level, wherein the selected hierarchy threshold is less than all storage elements configured for access through a corresponding hierarchical system component;

identifying as blacklisted, based on the evaluation of the aggregated blacklisted storage elements, all storage elements configured for access through the corresponding hierarchical system component; and

determining alternative target storage elements for storage requests to blacklisted storage elements.

11. The computer-implemented method of claim 10 , further comprising:

disassembling a data object into a predetermined number of redundant data blocks comprising an object set for the data object;

distributing the predetermined number of redundant data blocks to the plurality of storage elements while excluding blacklisted storage elements;

retrieving a subset of the predetermined number of redundant data blocks while excluding blacklisted storage elements; and

assembling the data object from the subset of the predetermined number of redundant data blocks.

12. The computer-implemented method of claim 10 , further comprising:

identifying, using a hierarchical address, each storage element of the plurality of storage elements, wherein the hierarchical address includes a plurality of hierarchy level identifiers corresponding to a hierarchical path from at least one controller node to a selected storage element through the plurality of hierarchical system components.

13. The computer-implemented method of claim 10 , wherein the selected hierarchy threshold for each hierarchy level is greater than one storage element configured for access through the corresponding hierarchical system component.

14. The computer-implemented method of claim 10 , wherein the plurality of hierarchical system components is selected from a storage node, a storage rack, a storage cluster, a storage site, a network switch, a network, a subnetwork, and a storage system.

15. The computer-implemented method of claim 10 , further comprising:

identifying, at a plurality of hierarchy levels of the plurality of hierarchical system components, failed storage requests directed to the plurality of storage elements configured for access through the corresponding hierarchical system component; and

storing, at a distributed set of hierarchical system components, blacklist data for hierarchical system components of a lower level of the hierarchy levels than each hierarchical system component of the distributed set of hierarchical system components.

16. The computer-implemented method of claim 10 , further comprising:

identifying as blacklisted, based on aggregate blacklisted hierarchical storage components of a lower level of the hierarchy levels than a selected hierarchical system component, the selected hierarchical system component.

17. The computer-implemented method of claim 10 , further comprising:

polling blacklisted hierarchical system components;

removing, based on a response from a responding blacklisted hierarchical system component, the responding blacklisted hierarchical system component from blacklist;

comparing, responsive to removing the responding blacklisted hierarchical system component from blacklist, a remaining number of blacklisted hierarchical system components configured for access through a higher-level blacklisted hierarchical system component to a removal threshold for the higher-level blacklisted hierarchical system component; and

removing, responsive to the remaining number being below the removal threshold, the higher-level blacklisted hierarchical system component from the blacklist.

18. The computer-implemented method of claim 10 , further comprising:

calculating at least one system cost value for each storage element of the plurality of storage elements storing an object set of data blocks;

modifying the at least one system cost value for each blacklisted storage element; and

selecting, based on a comparison of the at least one system cost value for each storage element, a subset of the object set of data blocks from which a data object is recoverable.

19. A system, comprising:

a plurality of storage elements configured to store a plurality of data blocks;

at least one controller node configured to communicate with a plurality of storage nodes;

a plurality of hierarchical system components in a storage path from at least one controller to the plurality of storage elements;

means for identifying, based on failed storage request events, blacklisted storage elements among the plurality of storage elements;

means for aggregating blacklisted storage elements for each hierarchical system component of the plurality of hierarchical system components;

means for evaluating the aggregated blacklisted storage elements for each hierarchy level against a selected hierarchy threshold for that hierarchy level, wherein the selected hierarchy threshold is less than all storage elements configured for access through a corresponding hierarchical system component;

means for identifying as blacklisted, based on the aggregated blacklisted storage elements for the corresponding hierarchical system component exceeding a hierarchy threshold for a hierarchy level of the corresponding hierarchical system component, storage elements configured for access through the corresponding hierarchical system component; and

means for determining alternative target storage elements for storage requests to blacklisted storage elements.

20. The system of claim 19 , further comprising:

means for polling blacklisted hierarchical system components;

means for removing, based on a response from a responding blacklisted hierarchical system component, the responding blacklisted hierarchical system component from blacklist;

means for comparing, responsive to removing the responding blacklisted hierarchical system component from blacklist, a remaining number of blacklisted hierarchical system components configured for access through a higher-level blacklisted hierarchical system component to a removal threshold for the higher-level blacklisted hierarchical system component; and

means for removing, responsive to the remaining number being below the removal threshold, the higher-level blacklisted hierarchical system component from the blacklist.

Assignments (5)
PATENT COLLATERAL AGREEMENT - A&R LOAN AGREEMENT Recorded Aug 21, 2023
From: WESTERN DIGITAL TECHNOLOGIES, INC.
To: JPMORGAN CHASE BANK, N.A.
Reel/Frame 064715/0001 →
PATENT COLLATERAL AGREEMENT - DDTL LOAN AGREEMENT Recorded Aug 21, 2023
From: WESTERN DIGITAL TECHNOLOGIES, INC.
To: JPMORGAN CHASE BANK, N.A.
Reel/Frame 067045/0156 →
RELEASE OF SECURITY INTEREST AT REEL 052025 FRAME 0088 Recorded Feb 8, 2022
From: JPMORGAN CHASE BANK, N.A.
To: WESTERN DIGITAL TECHNOLOGIES, INC.
Reel/Frame 058965/0699 →
SECURITY INTEREST Recorded Feb 26, 2020
From: WESTERN DIGITAL TECHNOLOGIES, INC.
To: JPMORGAN CHASE BANK, N.A., AS AGENT
Reel/Frame 052025/0088 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Dec 11, 2019
From: DEVRIENDT, STIJN; BOELAERT, LIEN; DE CONINCK, ARNE; DE ROECK, SAM
To: WESTERN DIGITAL TECHNOLOGIES, INC.
Reel/Frame 051250/0205 →
Continuity (1)
Related Publication 20210149579A1 · May 20, 2021