Optimizing cache performance with probabilistic model
Determining storage of particular data in cache memory of a storage device includes using a first mechanism to determine when to remove the particular data from the cache memory and using a second mechanism, independent from the first mechanism, to inhibit the particular data from being stored in the cache memory independent of whether the first mechanism otherwise causes the particular data to be stored in the cache memory. The first mechanism may remove data from the cache memory that was least recently accessed. The second mechanism may be based, at least in part, on a prediction value of an expected benefit of storing the particular data in the cache memory. The prediction value may be determined based on input data corresponding to measured cache read hits (RH), cache write hits (WH), cache read misses (RM), cache write destage operations (WD), and prefetch reads (PR) for the particular data.
1. A method of determining storage of particular data in cache memory of a storage device, comprising:
using a first mechanism to determine when to remove the particular data from the cache memory; and
using a second mechanism, independent from the first mechanism, to inhibit the particular data from being stored in the cache memory independent of whether the first mechanism otherwise causes the particular data to be stored in the cache memory, wherein the second mechanism is based, at least in part, on a prediction value of an expected benefit of storing the particular data in the cache memory and wherein the prediction value is determined based on input data corresponding to measured cache read hits (RH), cache write hits (WH), cache read misses (RM), cache write destage operations (WD), and prefetch reads (PR) for the particular data.
2. A method, according to claim 1 , wherein the prediction value is determined based on a formula:
prediction value=( RH+WH )/( RM+WD+PR )+RandomValue
wherein the RandomValue is a value between zero and one.
3. A method, according to claim 2 , wherein the input data for RH, WH, RM, WD, and PR is aged to cause more recent data to have a greater influence on the prediction value than less recent data.
4. A method, according to claim 3 , wherein aging the input data includes using a short term average that halves values of the input data once every twenty-hours and a long term average that halves values of the input data once every five days.
5. A method, according to claim 2 , wherein a prediction value of greater than one causes the second mechanism to always allow the particular data to be stored in the cache memory.
6. A method, according to claim 2 , further comprising:
generating a random number between zero and one; and
allowing the particular data to be stored in the cache memory in response to the random number being less than the prediction value.
7. A method, according to claim 2 , wherein the prediction value is stored in a hash table that is accessed where data is being stored in the cache memory.
8. A method, according to claim 1 , wherein the first mechanism removes data from the cache memory that was least recently accessed.
9. A non-transitory computer-readable medium containing software that determines storage of particular data in cache memory of a storage device, the software comprising:
executable code that uses a first mechanism to determine when to remove the particular data from the cache memory; and
executable code that uses a second mechanism, independent from the first mechanism, to inhibit the particular data from being stored in the cache memory independent of whether the first mechanism otherwise causes the particular data to be stored in the cache memory, wherein the second mechanism is based, at least in part, on a prediction value of an expected benefit of storing the particular data in the cache memory and wherein the prediction value is determined based on input data corresponding to measured cache read hits (RH), cache write hits (WH), cache read misses (RM), cache write destage operations (WD), and prefetch reads (PR) for the particular data.
10. A non-transitory computer-readable medium, according to claim 9 , wherein the prediction value is determined based on a formula:
prediction value=( RH+WH )/( RM+WD+PR )+RandomValue
wherein the RandomValue is a value between zero and one.
11. A non-transitory computer-readable medium, according to claim 10 , wherein the input data for RH, WH, RM, WD, and PR is aged to cause more recent data to have a greater influence on the prediction value than less recent data.
12. A non-transitory computer-readable medium, according to claim 11 , wherein aging the input data includes using a short term average that halves values of the input data once every twenty-hours and a long term average that halves values of the input data once every five days.
13. A non-transitory computer-readable medium, according to claim 10 , wherein a prediction value of greater than one causes the second mechanism to always allow the particular data to be stored in the cache memory.
14. A non-transitory computer-readable medium, according to claim 10 , further comprising:
executable code that generates a random number between zero and one; and
executable code that allows the particular data to be stored in the cache memory in response to the random number being less than the prediction value.
15. A non-transitory computer-readable medium, according to claim 10 , wherein the prediction value is stored in a hash table that is accessed where data is being stored in the cache memory.
16. A non-transitory computer-readable medium, according to claim 9 , wherein the first mechanism removes data from the cache memory that was least recently accessed.