Back to results
US 8,510,499 B1Granted
Solid state drive caching using memory structures to determine a storage space replacement candidate
AssigneeSymantec Corporation
InventorAnindya Banerjee
Life of this patent
Estimating the term…
Abstract
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.
Claims17
A method comprising:
- storing a mapping entry comprising a mapping of a storage volume data location to a solid state drive (SSD) memory location, wherein
- the mapping entry is stored in a tree data structure;
- storing data from the storage volume data location in the SSD memory location;
- storing a timestamp with the mapping entry wherein the timestamp is associated with a last time the data stored in the SSD memory location is accessed;
- 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 node of the node;
- and
- finding a least recently accessed SSD memory location, wherein
- the least recently accessed SSD memory location has a first mapping entry stored with the oldest timestamp, and
- the finding comprises
- searching a first node of the tree data structure for the first mapping entry stored with the oldest timestamp,
- if the first node is a leaf node of the tree data structure, identifying the SSD memory location stored in the first mapping entry, and
- if the first node is not a leaf node, performing
- identifying the key in the first mapping entry,
- following the key to a child node, and
- repeating said searching.
13 more elements
A system comprising:
- a processor;
- a storage volume coupled to the processor, wherein the storage volume comprises one or more hard disk drives;
- a solid state drive (SSD) coupled to the processor;
- and
- a memory coupled to the processor and storing instructions executable by the processor, the instructions configured to:
- store a mapping entry comprising a mapping of a storage volume data location to a SSD memory location, wherein the mapping entry is stored in a tree data structure,
- store data from the storage volume data location in the SSD memory location,
- store a timestamp with the mapping entry wherein the timestamp is associated with a last access time of the data stored in the SSD memory location,
- determine an oldest timestamp of all entries stored in a node of the tree data structure,
- store the oldest timestamp in association with a key entry linked to the node of the tree data structure in a parent node of the node, and
- find a least recently accessed SSD memory location, wherein
- the least recently accessed SSD memory location has a first mapping entry stored with the oldest timestamp, and
- finding the least recently accessed SSD memory location comprises
- searching a first node of the tree data structure for the first mapping entry stored with the oldest timestamp,
- identifying the SSD memory location stored in the first mapping entry, if the first node is a leaf node of the tree data structure, and
- if the first node is not a leaf node, identifying the key in the first mapping entry, following the key to a child node, and repeating the searching.
13 more elements
A non-transitory computer-readable storage medium storing instructions executable to:
- store a mapping entry in a tree data structure, wherein the mapping entry comprises a mapping of a storage volume data location to a solid state drive (SSD) memory location;
- store data from the storage volume data location in the SSD memory location;
- store a timestamp with the mapping entry wherein the timestamp is associated with a last time the data stored in the SSD memory location is accessed;
- determine an oldest timestamp of all entries stored in a node of the tree data structure;
- store the oldest timestamp in association with a key entry linked to the node of the tree data structure in a parent node of the node;
- and
- find a least recently accessed SSD memory location, wherein
- the least recently accessed SSD memory location has a first mapping entry stored with the oldest timestamp, and
- finding the least recently accessed SSD memory location comprises searching a first node of the tree data structure for the first mapping entry stored with the oldest timestamp,
- identifying the SSD memory location stored in the first mapping entry if the first node is a leaf node of the tree data structure, and
- if the first node is not a leaf node, identifying the key in the first mapping entry, following the key to a child node, and repeating the searching.
8 more elements
Dependencies are inferred from the claim text.