Storage device access mediation

• US 9,917,790 B2
• Filed: 07/31/2014
• Issued: 03/13/2018
• Est. Priority Date: 07/31/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Kuznetsov, Slava, Shankar, Vinod R., D'Amato, Andrea, Petter, Vladimir
• Primary Examiner(s): Vo, Tim T
• Assistant Examiner(s): Iradukunda, Herve
• Application Number:
  US14/448,781
• Publication Number:
  US 20160036720A1
• Time in Patent Office: 1,321 Days
• Field of Search: 711168
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers

Abstract

A system is configured to use a de-randomizer and budget data structure to economize I/O operations for a shared storage device while still allowing access to the device to a number of different entities. Embodiments can identify a comparatively low cost next operation as compared to other I/O operations, including a cost for seek time, for a first entity to dispatch to the storage device when the first entity has sufficient budget to have the I/O operation performed on its behalf and to identify an I/O operation for a second entity to dispatch to the storage device when there is insufficient budget for the first entity.

Claims

1. A computing system for managing outstanding I/O operations for a plurality of entities to a hardware storage device, the system comprising:

a de-randomizer, operating on one or more processors of the computing system, wherein the de-randomizer comprises a plurality of slots for a hardware storage device, each slot comprising a queued list for listing I/O operations to be dispatched to the hardware storage device, wherein the slots are organized based on the hardware storage device size and offsets into the hardware storage device such that operations adjacent to each other in a queued list in the same slot are treated as sequential I/O operations to the hardware storage device to determine I/O cost, and non-adjacent operations within the same slot are treated as sparse I/O operations to the hardware storage device to determine I/O cost, and I/O operations from different queued lists in different slots are treated as random I/O operations to the hardware storage device to determine operation cost;

a plurality of entity queues coupled to the de-randomizer, the entity queues being configured to queue I/O operations for the plurality of entities to the hardware storage device;

a budget data structure coupled to the de-randomizer, wherein the budget data structure is configured to track budgets credits for the plurality of entities to determine which of the plurality of entities have sufficient budget to be allowed to have I/O operations dispatched to the hardware storage device;

wherein, based on either a most recent or current I/O operation dispatched to a hardware storage device, the computing system is configured to use the de-randomizer and budget data structure to identify sequential and sparse operations for a first entity of the plurality of entities to dispatch to the hardware storage device when the first entity has sufficient budget to have the I/O operation performed on its behalf, wherein when selecting the next operation for a first entity, the relative cost of the next operation is determined, including a comparison to other I/O operations and a cost for seek time, and the de-randomizer prioritizes selecting a sequential I/O operation in a given slot over a sparse I/O operation in the given slot;

wherein, based on determining that (i) the first entity has sufficient budget to have an I/O operation performed on its behalf, and that (ii) there are no remaining queued sequential operations in the given slot, the computer system is configured to use the de-randomizer to select a next sparse operation and to dispatch the next sparse operation to the hardware storage device; and

wherein, based on determining that the first entity lacks sufficient budget to have an additional I/O operation performed on its behalf, the computing system is configured to use the de-randomizer to identify an I/O operation for a second entity of the plurality of entities to dispatch to the hardware storage device.

2. The computing system of claim 1, wherein the computing system is configured to identify the I/O operation for the second entity of the plurality of entities to dispatch to the hardware storage device by identifying the second entity based on an amount of budget credit in the second entity'"'"'s I/O budget as compared to amounts of budget credit in one or more other entities of the plurality of entities I/O budgets.

3. The computing system of claim 2, wherein the computing system is configured to identify the I/O operation for the second entity to dispatch to the hardware storage device by identifying that the second entity has a budget credit amount in its I/O budget that exceeds a threshold.

4. The computing system of claim 1, wherein the budget data structure comprises:

a throttle data structure that includes entities of the plurality of entities having no I/O operations, one or more pending I/O operations, and a threshold amount of I/O budget credit;

an empty data structure that includes entities of the plurality of entities having no I/O operations and a threshold amount of I/O budget credit;

the ready data structure that includes entities of the plurality of entities having I/O operations and a threshold amount of I/O budget credit; and

a jail data structure that includes entities of the plurality of entities not having a threshold amount of I/O budget credit; and

wherein identifying the I/O operation for a second entity of the plurality of entities to dispatch to the hardware storage device comprises identifying the particular entity from the ready data structure.

5. The computing system of claim 1, wherein identifying the I/O operation for the second entity of the plurality of entities to dispatch to the hardware storage device comprises identifying an I/O operation by age to identify an I/O operation that is comparatively older than other I/O operations.

6. The computing system of claim 1, wherein the plurality of entities are defined by priority, category, and node.

7. In a computing system comprising one or more processors and a plurality of entities, a method of managing outstanding I/O operations to a hardware storage device, the method comprising:

operating a de-randomizer that comprises a plurality of slots for a hardware storage device, each slot comprising a queued list for listing I/O operations to be dispatched to the hardware storage device, wherein the slots are organized based on the hardware storage device size and offsets into the hardware storage device such that operations adjacent to each other in a queued list in the same slot are treated as sequential I/O operations to the hardware storage device to determine I/O cost, and non-adjacent operations within the same slot are treated as sparse I/O operations to the hardware storage device to determine I/O cost, and I/O operations from different queued lists in different slots are treated as random I/O operations to the hardware storage device to determine operation cost;

queueing, at a plurality of entity queues coupled to the de-randomizer, I/O operations for the plurality of entities to the hardware storage device;

tracking, at a budget data structure coupled to the de-randomizer, budgets credits for the plurality of entities to determine which of the plurality of entities have sufficient budget to be allowed to have I/O operations dispatched to the hardware storage device;

wherein, based on either a most recent or current I/O operation dispatched to a hardware storage device, using the de-randomizer and budget data structure to identify sequential and sparse operations for a first entity of the plurality of entities to dispatch to the hardware storage device when the first entity has sufficient budget to have the I/O operation performed on its behalf, wherein when selecting the next operation for a first entity, the relative cost of the next operation is determined, including a comparison to other I/O operations and a cost for seek time, and the de-randomizer prioritizes selecting a sequential I/O operation in a given slot over a sparse I/O operation in the given slot;

wherein, based on determining that (i) the first entity has sufficient budget to have an I/O operation performed on its behalf, and that (ii) there are no remaining queued sequential operations in the given slot, using the de-randomizer to select a next sparse operation and to dispatch the next sparse operation to the hardware storage device; and

wherein, based on determining that the first entity lacks sufficient budget to have an additional I/O operation performed on its behalf, using the de-randomizer to identify an I/O operation for a second entity of the plurality of entities to dispatch to the hardware storage device.

8. The method of claim 7, wherein identifying the I/O operation for the second entity of the plurality of entities to dispatch to the hardware storage device comprises identifying the second entity based on an amount of budget credit in the second entity'"'"'s I/O budget as compared to amounts of budget credit in one or more other entities of the plurality of entities I/O budgets.

9. The method of claim 8, wherein the second entity has a budget credit amount in its I/O budget that exceeds a threshold.

10. The method of claim 7, wherein identifying at the one or more processors the I/O operation for the second entity to dispatch to the hardware storage device comprises identifying the second entity from a ready data structure that is included in a set of data structures including:

a throttle data structure operating at the one or more processors that includes entities of the plurality of entities having no I/O operations, one or more pending I/O operations, and a threshold amount of I/O budget credit;

an empty data structure operating at the one or more processors that includes entities of the plurality of entities having no I/O operations and a threshold amount of I/O budget credit;

the ready data structure operating at the one or more processors that includes entities of the plurality of entities having I/O operations and a threshold amount of I/O budget credit; and

a jail data structure operating at the one or more processors that includes entities of the plurality of entities not having a threshold amount of I/O budget credit.

11. The method of claim 10, further comprising replenishing budget credit to one or more entities of the plurality of entities based on a determination that all entities of the plurality of entities have been fairly granted an opportunity to access the hardware storage device by determining that the one or more entities are present in the jail data structure, that no entities are present in the ready data structure and that no entities are present in the throttle data structure.

12. The method of claim 10, further comprising replenishing budget credit to the one or more entities, but limiting the amount of credit refilled to entities based on a predetermined maximum budget credit threshold for entities.

13. The method of claim 7, further comprising replenishing budget credit to one or more entities of the plurality of entities based on a determination that all entities have been fairly granted an opportunity to access the hardware storage device.

14. The method of claim 7, wherein identifying at the one or more processors the I/O operation for the second entity to dispatch to the hardware storage device comprises identifying an I/O operation by age.

15. The method of claim 7, further comprising at a later time performing the next I/O operation as a result of determining that there was not sufficient I/O budget credit, and wherein the next I/O has a different cost value when performed at the later time due to intervening I/O operations increasing the seek time cost for the next I/O.

16. The method of claim 7, wherein the plurality of entities are defined by priority, category, and node.

17. The method of claim 7, wherein the seek time factor includes a gap cost.

18. A hardware storage device comprising computer executable instructions that when executed by one or more processors cause the following method to be performed:

operating a de-randomizer that comprises a plurality of slots for a hardware storage device, each slot comprising a queued list for listing I/O operations to be dispatched to the hardware storage device, wherein the slots are organized based on the hardware storage device size and offsets into the hardware storage device such that operations adjacent to each other in a queued list in the same slot are treated as sequential I/O operations to the hardware storage device to determine I/O cost, and non-adjacent operations within the same slot are treated as sparse I/O operations to the hardware storage device to determine I/O cost, and I/O operations from different queued lists in different slots are treated as random I/O operations to the hardware storage device to determine operation cost;

queueing, at a plurality of entity queues coupled to the de-randomizer, I/O operations for the plurality of entities to the hardware storage device;

tracking, at a budget data structure coupled to the de-randomizer, budgets credits for the plurality of entities to determine which of the plurality of entities have sufficient budget to be allowed to have I/O operations dispatched to the hardware storage device;

wherein, based on either a most recent or current I/O operation dispatched to a hardware storage device, using the de-randomizer and budget data structure to identify sequential and sparse operations for a first entity of the plurality of entities to dispatch to the hardware storage device when the first entity has sufficient budget to have the I/O operation performed on its behalf, wherein when selecting the next operation for a first entity, the relative cost of the next operation is determined, including a comparison to other I/O operations and a cost for seek time, and the de-randomizer prioritizes selecting a sequential I/O operation in a given slot over a sparse I/O operation in the given slot;

wherein, based on determining that (i) the first entity has sufficient budget to have an I/O operation performed on its behalf, and that (ii) there are no remaining queued sequential operations in the given slot, using the de-randomizer to select a next sparse operation and to dispatch the next sparse operation to the hardware storage device; and

wherein, based on determining that the first entity lacks sufficient budget to have an additional I/O operation performed on its behalf, using the de-randomizer to identify an I/O operation for a second entity of the plurality of entities to dispatch to the hardware storage device.

19. The hardware storage device of claim 18, wherein identifying the I/O operation for the second entity to dispatch to the hardware storage device comprises identifying the second entity based on an amount of budget credit in the second entity'"'"'s I/O budget as compared to amounts of budget credit in one or more other entities I/O budgets.

20. The hardware storage device of claim 18, the method further comprising at a later time performing the next I/O operation as a result of determining that there was not sufficient I/O budget credit, and wherein the next I/O has a different cost value when performed at the later time due to intervening I/O operations increasing the seek time cost for the next I/O.