Data allocation in a distributed storage system

Abstract

A method for data distribution, including distributing logical addresses among an initial set of devices so as provide balanced access, and transferring the data to the devices in accordance with the logical addresses. If a device is added to the initial set, forming an extended set, the logical addresses are redistributed among the extended set so as to cause some logical addresses to be transferred from the devices in the initial set to the additional device. There is substantially no transfer of the logical addresses among the initial set. If a surplus device is removed from the initial set, forming a depleted set, the logical addresses of the surplus device are redistributed among the depleted set. There is substantially no transfer of the logical addresses among the depleted set. In both cases the balanced access is maintained.

1 . A method for distributing data among a set of storage devices, comprising: 
 applying a randomizing function to the set so as to allocate logical addresses to respective primary storage devices of the set and so as to provide a balanced access to the devices;    forming subsets of the storage devices by subtracting the respective primary storage devices from the set;    applying the randomizing function to the subsets so as to allocate the logical addresses to respective secondary storage devices of the subsets while maintaining the balanced access to the devices; and    storing the data on the respective primary storage devices and a copy of the data on the respective secondary storage devices in accordance with the logical addresses.    
     
     
         2 . A data distribution system, comprising: 
 a set of data storage devices to which is applied a randomizing function so as to allocate logical addresses to respective primary storage devices of the set and so as to provide a balanced access to the devices; and    subsets of the storage devices formed by subtracting the respective primary storage devices from the set, the randomizing function being applied to the subsets so as to allocate the logical addresses to respective secondary storage devices of the subsets while maintaining the balanced access to the devices, data being stored on the respective primary storage devices and a copy of the data being stored on the respective secondary storage devices in accordance with the logical addresses.