JP2015215754A - CLUSTER SYSTEM AND Split-BrainSyndrome GENERATION PREVENTION METHOD - Google Patents

Abstract

[PROBLEMS] To prevent a split-brain syndrome and prevent a situation in which a privileged node is not determined as much as possible when determining a privileged node. A distributed system 100 includes an external server 2 outside a cluster 10, and the external server 2 aggregates information on the number of members of each subcluster from privileged node candidates of each subcluster from which the cluster 10 is divided. If there are multiple sub-clusters with the largest number of members, or multiple sub-clusters with the largest and equal number of members, approval of privilege node promotion is granted to privileged node candidates of one sub-cluster selected based on specific logic. Notify the other privileged node candidates of the rejection. If a privileged node candidate of each sub-cluster receives an acknowledgment from the external server 2, it is promoted to a privileged node to build the cluster 10, and if it receives a denial notification from the external server 2, disassembles the sub-cluster. To do. [Selection] Figure 7

Description

  The present invention relates to a cluster system and a split-brain syndrome generation prevention method for preventing split-brain syndrome that occurs due to a path failure or the like in a distributed system.

In recent years, with the rise of cloud computing, it is required to efficiently process and manage a large amount of data. Thus, distributed processing technology has been developed that realizes efficient processing by operating a plurality of servers in a coordinated manner.
When performing distributed processing, there is a case where a cooperative operation is performed between servers (hereinafter referred to as nodes) constituting a distributed system (hereinafter referred to as a cluster). For example, in a system that requires high availability, when a failure occurs in a certain node, a collaborative operation is performed such that the replicated data is held in another node (data redundancy) so that processing can be continued in another node. An example is given. In order to carry out such a cooperative operation, it is necessary for all the nodes participating in the cluster to grasp the information (IP address, etc.) of the nodes constituting the cluster.

  Therefore, there is a node management method in which one of the nodes constituting the cluster is selected as a node having a privilege to manage the node (hereinafter referred to as a privileged node). Here, all nodes know the same rule for selecting a privileged node in advance, and when a failure occurs in a privileged node, one of the remaining nodes takes over the privilege. Thus, by closing the node in the cluster and performing node management, the privileged node does not become a single point of failure (SPOF). When a node failure occurs, it is notified to a privileged node (the node that will be the next privileged node when a privileged node fails), information on managed nodes is updated, and all remaining nodes are notified. .

  In a cluster system, communication between nodes constituting the cluster system may be disconnected due to a route failure or the like, and NW (network) partitioning may occur. When NW partitioning occurs, there is a possibility that a split-brain syndrome in which the cluster is separated into a plurality of sub-clusters and each continues to operate.

FIG. 16 is a diagram illustrating an example of occurrence of Split-Brain Syndrome and an example of elimination of Split-Brain Syndrome.
As shown in FIG. 16 (a), in a cluster system in which nodes A to E, which are server groups constituting a cluster, are interconnected to operate like a single server, nodes A and B and nodes C to E Suppose that the path connecting the two has failed. In FIG. 16 (b), a mark indicating that the path has failed is attached to the path connecting the nodes A and B and the nodes C to E. In addition, a crown indicating that the node is a privileged node of the cluster is attached to the node A of the cluster. In the case of FIG. 16B, the nodes A and B and the nodes C to E constituting the cluster are divided by the path failure, and the nodes C and E appear to have failed from the nodes A and B. From E, nodes A and B appear to have failed.

  The cluster system is equipped with a failure prevention mechanism that dynamically reconfigures a cluster and maintains services even when a failure occurs. As indicated by reference symbol a in FIG. 16B, a privileged node (node A and node C here) is selected for each of the sub-clusters, and a split-brain syndrome is generated in which the sub-clusters continue to operate. In FIG. 16B, a crown indicating that the node A of one sub-cluster is a privileged node of the cluster is attached, and a crown indicating that the node C of the other sub-cluster is a privileged node of the cluster. It is marked. Such a situation is an example of split-brain syndrome.

  If Split-Brain Syndrome occurs, it may lead to problems such as data consistency failure and service interruption. For example, it is possible to cause various fatal phenomena such as inability to access services from outside the cluster, conflicts in writing to the database of multiple nodes, destroying the database, and inconsistency. There is sex.

On the other hand, there is a distributed arbitration protocol as a method for selecting one master (privileged node) from a plurality of data management devices or a method for aligning the data states held by the data management device to the same. As a distributed arbitration protocol, for example, a Paxos algorithm used for a database or a file system is known (see Non-Patent Document 1).
Non-Patent Document 2 describes Master Lease, which is a predetermined lease period.

  When NW partitioning occurs and the cluster is divided into a plurality of sub-clusters, a Paxos algorithm or the like is used to construct a cluster using privileged node candidates of sub-clusters that satisfy a majority of the original cluster as privilege nodes.

As indicated by reference symbol a in FIG. 16C, the Paxos algorithm disassembles when the number of members of the original cluster is less than half. As indicated by reference symbol b in FIG. 16C, when a majority of the number of members of the original cluster is satisfied, a cluster is constructed.
In this way, the Paxos algorithm eliminates the split-brain syndrome by dismantling others while leaving the subcluster in which the majority of members remain.

Lamport, L. “The part-time parliament,” ACM Transactions on Computer Systems 16, 2 (1998), pp.133-169. Gray, C., Cheriton, D. “Leases: An efficient fault-tolerant mechanism for distributed file cache consistency,” In Proceedings of the 12th ACM Symposium on Operating Systems Principles (1989), pp. 202-210.

However, the split-brain syndrome detection / resolution method using the Paxos algorithm has the following problems.
17 and 18 are diagrams for explaining the problem of the split-brain syndrome detection / resolution method using the Paxos algorithm.

(Problem 1)
As shown in FIG. 17A, there is one privileged node (node A in this case) that manages the nodes A to F constituting the cluster for each cluster. As shown in FIG. 17B, it is assumed that the path connecting the nodes A to C and the nodes D to F has a path failure. A path connecting the nodes A to C and the nodes D to F is marked with a cross indicating that a path failure has occurred. In addition, a crown mark indicating that the node is a candidate for a privileged node of the cluster is attached to the node A and the node D of the cluster.

  As shown by reference symbol a in FIG. 17B, it is assumed that the cluster is divided into two sub-clusters by NW division, and that the number of members of the two sub-clusters is the same number (half of the original cluster). To do.

  In this case, the Paxos algorithm corresponds to a case where the number of members is less than half of the number of members of the original cluster, and there are no more sub-clusters than half of the number of members of the original cluster, as indicated by reference numeral a in FIG. So dismantle everything. In other words, if the cluster is divided into two sub-clusters by NW division and the number of members of the two sub-clusters is the same number (half of the original cluster), the number of clusters that can be operated can be secured. Nevertheless, the entire cluster is dismantled.

(Problem 2)
As shown in FIG. 18A, there is one privileged node (node A here) that manages the nodes A to E constituting the cluster for each cluster. As shown by the symbol a in FIG. 18B, the path connecting the nodes A and B and the nodes C to E and the path connecting the node C and the nodes A, B, D, and E are divided (multiple division). Suppose that A plurality of divided paths are marked with a cross indicating that a path failure has occurred. In addition, a crown mark is attached to node A, node C, and node D of the cluster indicating that they are privileged node candidates of the cluster.

  As shown by a symbol a in FIG. 18B, a case is assumed in which a plurality of NW divisions occur to divide a cluster into a plurality of clusters, and there are no subclusters in which a majority of the original clusters remain.

In this case, the Paxos algorithm corresponds to the case where the number of members of the original cluster is less than half, and as shown by the symbol a in FIG. 18C, there are no more subclusters than half of the number of members of the original cluster. So dismantle everything. That is, if multiple NW partitioning occurs and the cluster is divided into multiple clusters, and there is no sub-cluster in which a majority of the original cluster remains, the entire cluster is dismantled and the service cannot be partially continued. .
As described above, in the split-brain syndrome detection / resolution method using the Paxos algorithm, when the number of divided sub-cluster members is the same number (half of the original cluster) or more than half of the number of members of the original cluster If the cluster does not exist, the privileged node cannot be determined and the entire cluster is dismantled.

  The present invention has been made in view of such a background, and the present invention prevents split-brain syndrome while preventing privileged nodes from being determined as much as possible when performing privileged node determination. It is an object of the present invention to provide a cluster system and a split-brain syndrome prevention method.

  In order to solve the above-mentioned problem, the invention according to claim 1 is a privileged node having a privilege to manage a node from among a plurality of nodes constituting a cluster by applying a majority vote distributed consensus forming algorithm including a Paxos algorithm. The external server that manages the privileged node is provided outside the cluster, and the external server includes the number of members of each subcluster from the privileged node candidates of each subcluster from which the cluster is divided. If there are multiple sub-clusters with the largest number of members or those with the largest and equal number of members, privilege nodes are selected as privilege node candidates for one sub-cluster selected based on specific logic. A management unit for notifying the approval of the promotion to the other privileged node candidates; When the right node candidate receives a notice of approval from the external server, the right node candidate is promoted to a privileged node to build a cluster, and when a notice of denial is received from the external server, the sub-cluster is disassembled. To do.

  The invention according to claim 8 is a cluster system that selects a privileged node having a privilege to manage a node from among a plurality of nodes constituting a cluster by applying a majority vote consensus building algorithm including a Paxos algorithm. A split-brain syndrome prevention method, wherein an external server that manages the privileged node is provided outside the cluster, and the external server determines each subcluster from a privileged node candidate of each subcluster from which the cluster is divided. A step of aggregating information on the number of members and a sub-cluster with the largest number of members, or a privileged node of one sub-cluster selected based on specific logic when there are multiple sub-clusters with the largest number of members and the same number of members A step of notifying the candidate of the privilege node promotion approval and notifying the other privileged node candidates of the rejection. The privileged node candidate of the sub-cluster receives a notification of approval from the external server, promotes to a privileged node to build a cluster, and receives a rejection notification from the external server, A split-brain syndrome prevention method for a cluster system, characterized by executing a step of disassembling a sub-cluster.

  By doing so, it is possible to prevent a situation where a privileged node is not determined as much as possible when performing privileged node determination while preventing split-brain syndrome. For example, when a plurality of NW divisions occur and the cluster is divided into a plurality of clusters, and there is no sub-cluster in which a majority of the original clusters remain, the Paxos algorithm disassembles the entire cluster. For example, even when there is no sub-cluster that satisfies the majority, it is possible to prevent the entire cluster from being disassembled and continue operation.

  Further, the invention according to claim 2 is that, when the privileged node candidate of the sub-cluster does not receive an approval or rejection response from the external server and the number of members of the sub-cluster satisfies a majority, A cluster is autonomously constructed as a privileged node by applying an algorithm.

  According to such a configuration, when there is no “acknowledge / deny” response from the external server due to some failure, if the majority of sub-cluster members satisfy the majority, Paxos does not wait for a response from the external server. A privileged node can autonomously construct a cluster by using a majority vote distributed consensus building algorithm including an algorithm.

  Further, the invention according to claim 3 is that when a privileged node candidate of the sub-cluster has not responded to the approval or rejection from the external server and the number of members of the sub-cluster does not satisfy the majority, a predetermined timeout period has elapsed. The sub-cluster is dismantled autonomously later.

  According to such a configuration, if there is no “acknowledge / decline” response from the external server due to some failure, and the subcluster member count does not satisfy the majority, the subcluster autonomously responds with a response timeout from the external server. Can be dismantled. Therefore, Split-Brain Syndrome can be prevented when there are other sub-clusters that have a majority of members.

  According to a fourth aspect of the present invention, the privileged node information indicating that the cluster is a privileged node and the number of cluster members are periodically updated when the number of cluster members changes. It is characterized by reporting to.

  According to such a configuration, the external server receives the periodic report to grasp the number of members of the entire cluster before the division, receives the report when the number of cluster members changes, and receives the current cluster state (privileged node). Information, the number of cluster members).

  According to a fifth aspect of the present invention, the privileged node candidate of the subcluster includes privileged node candidate information indicating that the number of members of the subcluster is a privileged node candidate and the number of subcluster members. A node promotion request is issued to the external server.

  According to such a configuration, the external server can grasp a node that is a privileged node candidate and the number of sub-cluster members of the sub-cluster.

  In the invention according to claim 6, the external server can communicate when the total number of sub-cluster members reported from all privileged node candidates capable of communication is less than half of the total number of members of the cluster. This is characterized in that the rejection is uniformly notified to a privileged node candidate.

  According to such a configuration, a uniform “denial” is notified to privileged node candidates communicable with the external server, so that there exists a sub-cluster that satisfies a majority when it cannot be detected from the external server. Even if a privileged node is elected, split-brain syndrome can be surely prevented.

  Further, the invention according to claim 7 is directed to a case where the total number of sub-cluster members reported from all the privileged node candidates capable of communication is less than half of the total number of members of the cluster. Notifying the terminal of the privileged node candidate, receiving a notification of acceptance or rejection of the privileged node candidate from the maintenance person terminal, and notifying the approval or rejection of the privileged node candidate according to the determination notification To do.

  According to such a configuration, when the total number of members of the sub-cluster reported from all the privileged node candidates capable of communication is less than half of the total number of members of the cluster, a uniform “denial” Compared with the case of notifying ", it is possible to continue more appropriate operation while preventing split-brain syndrome.

  According to the present invention, it is possible to prevent a state in which a privileged node is not determined as much as possible when performing privileged node determination while preventing split-brain syndrome.

It is a figure which shows the structural example of the distributed system which concerns on this embodiment. It is a figure which shows the function example of the node which comprises the cluster which concerns on this embodiment. It is a figure which shows an example of the node management table of the node which comprises the cluster which concerns on this embodiment. It is a figure which shows the example of a setting of the alive monitoring table of the node which comprises the cluster which concerns on this embodiment. It is a figure which shows the function example of the external server which concerns on this embodiment. It is a figure which shows operation | movement of the distributed system containing the cluster which concerns on this embodiment. It is a figure which shows operation | movement of the distributed system containing the cluster which concerns on this embodiment. It is a figure which shows operation | movement when a failure generate | occur | produces in the external server of the distributed system containing the cluster which concerns on this embodiment. It is a figure which shows operation | movement when a failure generate | occur | produces between a part of cluster of the cluster system which concerns on this embodiment, and an external server. It is a figure which shows operation | movement when a failure generate | occur | produces between a part of cluster of the cluster system which concerns on this embodiment, and an external server. It is a figure explaining the procedure of the Split-Brain Syndrome generation | occurrence | production prevention method using the external server of the cluster system which concerns on this embodiment. It is a flowchart which shows the management process of the privilege node / privilege node candidate of the cluster system which concerns on this embodiment. It is a flowchart which shows the main process of the privilege node selection function of the external server of the cluster system which concerns on this embodiment. It is a flowchart which shows the timer process of the privileged node selection function of the external server of the cluster system which concerns on this embodiment. It is a sequence diagram explaining the flow of privileged node selection of the cluster system which concerns on this embodiment. It is a figure which shows the generation example of Split-Brain Syndrome of a cluster system, and the cancellation example of Split-Brain Syndrome. It is a figure explaining the subject of the Split-Brain Syndrome generation | occurrence | production prevention method using the Paxos algorithm of a cluster system. It is a figure explaining the subject of the Split-Brain Syndrome generation | occurrence | production prevention method using the Paxos algorithm of a cluster system.

  A cluster system and the like in a mode for carrying out the present invention (hereinafter referred to as “the present embodiment”) will be described below with reference to the drawings.

(Embodiment)
[Configuration of distributed system]
FIG. 1 is a diagram illustrating a configuration example of a distributed system including clusters according to the present embodiment.
As shown in FIG. 1, a distributed system 100 (cluster system) includes a plurality of nodes 1 constituting a cluster 10, an external server 2 that is provided outside the cluster 10 and manages privileged nodes, a network 20, And a client 30.

The node 1 is a physical device such as a computer that constitutes the cluster 10. The node 1 may be a logical device such as a virtual machine. In FIG. 1, the node 1 is represented by a physical server image. The node 1 has a function of providing a service by receiving a message transmitted from the client 30, executing a process, and returning response information (service information) to the client 30.
The external server 2 is a management server outside the cluster 10 that determines privileged nodes.

  In order for the nodes 1 constituting the cluster 10 to operate in cooperation, each node 1 processes and holds data based on data (management information) that requires consistency between the nodes 1. Yes. For example, data (management information) that requires consistency includes information on a group of nodes constituting the cluster 10. Specifically, data (management information) that requires consistency includes a node management table (to be described later) in which the node identifier of each node 1 is stored, and a target node for alive monitoring. There is a life and death monitoring table (listed below).

In order for the user to enjoy the network service, the client 30 transmits a message (input information or the like) to the service to the cluster 10 or receives and displays response information (service information) corresponding to the message from the cluster 10. It has a function to do. The client 30 has an input / output unit (not shown), a control unit, a storage unit, and the like.
A message from the client 30 is transmitted to any one of the nodes 1 constituting the cluster 10 via the network 20. Each node 1 performs message processing and provides a service to the client 30.

  Instead of directly transmitting a message from the client 30 to the node 1, a message may be distributed to the node 1 by installing a load balancer or the like between the client 30 and the node 1. This load balancer (not shown) has a function of distributing a message transmitted from the client 30 by a simple round robin method or the like.

[node]
Next, a function example of the node 1 will be described with reference to FIG. 2 (see FIG. 1 as appropriate).
FIG. 2 is a diagram illustrating a function example of the node 1.
As illustrated in FIG. 2, the node 1 includes a processing unit 11, a storage unit 12, and a communication unit 13.
The processing unit 11 includes a CPU (Central Processing Unit) and a main memory (not shown), expands a program stored in the storage unit 12 to the main memory, a node management unit 111, a message processing unit 112, and an alive monitoring unit. 113, the privileged node selection unit 114, and the cluster leave instruction unit 115 are realized as functions.

The storage unit 12 includes a memory, a hard disk, and the like, and includes a node management table (node management information) 121, a life / death monitoring table (life / death monitoring information) 122, and a data storage unit 123. The data storage unit 123 stores data managed by the node 1, the proposal number b of the Paxos algorithm, and the proposal content V (details will be described later).
The communication unit 13 is a communication interface for transmitting and receiving messages and response information.

<Node management unit 111>
The node management unit 111 updates the information of the node 1 constituting the cluster 10 and manages it as the node management table 121 when the node 1 is added to or removed from the cluster 10. Here, “update of node information” is based on failure information (described later) of node 1 notified from the alive monitoring unit 113, node participation information from the additional node 1, etc., when the node itself is a privileged node. This means that the node management table 121 (see FIG. 3) is updated and the information is distributed to all the remaining nodes 1. Further, when the node itself is a node 1 other than the privileged node, it means that the update information of the node 1 distributed from the privileged node is reflected in the node management table 121.
The node information needs to uniquely identify at least the node 1 constituting the cluster 10 of each node 1 (for example, an IP (Internet Protocol) address if the node 1 constituting the cluster 10 is in the same subnet). Corresponding information (for example, cluster participation time) is included accordingly.

<Node management table 121>
Next, an example of the node management table 121 will be described with reference to FIG. 3 (see FIG. 2 as appropriate).
FIG. 3 is a diagram illustrating an example of the node management table 121.
The node management table 121 is stored in the storage unit 12 and stores an IP address (node identifier) 131 and a cluster participation time 132 as ancillary information as necessary.

The IP address 131 is assigned so as to identify the node 1, and uniquely corresponds to an ID space ID or a virtual ID used in, for example, the management (distribution) method of the consistent hashing method. It may be.
The cluster participation time 132 stores the cluster participation time of the node 1.

<Message processing unit 112>
Returning to FIG. 2, the message processing unit 112 provides a service by executing processing of the received message and returning a processing result to the client. At this time, as shown in the above-described example, in a system in which replicated data is arranged in another node 1, rules set in advance with reference to the node management table 121 (for example, the node management table 121 own A collaborative operation may be performed in which a duplication destination is specified based on the nodes in the lower row and data duplication is arranged.

<Life and death monitoring unit 113>
The life and death monitoring unit 113 refers to the life and death monitoring table 122 and always exchanges a life and death monitoring signal with a designated node (for example, a node in the next row of itself), and detects a failure of the node 1 constituting the cluster 10. To detect. When a failure of the node 1 is detected, the alive monitoring unit 113 notifies the node management unit 111 when the node itself is a privileged node, and notifies the privileged node when the node itself is other than the privileged node. The alive monitoring unit 113 updates the alive monitoring table 122 in synchronization with the update of the node management table 121 when the node 1 constituting the cluster 10 is added or removed.

<Privileged node selection unit 114>
The privileged node selection unit 114 selects a privileged node by applying the Paxos algorithm, which is a majority protocol that guarantees that one proposal can be agreed only in a series of flows until the algorithm is completed.

  The privileged node selection unit 114 is activated in conjunction with the life and death monitoring unit 113, that is, in conjunction with a trigger from the life and death monitoring unit 113. The privileged node selection unit 114 starts operation at that stage when the life and death monitoring unit 113 finds that a failure has occurred in a certain member (node). In order to update the node management table 121, the privileged node selection unit 114 executes the Paxos algorithm once so as to be linked with information discovered (detected) by the alive monitoring unit 113. The privileged node selection unit 114 only needs to move in conjunction with the life / death monitoring unit 113, and may be configured to be included in the life / death monitoring unit 113. Specific processing of the privileged node selection unit 114 using the Paxos algorithm will be described later.

≪Privilege node≫
Here, the privileged node will be described.
The privileged node is uniquely determined according to a predetermined rule. Specifically, the privileged node is uniquely determined in accordance with a rule such that the node management table 121 or the alive monitoring table 122 starts with the node in the top row or starts with the node with the oldest cluster participation time. Similarly, the candidate node that will be the next privileged node is uniquely determined according to the predetermined rule.

  For example, when a failure occurs in a privileged node, the next candidate has a right to become a new privileged node, such as the node in the second row in the table or the node with the second oldest cluster participation time. Since all members (nodes) have the same life and death monitoring table 122 and node management table 121, the next privileged member candidate can be uniquely identified.

<Life monitoring table 122>
Next, a setting example of the life and death monitoring table 122 will be described with reference to FIG.
FIG. 4 is a diagram illustrating a setting example of the life and death monitoring table 122.
The alive monitoring table 122 is created for each physical device, and lists nodes to be monitored. The alive monitoring table 122 stores the IP address of the monitoring target node.
The alive monitoring table 122 is selected at least once for each physical member in consideration of a pattern in which nodes are configured for each logical device. That is, by selecting at least once for each physical member, there is no member (node) that is not monitored for life and death.

  The life and death monitoring table 122 is updated synchronously with the node management table 121 when the node 1 constituting the cluster 10 (see FIG. 1) is added or removed. Here, for example, if there is a member (node) registered in the node management table 121 but not registered in the alive monitoring table 122, the node is not monitored. In order to avoid this state, when the node management table 121 is updated due to a change of a node or the like, synchronization is always performed so that the alive monitoring table 122 is also updated.

  Note that different node management table 121 and alive monitoring table 122 may be used. For example, if there are virtually several IDs for one server, the same node will be monitored from multiple nodes. In this case, only the physical node is extracted. It is preferable to prepare such an alive monitoring table 122.

<Cluster leaving instruction unit 115>
In the privileged node selection process using the Paxos algorithm by the privileged node selection unit 114, the cluster leaving instruction unit 115 receives split proposals twice in succession, or when a response cannot be collected from the majority, the split-brain syndrome Is determined to have occurred.
If the cluster leaving instruction unit 115 rejects a proposal that it is a privileged node for two consecutive times, or if a response is not collected from the majority, the cluster leaving instruction unit 115 applies the cluster to all the nodes of the cluster 10 to which it belongs. The node that has issued a leave instruction from the cluster 10 and has received the leave instruction from the cluster 10 leaves the cluster 10 to eliminate the split-brain syndrome. In the above description, since the instruction does not reach the other divided cluster, it is a leave instruction for one divided cluster.

  Further, the cluster leaving instruction unit 115 may output alarm information indicating that a split-brain syndrome has occurred as an alarm when the occurrence of the split-brain syndrome is detected. With this alarm information, the administrator can be aware of the occurrence of Split-Brain Syndrome.

[External server]
Next, a function example of the external server 2 will be described with reference to FIG.
FIG. 5 is a diagram illustrating an example of functions of the external server 2.
As shown in FIG. 5, the external server 2 includes a management unit 21, a storage unit 22, and a communication unit 23.
The management unit 21 includes a CPU and a main memory (not shown), expands a program stored in the storage unit 22 to the main memory, and manages privileged node candidates / privileged nodes of each sub-cluster. In a limited situation where the number of divided subcluster members is less than a majority, the management unit 21 causes privileged node candidates of the subcluster having the largest number of subcluster members to be privileged nodes.

  The management unit 21 aggregates information on the number of members of each sub-cluster from the privileged node candidates of each sub-cluster where the cluster 10 (see FIG. 1) is divided, and stores the information in the storage unit 22. Based on the result of the aggregation, the management unit 21 selects a sub-cluster having the largest number of members or one sub-cluster selected based on specific logic when there are a plurality of sub-clusters having the largest number of members and the same number. The communication unit 23 notifies the privilege node candidate of “approval” of privilege node promotion, and notifies the other privilege node candidates of “denial”.

  When the total number of sub-cluster members reported from all privileged node candidates that can communicate with the external server 2 is less than half of the total number of members of the cluster 10, the management unit 21 can communicate with the external server 2. The communication unit 23 notifies the candidates of “denied” uniformly.

  When the total number of sub-cluster members reported from all privileged node candidates capable of communicating with the external server 2 is less than half of the total number of members of the cluster 10, the management unit 21 notifies the maintenance person via the communication unit 23. In addition to notifying the privileged node candidate, the maintenance person receives a notification of “approval / denial” of the privileged node candidate.

The storage unit 22 is configured by a memory, a hard disk, and the like, and stores an aggregation result of information on the number of members of each subcluster from privileged node candidates of each subcluster. The storage unit 22 also reports the cluster status (privileged node information, number of cluster members) reported from the privileged node candidates of each subcluster, and privileged node promotion requests (privileged node candidate information, subclusters) issued from the privileged node candidates. Number of members).
The communication unit 23 is a communication interface for transmitting and receiving reports and response information between privileged node candidates / privileged nodes of each sub-cluster.

The operation of the cluster system configured as described above will be described below.
(Principle explanation)
In the present invention, in a limited situation where the number of members of a subcluster is less than a majority, an external server installed outside the cluster uses the privileged node candidate of the subcluster with the largest number of members of the subcluster as a privileged node. “Accept” and “reject” privileged node candidates of other sub-clusters to disassemble the sub-clusters. The present invention is also a split-brain syndrome prevention method using an external server.

The present invention makes full use of the advantages of the Paxos algorithm that can construct a cluster autonomously, but the Paxos algorithm uses the help of an external server to prevent the entire cluster from being dismantled and operated. It provides a mechanism to continue
The characteristics are described below.

(1) A cluster system that detects and resolves a split-brain syndrome autonomously within a cluster by using a majority vote consensus building algorithm such as the Paxos algorithm.
(2) An external server 2 that manages the privileged nodes of the cluster is provided outside the cluster. The external server 2 aggregates information on the number of members of each subcluster from the privileged node candidates of each subcluster.
(3) As a result of the aggregation, the external server 2 has a sub-cluster with the largest number of members, or a single sub-cluster selected based on specific logic when there are a plurality of sub-clusters with the largest and equal number of members. “Accept” for the privilege node promotion is notified to the privileged node candidates, and “Negative” is notified to the other privileged node candidates.
(4) A privileged node candidate that has been notified of approval is promoted to a privileged node. As a result, even when there is no sub-cluster satisfying the majority, the entire cluster can be prevented from being dismantled and the operation can be continued.

[Basic operation of split-brain syndrome detection method using external server 2]
First, the basic operation of the split-brain syndrome detection method using the external server 2 will be described.
The distributed system 100 is premised on a cluster system in which one privileged node that manages the node 1 constituting the cluster 10 exists for each cluster.
The distributed system 100 selects a privileged node having a privilege to manage a node from among a plurality of nodes constituting the cluster 10 by applying a majority vote distributed agreement forming algorithm including the Paxos algorithm.
In the present embodiment, a Paxos algorithm (see Non-Patent Document 1) is introduced, in which one privilege node (representative node) is present for each cluster, and a privilege node is re-selected when one of the nodes leaves.

(Operation example 1)
FIG. 6 is a diagram illustrating the operation of the distributed system including clusters according to the present embodiment. 18 is an operation example corresponding to (Problem 1) in FIG.
In the case of FIG. 6, NW division occurs in the cluster 10 (total number of members: 12), and the cluster 10 is divided into two sub-clusters (sub-cluster A (total number of members: 6) and sub-cluster B (total number of members: 6)). This is the case when it is divided. Note that the node 1 constituting the cluster 10 is represented by “◯ (white circle)”, and the privileged node candidate is represented by “◎ (double circle)” as described later.

  In such a case, in the conventional majority distributed agreement formation algorithm such as Paxos algorithm, the number of members of sub-cluster A (total number of members: 6) and sub-cluster B (total number of members: 6) divided by NW division is the same (original Therefore, the entire cluster was disassembled even though it was possible to secure the number of operable clusters.

  In this embodiment, the external server 2 that manages privileged nodes of the cluster is provided outside the cluster. The external server 2 receives a report of information on the number of members of each of the subclusters A and B from the privileged node candidates “1” and “2” (丸 (double circle)) of each of the subclusters A and B. Information on the number of members of clusters A and B is collected. The external server 2 has a sub-cluster with the largest number of members, or a single sub-cluster selected based on specific logic when there are a plurality of sub-clusters with the largest number of members and the same number (in this case, sub-cluster A). Privilege node candidate “1” (◎ (double circle)) is granted “acknowledgement” of privilege node promotion, otherwise (sub-cluster B) privilege node candidate “2” (◎ (double circle)) Is notified of the “denial”. The specific logic may be any type, for example, a mode in which a new node ID is selected.

In addition, as shown by symbol a in FIG. 6, the external server 2 selects one privileged node from among privileged node candidates based on specific logic even when there are a plurality of subclusters having the largest number of members and the same number. Select
Even if there is no sub-cluster that satisfies the majority by the promotion of the privileged node candidate “1” (◎ (double circle)) of the sub-cluster A that has received the notification of “acknowledgement” to the privileged node, Can be prevented and the operation can be continued.

(Operation example 2)
FIG. 7 is a diagram illustrating the operation of the distributed system including the cluster according to the present embodiment. 19 is an operation example corresponding to (Problem 2) in FIG.
In the case of FIG. 7, NW division occurs in the cluster 10 (total number of members: 12), and the cluster 10 has three subclusters (subcluster A (total number of members: 3), subcluster B (total number of members: 5), and sub Cluster C (total number of members: 4)), and no sub-cluster is a majority of the original cluster.

  In such a case, in the majority vote consensus building algorithm such as the conventional Paxos algorithm, a plurality of NW divisions occur, the cluster is divided into a plurality, and there is no sub-cluster in which a majority of the original cluster remains, that is, the original Since there are no more subclusters than half of the members of the cluster, all of them were dismantled.

  In this embodiment, when NW partitioning occurs, the privileged node candidates “1” to “3” (（(double circle)) of each of the sub-clusters A, B, and C Report the number of cluster members. The external server 2 receives a report on the number of members of each sub-cluster A, B, C from the privileged node candidates “1” to “3” (」(double circle)) of each sub-cluster A, B, C Then, the information on the number of members of each of the sub-clusters A, B, and C is collected. The external server 2 has a sub-cluster having the largest number of members, or one sub-cluster selected based on specific logic when there are a plurality of sub-clusters having the largest number of members and the same number (in this case, sub-cluster B). Privilege node candidate “2” (◎ (double circle)) is granted “acknowledgement” of privilege node promotion, and privilege node candidate candidates “1”, “3” (◎ in this case (sub-clusters A and C)) (Double circle)) is notified.

  In this way, the external server 2 is “accepted” for the privileged node candidate of the sub-cluster having the largest number of members, as shown by the symbol a in FIG. Responds with "No".

  The candidate for the privileged node “2” (◎ (double circle)) of the sub-cluster B that has received the notification of “acknowledgement” is promoted to a privileged node to construct the cluster, and the sub-cluster A that has received the notification of “denial” , C privileged node candidates “1” and “3” (◎ (double circle)) disassemble the cluster. As a result, even when multiple NW partitioning occurs and the cluster is divided into multiple clusters, and there is no sub-cluster in which a majority of the original cluster remains, the entire cluster can be prevented from being dismantled and continued to operate. it can.

[Operation when a failure occurs in the external server 2]
Next, an operation when a failure occurs in the external server 2 will be described.
FIG. 8 is a diagram illustrating an operation when a failure occurs in the external server 2 of the distributed system including the cluster according to the present embodiment.
In this embodiment, when there is no “acknowledge / deny” response from the external server 2 due to some failure, the privileged node autonomously waits for a response from the external server 2 if the sub-cluster members satisfy the majority. If the cluster is constructed and the number of members of the sub-cluster does not satisfy the majority, the sub-cluster is dismantled autonomously with a response timeout from the external server 2.

  In the case of FIG. 8, NW division occurs in the cluster 10 (total number of members: 12), and the cluster 10 has three sub-clusters (sub-cluster A (total number of members: 3), sub-cluster B (total number of members: 7), and sub Assume that the data is divided into cluster C (total number of members: 2)). In this case, as indicated by the broken-line arrows in FIG. 8, privileged node candidates “1” to “3” (（(double circle)) of each of the sub-clusters A, B, and C A report of information on the number of members of sub-clusters A, B, and C is transmitted. However, if a failure has occurred in the external server 2, the external server 2 cannot aggregate information on the number of members of each sub-cluster A, B, or C, or the corresponding privileged node candidate (◎ (double circle)) “Accept” for promotion of privileged node cannot be notified, and “Negative” cannot be notified to other privileged node candidates (（(double circle)).

  In the case of FIG. 8, for the privileged node candidate “2” (」(double circle)) of the subcluster B, the privileged node candidate of the subcluster satisfying the majority is autonomous by the Paxos algorithm (see Non-Patent Document 1). To a privileged node. However, even for the privileged node candidates “1” and “3” (◎ (double circle)) of the sub-clusters A and C, the promotion request to the privileged node is issued to the external server 2 and the external server 2 Waiting for a response of “acknowledgement” or “denial” of the privilege node promotion. Here, since it is assumed that a failure has occurred in the external server 2 (including a failure in the external server 2 itself or a failure in the communication path), the privileged node candidates “1” of the sub-clusters A and C, The response “accept / deny” is not notified from the external server 2 to “3” (（(double circle)).

Therefore, as shown by the symbol a in FIG. 8, the privileged node candidates “1” to “3” (二 重 (double circle)) of each of the sub-clusters A, B, and C are transmitted to the external server 2 as promotion requests. After that, when the timer is started and there is no “decision” response from the external server 2, the privileged node candidates “1” and “3” (◎ (double circle)) of the sub-cluster that does not satisfy the majority are Dismantle the cluster with a response timeout.
Further, as shown by the symbol b in FIG. 8, even when there is no “acknowledge” response from the external server 2, the privileged candidate node “2” (（(double circle)) of the sub-cluster satisfying the majority is the timer. Is promoted to privileged node with a response timeout of.

  As described above, after the promotion request is transmitted to the external server 2, the timer is started, and even if there is no approval / disapproval response from the external server 2, if the number of sub-cluster members satisfies the majority, the external server If the privileged node autonomously constructs a cluster without waiting for a response from 2 and the number of members of the subcluster does not satisfy the majority, the subcluster is dismantled autonomously by a response timeout from the external server 2.

[Operation when a failure occurs between a part of the cluster and the external server 2 (part 1)]
Next, an operation when a failure occurs between a part of the cluster and the external server 2 will be described.
FIG. 9 is a diagram illustrating an operation when a failure occurs between a part of the cluster of the cluster system according to the present embodiment and the external server 2.
In the present embodiment, when a partial failure occurs between a part of the cluster and the external server 2, the total number of sub-cluster members reported from all privileged node candidates that can communicate with the external server 2 is the cluster. In consideration of the possibility that a privileged node is selected in a case where it cannot be detected from the external server 2, the external server 2 uniformly notifies the communicable privileged node candidate of “no”. This will be specifically described below.

  In the case of FIG. 9, NW partitioning occurs in the cluster 10 (total number of members: 12), and the cluster 10 has three sub-clusters (sub-cluster A (total number of members: 3), sub-cluster B (total number of members: 7), and sub Assume that the data is divided into cluster C (total number of members: 2)). In this case, as indicated by broken lines and solid arrows in FIG. 9, when a failure occurs in a part of the cluster (here, sub-clusters B and C) and the external server 2, a part of the cluster (here, the sub-cluster). B, C) cannot send a report of information on the number of members of the sub-clusters B and C to the external server 2. In this case, all privileged node candidates that can communicate with the external server 2 are the privileged node candidate “1” (（(double circle)) (number of members: 3) of the sub-cluster A. Therefore, the external server 2 cannot aggregate information on the number of members of each of the sub-clusters B and C, or grants “acceptance” for privilege node promotion to the corresponding privilege node candidate (◎ (double circle)) and other privileges. The node candidate (「(double circle)) cannot be notified of“ denial ”.

  9, the external server 2 cannot see the state of more than half of the cluster members from itself (sub-cluster A privileged node candidate “1” (◎ (double circle)) (number of members: Only 3) is visible).

  On the other hand, as shown by the symbol b in FIG. 9, the privileged node candidate “2” (◎ (double circle)) satisfies the majority, so that a response from the external server 2 is obtained by a majority decision consensus building algorithm such as the Paxos algorithm. Even if there is no cluster, it is promoted autonomously to a privileged node to build a cluster.

  Accordingly, in the case of FIG. 9, the privileged node candidate “2” (二 重 (double circle)) is promoted to a privileged node and constructed as a cluster even if there is no response from the external server 2, while from the external server 2. The cluster that can be seen is only the privileged node candidate “1” (サ ブ (double circle)) (number of members: 3) of the sub-cluster A. When the external server 2 notifies the privileged node candidate “1” (◎ (double circle)) of the sub-cluster A of “acceptance” for promotion of the privileged node, the sub-clusters A and B continue to operate. Split-Brain Syndrome may occur. Such a problem may occur when a failure occurs between a part of the cluster and the external server 2.

  Therefore, as indicated by reference symbol a in FIG. 9, the external server 2 uniformly notifies “decision” when the state of more than half of the cluster members cannot be seen from itself. In other words, when the total number of sub-cluster members reported from all privileged node candidates communicable with the external server 2 is less than half of the total number of members of the cluster, the external server 2 immediately notifies “No”.

  Thus, when a partial failure occurs between a part of the cluster and the external server 2, the total number of sub-cluster members reported from all privileged node candidates that can communicate with the external server 2 is If less than half of the total number of members, considering the possibility that a privileged node will be selected when it cannot be detected from the external server 2, the external server 2 notifies the communicable privileged node candidate of a uniform “denial”. Thereby, even when a failure occurs between a part of the cluster and the external server 2, the split-brain syndrome can be prevented.

[Operation when a failure occurs between a part of the cluster and the external server 2 (part 2)]
Next, an operation when a failure occurs between a part of the cluster and the external server 2 will be described.
FIG. 10 is a diagram illustrating an operation when a failure occurs between a part of the cluster of the cluster system according to the present embodiment and the external server 2.
In the present embodiment, when a partial failure occurs between a part of the cluster and the external server 2, the total number of sub-cluster members reported from all privileged node candidates that can communicate with the external server 2 is the cluster. In consideration of the possibility that a privileged node is selected in a case where it cannot be detected from the external server 2, the external server 2 notifies the maintenance node (maintenance terminal) of the privileged node candidate. The maintenance person makes an “approval / denial” decision.

  In the case of FIG. 10, as in the case of FIG. 9, NW division occurs in the cluster 10 (total number of members: 12), and the cluster 10 has three subclusters (subcluster A (total number of members: 3) and subcluster B). It is assumed that the number of members is divided into (total number of members: 7) and sub-cluster C (total number of members: 2)). In this case, as indicated by broken lines and solid arrows in FIG. 10, when a failure occurs in a part of the cluster (here, subclusters B and C) and the external server 2, a part of the cluster (here, the subcluster) B, C) cannot send a report of information on the number of members of the sub-clusters B and C to the external server 2. Further, the external server 2 cannot aggregate the information on the number of members of each of the sub-clusters B and C, or grants “approval” of privilege node promotion to the corresponding privilege node candidate (◎ (double circle)) and other privileges. The node candidate (「(double circle)) cannot be notified of“ denial ”.

Therefore, as indicated by reference symbol a in FIG. 10, since the external server 2 cannot see the state of more than half of the cluster members from itself, it notifies the maintenance person (maintenance person terminal) of the privileged node candidate, and the maintenance person Determine the privileged node. In the case of FIG. 9, since the external server 2 cannot see the state of more than half of the cluster members from itself, it has been notified of “decision” uniformly, but in the case of FIG. 10, the external server 2 is the external server. 2 notifies the maintenance person (maintenance person's terminal) of the privileged node candidate, receives the determination of “denial / passed” from the maintenance person (maintenance person's terminal), and receives the corresponding privilege node candidate “1” (◎ (double circle) )) Is notified of "approval / denial".
Further, as indicated by a symbol b in FIG. 10, the privileged node candidate “2” (◎ (double circle)) satisfies the majority, and is promoted to a privileged node even if there is no response from the external server 2.

  Thus, when a partial failure occurs between a part of the cluster and the external server 2, the total number of sub-cluster members reported from all privileged node candidates that can communicate with the external server 2 is If less than half of the total number of members, the external server 2 notifies the maintenance person (maintenance person terminal) of the optimal privilege node candidate in consideration of the possibility of selecting a privileged node where it cannot be detected from the external server 2. The determination of “acknowledgement / denial” is made by the maintenance person (maintenance person terminal).

  Thereby, even when a failure occurs between a part of the cluster and the external server 2, the split-brain syndrome can be prevented. In addition, more appropriate operation can be continued as compared with the case where a uniform “denial” is notified as shown in FIG. 9. For example, in the case of FIG. 10, when the sub-cluster B (total number of members: 12) is further divided into two (cluster 10 is divided into four), in the example of FIG. Although all sub-clusters are dismantled, the maintenance person (maintenance person terminal) makes an “acknowledge / denial” decision, so that some sub-clusters of the divided sub-clusters B are clustered. Can be constructed.

[Procedure for Split-Brain Syndrome Prevention Method Using External Server 2]
Next, the procedure of the Split-Brain Syndrome occurrence prevention method using the external server 2 will be described.
FIG. 11 is a diagram for explaining the procedure of the split-brain syndrome generation prevention method using the external server 2 of the cluster system according to the present embodiment. 11A shows selection of privileged node candidates (procedure 1), FIG. 11B shows reports and responses to the external server 2 (procedures 2 and 3), and FIG. 11C shows cluster construction / disassembly (procedure). 4).

(Procedure 1): Selection of privileged node candidates (see FIG. 11A)
In procedure 1, a privileged node candidate is selected for each divided part (subcluster) of the cluster.
As shown in FIG. 11A, NW partitioning occurs in the cluster 10 (total number of members: 13), and the cluster 10 has three sub-clusters (sub-cluster A (total number of members: 6)) and sub-cluster B (total number of members: 3) and sub-cluster C (total number of members: 4)). In this case, privileged node candidates “1” to “3” (◎ (double circle)) are selected for each of the sub-clusters A, B, and C.

(Procedure 2): Report to the external server 2 (see FIG. 11B)
In procedure 2, the privileged node candidate executes the following procedure (2-A) or procedure (2-B).

  (2-A) When the number of members of the sub-cluster satisfies a majority of the total number of members before the division, the cluster state (privileged node information, cluster members) is set as a privileged node (note: not a “privileged node candidate”). Number) to the external server 2. Note that FIG. 11 does not correspond to the case (2-A).

  (2-B) As shown in FIG. 11B, when the number of members of the sub-cluster is equal to or less than half the number of members of the entire cluster before the division, a privileged node promotion request (privileged node candidate information) , The number of sub-cluster members) is issued (reported) to the external server 2. In the case of FIG. 11B, since the number of members of the sub-clusters A, B, and C is less than half the number of members of the entire cluster before the division, the privileged node is designated as a privileged node candidate (◎ (double circle)). An promotion request (privileged node candidate information, number of subcluster members) is issued to the external server 2.

(Procedure 3): Reply from the external server 2 (see FIG. 11B)
In the procedure 3, the external server 2 performs one of the following procedures depending on the number of members when the “report” of the procedure (2-A) is present or not, and when there is no “report”. Run.

  (3-A) When there is a “report” in the above procedure (2-A), the external server 2 notifies the “rejection” in response to a promotion request from other privileged node candidates.

  (3-B) If the external server 2 does not have the “report” in the above procedure (2-A) and more than half of the cluster members are visible from the external server 2 during the timeout period (T2), the privileged node The promotion requests are aggregated, and “Accept” is notified to the privileged node candidate of the subcluster having the largest number of subcluster members, and “Negative” is notified to the other privileged node candidates. Even when there are the largest number of members and the same number of sub-clusters, only one privileged node candidate is notified of “acknowledgment” based on the predetermined logic. In the case of FIG. 11B, the external server 2 gives “accept” to the privileged node candidate “1” (（(double circle)) of the subcluster A having the largest number of subcluster members, and other privileged nodes. The candidates “2” and “3” (（(double circle)) are notified of “denied”. The timeout period (T2) is a fixed period in which the external server 2 waits for a report from a privileged node candidate of the sub-cluster.

  (3-C) If the external server 2 does not have the “report” in the above procedure (2-A) and more than half of the cluster members cannot be seen from the external server 2 during the timeout period (T2), Step (3-C-1) or step (3-C-2) is executed. In the procedure (3-C-1), the external server 2 notifies a “denial” to all privileged node candidates visible from the external server 2 (see FIG. 9). In the procedure (3-C-2), the external server 2 notifies the maintenance person (maintenance person terminal) and notifies “acknowledgement / denial” through the maintenance person (see FIG. 10).

(Procedure 4): Cluster construction / disassembly (see FIG. 11C)
In procedure 4, the privileged node candidate executes the following procedure (4-A), procedure (4-B), or procedure (4-C).

  (4-A) When the privileged node candidate receives the “acknowledge” notification from the external server 2, the privileged node candidate 1 of the sub-cluster A is designated as the privileged node “★ ( Promote to "star" and build a cluster.

  (4-B) When the privileged node candidate receives the “denial” notification from the external server 2, the privileged node candidate disassembles the clusters (here, the sub-clusters B and C) as indicated by the crosses in FIG.

  (4-C) If there is no notification from the external server 2 for a certain period of time (timeout T1), the privileged node candidate disassembles the cluster as shown by a cross in FIG.

  Next, the management process of the privileged node / privileged node candidate and the external server 2 will be described. First, management processing of privileged nodes / privileged node candidates will be described.

[Management processing of privileged nodes / privileged node candidates]
FIG. 12 is a flowchart showing the management processing of privileged nodes / privileged node candidates in the cluster system according to this embodiment, and corresponds to (Procedure 4) in FIG.
This flow starts with a change in the number of members as an event. In step S11, the privileged node selection unit 114 aggregates the number of cluster members (number of members m) recognized by the privileged node candidate. The aggregation of the number of cluster members (number of members m) is the sum of the number of Acceptors (accepting nodes) that have returned responses in the first phase (Prepare phase) of the Paxos algorithm (see Non-Patent Document 1) shown in FIG. To do.

In step S12, the privileged node selection unit 114 determines whether the number of members m recognized by the privileged node candidate is greater than the total number of members N / 2 before the NW division (m> N / 2). .
In the case of m> N / 2, the privileged node selection unit 114 is promoted to a privileged node and builds a cluster in step S13, and the privileged node of the cluster periodically changes the cluster status (privileged node information, number of cluster members) and When the number of cluster members changes, the external server 2 is notified and this flow is terminated.
When m ≦ N / 2, the privileged node selection unit 114 transmits (issues) a privileged node promotion request (privileged node candidate information, number of cluster members) to the external server 2 as a privileged node candidate in step S14.

Next, in step S <b> 15, the privileged node selection unit 114 determines whether there is a notification from the external server 2.
If “acknowledgement” is received from the external server 2 in step S15, the process proceeds to step S13. As described above, in step S13, the privileged node selection unit 114 is promoted to a privileged node, builds a cluster, and reports the cluster status (privileged node information, number of cluster members) to the external server 2.
If the “No” is received from the external server 2 in step S15 or if there is no response from the external server 2 (timeout T1), the privileged node selection unit 114 disassembles the cluster and ends this flow in step S16. To do.

[Management processing of external server 2]
Next, the management process of the external server 2 will be described.
The external server 2 has a “normal function” and a “privileged node selection function”. The “privileged node selection function” further includes <main processing> (see FIG. 13 to be described later) and <timer processing> (see FIG. 14 to be described later). ) And execute.

(Normal function)
In the “normal function”, the external server 2 grasps the total number of members of the current cluster (period confirmation to the privileged node). Also, the current privilege node is grasped (period confirmation to the privilege node).

(Privileged node selection function)
The external server 2 receives a privileged node promotion request (privileged node candidate information, number of cluster members) from a privileged node candidate.
After receiving the request, the external server 2 waits for a response until the specific timer held by itself (expiration of the timeout period T2) and confirms the status of the last privileged node held.

  The external server 2 aggregates the contents (number of cluster members) received from all privileged node candidates during the above period and the status (number of cluster members) of the latest privileged node held by the external server 2.

Here, the total number of members of the most recent cluster held by the external server 2 is N. Also, let the number of members reported from each privileged node candidate (including the current privileged node) be m ₀ , m ₁ , m ₂ , m ₃ ,. Note that the number of members reported is at most the number of sub-clusters after division. The total number M of members reported from all privileged node candidates (including the current privileged node) is M = m ₀ + m ₁ + m ₂ + m ₃ +.

When M> N / 2, the external server 2 notifies the privileged node candidate having the maximum number of cluster members of “acceptance” and notifies other privileged node candidates of “denial”.
When M ≦ N / 2, the external server 2 notifies the all-privilege node candidate of “No”. Alternatively, the external server 2 notifies the maintenance person (maintenance person terminal) when M ≦ N / 2.

FIG. 13 is a flowchart showing a main process of the privileged node selection function of the external server 2 in the cluster system according to the present embodiment, and corresponds to (procedures 2 and 3) in FIG.
This flow starts upon reception of a privileged node promotion request (number of members m ₀ ) as an event (trigger). In step S21, the management unit 21 determines whether the privilege node promotion request (number of members m ₀ ) is larger than the total number of members N / 2 of the latest cluster held by the external server 2 (m ₀ > N / 2). Is determined.

If m ₀ > N / 2, in step S22, the management unit 21 notifies the privileged node candidate having the maximum number of cluster members of “approval” and notifies other privileged node candidates of “denial”, and ends this flow. .
When m ₀ ≦ N / 2, in step S23, the management unit 21 sets the number of members m ₀ as the total number M of members reported from all privileged node candidates (including the current privileged node) (m ₀ → M ).
In step S24, the management unit 21 starts a timer that times out the timeout period T2.

In step S _< b _> 25, the management unit 21 receives a privileged node promotion request (number of members m _n ). Here, n is a sub-cluster identification number. The identification number n of the subcluster and the number of subclusters after division can be expressed as “0 ≦ n ≦ number of subclusters after division”. For example, when the cluster is divided into three, 0 ≦ n ≦ 2.
In step S <b> 26, the management unit 21 determines whether or not the privilege node promotion request (number of members m _n ) is larger than the total number of members N / 2 of the most recent cluster held by the external server 2 (m _n > N / 2). Is determined.

If m _n > N / 2, the process proceeds to step S22. In step S22, "Accept" is notified to the privileged node candidate having the maximum number of cluster members, and "No" is notified to the other privileged node candidates, and this flow is finished.
When m _n ≦ N / 2, in step S27, the management unit 21 sets the total number of members M + the number of members m _n to the total number M of members reported from all privileged node candidates (including the current privileged node). (M ← M + _mn ).

  In step S28, the management unit 21 has the total number of members N of the latest cluster held in the external server 2 smaller than the total number M of members reported from all privileged node candidates (including the current privileged node) ( It is determined whether or not M <N).

If M <N, the process returns to step S25.
If M ≧ N, in step S29, the management unit 21 notifies the privileged node candidate having the maximum number of cluster members of “approval” and notifies other privileged node candidates of “denial”, and ends this flow.

  FIG. 14 is a flowchart showing timer processing of the privileged node selection function of the external server 2 in the cluster system according to the present embodiment. The timer process flow of FIG. 14 is executed in the main process of FIG. 13 when the timer is started and the timeout value of the timeout period T2 is measured (timeout occurs).

  This flow starts with a time-out detection as an event. In step S31, the management unit 21 determines that the total number M of members reported from all privileged node candidates (including the current privileged node) is the total number N / 2 of the latest clusters held in the external server 2. It is determined whether or not it is large (M> N / 2).

  When M> N / 2, in step S32, the management unit 21 notifies the privilege node candidate having the largest number of members of “approval” and notifies other privilege node candidates of “denial”, and ends this flow. This step S32 corresponds to the operation of FIG.

  In the case of M ≦ N / 2, in step S33, the management unit 21 considers the possibility that a privileged node is selected when it cannot be detected from the external server 2, and the external server 2 uniformly sets “ This flow is finished (corresponding to the operation of FIG. 9). Alternatively, the management unit 21 notifies the privileged node candidate optimal for the maintenance person (maintenance person terminal) (corresponding to the operation of FIG. 10). In this case, the determination of “acknowledgement / denial” is performed by the maintenance person (maintenance person terminal).

Next, a split-brain syndrome detection method using the external server 2 will be described.
[Occurrence of split-brain syndrome]
As shown in FIG. 16, when one cluster is divided into a plurality of clusters due to a path failure or the like, there is no response to the alive monitoring signal from the node of the other cluster in each cluster. In a cluster where a privileged node does not exist (separated from a privileged node), a new privileged node is selected, and the privileged node updates the node management table 121 in both clusters to become Split-Brain Syndrine. Conceivable.

[Paxos algorithm]
In general, the Paxos algorithm (see Non-Patent Document 1) is a distributed environment in which a set of processes with low reliability (a cluster composed of a set of multiple nodes in this embodiment) agrees on one value. Is an algorithm for The Paxos algorithm changes the number of nodes constituting the distributed system without disassembling the distributed system if up to half of the failures occur simultaneously. Further, even if the processing time of each node cannot be guaranteed, it is possible to guarantee that an agreement can always be reached or no agreement can be reached in the distributed system.

[Description of operation of this embodiment]
This embodiment will be described in more detail. According to this method, it is possible to detect the possibility of occurrence of a split-brain syndrome that occurs due to a path failure or the like in the distributed system 100 (see FIG. 1). Note that the following series of processing is realized by the privileged node selection unit 114 and the cluster leaving instruction unit 115 that are linked to the alive monitoring unit 113 (see FIG. 2; the same applies hereinafter).

  In the present embodiment, the right to operate as a privileged node using this method (that is, to update the node management table 121) before executing the process of deleting the failed node from the node management table 121 as a privileged node. To agree within the cluster. The agreement of privileged nodes and the update of the node management table 121 are roughly divided into three phases.

<Prepare phase>
In the first phase (Prepare phase), the proposer who can propose the proposal content is selected.
In the first phase (Prepare phase), in order to comply with the Paxos algorithm (see Non-Patent Document 1), a privileged node or a privileged node candidate node (hereinafter referred to as a Proposer (proposer: proposal node)) is a node 1 When notification of leaving (see FIG. 15 below) is notified, a Prepare request with a proposal number is transmitted to the remaining node 1 (hereinafter referred to as an Acceptor (accepting node)) (see step S1 in FIG. 15 below). ). The remaining nodes are all nodes existing in the node management table 121, and include the node 1 even when the node management table 121 is updated due to the notification of leaving the node 1.

  When Acceptor receives a Prepare request with a proposal number larger than the largest accepted proposal number, Acceptor promises to reject proposal numbers smaller than the larger proposal number and returns a Promise response (step S2 in FIG. 15 described later). reference). For example, if the maximum proposal number received by a node (Acceptor “A”) is “5”, a larger proposal number (for example, “10”) will result in a larger proposal number. Accept the number because it has been received. Thereafter, even if a proposal number of “9” or less is received, it is not accepted. Incidentally, since the other node knows that the acceptor “A” has received the proposal number “10” in response to the promise response from the acceptor “A”, the proposal number “10” is sent to the acceptor “A”. The proposal with the proposal number smaller than the number is not transmitted.

  When the Acceptor receives a Prepare request with a small proposal number, the Acceptor returns a Reject response (see step S2 in FIG. 15 described later). Acceptor accepts a proposal having another small proposal number b at the time of receiving a Prepare request, and returns a proposal number b and a proposal content V together with a Promise response when a series of Paxos algorithms is not completed. . In the first phase, there may be an Acceptor that returns only the proposal number b together with the Promise response (the process branches depending on whether the proposal is received).

For example, in the case of the above example, it is assumed that a proposal number “5” is accepted as a maximum proposal number from a certain Acceptor “A” and a Promise response is returned to another node. Here, when a Prepare request with the proposal number “8” is received from another member (Acceptor “B”), the Acceptor “B” has a proposal number “5” that is larger than the proposal number “5” from the Acceptor “A”. Because it is number 8 ”, it is accepted. Although accepted, Acceptor “B” returns the proposal number “5” and the proposal content V that have already been accepted together with the Promise response. In the first phase, no proposal is made and only the proposal number is reserved.
The case where a series of flows is not completed means a state in which a proposal is being received, that is, a state in which the process has not shifted to the third phase (Commit phase) described below.

  When the Proposer receives a Promise response from the majority of Acceptors, it proceeds to the next phase (second phase). If the Proposer cannot collect the Promise responses from the majority after waiting for a certain time (cannot collect the Promise responses from the majority within the timeout), it starts again from Prepare.

  The number of times that the Proposer can make proposals consecutively before the series of Paxos algorithms is completed is two. If the Promise responses from the majority cannot be collected twice consecutively, proceed to the next phase (second phase). That is, the Proposer shifts to the next phase (second phase) even if Promise responses are not returned from the majority of nodes (see step S3 in FIG. 15 described later).

In the case where the detached node is restored, it is assumed that it is set as a new node after the failure is removed. For this reason, the detached node will not be restored in an incomplete state.
In general, in the Paxos algorithm, when executing a new Paxos algorithm, if the node to be proposed is a Proposer of the Paxos algorithm that was completed last time, the first phase is omitted, It is allowed to carry out only the third phase.

<Second phase>
The second phase (Vote phase) is a phase in which the proposer proposes proposal contents.
In the second phase (Vote phase), the Proposer transmits an Accept request to the Acceptor when receiving a Promise response from the majority of Acceptors so as to comply with the Paxos algorithm (see Non-Patent Document 1) (see FIG. 15 described later). (See step S4). The Accept request includes the proposal number b and the proposal content V, and the proposal number b used in the first phase is adopted. In other words, the proposal number b in the second phase is a proposal number that was proposed in the first phase (Prepare phase) and received a Promise response. From another Acceptor's point of view, since the proposal came from the promised proposal number b, the Accept request is received in the second phase. If the proposal content V has received the proposal number b and the proposal content V in the Promise response of the first phase, the proposal with the largest proposal number b from among them is optional. Adopt the content. Here, the proposal content V is a proposal that a node is a privileged node and updates the node management table 121 when the node leaves.

  By the way, in the Paxos algorithm (see Non-Patent Document 1), the Proposer must always propose the proposal content V assigned the largest proposal number b. That is, in the Paxos algorithm (see Non-Patent Document 1), a plurality of Proposers may appear at the same time. For this reason, an Accept request may be received from a plurality of Proposers at the same time. For such a case, in the Paxos algorithm (see Non-Patent Document 1), the Proposer is not an own proposal from among a plurality of proposals. The proposal with the largest proposal number b must be selected. Therefore, the Proposer transmits an Accept request including the proposal number b and the proposal content V to the Acceptor.

  In this embodiment, when the Acceptor receives an Accept request whose proposal number b is greater than or equal to the proposal number b accepted in the first phase, the Acceptor accepts the proposal and receives a privilege node or a privileged node candidate node (Paxos In the algorithm (refer to Non-Patent Document 1), it is called Learner, and in this method, the Proposer node also serves as a Learner), and returns ACK. When the Acceptor receives an Accept request having a value less than the proposal number b accepted in the first phase, the Acceptor returns a Reject response (see step S5 in FIG. 15 described later).

When Learner (Proposer in this case) receives ACK from a majority of Acceptors, it reports the number of Acceptors that have received ACK to external server 2 (see step S6 in FIG. 15 below), and the next phase (third phase) Proceed to
If it is not possible to collect ACKs from the majority of Acceptors after waiting for a certain period of time (when ACKs from the majority cannot be collected within the timeout), report the number of Acceptors that received ACK to the external server 2, and from the external server 2 With the approval, proceed to the next phase (third phase). If it is rejected from the external server 2 or if there is no response from the external server 2 after waiting for a certain time, the local subcluster is disassembled.

  Here, when the Proposer receives ACK from the majority of nodes, the process proceeds to the third phase (Commit phase) (see step S7 in FIG. 15 described later).

<Commit phase>
In the third phase (Commit phase), update information (Commit) is notified.
In the third phase (Commit phase), the Learner obtains the right to update the node management table 121 (ID table) as a privileged node when ACK is received from a majority of Acceptors or when the external server 2 accepts the ACK. It will be. Then, the updated node management table 121 or the updated node information is distributed to the Acceptor excluding the node that has left the node management table 121 after updating. If the node management table 121 (ID table) is transmitted as it is, the distribution load increases. Therefore, instead of transmitting the node management table 121, updated node information (difference information) may be distributed.
The Acceptor returns ACK when receiving update information of the node management table 121 (ID table).

[Flow of selecting privileged nodes]
The flow of privileged node selection described above will be described with reference to FIG.
FIG. 15 is a sequence diagram illustrating the flow of selecting a privileged node in the cluster system according to the present embodiment.
First, the privileged node or the privileged node candidate node 1 (“Proposer”) is notified of all nodes 1 (“Acceptor”) existing in the node management table 121 (see FIG. 2) when being notified of the withdrawal of the node. Then, a Prepare request with a proposal number is transmitted (step S1).

When Acceptor receives a Prepare request with a proposal number b greater than or equal to the largest accepted proposal number b, the Acceptor promises to reject the proposal number b less than the proposal number b, and the proposal number b and the proposal content V Is returned together with the Promise response (step S2). As described above, the case where the proposal content V is returned together with the Promise response may have received another proposal that has already been executed up to the second phase. When the Acceptor receives a Prepare request with a proposal number b smaller than the largest accepted proposal number b, the Acceptor returns a Reject response (step S2).
The above is the processing in the first phase (Prepare phase).

Next, when the Proposer receives a Promise response from the majority of Acceptors, the Proposer proceeds to the second phase (Vote phase). Proposer shifts to the next phase (second phase) even if a Promise response is not returned from the majority of nodes (step S3).
When the Proposer receives a Promise response from the majority of Acceptors, the Proposer transmits an Accept request to the Acceptors (step S4). The Accept request includes the proposal number b and the proposal content V, and the proposal number b adopts the number used in the first phase (based on the Paxos algorithm (see Non-Patent Document 1)). If the proposal content V has received the proposal number b and the proposal content V in the first-phase Promise response, the proposal with the largest proposal number b is not received. Adopt any content.

  When Acceptor receives an Accept request whose proposal number b is greater than or equal to the proposal number b accepted in the first phase, the acceptor accepts the proposal and receives a privilege node or a privileged node candidate node (Proposer, here, Learner) ACK is returned to (step S5). When the Acceptor receives an Accept request having a value less than the proposal number b accepted in the first phase, the Acceptor returns a Reject response.

The Proposer reports the number of Acceptors that received ACK to the external server 2 (Step S6).
The external server 2 notifies “privileged” to the privileged node / privileged node candidate that has reported the maximum number of Acceptors, and notifies “denied” to others (steps S7 and S7a).
Here, Proposer is already operating as a Learner (step S8).

  When the ACK is returned from the majority of Acceptors or when approved by the external server 2, the Proposer moves to the next phase (third phase) (Step S9).

Next, the Proposer (Learner) recognizes that the proposal has been agreed upon when an ACK is received from the majority of Acceptors. That is, at this stage, the right to update the node management table 121 as a privileged node is obtained. Then, the node management table 121 (ID table) is updated and the updated node management table 121 (ID table) or updated node information is distributed to the Acceptor excluding the detached node (step S10).
When acceptor receives update information of the node management table 121 (ID table), the Acceptor returns ACK (not shown).

  With the above processing, it is possible to prevent a plurality of privileged nodes from updating the node management table 121 (ID table) at the same time. That is, when a route failure or the like occurs and the node is divided into a plurality of clusters, the node leaving process is mutually performed and the process does not continue with the plurality of clusters.

  As described above, the distributed system 100 according to this embodiment includes the external server 2 outside the cluster 10, and the external server 2 is a member of each subcluster from the privileged node candidates of each subcluster from which the cluster 10 is divided. If the number of sub-clusters with the largest number of members or multiple sub-clusters with the largest and equal number of members exists, the privileged privileged node is selected as a privileged node candidate for one sub-cluster selected based on specific logic. Notify approval of node promotion, and reject to other privileged node candidates. If a privileged node candidate of each sub-cluster receives an acknowledgment from the external server 2, it is promoted to a privileged node to build the cluster 10, and if it receives a denial notification from the external server 2, disassembles the sub-cluster. To do.

  With this configuration, it is possible to prevent a split-brain syndrome and prevent a privileged node from being determined as much as possible when making a privileged node decision. For example, if a plurality of NW divisions occur and the cluster is divided into a plurality of clusters, and there is no sub-cluster in which a majority of the original clusters remain, the Paxos algorithm disassembles the entire cluster. Accordingly, even when there is no sub-cluster that satisfies the majority, the entire cluster can be prevented from being dismantled and the operation can be continued.

  Therefore, even if the cluster is divided into two sub-clusters due to NW division and the number of members of the two sub-clusters is the same, one sub-cluster is left with the approval from the external server 2, and the split-brain syndrome Operation can be continued with no occurrence. The (Problem 1) in FIG. 17 can be solved.

  Even if multiple NW divisions occur and the cluster is divided into multiple clusters, and there is no subcluster in which the majority of the original cluster remains, one subcluster is left with the approval from the external server 2, and Split- Operation can be continued in the absence of Brain Syndrome. The (Problem 2) in FIG. 18 can be solved.

.
Further, in this embodiment, the privileged node candidate of the sub-cluster, when there is no response of acceptance or rejection from the external server 2 and the number of members of the sub-cluster satisfies the majority, the majority distributed agreement formation algorithm including the Paxos algorithm is used. Applying it, the cluster 10 is autonomously constructed as a privileged node. As a result, when there is no “acknowledge / decline” response from the external server due to some failure, if the majority of the sub-cluster members meet the majority, the majority distribution including the Paxos algorithm is not waited for the response from the external server. A privileged node can autonomously construct a cluster using a consensus building algorithm.

  In this embodiment, the privileged node candidate of the sub-cluster autonomously receives the response after the predetermined timeout period elapses when there is no acknowledgment or rejection response from the external server 2 and the number of members of the sub-cluster does not satisfy the majority. Dismantle the subcluster. As a result, when there is no approval / disapproval response from the external server due to some failure, if the number of members of the subcluster does not satisfy the majority, the subcluster can be dismantled autonomously by a response timeout from the external server. .

  In this embodiment, the privileged node of the cluster reports the privileged node information indicating that it is a privileged node and the number of cluster members to the external server 2 periodically and when the number of members of the cluster changes. As a result, the external server 2 receives the periodic report, grasps the number of members of the entire cluster before the division, receives the report when the number of members of the cluster has changed, and receives the current cluster status (privileged node information, cluster members). Number).

  In the present embodiment, the privileged node candidate information indicating that the privileged node candidate of the subcluster is itself a privileged node candidate when the number of members of the subcluster is equal to or less than half the number of members of the entire cluster before the division. And issues a privileged node promotion request including the number of sub-cluster members to the external server 2. As a result, the external server 2 can grasp the nodes that are privileged node candidates and the number of sub-cluster members of the sub-cluster.

  In this embodiment, the external server 2 can communicate with the privileged node candidate when the total number of members of the sub-cluster reported from all the privileged node candidates that can communicate is less than half of the total number of members of the cluster 10. Is uniformly notified of the rejection, the privileged node candidate communicable with the external server 2 is uniformly notified of the “rejection”. This makes it possible to reliably prevent split-brain syndrome even when sub-clusters satisfying the majority exist where they cannot be detected from the external server 2 and privileged nodes are autonomously selected according to the majority-distribution consensus building algorithm.

  Further, in the present embodiment, the external server 2 determines that the maintenance person (maintenance person terminal) if the total number of sub-cluster members reported from all the privileged node candidates that can communicate is less than half of the total number of members of the cluster 10. ) Is notified of the privileged node candidate and also received a notification of approval or rejection of the privileged node candidate from the maintenance person, and the approval or rejection of the privileged node candidate is notified according to the notification of determination. As a result, it is possible to continue the more appropriate operation while preventing the split-brain syndrome compared to the case of notifying the uniform “decision”.

1 node 2 external server 10, 10A, 10B cluster 11 processing unit 12, 22 storage unit 13, 23 communication unit 20 network 21 management unit 30 client 100 distributed system (cluster system)
111 Node management unit 112 Message processing unit 113 Alive monitoring unit 114 Privileged node selection unit 115 Cluster leave instruction unit 121 Node management table (node management information) (ID table)
122 Alive monitoring table (life monitoring information)
b Proposal number V Proposal content

Claims (8)

A cluster system that selects a privileged node having a privilege to manage a node from a plurality of nodes constituting a cluster by applying a majority voted consensus building algorithm including a Paxos algorithm,
An external server for managing the privileged node is provided outside the cluster,
The external server is
When the information on the number of members of each sub-cluster is aggregated from the privileged node candidates of each sub-cluster where the cluster has been divided, and there are multiple sub-clusters with the largest number of members or with the largest number of equal members Comprises a management unit for notifying the privilege node promotion approval to the privilege node candidate of one sub-cluster selected based on specific logic, and notifying the other privilege node candidates of the rejection,
The privileged node candidate of the sub-cluster is
When a notification of acceptance is received from the external server, it is promoted to a privileged node to build a cluster,
A cluster system comprising: disassembling the sub-cluster when receiving a rejection notice from the external server. The privileged node candidate of the sub-cluster is
When there is no approval or rejection response from the external server and the number of members of the sub-cluster satisfies a majority, the majority vote distributed agreement formation algorithm is applied, and a cluster is autonomously constructed as a privileged node, The cluster system according to claim 1. The privileged node candidate of the sub-cluster is
The subcluster is autonomously dismantled after a predetermined time-out period when there is no acknowledgment or rejection response from the external server and the number of members of the subcluster does not satisfy the majority. Item 3. The cluster system according to Item 2.   2. The privileged node of the cluster reports privileged node information indicating that it is a privileged node and the number of cluster members to the external server periodically and when the number of members of the cluster changes. The cluster system according to any one of claims 3 to 4. The privileged node candidate of the sub-cluster is
The privileged node promotion request including privilege node candidate information indicating that the number of members of the subcluster is a privileged node candidate and the number of subcluster members is issued to the external server. Item 5. The cluster system according to any one of items 4. The external server is
When the total number of sub-cluster members reported from all communicable privileged node candidates is less than half of the total number of members of the cluster, the communicable privileged node candidates are uniformly notified of rejection. The cluster system according to claim 2. The external server is
When the total number of sub-cluster members reported from all communicable privileged node candidates is less than half of the total number of members of the cluster, the maintenance node is notified of the privileged node candidates and from the maintenance node The cluster system according to claim 2, wherein a notification of acceptance or rejection of the privileged node candidate is received, and approval or rejection is notified to the privileged node candidate according to the determination notification. A split-brain syndrome prevention method for a cluster system that selects a privileged node having a privilege to manage a node from a plurality of nodes constituting a cluster by applying a majority voting distributed consensus algorithm including a Paxos algorithm,
An external server for managing the privileged node is provided outside the cluster,
The external server is
Aggregating information on the number of members of each sub-cluster from the privileged node candidates of each sub-cluster from which the cluster was divided;
If there are multiple sub-clusters with the largest number of members, or sub-clusters with the largest and equal number of members, the approval of privileged node promotion is given to the privileged node candidates of one subcluster selected based on specific logic. A step of notifying the privileged node candidate other than
The privileged node candidate of the sub-cluster is
When receiving a notification of consent from the external server, the step of promoting to a privileged node and building a cluster;
When receiving a notice of rejection from the external server, disassembling the sub-cluster,
A split-brain syndrome prevention method for a cluster system characterized by

Images