HMC: A hybrid mirror-and-chained data replication method to support high data availability for disk arrays

A method of distributing a set of data among a plurality of disks, comprising steps of:

• dividing a total number of the disks into a plurality of clusters;
• and,
• storing blocks of the data in each cluster such that each cluster contains a complete set of the data and such that data block placement in each cluster is a unique permutation of the data block placement in other ones of the clusters;
• wherein, for given nurser rn of the disks numbered 0, 1, 2, . . . , rn-1, where r is a number of clusters, n is a number of disks of a cluster, the i.sup.th partition of the j.sup.th replica is placed on the disk numbered d(i,j) in accordance with the relationship d(i,j)=(i+[i/n] * (j-1)) mod n+(j-1) * n.

A video server, comprising:

• a network interface;
• a disk array coupled to the network interface and having a set of movies stored thereon, each of the movies being stored as a plurality of data blocks;
• a scheduler coupled to the disk array, for scheduling transmission of the movies to users, by way of the network interface;
• and,
• a disk controller coupled to the disks and the video server for controlling accesses to the disks and for rebalancing data block accesses to remaining operational disks in the disk array in the event of failure of a disk;
• wherein, a complete replicated set of the movies is stored in each of a plurality of groups of the disks, each group of the disks having the data blocks placed thereon such that the data block placement in each group is a unique permutation of the data block placement in other ones of the groups.

A method of storing movies in a video server of a type having a plurality of disks for storage of movies, comprising the steps of:

• selecting a set of the movies to store on the disks;
• placing data blocks of the movies on the disks such that each of a plurality of groups of the disks has a replicated set of the movies stored thereon and such that each group of the disks has the data blocks placed thereon such that the data block placement in each group is a unique permutation of the data block placement in other ones of the groups;
• wherein, when a failure of one of the disks is detected, redirecting accesses for each data block on a failed disk to another one of the disks having a copy of the data block, and;
• rebalancing further access to the disks that remain operational.