Failure monitoring in distributed computing systems

Arbitration techniques in distributed computing systems are disclosed herein. In one embodiment, a method includes receiving an arbitration request from a first node in the computing system. The first arbitration request indicating that a one-way lease between the first node and a second node in the computing system has failed. The method also includes in response to receiving the arbitration request from the first node, providing an arbitration result to the first node, the arbitration result allowing both the first and second nodes to continue to operate despite of that the one-way lease between the first and second nodes has failed.

BACKGROUND

Distributed computing systems such as datacenters and other computing systems typically include routers, switches, bridges, and other physical network devices that interconnect a large number of servers, network storage devices, and other types of nodes via wired or wireless network links. The individual nodes can host one or more virtual machines or other types of virtualized components accessible to cloud computing clients. The virtual machines can exchange messages such as emails via virtual networks in accordance with one or more network protocols supported by the physical network devices.

SUMMARY

Distributed computing systems typically include a large number of nodes interconnected by a computer network to provide computation, communications, or other types of cloud services. Such distributed computing systems often use lease protocols for failure monitoring and detection. A lease generally refers to a relationship between a pair of nodes established via exchange of periodic messages between the pair of nodes.

Using such leases, one node can detect failure of another node. For example, a first node acting as a subject can send periodic renewal requests to a second node as a monitor. If a proper renewal request is received from the first node, the second node can renew the lease by transmitting a renewal response to the first node and inferring that the first node is operating normally. Such a lease scenario is often referred to as a one-way lease. In other examples, the second node can also act as a subject while the first node acts as a monitor for the second node. As such, the lease between the first and second nodes can be referred to as a two-way lease.

Under certain conditions, the foregoing failure detection scheme can cause nodes to terminate prematurely or unnecessarily, and thus causing a reduction in processing, storage, or other types of resources in distributed computing systems. In a two-way lease example, when communications between the first and second nodes is lost due to network congestion or failure, both the first and second nodes can transmit an arbitration request to an arbitrator. The arbitrator, however, would allow only one of the first or second node to continue to operate or to “live” based on, for example, prior arbitration history and/or whose arbitration request arrives at the arbitrator first. Thus, even when the network congestion or failure can be remedied quickly, the arbitration process would lead to at least one of the first or second node to terminate, and thus reduce capacity in the distributed computing system. Similarly, in the one-way lease example above, communications between the first and second nodes may be temporarily lost due to network congestion or failure. However, if the one-way lease is lost, the first node as a subject would be terminated even though the first node may be operating normally otherwise.

Several embodiments of the disclosed technology can at least ameliorate some drawbacks of the foregoing failure detection scheme. For two-way leases, several embodiments of the disclosed technology can utilize delay and neutral arbitration results to allow both the first and second nodes to continue to operate. For example, the first and second nodes can send first and second arbitration requests, respectively, to an arbitrator when a two-way lease between the first and second nodes is lost. When the arbitrator receives the first arbitration request, unlike in other arbitration schemes, the arbitrator can neither grant nor reject the first arbitration request from the first node. Instead, the arbitrator can issue a delay arbitration result to the first node allowing the first node to continue to operate. The arbitrator would wait for the second arbitration request to arrive from the second node. If the second arbitration request does not arrive within a preset waiting period, the arbitrator can grant the first arbitration request by issuing a positive arbitration result to the first node, and inferring that the second node has failed and is to be terminated. On the other hand, if the second arbitration request arrives within the waiting period, the arbitrator can issue a neutral arbitration result to both the first and second nodes, allowing both the first node and the second node to continue to operate.

In other embodiments of the disclosed technology, a subject node can be in a one-way lease with a monitor node. Once the subject node detects that the one-way lease with the monitor node is lost, for example, due to a communications loss with the monitor node, the subject node can transmit an arbitration request to an arbitrator. In response, the arbitrator can allow the subject node to continue to operate by issuing a neutral arbitration result to the subject node. However, the neutral arbitration result issued to the subject node would not lead to the monitor node to be terminated.

In the foregoing one-way lease example, the monitor node can also send an arbitration request to the arbitrator when the one-way lease with the subject node is lost. If the arbitration request from the monitor node is granted, for example, when no arbitration request from the subject node is received in time, the subject node is to be terminated. Even if the arbitration request from the monitor node is not granted (e.g., another arbitration request has been received from the subject node), the arbitrator can allow the monitor node to continue to operate normally by issuing a neutral arbitration result to the monitor node. In further embodiments, the monitor node can ignore the failed one-way lease with the subject node and continue operation normally without sending the arbitration request to the arbitrator regarding the lost one-way lease.

Several embodiments of the disclosed technology can reduce or limit premature or unnecessary termination of nodes in distributed computing systems by allowing time for the first or second arbitration request to reach the arbitrator by utilizing delay and/or neutral arbitration results. Typically, in distributed computing systems, even when sent simultaneously by the first and second nodes, the first and second arbitration requests can still arrive at the arbitrator at different times due to network traffic conditions, network routes, or other reasons. Thus, one of the first or second arbitration request would likely arrive before the other at the arbitrator. Instead of causing at least one of the first or second node to terminate in arbitration, several embodiments of the disclosed technology can allow both the first and second nodes to live if the first and second arbitration requests arrive at the arbitrator within the preset waiting period, and thus preventing or at least lowering reduction of capacity in distributed computing systems when compared to other arbitration schemes.

DETAILED DESCRIPTION

Certain embodiments of systems, devices, components, modules, routines, data structures, and processes for implementing failure monitoring and/or detection schemes in datacenters or other suitable distributed computing systems are described below. In the following description, specific details of components are included to provide a thorough understanding of certain embodiments of the disclosed technology. A person skilled in the relevant art will also understand that the technology can have additional embodiments. The technology can also be practiced without several of the details of the embodiments described below with reference toFIGS. 1-9.

As used herein, the term a “computing system” generally refers to an interconnected computer network having a plurality of network devices that interconnect a plurality of servers or nodes to one another or to external networks (e.g., the Internet). The term “network device” generally refers to a physical network device, examples of which include routers, switches, hubs, bridges, load balancers, security gateways, or firewalls. A “node” generally refers to a physical computing device configured to implement, for instance, one or more virtual machines or other suitable virtualized components. For example, a node can include a server having a hypervisor configured to support one or more virtual machines or other suitable types of virtual components.

A computer network can be conceptually divided into an overlay network implemented over an underlay network. An “overlay network” generally refers to an abstracted network implemented over and operating on top of an underlay network. The underlay network can include multiple physical network devices interconnected with one another. An overlay network can include one or more virtual networks. A “virtual network” generally refers to an abstraction of a portion of the underlay network in the overlay network. A virtual network can include one or more virtual end points referred to as “tenant sites” individually used by a user or “tenant” to access the virtual network and associated computing, storage, or other suitable resources. A tenant site can have one or more tenant end points (“TEPs”), for example, virtual machines. The virtual networks can interconnect multiple TEPs on different nodes. Virtual network devices in the overlay network can be connected to one another by virtual links individually corresponding to one or more network routes along one or more physical network devices in the underlay network.

Also used herein, the term “lease” generally refers to a subject-monitor relationship between a pair of nodes in a distributed computing system. In certain embodiments, the subject-monitor relationship can be established and/or renewed via exchange of periodic renewal requests and renewal responses between a pair of nodes. In one example, a first node, acting as a subject can send periodic renewal requests to a second node acting as a monitor. If the second node determines that the received renewal request is proper, the second node can establish or renew the lease with the first node by transmitting a renewal response to the first node and inferring that the first node is operating normally. In other embodiments, the subject-monitor relationship can be established and/or renewed via query-response, event monitoring, or other suitable techniques.

A lease can be lost or failed when, for example, an appropriate renewal request (e.g., in an appropriate format) from the first node is not received at the second node within a preset lease period. Upon a loss of the lease, the first and/or second nodes can initiate a process referred to herein as “arbitration” to determine whether one of the first or second node can continue to operate and the other is to be terminated, as described in more detail below. A lease can be a one-way lease when the first node monitors the second node but not vice versa. A lease can be a two-way lease when the second node also acts as a monitor for the first node.

An “arbitration” as used herein generally refers to a process of determining whether one of a pair of nodes can continue to operate while the other must terminate itself when a lease between the pair of nodes is lost. The determination can be based on a type of the lease that is lost, arbitration history between the pair of nodes, or other suitable information. For instance, in a two-way lease example, a first node can transmit an arbitration request to an arbitrator (e.g., a management node) for declaring that a second node has failed when a lease between the first and second nodes is lost. In response, the arbitrator can grant the arbitration request from the first node allowing the first node to continue to operate or to “live” (referred to as a “positive arbitration result”) while the second node is to be terminated, shutdown, or to “die.” Alternately, the arbitrator can reject the arbitration request from the first node (referred to as a “negative arbitration result”) and in response, the first node would terminate itself or die.

Unlike in other arbitration schemes, the arbitrator can also issue a “delay arbitration result” that is neither positive nor negative to the first node in response to receiving the arbitration request from the first node. The delay arbitration result allows the first node to continue to operate or to live, without having the second node to terminate itself. Instead, the arbitrator can determine a health condition of the second node by, for example, monitoring for another arbitration request from the second node. If an arbitration request is received from the second node within a preset waiting period, the arbitrator can issue a “neutral arbitration result” to both the first and second nodes, allowing both the first and second nodes to continue to operate. As such, the second node is also allowed to live even though the arbitration request from the first node arrives at the arbitrator first when the lease between the first and second nodes is lost. Thus, by allowing both the first and second nodes to live, reduction of capacity in distributed computing systems can be lowered when compared to arbitration schemes in which one of the first or second node must terminate itself. Further details of several embodiments of the disclosed technology are described below with reference toFIGS. 1-9.

FIG. 1is a schematic diagram illustrating a distributed computing system100implementing arbitration schemes configured in accordance with embodiments of the disclosed technology. As shown inFIG. 1, the distributed computing system100can include an underlay network108interconnecting a plurality of nodes106, a plurality of tenants101, and an arbitrator126to one another. Even though particular components of the distributed computing system100are shown inFIG. 1, in other embodiments, the distributed computing system100can also include network storage devices, maintenance managers, and/or other suitable components (not shown) in addition to or in lieu of the components shown inFIG. 1.

As shown inFIG. 1, the underlay network108can include multiple network devices112that interconnect the multiple nodes106, the tenants101, and the arbitrator126. In certain embodiments, the nodes106can be organized into racks, action zones, groups, sets, or other suitable divisions. For example, in the illustrated embodiment, the nodes106are grouped into three node sets identified individually as first, second, and third node sets107a-107c.In the illustrated embodiment, each of the node sets107a-107cis operatively coupled to corresponding network devices112a-112c,respectively, which are commonly referred to as “top-of-rack” or “TOR” network devices. The TOR network devices112a-112ccan then be operatively coupled to additional network devices112to form a computer network in a hierarchical, flat, mesh, or other suitable types of topology. The computer network can allow communications among the nodes106, the arbitrator126, and the tenants101. In other embodiments, the multiple node sets107a-107ccan share a single network node112or can have other suitable arrangements.

The nodes106can individually be configured to provide computing, storage, and/or other suitable cloud computing services to the individual tenants101. For example, as described in more detail below with reference toFIG. 2, one of the nodes106can initiate and maintain one or more virtual machines144(shown inFIG. 2) upon requests from the tenants101. The tenants101can then utilize the instantiated virtual machines144to perform computation, communication, and/or other suitable tasks. In certain embodiments, one of the nodes106can provide virtual machines144for multiple tenants101. For example, the node106acan node three virtual machines144individually corresponding to each of the tenants101a-101c.In other embodiments, multiple nodes106can node virtual machines144for the tenants101a-101c.

In accordance with several embodiments of the disclosed technology, the arbitrator126can be configured to determine whether any of a pair of nodes106can be allowed to continue to operate or is must terminate itself when a lease between the pair of nodes106is lost. In certain embodiments, the arbitrator126can include a standalone server, desktop computer, laptop computer, or other suitable types of computing device operatively coupled to the underlay network108. In other embodiments, the arbitrator126can include one of the nodes106. In further embodiments, the arbitrator126can be implemented as one or more network services executing on and provided by, for example, one or more of the nodes106or another server (not shown). Even though only one arbitrator126is shown inFIG. 1, in yet further embodiments, the distributed computing system100can include multiple arbitrators (e.g., as shown inFIGS. 5A-5D). Example components and operations of the arbitrator126are described in more detail below with reference toFIGS. 3A-6.

FIG. 2is a schematic diagram illustrating an overlay network108′ implemented on the underlay network108ofFIG. 1in accordance with embodiments of the disclosed technology. InFIG. 2, only certain components of the underlay network108ofFIG. 1are shown for clarity. As shown inFIG. 2, the first node106aand the second node106bcan each include a processor132, a memory134, and an input/output component136operatively coupled to one another. The processor132can include a microprocessor, a field-programmable gate array, and/or other suitable logic devices. The memory134can include volatile and/or nonvolatile media (e.g., ROM; RAM, magnetic disk storage media; optical storage media; flash memory devices, and/or other suitable storage media) and/or other types of computer-readable storage media configured to store data received from, as well as instructions for, the processor132(e.g., instructions for performing the methods discussed below with reference toFIG. 5A). The input/output component136can include a display, a touch screen, a keyboard, a mouse, a printer, and/or other suitable types of input/output devices configured to accept input from and provide output to an operator and/or an automated software controller (not shown).

The first and second nodes106aand106bcan individually contain instructions in the memory134executable by the processors132, cause the individual processors132to provide a hypervisor140(identified individually as first and second hypervisors140aand140b) and a status agent141(identified individually as first and second status agent141aand141b). Even though the hypervisor140and the status agent141are shown as separate components, in other embodiments, the status agent141can be a part of the hypervisor140or an operating system (not shown) executing on the corresponding node106. In further embodiments, the status agent141can be a standalone application.

The hypervisors140can be individually configured to generate, monitor, terminate, and/or otherwise manage one or more virtual machines144organized into tenant sites142. For example, as shown inFIG. 2, the first node106acan provide a first hypervisor140athat manages first and second tenant sites142aand142b, respectively. The second node106bcan provide a second hypervisor140bthat manages first and second tenant sites142a′ and142b′, respectively. The hypervisors140are individually shown inFIG. 2as a software component. However, in other embodiments, the hypervisors140can be firmware and/or hardware components. The tenant sites142can each include multiple virtual machines144for a particular tenant101(FIG. 1). For example, the first node106aand the second node106bcan both host the tenant site142aand142a′ for a first tenant101a(FIG. 1). The first node106aand the second node106bcan both host the tenant site142band142b′ for a second tenant101b(FIG. 1). Each virtual machine144can be executing a corresponding operating system, middleware, and/or applications.

Also shown inFIG. 2, the computing system100can include an overlay network108′ having one or more virtual networks146that interconnect the tenant sites142aand142bacross multiple nodes106. For example, a first virtual network142ainterconnects the first tenant sites142aand142a′ at the first node106aand the second node106b.A second virtual network146binterconnects the second tenant sites142band142b′ at the first node106aand the second node106b.Even though a single virtual network146is shown as corresponding to one tenant site142, in other embodiments, multiple virtual networks (not shown) may be configured to correspond to a single tenant site146.

The virtual machines144on the virtual networks146can communicate with one another via the underlay network108(FIG. 1) even though the virtual machines144are located or hosted on different nodes106. Communications of each of the virtual networks146can be isolated from other virtual networks146. In certain embodiments, communications can be allowed to cross from one virtual network146to another through a security gateway or otherwise in a controlled fashion. A virtual network address can correspond to one of the virtual machine144in a particular virtual network146. Thus, different virtual networks146can use one or more virtual network addresses that are the same. Example virtual network addresses can include IP addresses, MAC addresses, and/or other suitable addresses.

In certain embodiments, the first and second nodes106aand106bcan be in a one-way lease. Operations of the first and second nodes106aand106bin the one-way lease and the arbitrator126are described in more detail below with reference toFIGS. 3A-3F. In other embodiments, the first and second nodes106aand106bcan also be in a two-way lease. Operations of the first and second nodes106aand106bin the two-way lease and the arbitrator126are described in more detail below with reference toFIGS. 4A-4F. In further embodiments, the first and second nodes106aand106bcan also have an implicit lease, as described in more detail below with reference toFIG. 6.

FIGS. 3A-3Fare block diagrams illustrating components of first and second nodes106aand106bin a one-way lease and an arbitrator126during stages of an arbitration process in accordance with embodiments of the disclosed technology. InFIGS. 3A-3Fand in other Figures herein, individual software components, objects, classes, modules, and routines may be a computer program, procedure, or process written as source code in C, C++, C#, Java, and/or other suitable programming languages. A component may include, without limitation, one or more modules, objects, classes, routines, properties, processes, threads, executables, libraries, or other components. Components may be in source or binary form. Components may also include aspects of source code before compilation (e.g., classes, properties, procedures, routines), compiled binary units (e.g., libraries, executables), or artifacts instantiated and used at runtime (e.g., objects, processes, threads).

Components within a system may take different forms within the system. As one example, a system comprising a first component, a second component, and a third component. The foregoing components can, without limitation, encompass a system that has the first component being a property in source code, the second component being a binary compiled library, and the third component being a thread created at runtime. The computer program, procedure, or process may be compiled into object, intermediate, or machine code and presented for execution by one or more processors of a personal computer, a tablet computer, a network server, a laptop computer, a smartphone, and/or other suitable computing devices.

Equally, components may include hardware circuitry. In certain examples, hardware may be considered fossilized software, and software may be considered liquefied hardware. As just one example, software instructions in a component may be burned to a Programmable Logic Array circuit, or may be designed as a hardware component with appropriate integrated circuits. Equally, hardware may be emulated by software. Various implementations of source, intermediate, and/or object code and associated data may be stored in a computer memory that includes read-only memory, random-access memory, magnetic disk storage media, optical storage media, flash memory devices, and/or other suitable computer readable storage media. As used herein, the term “computer readable storage media” excludes propagated signals.

FIG. 3Aillustrates an example one-way lease161in which a first node106ais a subject node, and a second node106bis a monitor node. As shown inFIG. 3A, the first and second nodes106aand106bcan each include a lease component156having a monitor module152and a subject module154. InFIGS. 3A-3F, the monitor module152aof the first node106aand the subject module152bof the second node106bare not used for the one-way lease161but can be used for two-way leases such as in the example shown inFIGS. 4A-4F.

The monitor module152can be configured to monitor whether a lease is lost with a subject node, e.g., the first node106binFIG. 3A. In certain embodiments, the subject module154aof the first node106acan be configured to periodically transmit a renewal request162to the second node106bvia, for example, the overlay network108′ ofFIG. 2and the underlay network108ofFIG. 1. The monitor module152bof the second node106bcan be configured to analyze the received renewal request162to determine whether the renewal request162is proper or appropriate based on one or more of a time of arrival, a format of the renewal request162, content of the renewal request162, a port at which the renewal request162is received at the second node106b,or other suitable characteristics of the renewal request162.

In response to determining that the renewal request162is proper, the monitor module152bat the second node106bcan be configured to generate and transmit a renewal response164to the first node106a,thereby renewing the lease with the first node106a.Upon receiving the renewal response164, the lease component156aof the first node106acan reset a timer for a lease period, expiration of which would trigger the subject module154ato transmit another renewal request162. If no renewal response164is received within a threshold period, the lease component156aof the first node106acan initiate an arbitration process by transmitting a first arbitration request166a(FIG. 3B) to the arbitrator126(FIG. 3B), as described in more detail below with reference toFIG. 3B.

In response to determining that the renewal request162from the first node106ais not proper, for example, the renewal request162is not received before a lease period (e.g., 120 seconds) has expired, the monitor component152bof the second node106bcan be configured to indicate that the one-way lease161with the first node106ais lost. In response, the lease component156bof the second node106bcan initiate an arbitration process by transmitting a second arbitration request166b(FIG. 3B) to the arbitrator126, as described in more detail below with reference toFIG. 3B.

As shown inFIG. 3B, the arbitrator126can include a processor131and a memory137that are generally similar in structure and function as the processor132and memory134inFIG. 2. The memory137can contain records of arbitration results145from previous arbitration processes. The memory137can also contain instructions that the processor131can execute to provide several components for processing the arbitration requests166aand166b.For example, the processor131can provide an interface component133and an arbitration component135operatively coupled to one another. In other embodiments, the processor131can also provide a calculation component, a display component, or other suitable components.

The interface component133can be configured to transmit and receive messages to/from the first and second nodes106aand106b.In certain embodiments, the interface component133can include a network interface driver, a virtual router, or other suitable modules. The interface component133can also be configured to forward messages, for example, the first and second arbitration requests166aand166bfrom the first and second nodes106aand106bto the arbitration component135for further processing.

As shown inFIG. 3B, the arbitration component135can include an analysis module141and a process module143. The analysis module141can be configured to analyze the received arbitration requests166and determine whether the first and/or second nodes106aand106bcan continue to operate or are to be terminated. The process component143can be configured to issue various types of arbitration results (shown inFIG. 3C) based on analysis results from the analysis module141. Details of analyzing the arbitration requests166are described below using an example in which the first node106ais the subject node and the second node106bis the monitor node in the one-way lease161(FIG. 3A).

In certain embodiments, the analysis module141can be configured to determine whether a received arbitration request166is from a monitor node or from a subject node. For example, as shown inFIG. 3B, the analysis module141can be configured to determine that the first arbitration request166ais from a subject node and the second arbitration request166bis from a monitor node based on indication included in the arbitration requests166, prior lease assignments, previous arbitration results145in the memory137, or other suitable information. In other embodiments, such analysis can be omitted.

When the first arbitration request166aarrives first at the arbitrator126, the analysis module141can be configured to indicate to the process module143that the subject node, i.e., the first node106ais operating normally. The process module143can then issue a neutral arbitration result170to the first node106a,as shown inFIG. 3C. However, the neutral arbitration result170to the first node106bdoes not cause the second node106bto terminate. Instead, the process module143can issue another neutral arbitration result170to the second node106bin response to the second arbitration request166b(FIG. 3B) as well to allow the second node106bto continue to operate. As such, both the first node106aand the second node106bare allow to continue to operate or to live, without reducing capacity in the distributed computing system100.

When the second arbitration request166barrives first at the arbitrator126, the process module143can initially issue a delay arbitration result171to the second node106b,as shown inFIG. 3D. The analysis module141can be configured to then determine whether the subject node, i.e., the first node106ais to be terminated. In one embodiment, the analysis module141can declare that the first node106ais to be terminated if the first arbitration request166a(shown in phantom lines for clarity) from the first node106ais not received within a threshold period after receiving the second arbitration request166b.In other embodiments, the analysis module141can also determine whether the first node106ais to be terminated by querying the first node106a,querying an event log associated with the first node106a,or utilizing other suitable techniques.

In response to determining that the first node106ais to be terminated, the analysis module141can indicate to the process module143accordingly. As shown inFIG. 3D, the process module143can then be configured to grant the second arbitration request166bfrom the second node106bby issuing a positive arbitration result172to the second node106b,allowing the second node106bto continue to operate. The process module143can also be configured to issue a negative arbitration result174, or not issuing any arbitration result at all, to the first node106a, and causing the first node106ato terminate itself.

On the other hand, in response to determining that the first node106ais operating normally, for example, by receiving the first arbitration request166awithin the threshold period, the analysis module141can indicate accordingly to the process module143. As shown inFIG. 3E, the process module143can be configured to issue a neutral arbitration result170to both the first and second nodes106aand106b, and thus allowing both the first and second nodes106aand106bto continue to operate. In further embodiments, the arbitration process illustrated inFIGS. 3D-3Ecan be omitted. Instead, the monitor node, i.e., the second node106bcan simply ignore the loss of the one-way lease with the subject node, i.e., the first node106aand continue to operate normally.

As described above, by utilizing the neutral and delay arbitration results170and171, the first and second nodes106can be allowed to continue to operate when experiencing temporary network issues, as shown inFIGS. 3D and 3E, when the first and second nodes106aand106bare operating normally. In other embodiments, several embodiments of the disclosed technology can also utilize “keep-alive” notifications in order to avoid terminating nodes106due to temporary network issues and reduce failure detection time when a node106is actually down. For example, as shown inFIG. 3F, the first node106acan transmit a keep-alive notification169to the arbitrator126when the first node106adetermines that the one-way lease161(FIG. 3A) with the second node106bis about to be lost. The keep-alive notification169informs the arbitrator126that the first node106is still operating normally or “alive.” The first node106acan determine that the one-way lease161is about to be lost by monitoring an elapsed time after transmitting the renewal request162to the second node106b.If the elapsed time is longer than a threshold (e.g., 5, 10, or 20 milliseconds) and no renewal response164has been received, the first node106acan determine that the one-way lease161would probably be lost soon.

As shown inFIG. 3F, when the one-way lease161is lost, the second node106bcan send the second arbitration request166bto the arbitrator126. In response, the arbitrator126can predict a chance of the other node (e.g., the first node106a) is alive and issue a delay or positive arbitration result171or172based on previously history related to the first and second nodes106aand106b.If the keep-alive notification169is in the history, then the arbitrator126can have a much higher chance to issue the delay arbitration result171to the second node106binstead of a positive arbitration result172. In certain embodiments, to avoid sending unnecessary keep-alive notifications169, the first node106acan limit a number of such keep-alive notifications169by implementing a minimum interval (e.g., 60 seconds) between successive keep-alive notifications169or via other suitable techniques. Even though the keep-alive notification169is described in the context of the one-way lease161, in other embodiments, the keep-alive notification169can also be used in two-way leases, such as that described below with reference toFIGS. 4A-4F, instead of or in addition to utilizing delay arbitration results171.

FIGS. 4A-4Fare block diagrams illustrating components of first and second nodes106aand106bin a two-way lease165and an arbitrator126during stages of an arbitration process in accordance with embodiments of the disclosed technology. InFIGS. 4A-4Fand other figures herein, components similar in structure and function are identified by similar numbers. For example, as shown inFIG. 4A, the first and second nodes106aand106bcan each include a lease component156having a monitor module152and a subject module154that are generally similar to corresponding components shown inFIGS. 3A-3F.

FIG. 4Aillustrates a two-way lease165between the first node106aand the second node106b.As such, in a first one-way lease161a,the first node106ais a subject node and the second node106bis a monitor node. In a second one-way lease161b,the second node106bis a subject node, and the first node106ais a monitor node. Thus, the first node106acan monitor an operating status of the second node106bby monitoring the renewal requests162bfrom the subject module152bof the second node106b.In response, the monitor module154aof the first node106acan transmit a first renewal response164ato the second node106b.The second node106bcan also monitor an operating status of the first node106aby monitoring the renewal requests162afrom the subject module154aof the first node106a.In response, the monitor module152bof the second node106bcan transmit a second renewal response164bto the first node106a.

As shown inFIG. 4B, communications failure or other conditions in the distributed computing system100can cause the two-way lease165to fail. As such, the first and second nodes106aand106bcan stop receiving the first and second renewal requests162aand162b(FIG. 4A) as well as the first and second renewal responses164aand164b.In response to a loss of the two-way lease165, the first and second nodes106aand106bcan individually initiate an arbitration process with the arbitrator126to declare that the other node has failed and is to be terminated. As described in more detail below, several embodiments of the disclosed technology can allow both the first and second nodes106aand106bto continue to operate by utilizing neutral and delay arbitration results170and171, respectively.

FIG. 4Billustrates a scenario in which a first arbitration request166afrom the first node106aarrives at the arbitrator126before the second arbitration request166barrives at the arbitrator126. Unlike in other arbitration schemes in which a node whose arbitration request arrives first is allowed to continue to operate while the other node is to be terminated, several embodiments of the disclosed technology can allow both the first and second nodes106aand106bto continue to operate. For example, as shown inFIG. 4C, instead of granting the first arbitration request166afrom the first node106a,the process module143can be configured to issue a delay arbitration result171to the first node106a.The delay arbitration result171can allow the first node106ato continue to operate while the process module143continues to monitor for a second arbitration request166bfrom the second node106b.

As shown inFIG. 4D, if the second arbitration request166barrives at the arbitrator126within a waiting period (e.g., 5 milliseconds), the process module143can be configured to issue a neutral arbitration result170to both the first and second nodes106aand106b,and allowing both the first and second nodes106aand106bto continue to operate. On the other hand,FIG. 4Eillustrates a situation where the second arbitration request166bdoes not arrive at the arbitrator126during the waiting period. In response, as shown inFIG. 4F, the process module143can be configured to issue a positive arbitration result172to the first node106aand issue a negative arbitration result174(or no arbitration result at all) to the second node106b.

As discussed above, several embodiments of the disclosed technology can reduce unnecessary termination of nodes106by allowing time for the first or second arbitration request166aand166bto reach the arbitrator126. Typically, in distributed computing systems, even when sent simultaneously, the first and second arbitration requests166aand166bcan still arrive at the arbitrator126at different times due to network traffic conditions, network routes, or other reasons. Thus, as discussed in the example above, the first arbitration request166acan arrive before the second arbitration request166bat the arbitrator126. Instead of terminating at least one of the first or second node106aand106bin the arbitration process, both the first and second nodes106aand106bcan be allowed to live if the first and second arbitration requests166aand166barrive at the arbitrator126within the waiting period, and thus preventing reduction of capacity in distributed computing system100.

Even though only one arbitrator126is shown inFIGS. 3B-4F, in other embodiments, the distributed computing system100can also utilize multiple arbitrators.FIGS. 5A-5Dillustrate arbitration based on multiple arbitrators in accordance with embodiments of the disclosed technology. InFIGS. 5A-5C, three arbitrators126a-126care shown for illustration purposes. In other embodiments, the distributed computing system100can utilize five, seven, nine, or any other suitable number of arbitrators.

In certain embodiments, arbitration using multiple arbitrators126can be based on a simple majority of decisions, often referred to as a quorum. For example, as shown inFIG. 5A, if there is a quorum of the positive results172, then the node106can deem the final arbitration result as positive. In another example, as shown inFIG. 5B, if there is a quorum of the negative results174, then the node106can deem the final arbitration result as negative. In yet another example, as shown inFIG. 5C, if the positive result172and the neutral result170form a quorum over the negative result174, the node106can deem the final arbitration result as a neutral arbitration result. In a further example, as shown inFIG. 5D, if the positive result172and the delay result170form a quorum, the node106can deem the overall arbitration result as a delay result171. In certain embodiments, the node106can also check with the arbitrator126bafter a period of time to determine whether the delay result171is modified to a positive result172or a negative result170, and reevaluate for the final arbitration result based thereon. In other embodiments, such modification can be transmitted to the node106by the arbitrator126b.

As discussed above, after a lease is lost, for example, between the first and second nodes106aand106binFIGS. 4A-4F, the first and second nodes106aand106bcan continue to live. Before a new lease is established, failure detection may not be available between the first and second nodes106aand106bif the first and second nodes106aand106bdo not have lease relationships with other nodes106. Thus, if one of the first or second node106aand106bfails, such a failure may not be detected.

FIG. 6is a block diagram illustrating first and second nodes106aand106bin an implicit lease in accordance with embodiments of the disclosed technology. In accordance with several embodiments of the disclosed technology, each node106(FIG. 1) can have an “implicit lease” with one or more other nodes106acting as default monitor(s) for the node106and arbitrate when such an implicit lease expires, even though a formal lease (such as the one-way lease161shown inFIG. 3Aor the two-way lease165shown inFIG. 4A) has never been successfully established. The implicit lease can be based on a logical relationship among pairs of the nodes106in the distributed computing system100ofFIG. 1. As such, a node106can have implicit lease(s) with one or more immediate neighbors that can be any nodes106in the distributed computing system100and designated in various suitable ways. For example, in certain implementations, every node106can maintain implicit leases with a set of other nodes106selected by higher layer logic capable of handling dynamic node join and departure. The nodes106can form a logical ring based on, for instance, node identifications, node numbers, or other suitable parameters of the nodes. Thus, the set of other nodes106can simply include every node's immediate predecessor and successor in the logic ring. In other embodiments, the nodes106can also form a logic mesh, grid, or other suitable types of logical topology.

As such, every node106can detect whether one or more immediate neighbors are acting as a monitor node for itself. If such an implicit lease relationship has been inactive for a duration larger than an implicit threshold (TI), the node106can be configured to perform an implicit arbitration to obtain an approval to live from the arbitrator126. For example, as shown inFIG. 6, if the first node106ais not able to establish a lease relationship with its immediate neighbor, e.g., the second node106b, the first node106acan complete an arbitration once for every TI+AT (where AT is the arbitration timeout, expiration of which causes a requesting node to terminate) to obtain approval from the arbitrator126to continue to operate. The first node106acan determine that the second node106bis not acting as a monitor for the first node106aby, for example, monitoring for any renewal response164(or absence thereof) from the second node106b.In turn, the arbitrator126can issue a neutral arbitration result to the first node106a.The first node106acan report the second node106bhas failed if the second node106bhas not established the lease relationship with the first node106b(or any other nodes106) and the arbitrator126does not have an arbitration record from the second node106bfor such a period, as described in more detail below.

To achieve the above, a lease expiration time can be maintained on a node (e.g., the first node106a) for an immediate neighbor (e.g., the second node106b). Then, an elapsed time since last successful arbitration by, for example, the second node106bcan be determined. For instance, at t1, the first node106acan send a query180to the arbitrator126requesting the arbitration history182associated with the second node106bbased on, for example, the arbitration results145in the memory137. The arbitration history182can include a time value at which the second node106bhas completed an arbitration process with an arbitration result that is not negative, e.g., positive or neutral. The arbitrator126receives the query180at t2, and determines that the last such arbitration result was at t0. The arbitrator126can then respond with a value of t2−t0. At t3, the first node106areceives the response from the arbitrator126. Based on the received response, the first node106acan determine whether the arbitrator126have any record for the second node106bbetween t3−(t2−t0) to t1.

The first node106acan maintain the last time the first node106ahas an active lease relationship as a subject node with its immediate neighbors (e.g., the second node106b), for example, by recording a time when the last renewal response164is received from the second node106b.When such an implicit lease is lost, i.e., no renewal response164has been received before a lease expiration period, this time can be set to the subject side lease expiration time. If the immediate neighbor (e.g., the second node106b) switches to a different node (e.g., another node106inFIG. 1), and before the switch an active lease with a previous immediate neighbor (e.g., the second node106b) is present, such a time can be set to the current time.

Once the first node106alost its implicit lease with an immediate neighbor, e.g., the second node106b,the first node106acan attempt to re-establish the lost lease within TI, which can be 5-10 minutes. If such an implicit lease with the second node106bcannot be established within TI, the first node106acan perform another arbitration for implicit lease to obtain an approval to continue to operate. The first node106acan get a neutral or negative arbitration result. If the arbitration result is negative, the first node106ais terminated. Otherwise, the first node106ahas a period of TI to retry establishing the implicit lease with the second node106b.The arbitrator126can grant the arbitration request from the first node106awithout any history. Alternately, based on historical information for the requesting first node106aand its immediate neighbor (e.g., the second node106b), the arbitrator126can also decide to reject the arbitration request from the first node106a.

The first node106acan also query the arbitrator126to determine whether its immediate neighbor, e.g., the second node106b,is down based on the following conditions:

There is no active lease relationship with the second node106beither on the monitor side or on the subject side;

The second node106bhas become the immediate neighbor of the first node106afor at least TI+(AT+MT)*2, where MT is the maximum lease timeout, during which first node106aremains as the immediate neighbor of the first node106awithout interruption; and

There has been at least an interval of AT since the monitor side lease with first node106aexpired.

Assuming that at time t1, the first node106asends the arbitrator126queries based on the above. According to the query, the second node106bhas not performed a successful arbitration started within (t0, t1−AT), where t0=t1−(TI+AT*2+MT). Based on the foregoing, the arbitrator126can declare that the second node106bhas failed and command the second node106bto terminate.

FIG. 7Ais a flowchart illustrating a process200of arbitrating a lease loss in accordance with embodiments of the disclosed technology. Even though the process200is described in relation to the distributed computing system100ofFIG. 1, in other embodiments, the process200can also be implemented in other suitable systems. As shown inFIG. 7A, the process200includes receiving an arbitration request from a requesting node (e.g., a monitor node) at stage202. The process200can then include a decision stage203to determine whether the other node of the lease (e.g., a subject node) of the lease has failed. In one embodiment, the other node can be declared as failed if an arbitration request from the other node is not received within a threshold period. In other embodiments, the other node can be declared as failed based on event logs, direct queries to the other node, or other suitable techniques. In response to determining that the other node has failed, the process200includes providing a positive arbitration result to the requesting node allowing the requesting node to continue to operate at stage206. In response to determining that the other node has not failed, the process200include issuing a neutral arbitration result to both the requesting node and the other node allowing both the nodes to continue to operate at stage204.

FIG. 7Bis a flowchart illustrating a process210of arbitrating a lease loss by a node in accordance with embodiments of the disclosed technology. As shown inFIG. 7B, the process210includes transmitting an arbitration request upon detecting that a lease is lost at stage212. The process210can then include receiving an arbitration result from an arbitrator at stage214. The process210can include a decision stage216to determine whether the arbitration result is negative. In response to determining that the arbitration result is not negative, e.g., positive, neutral, or delay, the process210can include continuing operation at stage219. In response to determining that the arbitration result is negative or an arbitration result is not received within a threshold period (e.g., an arbitration timeout), the process210includes terminating operations at stage218.

FIG. 7Cis a flowchart illustrating a process240of arbitrating an implicit lease in accordance with embodiments of the disclosed technology. As shown inFIG. 7C, the process240can include receiving an arbitration request from a requesting node at stage242. The arbitration request indicates that node is unable to establish a lease with another node for a predetermined threshold period. The other node is logically related to the requesting node according to a logic relationship and is a default monitor for the requesting node. The process240can then include in response to receiving the arbitration request from the requesting node, providing a neutral arbitration result to the requesting node within an arbitration timeout period. The neutral arbitration result allows the requesting node to continue to operate without causing the other node to terminate itself.

FIG. 7Dis a flowchart illustrating a process260of arbitrating an implicit lease loss by a node in accordance with embodiments of the disclosed technology. As shown inFIG. 7D, the process260includes detecting whether another node is acting as a monitor for the node at stage262, for example by monitoring an elapsed time since last renewal response from the other node. The process260can then include a decision stage262to determine whether the other node is not acting as the monitor for the node for a predetermined threshold period. In response to determining that the other node is acting as the monitor for the node, the process260reverts to detecting whether another node is acting as a monitor for the node at stage262. In response to determining that the other node is not acting as a monitor for the predetermine threshold period, the process260includes transmitting an arbitration request to an arbitrator at stage266.

FIG. 8is a flowchart illustrating a process220of arbitrating a two-way lease in accordance with embodiments of the disclosed technology. As shown inFIG. 8, the process220can include receiving an arbitration request from a first node at stage222. The arbitration request contends that a second node having a lease with the first node has failed. In the illustrated embodiment, the process220can then include starting a waiting period at stage224and providing a delay arbitration result to the first node at stage226. The delay arbitration result neither grant nor reject the received arbitration request from the first node. Instead, the delay arbitration result allows the first node to continue to operate. In other embodiments, the arbitrator may also directly grant or reject the arbitration result from the first node based on, for example, arbitration history of the first node if the first node has been involved in lease loss before.

The process220can then include a decision stage228to determine whether the waiting period has expired. In response to determining that the waiting period has expired, the process220can include providing a positive arbitration result to the first node at stage236. The positive arbitration result supersedes the neutral arbitration result previously issued to the first node. On the other hand, the second node would terminate itself if a neutral or positive arbitration result is not received.

In response to determining that the waiting period has not expired, the process220includes monitoring for another arbitration request from the second node. The process220can then include another decision stage232to determine whether another arbitration request has been received from the second node. In response to determining that another arbitration request has not been received from the second node, the process220reverts to decision stage228to determine whether the waiting period has expired. In response to determining that another arbitration request has been received from the second node, the process220includes providing a neutral arbitration result to both the first and second nodes at stage234. As such, both the first and second nodes can be allowed to continue to operate.

FIG. 9is a computing device300suitable for certain components of the distributed computing system100inFIG. 1. For example, the computing device300can be suitable for the nodes106or the arbitrator126ofFIG. 1. In a very basic configuration302, the computing device300can include one or more processors304and a system memory306. A memory bus308can be used for communicating between processor304and system memory306.

Depending on the desired configuration, the processor304can be of any type including but not limited to a microprocessor (pP), a microcontroller (pC), a digital signal processor (DSP), or any combination thereof. The processor304can include one more levels of caching, such as a level-one cache310and a level-two cache312, a processor core314, and registers316. An example processor core314can include an arithmetic logic unit (ALU), a floating point unit (FPU), a digital signal processing core (DSP Core), or any combination thereof. An example memory controller318can also be used with processor304, or in some implementations memory controller318can be an internal part of processor304.

Depending on the desired configuration, the system memory306can be of any type including but not limited to volatile memory (such as RAM), non-volatile memory (such as ROM, flash memory, etc.) or any combination thereof. The system memory306can include an operating system320, one or more applications322, and program data324. As shown inFIG. 9, the operating system320can include a hypervisor140for managing one or more virtual machines144. This described basic configuration302is illustrated inFIG. 8by those components within the inner dashed line.

The computing device300can have additional features or functionality, and additional interfaces to facilitate communications between basic configuration302and any other devices and interfaces. For example, a bus/interface controller330can be used to facilitate communications between the basic configuration302and one or more data storage devices332via a storage interface bus334. The data storage devices332can be removable storage devices336, non-removable storage devices338, or a combination thereof. Examples of removable storage and non-removable storage devices include magnetic disk devices such as flexible disk drives and hard-disk drives (HDD), optical disk drives such as compact disk (CD) drives or digital versatile disk (DVD) drives, solid state drives (SSD), and tape drives to name a few. Example computer storage media can include volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data. The term “computer readable storage media” or “computer readable storage device” excludes propagated signals and communication media.

The system memory306, removable storage devices336, and non-removable storage devices338are examples of computer readable storage media. Computer readable storage media include, but not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other media which can be used to store the desired information and which can be accessed by computing device300. Any such computer readable storage media can be a part of computing device300. The term “computer readable storage medium” excludes propagated signals and communication media.

The computing device300can also include an interface bus340for facilitating communication from various interface devices (e.g., output devices342, peripheral interfaces344, and communication devices346) to the basic configuration302via bus/interface controller330. Example output devices342include a graphics processing unit348and an audio processing unit350, which can be configured to communicate to various external devices such as a display or speakers via one or more AN ports352. Example peripheral interfaces344include a serial interface controller354or a parallel interface controller356, which can be configured to communicate with external devices such as input devices (e.g., keyboard, mouse, pen, voice input device, touch input device, etc.) or other peripheral devices (e.g., printer, scanner, etc.) via one or more I/O ports358. An example communication device346includes a network controller360, which can be arranged to facilitate communications with one or more other computing devices362over a network communication link via one or more communication ports364.

Specific embodiments of the technology have been described above for purposes of illustration. However, various modifications can be made without deviating from the foregoing disclosure. In addition, many of the elements of one embodiment can be combined with other embodiments in addition to or in lieu of the elements of the other embodiments. Accordingly, the technology is not limited except as by the appended claims.