Solid state drive caching using memory structures to determine a storage space replacement candidate

A mechanism to identify data that can be removed from a solid state drive (SSD) cache by determining a least recently accessed memory region of the SSD is provided. This functionality is provided by using a tree data structure to store a table mapping storage volume data locations to SSD data locations and associating a time stamp with each entry. The time stamp is updated with each access to the associated SSD location. Advantages of the tree data structure are utilized to efficiently determine an SSD memory location associated with an oldest time stamp in order to make that SSD memory location available for storage of recently accessed data from the storage volume.

FIELD OF THE INVENTION

The present invention relates to the field of data storage, and particularly to freeing up cache memory space on a solid state drive associated with a hard disk drive.

BACKGROUND OF THE INVENTION

An ever-increasing reliance on information and computing systems that produce, process, distribute, and maintain such information in its various forms continues to put great demands on techniques for providing data storage and access to that data storage. Today's data centers and cloud computing environments require increased input/output (I/O) performance to support large-scale applications such as databases, web servers, e-commerce applications, file servers, and electronic mail. These applications typically accommodate a large number of end-users. To meet service requirements of these end-users, data center operators deploy servers with high I/O throughput. The larger the number of end-users on the servers translates to an increase in the number of I/O operations required from these servers. As a consequence, servers are often maintained at low storage capacity utilization in order to meet the required number of I/Os, which is an inefficient use of resources.

Solid state drives (SSD) are storage devices capable of high I/O performance. An SSD uses flash components to store data and, unlike a hard disk drive (HDD), has no moving parts and no rotating media. SSDs offer a higher read bandwidth, higher I/Os per second, better mechanical reliability than HDDs, and higher resistance to shock and vibrations. But SSDs have more limited capacity than do HDDs, and therefore generally cannot be used as a replacement for HDDs in a data center.

SSDs can, however, be used to improve I/O performance of data center servers by functioning as a caching layer between HDDs and server main memory. HDD data can be copied to an associated SSD upon access of that data in order to improve the speed of subsequent access to that data. But since the SSD cache will not have the same storage capacity as the associated HDD, the SSD will ultimately cease to have sufficient free space to copy newly accessed data from the HDD. A mechanism for efficiently identifying areas of memory in the SSD cache to make available is desirable.

SUMMARY OF THE INVENTION

Embodiments of the present invention identify data that can be removed from a solid state drive cache by determining a least recently accessed memory region of the SSD. Embodiments of the present invention provide this functionality by using a tree data structure to store a table mapping storage volume data locations to SSD data locations and associating a time stamp with each entry. Embodiments of the present invention update the time stamp with each access to the associated SSD location. Embodiments of the present invention further use advantages of the tree data structure to efficiently determine an SSD memory location associated with an oldest time stamp in order to make that SSD memory location available for storage of recently accessed data from the storage volume.

Embodiments of the present invention provide a method, system and computer-readable storage medium for storing a mapping entry including a mapping of a storage volume data location to a SSD memory location in a tree data structure, storing data from the storage volume data location at the SSD memory location, storing a timestamp with the mapping entry, determining an oldest timestamp of all entries stored in a node of the tree data structure, storing the oldest timestamp in association with a key entry linked to the node of the tree data structure in a parent of the node, and finding a least-recently-accessed SSD memory location using the timestamp information. Aspects of the above embodiment provide that the timestamp is associated with the last time the data in the SSD memory location is accessed. Another aspect of the above embodiment is that the least recently accessed SSD memory location has a mapping entry stored with the oldest timestamp.

Another aspect of the above embodiment provides for finding the least recently accessed SSD memory location by searching a node of the tree data structure for an entry stored with the oldest timestamp, if the node is a leaf node then the SSD memory location is the sought for memory location, and if the node is not a leaf node then a key associated with the timestamp is identified and the key is followed to a child node where the searching continues. A further aspect of the above aspect is performing the finding of a least recently accessed SSD memory location in response to a request to store additional data in the SSD but the SSD has insufficient space to store the additional data. Another aspect further involves deleting the entry stored with the oldest timestamp, storing the second data at the SSD memory location, storing a second mapping entry including a mapping of the storage volume location of the second data to the SSD memory location, and storing a second timestamp with the second mapping entry.

A further aspect of the above embodiment provides for the timestamp to be a clock value or a counter value. Another aspect of the above embodiment updates the timestamp upon access to the data stored in the SSD memory location.

DETAILED DESCRIPTION

Embodiments of the present invention identify data that can be removed from a solid state drive cache by determining a least recently accessed memory region of the SSD. Embodiments of the present invention provide this functionality by using a tree data structure, such as a B+ tree, to store a table mapping storage volume data locations to SSD data locations and associating a time stamp with each entry. Embodiments of the present invention update the time stamp with each access to the associated SSD location. Embodiments of the present invention further use advantages of the tree data structure to efficiently determine an SSD memory location associated with an oldest time stamp in order to make that SSD memory location available for storage of recently accessed data from the storage volume.

Solid State Drive Caching

FIG. 1is a simplified block diagram illustrating an example of a system incorporating a SSD cache, in accord with embodiments of the present invention. A server110hosting a mechanism for providing access to disk volumes or file systems on disk volumes (e.g., volume manager140) is coupled to one or more client computers120via a network130. Embodiments of network130can include, for example, a local area network, metro area network, wide area network, storage area network, or any combination thereof. Embodiments of the present invention are not limited by the type or protocols of communication for network130. Server110can provide access to disk volume or file system space either to directly-coupled disk volumes or by disk volumes that are served to server110via a storage area network, network attached storage, a storage appliance, and the like.

As illustrated, server110hosts a volume manager140that provides access to a storage volume150. Storage volume150can include one or more physical hard disk drives (HDD) and data stored thereon. Volume manager140also provides, via cache manager160, access to a solid state drive (SSD) cache170. The SSD cache is configured to store data accessed from storage volume150and to be the source of that data for subsequent accesses to that data until that data is removed from the SSD cache. Typically, the SSD cache will be as large as 10% of the storage size of an associated storage volume, and will therefore not have capacity to store all of the data stored on the associated storage volume. Thus, a mechanism for identifying candidate data to be removed from the SSD cache when no longer needed, or when not accessed recently, is desirable.

FIG. 2is a simplified flow diagram illustrating a method for accessing data in a data caching system, in accord with embodiments of the present invention. A request is received for data stored in a storage volume (e.g., storage volume150) (210). The data request can be received from, for example, any one of clients120or a user accessing server110in another manner. The request can be received by, for example, a volume manager140. A determination is then made as to whether the requested data is located in the cache (e.g., SSD cache170) (220). Such a determination can be performed by checking a mapping table that includes entries associating storage blocks from the storage volume to memory locations in the SSD cache. Such a mapping table can be maintained, for example, by cache manager160, which can also perform the table lookup. If the requested storage volume data locations are mapped to the SSD cache, then the requested data can be read from the cache (230). Once the data is read from the SSD cache, that data can be provided by the server to the requesting entity.

If the mapping table lookup does not provide a corresponding location in the SSD cache, this means that the requested data has not previously been provided to the SSD cache or the SSD cache currently does not have the requested data stored therein. The requested data is then read from the storage volume and provided to the requesting entity (240). The read can be performed as with any normal read through the use of disk calls provided by, for example, volume manager140to storage volume150. If the requested data should be cached, then a determination is then made as to whether there is sufficient free space available in the SSD cache to store the data read from the storage volume (250). If sufficient free space is available, then the data read from the storage volume is copied to the free space in the SSD cache (260). The mapping table is then updated to include an entry identifying the memory location from the hard disk drive and identifying the location in the SSD cache where the cached image is stored (270).

If sufficient free space for the data read from the disk volume is not found (250), then cache memory space is identified for freeing up so that the new data can be stored in the cache (280). As will be discussed in further detail below, one method of identifying cache memory space to free up involves determining that cache space that has least recently been accessed. Once the cache memory space to be freed up has been identified, the cache manager can delete the data stored in the identified cache space and the entry associated with the freed up cache memory space in the mapping table can be deleted (290). At this point, the cache manager, for example, can perform the tasks related to copying data from the storage volume to the freed up space in the cache (260) and record the mapping of the hard disk drive storage space to the solid state drive storage space (270).

In this manner, data can be read from the SSD cache in order to provide quick I/O response times. If the data is not available in the SSD cache, the data can be accessed from the hard disk drive and then stored in an appropriate location in the solid state drive. It should be noted, that the structures referenced above for bothFIGS. 1 and 2for performing the various tasks inFIG. 2, are provided by nature of an example only. Alternate structures and devices can perform the tasks or part thereof. Embodiments of the present invention are not limited to the structures discussed above.

Identifying and Freeing Up Cache Memory Space

In order to track the mappings from data storage space in a storage volume and associated data storage space in an SSD cache, a mapping index is maintained. A key to the index can be the storage volume storage location. In this manner, when data stored in the storage volume is requested, the data location can be rapidly searched in the index to determine whether the storage volume data has already been stored on the solid state drive. One example of a data structure that can be used to efficiently store entries of such a mapping table is a tree data structure, such as a B+ tree. Given the large number of entries that can be present in such a mapping table because of the size of the solid state drive and the number of data blocks present in the storage volume, a tree data structure provides a flexible and efficient data storage mechanism for referencing the information in the mapping table. The mapping table tree data structure can be stored either in memory of the server providing access to the SSD or on the SSD itself for quick access.

FIG. 3Aillustrates an example B+ tree data structure300that can be used in conjunction with embodiments of the present invention. A B+ tree has three types of nodes: a leaf node310, an internal node320, and a root node330. In a B+ tree, in contrast to, for example, a B-tree, all records are stored at the leaf node level of the tree, while keys to lower level nodes are stored in the internal nodes. Thus, each entry of the mapping table would be located as an entry in a leaf node. Each leaf node can be linked to one another as a linked list, thereby making range queries or an ordered iteration through the leaf node entries simpler and more efficient. In a typical B+ tree, each internal node contains a key pointer to one or more child nodes of that internal node. A root node is the top level internal node which can contain two or more key pointers to internal nodes in the level immediately beneath the root node.

Embodiments of the present invention modify entries and keys stored in a typical B+ tree data structure by including a time stamp indicating the latest time the entry was accessed. Such a time stamp can be either a true clock time stamp or a logical sequence number or checkpoint number increasing linearly over time or with the number of accesses to data stored in the SSD. Through such time stamps, the last accessed time for an entry can be determined either absolutely (e.g., through the use of a clock time stamp) or relatively (e.g., through the use of an increasing checkpoint number).

FIG. 3Billustrates an example of data that can be contained in a leaf node entry350, in accord with embodiments of the present invention. A value representing the hard disk drive or storage volume starting block (360), which can also be the index value of the mapping table, a length or number of blocks of the data found on the hard disk drive or storage volume (365), the SSD starting memory location (370), the SSD length or number of blocks (375), and the time stamp (380). In a typical B+ tree used to track mapping for a SSD cache, a leaf node can have on the order of 350 entries, while each internal node can have on the order of 350 keys pointing to child nodes.

One goal of embodiments of the present invention is to be able to efficiently locate a cache entry that has least recently been accessed. This can be accomplished by modifying the typical B+ tree to include with the keys in an internal node the oldest time stamp reflected in that internal node's child nodes. Thus, for example, an internal node having only leaf nodes as its children, contains not only keys to the leaf nodes, but also a time stamp associated with each key that is the earliest timestamp recorded for all the entries of the leaf node pointed to by that key. Each key in an internal node will have such a time stamp.

When data associated with a leaf node entry is accessed, the time stamp associated with that leaf node entry will be updated. If appropriate, time stamps for all the keys leading to the root from the leaf node entry will be updated if the previous values for those entries were due to the accessed leaf node entry.

Using the timestamps, and the tree data structure, the method for determining the best candidate for deletion in the SSD cache involves following a path through the tree data structure of the least or earliest time stamp from the root node to a node storing the entry associated with the earliest timestamp (e.g., a leaf node of a B+ tree). Once the appropriate entry has been located, the cache manager can delete the data stored on the SSD cache or otherwise indicate that the memory location can be overwritten, and the entry associated with that space on the SSD cache is be removed from the mapping index.

FIG. 4is a simplified flow diagram illustrating an example of a process for identifying cache space to make available, in accord with embodiments of the present invention. The process illustrated inFIG. 4can be used to perform a combination of steps280and290ofFIG. 2.

The process illustrated inFIG. 4can be performed in response to determining that free memory space for a newly accessed section of an associated storage volume is unavailable in an SSD cache or when available free space in the SSD cache falls below a predefined threshold (410). This step corresponds to conditional step250illustrated inFIG. 2. In order to identify SSD cache memory to free up, a search is made for an oldest time stamp associated with a key stored in a root node of a tree data structure storing a table mapping entries of storage volume data locations to SSD cache memory locations (420). The tree data structure can be a B+ tree as illustrated inFIG. 3A, or another tree data structure (e.g., B-tree). Once the oldest time stamp associated with a key is found, a pointer is followed from the key associated with the oldest time stamp to a child node of the root node (430). If the child node is not a leaf node (440), key entries in the internal node are searched for an oldest associated time stamp (450). Once the oldest time stamp is found, a pointer from the key associated with that oldest time stamp is once again followed to the appropriate child internal node (430).

The walk through the internal nodes of the tree data structure continues to be performed until a node storing mapping table entries is reached (e.g., a leaf node of a B+ tree) (440). The mapping table entries of the node are then searched for an oldest time stamp in that node (460). Once the entry having the oldest time stamp is located, the SSD cache memory space associated with that entry is freed up or made available (470). This operation of freeing up or making available the SSD cache memory space allows for subsequent writing of additional data to the identified SSD cache memory space. The entry associated with the oldest time stamp in the node is then removed from the index (480). A determination is then made as to whether there is sufficient free cache memory space available in the SSD cache to store the data from the associated storage volume (490). If not, then an additional search is made for a next oldest time stamp and associated memory (420et seq.). If sufficient free space is available in the solid state cache, then the flow diagram illustrated byFIG. 2continues at step260.

This process of identifying cache space to make available for storage of new data read from the associated storage volume can be performed, for example, by a cache manager160, as illustrated inFIG. 1. Cache manager160can be located on a storage server110or other processing device controlling the SSD cache.

Example Computing Environment

FIG. 5is a block diagram of a computing system510capable of implementing a volume manager or a cache manager, as described above. Computing system510broadly represents any single or multi-processor computing device or system capable of executing computer-readable instructions. Examples of computing system510include, without limitation, any one or more of a variety of devices including workstations, personal computers, laptops, client-side terminals, servers, distributed computing systems, handheld devices (e.g., personal digital assistants and mobile phones), network appliances, storage controllers (e.g., array controllers, tape drive controller, or hard drive controller), and the like. In its most basic configuration, computing system510may include at least one processor514and a system memory516. By executing the software that implements a volume manager or a cache manager, computing system510becomes a special purpose computing device that is configured to provide high availability of one or more applications.

Processor514generally represents any type or form of processing unit capable of processing data or interpreting and executing instructions. In certain embodiments, processor514may receive instructions from a software application or module. These instructions may cause processor514to perform the functions of one or more of the embodiments described or illustrated herein. For example, processor514may perform or be a means for performing the operations described herein. Processor514may also perform or be a means for performing any other operations, methods, or processes described or illustrated herein.

System memory516generally represents any type or form of volatile or non-volatile storage device or medium capable of storing data or other computer-readable instructions. Examples of system memory516include, without limitation, random access memory (RAM), read only memory (ROM), flash memory, or any other suitable memory device. Although not required, in certain embodiments computing system510may include both a volatile memory unit (such as, for example, system memory516) and a non-volatile storage device (such as, for example, primary storage device532or solid state drive170, as described in detail below). In one example, one or more of a volume manager140or cache manager160may be loaded into system memory516.

In certain embodiments, computing system510may also include one or more components or elements in addition to processor514and system memory516. For example, as illustrated inFIG. 5, computing system510may include a memory controller518, an Input/Output (I/O) controller520, and a communication interface522, each of which may be interconnected via a communication infrastructure512. Communication infrastructure512generally represents any type or form of infrastructure capable of facilitating communication between one or more components of a computing device. Examples of communication infrastructure512include, without limitation, a communication bus (such as an Industry Standard Architecture (ISA), Peripheral Component Interconnect (PCI), PCI express (PCIe), or similar bus) and a network.

Memory controller518generally represents any type or form of device capable of handling memory or data or controlling communication between one or more components of computing system510. For example, in certain embodiments memory controller518may control communication between processor514, system memory516, and I/O controller520via communication infrastructure512. In certain embodiments, memory controller518may perform or be a means for performing, either alone or in combination with other elements, one or more of the operations or features described or illustrated herein.

In certain embodiments, communication interface522may also represent a host adapter configured to facilitate communication between computing system510and one or more additional network or storage devices via an external bus or communications channel. Examples of host adapters include, without limitation, Small Computer System Interface (SCSI) host adapters, Universal Serial Bus (USB) host adapters, Institute of Electrical and Electronics Engineers (IEEE) 1394 host adapters, Serial Advanced Technology Attachment (SATA) and external SATA (eSATA) host adapters, Advanced Technology Attachment (ATA) and Parallel ATA (PATA) host adapters, Fibre Channel interface adapters, Ethernet adapters, or the like.

Communication interface522may also allow computing system510to engage in distributed or remote computing. For example, communication interface522may receive instructions from a remote device or send instructions to a remote device for execution.

As illustrated inFIG. 5, computing system510may also include at least one input device528coupled to communication infrastructure512via an input interface530. Input device528generally represents any type or form of input device capable of providing input, either computer or human generated, to computing system510. Examples of input device528include, without limitation, a keyboard, a pointing device, a speech recognition device, or any other input device.

As illustrated inFIG. 5, computing system510may also include a primary storage device532and a backup storage device533coupled to communication infrastructure512via a storage interface534. Storage devices532and533generally represent any type or form of storage device or medium capable of storing data or other computer-readable instructions. For example, storage devices532and533may be a magnetic disk drive (e.g., a so-called hard drive), a floppy disk drive, a magnetic tape drive, an optical disk drive, a flash drive, or the like. Storage interface534generally represents any type or form of interface or device for transferring data between storage devices532and533and other components of computing system510. A storage device like primary storage device532can store information such as configuration information590(e.g., configuration information indicating the priority of applications and the number of retry attempts per application, as described above).

Many other devices or subsystems may be connected to computing system510. For example, storage volume150and solid state drive170can be coupled to computing system510directly via one or more storage interfaces534or indirectly via a network interface (e.g., communication interface522). Conversely, all of the components and devices illustrated inFIG. 5need not be present to practice the embodiments described or illustrated herein. The devices and subsystems referenced above may also be interconnected in different ways from that shown inFIG. 5or described herein.

Computing system510may also employ any number of software, firmware, or hardware configurations. For example, one or more of the embodiments disclosed herein may be encoded as a computer program (also referred to as computer software, software applications, computer-readable instructions, or computer control logic) on a computer-readable medium. Examples of computer-readable media include magnetic-storage media (e.g., hard disk drives and floppy disks), optical-storage media (e.g., CD- or DVD-ROMs), electronic-storage media (e.g., solid-state drives and flash media), and the like. Such computer programs can also be transferred to computing system510for storage in memory via a network such as the Internet or upon a carrier medium. Non-transitory computer-readable media include all forms of computer-readable media except for a transitory, propagating signal.

The non-transitory computer-readable medium containing the computer program may be loaded into computing system510. All or a portion of the computer program stored on the non-transitory computer-readable medium may then be stored in system memory516or various portions of storage devices532and533. When executed by processor514, a computer program loaded into computing system510may cause processor514to perform or be a means for performing the functions of one or more of the embodiments described or illustrated herein. Additionally or alternatively, one or more of the embodiments described or illustrated herein may be implemented in firmware or hardware. For example, computing system510may be configured as an application specific integrated circuit (ASIC) adapted to implement one or more of the embodiments disclosed herein.

Example Network Architecture

FIG. 6is a block diagram of an alternative network architecture600in which client systems610,620, and630(or clients120) and servers640and645(or server110) may be coupled to a network650. Client systems610,620, and630generally represent any type or form of computing device or system, such as computing system510inFIG. 5.

Similarly, servers640and645generally represent computing devices or systems, such as application servers or database servers, configured to provide various database services or run certain software applications. Network650generally represents any telecommunication or computer network including, for example, an intranet, a wide area network (WAN), a local area network (LAN), a personal area network (PAN), or the Internet. In one example, client systems610,620, or630or servers640or645may include monitoring agents or decision-making agents as shown inFIGS. 1 and 2.

As illustrated inFIG. 6, one or more storage devices660(1)-(N) may be directly attached to server640. Similarly, one or more storage devices670(1)-(N) may be directly attached to server645. Storage devices660(1)-(N) and storage devices670(1)-(N) generally represent any type or form of storage device or medium capable of storing data or other computer-readable instructions. In certain embodiments, storage devices660(1)-(N) and storage devices670(1)-(N) may represent network-attached storage (NAS) devices configured to communicate with servers640and645using various protocols, such as Network File System (NFS), Server Message Block (SMB), or Common Internet File System (CIFS).

Servers640and645may also be connected to a storage area network (SAN) fabric680. SAN fabric680generally represents any type or form of computer network or architecture capable of facilitating communication between a plurality of storage devices. SAN fabric680may facilitate communication between servers640and645and a plurality of storage devices690(1)-(N) or an intelligent storage array695. SAN fabric680may also facilitate, via network650and servers640and645, communication between client systems610,620, and630and storage devices690(1)-(N) or intelligent storage array695in such a manner that devices690(1)-(N) and array695appear as locally attached devices to client systems610,620, and630. As with storage devices660(1)-(N) and storage devices670(1)-(N), storage devices690(1)-(N) and intelligent storage array695generally represent any type or form of storage device or medium capable of storing data or other computer-readable instructions.

In certain embodiments, and with reference to computing system510ofFIG. 5, a communication interface, such as communication interface522inFIG. 5, may be used to provide connectivity between each client system610,620, and630and network650. Client systems610,620, and630may be able to access information on server640or645using, for example, a web browser or other client software. Such software may allow client systems610,620, and630to access data hosted by server640, server645, storage devices660(1)-(N), storage devices670(1)-(N), storage devices690(1)-(N), or intelligent storage array695. AlthoughFIG. 6depicts the use of a network (such as the Internet) for exchanging data, the embodiments described or illustrated herein are not limited to the Internet or any particular network-based environment.