Method and system for safely arbitrating disk drive ownership using a timestamp voting algorithm

In data storage system including multiple servers and multiple disks, and wherein each server is in communication with each disk, each disk has a reserved disk block for each of the servers. The system includes a disk arbitration mechanism that uses a timestamp-based voting algorithm over the disk blocks associated with the servers to exchange votes for a primary server to arbitrate access of the servers to a set of disks. The disk arbitration mechanism further includes each server writing its state in its own associated disk block in each disk, and reading all the other servers' disk blocks in each disk in order to determine which server has access to, use, and control of the disks at a given time.

FIELD OF THE INVENTION

The present invention is related to a data storage system. More specifically, the present invention pertains to a data storage system with D disks, where each disk has a reserved disk block for each of N servers that uses a timestamp-based voting algorithm to arbitrate access of the servers to a set of disks, or each server reads all the other servers' disk blocks in each disk in order to determine which server has access to, and use and control of the disks at a given time.

BACKGROUND OF THE INVENTION

In many environments requiring a highly available system, disk drives need to be shared among two or more machines, such that if one machine fails, one of the others can provide access to the data stored on the shared disk drives. In such environments, it is crucial that the data on the disk drives not be accessed by multiple machines simultaneously, to prevent serious data corruption. The present invention provides for an arbitration that has fewer failure modes than previous systems for shared disk drives.

There are two areas in which the present invention is superior to the prior art in the area of disk ownership arbitration.

Typical prior art for arbitration among N servers for access to a set of disks involves a heartbeat being exchanged between two servers, and when the primary server crashes, the secondary server detects a loss of heartbeat and takes over for the failed primary. There are three weaknesses with this art that are solved by this invention.

First, the prior art typically works only with 2 servers, rather than an arbitrary number of servers.

Second, by using the disk as the communications mechanism, rather than a separate communication path, the present invention reduces the chances that the communication path used for determining which server should access the disk will fail independently from the communication path used for accessing the disk itself.

Third, even with a network partition, it is guaranteed that at most one server is granted access to the arbitrated set of disks, while most prior art has the possibility of assigning two servers access to the set of disks in the case where there is a network partition in the communications network, and both servers are actually still connected to the disks.

Another prior art device (Ubik, by Transarc Corporation [1989]), used a similar voting mechanism, run over an IP network, to elect a synchronization server for a distributed database. However, the Ubik system did not use an array of disk blocks for a communication medium, but instead used network packets exchanged over an IP network.

SUMMARY OF THE INVENTION

The present invention pertains to a data storage system. The system comprises N servers, where N≧2 and is an integer. The system comprises D disks, where D≧2 and is an integer. Each server is in communication with each disk. Each disk has a reserved disk block for each of the N servers. The system comprises a disk arbitration mechanism that uses a timestamp-based voting algorithm over the disk blocks associated with the servers to exchange votes for a primary server to arbitrate access of the servers to a set of disks.

The present invention pertains to a data storage system. The system comprises N servers, where N≧2 and is an integer. The system comprises D disks, where D≧2 and is an integer. Each server is in communication with each disk. Each disk has a reserved disk block for each of the N servers. The system comprises a disk arbitration mechanism where each of the N servers writes its state in its own associated disk block in each disk, and reads all the other servers' disk blocks in each disk in order to determine which server has access to, and use and control of the disks at a given time.

The present invention pertains to a method for storing data. The method comprises the steps of writing by N servers into each servers' own associated disk block in each disk of D disks its state, where N≧2 and D≧2 and are integers. There is the step of reading by each server all the other servers' disk blocks in each disk in order to determine which server has access to, and use and control of the disks at a given time.

DETAILED DESCRIPTION

Referring now to the drawings wherein like reference numerals refer to similar or identical parts throughout the several views, and more specifically toFIG. 1thereof, there is shown a data storage system10. The system10comprises N servers12, where N≧2 and is an integer. The system10comprises D disks14, where D≧2 and is an integer. Each server12is in communication with each disk. Each disk has a reserved disk block18for each of the N servers12. The system10comprises a disk arbitration mechanism16that uses a timestamp-based voting algorithm over the disk blocks18associated with the servers12to exchange votes for a primary server to arbitrate access of the servers12to a set of disks14.

The present invention pertains to a data storage system10, as shown inFIG. 1. The system10comprises N servers12, where N≧2 and is an integer. The system10comprises D disks14, where D≧2 and is an integer. Each server12is in communication with each disk. Each disk has a reserved disk block18for each of the N servers12. The system10comprises a disk arbitration mechanism16where each of the N servers12writes its state in its own associated disk block18in each disk, and reads all the other servers'12disk blocks18in each disk in order to determine which server12has access to, and use and control of the disks14at a given time.

Preferably, each server12has an index. The disk arbitration mechanism16preferably causes each server12at first predetermined times to read all of the disk blocks18, and write its own disk block18to determine which server12has access to, and use and control of the disks14at a given time.

Preferably, each server12includes a state machine20and a local RAM22, and maintains in local RAM22a last time at which each servers'12state's heartbeat counter changed and a value associated with the state when it last changed. Each server12preferably determines which of the other servers12are operating by identifying which of the other servers12had their state's heartbeat counter change during second predetermined times.

The present invention pertains to a method for storing data. The method comprises the steps of writing by N servers12into each servers'12own associated disk block18in each disk of D disks14its state, where N≧2 and D≧2 and are integers. There is the step of reading by each server12all the other servers'12disk blocks18in each disk in order to determine which server12has access to, and use and control of the disks14at a given time.

Preferably, the reading step includes the step of performing a voting protocol to determine which server12has access to, and use and control of the disks14at a given time. After the reading step, there are preferably the steps of determining which server12becomes a winning server12and has access to, and use and control of the disk at a given time; and accessing the disk exclusively by the winning server12. Preferably, the accessing step includes the step of transmitting by the winning server12its state from not winning to winning and invalidating by the winning server12all caches of the winning server12.

The writing step preferably includes the step of assigning an index to each server12only at initialization of the servers12and the disks. Preferably, the reading step includes the step of reading at predetermined times by each server12all disk blocks18. The writing step preferably includes the step of writing its own respective disk block18. The writing step preferably includes the step of maintaining by each server12in each servers'12own local RAM22a last time for each other server12when each other servers'12status changed and a value of a status counter at the last time.

Preferably, the reading step includes the step of determining by each server12which of the other servers12are operating by declaring that each of the other servers12whose status has changed within a last predetermined time period is operating. The reading step preferably includes the step of voting by the servers12that are up for a winning server12that is up and believes it is the winning server12. Preferably, the reading step includes the step of voting for the server12that is up and has a lowest index if no server12believes it is the winning server12.

In the operation of the invention, the system10is used to allow N servers12to share and arbitrate for access to one or more disk drives. The system10works by having N servers12perform a voting protocol, using a set of N disk blocks18for their communications medium. The servers12are all connected to the set of disks14for which arbitration is being performed, so that any server12can access all of the disks14. In a fibrechannel switched network system, the system topology is shown inFIG. 2.

Note that the server12that has won the arbitration election is clear, while the others are cross-hatched inFIG. 2, indicating that they will not attempt to access the disk drives beyond performing the reads and writes required by the voting protocol.

Note that the server that has won the arbitration election is clear, while the others are cross-hatched, indicating that they will not attempt to access the disk drives. The server that wins the election is called the primary server. Note that this is a dynamic concept, based upon the entity that wins the election, not based upon a fixed assignment.

Note that the box labeled “fibrechannel switched network” inFIG. 1is not an arbiter, it is a simple disk controller having several access ports. The arbitration is accomplished by the voting algorithm described here, in that the winner of that election is the only server that is permitted access to the disks.

The server12that wins the election is given exclusive access to the relevant set of disks14. At the time the server12transitions from the state of having not won an election to one of having one an election, it must invalidate all of its caches, since during the time between the last time the server12won an election and its winning this election, other servers12may have modified the contents of the disks14in question.

The system10must be used with write-through caching, so that at the time that after a server12crashes, the disks14have up-to-date data, and a newly elected server12can immediately take over responsibility for the set of arbitrated disks14.

The voting protocol executed by each of the N servers12is now described. The system10described herein reserves one disk block18for each of the N servers12, at a fixed location on the disk. Each of the N blocks has the following format:

Each server12is also assigned a fixed index (1 . . . N) such that all servers12agree upon which server12has which index. This would typically be done when configuring the system10. This assignment gives all servers12a common agreed-upon fixed ordering as determined by this index.

Each server12executes the same state machine20, parameterized by the time constants theartbeat, tmin and tmax described below. Once each theartbeat seconds (typically 1 second), each server12reads all of the vote blocks, and writes its own vote block. There are two other constants, tmin and tmax, (again, typically 10 and 15 seconds, respectively), which will be used below.

Every time that a server writes its own vote block, it increments the heartbeat field, which is a simple counter. The server also places in the vote field the index of the server for whom it is voting; a value of 0×FFFFFFFF indicates that no vote is being cast. Finally, the amPrimaryServer field contains a 1 if the server believes that it has won the election, and 0 otherwise.

Each server12maintains in local RAM22, for each other server12, the last time at which the server's heartbeat changed, and the value of the heartbeat counter at that time. The server12then determines which of its peers are actually operating by declaring that any site whose heartbeat has changed during the last tMin seconds is up, and otherwise that the server12is down.

FIG. 3shows which disk blocks18are written and read by which servers12in a three server12configuration. An arrow from left to right indicates that the server12on the left writes the disk block18on the right, and an arrow drawn from right to left indicates that the server12on the left reads the disk block18on the right.

The server12determines for whom to vote based on the following algorithm. First, if a proper majority of those servers12that are up are voting for a server12, and that server12believes that it has won the election, then the server12deciding how to vote casts its vote for the current election winner, to minimize disruption to the election process if servers12come up at varying times. Otherwise, the server12votes for the working server12with the lowest index, subject to the constraint that a server12can not vote for a new server12within tMax seconds of casting a vote for another server12; in the interim it must vote for a null server12indicating that it casts no vote. If a server12discovers that it has a majority of votes from the set of servers12, it sets the amPrimaryServer flag in its own record to indicate that the server12believes that it has won the election at least for another tMin seconds.

Under the assumptions that clock rate skew is limited to being below the fraction (tMax−tMin)/tMax, this algorithm guarantees that no two servers12ever simultaneously claim to win an election.

FIG. 4shows the states that the server12participating in the election protocol goes through.

In this state machine20, the transition from state1to state2occurs if the server12has been in state1for a minimum of tMax seconds, and during that time, has seen itself as the server12that is both functioning and has the lowest index. A transition from state2to state3occurs after a server12sees that it has the votes of a proper majority of the servers12, including itself. A transition from state1to state4occurs after a minimum of tMax seconds if the server12sees that another server X is the server12that is both functioning and has the lowest index of all functioning servers12. A transition from state4to state5occurs if the server12sees that server X has declared itself the winner of the election. A transition directly from state1to state5occurs if a minimum of tMax has passed and during that time server X has declared that it has won the election. A transition from state5to state1occurs if the server12that has declared it has won the election no longer appears up (has not updated its heartbeat field for at least tMax seconds), or no longer declares that it has won the election. A transition from state4to state1occurs if server X no longer appears up. A transition from state2to state1occurs if we have not yet won the election, and another working server12appears with a lower index than ours. A transition from state3to state1occurs if it sees another server12with a lower index decide that it has won the election (this should never happen under normal operation, and should be logged to an error manager as a significant error in the invention's implementation).