ASSIGNING READ REQUESTS BASED ON BUSYNESS OF DEVICES
First Claim
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 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;
wherein the method is performed by one or more computing devices.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
20 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 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; wherein the method is performed by one or more computing devices. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. 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 read requests to the devices that store copies of the item based on the fractions that were determined for the devices for that item. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
Specification