Dynamically quantifying and improving the reliability of distributed data storage systems

1. 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.

2. The method of claim 1 , further comprising the steps of:

calculating a first gain value based at least in part on the first Normalcy Deviation Score;

calculating a first performance loss value;

calculating a first tradeoff value based at least in part on the calculated first gain value and the calculated first performance loss; and

generating the first schedule based at least in part on the calculated first tradeoff value.

3. The method of claim 2 , further comprising the step of:

increasing recovery bandwidth if the calculated first tradeoff value is greater than a user-defined value.

4. The method of claim 1 , wherein the intersection matrix for each specific queue in the set of queues contains the size of a pairwise intersection of potential source disks for the reconstructions in the specific queue.

5. The method of claim 1 , wherein the diskscore comprises a static score and a dynamic score.

6. The method of claim 1 , further comprising the steps of:

calculating a second intersection matrix for reconstructions in a second queue, the second queue having the second lowest redundancy level;

calculating a second Normalcy Deviation Score;

calculating a second diskscore for each disk in the plurality of disks; and

generating a second schedule for the received set of reconstructions based at least in part on the first intersection matrix, the first Normalcy Deviation Score, the first diskscores, the second intersection matrix, the second Normalcy Deviation Score, and the second diskscores.

7. The method of claim 6 , further comprising the steps of:

calculating a second gain value based at least in part on the second Normalcy Deviation Score;

calculating a second performance loss value;

calculating a second tradeoff value based at least in part on the calculated second gain value and the calculated second performance loss; and

generating the second schedule based at least in part on the calculated second tradeoff value.

8. The method of claim 7 , further comprising the step of:

increasing recovery bandwidth if the calculated second tradeoff value is greater than or equal to a user-defined value.

9. A computer readable medium storing computer program instructions for scheduling reconstructions of data in a distributed data storage system comprising a plurality of disks, the computer program instructions defining 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 computer program instructions defining 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

f is a user-defined scaling factor.

10. The computer readable medium of claim 9 , wherein the computer program instructions for scheduling reconstructions of data further comprise computer program instructions defining the steps of:

calculating a first gain value based at least in part on the first Normalcy Deviation Score;

calculating a first performance loss value;

calculating a first tradeoff value based at least in part on the calculated first gain value and the calculated first performance loss; and

generating the first schedule based at least in part on the calculated first tradeoff value.

11. The computer readable medium of claim 9 , wherein the computer program instructions for scheduling reconstructions of data further comprise computer program instructions defining the step of:

increasing recovery bandwidth if the calculated first tradeoff value is greater than a user-defined value.

12. The computer readable medium of claim 9 , wherein the intersection matrix for each specific queue in the set of queues contains the size of a pairwise intersection of potential source disks for the reconstructions in the specific queue.

13. The computer readable medium of claim 9 , wherein the diskscore comprises a static score and a dynamic score.

14. The computer readable medium of claim 9 , wherein the computer program instructions for scheduling reconstructions of data further comprise computer program instructions defining the steps of:

calculating a second intersection matrix for reconstructions in a second queue, the second queue having the second lowest redundancy level;

calculating a second Normalcy Deviation Score;

calculating a second diskscore for each disk in the plurality of disks; and

generating a second schedule for the received set of reconstructions based at least in part on the first intersection matrix, the first Normalcy Deviation Score, the first diskscores, the second intersection matrix, the second Normalcy Deviation Score, and the second diskscores.

15. The computer readable medium of claim 14 , wherein the computer program instructions for scheduling reconstructions of data further comprise computer program instructions defining the steps of:

calculating a second gain value based at least in part on the second Normalcy Deviation Score;

calculating a second performance loss value;

calculating a second tradeoff value based at least in part on the calculated second gain value and the calculated second performance loss; and

generating the second schedule based at least in part on the calculated second tradeoff value.

16. The computer readable medium of claim 15 , wherein the computer program instructions for scheduling reconstructions of data further comprise computer program instructions defining the step of:

increasing recovery bandwidth if the calculated second tradeoff value is greater than a user-defined value.