Patent Description:
A clustered storage system generally includes multiple storage devices as cluster nodes. Each of the storage devices contributes a portion of its memory space to form a so called "global" memory of the clustered storage system. The global memory of the clustered storage system is accessible by every cluster node, and thus expands the memory space of each individual cluster node. The clustered storage system has flexibility to scale out the capacity of the global memory, e.g., by adding nodes in the clustered storage system.

<CIT> discloses a data storage system, and processes and computer programs for such data storage system, for example including processing of: managing one or more metadata tree structures for storing data to one or more storage devices of the data storage system in units of blocks, each metadata tree structure including a root node pointing directly and/or indirectly to blocks, and a leaf tree level having one or more direct nodes pointing to blocks, and optionally including one or more intermediate tree levels having one or more indirect nodes pointing to indirect nodes and/or direct nodes of the respective metadata tree structure; maintaining the root node and/or nodes of at least one tree level of each of at least one metadata structure in a cache memory; and managing I/O access to data based on the one or more metadata structures, including obtaining the root node and/or nodes of the at least one tree level of the metadata structure maintained in the cache memory from the cache memory and obtaining at least one node of another tree level of the metadata structure from the one or more storage devices.

<CIT> discloses systems, methods and/or devices that are used to perform memory-efficient mapping of block/object addresses. In one aspect, a method of managing a storage system having one or more storage devices includes a tiered data structure in which each node has a logical ID and entries in the nodes reference other nodes in the tiered data structure using the logical IDs. As a result, when a child node is updated and stored to a new location, but retains its logical ID, its parent node does not need to be updated, because the logical ID in the entry referencing the child node remains unchanged. Further, the storage system uses a secondary mapping table to translate the logical IDs to the corresponding physical locations of the corresponding nodes. Additionally, the secondary mapping table is cached in volatile memory, and as a result, the physical location of a required node is determined without accessing non-volatile memory.

<CIT> discloses a system and method for a unified memory and network controller for an all-flash array (AFA) storage blade in a distributed flash storage clusters over a fabric network. The unified memory and network controller has <NUM>-way control functions including unified memory buses to cache memories and DDR4-AFA controllers, a dual-port PCIE interconnection to two host processors of gateway clusters, and four switch fabric ports for interconnections with peer controllers (e.g., AFA blades and/or chassis) in the distributed flash storage network. The AFA storage blade includes dynamic random-access memory (DRAM) and magnetoresistive random-access memory (MRAM) configured as data read/write cache buffers, and flash memory DIMM devices as primary storage. Remote data memory access (RDMA) for clients via the data caching buffers is enabled and controlled by the host processor interconnection(s), the switch fabric ports, and a unified memory bus from the unified controller to the data buffer and the flash SSDs.

The invention is set out by the appended claims.

In accordance with one embodiment of the present disclosure, there is provided a method that includes receiving, by a first storage device in a storage cluster including a plurality of storage devices, a request for reading a data. The storage cluster has a cache memory accessible by the plurality of storage devices, and the cache memory includes a plurality of memories located in the respective plurality of storage devices. The method further includes locating a first address array upon receipt of the request, where the first address array includes one or more addresses; and determining a first address from the first address array in accordance with the request. The first address identifies a memory location of a second address array, and the second address array includes one or more memory addresses. The method also includes determining a second address from the second address array in accordance with request, where the second address identifies a memory location of the data that has been cached in the cache memory; and reading the data from the cache memory in accordance with the second address. By use of the first address array and the second address array, the method has an advantage of determines the memory location of the cached data faster, and is thus able to access the cached data faster. Further, less memory space is needed for storing the first address array and the second address array, which include cache metadata used for accessing the cached data.

In the above embodiment, the data may be cached in a portion of the cache memory that is located in the first storage device, and/or a second storage device different than the first storage device. The data may be read using remote direct memory access (RDMA) or direct memory access (DMA). The first address array and/or the second address array may be stored in the cache memory of the storage cluster. When remote direct memory access (RDMA) is used, the method only needs to perform three RDMA accesses to access the first address array, the second address array and the cached data, thus requiring less RDMA operations for accessing the memory of the storage cluster for reading the cached data.

The above method may include determining, by the first storage device, that the data has not been cached in the cache memory of the storage cluster upon determining that the first address array does not include the first address. The above method may also include determining, by the first storage device, that the data has not been cached in the cache memory of the storage cluster upon determining that the second address array does not include the second address. Accordingly, the method has advantages of determining whether a data is cached in the cache memory fasters based on the first and the second address arrays.

In accordance with another embodiment of the present disclosure, there is provided a method that includes receiving, by a first device in a storage cluster comprising a plurality of devices, a write I/O request for writing a data, where the storage cluster has a cache memory formed by a plurality of memories located in the respective plurality of devices, and the cache memory is accessible by the plurality of devices. The method further includes writing, by the first device, the data into the cache memory to cache the data. The method also includes adding, by the first device, a first address of the data in a first address array, where the first address identifies a memory location of the data cached in the cache memory. The first address array is locatable by a second address included in a second address array, and the second address identifies a memory location of the first address array. The method thus stores the memory location of the cached data using a layered structure.

In accordance with another embodiment of the present disclosure, there is provided a method that includes receiving, by a first storage device in a storage cluster including a plurality of storage devices, a request for reading a data, where the storage cluster includes a plurality of memories located in the respective plurality of storage devices, and the plurality of memories forming a cache memory of the storage cluster. The cache memory is accessible by the plurality of storage device. The method further includes determining a first memory address from a first set of cache metadata in accordance with the request, where the first set of cache metadata includes one or more memory addresses, and the first memory address identifies a memory location of a second set of cache metadata. The method also includes determining a second memory address from the second set of cache metadata in accordance with request, where the second set of cache metadata includes one or more memory addresses, and the second memory address identifies a memory location of the data that has been cached in the cache memory; and reading the data from the cache memory in accordance with the memory location of the data. By use of the first set of cache metadata and the second set of cache metadata, the method is able to determine the memory location of the cached data faster, and is thus able to access the cached data faster. Further, less memory space is needed for storing the first set of cache metadata and the second set of cache metadata, which include cache metadata used to the access the cached data. The method also has advantages of requiring less RDMA operations for accessing the cache memory of the storage cluster for reading the cached data. In this embodiment, the method may use three RDMA accesses for accessing the first set of cache metadata, the second set of cache metadata, and the cached data.

In accordance with another embodiment of the present disclosure, there is provided an apparatus for performing the above described embodiment methods. In accordance with another embodiment of the present disclosure, there is also provided a clustered storage system that includes a plurality of storage devices. Each of the plurality of storage devices is configured to perform above described embodiment methods.

Embodiments of the present disclosure provide methods for accessing a global cache of a clustered storage system. The clustered storage system includes a plurality of storage devices, each of which contributes a portion of its memory to form the global cache of the clustered storage system. Thus, the global cache of the clustered storage system is distributed among the plurality of storage devices, but is accessible by each of the plurality of storage devices. In some embodiments, a multi-layered structure may be used to organize cache metadata for accessing data cached in the global cache. Each layer may include information of addresses pointing to a next layer, and the last layer, i.e., the bottom layer, may include memory addresses locating data that has been cached in the global cache. The multi-layered structure may include various numbers of layers, which may be configurable.

According to some embodiments, a first layer in the multi-layered structure may include an address array, which may include addresses representing the address space of the global cache. Each of the addresses of the first layer is used to locate a node in the second layer. Each node in the second layer points to a portion (e.g., a set of cache pages) of the global cache that has cached data. Each node includes an address array, and the address array includes a set of addresses pointing to, respectively, the set of cache pages. When a cache page has data cached in the cache page, the address of the cache page is included in the address array of a node in the second layer. Otherwise, when the cache page does not have cached data, the address of the cache page will not be included in the address array of the node in the second layer. When a node in the second layer points to (i.e., includes an address that points to) at least one cache page that has cached data, the address array in the first layer includes an address for locating the node of the second layer. Otherwise, when none of the cache pages pointed by the node has cached data, the address array in the first layer does not need to include the address for locating the node of the second layer. With the cache metadata organized in the multi-layered structure, cached data in the global cache may be accessed with a faster speed and reduced number of remote direct memory access (RDMA) operations, and less memory space may be needed for storing the cache metadata. Detailed description will be provided in the following.

A clustered storage system typically includes a plurality of storage devices as cluster nodes, each of which contributes a portion of its memory space to form a so called "global" memory of the clustered storage system. In other words, the global memory of the clustered storage system is distributed among the cluster nodes. The global memory of the clustered storage system is accessible by every cluster node. A cluster node may access distributed memories from any other cluster nodes.

When accessing data across different nodes in a clustered storage system, read and write access to data may go through an indirection layer, i.e., a cache layer, in order to improve overall system performance by exploring spatial and temporal localities. The global memory of the clustered storage system as described above may be used as a global cache memory (or a global cache) of the clustered storage system, and is used by the cluster nodes for caching data. The cache layer in the clustered storage system may thus be referred to as a "globally" accessible cache layer. Data to be written into a main storage device may be temporarily stored in the global cache. Data may also be read directly from a global cache if the data has been cached in the global cache. Since the access speed of a cache memory is usually higher than main storage device, caching significantly improves the read/write performance of the clustered storage system.

Various methods have been used to implement a globally accessible cache layer for accessing a global cache in a clustered storage system. For example, accessing of the distributed memories may be performed through a remote direct memory access (RDMA) network. RDMA is a technique that allows direct memory access from a memory of one computer device into that of another computer device without involving either one's operating system, or processor. This permits high-throughput, low-latency networking. In a clustered storage system, a cluster node may access the distributed memories from any other cluster nodes with a global unique linear virtual address. Metadata and data may be placed in the distributed memories and accessed through RDMA operations. Every access to the distributed memories other than from the originator goes to the RDMA network.

Different cache metadata may be created to reference the caches. Cache metadata may refer to a set of data used to describe or index cache memories. Cached data is thus able to be located in the cache memories by use of the cache metadata. For example, in an asymmetric logical unit access (ALUA) type of storage system, cache metadata may be organized by a certain type of hash tables. Using hash tables is a common practice for a storage system to reference cache pages. A hash value may be calculated for each piece of cached data and saved in a hash table, and the cached data is identified and retrieved by referencing the hash table. In this example, hash values are cache metadata used to access cached data, and organized using a hash table. However, this cache metadata structure is not generally friendly for accessing a global cache. For example, a hash table is not linearly aligned, because two contiguous data blocks may be hashed to two non-contiguous buckets. Further, conflicts may be inevitable due to a limit size of a hash table, and this may result in reduced efficiency of hashing cached data.

In another example, direct mapping may be used to map physical addresses of caches to cached data. The mapping relationship (which is cache metadata) may be saved in memories. However, this may require a large amount of memory space to store the mapping relationship, and space efficiency is a major concern when using this approach for accessing caches. As an illustrative example, in a storage system with an 8PB memory space used as a cache memory, if each cache page store <NUM> data (that is, each cache page has a memory size of <NUM>), <NUM> TB total memories may be required to store cache metadata referencing the cache pages. Cache may be generally organized as cache pages. Each cache page may have a memory size, e.g., <NUM>, <NUM>, or <NUM>. Each cache page may be identified using a memory address. Contiguous cache pages have contiguous memory addresses.

Embodiments of the present disclosure provide methods and apparatus for accessing a global cache of a clustered storage system (or a storage cluster), where cache metadata is organized in a multi-layered cache metadata structure, and used for locating cached data in the global cache. RDMA may be used to access cached data across clustered nodes. Throughout the disclosure, the terms of "clustered storage system" and "storage cluster" are used interchangeably, and the terms of "cache" and "cache memory" are used interchangeably.

<FIG> illustrates a diagram of an embodiment storage cluster <NUM>. The storage cluster <NUM> includes cluster nodes <NUM>, <NUM>, and <NUM>. Each of the cluster nodes <NUM>, <NUM>, and <NUM> may be a storage device, a computer device, or a server. The cluster nodes <NUM>, <NUM>, and <NUM> may be connected to respective hosts, which send input/output (I/O) requests to the respective cluster nodes for reading or writing data. While <FIG> illustrates three cluster nodes in the storage cluster <NUM>, any number of cluster modes may be applicable. For example, the storage cluster <NUM> may include <NUM>, <NUM>, or <NUM> cluster nodes. The cluster nodes <NUM>, <NUM>, and <NUM> include a physical memory <NUM><NUM>, <NUM>, respectively. The memory of each cluster node may be a dynamic random access memory (DRAM). Each of the cluster nodes <NUM>, <NUM>, and <NUM> may include a RDMA network interface card (RNIC), and configured to access memory of a different cluster node through a RDMA network <NUM>.

As shown, each of the cluster nodes <NUM>, <NUM>, and <NUM> contributes a portion of its memory space, i.e., <NUM>, <NUM> and <NUM>, respectively, to form a single logical cache memory space <NUM> for the storage cluster <NUM>. In other words, the single logical cache memory space <NUM> is distributed among the cluster nodes <NUM>, <NUM>, and <NUM>, and includes distributed memories <NUM>, <NUM> and <NUM>. The single logical cache memory space <NUM> is accessible by any cluster node of the storage cluster <NUM>. The single logical cache memory space <NUM> may also be referred to as a global cache memory or a global cache. A portion of memory space contributed by a cluster node may have various sizes, e.g., 8GB, 16GB, or <NUM> GB. The portions of memory space <NUM>, <NUM> and <NUM> may have the same size or different sizes.

As an illustrative example, when a cluster node, e.g., the cluster node <NUM>, receives an I/O request for reading data, the cluster node <NUM> may first check whether the data has been cached in the global cache <NUM>. If the data has been cached, cluster node <NUM> may read the data from the global cache <NUM>. Because the global cache <NUM> is distributed among the cluster nodes <NUM>, <NUM>, <NUM>, the cached data may be located in any of the distributed memories <NUM>, <NUM>, <NUM>. If the cached data is located in the cluster node <NUM>, i.e., in the distributed memory <NUM>, the cluster node <NUM> may read the cached data locally, e.g., using direct memory access (DMA). As one example, one or more cache pages storing the data may be located in the distributed memory <NUM>. If the cached data is located in a different cluster node, e.g., the distributed memory <NUM> of the cluster node <NUM>, the cluster node <NUM> may use RDMA to access (i.e., read) the cached data, i.e., through the RDMA network <NUM>. As one example, one or more cache pages storing the data may be located in the distributed memory <NUM>.

Similarly, when the cluster node <NUM> receives an I/O request for writing data, the cluster node <NUM> may write the data into the global cache <NUM>. If a cache page of the global cache <NUM>, to which data is to be written, is located locally, i.e., in the cluster node <NUM>, the cluster node <NUM> may write the data locally, e.g., using DMA. If the cache page is located in a different cluster node, e.g., the cluster node <NUM>, the cluster node <NUM> may use RDMA to write the data into the cache page, i.e., through the RDMA network <NUM>.

In some embodiments, a multi-layered structure may be used to organize cache metadata for accessing the global cache <NUM> of the storage cluster <NUM>. Each layer may include information of addresses pointing to a next layer, and the last layer, i.e., the bottom layer, may include physical addresses pointing to the actual cached data. The multi-layered structure may include two layers, three layers, or any number of layers, and may be re-configured to provide different numbers of layers, which provides flexibility to scale the cache metadata structure. In this way, each layer may be located or identified by a previous layer using linear access, which improves speed to access cached data. With the cache metadata organized in the multi-layered structure, cached data may be accessed with a faster speed and reduced number of RDMA operations, and less memory space will be needed for storing the cache metadata.

<FIG> illustrates a diagram of an embodiment two-layered cache metadata structure <NUM>. The cache metadata structure <NUM> may be used by a clustered storage system, e.g., the storage cluster <NUM>, to access cached data in a global cache. In this example, cache metadata used to locate cached data in a global cache, e.g., the global cache <NUM>, is organized in two layers, i.e., a first layer <NUM> and a second layer <NUM>. The two layers form a cache layer for the clustered storage system.

The first layer <NUM> is an indirection layer. The first layer <NUM> includes cache metadata pointing to the second layer <NUM>. The first layer <NUM> may be represented by a linear address array including entries. The linear address array represents a contiguous address space of the logical cache memory space used in a clustered storage system, e.g., the global cache <NUM> of the storage cluster <NUM>. Each entry, e.g., <NUM>, <NUM>,. , <NUM>, in the linear array of the indirection layer has an address (i.e., memory address) pointing to the second layer <NUM> or a Null value. In this disclosure, the terms of "memory address" and "address" are used interchangeably.

The second layer <NUM> is a leaf layer. The second layer <NUM> includes a plurality of leaf nodes <NUM>, <NUM>,. Each leaf node includes cache metadata pointing to cache pages storing cached data. Each leaf node may be represented by an address array including entries. Each entry in the address array of a leaf node has an address (i.e., memory address) pointing to a cache page that stores cached data or has a Null value. A cache page storing cached data may be referred to as a cache data page throughout the present disclosure. For example, as shown, the leaf node <NUM> has entries pointing to cache data pages <NUM>, <NUM>,. , <NUM>, and the leaf node <NUM> has entries pointing to cache data pages <NUM>, <NUM>,. When a cache page storing cached data is reclaimed, a corresponding entry of a leaf node pointing to the cache page will have a Null value. A leaf node only exists when its entries point to at least one cache data page. When all the cache pages pointed by a leaf node are flushed, the leaf node may be reclaimed by the clustered storage system. In this case, the entry in the first layer <NUM> pointing to the reclaimed leaf node will have a Null value. Thus, the second layer <NUM> may be thin.

In some embodiments, to construct the two-layered cache metadata structure <NUM>, a global cache of the clustered storage system may be divided into a plurality of groups of cache pages, e.g., N groups. Each group of cache pages corresponds to one leaf node. Accordingly, the second layer <NUM> has N leaf nodes, and each leaf node points to a group of cache pages. The linear array in the first layer <NUM> may include N entries corresponding to the N groups, and each entry has an address (i.e., an entry value) identifying one of the N groups, i.e., N leaf nodes. That is, each entry in the first layer has an address indicating the memory location of a leaf node, consequently, memory location of cache metadata of a corresponding leaf node. A memory location as used herein refers to a location in a memory of a storage cluster. The memory may be a global cache memory of the storage cluster. The memory may be a memory of a cluster node (or a local memory of the cluster node). The memory may also be a global memory of the storage cluster not used as cache. If one leaf node is reclaimed, i.e., none of the cache pages pointed by the leaf node has data, the entry in the first layer pointing to the leaf node may be empty or Null (i.e., does not have a value). If data is then saved in at least one cache page of the reclaimed leaf node, the entry in the first layer corresponding to the leaf node will be filled with the address of the leaf node. Thus, cache metadata in the first layer includes the N entries, which need to be saved in memory, and used for locating leaf nodes in the second layer.

Each of the N leaf nodes may correspond to the same number of cache pages or different numbers of cache pages. An address array representing a leaf node in the second layer <NUM> may include M entries corresponding to M cache pages. The M entries include memory addresses indicating memory locations of the M cache pages. An entry is filled with a physical address of a cache page when the cache page has data cached. Otherwise, if a cache page of the M cache pages does not have cached data, the entry in the address array corresponding to the cache page will be Null or empty. If new data is cached in this cache page later, a physical address of this cache page will be filled in the corresponding entry of the address array of the leaf node. Thus, cache metadata in the second layer includes MxN entries, which need to be saved in memory, and used for locating cache data pages in the global cache.

Table <NUM> below shows an example address array. The address array includes <NUM> entries, having entry values V<NUM>-V<NUM>, respectively.

Table <NUM> above may be used to represent the linear array (also referred to generally as an address array) for the first layer <NUM>. In this case, Table <NUM> may include <NUM> entries, and each entry has an entry value of an address, i.e., V<NUM>-V<NUM>, respectively, pointing to a leaf node (i.e., indicating a memory location of the leaf node). When Table <NUM> above is used to represent the address array for the second layer <NUM>, Table <NUM> may include <NUM> entries, and each entry has an entry value of a physical address indicating a cache page (i.e., a memory address of the cache page).

Table <NUM> below shows another example address array, which includes entries, having entry values V1-V3, Null and V<NUM>, respectively.

When Table <NUM> is used to represent the address array for the first layer <NUM>, it points to four leaf nodes with memory addresses of V1, V2, V3 and V5. When Table <NUM> is used to represent the address array for the second layer <NUM>, it points to four cache pages having cached data, with memory addresses of V1, V2, V3 and V5.

The cache metadata in the first and the second layers may be saved in a metadata region of the clustered storage system. The metadata region may be located in one of the plurality of cluster nodes of the clustered storage system. Other cluster nodes who want to access the cache metadata may do so using RDMA. The metadata region may also be located in a global memory space, such as a global cache of a storage cluster. In this case, the cache metadata may be stored in different cluster nodes of the storage cluster. In one embodiment, each cluster nodes may store a copy of the cache metadata, and access the cache metadata locally when needed.

Referring back to <FIG>, the entries <NUM>, <NUM>, <NUM> of the address array in the first layer <NUM> have entry values of V1, V2, V3, respectively. Each of the entry values is an address that identifies a memory location of metadata of a leaf node in the second layer <NUM> corresponding to the entry. For example, V1 is an address of the leaf node <NUM>, and shows where cache metadata of the leaf node <NUM> is stored. Similarly, V2 is an address of the leaf node <NUM>, where cache metadata of the leaf node <NUM> is stored, and V3 is an address of the leaf node <NUM>, where cache metadata of the leaf node <NUM> is stored. As an illustrative example, entries of the leaf node <NUM> have entry values of Y1, Y2,. Y3, respectively. Y1, Y2, Y3 are addresses of the cache data page <NUM>, <NUM>, and <NUM>, respectively. Thus, the first layer corresponds to a first set of cache metadata, i.e., entries <NUM>, <NUM>,. <NUM>, corresponding to the plurality of leaf nodes <NUM>, <NUM>,. Each of the first set of cache metadata identifies a location of a second set of metadata, i.e., a leaf node, or has a Null value. Each of the second set of metadata identifies a cache data page, e.g., the cache data page <NUM>, or has a Null value. The first set of metadata and the second set of metadata may also be stored in the global cache. Thus, the global cache may be used to store data and metadata.

As an illustrative example of a two-layered cache metadata structure, the first layer may represent a contiguous logical block address space of the global cache of the storage cluster. Each entry of the first layer may be a pointer pointing to the second layer which further points to cache pages storing cached data. Each entry of the first layer may have an address pointing to one of the N groups of cache pages. Thus, there are N leaf nodes. In a case where each cache page is 8KB and each leaf node includes <NUM> entries, each leaf node (consequently, a corresponding entry in the first layer) points to a <NUM>*8KB memory (i.e., 8MB memory). In such a case, for example, a first entry in the first layer points to <NUM>-8MB cache pages (i.e., a first leaf node) of the global cache, a second entry in the first layer points to <NUM>-16MB cache pages (i.e., a second leaf node) of the global cache, and a third entry in the first layer points to 16MB-32MB cache pages (i.e., a third leaf node) of the global cache, etc. When an I/O request is received, an entry in the first layer may be determined first, which points to a leaf node in the second layer, and then an entry in the leaf node pointed by the entry in the first layer may be determined. The entry in the leaf node identifies a cache page with cached data in response to the I/O request. In some embodiments, offsets may be used to determine entries in the first layer and the second layers. For example, if the I/O request has a first offset of 16MB for the first layer, then the third entry in the first layer (pointing to 16MB-32MB cache pages) may be located. When the third entry in the first layer is located, the third leaf node in the second layer (corresponding to the third entry of the first layer) is thus located. Since each entry in the second layer points to an 8KB cache page, if the I/O request has a second offset of 24KB for the second layer, a fourth entry (a first entry points to <NUM>-8KB, a second entry points to <NUM>-16KB, a third entry points to <NUM>-24KB, the fourth entry points to <NUM>-32KB, etc.) in the third leaf node may be located. Thus, the cache page pointed by the fourth entry in the third leaf node may be determined and the cached data may then be retrieved. If a cache page pointed by a leaf node does not exist, i.e., no data has been cached in the cache page, an entry of a leaf node pointing to the cache page is Null. Those of ordinary skill in the art would recognize that various mechanisms or methods may be used to determine (or locate) entries in the multi-layered metadata structure in response to an I/O request.

When an entry in the first layer determined based on the first offset is Null, which means that the requested data has not cached, then there is no need to locate and access the second layer metadata. When an entry in the second layer determined based on the second offset is Null, this means that requested data is not cached. If all the entries of a leaf node are Null, then this leaf node is reclaimed, i.e., cache pages pointed by the leaf node are cleaned and become available for caching new data. Accordingly, an entry in the first layer pointing to this leaf node is updated to be Null. Thus, a cluster node may determine whether or not requested data has been cached based on whether an entry in the first layer, or an entry in the second layer, is Null.

In one example, when a cluster node receives an I/O request for reading data, the cache layer may be first consulted to determine whether the data has been cached in the global cache. The cluster node may locate the cache metadata of the first layer, and then locate an entry of the first layer. In one example, the I/O request may include a device ID and an offset, which are used to identify the location of the first layer cache metadata. The cluster node may then determine an entry in the cache metadata of the first layer based on the request (e.g., an offset). If the entry is empty or Null, it means there is no cached data page existing, i.e., the data is not cached. If the entry points to a leaf node, i.e., the entry has an address identifying a memory location of the leaf node, the cluster node locates the cache metadata of the leaf node, and determines an entry of the leaf node (e.g., based on an offset), and consequently, determines an address of a cache page that stores the data. If the leaf node points to valid cache data pages, operations on these cache data page are allowed.

In another example, when a cluster node receives an I/O request for writing data, the cluster node may first write the data to the global cache. The data may be written into a cache page of the global cache. An address of the cache page may then be used as a value of an entry of a leaf node in the second layer. For example, the entry previously had a Null value, which is overwritten by the address of the cache page). If the entry is the first entry that has a value not Null, i.e., the leaf node did not exist previously, then, an entry in the first layer corresponding to the leaf node will be filled with an address indicating memory location of the leaf node.

<FIG> shows that cache metadata of a storage cluster is organized using a two-layer structure. In some embodiments, a multi-layer structure with more than two layers, e.g., <NUM>-layer, or <NUM>-layer, may also be used to organize cache metadata of a storage cluster. other <FIG> illustrates a diagram of an embodiment three-layered cache metadata structure <NUM>. Those of ordinary skill in the art would recognize that other number of layered structure for organizing the global cache may be built similarly without departing from the scope of the present disclosure. The cache metadata structure <NUM> may be used by a clustered storage system, e.g., the storage cluster <NUM>, to access cached data in a global cache, e.g., the global cache <NUM>. In this example, cache metadata used to locate cached data in the global cache is organized in three layers, i.e., a first layer <NUM>, a second layer <NUM>, and a third layer <NUM>. The three layers form a cache layer for the clustered storage system. The first layer <NUM> and the second layer <NUM> are indirection layer. The third layer <NUM> is a leaf layer.

The first layer <NUM> includes cache metadata representing the logical cache memory space used in a clustered storage system, e.g., the logical cache memory space <NUM> of the storage cluster <NUM>. The first layer may be represented by an address array (e.g., a linear array) including entries. Each entry, e.g., <NUM>, <NUM>,. , <NUM>, in the linear array of the indirection layer has an address pointing to the second layer <NUM>, or has a Null value.

The second layer <NUM> includes a plurality of branch nodes <NUM>, <NUM>,. Each of the branch nodes <NUM>, <NUM>,. , <NUM> includes cache metadata pointing to the third layer <NUM>. Each branch node may be represented by an address array that includes a plurality of entries. Each entry has an address pointing to the third layer <NUM>.

The third layer <NUM> is similar to the second layer <NUM> in <FIG>. The third layer <NUM> includes a plurality of leaf nodes <NUM>, <NUM>,. Each leaf node is represented by an address array. Each entry in the address array of a leaf node points to a cache data page. For example, as shown, the leaf node <NUM> has entries pointing to cache data pages <NUM>, <NUM>,.

As shown in <FIG>, each entry of the first layer <NUM> points to a branch node of the second layer <NUM>, and each entry of a branch node points to a leaf node of the third layer <NUM>. Each entry of a leaf node in the third layer points to a cache page. A leaf node only exists when its entries point to at least one cache data page. When all the cache pages pointed by a leaf node are flushed, the leaf node may be reclaimed by the clustered storage system. If one leaf node is reclaimed, i.e., none of the cache pages pointed by the leaf node has data, an entry in the second layer corresponding to the leaf node may be empty i.e., does not have a value or has a Null value (not shown). If new data is saved in at least one cache page of the reclaimed leaf node, the entry corresponding to the leaf node in the second layer will be filled with the address of the leaf node. When a branch node has all entries empty, an entry in the first layer corresponding to the branch node will be empty (has a Null value).

In some embodiments, to construct a three-layered cache metadata structure, a global cache of the clustered storage system may be divided into a plurality of groups of cache pages, e.g., N groups. Each group of cache pages corresponds to one branch node. Accordingly, the second layer <NUM> has N branch nodes (e.g., branch nodes <NUM>-<NUM>). The linear array in the first layer <NUM> may include N entries (e.g., entries <NUM>-<NUM>) corresponding to the N groups, and each entry has an address (i.e., an entry value) identifying (locating) one of the N branch nodes. Thus, cache metadata in the first layer includes the N entries, which need to be saved in memory, and used for locating branch nodes in the second layer.

Each of the N groups (i.e., N branch nodes) in the second layer may be further divided into K sub-groups of cache pages, and each sub-group corresponds to a leaf node. Accordingly, each branch node (e.g., branch node <NUM>) points to K leaf nodes (e.g., leaf nodes <NUM>-<NUM>) in the third layer <NUM>. Each branch node in the second layer has an address array including K entries. Each of the K entry points to one leaf node in the third layer. Thus, cache metadata in the second layer includes KxN entries, which will be saved in memory and used for locating the leaf nodes. Each branch node may have different numbers of entries, i.e., may point to different numbers of leaf nodes.

There are KxN leaf nodes in the third layer <NUM>. Each of the KxN leaf nodes may correspond to the same number of cache pages, or different numbers of cache pages. An address array for a leaf node in the third layer <NUM> may include M entries corresponding to M cache data pages. An entry is filled with a physical address of a cache page when the cache page has data cached. Otherwise, if a cache page of the M cache pages does not have cached data, the entry in the address array corresponding to the cache page will be empty. If new data is cached in this cache page later, physical address of this cache page will be filled in the corresponding entry of the address array. Thus, cache metadata in the third layer includes MxKxN entries, which need to be saved in memory, and used for locating cache data pages in the global cache. One of ordinary skill in the art would recognize that cache metadata may be organized in a multi-layered structure having more than three layers in a similar way as illustrated in <FIG>.

<FIG> illustrates a flowchart of an embodiment method <NUM> for accessing data in a storage cluster. The method <NUM> may be performed by a cluster node in the storage cluster. In this example, cache metadata is organized in two layers, as illustrated in <FIG>, and RDMA is used to access memories across cluster nodes. At step <NUM>, the cluster node receives a read request for reading data. The read request may then be sent to a cache controller (or storage controller), and the cache controller may determine location of the data in a global cache of the storage cluster if the data is cached. At step <NUM>, the cluster node determines, by the cache controller, a location of cache metadata of a first layer. For example, the cluster node may determine the location according to a device ID (devid) and an offset (similar to the first offset as described above used to determine an entry in the first layer) to the devid. In this case, each cluster node may own a set of first layer cache metadata that can be located using a devid of the corresponding cluster node, and the offset is used to determine an entry in the first layer. When all cluster nodes use one set of first layer cache metadata, the offset may need to be pre-processed so that the same offset for different cluster nodes (i.e., different devid) points to different entries in the first layer. The cache metadata of the first layer includes a first set of addresses. At step <NUM>, the cluster node reads the first layer cache metadata, i.e., the first set of addresses, according to the determined location. At step <NUM>, the cluster node determines a first address from the cache metadata of the first layer based on the request. That is, the cluster node determines (or selects) the first address from the first set of addresses. If the cluster node cannot find the first address, which indicates that the data is not cached, the method <NUM> stops. At step <NUM>, the cluster node locates cache metadata of a second layer based on the determined first address. The cache metadata of the second layer includes a second set of addresses. The second set of addresses points to a set of cache pages storing cached data. At step <NUM>, the cluster node determines a second address from the cache metadata of the second layer. That is, the cluster node determines (or selects) the second address from the second set of addresses. At step <NUM>, the cluster node locates a cache data page based on the second address. At step <NUM>, the method reads the data that is cached in the cache data page. In this example, the cluster node performs <NUM> RDMA accesses, i.e., the method <NUM> accesses the cache metadata of the first layer, accesses the cache metadata of the second layer, and reads the data from the cache data page.

<FIG> illustrates a flowchart of an embodiment method <NUM> for accessing data in a storage cluster. The method <NUM> may be performed by a cluster node in the storage cluster. In this example, cache metadata is organized in two layers, as illustrated in <FIG>. At step <NUM>, the cluster node receives a write request for writing data. The write request may then be sent to a cache controller (or storage controller), and cache controller may write the data in a global cache of the storage cluster, and generate cache metadata for locating the cached data. At step <NUM>, the cluster node writes the data in the global cache. At step <NUM>, the cluster node obtains an address of the cached data in the global cache. The address identifies a cache page in the global cache that stores the data. At step <NUM>, the cluster node changes cache metadata in a first layer. This is the case when a leaf node pointing to the cache page in a second layer does not exist. An entry in the first layer corresponding to the leaf node will be filled with an address pointing to the leaf node. If the leaf node pointing to the cache page has exited, this step may be skipped. At step <NUM>, the cluster node changes cache metadata in the second layer. That is, an entry corresponding to the cache page is filled with a physical address of the cache page where the data is cached. In this example, the method <NUM> performs <NUM> RDMA accesses, i.e., the cluster node writes data to the cache page, changes the cache metadata of the first layer, and changes the cache metadata of the second layer.

The embodiment methods have advantages of requiring less memory space to store cache metadata and requiring less RDMA accesses for accessing a global cache of a clustered storage system. As an illustrative example, a storage cluster has 8PB memory capacity, and each cache page stores <NUM> data. In a case where direct mapping is used to reference cached data, 1T of entries may be required to index the cache metadata referencing the cached data in the 8PB memory. In contrast, the embodiment methods, e.g., when a two-layered cache metadata structure is used, need <NUM> of entries for the first layer. The second layer is added when there are cache data pages pointed by the first layer. Thus, the second layer metadata size is bounded by sizes of caches that storing data, not the storage size of the storage cluster. In another example, when hash tables are used to organize cache metadata, and the hash tales keeps an address for each <NUM> user data, a request for accessing <NUM> data (continuous) requires reading <NUM> times of cache metadata. In contrast, the embodiment methods, e.g., when a two-layered cache metadata structure is used, need <NUM> time read of cache metadata in the first layer, and <NUM> time read of cache metadata in second layer, i.e., only <NUM> times access to the cache metadata. Moreover, as discussed above, a cluster node may determine whether or not requested data has been cached based on whether an entry in a layer is Null (i.e., has a value of Null). If an entry in a layer (e.g., layer <NUM> or <NUM>) is Null, then the cluster node does not need to continue to check the cache metadata in other layers lower than the layer (e.g., layer <NUM> or <NUM>). The cluster node is thus able to determine whether requested data has been cached faster, and avoid wasting time checking all cache metadata of the global cache.

<FIG> illustrates a flowchart of an embodiment method <NUM> for accessing data in a storage cluster including a plurality of storage devices. The method <NUM> may be performed by a storage device of the storage cluster. As shown, at step <NUM>, the storage device receives a request for reading a data. The storage cluster has a cache memory accessible by the plurality of storage devices, and the cache memory includes a plurality of memories located in the respective plurality of storage devices. At step <NUM>, the storage device locates a first address array upon receipt of the request. The first address array includes one or more addresses. At step <NUM>, the storage device determines a first address from the first address array in accordance with the request, where the first address identifies a memory location of a second address array. The second address array includes one or more memory addresses. At step <NUM>, the storage device determines a second address from the second address array in accordance with request. The second address identifies a memory location of the data that has been cached in the cache memory. At step <NUM>, the storage device reads the data from the cache memory in accordance with the second address.

<FIG> illustrates a flowchart of an embodiment method <NUM> for accessing data in a storage cluster including a plurality of storage devices. The method <NUM> may be performed by a storage device of the storage cluster. As shown, at step <NUM>, the storage device receives a write I/O request for writing a data. The storage cluster has a cache memory formed by a plurality of memories located in the respective plurality of devices, and the cache memory is accessible by the plurality of devices. At step <NUM>, the storage device writes the data into the cache memory to cache the data. At step <NUM>, the storage device adds a first address of the data in a first address array, where the first address identifies a memory location of the data in the cache memory, and the first address array is locatable by a second address included in a second address array. The second address identifies a memory location of the first address array.

<FIG> illustrates a flowchart of an embodiment method <NUM> for accessing data in a storage cluster including a plurality of storage devices. The method <NUM> may be performed by a storage device of the storage cluster. As shown, at step <NUM>, the storage device receives a request for reading a data. The storage cluster includes a plurality of memories located in the respective plurality of storage devices, and the plurality of memories forms a cache memory of the storage cluster. The cache memory is accessible by the plurality of storage device. At step <NUM>, the storage device determines a first memory address from a first set of cache metadata in accordance with the request, where the first memory address identifies a memory location of a second set of cache metadata. The first set of cache metadata includes one or more memory addresses. At step <NUM>, the storage device determines a second memory address from the second set of cache metadata in accordance with request, where the second memory address identifies a memory location of the data that has been cached in the cache memory. The second set of cache metadata includes one or more memory addresses. At step <NUM>, the storage device reads the data from the cache memory in accordance with the memory location of the data.

<FIG> illustrates an embodiment computing platform that may be used for implementing, for example, the devices and methods described herein, in accordance with an embodiment. Specific devices may utilize all of the components shown, or only a subset of the components, and levels of integration may vary from device to device. Furthermore, a device may contain multiple instances of a component, such as multiple processing units, processors, memories, transmitters, receivers, etc. The processing system may comprise a processing unit equipped with one or more input/output devices, such as a speaker, microphone, mouse, touchscreen, keypad, keyboard, printer, display, and the like. The processing unit may include a central processing unit (CPU), memory, a mass storage device, a video adapter, and an I/O interface connected to a bus.

The bus may be one or more of any type of several bus architectures including a memory bus or memory controller, a peripheral bus, video bus, or the like. The CPU may comprise any type of electronic data processor. The memory may comprise any type of non-transitory system memory such as static random access memory (SRAM), dynamic random access memory (DRAM), synchronous DRAM (SDRAM), read-only memory (ROM), a combination thereof, or the like. In an embodiment, the memory may include ROM for use at boot-up, and DRAM for program and data storage for use while executing programs.

The mass storage device may comprise any type of non-transitory storage device configured to store data, programs, and other information and to make the data, programs, and other information accessible via the bus. The mass storage device may comprise, for example, one or more of a solid state drive, hard disk drive, a magnetic disk drive, an optical disk drive, or the like.

The video adapter and the I/O interface provide interfaces to couple external input and output devices to the processing unit. As illustrated, examples of input and output devices include the display coupled to the video adapter and the mouse/keyboard/printer coupled to the I/O interface. Other devices may be coupled to the processing unit, and additional or fewer interface cards may be utilized. For example, a serial interface such as Universal Serial Bus (USB) (not shown) may be used to provide an interface for a printer.

The processing unit also includes one or more network interfaces, which may comprise wired links, such as an Ethernet cable or the like, and/or wireless links to access nodes or different networks. The network interface allows the processing unit to communicate with remote units via the networks. For example, the network interface may provide wireless communication via one or more transmitters/transmit antennas and one or more receivers/receive antennas. In an embodiment, the processing unit is coupled to a local-area network or a wide-area network for data processing and communications with remote devices, such as other processing units, the Internet, remote storage facilities, or the like.

<FIG> illustrates a block diagram of an embodiment processing system <NUM> for performing methods described herein, which may be installed in a host device. As shown, the processing system <NUM> includes a processor <NUM>, a memory <NUM>, and interfaces <NUM>-<NUM>, which may (or may not) be arranged as shown in <FIG>. The processor <NUM> may be any component or collection of components adapted to perform computations and/or other processing related tasks, and the memory <NUM> may be any component or collection of components adapted to store programming and/or instructions for execution by the processor <NUM>. In an embodiment, the memory <NUM> includes a non-transitory computer readable medium. The interfaces <NUM>, <NUM>, <NUM> may be any component or collection of components that allow the processing system <NUM> to communicate with other devices/components and/or a user. For example, one or more of the interfaces <NUM>, <NUM>, <NUM> may be adapted to communicate data, control, or management messages from the processor <NUM> to applications installed on the host device and/or a remote device. As another example, one or more of the interfaces <NUM>, <NUM>, <NUM> may be adapted to allow a user or user device (e.g., personal computer (PC), etc.) to interact/communicate with the processing system <NUM>. The processing system <NUM> may include additional components not depicted in <FIG>, such as long term storage (e.g., non-volatile memory, etc.).

In some embodiments, the processing system <NUM> is included in a network device that is accessing, or part otherwise of, a telecommunications network. In one example, the processing system <NUM> is in a network-side device in a wireless or wireline telecommunications network, such as a base station, a relay station, a scheduler, a controller, a gateway, a router, an applications server, or any other device in the telecommunications network. In other embodiments, the processing system <NUM> is in a user-side device accessing a wireless or wireline telecommunications network, such as a mobile station, a user equipment (UE), a personal computer (PC), a tablet, a wearable communications device (e.g., a smartwatch, etc.), or any other device adapted to access a telecommunications network.

In some embodiments, one or more of the interfaces <NUM>, <NUM>, <NUM> connects the processing system <NUM> to a transceiver adapted to transmit and receive signaling over the telecommunications network. <FIG> illustrates a block diagram of a transceiver <NUM> adapted to transmit and receive signaling over a telecommunications network. The transceiver <NUM> may be installed in a host device. As shown, the transceiver <NUM> comprises a network-side interface <NUM>, a coupler <NUM>, a transmitter <NUM>, a receiver <NUM>, a signal processor <NUM>, and a device-side interface <NUM>. The network-side interface <NUM> may include any component or collection of components adapted to transmit or receive signaling over a wireless or wireline telecommunications network. The coupler <NUM> may include any component or collection of components adapted to facilitate bi-directional communication over the network-side interface <NUM>. The transmitter <NUM> may include any component or collection of components (e.g., up-converter, power amplifier, etc.) adapted to convert a baseband signal into a modulated carrier signal suitable for transmission over the network-side interface <NUM>. The receiver <NUM> may include any component or collection of components (e.g., down-converter, low noise amplifier, etc.) adapted to convert a carrier signal received over the network-side interface <NUM> into a baseband signal. The signal processor <NUM> may include any component or collection of components adapted to convert a baseband signal into a data signal suitable for communication over the device-side interface(s) <NUM>, or vice-versa. The device-side interface(s) <NUM> may include any component or collection of components adapted to communicate data-signals between the signal processor <NUM> and components within the host device (e.g., the processing system <NUM>, local area network (LAN) ports, etc.).

The transceiver <NUM> may transmit and receive signaling over any type of communications medium. In some embodiments, the transceiver <NUM> transmits and receives signaling over a wireless medium. For example, the transceiver <NUM> may be a wireless transceiver adapted to communicate in accordance with a wireless telecommunications protocol, such as a cellular protocol (e.g., long-term evolution (LTE), etc.), a wireless local area network (WLAN) protocol (e.g., Wi-Fi, etc.), or any other type of wireless protocol (e.g., Bluetooth, near field communication (NFC), etc.). In such embodiments, the network-side interface <NUM> comprises one or more antenna/radiating elements. For example, the network-side interface <NUM> may include a single antenna, multiple separate antennas, or a multi-antenna array configured for multi-layer communication, e.g., single input multiple output (SIMO), multiple input single output (MISO), multiple input multiple output (MIMO), etc. In other embodiments, the transceiver <NUM> transmits and receives signaling over a wireline medium, e.g., twisted-pair cable, coaxial cable, optical fiber, etc. Specific processing systems and/or transceivers may utilize all of the components shown, or only a subset of the components, and levels of integration may vary from device to device.

It should be appreciated that one or more steps of the embodiment methods provided herein may be performed by corresponding units or modules. For example, a signal may be transmitted by a transmitting unit or a transmitting module. A signal may be received by a receiving unit or a receiving module. A signal may be processed by a processing unit or a processing module. Other steps may be performed by a locating unit/module, a determining unit/module, a reading unit/module, a writing unit/module, an accessing unit/module, a caching unit/module, a storing unit/module, an adding unit/module, and/or a setting unit/module. The respective units/modules may be hardware, software, or a combination thereof. For instance, one or more of the units/modules may be an integrated circuit, such as field programmable gate arrays (FPGAs) or application-specific integrated circuits (ASICs).

Claim 1:
A method (<NUM>), comprising:
receiving (<NUM>), by a first storage device in a storage cluster comprising a plurality of storage devices, a request for reading a data, the storage cluster having a cache memory accessible by the plurality of storage devices, and the cache memory comprising a plurality of memories located in the respective plurality of storage devices;
locating (<NUM>) a first address array upon receipt of the request, the first address array comprising one or more addresses;
determining (<NUM>) a first address from the first address array in accordance with the request, and the first address identifying a memory location of a second address array, the second address array comprising one or more memory addresses;
determining (<NUM>) a second address from the second address array in accordance with request, the second address identifying a memory location of the data that has been cached in the cache memory; and
reading (<NUM>) the data from the cache memory in accordance with the second address.