Method for finding failing components in a large distributed storage system connectivity

Embodiments of the present systems and methods may provide techniques for finding failing components in a distributed storage system. For example a method may comprise measuring problems and health of a plurality of physical and logical components in a distributed storage system, the plurality of physical and logical components forming nodes of the distributed storage system, and generating a graph of the nodes organized in a plurality of hierarchical levels, generating, for each node in the graph, a score summarizing the measured problems and health of the node, determining a highest score at a highest hierarchical level of the graph and determining the associated node as a failing component at a most significant level.

BACKGROUND

The present invention relates to techniques that provide the capability to find failing components in a distributed storage system.

Large distributed storage systems deployed in geographically dispersed environments, such as cloud storage services deployed in the cloud, have become quite common. From the network infrastructure perspective, such a system consists of numerous endpoints (servers) connected to the network access layer through network devices, such as Top of Rack (ToR) switches. Further internetwork connectivity traverses datacenter networks, which in turn are connected by cross-datacenter links and in some cases by trans-continental backbone networks. The exact underlying network links and devices at the network core layers are typically not known to the storage application owners.

Problems may arise when failures occur in the network infrastructure. For example, one step in dealing with a failure is determining the point of failure in the storage system connectivity at the highest level of network hierarchy. This step may be difficult when the connectivity information available is limited to the network application layer connectivity, such as connectivity metrics collected by the endpoints/servers between them. The determination of the point of failure may be important to storage systems operations teams. Similar difficulties may be faced by any other general purpose application owners that face connectivity problems in a hierarchical application deployment with partial knowledge of underlying infrastructure connectivity state.

Accordingly, a need arises for techniques that provide the capability to find failing components in a distributed storage system.

SUMMARY

Embodiments of the present systems and methods may provide techniques for finding failing components in a distributed storage system. The failing component of interest is the one that represents the problem at the highest possible level of aggregation/hierarchy, while representing the most significant failure problem currently occurring in the system. Such a component may be termed a failing component at the most significant level. Embodiments of the present systems and methods may solve the complex problem of finding failing components in a large distributed storage system by representing the system as a flow network in a graph theory domain. The failing components determination problem may be reduced to a problem in hierarchical flow networks in graph theory. This new representation allows the finding of easy solution to the defined problem.

For example, in an embodiment, a method may be implemented in a computer comprising a processor, memory accessible by the processor, and computer program instructions stored in the memory and executable by the processor, the method may comprise measuring problems and health of a plurality of physical and logical components in a distributed storage system, the plurality of physical and logical components forming nodes of the distributed storage system, and generating a graph of the nodes organized in a plurality of hierarchical levels, generating, for each node in the graph, a score summarizing the measured problems and health of the node, determining a highest score at a highest hierarchical level of the graph and determining the associated node as a failing component at a most significant level, and generating a list of additional failing components, the list ordered by a highest score of each successive node at each successive hierarchical level of the graph.

In embodiments, the measuring may comprise measuring metrics relating to connectivity and processing performance of nodes comprising at least one server, network device, datacenter business offering, geographic location, and the distributed storage system as a whole, and connectivity and communication performance of communication links connecting the nodes. The generated score for each node and link may further be a function of scores of nodes and links lower in the hierarchy of the graph. The generated score for each node and link may be any function of the weights of the lower level nodes and links in the hierarchy. For example, the weighting may be based on an average of the lower levels, such as:

In embodiments, determining the highest score at the highest hierarchical may comprise traversing the nodes of the plurality of hierarchical levels of the graph, starting at a highest hierarchical level, determining a node having a score that is greater than or equal to scores of any nodes in a sub-tree of the node at any lower level, and determining that the determined node is a failing component at a most significant level. Generating a list of additional failing components may comprise removing the sub-tree of the failing component from the graph, traversing the remaining nodes of the plurality of hierarchical levels of the graph, starting at a highest hierarchical level, determining a node having a score that is greater than or equal to scores of any nodes in a sub-tree of the node at any lower level, and determining that the determined node is a failing component at that hierarchical level of the graph. The method may further comprise repeating until no nodes having scores indicating problems remain in the graph.

In an embodiment, a system may comprise a processor, memory accessible by the processor, and computer program instructions stored in the memory and executable by the processor to perform measuring problems and health of a plurality of physical and logical components in a distributed storage system, the plurality of physical and logical components forming nodes of the distributed storage system, and generating a graph of the nodes organized in a plurality of hierarchical levels, generating, for each node in the graph, a score summarizing the measured problems and health of the node, determining a highest score at a highest hierarchical level of the graph and determining the associated node as a failing component at a most significant level, and generating a list of additional failing components, the list ordered by a highest score of each successive node at each successive hierarchical level of the graph.

In an embodiment, a computer program product may comprise a non-transitory computer readable storage having program instructions embodied therewith, the program instructions executable by a computer, to cause the computer to perform a method comprising measuring problems and health of a plurality of physical and logical components in a distributed storage system, the plurality of physical and logical components forming nodes of the distributed storage system, and generating a graph of the nodes organized in a plurality of hierarchical levels, generating, for each node in the graph, a score summarizing the measured problems and health of the node, determining a highest score at a highest hierarchical level of the graph and determining the associated node as a failing component at a most significant level, and generating a list of additional failing components, the list ordered by a highest score of each successive node at each successive hierarchical level of the graph.

DETAILED DESCRIPTION

Embodiments of the present systems and methods may provide techniques for finding failing components in a large distributed storage system. The failing component of interest is the one that represents the problem at the highest possible level of aggregation/hierarchy, while representing the most significant failure problem currently occurring in the system. Such a component may be termed a failing component at the most significant level. Embodiments of the present systems and methods may solve the complex problem of finding failing components in a large distributed storage system by representing the system as a flow network in a graph theory domain. The failing components determination problem may be reduced to a problem in hierarchical flow networks in graph theory. This new representation allows the finding of easy solution to the defined problem.

An exemplary block diagram of a hierarchical flow network representation of a distributed storage system100according to embodiments of the present systems and methods is shown inFIG. 1. In this example, system100may include a plurality of levels, such as the service level102, geography level104, offerings level106, datacenters level108, network devices level110, and devices level112. Devices level112may include a plurality of physical or logical devices on the network, such as servers112A-N and servers112O-X, which may provide the actual storage for system100. Network devices level110may include a plurality of network devices communicatively connecting devices112A-Q, such as ToR switches110A-Q, which may provide communication switching among devices112A-Q. Datacenters level108may include a plurality of datacenter gateways, such as datacenter gateways108A-P, each of which may connect to a plurality of network devices110A-Q and devices112A-Q communicatively connected to form a whole physical or logical entity for storing and providing data. Offering level106may include a plurality of business offerings, such as offerings106A-N, each of which may include logical or physical combinations of datacenters108A-P, and their constituent network devices110A-Q and devices112A-Q, to form a unified arrangement of data storage and provision. Geography level104may include a plurality of geolocations, such as geolocations104A-M, which may be distinct logical or physical geographic locations, each of which may include one or more offerings106or arrangements of offerings, as well as the constituent components, datacenters108A-P, network devices110A-Q, and devices112A-Q. Service level102may include one or more distributed storage systems102A, which may represent a unified logical or physical system.

An exemplary flow diagram of a process200, according to embodiments of the present techniques, is shown inFIG. 2. It is best viewed in conjunction withFIGS. 1 and 3. Process200begins with202, in which a hierarchical flow network representation, such as that shown inFIG. 1, of a distributed storage system100, may be generated. In the representation, data sources and sinks are the actual storage nodes/servers, such as devices112A-Q. Examples of such devices112A-Q may include SLICESTOR® nodes, which are devices, such as a server or a virtual machine, that are used to store object data, and ACCESSER® nodes, which are devices, such as a server or a virtual machine, that are used to access the SLICESTOR® nodes in IBM® Cloud Object Storage. The rest of the nodes in the flow network may be the physical/logical topology aggregation entities, such as ToR switches, clusters of switches, datacenters, business offerings, geographical locations, etc. Storage nodes, servers112A-Q, may be positioned at the lowest level of hierarchy, devices level112, as leaves of the deployment tree of system100. Further, links may connect the entities. For example, one or more virtual links or paths may connect each nodes in the hierarchy, such as links114connecting servers (devices112A-Q) to switches (network devices110A-Q) and paths116connecting switches (network devices110A-Q) to datacenter gateways108A-P.

At204, node scores may be generated. For example, at204A, for each node at each level102-112, connectivity and other performance metrics may be measured to determine the presence or absence of problems and the health of each node and its associated links. A score summarizing the problems and health of each node/link, may be generated for each node, which, as mentioned above, form the leaves of the deployment tree of system100. For example, the greater the problems and/or worse the health of the node/link, the higher the score may be. For example, as shown inFIG. 3, node302may have a score of 0, indicating no problems, while node304may have a score of 0.2, which does indicate a problem. As servers112A-Q are at the lowest level, device level112, of the hierarchy, the score for each servers112A-Q may be determined, for example, according to:

At204B, each node/link may further be scored as a function of scores of the nodes/links further down the hierarchy. The weighting may be any function of the scores of the lower level nodes/links. For example, for each node, the average score of the children of that node/link, that is the average score of the leaves in the subtree of the node/link, may be determined. For example, as shown inFIG. 3, the score for each switch110A-Q may be determined according to:

WeightSwitch=∑ConnectedServers⁢WeightServer#⁢ConnectedServers
and similarly for higher levels. This may be generalized to:

Weightlevel⁢⁢n=∑nodes⁢⁢in⁢⁢level⁢⁢n-1⁢Weightlevel⁢⁢n-1#⁢nodes⁢⁢in⁢⁢level⁢⁢n-1
For example, as shown inFIG. 3, the servers connected to switch306all have scores of 1, which yields a score for switch306of 1. Datacenter304has five connected switches, four with scores of 0 and one with a score of 1, which yields a score for data center304of 0.2.

At206, the highest score at the highest hierarchy level may be determined. This score is associated with the failing component that is at the most significant level in the hierarchy. For example, at206A, the graph of the hierarchy may be traversed starting from the root node, distributed storage system102A, at service level102. At206B, the highest level at which the score is not getting higher when going down the tree may be found. That is, there may be a level in the hierarchy at which, for example, the score of the node at that level is greater than or equal to the scores of any nodes in the sub-tree of the node at any lower level. For example, as shown inFIG. 3, the root node312has a score of 0.005, the geographic level node310has a score of 0.017, the offering level node308has a score of 0.07, the datacenter level node304has a score of 0.2, the switch level node306has a score of 1, and all the server level nodes314have scores of 1. Thus, switch level node306is the node at that highest level of the hierarchy at which the score in not getting higher. At206C, it may be determined that the node/link or group of nodes and their links are the failing component at the most significant level. For example, as shown inFIG. 3, switch level node306may be determined to be the failing component at the most significant level.

At208, an ordered list of failing components may be generated. For example, the ordered list of failing components may be ordered by their error significance and level of hierarchy. To generate such a list, at208A, the sub-tree rooted at the failing component found206C may be removed. At208B, the graph may be traversed starting from the root node, distributed storage system102A, at service level102. At208C, the highest level at which the score is not getting higher when going down the tree may be found. At208D, it may be determined that the node/link or group of nodes and their links are the failing component(s) at the next most significant level. At208E, the process208may be repeated starting at208A as long as additional nodes/links with problems or errors are found. When no further problems or errors are found, the process may stop. For example, as shown inFIG. 3, the ordered list may be as follows: switch level node306as the failing component at the most significant level, then datacenter level node304, then offering level node308, then geographic level node310, and finally root node312.

An exemplary block diagram of a computer system402, in which processes involved in the embodiments described herein may be implemented, is shown inFIG. 4. Computer system402may be implemented using one or more programmed general-purpose computer systems, such as embedded processors, systems on a chip, personal computers, workstations, server systems, and minicomputers or mainframe computers, or in distributed, networked computing environments. Computer system402may include one or more processors (CPUs)402A-402N, input/output circuitry404, network adapter406, and memory408. CPUs402A-402N execute program instructions in order to carry out the functions of the present communications systems and methods. Typically, CPUs402A-402N are one or more microprocessors, such as an INTEL CORE® processor.FIG. 4illustrates an embodiment in which computer system402is implemented as a single multi-processor computer system, in which multiple processors402A-402N share system resources, such as memory408, input/output circuitry404, and network adapter406. However, the present communications systems and methods also include embodiments in which computer system402is implemented as a plurality of networked computer systems, which may be single-processor computer systems, multi-processor computer systems, or a mix thereof.

Input/output circuitry404provides the capability to input data to, or output data from, computer system402. For example, input/output circuitry may include input devices, such as keyboards, mice, touchpads, trackballs, scanners, analog to digital converters, etc., output devices, such as video adapters, monitors, printers, etc., and input/output devices, such as, modems, etc. Network adapter406interfaces device400with a network410. Network410may be any public or proprietary LAN or WAN, including, but not limited to the Internet.

The contents of memory408may vary depending upon the function that computer system402is programmed to perform. In the example shown inFIG. 4, exemplary memory contents are shown representing routines and data for embodiments of the processes described above. However, one of skill in the art would recognize that these routines, along with the memory contents related to those routines, may not be included on one system or device, but rather may be distributed among a plurality of systems or devices, based on well-known engineering considerations. The present communications systems and methods may include any and all such arrangements.

In the example shown inFIG. 4, memory408may include representation generation routines412, scoring routines414, most significant/ordered list generation routines416, hierarchy data418, and operating system420. Representation generation routines412may include software routines to perform generate a hierarchical flow network representation of a distributed storage system, as described above. The generated representation may be stored as hierarchy data418. Scoring routines414may include software routines to measure connectivity and other performance metrics to determine the presence or absence of problems and the health of each node and its associated links and to generate scores score summarizing the problems and health of each node/link and further as a function of the nodes/links further down the hierarchy, as described above. Most significant/ordered list generation routines416may include software routines to perform determine the failing component at the most significant level and to generate ordered list of failing components, as described above. Operating system420may provide overall system functionality.

As shown inFIG. 4, the present communications systems and methods may include implementation on a system or systems that provide multi-processor, multi-tasking, multi-process, and/or multi-thread computing, as well as implementation on systems that provide only single processor, single thread computing. Multi-processor computing involves performing computing using more than one processor. Multi-tasking computing involves performing computing using more than one operating system task. A task is an operating system concept that refers to the combination of a program being executed and bookkeeping information used by the operating system. Whenever a program is executed, the operating system creates a new task for it. The task is like an envelope for the program in that it identifies the program with a task number and attaches other bookkeeping information to it. Many operating systems, including Linux, UNIX®, OS/2®, and Windows®, are capable of running many tasks at the same time and are called multitasking operating systems. Multi-tasking is the ability of an operating system to execute more than one executable at the same time. Each executable is running in its own address space, meaning that the executables have no way to share any of their memory. This has advantages, because it is impossible for any program to damage the execution of any of the other programs running on the system. However, the programs have no way to exchange any information except through the operating system (or by reading files stored on the file system). Multi-process computing is similar to multi-tasking computing, as the terms task and process are often used interchangeably, although some operating systems make a distinction between the two.

The present invention may be a system, a method, and/or a computer program product at any possible technical detail level of integration. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the present invention. The computer readable storage medium can be a tangible device that can retain and store instructions for use by an instruction execution device.