DE102020104701B4 - Cache data localization system - Google Patents

Abstract

A method (100) comprising:storing (104) a direct cache address translation data structure (40; 240; 540) in a volatile memory (32; 232) that can be used to directly translate a logical block address for target data to a candidate physical location on a cache device (28; 228);storing (108) a multi-level translation index (44; 244) in the volatile memory (32; 232) for translating the logical block address for the target data to an expected physical location of the target data on the cache device (28; 228),the multi-level translation index (44; 244) comprising:a first index table for translating the logical block address into a first internal identifier; anda second index table for translating the first internal identifier to the physical storage location on the cache device (28; 228),determining (112) whether the target data is located at the candidate physical location determined via the direct cache address translation data structure (40; 240; 540);in response to the target data being located at the candidate physical location, accessing the target data at the candidate physical location; andin response to the target data not being located at the candidate physical location, accessing (116) the target data at the expected physical storage location determined via the multi-level translation index (44; 244); andmapping the first internal identifier to a different physical storage location in response to data at the expected physical storage location being moved to the different physical storage location.

Description

BACKGROUND

Many computer storage systems may include a cache that contains copies of data stored on slower persistent media. The cache provides faster access to data that is accessed more frequently. Finding the physical location or address of the data in the cache may involve internal metadata lookups.

US 7 685 399 B2 describes a method for moving data between memory addresses in a computer system in which data referenced by memory addresses is stored in physical memory. The method includes providing a translation mechanism for mapping respective pages of contiguous memory addresses to corresponding locations in physical memory according to a specified mapping, whereby a first page of memory addresses is mapped to a first location in physical memory and a second page of memory addresses is mapped to a second location in physical memory; and changing the specified mapping of the translation mechanism to a new mapping in which the second page of memory addresses is mapped to the first location in physical memory, whereby the data stored in the first location has effectively been moved from the first page of memory addresses to the second page of memory addresses without moving the data between locations in physical memory.

DE 695 18 676 T2 describes a cache system that buffers data stored in a main memory and used by a processor. The cache system includes a first cache, a second cache, a first transfer device, a second transfer device, a third transfer device, and an access device. The first cache is fully associative. The second cache is directly mapped. The first transfer device transfers data lines from the main memory to the first cache. The second transfer device transfers data lines from the first cache to the second cache. The third transfer device transfers data lines from the second cache to the main memory. Accesses to data lines from the first cache and the second cache are performed in parallel.

US 2011 / 0 023 027 A1 describes an input/output memory management unit (IOMMU) configured to control requests from an I/O device to system memory, comprising control logic that can perform a two-stage guest translation to translate an address associated with a request generated by an I/O device using translation data stored in system memory. The translation data includes a device table having a number of entries. The control logic can select the device table entry for a given request using a device identifier corresponding to the I/O device generating the request. The translation data can also include a first set of I/O page tables including a set of guest page tables and a set of nested page tables. The selected device table entry for the given request can include a pointer to the set of guest translation tables, and a final guest translation table includes a pointer to the set of nested page tables.

SHORT DESCRIPTION

A method according to claims 1 to 5, a system according to claims 6 to 17 and a non-volatile storage medium according to claims 18 to 20 are disclosed.

BRIEF DESCRIPTION OF THE DRAWINGS

• 1 is a block diagram schematically illustrating portions of an example cache data location system.
• 2 is a block diagram schematically illustrating portions of an example non-transitory computer-readable medium storing example instructions for locating cache data.
• 3 is a flowchart of an example cache data location method.
• 4 is a block diagram schematically illustrating portions of an example cache data location system.
• 5 is a flowchart of an example cache data location method.
• 6 is a flowchart of an example cache data location method.
• 7 is a diagram illustrating portions of an example direct cache address translation data structure in the form of an example hash table.

Throughout the drawings, identical reference numbers indicate similar, but not necessarily identical, elements. The figures are not un ding is to scale, and the size of some parts may be exaggerated to more clearly illustrate the example shown. In addition, the drawings contain examples and/or implementations that are consistent with the description; however, the description is not limited to the examples and/or implementations shown in the drawings.

DETAILED DESCRIPTION OF THE EXAMPLES

Disclosed herein are example systems, methods, and computer-readable instructions that reduce the time required to access data stored in a cache. The disclosed systems, methods, and instructions reduce the time required to access data stored in a cache by reducing the time required to identify the physical location of data in the cache, which may be referred to herein as a "physical location of the cache." With the advent of faster cache memory, the time required to find data in the cache often becomes a bottleneck. The disclosed storage systems, methods, and instructions address this bottleneck by using a less current, but direct and faster address translation data structure in combination with a more current, but slower multi-level address translation index (which may be referred to herein as a "multi-level translation index") in circumstances where direct address translation is no longer current due to data movement or data removal.

In some implementations, copies of data stored on slower persistent media, such as a hard disk drive, are also maintained on a low-latency cache device, such as a storage class memory (SCM) device. In such an implementation, the data stored on the low-latency cache device may be accessed using one or both of two different address translation mechanisms stored in volatile memory (e.g., DRAM or the like). The volatile memory stores a direct cache address data structure, which may be implemented using a hash table. The volatile memory also stores a multi-level translation index that translates logical block addresses into corresponding physical cache addresses. For each of multiple logical block addresses (which may be referred to as "host addresses" or "user input addresses"), the faster direct cache address translation data structure may translate a logical block address directly into a candidate physical address of a candidate physical location in the cache, which may contain a current or previous version of the requested or targeted data. In circumstances where the target data no longer exists at the candidate physical location identified by the direct cache address translation data structure, for example, when the target data has moved within the cache, the multi-level translation index is used to identify an actual physical address of an expected physical location in the cache containing the target data.

As disclosed above, the direct cache address translation data structure is first used to attempt to locate the target data identified by the logical block address. However, in many cases, the target data may no longer be located at the candidate physical location identified by the candidate physical address obtained from the direct cache address translation data structure based on the logical block address. This may be due to the target data having moved to a different location in the cache. For example, older data present in a first physical location of the cache may be overwritten by newer data written to a second physical location of the cache, causing the older data to become out of date. During a process sometimes referred to as "garbage collection," all current data is collected and concentrated with other current data in other physical locations in the cache. For example, such a garbage collection process may copy the newer data at the second physical location to a third physical location of the cache, deleting both the old data at the first physical location (which is no longer current data) and the newer data at the second physical location (which was originally used to overwrite the older data at the first physical location). Such a garbage collection process results in a change in the physical location of the newer data, which may be the target data in this example. When this change occurs, the multi-level translation index is updated to include the new physical location of the newer data (e.g., indicating the newer data stored at the third physical location in the above example). In such examples, the multi-level translation index may be updated for all such current data that has been moved. However, the direct cache address translation data structure (sometimes referred to herein as the direct logical block address to physical address translation data structure) may not be updated at the time of each garbage collection process. This may result in that a physical address retrieved or output from the direct cache address translation data structure (which may be referred to herein as a "candidate physical address") is invalid in that it does not correspond to a physical location in the cache that actually contains the target data. In the examples described here, the physical location indicated by a candidate physical address may be referred to as a "candidate physical location."

Once the candidate physical address for a candidate physical location (which may include the target data) is obtained from the direct cache address translation data structure, the disclosed systems, methods, and computer-readable instructions verify that the target data is actually located at the candidate physical location. In one implementation, each physical location in the cache may store a first identifier that is directly associated with and moves with the allocated data (e.g., when the data is copied to another location, as in the garbage collection process). The entry in the direct cache address translation data structure that links the logical block address to the candidate physical address contains a second identifier associated with the data expected to be located at the candidate physical location. The first time the direct cache address translation data structure is populated with the second identifier, the second identifier is the same as the first identifier stored with the data at the candidate physical location. However, once the data has been moved to a new location, for example due to the garbage collection process described above, the candidate physical location may be free of data or may store other data with an identifier that is different from the identifier associated with the logical block address and previously stored in the direct cache address translation data structure.

The disclosed systems, methods, and computer-readable instructions verify that the target data is actually located at the candidate physical location by comparing the two identifiers. If the two identifiers match, the data at the candidate physical location is the target data identified by the logical block address. If the two identifiers do not match, the data at the candidate physical location is not the target data identified by the logical block address. As a result, the systems, methods, and computer-readable instructions then shift to using the multi-level translation index to locate the target data via a first mapping of the logical block address for the target data to a logical cache address and a second mapping of that logical cache address to the expected (e.g., current) physical address of the target data in the cache. Although the use of the multi-level translation index has increased latencies compared to the direct cache address translation data structure due to the multiple levels or multiple translations, the multi-level translation index is updated more frequently with the current locations for data as part of the garbage collection process can provide a more current and accurate location for the target data.

Once the more current address for the "expected" physical location in the cache containing the target data is found in or retrieved from the multi-level translation index, the systems, methods, and computer-readable instructions use the expected physical location for the target data to update or correct the direct cache address translation data structure. Specifically, the old entry in the direct cache address translation data structure containing the incorrect or invalid candidate address for the target data is removed from the data structure, and a new entry mapping the logical block address to the physical address for the expected physical location of the target data retrieved from the multi-level translation index is added. In other words, the physical address for the expected physical location of the target data output by the multi-level translation index is cached in the direct cache address translation data structure. The "expected" physical location may be the location where the target data is more likely to be located due to the more frequent updating of the multi-level translation index than any physical location provided by the direct cash address translation data structure. Although greater reliability regarding the actual physical location for the target data may be provided, the output of the physical address for the expected physical location may sometimes be erroneous due to a variety of other possible causes. As a result, the term "expected" is used in the present disclosure when describing the physical address for the target data output by the multi-level translation index.

When a system is initiated, the direct cache address translation data structure may contain entries for a given logical block address that are empty, or it may omit any entry corresponding to the logical block address. In response to identifying an empty entry or the absence of a mapped entry for a logical block address, the multi-level translation index may be automatically consulted to identify the actual physical address of the expected physical location containing the data targeted by the logical block address. Once the actual physical address for the expected physical location of the data targeted by the logical block address has been identified using the multi-level translation index, an empty logical block address entry in the data structure may be filled with the actual physical address for the expected physical location, or the data structure may be filled with a new logical block address entry containing the actual physical address for the expected physical location.

An example of such a multi-level translation index is an index that includes a first level that includes a block index that includes a tree that maps, for each of a plurality of logical block addresses, a logical block address (e.g., a volume ID and an offset), which may be referred to as a "logical block address" or "host address") to a respective logical cache address (e.g., a user block (BU), and which may be referred to as a data identifier). The index further includes a second level that includes a cache index that includes a tree that maps, for each of a plurality of logical cache addresses, a logical cache address (e.g., the user block) to a respective actual physical address (e.g., segment ID and offset) for a physical cache location where the data corresponding to (or targeted by) the logical block address is stored in the cache. The cache index is updated when the physical addresses of the data in the cache change. For example, the actual physical address (e.g., the segment ID and offset) of data corresponding to a logical cache address (e.g., user block) may be updated when the physical location of the data associated with the logical cache addresses changes (e.g., as a result of a garbage collection process, as described above).

In one implementation, the direct cache address translation data structure comprises a hash table. In one implementation, for each of multiple logical block addresses, the hash table maps the logical block address (e.g., volume ID and offset, user input address, or host address) directly to a respective physical address (e.g., segment ID and offset) for a physical storage location in a cache, replacing the two tree walks of the multi-level translation index with a single hash table lookup. The hash table, which serves as an acceleration index, can be thought of as a "metadata bypass cache" used in the cache data location system to facilitate storage system addressing in the SCM cache layer without incurring the CPU cost of internal metadata lookups (e.g., by bypassing a lookup for a logical cache address in metadata).

In one implementation, a key for a lookup in the hash table may be based on the logical block address for target data. For example, a hash function may be applied to the logical block address to generate or obtain a "hash" of the logical block address. The hash, or portions of the hash, may serve as a key to perform a lookup in the hash table. For example, a portion of the hash of the logical block address (e.g., the hash without the last 4 bits of the hash) may be used as the first key in the hash table to identify a page that contains an entry containing the candidate physical address for a candidate physical location (e.g., which may contain the target data). The full hash may be used as the second key in the hash table to identify a specific location on the identified page for the entry containing the candidate physical address.

In one implementation, the hash table comprises a two-level table comprising an array of pointers to pages with key/candidate location (K/CPL) entries on each page. In one implementation, each page must be no more than 10 MB in size, and where the pages comprise at least 200,000 pages. In one implementation, each page is 1 MB in size, with the hash table comprising 500,000 pages. In one implementation, each page comprises no more than 50,000 K/CPL entries. Each K/CPL entry can map a logical block address (e.g., via a hash of the logical block address) to a candidate physical address in the entry. In one implementation, each page comprises 32,000 K/CPL entries.

In such implementations, the size of the pages (no larger than 10 MB, and in some implementations 1 MB) can be efficiently managed by a memory allocator. For example, if a uniform allocator is to reclaim memory, pages may be discarded while only a small part of the hash table is lost. In addition, a separate lock (such as a spin lock) can be implemented for each page. In such implementations, gen, most accesses do not conflict with a lock because number of pages is large. In such examples, each page may be protected with a lock, such as a spin lock, but the probability of lock contention for concurrent threads may be negligible. At the same time, number of entries in a page is high, so the space overhead of such a lock is minimal. Such sizing can achieve the inclusion of all entries for a large input/output (IO) under only one lock. For example, a single lock can protect every entry of a page (e.g., 32,000 entries). As a result, such implementations can provide granular page locking that is efficient and enables high concurrency.

In one implementation, a hash of the logical block addresses with the low four bits hidden is used as a key to select a page, so that adjacent logical block addresses (LBAs) end up on the same page. Within each page, an array of key/CPL values is indexed by the (full) hash of the logical block addresses as a key. In one example, the hash table is set to be four-way associative, meaning that there are four possible slots for each key. This arrangement can provide a high load factor with low and deterministic check costs. Performance can be improved because all possible locations for an item in memory are contiguous and can fit in two CPU cache lines.

In one implementation, the location of entry into the set serves as a proxy for its temperature. In such an implementation, the entries in the set are managed in a least recently used (LRU) order by promoting new and accessed entries to the top or least recently used (MRU) end of the set and removing the entry at the bottom or LRU end of the set (the most recently used entry in the set) when a new entry is inserted into a complete set. As a result, the position in the set is used as an indicator of the entry's temperature. Thus, the LRU cache policy can be approximated with little or no storage overhead.

Although using a hash table to implement the direct address translation data structure can, in some examples, result in collisions and evictions that cannot be resolved under a high load factor, the additional inclusion of the multi-level translation index addresses such concerns. Since the direct address translation data structure is itself a cache, misses are acceptable as they are resolved by a data translation path through the multi-level address translation index, albeit at a slightly higher latency.

Disclosed is an example system that may include persistent storage devices, low latency cache devices, volatile memory, and at least one processor. The processor is to execute instructions to store a direct address translation data structure in the volatile memory that can be used to directly translate a logical block address for target data to a candidate physical address of a candidate physical location on the cache device, and store a multi-level translation index in the volatile memory for translating the logical block address for the target data to an actual physical address for an expected physical location containing the target data on the cache device, and determine whether the target data is located at the candidate physical location corresponding to the candidate physical address retrieved from the direct cache address translation data structure.

In response to the target data being located at the candidate's physical location, the processor may execute instructions to access the target data at the candidate's physical location. In response to the target data not being located at the candidate's physical address, the processor may execute instructions to access the target data at the expected physical location retrieved from the multi-level translation index.

Described is an example method that includes storing a data structure in a volatile memory that directly translates a block logical address for the targeted data to a candidate physical address of a candidate physical location on a cache device, storing a multilevel translation index in the volatile memory that can be used to translate the logical block address for the target data into an actual physical address for the expected physical location on the cache device; and determining whether the target data is located at the candidate physical location corresponding to the candidate physical address retrieved from the direct cache address translation data structure. In response to the target data not being located at the candidate physical address, accessing the target data at the expected physical location corresponding to an actual physical address retrieved from the multilevel translation index. In addition, the translation structure retrieves the expected physical location from the multilevel translation index in the direct cache Address translation structure, resulting in automatic updating of the direct cache address.

Disclosed is an example of a non-transitory computer-readable medium containing instructions for a processor. The instructions are operable by the processor to instruct a processor to receive a logical block address for target data, translate the received logical block address directly to a candidate physical address using a direct cache address translation data structure, and determine whether the target data is located at a candidate physical location in a cache that corresponds to the candidate physical address. In response to the target data being located at the candidate physical location, the instructions are operable by the processor to access the target data at the candidate physical location. In response to the target data not being located at the candidate physical location, the instructions are to instruct the processor to use a multi-level translation index to translate the logical block address to a logical cache address, translate the logical cache address to an actual physical address, and access the target data at the actual physical address (e.g., an expected physical location in the cache that corresponds to the actual physical address). In some implementations, the instructions further use the results from the multi-level translation index to automatically update the direct cache address translation data structure.

1 is a block diagram schematically illustrating portions of an exemplary cache data location system 20. System 20 may reduce the time consumed to locate and access data stored on a cache. System 20 may reduce the time required to access cached data by reducing the time required to identify the physical location of data in the cache. System 20 includes persistent storage device(s) 24, low latency cache unit(s) 28, volatile memory 32, and at least one processor 36

Persistent storage devices 24 include one or more non-volatile memory devices for storing data to be accessed, retrieved, or read from. Persistent storage devices 24 further include an area to which data may be copied or written. In the examples described herein, persistent storage devices (such as persistent storage devices 24) may be implemented by hard disk drives (HDD(s)), solid state drives (SSDs) (e.g., flash memory device(s)), or the like, or a combination thereof.

Low latency cache device 28 includes a storage device that stores copies of at least some of the data (schematically shown in dashed lines) that is also stored on persistent storage devices 24. Low latency cache device 28 has a latency or response time that is less than that of persistent storage device(s) 24. As a result, low latency cache device 28 facilitates timely access to copies of data. In one implementation, low latency cache device 28 includes low latency persistent storage device(s) or non-volatile memory device(s). In one implementation, low latency cache device 28 includes one or more storage class memory (SCM) devices. In the examples described herein, SCM may be a type of non-volatile memory (NVM). In some examples, SCM may communicate using a protocol consistent with NVM Express™ (NVMe™). In the examples described herein, an SCM device may be implemented in one of several different forms, such as a 3D XPoint chip (or 3D XPoint DIMM device, a phase change memory (PCM) device (e.g., a phase change random access memory (RAM), Magnetic RAM (MRAM) (such as Spin-Torque Transfer (STT) RAM), Resistive RAM (RRAM), Memristor, or such as, or a combination thereof. In some examples, the SCM may implement block-based access. In other examples, SCM may implement memory-based semantics for data access. In one implementation, persistent storage devices 24 include a hard disk or solid state drive with a response time for a given amount of data of about 10,000 us. In comparison, the low latency cache device 28 in the form of an SCM has a response time for the same data of about 10 us. In some examples, a low latency cache device may be a byte-addressable non-volatile storage device. In some examples, a persistent storage device may be a block-addressable non-volatile storage device.

The volatile memory 32 is volatile in that the non-volatile data storage 32 is lost if power is not supplied to the memory 32 for an extended period of time. In one implementation, the volatile memory 32 comprises a random access memory, such as a dynamic random access memory (DRAM). The volatile memory 32 may have a response time that is less than that of the low latency cache device 28. In one implementation, the low latency cache device 28 in the form of an SCM has a response time of 10 us for the given amount of data, while the volatile memory in the form of a DRAM has a response time for the same given amount of data of approximately 0.1 us.

Processor 36 manages low latency access to data on cache device 28. Processor 36 may be in the form of an application specific integrated circuit or other processing unit (e.g., physical hardware) that executes instructions, code, programming, or circuit logic to manage low latency access to data of cache device 28. The instructions or circuit logic that drive processor 36 cause processor 36 40 to use a direct cache address translation data structure to store data in volatile memory 32. In one implementation, direct address translation data structure 40 directly maps logical block addresses (e.g., each a volume ID and offset) to a respective candidate physical address (e.g., segment ID and offset) for data to be targeted.

Because the address translation is direct (rather than traversing multiple tables or trees), the data structure 40 can enable much faster and more responsive locating a physical address to access user-requested data. In implementations where the data being accessed is stored on the low-latency cache device, such as an SCM storage device, use of the direct address translation table 40 reduces the time or cost associated with locating the physical address of the data, the bottleneck in the overall time to access the data. In one implementation, the direct cache address translation data structure 40 can include a hash table. For example, a hash function can be applied to the logical block address, with the resulting hash serving as the key for a search or lookups in the hash table. In other implementations, the direct address translation data structure 40 can include other data structures, such as a search tree.

The instructions or circuit logic driving the processor 36 also cause the processor 36 to store a multi-level address translation index 44 in a volatile memory 32. The multi-level address translation index 44 may serve as an authoritative (i.e., current) backup when use of the less authoritative direct address translation data structure 40 is unsuccessful, for example, when the physical address of the data requested by the user in the cache device 28 has changed and the direct cache address translation data structure 40 has not yet been updated to reflect the change. The multi-level translation index 44 is more “authoritative” compared to the direct address translation data structure 40 because the multi-level translation index 44 may be more current or up-to-date with respect to the physical location of the target data in the cache due to more frequent updating of the multi-level translation index 44 with the expected physical locations of data in the cache 28 (as this data is moved to different locations in the cache 28) compared to the direct cache address translation data structure 40. An example of such a multi-level translation index 44 is an index that includes a first level that includes a block index that includes a tree that maps logical block addresses (e.g., each with a volume ID and offset) (the logical block address) to the respective cache logical address (e.g., a corresponding user block identifier). The index further includes a second level that includes a cache index that includes a tree that maps the logical cache addresses to the respective actual physical addresses in the cache (e.g., each a segment ID and an offset) that can be used to physically locate the data in the cache. The cache index is updated when the respective physical addresses of the data in the cache change.

2 is a block diagram illustrating portions of an example non-transitory computer-readable medium 60 containing instructions executable by a processor, such as processor 36, to manage access to data stored in a low latency cache (e.g., implemented by a caching device(s), such as device(s) 28). In one implementation, processor 36 follows instructions contained in memory 60. 3 is a flowchart of an example method 100 that may be performed by system 20 having processor 36 according to instructions in memory (or other machine-readable storage medium) 60. It is understood that memory 60 may be used with cache data location systems 20. Likewise, method 100 may be performed with any of the cache data location systems described below or a similar storage system.

As in 2 As shown, the memory 60 includes direct translation data structure instructions 64, multi-level translation index instructions 68; and address access instructions 72. Instructions 64 include programming, code, or logic circuitry that direct processor 36 to execute block 104 of method 100 shown in FIG. 3. In particular, instructions 64 instruct processor 36 to store a data structure, such as data structure 40, in volatile memory, such as volatile memory 32, that directly translates logical block addresses into respective candidate physical addresses for respective candidate physical locations in a cache device, such as cache device(s) 28, as described above. In one implementation, instructions 64 are executable to set up, create, and store a direct translation data structure 40 in the form of a hash table (as described above) in volatile memory 32.

Multi-level translation index instructions 68 include programming, code, or circuit logic executable to direct processor 36 to perform block 108 of method 100 shown in FIG. 3. Instructions 68 instruct direct processor 36 to create, store, and maintain a multi-level translation index, such as index 44, in volatile memory 32 for translating logical block addresses into respective actual physical addresses for respective expected physical locations on cache devices 28, as described above. As described above, in some implementations, the multi-level translation index 44 is created and stored may include a first level that includes a block index comprising a tree that maps lock logical addresses (e.g., each having an ID volume and offset) to a respective logical cache address (e.g., a corresponding user block). The index 44 further includes a second level cache index comprising a tree that maps the logical cache addresses to the respective actual physical addresses (e.g., each a segment ID and an offset) that can be used to physically locate data in the cache. The cache index is updated when the physical address of particular data in the cache changes.

Address access instructions 72 include programming, code, or logic circuitry executable direct processor 36 to perform blocks 114 and 116 of the method 100 in FIG. 3. As indicated by block 112, in response to the processor 36 receiving a logical block address 50 (in 1 shown), the address access instructions 72 direct the direct processor 36 to first determine whether the data targeted by the logical block address 50 is located at the candidate physical address retrieved from the direct cache address translation data structure. To make such a determination, the direct processor 36 directs the instruction 70 to retrieve the candidate physical address for the target data from the direct cache address translation data structure 40. In an implementation where the direct cache address translation data structure 40 includes a hash table, a hash of the logical block address (or portions thereof) may serve as a key to the hash table (as described above) to obtain a candidate physical address for the data item in the cache 28. For example, in one implementation, the hash table maps a hash of the logical block address (the volume ID and offset) directly to the segment ID and offset (the candidate physical location or address), replacing the two tree walks of the multi-level translation index with a single hash table lookup. The hash table, which serves as an acceleration index, is a metadata bypass cache used in the storage system to facilitate addressing of the storage system in the SCM cache layer without incurring the CPU cost of internal metadata lookups.

Once the candidate physical location address is retrieved, a determination is made as to whether the target data is located at the candidate's physical location. In one implementation, the determination is made by comparing two identifiers. In one implementation, each physical location in the cache has a first identifier stored that is directly associated with and moves with the allocated data. The entry in the direct cache address translation data structure that links the logical block address to the candidate's physical location contains a second identifier associated with the data believed to be located at the candidate's physical location. When the direct cache address translation data structure is first populated with the second identifier, the second identifier is the same as the first identifier stored at the candidate's physical location. However, once the data has been moved to a new location, for example due to the garbage collection process described above, the candidate's physical location may be devoid of data and an identifier, or may actually store different data with a different identifier than the identifier associated with the logical block address and previously stored in the direct cache address translation data structure. A comparison of the two identifiers indicates whether the data associated with the logical block address is actually located at the candidate address. If the two identifiers match, the Data at the candidate's physical location is the target data identified by the logical block address, and the target data can be accessed. If the two identifiers do not match, the data at the candidate's physical location is not the target data identified by the logical block address.

As indicated by block 116 in method 100, address response access to the target data that is not located at the candidate's physical location, such as the candidate's physical location that does not contain data or contains data other than the target data corresponding to the logical block address. Instructions 72 instruct processor 36 to access the physical location or address corresponding to the logical block address retrieved from multi-level translation index 44. Specifically, processor 36 performs a first tree lookup in a block index that maps the logical block address (a volume ID and offset) to a user block (which may be the first identifier). Instructions 72 then instruct processor 36 to perform a second tree lookup in a cache index that maps the user block to a segment ID and offset (the expected physical address or position in cache 28) that can be used to physically locate the target data in cache 28.

4 is a block diagram schematically illustrating portions of an example cache data location system 220. The system 220 is similar to the system 20 described above, except that the system 220 specifically includes persistent storage devices 224 in the form of at least one SSD, at least one hard disk, or a combination thereof, a low latency cache device 228 in the form of storage class memory cache, a volatile memory 232 in the form of DRAM, a direct address translation data structure 240 in the form of a hash table, and a multi-level address translation index 244 in the form of an index having a block index 252 and a cache index 254. The remaining components of the system 220 that correspond to the components of the system 20 are similarly numbered. In some implementations, the persistent storage device 224 may comprise a hard disk drive or a combination of a solid state drive and a hard disk drive. As described above, the block index 252 includes a tree that maps a volume ID and offset to a user block. The cache index includes a tree that maps the user block to a segment ID and offset that can be used to physically locate the data in the cache. The cache index 254 is updated when the physical address of particular data in the cache changes.

5 is a flow diagram of an exemplary cache data location method 300. The method 300 is described in the context of execution by the system 220. It is understood that the method 300 may be described by any of the systems described herein or by other similar storage systems.

As indicated by block 304, the cache data location system 220 receives a request from a user to access a copy of the data stored in the memory 228. The system 220 receives a logical block address or a host address. In one implementation, the logical block address includes or corresponds to a volume ID and an offset.

As indicated by block 308, according to instructions, such as instructions included in memory 60 described above, processor 36 determines or identifies a candidate address for the data targeted by the logical block address using the hash table of the direct cache address translation data structure. In other words, processor 36 attempts to identify the physical address in cache 228 that corresponds to the logical block address using direct address translation hash table 240. Direct address translation hash table 240 provides a direct translation from the logical block address to the physical address in cache 228. Specifically, a hash function is applied to the logical block address, with the resulting hash serving as a key to perform a hash table lookup for the physical location of the candidate for the target data. In one implementation, the direct address hash table is used to translate the volume ID and offset (logical block address or logical block address) into a segment ID and offset (the candidate physical location) of the cache 228 without multiple tree index lookups.

As indicated by block 310, the processor 36 determines, in accordance with instructions including the memory 60, whether the direct cache address translation data structure used in block 308 has identified a candidate physical address corresponding to the logical block address (e.g., where the requested data item is stored) that was found. For example, in circumstances where the physical address of the particular target data piece or copy of the data in the cache 228 has been moved, the target data may not actually be delivered to the candidate physical location obtained from the direct cache address translation data structure.

In one implementation, the determination is made by comparing two identifiers. In one implementation, each physical location in the cache has a first identifier stored that is directly associated with and moves with the allocated data. The entry in the direct cache address translation data structure that links the logical block address to the candidate physical location contains a second identifier associated with the data believed to be located at the candidate physical location. When the direct cache address translation data structure is first populated with the second identifier, the second identifier is the same as the first identifier stored at the candidate physical location. However, once the data has moved to a new location, for example due to the garbage collection process described above, the candidate physical location may be free of data and an identifier, or may actually store different data with a different identifier than the identifier associated with the logical block address and previously stored in the direct cache address translation data structure. A comparison of the two identifiers indicates whether the data associated with the logical block address is actually located at the candidate address. If the two identifiers match, the data at the candidate's physical location is the target data identified by the logical block address. If the two identifiers do not match, the data at the candidate's physical location is not the target data identified by the logical block address.

As indicated by block 314, when the correct physical address of the requested data (based on the logical block address) is found, the processor 36 accesses the physical address on the cache device 228. Such access may include reading data from the particular physical address or writing data to the particular physical address.

Alternatively, as indicated by block 316, in response to the cache data location process performed in block 308 not identifying the correct physical address for the requested data, the processor 36 performs a multi-level translation index lookup 320 according to the instruction contained in the memory 60. As indicated by block 322, the processor 36 performs a first tree lookup in a block index that associates the user input (a volume ID and an offset) with a user block. As indicated by block 324, the processor 36 performs a second tree lookup in a cache index that associates the user block with a segment ID and an offset (the physical address in cache 28) that can be used to identify an expected physical location for the target data on the cache 28 per block 314.

As indicated by block 322, the expected physical location retrieved from the multi-level translation index lookup 320 is cached in the hash table. As a result, the direct cache address translation data structure is automatically updated with address information from the more frequently updated multi-level translation index when errors are found in block 308.

6 is a flowchart of an exemplary cache data locating method 400 for locating data in a cache. Although method 400 is described in the context of execution by system 220 (shown and described above with respect to FIG. 4), method 400 may also be performed by system 20 or other similar cache data locating systems or similar storage systems. The blocks of method 400 may be executed by processor 36 according to instructions stored on a non-transitory computer-readable medium. In one implementation, method 400 may be executed by a processor following the instruction contained in a non-transitory computer-readable medium or memory, such as memory 60, where instruction 64, 68, and 72 direct processor 36 to execute method 400.

As indicated by block 404, cache data location system 220 receives a request from a user to access targeted data stored in memory 228. System 220 receives a logical block address, sometimes referred to as a host address or logical block address (BLA). The logical block address is different from the address of the physical location in the cache where the target address is stored. Method 400 facilitates identifying the actual physical address in the cache where the user-identified data is stored with the provided logical block address. In one implementation, the logical block address includes or corresponds to a volume ID and an offset.

Blocks 406 and 408 illustrate an example of directly translating the logical block address into a physical location, a physical cache address that is a candidate for storing the data that the logical block address is looking for, the target data. Blocks 406 and 408 may be executed by processor 36 according to instructions contained in medium 60, such as instruction 68. In block 406, a hash function is applied to the received logical block address. In the example illustrated, the hash function is applied to the logical block address comprising a volume plus offset to produce a hash value.

In block 408, instructions on the non-transitory computer-readable medium direct processor 36 to derive at least one key from the hash value, wherein a lookup of a hash table is performed using the at least one key to identify an entry containing an address for a candidate physical location in the low latency cache device for the target data. The candidate physical location is a physical location in the cache (the low latency cache device, such as the one in device 28 shown), where the target data was known to be located at the time of the last search.

In one implementation, according to instructions included in the medium, processor 36 uses a first portion of the resulting hash as a first key for the hash table to identify a particular page from a plurality of pages for the entry. According to instructions included in the medium, processor 36 uses the entire resulting hash as a second key for the hash table to identify where on the particular page the entry is located. In other implementations, a single key derived from the resulting hash or more than two keys derived from the resulting hash may be used to locate the entry in the hash table that contains the candidate physical address or cache address for the target data.

As described below with respect to FIG. 7, in some implementations, a limited number of entries are maintained for a limited number of corresponding potential block logical addresses. In such implementations, entries linking logical block addresses (or keys derived from hashes of the logical block addressor) to candidate physical locations are maintained only for the most active logical block addresses or logical block addresses. In decision block 410, the instructions instruct processor 36 to determine whether an entry corresponding to the logical block address or logical key exists. In other words, it is determined whether an entry exists in the direct cache address translation data structure associated with the key derived from the hash or hash value. In the example described above, where the entries are stored on different pages, a conclusion can be drawn that an entry for the logical block address or logical key does not exist if the keys derived from the hash, which results from applying the hash function to the logical block address, do not correspond to any pages in the direct cache data location data structure.

In circumstances where the direct cache address translation data structure contains an entry corresponding to the key derived from the hash, the instructions instruct processor 36 to then check the validity of the entry to verify that the candidate physical location address for the target data found in the entry actually contains the target data. In addition to the candidate physical location address for the target data, the entry found in block 408 contains a second data identifier (DI-2). The second data identifier identifies the data corresponding to the logical block address as the target data. In the example illustrated, the entry containing the candidate physical location address may also contain other information, such as the length of data stored at the candidate physical location. Each entry associated with a different logical block address may have a corresponding first data identifier.

When data is written to the cache, the data is assigned a first data identifier D1-1. The second data identifier, sometimes called a block unit (BU), is assigned to the data itself, regardless of the physical location where the data is currently stored. The first data identifier D1-1 and the second data identifier D1-2 facilitate the determination of whether the physical location of the candidate whose address is found in the entry actually contains the target data.

As indicated by blocks 412 and 414, the instructions instruct the processor 36 to read the first data identifier stored at the candidate physical location corresponding to the actual data stored at the candidate physical location and the first data identifier with the second data identifier (DI-2) in the entry. As indicated by block 416, if the first data identifier read from the candidate physical location is equal to the second data identifier stored in the entry (part of the direct cache location data structure), the process 36 concludes that the data stored at the identified candidate physical location is close to the address in the entry that corresponds to the logical block address, and the same data is acquired from the logical block address. As a result, the instructions instruct the processor 36 to access the target data at the candidate physical location. As described above, such access may include modifying the existing data at the candidate physical location or reading the data at the candidate physical location if such reading does not modify the data.

As indicated by block 418, in response to the first data identifier read from the candidate's physical location not matching the second data identifier stored in the entry containing the candidate's physical location address, processor 36 concludes that the target data no longer resides at the candidate's physical location; the data at the candidate's physical location is not the target data corresponding to the logical block address. As a result, the instructions instruct processor 36 to dissociate the candidate physical address in the entry from the logical block address (logical block address) for the target data. In the example illustrated, such dissociation involves completely removing the entry corresponding to the logical block address or logical key.

As indicated by blocks 420 and 422, in response to the absence of an entry in the direct cache data location structure (in the example, the hash table) corresponding to the logical block address or key, or in response to the existing entry but containing a candidate physical location address 400 that does not contain the target data (D1-1 is not equal to D1-2), the method 400 automatically uses the multi-level translation index to attempt to locate the physical location in the cache for the target data. Blocks 420 and 422 illustrate an example of translating the logical block address to an expected physical location or cache address for the target data using a multi-level translation index. As indicated by block 420, the instructions instruct the processor 36 to translate the logical block address to a logical cache address. As indicated by block 422, after retrieving or identifying the logical cache address, the instructions instruct processor 36 to translate the logical cache address into an expected physical location (physical cache location or address) for the target data.

The "expected" physical location is an address provided by the multi-level translation index for the physical location expected to contain the target data. Although the target data cannot necessarily be guaranteed to be located at the expected physical location or at the address of the expected physical location provided by the multi-level translation of blocks 420 and 422, the expected physical location may be more authoritative than the candidate physical location provided by the direct cache location data structure and output in blocks 406 and 408. As described above, the expected physical location is more authoritative than the candidate possible physical location because the expected physical location is currently likely to contain the target data because the multi-level translation index used to perform blocks 420 and 422 is updated more frequently following movement of data within the cache, for example, as a result of the garbage collection processes described above. In contrast, in one implementation, the direct cache location data structure may only be updated in response to a candidate physical location failure (per block 414) or upon system initiation when entries may not yet exist (per block 410).

As indicated by block 424, the expected physical location for the target data corresponding to the logical block address may then be used to access the target data. This may be done directly or may involve returning to block 408 with the direct cache location data structure updated as described below.

As indicated in block 426, after identifying the expected physical location for the target data in block 422, the retrieved expected physical location is used to update the direct cache address translation structure. In one implementation, the physical address for the expected physical location of the target data is retrieved from the multi-level translation index cached in the direct cache address translation data structure. In the example shown, where invalid entries for a logical block address or logical key (entries where the identified D1-1 does not equal D1-2) are completely removed from the direct cache data location data ten structure is removed (hash table in the example), the Direct Cache Address Translation data structure is updated by adding a brand new complete entry to the Direct Cache Address Translation data structure, where the new entry associates the logical block address or logical key with the address of the expected physical location of the target data and its first data identifier D1-1.

In other implementations, updating the direct cache address translation structure may be accomplished in other ways. For example, unpopulated entries for keys may be retained, with the entry populated with the address of the expected physical location for the target data retrieved from the multi-level translation index. Rather than completely removing the entire populated entry for the key in block 418, the invalid portion of the entry, the address for the candidate physical location in the cache incorrectly believed to contain the target data, may be overwritten, removed, and replaced, or otherwise modified to alternatively include the address for the expected physical location as retrieved from the multi-level translation index in blocks 420 and 422.

In the illustrated example, the method 400 saves storage space by not necessarily storing an entry for each logical block address in the direct cache address translation data structure. In the illustrated example, the direct cache address translation data structure comprises N-way entry sets, meaning that for each logical block address or logical block key, there are n possible entry slot ranges of available storage space. In other words, more than N logical block addresses or keys may be pre-allocated to a corresponding set, but only N entries are available for the logical block addresses or keys assigned to the set. When the set is full, all four slots are occupied by an entry for a corresponding key. Adding a new entry for a new key may cause a current entry for a different key to be removed from the set. Using the N-way entry sets in the direct cache address translation data structure provides a high load factor with a low and deterministic check cost. In one implementation, the direct cache address translation data structure uses 4-way entry sets. In other implementations, the direct cache address translation data structure may use N-way sets of other sizes.

In the example illustrated, method 400 manages the entries in each set in a least recently used (LRU) order by promoting new and accessed entries to the top (most recently used (MRU) end) and removing the bottom (LRU) entry when a new entry is inserted into a complete set. As a result, method 400 uses a position in the set as an indicator of a "temperature" of the entry, i.e., how active the entry is. As a result, the size of the direct cache address translation data structure can be regulated with little storage overhead. As indicated in block 426, a new entry containing the address for the expected physical location is placed at the top (MRU end) of its predetermined set. Similarly, as indicated by block 428, if an existing entry has been validated and the target data has been accessed at the candidate physical location identified by the address in the entry (MRU end) of the designated set, the entry containing the address for the candidate physical location is at the top of the designated set. In circumstances where the entry is already at the top of the designated set, no action is taken. In cases where the entry is not at the top, the entry is moved or relocated to the top of the designated set of entries. In other implementations, other schemes may be used to remove existing entries in the N-way sets of the direct cache address translation data structure when a new entry is to be added to a complete set.

7 is a diagram illustrating an example direct cache address translation structure 540 that serves as an acceleration index or metadata bypass cache and utilizes a hash table 570. The direct cache address translation data structure 540 may be used as part of the method 400. In the example illustrated, the hash table 570 includes a two-level table that includes an array of pointers (vectors 572) to pages 574 (one of which is shown) with a plurality of candidate physical location key (K/CPL) entries 576 on each page. Each K/CPL entry may include a mapping of a key (the product of a hash function applied to the logical block address or host address) to a candidate physical address in a cache that corresponds to the logical block address or host address. In one implementation, each page 574 may be no more than 10 MB in size, and where the pages comprise at least 200,000 pages. In one implementation, each page is 1 MB in size, with table 570 containing 500,000 pages. In one implementation Each page 574 comprises no more than 50,000 K/CPL entries 576 (block logical address to physical address entries). In one implementation, each page comprises 32,000 K/CPL entries.

In such implementations, the size of each page 574 (no larger than 10 MB, and in some implementations 1 MB) can be efficiently managed by a memory allocator. For example, if a uniform allocator is to reclaim memory, pages may be discarded while only a small part of the hash table is lost. In such implementations, most accesses do not conflict under a lock because a number of pages 574 is large. In other words, each page 574 can be protected with a lock, such as a spin lock 578, but the probability of lock contention for concurrent threads may be negligible. At the same time, the number of entries 576 in a page is high, so the space overhead for such a lock is minimal. Such sizing can achieve the inclusion of all entries for a large input/output (IO) under only one lock. For example, a single lock may protect each of the logical block addresses from physical address entries of the direct cache data location structure 540, such as each of the 32,000 entries (corresponding to 32,000 possible logical block addresses or the "keys" (resulting from applying a hash function to the logical block addresses) in one example. As a result, such implementations provide granular page locking that is efficient and enables high parallelism.

In one implementation, to select an appropriate page 574 for a given key, a hash function is applied to the logical block address and certain bits (e.g., the low four bits) of the resulting hash are masked, and the remaining bits of the hash are used to select the appropriate page 574 for the given key. If you use this technique to select page mappings for nearby logical block addresses (e.g., logical block addresses (LBAs)), they are likely to end up on the same page. Within each page 574, an array of K/CPL pairs is indexed by the respective keys. In one example, the hash table is seeded in four directions associatively, meaning that there are four possible slots for each key. This arrangement provides a high load factor with a low and deterministic check cost. Performance is improved because all possible locations for an item in memory are contiguous and fit into two CPU cache lines.

In one implementation, for each of the sets 580-1, 580-2...580-n (collectively referred to as sets 480) of a table 570, K/CPL entries are stored in a set based on how recently each entry was accessed (relative to the other entries in the set). As such, the relative position of a K/CPL entry within a set 580 can serve as a proxy for its “temperature” (i.e., how recently the entry was accessed). In such an implementation, the K/CPL entries in the sets 580 are maintained in an LRU order by promoting new and accessed entries to the top or MRU end of the set and removing the bottom or LRU entry in the set when a new entry is inserted into a complete set. As a result, the position in the set is used as an indicator of the temperature of the entry. Thus, the LRU cache policy can be approximated with little or no storage overhead.

In one implementation, a typical block size is 4 kB. The AK/CPL entry may be approximately 32 bytes. As a result, the Al/data structure 540 to data size ratio is 32/4096, 0.7%. For example, a 1.5 TB cache device may use only 12 GB of main memory. Alternatively, without using data structure 540, a design may use the same 12 GB to store a fraction of the data in the cache. Data structure 540 facilitates fast access to the entire cache device.

Although the use of the direct address translation data structure 540, such as a hash table 570, may result in collisions and evictions that cannot be handled under a high load factor, the additional inclusion of the multi-level translation index addresses such concerns. Since the direct address translation data structure is itself a cache, misses are acceptable as they are resolved by a data translation path through the multi-level address translation index, albeit at a slightly higher latency.

For example, although the present disclosure has been described with reference to example implementations, those skilled in the art will recognize that changes may be made in form and detail without departing from the spirit and scope of the claimed subject matter. Although various example implementations have been described as including features that provide one or more advantages, it is contemplated that the described features may be interchanged with one another, or alternatively combined with one another, in the described example implementations or in other alternative implementations. Because the technology of the present disclosure is relatively complex, not all changes in the technology are foreseeable. The present disclosure, described with reference to the example implementations and set forth in the following claims, is intended to be as broad as possible. For example, claims reciting a single specific element also include multiple such specific elements unless expressly stated otherwise. The terms "first,""second,""third," etc. in the claims merely distinguish various elements and are not specifically associated with any particular order or numbering of elements in the disclosure unless stated otherwise.

Claims (20)

A method (100) comprising: storing (104) a direct cache address translation data structure (40; 240; 540) in a volatile memory (32; 232) that can be used to directly translate a logical block address for target data to a candidate physical location on a cache device (28; 228); storing (108) a multi-level translation index (44; 244) in the volatile memory (32; 232) for translating the logical block address for the target data to an expected physical location of the target data on the cache device (28; 228), wherein the multi-level translation index (44; 244) comprises: a first index table for translating the logical block address into a first internal identifier; and a second index table for translating the first internal identifier to the physical storage location on the cache device (28; 228), determining (112) whether the target data is located at the candidate physical location determined via the direct cache address translation data structure (40; 240; 540); in response to the target data being located at the candidate physical location, accessing the target data at the candidate physical location; and in response to the target data not being located at the candidate physical location, accessing (116) the target data at the expected physical storage location determined via the multi-level translation index (44; 244); and mapping the first internal identifier to a different physical storage location in response to data at the expected physical storage location being moved to the different physical storage location. Procedure (100) according to Claim 1 wherein the direct cache address translation data structure (40; 240; 540) stores a first identifier for the target data; wherein a second identifier is stored at the candidate physical location; and wherein the method (100) further comprises comparing the first identifier to the second identifier to determine whether the data at the candidate physical location is the target data. Procedure (100) according to Claim 1 wherein, in response to the logical block address for the target data not being associated with a candidate physical location in the direct cache address translation data structure (40; 240; 540): determining the expected physical location for the target data using the multi-level translation index (44; 244); and modifying the direct cache address translation data structure to associate the determined expected physical location with the logical block address for the target data. Procedure (100) according to Claim 1 wherein the direct cache address translation data structure (40; 240; 540) comprises a hash table (570), the method further comprising: applying a hash function to the logical block address to generate a hash value; and retrieving the candidate physical location from the hash table (570) based on the hash value. Procedure (100) according to Claim 1 wherein in response to the target data not being located at the candidate physical location: caching the determined expected physical location in the direct cache address translation data structure (40; 240; 540), including modifying the direct cache address translation data structure (40; 240) by: separating the candidate physical location from the logical block address for the target data; and associating the determined expected physical location with the logical block address for the target data. A system (20; 220) comprising: a persistent storage device (24; 224); a low latency cache device (28; 228); a volatile memory (32; 232); and a processor (36) for executing instructions stored on a machine-readable storage medium to: store a direct cache address translation data structure (40; 240; 540) in the volatile memory (32; 232) that can be used to directly translate a logical block address for target data to a candidate physical location on the cache device (28; 228); store a multi-level translation index (44; 244) in the volatile memory (32; 232) for Translating the logical block address for the target data to an expected physical location of the target data on the cache device (28; 228), the multi-level translation index (44; 244) comprising: a first index table for translating the logical block address to a first internal identifier; and a second index table for translating the first internal identifier to the physical location on the cache device (28; 228), Determining whether the target data is located at the candidate physical location determined via the direct cache address translation data structure (40; 240; 540); in response to the target data being located at the candidate physical location, accessing the target data at the candidate physical location; and in response to the target data not being located at the candidate physical location, accessing the target data at the expected physical location determined via the multi-level translation index (44; 244); and associating the first internal identifier with a different physical location in response to data at the expected physical location being advanced to the different physical location. System (20; 220) according to Claim 6 wherein the low latency cache device (28; 228) comprises a second persistent storage device. System (20; 220) according to Claim 7 , wherein the second persistent storage device comprises a storage class memory (SCM). System (20; 220) according to Claim 6 wherein the direct cache address translation data structure (40; 240; 540) stores a first identifier for the target data; wherein a second identifier is stored at the candidate physical location; and wherein the instructions are executable to compare the first identifier to the second identifier to determine whether the data at the candidate physical location is the target data. System (20; 220) according to Claim 9 wherein the instructions are executable to, in response to the first identifier being different from the second identifier: separate the candidate physical location from the logical block address for the target data in the direct cache address translation data structure (40; 240; 540); determine the expected physical location for the target data using the multi-level translation index (44; 244); and associate the determined expected physical location with the logical block address for the target data. System (20; 220) according to Claim 6 wherein the instructions are executable to, in response to the logical block address for the target data not being associated with a candidate physical location: determine the expected physical location for the target data using the multi-level translation index (44; 244); and modify the direct cache address translation data structure (40; 240; 540) to associate the determined expected physical location with the logical block address for the target data. System (20; 220) according to Claim 6 wherein: the direct cache address translation data structure (40; 240; 540) comprises a hash table (570); the instructions further executable for: applying a hash function to the logical block address to generate a hash value; and retrieving the candidate physical location from the hash table (570) based on the hash value. System (20; 220) according to Claim 12 wherein the instructions for retrieving the candidate physical location from the hash table (570) based on the hash value comprise instructions for: using a first portion of the hash value as a first key for the hash table (570) to identify a particular page of a plurality of pages (574); and using the hash value as a second key for the hash table (570) to identify a storage location of the candidate physical location on the particular page. System (20; 220) according to Claim 13 wherein each of the plurality of sides is protected by a rotation lock (578). System (20; 220) according to Claim 12 , wherein the hash table (570) is associatively set, with each set fitting into two processor cache lines. System (20; 220) according to Claim 12 wherein the hash table (570) is associatively set and wherein each key has a location within its corresponding set based on an eviction temperature for the key. System (20; 220) according to Claim 6 , where the instructions are executable to: in response to the target data not being located at the candidate physical location: caching the particular expected physical location in the direct cache address translation data structure (40; 240; 540), including modifying the direct cache address translation data structure (40; 240; 540) by: separating the candidate physical location from the logical block address for the target data; and associating the determined expected physical location with the logical block address for the target data. A non-volatile storage medium comprising instructions executable by a processor (36) for: storing a direct cache address translation data structure (40; 240; 540) in a volatile memory (32; 232) that can be used to directly translate a logical block address for target data to a candidate physical location on a cache device (28; 228); storing a multi-level translation index (44; 244) in the volatile memory (32; 232) for translating the logical block address for the target data to an expected physical location of the target data on the cache device (28; 228), wherein the multi-level translation index (44; 244) comprises: a first index table for translating the logical block address into a first internal identifier; and a second index table for translating the first internal identifier to the physical storage location on the cache device (28; 228), determining whether the target data is located at the candidate physical location determined via the direct cache address translation data structure (40; 240; 540); in response to the target data being located at the candidate physical location, accessing the target data at the candidate physical location; and in response to the target data not being located at the candidate physical location, accessing the target data at the expected physical storage location determined via the multi-level translation index (44; 244); and mapping the first internal identifier to a different physical storage location in response to data at the expected physical storage location being moved to the different physical location. Non-volatile storage medium according to Claim 18 wherein the direct cache address translation data structure (40; 240; 540) comprises a hash table (570), the instructions further executable for: applying a hash function to the logical block address to generate a hash value; and retrieving the candidate physical location from the hash table (570) based on the hash value. Non-volatile storage medium according to Claim 18 wherein the instructions are executable to: in response to the target data not being at the candidate physical location: caching the retrieved expected physical location in the direct cache address translation data structure, including modifying the direct cache address translation data structure (40; 240; 540) by: separating the candidate physical location from the logical block address for the target data; and associating the determined expected physical location with the logical block address for the target data.

Images