Cost-based garbage collection scheduling in a distributed storage environment

1. A computer system comprising:

one or more processors; and

one or more computer-readable storage media having stored thereon computer-executable instructions that are executable by the one or more processors to cause the computer system to schedule garbage collection in a distributed environment that includes a plurality of partitions that point to a plurality of data blocks that store data objects, the garbage collection scheduling being based on a cost to reclaim one or more of the data blocks for further use, the computer-executable instructions including instructions that are executable to cause the computer system to perform at least the following:

determining a reclaim cost for one or more data blocks of one or more of the plurality of partitions during a garbage collection operation;

determining a byte constant multiplier that is configured to modify the reclaim cost to account for the amount of data objects that may be rewritten during the garbage collection operation;

accessing one or more of a baseline reclaim budget and a baseline rewrite budget, the baseline reclaim budget specifying an acceptable amount of data blocks that should be reclaimed by the garbage collection operation and the baseline rewrite budget specifying an upper limit on the amount of data objects that may be rewritten during the garbage collection operation;

iteratively varying one or more of the baseline reclaim budget, the baseline rewrite budget, and byte constant multiplier to determine an effect on the reclaim cost; and

generating a schedule for garbage collection, the schedule including those data blocks that at least partially minimize the reclaim cost based on the iterative varying.

2. The computing system according to claim 1 , wherein the reclaim cost includes a partition cost that specifies a cost of a number IOs needed to read metadata related to an occupancy of data objects on data blocks.

3. The computing system according to claim 1 , wherein the reclaim cost includes a data block cost that specifies a cost for rewriting the data objects stored on a first data block to a second data block.

4. The computing system according to claim 1 , wherein the reclaim cost includes a partition cost that specifies a cost of a number IOs needed to read metadata related to an occupancy of data objects on data blocks and a data block cost that specifies a cost for rewriting the data objects stored on a first data block to a second data block, wherein the partition cost and the data block cost are specified in terms of a latency and wherein data block cost is multiplied by the byte constant multiplier.

5. The computing system according to claim 1 , further comprising:

amortizing at least a portion of the reclaim cost.

6. The computing system according to claim 1 , further comprising:

modifying at least a portion of the reclaim cost to account for one or more data blocks that are shared by two or more partitions.

7. The computing system according to claim 1 , wherein one or more of the baseline reclaim budget, the baseline rewrite budget, and byte cost multiplier are determined based on historical data.

8. The computing system according to claim 1 , wherein the reclaim cost is determined based on historical data.

9. A method for scheduling garbage collection in a distributed environment that includes a plurality of partitions that reference a plurality of data blocks that store data objects, the garbage collection scheduling being based on a cost to reclaim one or more of the data blocks for further use, the method comprising:

an act of determining a reclaim cost for one or more data blocks of one or more of the plurality of partitions during a garbage collection operation;

an act of determining a byte constant multiplier that is configured to modify the cost information reclaim cost to account for the amount of data objects that may be rewritten during the garbage collection operation;

an act of accessing one or more of a baseline reclaim budget and a baseline rewrite budget, the baseline reclaim budget specifying an acceptable amount of data blocks that should be reclaimed by the garbage collection operation and the baseline rewrite budget specifying an upper limit on the amount of data objects that may be rewritten during the garbage collection operation;

an act of iteratively varying one or more of the baseline reclaim budget, the baseline rewrite budget, and byte constant multiplier to determine an effect on the reclaim cost; and

an act of generating a schedule for garbage collection, the schedule including those data blocks that at least partially minimize the reclaim cost based on the iterative varying.

10. The method according to claim 9 , wherein the reclaim cost includes a partition cost that specifies a cost of a number IOs needed to read metadata related to an occupancy of data objects on data blocks.

11. The method according to claim 9 , wherein the reclaim cost includes a data block cost that specifies a cost for rewriting the data objects stored on a first data block to a second data block.

12. The method according to claim 9 , wherein the reclaim cost includes a partition cost that specifies a cost of a number IOs needed to read metadata related to an occupancy of data objects on data blocks and a data block cost that specifies a cost for rewriting the data objects stored on a first data block to a second data block, wherein the partition cost and the data block cost are specified in terms of a latency and wherein data block cost is multiplied by the byte constant multiplier.

13. The method according to claim 9 , further comprising:

amortizing at least a portion of the reclaim cost.

14. The method according to claim 9 , further comprising:

modifying at least a portion of the reclaim cost to account for one or more data blocks that are shared by two or more partitions.

15. The method according to claim 9 , wherein one or more of the baseline reclaim budget, the baseline rewrite budget, and byte cost multiplier are determined based on historical data.

16. The method according to claim 9 , wherein the reclaim cost is determined based on historical data.

17. A computer system comprising:

one or more processors; and

one or more computer-readable storage media having stored thereon computer-executable instructions that are executable by the one or more processors to cause the computer system to schedule garbage collection in a distributed environment that includes a plurality of partitions that point to a plurality of data blocks that store data objects, the garbage collection scheduling being based on a cost to reclaim one or more of the data blocks for further use, the computer-executable instructions including instructions that are executable to cause the computer system to perform at least the following:

determining a partition cost of one or more of the plurality of partitions;

determining a data block cost for one or more data blocks that may be subjected to a garbage collection operation;

determining an overall reclaim cost by specifying both the partition cost and the data block cost in terms of a computing system latency;

applying a byte constant multiplier that is configured to modify the overall reclaim cost to account for the amount of data objects that may be rewritten during the garbage collection operation; and

determining the one or more partitions and/or one or more data blocks that have the lowest overall reclaim cost while reclaiming an acceptable amount of data block space to be included in a garbage collection schedule.

18. The computing system of claim 17 , wherein determining the one or more partitions and/or one or more data blocks comprises:

determining a baseline rewrite budget;

determining a baseline reclaim budget; and

iteratively varying one or more of the baseline rewrite budget, the baseline reclaim budget, and the byte constant multiplier to determine an effect on the overall reclaim cost.

19. The computing system according to claim 17 , wherein the partition cost specifies a cost of a number IOs needed to read metadata related to an occupancy of data objects on data blocks'.

20. The computing system according to claim 17 , wherein the data block cost specifies a cost for rewriting the data objects stored on a first data block to a second data block, wherein data block cost is multiplied by the byte constant multiplier.