A system, method, and computer program product are provided for allocating blocks of memory in a virtual storage device based on access frequency. The method includes the steps of tracking access frequency for a plurality of blocks of memory in a virtual storage device utilizing a heat map and reallocating the plurality of blocks of memory in the virtual storage device among a plurality of blocks of memory in two or more real storage devices based on the heat map. The heat map includes at least one data structure that maps block identifiers corresponding to the plurality of blocks of memory in the virtual storage device to heat values that represent the access frequency of a corresponding block of memory.