Patent ID: 7721044

Claim:
A method for expanding the data storage capacity of a storage cluster having two or more storage nodes, the method comprising: storing two or more maps, each map defining a stripe pattern for storing data on the storage nodes; striping data across the storage nodes of the cluster according to a first map; in response to the addition of a new storage node to the cluster, re-striping the data across the storage nodes according to a second map, wherein the stripe pattern for each map is defined such that when the storage cluster is striped according to the first map and the new storage node is added to the cluster, data is re-striped between the storage nodes according to the second map such that only the data that will subsequently reside in the new storage node is moved to the new storage node during re-striping, wherein the stripe pattern for each map is further defined such that when the new storage node is added to the cluster and the cluster is re-striped according to the second map, no movement of data occurs between two storage nodes that existed in the storage cluster prior to the addition of the new storage node, wherein the stripe pattern for each map is further defined such that when the new storage node is added to the cluster and the cluster is re-striped according to the second map, an equal amount of data is moved to the new storage node from each of the storage nodes that existed in the storage cluster prior to the addition of the new storage node, wherein data on the storage nodes is divided into storage zones, and wherein re-striping the data across the storage nodes according to a second map comprises identifying one or more storage zones to be moved to the new storage node based on the first and second maps, and individually moving each of the identified storage zones to the new storage node; and locking each storage zone individually while each storage zone is moved to the new storage node.