Arbitration of disk ownership in a storage pool

CROSS-REFERENCE TO RELATED APPLICATIONS

Not Applicable.

BACKGROUND

1. Background and Relevant Art

Computer systems and related technology affect many aspects of society. Indeed, the computer system's ability to process information has transformed the way we live and work. Computer systems now commonly perform a host of tasks (e.g., word processing, scheduling, accounting, etc.) that prior to the advent of the computer system were performed manually. More recently, computer systems have been coupled to one another and to other electronic devices to form both wired and wireless computer networks over which the computer systems and other electronic devices can transfer electronic data. Accordingly, the performance of many computing tasks is distributed across a number of different computer systems and/or a number of different computing environments.

Clustering refers to the grouping of multiple computer systems, referred to herein as nodes. Oftentimes, a cluster employs shared storage to enable applications executing on any of the nodes to access the same data. Shared storage enables fail over of applications from node to node in the cluster. For example, if a node fails, the applications executing on the failed node can be switched over to another node where they continue executing. Because the data used by the failed over applications is stored on a shared storage accessible from any node, the applications can continue to execute (e.g. access the same data) after being switched to another node. In this way, the failover is essentially transparent from a user's perspective.

To implement a cluster, it is necessary to maintain consistency across nodes. For example, cluster configuration data should remain consistent across nodes even though each node has access to the configuration data. As long as each node can communicate with the other nodes in the cluster, consistency can be maintained. In some clusters, each node stores a copy of the cluster configuration data, and a cluster service synchronizes the data across nodes.

One problem arises when a network partition occurs thus preventing nodes from communicating. <figref idrefs="DRAWINGS">FIG. 1</figref> (Prior Art) illustrates an example where a network partition <b>107</b> has occurred in a cluster <b>100</b> preventing a first partition of nodes (nodes <b>101</b>-<b>102</b>) from communicating with a second partition of nodes (nodes <b>103</b>-<b>104</b>). Shared storage <b>106</b> remains accessible to each node of the cluster; however, nodes in the first partition cannot communicate with nodes in the second partition. When such a split in the cluster occurs, it is necessary that only one partition continues functioning as a cluster to ensure that consistency is maintained.

To ensure that only one partition in a cluster continues executing (i.e. retains access to shared storage <b>106</b>), the cluster service requires a partition to have quorum. In general, having quorum means that the partition comprises a majority of the elements in the cluster. Depending on the configuration of the cluster, elements can include the nodes of the cluster and possibly a disk (sometimes referred to as a disk witness) or a file share. Disk witnesses are used when an even number of nodes exist to prevent the situation where a tie would occur (e.g. if only the nodes were considered when determining majority).

In <figref idrefs="DRAWINGS">FIG. 1</figref>, both the first and the second partition have the same number of nodes. Accordingly, whichever partition has ownership of shared storage <b>106</b> will have quorum (i.e. 2 nodes+1 disk). When a node owns a disk, it has write access to the disk. Other nodes can also write to the disk, but the owner can control which nodes can have access. In this way, a single node is given control over who can access the disk. In <figref idrefs="DRAWINGS">FIG. 1</figref>, prior to the occurrence of network partition <b>107</b>, node <b>101</b> has ownership of shared storage <b>106</b>.

In general, an owner node allows access to nodes that it knows are members of the cluster and are within the owner node's partition (e.g. when a partition occurs). Therefore, when a partition occurs, the node that owns the disk is responsible for preventing nodes outside the majority from accessing shared storage. For example, in <figref idrefs="DRAWINGS">FIG. 1</figref>, node <b>101</b>, as owner, would prevent nodes <b>103</b>-<b>104</b> from accessing shared storage <b>106</b> after network partition <b>107</b> occurs.

Disk ownership is commonly determined and managed using a SCSI protocol known as Persistent Reservation (PR). PR is a defense/challenge mechanism. In PR, each node has a unique key known as a registration key. To obtain ownership of a disk, a node must have registered its key, and then must obtain a reservation with the key.

<figref idrefs="DRAWINGS">FIG. 2A</figref> (Prior Art) illustrates two tables that are used in PR. <figref idrefs="DRAWINGS">FIG. 2A</figref> represents the state of the two tables when node <b>101</b> is the current owner of the disk (shared storage <b>106</b>). Although two tables are shown in this example, PR can be implemented using a single table or other data structure to store similar information.

To have write access to a disk, a node must register its registration key. A node registers its key by adding it to registration table <b>201</b>. For example, registration table <b>201</b> shows that nodes <b>101</b>-<b>104</b> have each registered their key. Accordingly, nodes <b>101</b>-<b>104</b> have write access to shared storage <b>106</b>.

Once registered, a node can then attempt to reserve its key by adding it to reservation table <b>202</b>. For example, reservation table <b>202</b> shows that node <b>101</b> has successfully reserved its key thereby making node <b>101</b> the owner of the disk. Once a node reserves its key, it can use its key to control the disk.

If, however, a reservation already exists when a node (referred to as a challenger) attempts to reserve its key, the reservation will fail. For example, because node <b>101</b>'s key is already reserved, any other node's attempt to reserve its key will fail. As part of this failed reservation, a challenger receives the current reservation key (e.g. node <b>101</b>'s key).

When a reservation already exists, a node must first preempt the reservation before it can reserve its own key. To enable an owner node (referred to as the defender) to defend its ownership of a disk, PR rules require a challenger to wait a specified time period (generally 6 seconds) after a reservation fails before issuing a preempt command. After this time period, the challenger awakes and issues a preempt command to attempt to remove the defender's key from the reservation table. The preempt command specifies the challenger's key as well as the current reservation key (the defender's key reserved in the reservation table that the challenger received when it failed reservation). For example, the preempt command specifies the key to remove from reservation table <b>202</b> (the defender's key), as well as the key to reserve in reservation table <b>202</b> (the challenger's key).

For the preempt command to succeed, the challenger's key must still be in registration table <b>201</b>. To defend its ownership (i.e. to cause the challenger's preempt command to fail), the defender must remove the challenger's registration key from registration table <b>201</b> before the challenger issues a preempt command. Generally, every 3 seconds, the defender will awake and check reservation table <b>202</b> to determine whether any challenges have been made. Because the defender owns the disk, it can remove any other node's registration key from the registration table <b>201</b>.

When node <b>101</b> sees node <b>104</b>'s key in registration table <b>201</b>, node <b>101</b> will remove node <b>104</b>'s registration key from registration table <b>201</b>. <figref idrefs="DRAWINGS">FIG. 2B</figref> (Prior Art) represents the state of the two tables after node <b>101</b> has defended against node <b>104</b>'s challenge. As shown, node <b>104</b>'s key is no longer listed in registration table <b>201</b>.

Accordingly, when node <b>104</b> awakes and issues a preempt command, the preempt command will fail because the defender has already removed node <b>104</b>'s registration key. Because node <b>104</b>'s registration key has been removed from registration table <b>201</b>, node <b>104</b> no longer has access to shared storage <b>106</b>.

Because the defender sleeps for a shorter duration than the challenger, as long as the defender remains functional and has no reason to not defend its ownership, it will retain ownership by periodically removing the registration keys of any node challenging for ownership. However, if the defender fails or otherwise loses access to the disk, it will fail to remove the registration key of a challenger thereby allowing the challenger to successfully preempt ownership (i.e. remove the defender's keys from the registration and reservation table).

In addition to removing a challenger's registration key in a defense, a defender will also periodically remove the registration keys of any nodes that it does not recognize as being part of the active cluster. In other words, a node in a cluster is periodically updated regarding which nodes it can communicate with. If an owner node receives a notification that it cannot communicate with another node in the cluster (e.g. due to a network partition), the owner node will remove the other node's registration key to prevent the other node from accessing cluster storage.

Accordingly, in conventional PR, there are two general ways in which a node's registration key will be removed: (1) when the owner node receives notification that it cannot communicate with the node; and (2) when the node unsuccessfully challenges for ownership of the shared storage.

When a network partition occurs (i.e. when a node becomes aware that it cannot communicate with each node in the cluster), a node in a partition that does not have ownership of the disk generally will begin challenging for ownership of the disk. For example, in <figref idrefs="DRAWINGS">FIG. 1</figref>, after network partition <b>107</b> occurs, one or more of nodes <b>103</b>-<b>104</b> can commence a challenge to preempt node <b>101</b>'s ownership of shared storage <b>106</b> (because nodes <b>103</b> and <b>104</b> need ownership of shared storage <b>106</b> to obtain quorum (to thereby be able to continue functioning within the cluster).

In <figref idrefs="DRAWINGS">FIG. 1</figref>, network partition <b>107</b> does not prevent any of the nodes from accessing shared storage <b>106</b> (i.e. it only prevents nodes <b>101</b>-<b>102</b> from communicating with nodes <b>103</b>-<b>104</b>). Accordingly, node <b>101</b> will continue to defend its ownership of shared storage <b>106</b> from node <b>103</b>'s or node <b>104</b>'s challenges.

If, however, node <b>101</b> were to fail or otherwise lose connection to shared storage <b>106</b> (or determine that it should not defend because it is not in a partition that could have quorum), challenges from node <b>103</b> or <b>104</b> would succeed (because node <b>101</b> would not be able to remove node <b>103</b>'s or node <b>104</b>'s registration keys). As a result, when the challenger (node <b>103</b> or node <b>104</b>) awakes, its registration key will still be listed in registration table <b>201</b> thus allowing it to preempt node <b>101</b>'s ownership. The challenger will then take ownership of shared storage <b>106</b>. As owner, the node will commence defending its ownership as described above (e.g. if node <b>101</b> or <b>102</b> commenced challenging for ownership).

The above example describes a cluster that provides the nodes and the storage with votes to determine ownership. Other voting schemes also exist which use the PR techniques described above. These schemes include node only voting (where only the nodes have a vote), and node+file share voting (where the nodes and a file share vote). Node only voting is commonly used when the cluster includes an odd number of nodes. Node+file share voting is similar to the node+storage voting described above, but is used when a file share is used for shared storage.

PR as described above functions correctly within many typical storage configurations. However, PR, as described above, is not always satisfactory when used in other types of storage configurations (e.g. when a cluster employs virtual disks as shared storage). In the Windows operating system, virtual disks are referred to as “Storage Spaces.” In a Storage Space, multiple physical disks are aggregated into a storage pool. The storage pool can then be divided into one or more logical “Spaces” (or virtual disks). Each Space appears to applications as a physical storage device even though the Space is virtualized and may actually span many different physical storage devices.

For example, <figref idrefs="DRAWINGS">FIG. 3</figref> (Prior Art) illustrates a cluster <b>300</b> that is similar to cluster <b>100</b> of <figref idrefs="DRAWINGS">FIG. 1</figref> except that shared storage <b>106</b> has been replaced by storage pool <b>306</b>. Storage pool <b>306</b> comprises three physical storage devices <b>310</b>-<b>312</b>. From this pool, the user can create one or more Spaces. <figref idrefs="DRAWINGS">FIG. 3</figref> shows that the user has created a single Space <b>307</b>. Space <b>307</b> can be treated, from the perspective of applications on each node in the cluster, as a normal physical disk.

When Spaces are used, the nodes of the cluster need to have access to each physical disk in the underlying pool because the Spaces can be spread among the physical disks. For example, in cluster <b>300</b>, data written to Space <b>307</b> could be physically stored on any of three physical storage devices in storage pool <b>306</b>. When using Spaces, a single node owns the storage pool (meaning that the node owns each physical disk in the pool).

One particular problem caused by applying standard PR techniques with Spaces is that anytime a challenger attempts to preempt ownership of the pool from which the Spaces are created, the owner of the pool will remove the challenger's key thus causing any I/O to any Space from applications on the challenger to fail (because the challenger's key must be registered with a physical disk to enable the applications on the challenger to write to the physical disk).

Causing I/O from a challenger to fail may be an incorrect result of a challenge. For example, a challenger may be notified of a network partition prior to the defender. In response to the network partition, the challenger commences a challenge for the pool. If the challenger is in a partition that has quorum, the correct result would be for the challenger to win the challenge to take ownership of the pool (to thereby allow the challenger's partition to continue executing).

If, however, the defender has not been notified of the network partition (and accordingly, not notified that it is in a partition that does not have quorum), the defender will successfully defend its ownership of the pool. Using conventional PR techniques as described above, this defense includes removing the challenger's registration key so that any writes from the challenger will fail. The defender will continue to successfully defend its ownership until it receives notification of the network partition. Accordingly, until the defender receives notification of the network partition, the cluster will not commence operating properly on the partition with quorum (i.e. the challenger's partition). In other scenarios, the application of conventional PR techniques also leads to undesirable results.

BRIEF SUMMARY

The present invention extends to methods, systems, and computer program products for implementing persistent reservation techniques for establishing ownership of one or more physical disks. These persistent reservation techniques can be employed to determine ownership of physical disks in a storage pool as well as in any other storage configuration. Using the persistent reservation techniques of the present invention, when a network partition occurs, a defender of a physical disk does not remove a challenger's registration key until the defender receives notification that the challenger is no longer in the defender's partition. In this way, pending I/O from applications executing on the challenger will not fail due to the challenger's key being removed until the proper ownership of the physical disk can be resolved.

In one embodiment, a first node defends against another node's attempt to preempt the first node's persistent reservation on a storage device. After a network partition that prevents the first node from communicating with another node in the cluster, and prior to the first node being notified of the network partition, the first node detects that another node in the cluster has attempted to reserve the storage device shared by nodes of the cluster. The detection comprises identifying that the other node has changed the other node's registration key in a registration data structure.

The first node changes the first node's registration key, registers the changed registration key in the registration data structure, and reserves the changed registration key in a reservation data structure.

In another embodiment, a second node attempts to remove a first node's persistent reservation on a storage device so as to obtain a persistent reservation for the second node. The second node receives a notification that a network partition has occurred that prevents the second node from communicating with the first node.

The second node attempts to reserve the second node's registration key so as to obtain a persistent reservation on the storage device. The attempt to reserve includes the second node reading the registration key of the first node that is stored in a reservation data structure and storing the first node's key. The attempt to reserve also includes the second node changing the second node's registration key and registering the changed registration key. The attempt to reserve also includes the second node sleeping for a specified duration of time prior to issuing a preempt command to remove the first node's persistent reservation.

This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter.

Additional features and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by the practice of the invention. The features and advantages of the invention may be realized and obtained by means of the instruments and combinations particularly pointed out in the appended claims. These and other features of the present invention will become more fully apparent from the following description and appended claims, or may be learned by the practice of the invention as set forth hereinafter.

BRIEF DESCRIPTION OF THE DRAWINGS

In order to describe the manner in which the above-recited and other advantages and features of the invention can be obtained, a more particular description of the invention briefly described above will be rendered by reference to specific embodiments thereof which are illustrated in the appended drawings. Understanding that these drawings depict only typical embodiments of the invention and are not therefore to be considered to be limiting of its scope, the invention will be described and explained with additional specificity and detail through the use of the accompanying drawings in which:

<figref idrefs="DRAWINGS">FIG. 1</figref> illustrates a typical cluster of nodes in which convention persistent reservation techniques are used.

<figref idrefs="DRAWINGS">FIGS. 2A-2B</figref> illustrate exemplary tables used in implementing conventional persistent reservation.

<figref idrefs="DRAWINGS">FIG. 3</figref> illustrates a cluster of nodes which employs a virtual disk for shared storage.

<figref idrefs="DRAWINGS">FIG. 4</figref> illustrates another cluster of nodes which employs a plurality of virtual disks for shared storage.

<figref idrefs="DRAWINGS">FIGS. 5A-5F</figref> illustrate exemplary tables used in implementing the persistent reservation techniques of the present invention;

<figref idrefs="DRAWINGS">FIG. 6</figref> illustrates an exemplary format of a registration key that can be used for persistent reservation according to the present invention;

<figref idrefs="DRAWINGS">FIG. 7</figref> illustrates a flow chart of an example method for a first node to defend against another node's attempt to preempt the first node's persistent reservation on a storage device; and

<figref idrefs="DRAWINGS">FIG. 8</figref> illustrates a flow chart of an example method for a second node to attempt to remove a first node's persistent reservation on a storage device so as to obtain a persistent reservation for the second node.

DETAILED DESCRIPTION

The present invention extends to methods, systems, and computer program products for implementing persistent reservation techniques for establishing ownership of one or more physical disks. These persistent reservation techniques can be employed to determine ownership of physical disks in a storage pool as well as in any other storage configuration. Using the persistent reservation techniques of the present invention, when a network partition occurs, a defender of a physical disk does not remove a challenger's registration key until the defender receives notification that the challenger is no longer in the defender's partition. In this way, pending I/O from applications executing on the challenger will not fail due to the challenger's key being removed until the proper ownership of the physical disk can be resolved.

In one embodiment, a first node defends against another node's attempt to preempt the first node's persistent reservation on a storage device. After a network partition that prevents the first node from communicating with another node in the cluster, and prior to the first node being notified of the network partition, the first node detects that another node in the cluster has attempted to reserve the storage device shared by nodes of the cluster. The detection comprises identifying that the other node has changed the other node's registration key in a registration data structure.

The first node changes the first node's registration key, registers the changed registration key in the registration data structure, and reserves the changed registration key in a reservation data structure.

In another embodiment, a second node attempts to remove a first node's persistent reservation on a storage device so as to obtain a persistent reservation for the second node. The second node receives a notification that a network partition has occurred that prevents the second node from communicating with the first node.

The second node attempts to reserve the second node's registration key so as to obtain a persistent reservation on the storage device. The attempt to reserve includes the second node reading the registration key of the first node that is stored in a reservation data structure and storing the first node's key. The attempt to reserve also includes the second node changing the second node's registration key and registering the changed registration key. The attempt to reserve also includes the second node sleeping for a specified duration of time prior to issuing a preempt command to remove the first node's persistent reservation.

Embodiments of the present invention may comprise or utilize a special purpose or general-purpose computer including computer hardware, such as, for example, one or more processors and system memory, as discussed in greater detail below. Embodiments within the scope of the present invention also include physical and other computer-readable media for carrying or storing computer-executable instructions and/or data structures. Such computer-readable media can be any available media that can be accessed by a general purpose or special purpose computer system. Computer-readable media that store computer-executable instructions are computer storage media (devices). Computer-readable media that carry computer-executable instructions are transmission media. Thus, by way of example, and not limitation, embodiments of the invention can comprise at least two distinctly different kinds of computer-readable media: computer storage media (devices) and transmission media.

Computer storage media (devices) includes RAM, ROM, EEPROM, CD-ROM, solid state drives (“SSDs”) (e.g., based on RAM), Flash memory, phase-change memory (“PCM”), other types of memory, other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store desired program code means in the form of computer-executable instructions or data structures and which can be accessed by a general purpose or special purpose computer.

A “network” is defined as one or more data links that enable the transport of electronic data between computer systems and/or modules and/or other electronic devices. When information is transferred or provided over a network or another communications connection (either hardwired, wireless, or a combination of hardwired or wireless) to a computer, the computer properly views the connection as a transmission medium. Transmissions media can include a network and/or data links which can be used to carry or desired program code means in the form of computer-executable instructions or data structures and which can be accessed by a general purpose or special purpose computer. Combinations of the above should also be included within the scope of computer-readable media.

Further, upon reaching various computer system components, program code means in the form of computer-executable instructions or data structures can be transferred automatically from transmission media to computer storage media (devices) (or vice versa). For example, computer-executable instructions or data structures received over a network or data link can be buffered in RAM within a network interface module (e.g., a “NIC”), and then eventually transferred to computer system RAM and/or to less volatile computer storage media (devices) at a computer system. Thus, it should be understood that computer storage media (devices) can be included in computer system components that also (or even primarily) utilize transmission media.

Computer-executable instructions comprise, for example, instructions and data which, when executed at a processor, cause a general purpose computer, special purpose computer, or special purpose processing device to perform a certain function or group of functions. The computer executable instructions may be, for example, binaries, intermediate format instructions such as assembly language, or even source code. Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the described features or acts described above. Rather, the described features and acts are disclosed as example forms of implementing the claims.

Those skilled in the art will appreciate that the invention may be practiced in network computing environments with many types of computer system configurations, including, personal computers, desktop computers, laptop computers, message processors, hand-held devices, multi-processor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, mobile telephones, PDAs, tablets, pagers, routers, switches, and the like. The invention may also be practiced in distributed system environments where local and remote computer systems, which are linked (either by hardwired data links, wireless data links, or by a combination of hardwired and wireless data links) through a network, both perform tasks. In a distributed system environment, program modules may be located in both local and remote memory storage devices.

Although the present invention is described as being implemented in cluster <b>400</b> shown in <figref idrefs="DRAWINGS">FIG. 4</figref>, it is to be understood that the PR techniques can also be implemented in other computer architectures that include multiple nodes. Cluster <b>400</b> includes four interconnected nodes (nodes <b>401</b>-<b>404</b>). Each node is connected to each of storage devices <b>410</b>-<b>412</b>. Storage devices <b>410</b>-<b>412</b> comprise storage pool <b>420</b> from which multiple virtual disks (or Spaces) <b>430</b><i>a</i>-<b>430</b><i>n </i>have been created. Accordingly, applications on each node can access each of virtual disks <b>430</b><i>a</i>-<b>430</b><i>n</i>. It is assumed that quorum in cluster <b>400</b> is determined using a nodes+storage voting scheme. Accordingly, each of nodes <b>401</b>-<b>404</b> and pool <b>420</b> has a vote. A single node owns each storage device in pool <b>420</b> at a given time.

Additionally, <figref idrefs="DRAWINGS">FIGS. 5A-5F</figref> illustrate various states of a registration table <b>501</b> and a reservation table <b>502</b> that can be maintained to implement the PR techniques of the present invention. A separate set of registration and reservation tables is maintained for each of storage devices <b>410</b>-<b>412</b>. In the following description, it will be assumed that registration table <b>501</b> and reservation table <b>502</b> pertain to storage device <b>410</b>, but it should be understood that a similar process would be followed for determining ownership of each storage device. Also, even though two tables are shown, the present invention can be implemented using a single table or any number of other data structures. Accordingly, the data structure used to store the keys is not essential to the invention.

<figref idrefs="DRAWINGS">FIGS. 5A-5F</figref> also include nodes <b>401</b> and <b>404</b> to illustrate how the nodes store currently reserved keys during the PR process of the present invention. Of course, although not shown, each node also stores its registration key.

<figref idrefs="DRAWINGS">FIG. 5A</figref> represents the state of the two tables prior to the occurrence of network partition <b>405</b>. In <figref idrefs="DRAWINGS">FIG. 5A</figref>, registration table <b>501</b> includes four registration keys, one for each of nodes <b>401</b>-<b>404</b> indicating that each node in the cluster can write to storage device <b>410</b>. Reservation table <b>502</b> also includes node <b>401</b>'s registration key indicating that node <b>401</b> has a reservation on storage device <b>410</b> (i.e. node <b>401</b> is the current owner of the physical disk).

When network partition <b>405</b> occurs, each node in the cluster will be notified of the partition. However, each node will not necessarily be notified at the same time. In this example, node <b>404</b> has been notified of network partition <b>405</b> and accordingly has commenced a challenge for ownership of each storage device in pool <b>420</b> (because node <b>404</b>'s partition needs ownership of pool <b>420</b> to have quorum).

Node <b>401</b>, however, at the time of node <b>404</b>'s challenge has yet to be notified of network partition <b>405</b>. As such, node <b>401</b> will think that it is still in the same partition as node <b>404</b>. In conventional PR, when node <b>404</b> challenges for ownership of storage device <b>410</b>, the fact that node <b>401</b> still thinks that node <b>404</b> is in the same partition would not matter, and node <b>401</b> would remove node <b>404</b>'s registration key from registration table <b>501</b> thus causing I/O from node <b>404</b> to fail.

In contrast, in the present invention, different PR techniques are applied to ensure that node <b>401</b> does not remove node <b>404</b>'s registration key until node <b>401</b> knows that node <b>404</b> is no longer in the same partition. <figref idrefs="DRAWINGS">FIGS. 5B-5E</figref> illustrates how the PR techniques of the present invention are implemented.

<figref idrefs="DRAWINGS">FIG. 5B</figref> represents the state of the two tables after node <b>404</b> has commenced a challenge for ownership of storage device <b>410</b>. Accordingly, <figref idrefs="DRAWINGS">FIG. 5B</figref> can represent the time period while node <b>404</b> is asleep and node <b>401</b> has not yet awakened to defend its ownership.

Node <b>404</b> attempts to reserve by performing the following tasks. Node <b>404</b> increments (or otherwise changes) its own registration key and registers it in registration table <b>501</b> (in place of its old registration key). However, because node <b>401</b> is the current owner, node <b>404</b>'s attempt to reserve will initially fail thus requiring node <b>404</b> to sleep before attempting to preempt node <b>401</b>'s reservation. Because the reservation failed, node <b>404</b> also reads the current reservation key (node <b>401</b>'s key in reservation table <b>502</b>) and stores it.

Accordingly, <figref idrefs="DRAWINGS">FIG. 5B</figref>, shows that registration table <b>501</b> has been changed by replacing node <b>404</b>'s old registration key with node <b>404</b>'s incremented registration key. In <figref idrefs="DRAWINGS">FIG. 5B</figref>, node <b>404</b> is shown as storing the current reservation key, node <b>401</b>'s registration key.

<figref idrefs="DRAWINGS">FIG. 5C</figref> represents the state of the two tables after node <b>401</b> has awakened to defend its ownership, but prior to node <b>401</b> being notified of network partition <b>405</b>. In a defense, a node removes the registration keys of any nodes that are not recognized as being part of the owner node's partition. Accordingly, when node <b>401</b> sees node <b>404</b>'s incremented registration key in registration table <b>501</b>, node <b>401</b> will not remove node <b>404</b>'s registration key because node <b>401</b> still believes node <b>404</b> is in the same partition.

Rather than remove node <b>404</b>'s registration key from registration table <b>501</b> (thus preventing node <b>404</b> from writing to storage device <b>410</b>), node <b>401</b> instead increments its own registration key, registers the incremented key, and reserves the incremented key. This is the owner node's form of defense when a node that is not known to be in a different partition challenges for ownership.

Accordingly, <figref idrefs="DRAWINGS">FIG. 5C</figref> shows that registration table <b>501</b> and reservation table <b>502</b> now each include node <b>401</b>'s incremented registration key in place of node <b>401</b>'s previous key. In short, because node <b>401</b> does not yet know that node <b>401</b> and node <b>404</b> are no longer in the same partition, node <b>401</b>'s response to node <b>404</b>'s challenge involves incrementing and reserving its registration key rather than removing node <b>404</b>'s registration key from registration table <b>501</b>.

<figref idrefs="DRAWINGS">FIG. 5D</figref> represents the state of the two tables after node <b>404</b> has awakened and issued preempt command <b>530</b>. Preempt command <b>530</b> includes node <b>404</b>'s current registration key and the reservation key that node <b>404</b> read prior to sleeping. Because node <b>401</b> has incremented its registration key and reserved the incremented key, the reservation key held by node <b>404</b> will not match the current reservation key stored in reservation table <b>502</b> (Node_—401_key_—0001 !=Node_—401_key_—0002). Thus, node <b>404</b>'s preemption attempt will fail, and node <b>401</b> will remain owner of storage device <b>410</b>. <figref idrefs="DRAWINGS">FIG. 5D</figref> accordingly shows that both tables remain the same as in <figref idrefs="DRAWINGS">FIG. 5C</figref> because node <b>401</b> has remained owner but has not removed node <b>404</b>'s registration.

At some later time, node <b>404</b> (or similarly, node <b>403</b>) can commence another challenge in the manner described with respect to <figref idrefs="DRAWINGS">FIGS. 5A-5B</figref>. <figref idrefs="DRAWINGS">FIG. 5E</figref> represents the state of the two tables after node <b>404</b> has commenced another challenge. As shown, registration table <b>501</b> now includes node <b>404</b>'s incremented key (Node_—404_key_—0003). Node <b>404</b> has also stored the current reservation key (Node_—401_key_—0002).

Prior to node <b>401</b> awakening to defend its ownership, node <b>401</b> has been notified of network partition <b>405</b>. Accordingly, node <b>401</b> responds differently to node <b>404</b>'s challenge. In particular, node <b>401</b> now knows that node <b>404</b> is not in the same partition, and as such, node <b>401</b> removes node <b>404</b>'s registration key from registration table <b>501</b> causing node <b>404</b>'s challenge to fail as well as preventing node <b>404</b> from writing to storage device <b>410</b>.

<figref idrefs="DRAWINGS">FIG. 5F</figref>, therefore, represents the state of the two tables after node <b>401</b> has been notified of network partition <b>405</b> and after node <b>401</b> has defended against node <b>404</b>'s challenge. As shown, registration table <b>501</b> does not include node <b>404</b>'s registration key. Although node <b>404</b> is shown as still storing the current reservation key, a preemption attempt by node <b>404</b> would fail because node <b>404</b>'s registration key is not in registration table <b>501</b>.

Although the above description uses the example of incrementing a key, the present invention can also be implemented by changing a key in any other way to notify another node of a challenge. For example, rather than increment its key, node <b>404</b> could change a bit. In essence, the changing of the registration key acts as a way for the nodes to continue communicating even though the network partition has prevented the nodes from directly communicating. Accordingly, any means of modifying the registration key to communicate a node's challenge can be used in the present invention.

It is noted that node <b>404</b>'s registration key may also be removed even without node <b>404</b> commencing a challenge. Any time node <b>401</b> awakes to defend ownership, it first checks for any registration keys of nodes it does not recognize as being part of the same partition. For example, if node <b>401</b> awakes after network partition <b>405</b> and prior to node <b>404</b> commencing a challenge, node <b>401</b> will remove node <b>404</b>'s key (as well as node <b>403</b>'s key) from registration table <b>501</b> because node <b>404</b> and <b>403</b> are no longer in the same partition.

Accordingly, an owner node does not remove another node's registration key until the owner node knows that the other node is not in the same partition as the owner node. In this way, an owner node will not remove another node's key when a network partition occurs until the owner node knows about the network partition and can respond accordingly (e.g. by defending or not defending its ownership).

Of course, during any given defense, the owner node can both remove registration keys of any node it does not recognize as being part of the same partition, as well as increment, register, and reserve its registration key in response to a challenge from a node that it does not yet know is in another partition. Using the same example of <figref idrefs="DRAWINGS">FIGS. 5A-5F</figref>, if node <b>403</b> and <b>404</b> challenged at the same time, but node <b>401</b> had only been notified that node <b>404</b> was no longer in the same partition, node <b>401</b> would remove node <b>404</b>'s key, while leaving node <b>403</b>'s key and incrementing its own key.

Similarly, if at any time, node <b>401</b> became aware that it was in a partition that did not have quorum (e.g. if network partition <b>405</b> separated node <b>401</b> from nodes <b>402</b>-<b>404</b>), node <b>401</b> would not defend its ownership thus allowing one of the nodes in the other partition to successfully preempt node <b>401</b>'s ownership.

As mentioned above, the process described with respect to <figref idrefs="DRAWINGS">FIGS. 5A-5F</figref> is performed for every storage device in a storage pool. For example, node <b>404</b> would challenge for ownership of storage devices <b>411</b> and <b>412</b> in the same manner. A single node, however, should generally have ownership of every storage device in the pool. To ensure that a single node obtains and retains ownership of each storage device, the process described above is carried out on each storage device is a predefined order.

In other words, each node knows of an order in which each storage device should be challenged for. This order can be determined, for example, based on an identifier associated with the storage device (e.g. a pool guide). For example, when node <b>404</b> awakes to issue preempt commands, it can issue the preempt commands in a specified order (such as by preempting on storage device <b>410</b>, then storage device <b>411</b>, then storage device <b>412</b>).

If any preempt command fails, the challenging node will cease challenging for ownership. For example, if node <b>404</b>'s preempt command failed on storage device <b>410</b>, node <b>404</b> would not attempt to preempt ownership of storage devices <b>411</b> and <b>412</b>. By issuing preempt commands in a specified order, the situation can be avoided where one node wins ownership of some storage devices in the pool, while one or more other nodes win ownership of other storage devices in the pool.

In addition to ensuring that an owner node or challenger node is part of a partition that has quorum (or could have quorum by obtaining ownership of the pool), a node can also verify that a quorum of disks in the pool are accessible prior to commencing a defense of or challenge for the storage devices of the pool. For example, when node <b>401</b> awakes to defend its ownership, it can first enumerate all storage devices in pool <b>420</b>. If the number of enumerated storage devices is less than a majority of the storage devices in the pool (e.g. less than 2 of storage devices <b>410</b>-<b>412</b>), node <b>401</b> can cease its defense. Similarly, when node <b>404</b> attempts a challenge, it can also enumerate the storage devices and cease the challenge if a quorum of the storage devices is not accessible. A storage device may be inaccessible if the storage device fails or otherwise stops operating correctly.

<figref idrefs="DRAWINGS">FIG. 6</figref> illustrates an exemplary format for a registration key <b>600</b>. Registration key <b>600</b> includes four sections: an identifier section <b>601</b>, a revision section <b>602</b>, a node identifier section <b>603</b>, and a signature section <b>604</b>. Identifier section <b>601</b> includes an identifier of the storage device for which the registration key is used. Revision section <b>602</b> is the portion of the key that is incremented as described above. Node identifier section <b>603</b> includes an identifier of the node to which the key pertains. Signature portion <b>604</b> includes a unique signature generated by the corresponding node.

<figref idrefs="DRAWINGS">FIG. 7</figref> illustrates a flow chart of an example method <b>700</b> for a first node to defend against another node's attempt to preempt the first node's persistent reservation on a storage device. Method <b>700</b> will be described with respect to FIGS. <b>4</b> and <b>5</b>A-<b>5</b>F.

Method <b>700</b> includes an act <b>701</b> of, after a network partition that prevents the first node from communicating with another node in the cluster, and prior to the first node being notified of the network partition, the first node detecting that another node in the cluster has attempted to reserve the storage device shared by nodes of the cluster. The detection comprises identifying that the other node has changed the other node's registration key in a registration data structure. For example, node <b>401</b> can detect that node <b>404</b> has changed its registration key in registration table <b>501</b> pertaining to storage device <b>410</b> while node <b>401</b> has a persistent reservation on storage device <b>410</b>.

Method <b>700</b> includes an act <b>702</b> of, the first node changing the first node's registration key, registering the changed registration key in the registration data structure, and reserving the changed registration key in the reservation data structure. For example, node <b>401</b> can change (e.g. increment) its registration key, register the changed registration key in registration table <b>501</b>, and reserve the changed registration key in reservation table <b>502</b>.

<figref idrefs="DRAWINGS">FIG. 8</figref> illustrates a flow chart of an example method <b>800</b> for a second node to attempt to remove a first node's persistent reservation on a storage device so as to obtain a persistent reservation for the second node. Method <b>800</b> will be described with respect to FIGS. <b>4</b> and <b>5</b>A-<b>5</b>F.

Method <b>800</b> includes an act <b>801</b> of the second node receiving a notification that a network partition has occurred that prevents the second node from communicating with the first node. For example, node <b>404</b> can receive notification that network partition <b>405</b> has occurred.

Method <b>800</b> includes an act <b>802</b> of the second node attempting to reserve the second node's registration key so as to obtain a persistent reservation on the storage device. Act <b>802</b> includes sub-acts <b>802</b><i>a</i>-<b>802</b><i>c. </i>

Sub-act <b>802</b><i>a </i>includes the second node reading the registration key of the first node that is stored in a reservation data structure and storing the first node's key. For example, node <b>404</b> can read node <b>401</b>'s registration key in reservation table <b>502</b>.

Sub-act <b>802</b><i>b </i>includes the second node changing the second node's registration key and registering the changed registration key. For example, node <b>404</b> can change its registration key and register the changed registration key in registration table <b>501</b>.

Sub-act <b>802</b><i>c </i>includes the second node sleeping for a specified duration of time prior to issuing a preempt command to remove the first node's persistent reservation. For example, node <b>404</b> can sleep for at least twice the duration as the defender node sleeps (e.g. six seconds if the node <b>401</b> sleeps for three seconds) prior to awaking and issuing a preempt command to remove node <b>401</b>'s reservation on storage device <b>410</b>.

The present invention may be embodied in other specific forms without departing from its spirit or essential characteristics. The described embodiments are to be considered in all respects only as illustrative and not restrictive. The scope of the invention is, therefore, indicated by the appended claims rather than by the foregoing description. All changes which come within the meaning and range of equivalency of the claims are to be embraced within their scope.