Assigning read requests based on busyness of devices

• US 9,875,040 B2
• Filed: 08/24/2015
• Issued: 01/23/2018
• Est. Priority Date: 12/21/2010
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Bridge, Jr., William H., Bagal, Prasad, Jain, Lavina, Wickremesinghe, Rajiv, Nagarajappa, Darshan, Long, Richard L.
• Primary Examiner(s): KROFCHECK, MICHAEL C
• Application Number:
  US14/833,432
• Publication Number:
  US 20150363123A1
• Time in Patent Office: 883 Days
• CPC Class Codes: G06F 11/2053 where persistent mass storage functionality or persistent mass storage control functionality is redundant error detection or correction in information storage based on relative movement between record carrier and transducer G11B20/18
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0683 Plurality of storage devices

Abstract

Techniques are provided for assigning read requests to storage devices in a manner that reduces the likelihood that any storage device will become overloaded or underutilized. Specifically, a read-request handler assigns read requests that are directed to each particular item among the storage devices that have copies of the item based on how busy each of those storage devices is. Consequently, even though certain storage devices may have copies of the same item, there may be times during which one storage device is assigned a disproportionate number of the reads of the item because the other storage device is busy with read requests for other items, and there may be other times during which other storage device is assigned a disproportionate number of the reads of the item because the one storage device is busy with read request for other items. Various techniques for estimating the busyness of storage devices are provided, including fraction-based estimates, interval-based estimates, and the response-time-based estimates. Techniques for smoothing those estimates, and for handicapping devices, are also provided.

Claims

1. A method comprising:

for each device of a plurality of devices that belong to a system, determining a respective first system-wide fraction;

wherein the respective first system-wide fraction determined for each device is a fraction, of all read requests handled by the system, to be sent to the device;

wherein the plurality of devices store a plurality of items;

wherein each device of the plurality of devices stores at least one copy of at least one item of the plurality of items;

for each item of the plurality of items, determining, for each device that has a copy of the item, a respective item-specific fraction;

wherein the respective item-specific fraction determined for a device is a fraction, of the read requests that are directed to the item, to be sent to the device in order for each device to receive the device'"'"'s respective first system-wide fraction of all read requests handled by the system; and

for each item of the plurality of items, sending amounts of read requests to the devices that store copies of the item wherein;

the amounts of read requests are proportional to the respective item-specific fractions that were determined for the devices for that item, and

each read request of the amounts of read requests is sent to a single device of the devices that store copies of the item;

wherein the method is performed by one or more computing devices.

2. The method of claim 1 further comprising, after failure of one or more of the plurality of devices, performing:

generating respective second system-wide fractions by adjusting the respective first system-wide fractions assigned to devices, of the plurality of devices, that did not fail; and

for each item of the plurality of items, determining what new respective item-specific fraction of the read requests that are directed to the item to send to each of the devices that has a copy of the item in order for each device to receive the device'"'"'s respective second system-wide fraction of all read requests handled by the system; and

for each item of the plurality of items, sending read requests to the devices that store copies of the item based on the new respective item-specific fractions that were determined for the devices for that item.

3. The method of claim 1 wherein:

the method includes calculating a smoothed busyness value for each device based on a current busyness value for the device and one or more past busyness values for the device; and

the respective first system-wide fraction determined for each device is based on the smoothed busyness value that is calculated for the device.

4. The method of claim 3 wherein calculating the smoothed busyness value includes giving a first weight to the one or more past busyness values when a system that includes the plurality of devices is in a steady state, and giving a second weight to the one or more past busyness values in response to a significant change in the system, wherein the first weight is greater than the second weight.

5. The method of claim 1 wherein the respective first system-wide fraction determined for each device is based on a response time of the device.

6. The method of claim 5 further comprising periodically decrementing the response time associated with each device.

7. The method of claim 1 independently performed by each of multiple client computers, wherein each client computer independently determines the respective first system-wide fraction of each device based on read requests originating from the client computer.

8. The method of claim 1 wherein at least three devices of the plurality of devices stores a copy of a same item of the plurality of items.

9. A method comprising:

for each device of a plurality of devices that belong to a system, determining a respective first system-wide fraction;

wherein the respective first system-wide fraction determined for each device is a fraction, of all read requests handled by the system, to be sent to the device;

wherein the plurality of devices store a plurality of items;

wherein each device of the plurality of devices stores at least one copy of at least one item of the plurality of items;

for each item of the plurality of items, determining, for each device that has a copy of the item, a respective item-specific fraction;

wherein the respective item-specific fraction determined for a device is a fraction, of the read requests that are directed to the item, to be sent to the device in order for each device to receive the device'"'"'s respective first system-wide fraction of all read requests handled by the system; and

for each item of the plurality of items, sending read requests to the devices that store copies of the item based on the respective item-specific fractions that were determined for the devices for that item;

calculating a smoothed busyness value for each device based on a current busyness value for the device and one or more past busyness values for the device;

wherein;

the respective first system-wide fraction determined for each device is based on the smoothed busyness value that is calculated for the device;

calculating the smoothed busyness value for each device includes calculating a busyness value based, at least in part, on an interval associated with the device;

the interval associated with a device is based on how many read requests are sent to other devices between two consecutive read requests that are sent to the device; and

the method is performed by one or more computing devices.

10. The method of claim 9 wherein the interval associated with a device is based, at least in part, on at least one of:

size of read requests sent to other devices, or size of read requests sent to the device.

11. The method of claim 9 further comprising periodically incrementing the interval associated with each device.

12. One or more non-transitory computer-readable media storing instructions, wherein the instructions include:

instructions which, when executed by one or more processors, cause, for each device of a plurality of devices that belong to a system, determining a respective first system-wide fraction;

wherein the respective first system-wide fraction determined for each device is a fraction, of all read requests handled by the system, to be sent to the device;

wherein the plurality of devices store a plurality of items;

wherein each device of the plurality of devices stores at least one copy of at least one item of the plurality of items;

instructions which, when executed by one or more processors, cause, for each item of the plurality of items, determining, for each device that has a copy of the item, a respective item-specific fraction;

wherein the respective item-specific fraction determined for a device is a fraction, of the read requests that are directed to the item, to be sent to the device in order for each device to receive the device'"'"'s respective first system-wide fraction of all read requests handled by the system; and

instructions which, when executed by one or more processors, cause, for each item of the plurality of items, sending amounts of read requests to the devices that store copies of the item wherein;

the amounts of read requests are proportional to the respective item-specific fractions that were determined for the devices for that item, and

each read request of the amounts of read requests is sent to a single device of the devices that store copies of the item.

13. The one or more non-transitory computer-readable media of claim 12 storing instructions which, when executed by one or more processors, cause:

after failure of one or more of the plurality of devices;

generating respective second system-wide fractions by adjusting the respective first system-wide fractions assigned to devices, of the plurality of devices, that did not fail; and

for each item of the plurality of items, determining what new fraction of the read requests that are directed to the item to send to each of the devices that has a copy of the item in order for each device to receive the respective second system-wide fraction of all read requests handled by the system; and

for each item of the plurality of items, sending read requests to the devices that store copies of the item based on the new fractions that were determined for the devices for that item.

14. The non-transitory computer-readable media of claim 12 wherein the respective first system-wide fraction determined for each device is based on a smoothed busyness value that is based on a current busyness value for the device and one or more past busyness values for the device.

15. The non-transitory computer-readable media of claim 14 wherein calculating smoothed busyness value for a device includes giving a first weight to the one or more past busyness values when a system that includes the plurality of devices is in a steady state, and giving a second weight to the one or more past busyness values in response to a significant change in the system, wherein the first weight is greater than the second weight.

16. The non-transitory computer-readable media of claim 12 wherein the respective first system-wide fraction determined for each device is based on a response time of the device.

17. The non-transitory computer-readable media of claim 16 wherein the instructions include instructions which, when executed by one or more processors, cause periodically decrementing the response time associated with each device.

18. The non-transitory computer-readable media of claim 12 wherein the instructions are independently executed by each of multiple client computers, wherein each client computer independently determines the respective first system-wide fraction of each device based on read requests originating from the client computer.

19. One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:

for each device of a plurality of devices that belong to a system, determining a respective first system-wide fraction;

wherein the respective first system-wide fraction determined for each device is a fraction, of all read requests handled by the system, to be sent to the device;

wherein the plurality of devices store a plurality of items;

wherein each device of the plurality of devices stores at least one copy of at least one item of the plurality of items;

for each item of the plurality of items, determining, for each device that has a copy of the item, a respective item-specific fraction;

wherein the respective item-specific fraction determined for a device is a fraction, of the read requests that are directed to the item, to be sent to the device in order for each device to receive the device'"'"'s respective first system-wide fraction of all read requests handled by the system; and

for each item of the plurality of items, sending read requests to the devices that store copies of the item based on the respective item-specific fractions that were determined for the devices for that item;

calculating a smoothed busyness value for each device based on a current busyness value for the device and one or more past busyness values for the device;

wherein;

the respective first system-wide fraction determined for each device is based on the smoothed busyness value that is calculated for the device;

calculating a smoothed busyness value for each device includes calculating a busyness value based, at least in part, on an interval associated with the device; and

the interval associated with a device is based on how many read requests are sent to other devices between two consecutive read requests that are sent to the device.

20. The non-transitory computer-readable media of claim 19 wherein the interval associated with a device is based, at least in part, on at least one of:

size of read requests sent to other devices, or size of read requests sent to the device.

21. The non-transitory computer-readable media of claim 19 wherein the instructions include instructions which, when executed by one or more processors, cause periodically incrementing the interval associated with each device.