Method and system for implementing cache size estimations

• US 10,114,751 B1
• Filed: 05/31/2016
• Issued: 10/30/2018
• Est. Priority Date: 06/05/2015
• Status: Active Grant

• Current Assignee: Nutanix Incorporated
• Original Assignee: Nutanix Incorporated
• Inventors: Faith, Rickard Edward, Wyckoff, Peter Scott
• Primary Examiner(s): Li, Zhuo
• Application Number:
  US15/169,381
• Time in Patent Office: 882 Days
• CPC Class Codes: G06F 11/34 Recording or statistical evaluation of computer activity, e.g. of down time, of input/output operation ; Recording or statistical evaluation of user activity, e.g. usability assessment
• CPC Class Codes: G06F 11/3457 Performance evaluation by simulation
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 2201/885 Monitoring specific for caches
• CPC Class Codes: G06F 2212/1021 Hit rate improvement
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/1048 Scalability
• CPC Class Codes: G06F 2212/601 Reconfiguration of cache memory
• CPC Class Codes: G06F 2212/604 Details relating to cache allocation
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking

Abstract

Disclosed is an improved approach to implement memory-efficient cache size estimations. A HyperLogLog is used to efficiently approximate an MRC with sufficient granularity to size caches.

Claims

1. A method implemented with a processor for performing cache estimation, comprising:

generating a list of cache sizes, the list of cache sizes corresponding to different sizes of caches, the caches comprising one or more storage components;

initializing a hyperloglog (HLL) for each cache size on the list of cache sizes, wherein a first HLL is initialized for a first cache having a first cache size and a second HLL is initialized for a second cache having a second cache size, wherein the first cache size is different than the second cache size;

performing cache estimation using the HLL by representing a change of state of the HLL as a cache miss and a non-change of state of the HLL as a cache hit;

computing, using the HLL, a miss rate curve (MRC) from a count of the cache miss and the cache hit; and

changing a size of a cache based at least in part on a MRC value determined from the MRC computed by the HLL.

2. The method of claim 1, wherein the HLL comprises a fixed amount of memory regardless of a cache size being simulated.

3. The method of claim 1, wherein a miss counter tracks the count of the cache miss and a hit counter tracks the count of the cache hit.

4. The method of claim 1, wherein a reset of the HLL occurs when the HLL is full.

5. The method of claim 4, wherein tracking of the count of the cache miss or cache hit does not occur immediately after the reset.

6. The method of claim 5, wherein tracking of the count of the cache miss or cache hit occurs after the reset when the HLL becomes more than half full.

7. The method of claim 1, wherein the MRC is determined by calculating a miss counter value divided by a sum of the miss counter value and a hit counter value.

8. The method of claim 1, further comprising selection of a cache size from the MRC.

9. The method of claim 1, wherein the cache estimation is for a cache in a virtualization system.

10. The method of claim 9, wherein the cache is within a computing node operating a hypervisor and one or more virtual machines.

11. A computer program product embodied on a computer readable medium, the computer readable medium having stored thereon a sequence of instructions which, when executed by a processor causes the processor to execute a method for implementing cache estimation, the method comprising:

generating a list of cache sizes, the list of cache sizes corresponding to different sizes of caches, the caches comprising one or more storage components;

initializing a hyperloglog (HLL) for each cache size on the list of cache sizes, wherein a first HLL is initialized for a first cache having a first cache size and a second HLL is initialized for a second cache having a second cache size, wherein the first cache size is different than the second cache size;

performing cache estimation using the HLL by representing a change of state of the HLL as a cache miss and a non-change of state of the HLL as a cache;

computing, using the HLL, a miss rate curve (MRC) from a count of the cache miss and the cache hit; and

changing a size of a cache based at least in part on a MRC value determined from the MRC computed by the HLL.

12. The computer program product of claim 11, wherein the HLL comprises a fixed amount of memory regardless of a cache size being simulated.

13. The computer program product of claim 11, wherein a miss counter tracks the count of the cache miss and a hit counter tracks the count of the cache hit.

14. The computer program product of claim 11, wherein a reset of the HLL occurs when the HLL is full.

15. The computer program product of claim 14, wherein tracking of the count of the cache miss or cache hit does not occur immediately after the reset.

16. The computer program product of claim 15, wherein tracking of the count of the cache miss or cache hit occurs after the reset when the HLL becomes more than half full.

17. The computer program product of claim 11, wherein the MRC is determined by calculating a miss counter value divided by a sum of the miss counter value and a hit counter value.

18. The computer program product of claim 11, wherein the computer readable medium further comprises instructions which, when executed by the processor causes the processor to execute selection of a cache size from the MRC.

19. The computer program product of claim 11, wherein the cache estimation is for a cache in a virtualization system.

20. The computer program product of claim 19, wherein the cache is within a computing node operating a hypervisor and one or more virtual machines.

21. A system for performing cache estimation, comprising:

a computer processor to execute a set of program code instructions; and

a memory to hold the program code instructions, in which the program code instructions comprises program code to perform;

generating a list of cache sizes, the list of cache sizes corresponding to different sizes of caches, the caches comprising one or more storage components;

initializing a hyperloglog (HLL) for each cache size on the list of cache sizes, wherein a first HLL is initialized for a first cache having a first cache size and a second HLL is initialized for a second cache having a second cache size, wherein the first cache size is different than the second cache size;

performing cache estimation using the HLL by representing a change of state of the HLL as a cache miss and a non-change of state of the HLL as a cache hit;

computing, using the HLL, a miss rate curve (MRC) from a count of the cache miss and the cache hit; and

changing a size of a cache based at least in part on a MRC value determined from the MRC computed by the HLL.

22. The system of claim 21, wherein the HLL comprises a fixed amount of memory regardless of a cache size being simulated.

23. The system of claim 21, wherein a miss counter tracks the count of the cache miss and a hit counter tracks the count of the cache hit.

24. The system of claim 21, wherein a reset of the HLL occurs when the HLL is full.

25. The system of claim 24, wherein tracking of the count of the cache miss or cache hit does not occur immediately after the reset.

26. The system of claim 25, wherein tracking of the count of the cache miss or cache hit occurs after the reset when the HLL becomes more than half full.

27. The system of claim 21, wherein the MRC is determined by calculating a miss counter value divided by a sum of the miss counter value and a hit counter value.

28. The system of claim 21, wherein the program code instructions further comprise program code to perform selection of a cache size from the MRC.

29. The system of claim 21, wherein the cache estimation is for a cache in a virtualization system.

30. The system of claim 29, wherein the cache is within a computing node operating a hypervisor and one or more virtual machines.