Patent ID: 8019728

Claim:
A method for scheduling reconstructions of data stored in a distributed data storage system comprising a plurality of disks, the method comprising the steps of: receiving a set of reconstructions; dividing the set of reconstructions into a set of queues rank-ordered by redundancy level ranging from a lowest redundancy level to a highest redundancy level; calculating a first intersection matrix for reconstructions in a first queue, the first queue having the lowest redundancy level; calculating a first Normalcy Deviation Score; calculating a first diskscore for each disk in the plurality of disks; generating a first schedule for the received set of reconstructions based at least in part on the first intersection matrix, the first Normalcy Deviation Score, and the first diskscores, wherein the data is organized into blocks, and wherein the step of calculating a Normalcy Deviation Score comprises the step of calculating a Normalcy Deviation Score according to the algorithm: N ⁢ ⁢ D ⁢ ⁢ S ⁡ ( t ) = ( ∑ i = 0 k - 1 ⁢ b i ⁡ ( t ) × f k - i ) × T alloc , wherein: NDS(t) is the Normalcy Deviation Score at time t; k is the level of redundancy of all blocks in the distributed data storage system under normal operation; b i is the number of blocks that have i levels of redundancy left at time t; T alloc is the minimum time to reconstruct a disk; and is a user-defined scaling factor.