Method and apparatus for quantized deadline I/O scheduling

1. A method for storing data, comprising:

receiving a request to store data at a logical block address in a storage pool;

determining a quantized deadline for the request;

placing the request in an Input/Output (I/O) queue using the quantized deadline; and

issuing the request to the storage pool using the I/O queue,

wherein the I/O queue is an AVL tree, and

wherein placing the request in the I/O queue comprises placing the request in the AVL tree with respect to the quantized deadline and the logical block address.

2. The method of claim 1 , wherein the I/O queue comprises a plurality of buckets.

3. The method of claim 2 , wherein the placing the request in the I/O queue further comprises placing the request in one of the plurality of buckets corresponding to the quantized deadline.

4. The method of claim 3 , wherein the request is ordered in the one of the plurality of buckets using the logical block address.

5. The method of claim 2 , wherein the plurality of buckets comprises a “now” bucket and a “later” bucket.

6. The method of claim 1 , further comprising:

processing a highest priority request in the AVL tree; and

re-balancing the AVL tree after the highest priority request has been processed.

7. The method of claim 1 , wherein the I/O queue is associated with a file system.

8. A system for storing data, comprising:

a storage pool configured to store data;

an I/O queue configured to store a request to store data at a logical block address in the storage pool; and

a file system configured to:

receive the request,

determine a quantized deadline for the request,

place the request in the I/O queue using the quantized deadline and the logical block address, and

process the request in the I/O queue,

wherein the I/O queue is an AVL tree, and

wherein placing the request in the I/O queue comprises placing the request in the AVL tree with respect to the quantized deadline and the logical block address.

9. The system of claim 8 , further comprising:

an application configured to issue the request to the file system.

10. The system of claim 8 , wherein the I/O queue is located in the file system.

11. The system of claim 8 , wherein the file system is further configured to issue the request to the storage pool using the I/O queue.

12. The system of claim 8 , wherein the I/O queue comprises a plurality of buckets.

13. The system of claim 12 , wherein the file system is further configured to place the request in one of the plurality of buckets corresponding to the quantized deadline.

14. The system of claim 13 , wherein the request is ordered in the one of the plurality of buckets using the logical block address.

15. The system of claim 12 , wherein the plurality of buckets comprises a “now” bucket and a “later” bucket.

16. The system of claim 15 , wherein the file system is further configured to:

process the “now” bucket; and

update the I/O queue after the “now” bucket has been processed.

17. The system of claim 16 , wherein processing the “now” bucket comprises issuing all requests in the “now” bucket to the storage pool.

18. The system of claim 8 , wherein the file system is further configured to:

process a highest priority request in the AVL tree; and

re-balance the AVL tree after the highest priority request has been processed.

19. A computer system for storing data, comprising:

a processor;

a memory;

a storage device; and

software instructions stored in the memory for enabling the computer systems under control of the processor, to:

receive a request to store data at a logical block address in a storage pool;

determine a quantized deadline for the request;

place the request in an Input/Output (I/O) queue using the quantized deadline; and

issue the request to the storage pool using the I/O queue,

wherein the I/O queue is an AVL tree, and

wherein placing the request in the I/O queue comprises placing the request in the AVL tree with respect to the quantized deadline and the logical block address.

20. The computer system of claim 19 , wherein the I/O queue comprises a plurality of buckets.

21. The computer system of claim 20 , wherein placing the request in the I/O queue further comprises placing the request in one of the plurality of buckets corresponding to the quantized deadline.

22. The computer system of claim 21 , wherein the request is ordered in the one of the plurality of buckets using the logical block address.

23. The computer system of claim 19 , further comprising software instructions stored in the memory for enabling the computer system, under control of the processor, to:

process a highest priority request in the AVL tree; and

re-balance the AVL tree after the highest priority request has been processed.

24. A computer readable medium comprising software instructions for enabling a computer system, under the control of a processor, to:

receive a request to store data at a logical block address in a storage pool;

determine a quantized deadline for the request;

place the request in an Input/Output (I/O) queue using the quantized deadline; and

issue the request to the storage pool using the I/O queue,

wherein the I/O queue is an AVL tree, and

wherein placing the request in the I/O queue comprises placing the request in the AVL tree with respect to the quantized deadline and the logical block address.

25. The computer readable medium of claim 24 , wherein the I/O queue comprises a plurality of buckets.

26. The computer readable medium of claim 25 , wherein placing the request in the I/O queue further comprises placing the request in one of the plurality of buckets corresponding to the quantized deadline.

27. The computer readable medium of claim 26 , wherein the request is ordered in the one of the plurality of buckets using the logical block address.

28. The computer readable medium of claim 24 , further comprising software instructions for enabling the computer system, under the control of the processor, to:

process a highest priority request in the AVL tree; and

re-balance the AVL tree after the highest priority request has been processed.

29. A plurality of nodes, comprising:

a storage pool configured to store data;

an I/O queue configured to store a request to store data at a logical block address in the storage pool; and

a file system configured to:

receive the request,

determine a quantized deadline for the request,

place the request in the I/O queue using the quantized deadline and the logical block address, and

process the request in the I/O queue,

wherein the storage pool is located on one of the plurality of nodes,

wherein the I/O queue is located on one of the plurality of nodes,

wherein the file system is located on one of the plurality of nodes,

wherein the I/O queue is an AVL tree, and

wherein placing the request in the I/O queue comprises placing the request in the AVL tree with respect to the quantized deadline and the logical block address.