Solid-State Disk Caching the Top-K Hard-Disk Blocks Selected as a Function of Access Frequency and a Logarithmic System Time

Abstract

A solid state disk (SSD) caches disk-based volumes in a heterogeneous storage system, improving the overall storage-system performance. The hottest data blocks are identified based on two factors: the frequency of access, and temporal locality. Temporal locality is computed using a logarithmic system time. IO latency is reduced by migrating these hottest data blocks from hard-disk-based volumes to the solid-state flash-memory disks. Some dedicated mapping metadata and a novel top-K B-tree structure are used to index the blocks. Data blocks are ranked by awarding a higher current value for recent accesses, but also by the frequency of accesses. A non-trivial value for accesses in the past is retained by accumulating the two factors over many time spans expressed as a logarithmic system time. Having two factors, access frequency and the logarithmic system time, provides for a more balanced caching system.

We claim: 
     
         1 . A heterogeneous storage system comprising:
 primary storage means for storing blocks of data, the primary storage means having a primary access time;   secondary storage means for caching blocks of data stored in the primary storage, the secondary storage means having a secondary access time that is faster than the primary access time;   storage module means for managing blocks of data stored in the primary storage means and cached in the secondary storage means;   identifier means, in the storage module means, for tracking blocks of data stored in the primary storage means and cached in the secondary storage means;   migrator means for moving blocks of data between the primary storage means and the secondary storage means;   miss counter means for counting accesses from a host for data that is not found in the secondary storage means;   miss timer means for counting time since the migrator means was last activated to move blocks of data between the primary storage means and the secondary storage means;   miss trigger means, coupled to the miss counter means and to the miss timer means, triggered when both the miss counter means exceeds a miss threshold and the miss timer means exceeds a miss time threshold, for activating the migrator means to move blocks of data between the primary storage means and the secondary storage means;   dispenser means for handling requests from the migrator means to access blocks of data in the primary storage means and in the secondary storage means;   mapping table means for storing physical block numbers of blocks of data stored in the secondary storage means and logic block numbers corresponding to the physical block numbers; and   top-K tracking table means for storing a plurality of K elements, wherein K is a whole number of blocks of data currently able to be stored in the secondary storage means;   wherein the migrator means accesses the top-K tracking table means to locate blocks of data to remove from the secondary storage means having a low current level;   wherein each element in the plurality of K elements stores a current level, the current level indicating a hotness of data stored in the block of data corresponding to the element;   wherein the current level is a function of an access frequency and a logarithmic system time,   whereby blocks of data are chosen for migration out of the secondary storage means based on access frequency and the logarithmic system time.   
     
     
         2 . The heterogeneous storage system of  claim 1  wherein each element in the plurality of elements stored in the top-K tracking table means comprise:
 a logic block number indicating a portion of a logical address of a block of data; 
 a current level; 
 a temporary level; and 
 a time array for storing a plurality of time stamps of recent accesses of the block of data identified by the logic block number. 
 
     
     
         3 . The heterogeneous storage system of  claim 2  wherein the plurality of K elements in the top-K tracking table means are stored in a sorted order. 
     
     
         4 . The heterogeneous storage system of  claim 3  wherein the plurality of K elements in the top-K tracking table means are stored in a sorted order based on the current level of each element. 
     
     
         5 . The heterogeneous storage system of  claim 4  wherein the top-K tracking table means further comprises a row of top pointers, each top pointer pointing to a location of a top element having a highest current level in a column of elements in the top-K tracking table means, the top element being in the plurality of elements. 
     
     
         6 . The heterogeneous storage system of  claim 2  further comprising:
 primary device driver means for accessing blocks of data in the primary storage means; 
 secondary device driver means for accessing blocks of data in the secondary storage means; 
 wherein the dispenser means submits requests to the primary device driver means to access the primary storage means, and to the secondary device driver means to access the secondary storage means. 
 
     
     
         7 . The heterogeneous storage system of  claim 2  wherein the primary storage means is a Hard Disk Driver (HDD) with spinning platters of magnetic disks;
 wherein the secondary storage means is a Solid-State-Drive (SSD) storing data in non-volatile memory. 
 
     
     
         8 . The heterogeneous storage system of  claim 7  wherein the secondary storage means is a flash memory storing data in electrically-erasable programmable read-only memory (EEPROM). 
     
     
         9 . A caching hybrid storage subsystem comprising:
 a hard-disk-drive (HDD) storage that stores blocks of data on rotating magnetic media;   a solid-state-drive (SSD) storage that stores blocks of data in non-volatile solid-stage memory;   top-K B-tree means for storing current levels for K blocks of data stored on the SSD storage, wherein K is a whole number of blocks of data stored on the SSD storage;   wherein each element in the top-K B-tree means stores a current level;   temporary level generator means for generating a temporary level for a block by combining an access frequency of the block with a logarithmic system time;   current level generator means for accumulating the current level for the block by accumulating the temporary level with a prior current level for the block;   a migrator that moves stale blocks of data from the SSD storage to the HDD storage, wherein the stale blocks have lower values of the current level than other blocks of data that remain in the SSD storage; and   an identifier for tracking accesses of blocks of data in the SSD by a host, the identifier storing access information for use by the temporary level generator as the access frequency.   
     
     
         10 . The caching hybrid storage subsystem of  claim 9  wherein the logarithmic system time is a logarithm of a linear system time that is reset at system initialization. 
     
     
         11 . The caching hybrid storage subsystem of  claim 9  further comprising:
 a time array, stored in each element of the top-K B-tree means, the time array storing recent time values when the block of data was accessed by the host, wherein the time array stores R recent time values, wherein R is a whole number, wherein the access frequency is generated from R divided by a time period that includes all R accesses. 
 
     
     
         12 . The caching hybrid storage subsystem of  claim 11  wherein the temporary level generator is activated for an element when R recent values have been stored in the time array for the element;
 wherein temporary levels are generated after every R accesses of the block of data. 
 
     
     
         13 . The caching hybrid storage subsystem of  claim 12  wherein R is a programmable value that is adjusted by programming to alter caching properties. 
     
     
         14 . The caching hybrid storage subsystem of  claim 9  further comprising:
 a sorter for sorting elements in the top-K B-tree means according to current levels, wherein the top-K B-tree means is sorted. 
 
     
     
         15 . The caching hybrid storage subsystem of  claim 9  further comprising:
 a miss counter for counting accesses from a host for data that is not found in the SSD storage; 
 a miss timer for counting time since the migrator was last activated to move blocks of data between the HDD storage and the SSD storage; 
 a miss trigger, coupled to the miss counter and to the miss timer, triggered when both the miss counter exceeds a miss threshold and the miss timer exceeds a miss time threshold, for activating the migrator to move blocks of data between the HDD storage and the SSD storage. 
 
     
     
         16 . A heterogeneous storage device comprising:
 a primary storage for storing blocks of data, the primary storage having a primary access time;   a secondary storage for caching blocks of data stored in the primary storage a, the secondary storage having a secondary access time that is faster than the primary access time;   a storage module for managing blocks of data stored in the primary storage and cached in the secondary storage;   an identifier, in the storage module, for tracking blocks of data stored in the primary storage and cached in the secondary storage;   a temporary level generator for generating a temporary level for a block by combining an access frequency of the block with a logarithmic system time;   a current level generator that accumulates a current level for the block by accumulating the temporary level with a prior current level for the block;   a migrator for moving blocks of data between the primary storage and the secondary storage; and   a top-K B-tree for storing a plurality of K elements, wherein K is a whole number of blocks of data currently able to be stored in the secondary storage;   wherein the migrator accesses the top-K B-tree to locate blocks of data to remove from the secondary storage having a low value of the current level;   wherein each element in the plurality of K elements stores a current level, the current level indicating a hotness of data stored in the block of data corresponding to the element;   whereby blocks of data are chosen for migration out of the secondary storage based on access frequency and the logarithmic system time.   
     
     
         17 . The heterogeneous storage device of  claim 16  wherein each element in the plurality of elements stored in the top-K B-tree comprise:
 a logic block number indicating a portion of a logical address of a block of data; 
 a current level; 
 a temporary level; and 
 a time array for storing a plurality of times of recent accesses of the block of data identified by the logic block number. 
 
     
     
         18 . The heterogeneous storage device of  claim 17  further comprising:
 a miss counter for counting accesses from a host for data that is not found in the secondary storage; 
 a miss timer for counting time since the migrator was last activated to move blocks of data between the primary storage and the secondary storage; 
 a miss trigger, coupled to the miss counter and to the miss timer, triggered when both the miss counter exceeds a miss threshold and the miss timer exceeds a miss time threshold, for activating the migrator to move blocks of data between the primary storage and the secondary storage. 
 
     
     
         19 . The heterogeneous storage device of  claim 17  further comprising:
 a dispenser for handling requests from the migrator to access blocks of data in the primary storage and in the secondary storage; 
 a mapping table for storing physical block numbers of blocks of data stored in the secondary storage and logic block numbers corresponding to the physical block numbers. 
 
     
     
         20 . The heterogeneous storage device of  claim 17  wherein the primary storage is a Hard Disk Driver (HDD) with spinning platters of magnetic disks;
 wherein the secondary storage is a Solid-State-Drive (SSD) storing data in non-volatile semiconductor memory.