Solid-state disk caching the top-K hard-disk blocks selected as a function of access frequency and a logarithmic system time

摘要

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.

主权项

1. A heterogeneous storage system 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, 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 migrator for moving blocks of data between the primary storage and the secondary storage; 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; 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 storing physical block numbers of blocks of data stored in the secondary storage and logic block numbers corresponding to the physical block numbers; and a top-K tracking table 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 tracking table to locate blocks of data to remove from the secondary storage 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 based on access frequency and the logarithmic system time.