Dynamically adapting the configuration of a multi-queue cache based on access patterns

1. A computer-implemented method for dynamically adjusting a configuration of a multi-queue cache comprising:

configuring the multi-queue cache with an initial configuration, wherein the initial configuration includes one or more queues for storing data items, each of the one or more queues having an initial size;

operating the multi-queue cache according to a multi-queue cache replacement algorithm;

analyzing access patterns for the multi-queue cache during operation of the multi-queue cache;

determining, based on the access patterns, that the size of a particular queue in the one or more queues is to be adjusted, wherein the size of the particular queue represents physical storage capacity of the particular queue and is independent from amount of data stored in the particular queue; and

in response to the determining:

generating, based on the access patterns, an updated configuration for the multi-queue cache including a new size for the particular queue, including

determining the new size for the particular queue in accordance with a cache hit ratio associated with the one or more queues; and

dynamically modifying the configuration of the multi-queue cache during operation of the multi-queue cache, wherein the modifying includes adjusting the size of the particular queue to the new size according to the updated configuration for the multi-queue cache.

2. The computer-implemented method of claim 1 , wherein determining the new size for the particular queue comprises: determining the new size for the particular queue in accordance with a cache hit ratio associated with a queue, in the one or more queue, that is different from the particular queue.

3. The computer-implemented method of claim 2 , wherein generating the updated configuration for the multi-queue cache includes computing updated sizes for each of the queues in the one or more queues based at least in part on the cache hit.

4. The computer-implemented method of claim 1 , wherein dynamically modifying the configuration of the multi-queue cache includes:

increasing the size of at least one queue;

decreasing the size of at least another queue based on the size increase for the at least one queue; and

removing one or more data items in the at least another queue according to a least recently used replacement algorithm.

5. The computer-implemented method of claim 1 , wherein the dynamically modifying the configuration of the multi-queue cache includes increasing a number of queues in the multi-queue cache.

6. The computer-implemented method of claim 1 wherein:

the initial configuration arranges the one or more queues in a hierarchy; and

generating the updated configuration includes:

determining that a queue arranged in a logically highest position of the hierarchy exceeds a threshold size; and

adding an additional queue to the multi-queue cache, wherein the additional queue is positioned, in the hierarchy, above the queue arranged in the logically highest position.

7. The computer-implemented method of claim 6 , wherein generating the updated configuration further includes updating the sizes of one or more queues based on a size for the at least one additional queue.

8. A non-transitory computer-readable medium storing executable computer instructions for dynamically adjusting a configuration of a multi-queue cache, the computer instructions comprising instructions for:

configuring the multi-queue cache with an initial configuration, wherein the initial configuration includes one or more queues for storing data items, each of the one or more queues having an initial size;

operating the multi-queue cache according to a multi-queue cache replacement algorithm;

analyzing access patterns for the multi-queue cache during operation of the multi-queue cache;

determining, based on the access patterns, that the size of a particular queue in the one or more queues is to be adjusted, wherein the size of the particular queue represents physical storage capacity of the particular queue and is independent from amount of data stored in the particular queue; and

in response to the determining:

generating, based on the access patterns, an updated configuration for the multi-queue cache including a new size for the particular queue, including

determining the new size for the particular queue in accordance with a cache hit ratio associated with the one or more queues; and

dynamically modifying the configuration of the multi-queue cache during operation of the multi-queue cache, wherein the modifying includes adjusting the size of the particular queue to the new size according to the updated configuration for the multi-queue cache.

9. The computer-readable medium of claim 8 , wherein determining the new size for the particular queue comprises: determining the new size for the particular queue in accordance with a cache hit ratio associated with a queue, in the one or more queue, that is different from the particular queue.

10. The computer-readable medium of claim 9 , wherein the instructions for generating the updated configuration for the multi-queue cache include instructions for computing updated sizes for each of the queues in the one or more queues based at least in part on the identified cache hit.

11. The computer-readable medium of claim 8 , wherein the instructions for dynamically modifying the configuration of the multi-queue cache include instructions for:

increasing the size of at least one queue;

decreasing the size of at least another queue based on the size increase for the at least one queue; and

removing one or more data items in the at least another queue according to a least recently used replacement algorithm.

12. The computer-readable medium of claim 8 , wherein the instructions for dynamically modifying the configuration of the multi-queue cache include instructions for increasing a number of queues in the multi-queue cache.

13. The computer-readable medium of claim 8 , wherein:

the initial configuration arranges the one or more queues in a hierarchy; and

the instructions for generating the updated configuration include instructions for:

determining that a queue arranged in a logically highest position of the hierarchy exceeds a threshold size; and

adding an additional queue to the multi-queue cache, wherein the additional queue is positioned, in the hierarchy, above the queue arranged in the logically highest position.

14. The computer-readable medium of claim 13 , wherein the instructions for generating the updated configuration include instructions for updating the sizes of one or more queues based on a size for the at least one additional queue.

15. A system for dynamically adjusting a configuration of a multi-queue cache, the system comprising:

a non-transitory computer-readable storage medium storing executable computer program instructions comprising instructions for:

configuring the multi-queue cache with an initial configuration, wherein the initial configuration includes one or more queues for storing data items, each of the one or more queues having an initial size;

operating the multi-queue cache according to a multi-queue cache replacement algorithm;

analyzing access patterns for the multi-queue cache during operation of the multi-queue cache;

determining, based on the access patterns, that the size of a particular queue in the one or more queues is to be adjusted, wherein the size of the particular queue represents physical storage capacity of the particular queue and is independent from amount of data stored in the particular queue; and

in response to the determining:

generating, based on the access patterns, an updated configuration for the multi-queue cache including a new size for the particular queue, including

determining the new size for the particular queue in accordance with a cache hit ratio associated with the one or more queues; and

dynamically modifying the configuration of the multi-queue cache during operation of the multi-queue cache, wherein the modifying includes adjusting the size of the particular queue to the new size according to the updated configuration for the multi-queue cache; and

a processor for executing the computer program instructions.

16. The system of claim 15 , wherein determining the new size for the particular queue comprises: determining the new size for the particular queue in accordance with a cache hit ratio associated with a queue, in the one or more queue, that is different from the particular queue.

17. The system of claim 16 , wherein the instructions for generating the updated configuration for the multi-queue cache include instructions for computing updated sizes for each of the queues in the one or more queues based at least in part on the identified cache hit.

18. The system of claim 15 , wherein the instructions for dynamically modifying the configuration of the multi-queue cache include instructions for:

increasing the size of at least one queue;

decreasing the size of at least another queue based on the size increase for the at least one queue; and

removing one or more data items in the at least another queue according to a least recently used replacement algorithm.

19. The system of claim 15 , wherein the instructions for dynamically modifying the configuration of the multi-queue cache include instructions for increasing a number of queues in the multi-queue cache.

20. The system of claim 15 , wherein:

the initial configuration arranges the one or more queues in a hierarchy; and

the instructions for generating the updated configuration include instructions for:

determining that a queue arranged in a logically highest position of the hierarchy exceeds a threshold size; and

adding an additional queue to the multi-queue cache, wherein the additional queue is positioned, in the hierarchy, above the queue arranged in the logically highest position.