Storage device access mediation

• US 10,686,721 B2
• Filed: 03/12/2018
• Issued: 06/16/2020
• 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:
  US15/918,525
• Publication Number:
  US 20180205665A1
• Time in Patent Office: 827 Days
• 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 comprising one or more processors for queueing outstanding I/O operations for a plurality of entities to a hardware storage device, the computing system comprising:

a de-randomizer comprising a plurality of de-randomizer slots, the plurality of de-randomizer slots being configured based on a size of the hardware storage device and on a quantity of offsets into the hardware storage device, wherein queued I/O operations for a plurality of entities are assigned by the de-randomizer into the plurality of de-randomizer slots for performance at the hardware storage device; and

a budget data structure configured to track budget credits for the plurality of entities and being usable to determine which of the plurality of entities have sufficient budget to be allowed to have queued I/O operations dispatched from the plurality of de-randomizer slots to the hardware storage device, wherein the computing system is configured to use the de-randomizer and budget data structure to identify queued operations to dispatch to the hardware storage device,

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

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

2. The computing system of claim 1, wherein adjacent operations in the same de-randomizer slot are treated as sequential I/O operations to the hardware storage device to determine an I/O cost, and non-adjacent operations within the same de-randomizer slot are treated as sparse I/O operations to the hardware storage device to determine I/O cost, and I/O operations from different de-randomizer slots are treated as random I/O operations to the hardware storage device to determine operation cost.

3. The computer system of claim 1, wherein prior to dispatching the queued I/O operation for the second entity, the second entity is identified based at least on comparing the cost of a next sparse I/O operation queued for the second entity relative to the cost of a next sparse I/O operation queued for a different entity, including comparing a cost for seek time.

4. The computer system of claim 1, wherein each de-randomizer slot comprises a queued list for listing I/O operations to be dispatched to the hardware storage device.

5. The computer system of claim 1, wherein the queued I/O operations for the plurality of entities are queued within a plurality of entity queues that are coupled to the de-randomizer.

6. The computer system of claim 1, wherein the budget data structure is configured to reduce remaining budget credits for a particular entity of the plurality of entities for a random operation more than for execution of a sparse operation, and to reduce budget credits for the particular entity for execution of a sparse operation more than for execution of a sequential operation.

7. 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 budget credit in IO budgets of one or more other entities of the plurality of entities.

8. The computing system of claim 7, wherein the computing system is configured to identify the queued 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.

9. The computing system of claim 1, wherein the budget data structure further 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 queued 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.

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

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

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

12. A method, operating at a computing system comprising one or more processors, for queueing I/O operations for a plurality of entities to a hardware storage device, the method comprising:

operating a de-randomizer comprising a plurality of de-randomizer slots, the plurality of de-randomizer slots being configured based on a size of the hardware storage device and on a quantity of offsets into the hardware storage device;

queuing, into the plurality of de-randomizer slots, a plurality of I/O operations for a plurality of entities for performance at the hardware storage device;

tracking, using a budget data structure, budgets credits for the plurality of entities, the budget data structure being usable for determining which of the plurality of entities have sufficient budget to be allowed to have queued I/O operations dispatched from the plurality of de-randomizer slots to the hardware storage device; and

using, at the computing system, the de-randomizer and budget data structure to identify queued operations to dispatch to the hardware storage device, wherein the computing system performs at least one of the following;

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

or

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 dispatch a queued I/O operation for a second entity of the plurality of entities to the hardware storage device.

13. The method of claim 12, wherein the plurality of de-randomizer slots are configured such that operations adjacent to each other in a queued list in the same de-randomizer slot are treated by the budget data structure as sequential I/O operations to determine I/O cost, and non-adjacent operations within the same slot are treated by the budget data structure 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 by the budget data structure as random I/O operations to the hardware storage device to determine operation cost.

14. The method of claim 13, wherein identifying the queued 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 budget credit in IO budgets of one or more other entities of the plurality of entities.

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

16. The method of claim 14, wherein identifying the queued 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.

17. The method of claim 16, 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.

18. The method of claim 16, 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.

20. A hardware storage device comprising computer executable instructions that when executed by one or more processors of a computing system cause the following to be performed:

operating a de-randomizer comprising a plurality of de-randomizer slots, the plurality of de-randomizer slots being configured based on a size of the hardware storage device and on a quantity of offsets into the hardware storage device;

queuing, into the plurality of de-randomizer slots, a plurality of I/O operations for a plurality of entities for performance at the hardware storage device;

tracking, using a budget data structure, budgets credits for the plurality of entities, the budget data structure being usable for determining which of the plurality of entities have sufficient budget to be allowed to have queued I/O operations dispatched from the plurality of de-randomizer slots to the hardware storage device; and

using, at the computer system, the de-randomizer and budget data structure to identify queued operations to dispatch to the hardware storage device,

wherein, based on determining that a first entity has sufficient budget to have a queued I/O operation performed on its behalf, and that there are no remaining queued sequential operations in a given de-randomizer slot, using the de-randomizer to dispatch a queued sparse operation for the first entity 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 dispatch a queued I/O operation for a second entity of the plurality of entities to the hardware storage device.