Patent ID: 7565569

Claim:
A method for distributing data over a set of N storage devices, wherein N is an integer greater than two, the method comprising: apportioning the data into multiple groups, each group consisting of one to (N−2) blocks of data; for each group, calculating a single parity block, so as to form a parity set of the blocks comprising the one to (N−2) blocks of data and the single parity block; and distributing the blocks of each parity set over the N storage devices so that every storage device stores both parity blocks and data blocks, while for each parity set each of the blocks in the parity set is stored on a different storage device and at least one of the N storage devices stores none of the blocks in the parity set, wherein distributing the blocks comprises distributing the single parity blocks among the N storage devices so that there is a balanced distribution of the parity blocks across the devices; adding one or more storage devices to the N storage devices, thus forming an extended set of the storage devices; and redistributing the blocks among the storage devices in the extended set so as to cause a portion of the blocks stored on the N devices to be redistributed to the one or more additional storage devices, while maintaining the balanced distribution and while ensuring that every storage device in the extended set stores both parity blocks and data blocks, while for each parity set each of the blocks in the parity set is stored on a different storage device and at least one of the storage devices in the extended set stores none of the blocks in the parity set, and without requiring a transfer of blocks between the storage devices in the N devices.