Patent Description:
A distributed system generally includes many loosely coupled computers, each of which typically includes a computing resource (e.g., one or more processors) and/or storage resources (e.g., memory, flash memory, and/or disks). A distributed storage system overlays a storage abstraction (e.g., key/value store or file system) on the storage resources of a distributed system. In the distributed storage system, a server process running on one computer can export that computer's storage resources to client processes running on other computers. Remote procedure calls (RPC) may transfer data from server processes to client processes. Alternatively, Remote Direct Memory Access (RDMA) primitives may be used to transfer data from server hardware to client processes. <CIT> relates to systems and methods for cache load balancing by reclaimable block migration, wherein the systems are configured to: maintain a first list of reclaimable blocks that reside in a first caching device and a first advertised age for the oldest reclaimable block of the first list; maintain a second list of reclaimable blocks that reside in a second caching device and a second advertised age for the oldest reclaimable block of the second list; determine that the second advertised age is older than the first advertised age; and cause the oldest reclaimable block on the first list to be migrated from the first caching device to the second caching device. <CIT> relates to techniques for accelerating and optimizing network traffic, such as HTTP based network traffic, in the areas of proxy caching, protocol acceleration, domain name resolution acceleration as well as compression improvements. by improving the efficiency of obtaining and servicing data from an originating server to server to clients. <CIT> discloses a multi-tenant, elastically scalable cache as a service. The multi-tenant cache service is implemented by maintaining/creating multiple named caches in a cache cluster and mapping each tenant's cache to a named cache in the cluster. Strict quotas are enforced on cache sizes This allows caches with different replication attributes to co-exist on the same cache server, allows migration of a cache from one cluster to another for load balancing purposes, and allows a cache to inflate/deflate to meet business needs. A network load balancer is used to route cache items to servers. <CIT> discloses a distributed cache system including a data storage portion, a data control portion, and a cache logic portion in communication with the data storage and data control portions. The data storage portion includes memory hosts, each having non-transitory memory and a network interface controller in communication with the memory for servicing remote direct memory access requests. The data control portion includes a curator in communication with the memory hosts. The curator manages striping of data across the memory hosts. The cache logic portion executes at least one memory access request to implement a cache operation. In response to each memory access request, the curator provides the cache logic portion a file descriptor mapping data stripes and data stripe replications of a file on the memory hosts for remote direct memory access of the file on the memory hosts through the corresponding network interface controllers.

Dependent claims describe embodiments thereof. One aspect of the disclosure provides a method for an in-memory distributed cache. The method includes receiving, at a memory host of a distributed storage system, a write request from a client device to write a block of client data in random access memory (RAM) of the memory host. The method also includes determining, by the memory host, whether to allow the write request by determining whether the client device has permission to write the block of client data at the memory host, determining whether the block of client data is currently saved at the memory host, and determining whether a free block of RAM is available. When the client device has permission to write the block of client data at the memory host, the block of client data is not currently saved at the memory host, and a free block of RAM is available, the write request is allowed. When the write request is allowed, the method includes allowing, at the memory host, the client to write the block of client data to the free block of RAM.

The method includes periodically determining, at the memory host, an amount of spare RAM available on the memory host. The method also includes determining, at the memory host, whether the amount of spare RAM satisfies a threshold amount comprising at least one block of free RAM. When the amount of spare RAM satisfies the threshold amount, the method may include allocating, at the memory host, at least one free block of RAM to a free block queue. Determining whether a free block of RAM is available may include determining whether at least one free block of RAM has been allocated to the free block queue. In some embodiments, when the amount of spare RAM fails to satisfy the threshold amount, the method may further include deallocating, at the memory host, at least one free block of RAM from the free block queue. Additionally or alternatively, when the amount of spare RAM fails to satisfy the threshold amount, the method includes deleting one or more blocks of client data from the memory host. When deleting one or more blocks of client data, the method includes selecting the one or more blocks of client data for deletion according to a priority. The priority may include selecting expired low priority client data first, selecting expired high priority client data second, selecting low priority client data third, and selecting high priority client data fourth, until the amount of spare RAM satisfies the threshold amount.

In some examples, the write request includes a respective client data hash of the block of client data. Determining whether the block of data is currently saved at the memory host may include determining whether a hash map includes a mapping for the respective client data hash. After the client writes the block of client data, the method may include updating, at the memory host, a block metadata table including a hash map mapping a client data hash to the block of client data and metadata for the block of client data. The metadata may include at least one of a client identifier, a retention priority, a time to live, or a length of the client data.

In some configurations, the method includes receiving, at a network interface controller (NIC) of the memory host, a read request including a client data hash of a stored block of client data. The method may also include allowing, at the memory host, remote direct memory access (RDMA) of the stored block of client data through the NIC. In some examples, after the client writes the block of client data, the method includes validating, at the memory host, the block of client data based on a length of the block of client data or a client data hash to the block of client data. Optionally, the method may also include releasing, at the memory host, any portion of the free block of RAM between an end of the client data and an end of the free block of RAM.

Another aspect of the disclosure provides a method for an in-memory distributed cache. The method includes sending a write request from a client device to a memory host of a distributed storage system. The write request includes a client data hash to a block of client data and metadata for the block of client data. The metadata includes at least one of a client identifier, a retention priority, a time to live, or a length of the client data. The memory host is configured to determine whether to allow the write request by determining whether the client device has permission to write the block of client data at the memory host, determining whether the block of client data is currently saved at the memory host, and determining whether a free block of RAM is available. When the client device has permission to write the block of client data at the memory host, the block of client data is not currently saved at the memory host, and a free block of RAM is available, the write request is allowed. When the write request is allowed, the memory host is configured to allow the client to write the block of client data to the free block of RAM.

Implementations of this aspect of the disclosure may include one or more of the following optional features. In some implementations, the method includes identifying, at the client device, at least one memory host to receive the write request based on a proximity of the memory host relative to the client device. The method may also include determining the block of client data as low priority or high priority. The high priority may result in more replications of the block of client data than the low priority across multiple memory hosts.

In some examples, the memory host is configured to periodically determine an amount of spare RAM available on the memory host and determine whether the amount of spare RAM satisfies a threshold amount comprising at least one block of free RAM. When the amount of spare RAM satisfies the threshold amount, the memory host may be configured to allocate at least one free block of RAM to a free block queue. Determining whether a free block of RAM is available may include determining whether at least one free block of RAM has been allocated to the free block queue. When the amount of spare RAM fails to satisfy the threshold amount, the memory host may also be configured to deallocate at least one free block of RAM from the free block queue. Additionally or alternatively, when the amount of spare RAM fails to satisfy the threshold amount, the memory host may be configured to delete one or more blocks of client data from the memory host. When the memory host is configured to delete one or more blocks of client data, the memory host may also be configured to select the one or more blocks of client data for deletion based on the retention priority of the metadata according to a priority. The priority may include selecting expired low priority client data first, selecting expired high priority client data second, selecting low priority client data third, and selecting high priority client data fourth, until the amount of spare RAM satisfies the threshold amount.

In some configurations, determining whether the block of data is currently saved at the memory host includes determining whether a hash map includes a mapping for the respective client data hash. After the client writes the block of client data, the method may include updating, at the memory host, a block metadata table. The block metadata table may include a hash map mapping the client data hash to the block of client data and metadata for the block of client data.

In some implementations, the memory host is configured to receive, at a network interface controller (NIC) of the memory host, a read request including the client data hash of a stored block of client data. The memory host may also be configured to allow remote direct memory access (RDMA) of the stored block of client data through the NIC. Optionally, after the client writes the block of client data, the memory host may be further configured to validate the block of client data based on a length of the block of client data or the client data hash to the block of client data. In some examples, the memory host is further configured to release any portion of the free block of RAM between an end of the client data and an end of the free block of RAM.

Data centers house computer systems and their associated components, such as telecommunications and storage systems <NUM> (<FIG>). Data centers may be located in different geographical locations (e.g., different cities, different countries, and different continents) and generally include many servers to execute various client processes. Although data centers attempt to prioritize processes based on whether the process is a customer facing job, a batch job, or a free job, computing systems often underutilize their associated computing resources (e.g., central processing units ("CPUs") and memory ("RAM")). For example, with regards to storage resources, larger data centers have observed that their computing systems do not use utilize portions of their RAM, at the ninety-fifth-percentile of usage and/or that routinely portions of their RAM remains idle.

To more effectively and efficiently utilize storage resources, software services may cache large amounts of RAM. Caches may be formed within a server (i.e. inprocess) or run as a separate service shared between multiple instances of a service (i.e. out-of-process). However, a potential concern with caches is that the unused (i.e. free) storage resources forming a cache may need to be later user by the computing system for client processes; thus, affecting cache durability. Even though caches are not durable, caches may accelerate computing by storing data likely to be accessed again in the near future; therefore, preventing reading data again from disk and/or potentially resource expensive re-calculations. Therefore, it is desirable to provide a cache that accounts for the ever changing processing demands of a distributed storage system <NUM>.

Referring to <FIG>, in some implementations, a distributed storage system <NUM> includes loosely coupled memory hosts <NUM>, 110a-n (e.g., computers or servers), each having a computing resource <NUM> (e.g., one or more processors or central processing units (CPUs)) in communication with storage resources <NUM> (e.g., memory, flash memory, dynamic random access memory (DRAM), phase change memory (PCM), and/or disks) that may be used for caching data. A storage abstraction (e.g., key/value store or file system) overlain on the storage resources <NUM> allows scalable use of the storage resources <NUM> by one or more clients <NUM>, 120a-n. The clients <NUM> may communicate with the memory hosts <NUM> through a network <NUM> (e.g., via remote programming calls (RPCs)).

In some implementations, the distributed storage system <NUM> is "single-sided," eliminating the need for any server jobs for responding to remote procedure calls (RPC) from clients <NUM> to store or retrieve data <NUM> on their corresponding memory hosts <NUM> and may rely on specialized hardware to process remote requests <NUM> instead. "Single-sided" refers to the method by which request processing on the memory hosts <NUM> may be done in hardware rather than by software executed on CPUs <NUM> of the memory hosts <NUM>. Rather than having a processor <NUM> of a memory host <NUM> (e.g., a server) execute a server process <NUM> that exports access of the corresponding storage resource <NUM> (e.g., non-transitory memory) to client processes <NUM> executing on the clients <NUM>, the clients <NUM> may directly access the storage resource <NUM> through a network interface controller (NIC) <NUM> of the memory host <NUM>. In other words, a client process <NUM> executing on a client <NUM> may directly interface with one or more storage resources <NUM> without requiring execution of a routine of any server processes <NUM> executing on the computing resources <NUM>. This single-sided distributed storage architecture offers relatively highthroughput and low latency, since clients <NUM> can access the storage resources <NUM> without interfacing with the computing resources <NUM> of the memory hosts <NUM>. This has the effect of decoupling the requirements for storage <NUM> and CPU <NUM> cycles that typical two-sided distributed storage systems <NUM> carry. The single-sided distributed storage system <NUM> can utilize remote storage resources <NUM> regardless of whether there are spare CPU <NUM> cycles on that memory host <NUM>; furthermore, since single-sided operations do not contend for server CPU <NUM> resources, a single-sided system <NUM> can serve cache requests <NUM> with very predictable, low latency, even when memory hosts <NUM> are running at high CPU <NUM> utilization. Thus, the single-sided distributed storage system <NUM> allows higher utilization of both cluster storage <NUM> and CPU resources <NUM> than traditional two-sided systems, while delivering predictable, low latency.

Additionally or alternatively, the distributed storage system <NUM> can utilize a traditional two-sided distributed storage system <NUM> where the clients <NUM> can access both the computing resources <NUM> and the storage resources <NUM> or a hybrid of a two-sided system and a single sided system. For example, when the request <NUM> is related to write operations, the client <NUM> can access the computing resources <NUM> to write to the storage resources <NUM>. Yet when the request <NUM> corresponds to read operations, the client <NUM> can bypass the computing resources <NUM> to the storage resources <NUM> (e.g., via a NIC <NUM>) similar to a single-sided distributed storage system <NUM>.

In some implementations, the distributed storage system <NUM> includes a cache management layer <NUM> and a storage abstraction layer <NUM>. The cache management layer <NUM> may include a cache manager <NUM> that is responsible for accessing the underlying data, for example, via RPC or single-sided operations. The cache management layer <NUM> may manage allocation and access to storage resources <NUM> with tasks, such as allocating storage resources <NUM>, registering storage resources <NUM> with the corresponding network interface controller <NUM> or computing resources <NUM>, setting up connections between the client(s) <NUM> and the memory hosts <NUM>, etc. The storage abstraction layer <NUM> may include the loosely coupled memory hosts <NUM>, 110a-n.

The distributed storage system <NUM> may store data <NUM> in dynamic random access memory (DRAM) <NUM> and serve the data <NUM> from the remote hosts <NUM> via remote direct memory access (RDMA)-capable network interface controllers <NUM>. Additional implementation details and features on RDMA are disclosed in <CIT>. The RDMA may transfer or allow access to stored data (e.g., client data <NUM>) through a network interface controller <NUM> (also known as a network interface card, network adapter, or LAN adapter). The network interface controller <NUM> may be a computer hardware component that connects a computing resource <NUM> to the network <NUM>. Both the memory hosts <NUM>10a-n and the client <NUM> may each have a network interface controller <NUM> for network communications. A host process <NUM> executing on the computing processor <NUM> of the memory host <NUM> registers a set of remote direct memory accessible regions 115a-n of the memory <NUM> with the network interface controller <NUM>. The host process <NUM> may register the remote direct memory accessible regions 115a-n of the memory <NUM> with a permission of read-only or read/write. The network interface controller <NUM> of the memory host <NUM> may create a client key for each registered memory region 115a-n.

The single-sided operations performed by the network interface controllers <NUM> may be limited to simple reads, writes, and compare-and-swap operations, none of which may be sophisticated enough to act as a drop-in replacement for the software logic implemented by a traditional cache server job to carry out cache requests and manage cache policies. The cache manager <NUM> translates commands, such as look-up or insert data commands, into sequences of primitive network interface controller operations. The cache manager <NUM> interfaces between clients <NUM> and the storage abstraction layer <NUM> of the distributed storage system <NUM>.

The distributed storage system <NUM> may include a co-located software process to register memory <NUM> for remote access with the network interface controllers <NUM> and set up connections with client processes <NUM>. Once the connections are set up, client processes <NUM> can access the registered memory <NUM> via engines in the hardware of the network interface controllers <NUM> without any involvement from software on the local CPUs <NUM> of the corresponding memory hosts <NUM>.

Referring to <FIG>, in some implementations, the distributed storage system <NUM> includes multiple clients 120a-n, each client <NUM> interacts with the memory hosts <NUM> through the network <NUM> with the cache manager <NUM>. The cache manager <NUM> is configured to manage a cache table <NUM> for data related to the memory resources <NUM> of the memory hosts <NUM>. The cache manager <NUM> may run on each memory host <NUM> or on a separate host machine. In some examples, the cache manager <NUM> may execute on a computing processor (e.g., server having a non-transitory memory) connected to the network <NUM> and manage the data storage, control data placements, and/or initiate data reallocation. Moreover, the cache manager <NUM> may track an existence and storage location of data (e.g., client data <NUM>) on the memory hosts <NUM>. The distributed storage system <NUM> may include multiple cache managers <NUM> accessible clients <NUM> based on their requests <NUM>. In some implementations, the cache manager(s) <NUM> track the striping of data across multiple memory hosts <NUM> and the existence and/or location of multiple copies of a given stripe for redundancy and/or performance. In computer data storage, data striping is the technique of segmenting logically sequential data in a way that accesses of sequential segments are made to different physical storage devices <NUM> (e.g., memory hosts <NUM>). Striping is useful when a processing device requests access to data more quickly than a storage device <NUM> can provide access. By performing segment accesses on multiple devices, multiple segments can be accessed concurrently. This provides more data access throughput, which avoids causing the processor to idly wait for data accesses.

As depicted by <FIG>, in some implementations, the cache manager <NUM> interfaces between a client <NUM> (e.g., with the client requests <NUM>) and the storage abstraction layer <NUM>. In some examples, the client <NUM> communicates with the cache manager <NUM> through one or more remote procedure calls (RPC). Here, the communication is designated by the client request <NUM>. The request <NUM> may be a write request from the client <NUM> (or client device <NUM>) to write a block of client data <NUM> in RAM <NUM> of the memory host <NUM>. Additionally or alternatively, the request <NUM> may be a read request from the client <NUM> to read a block of client data <NUM> from the RAM <NUM> of the memory host <NUM> (e.g., a "get" or a retrieval function). In response to the client request <NUM>, the cache manager <NUM> is configured to determine whether to allow the client request <NUM>.

In some examples, a proxy receives the request <NUM> and determines whether to allow the request <NUM>. The proxy may be related to the cache manager <NUM> or independent of the cache manager <NUM>. One advantage of the proxy is that the proxy may function as a filter to determine whether to allow the request <NUM> via filter criteria (e.g., permissions, existence of data, availability of resources, etc.). When the proxy functions as a filter, the proxy may then forward the request <NUM> to memory hosts <NUM> of the distributed storage system <NUM> once the request <NUM> satisfies some or all filter criteria.

As depicted in <FIG>, the cache manager <NUM> may send a query <NUM> to the storage abstraction layer <NUM> to determine whether to allow the client request <NUM>. In some examples, the cache manager <NUM> determines whether to allow the client request <NUM> by determining at least the following: whether the client <NUM> has permission for the request <NUM>; whether the block of client data <NUM> exists at the storage abstraction layer <NUM> (e.g., currently saved at the memory host <NUM>); and whether spare memory is available at the storage abstraction layer <NUM>. <FIG> illustrates that the query <NUM> may be initiated by the client <NUM> asking the request <NUM> of whether free space (e.g., at memory) is available for corresponding client data <NUM>. When the query <NUM> results that the client <NUM> has permission for the request <NUM>, that the block of client data <NUM> is not currently saved within the storage abstraction layer <NUM>, and the spare storage resources <NUM> (e.g., spare RAM) are available at the storage abstraction layer <NUM> for the corresponding client data <NUM>, the cache manager <NUM> and/or storage abstraction layer <NUM> allows the request <NUM>. In some examples, by allowing the request <NUM>, the cache manager <NUM> writes the client data <NUM> to a free block <NUM>F of RAM. In other examples, by allowing the request <NUM>, the cache manager <NUM> reads the client data <NUM> from a storage location corresponding to where the client data <NUM> has been written. The cache manager <NUM> may write the client data <NUM> to a free block of RAM within a cache table <NUM>. <FIG>, for example, depicts the client data <NUM> with a dotted line within the cache table <NUM> to indicate the client data <NUM> written to or stored within for read access to the cache table <NUM>. The cache table <NUM> of the cache manager <NUM> is generally configured to correspond with available (i.e. free blocks <NUM>F of RAM) storage resources <NUM> within the storage abstraction layer <NUM>. In some examples, the query <NUM> by the cache manager <NUM> permits a memory host <NUM> of the storage abstraction layer <NUM> to decide whether to allow the client request <NUM>. Additionally or alternatively, the cache manager <NUM> may provide encryption and/or compression related to a request <NUM> (e.g., when writing to memory hosts <NUM> or when reading from memory hosts <NUM>). For example, a cache manager <NUM> implemented in silicon (e.g., part of a network switch) performs encryption and/or compression in real-time for a request <NUM>. In other examples, a cache manager <NUM> is configured to manage computational resources such that encryption and/or compression is optional or performed selectively.

<FIG> and <FIG> are examples of a cache manager <NUM>. In some implementations, the cache manager <NUM> includes a status indicator <NUM>, cache map(s) (e.g., a cache access map <NUM> and a cache address map <NUM>), and a cache table <NUM>. The cache manager <NUM> may be software, such as a program or a network service. For example, the cache manager <NUM> is a daemon available to all clients <NUM> related to the distributed storage system <NUM>. The cache manager <NUM> may be an out-of-process service shared between clients <NUM>. The distributed storage system <NUM> may include more than one cache manager <NUM>. With more than one cache manager <NUM>, each cache manager <NUM> may operate independently such that a first cache manager <NUM>, 200a does not communicate with a second cache manager <NUM>, 200b. Each cache manager <NUM> of the distributed storage system <NUM> includes a cache manager address <NUM> as a form of identification. The cache manager address <NUM> enables a first client <NUM>, 120a to communicate a means of identification for a cache manager <NUM> to a second client <NUM>, 120b. The cache manager address <NUM> may also allow a client <NUM> consistent placement of client data <NUM>, because the client <NUM> may consistently request a same cache manager <NUM> with a given cache manager address <NUM> to manage the client data <NUM>.

Each cache manager <NUM> includes the cache table <NUM> that corresponds to blocks of storage resources <NUM> (e.g., RAM) available at the storage abstraction layer <NUM>. In other words, the available storage resources <NUM> at the storage abstraction layer <NUM> include a number of free blocks <NUM>F of RAM. Each free block <NUM>F of RAM corresponds to an amount of spare RAM available at memory hosts <NUM> of the distributed storage system <NUM>. Based on the free blocks <NUM>F of RAM, the cache table <NUM> includes a queue <NUM>. As depicted in <FIG>, the queue <NUM> may include a leaf abstraction layer with a number "n" of leaves 304a-n. Each leaf <NUM> within the queue <NUM> may correspond to a set size of data storage controlled by the cache manager <NUM>. The number of leaves "n" within a queue <NUM> of the cache table <NUM> depends on the amount of spare RAM available at memory hosts <NUM>. In other examples, the queue <NUM> of the cache manager <NUM> includes blocks 310a-n. <FIG> is one such example where an operating system maps RAM to address space without a leaf abstraction layer. In this regard, <FIG> and <FIG> may function similarly except that indicators, identifiers, and/or addresses may refer to leaves (e.g., generally designated with a "A" subscript) or blocks (e.g., generally designated with a "B" subscript).

In some examples, the cache manager <NUM> facilitates the cache table <NUM> by the status indicator <NUM> and the cache maps <NUM>, <NUM>. Each cache map <NUM>, <NUM> may be an array having a length proportional to a number of identifiers ("ID") (e.g., leaf IDs <NUM>A and block IDs <NUM>B). Referring to examples <FIG> and <FIG>, the cache access map <NUM> is configured to map a permission key <NUM>, such as a spinlock, to an ID <NUM>. The ID <NUM> is an assigned identifier (e.g., uniform resource identifier (URI), uniform resource locator (URL), and/or uniform resource name (URN)) for a leaf <NUM> or a block <NUM> within the cache table <NUM>. For each cache manager <NUM>, the IDs <NUM> may be a range of values, such as numbers, letters, or alphanumerics, assigned to identify each leaf <NUM> (or block <NUM>) within the cache manager <NUM>. As a basic example, the leaf ID <NUM>A ranges from <NUM> to a maximum leaf ID. The leaf ID <NUM>A may be programmed for a custom range or a range that dynamically relates to the available storage resources <NUM> of the distributed storage system <NUM>. In some implementations, an ID <NUM> within a range of IDs <NUM> is reserved to indicate that a storage location (e.g., a leaf <NUM> or a block <NUM>) with a particular ID <NUM> does not exist. In other words, when a client <NUM> references a leaf ID <NUM>A, the cache manager <NUM> may indicate that the referenced leaf ID <NUM>A does not exist (e.g., returns "DNE").

As depicted in <FIG> and <FIG>, each ID <NUM> may be paired with a corresponding permission key <NUM>. The corresponding permission key <NUM> generally enables shared resources, such as data within a cache manager <NUM>, to be accessed (e.g., by multiple clients <NUM> to be read) and to be shared without changing the resource itself (e.g., writing to the resource). This may be an advantage for an out-of-process cache manager <NUM>. For example, the permission key <NUM> is configured to protect writes to the ID <NUM> to address mapping. In some examples, each permission key <NUM> is a spinlock, such as a cooperative reader/writer spinlock. For example, the permission key <NUM> corresponding to a leaf ID <NUM>A mapped to a leaf address <NUM>A that corresponds to a leaf <NUM> may restrict more than one client <NUM> to write to blocks <NUM> within the leaf <NUM> without first acquiring the permission key <NUM> of the leaf <NUM>. In some implementations, when the client data <NUM> exists within a leaf <NUM>, the request <NUM> for writing the client data <NUM> includes the permission key <NUM> corresponding to the client data <NUM>. An inherent advantage of this permission key <NUM> is therefore protecting the client data <NUM> within a leaf <NUM>. In some examples, such as a spinlock, when the client <NUM> acquires the permission key <NUM>, the client <NUM> must release the permission key <NUM> after utilizing the corresponding resource (e.g., the leaf <NUM>, a block <NUM> of the leaf <NUM>, or the client data <NUM> within the leaf <NUM>). Otherwise, in these examples, other clients <NUM> can be locked out of the leaf <NUM> corresponding to the permission key <NUM>. In some configurations, the permission key <NUM> is a hash that functions as a client data identifier. For example, a hash function with a hash value (e.g., <NUM> bits) prevents one client from storing client data <NUM> within an occupied block of the cache table <NUM> without the same hash corresponding to the client data <NUM> in the occupied block.

In some examples, the cache address map <NUM> maps the ID <NUM> (e.g., explained above) to an address <NUM>. The address <NUM> may be any address assigned as a storage location or reference location for a given leaf <NUM> (e.g., URI, URL, or URN). The cache address map <NUM> maps, for each leaf <NUM> of the cache table <NUM>, a leaf address <NUM>A to a leaf ID <NUM>A. In addition to the permission key <NUM>, the client <NUM> and/or cache manager <NUM> may validate (e.g., lookup) that the cache address map <NUM> includes a valid address <NUM> from the corresponding ID <NUM>. In some examples, this validation step according to the cache address map <NUM> permits the client <NUM> to reference data (e.g., client data <NUM>) within the leaf <NUM> or block <NUM>.

In some configurations, the status indicator <NUM> tracks management of storage resources related to the cache table <NUM>. In these configurations, the cache manager <NUM> is configured to provide information for each leaf <NUM> or block <NUM>, such as a permission key <NUM>, an ID <NUM>, and an address <NUM>. The status indicator <NUM> may indicate to the client <NUM> that interacts with the cache manager <NUM>, unassigned IDs <NUM> (i.e. free leaf IDs) of the range of IDs <NUM> along with IDs <NUM> that have been assigned, but are no longer storing data (i.e. empty IDs). In this respect, the status indicator <NUM> may help the client <NUM> decide which cache manager <NUM> to request by understanding a load of each cache manager <NUM>. Additionally or alternatively, the status indicator <NUM> may enable the cache manager <NUM> to update, to allocate, or to deallocate data and leaf information within the cache manager <NUM>.

<FIG> are examples of a leaf <NUM> within the cache table <NUM> of the cache manager <NUM>. As discussed above, the leaf <NUM> is allocated by the cache manager <NUM> based on the free blocks <NUM>F of RAM available within the distributed storage system <NUM>. In other words, the number "n" of leaves 304a-n depends of the available storage resources <NUM>. Accordingly, the cache manager <NUM> may allocate more leaves <NUM> within the cache table <NUM> when the amount of spare RAM within the memory hosts <NUM> increases. Similarly, when the computing processing increases, the cache manager <NUM> may deallocate (e.g., remove and delete) leaves <NUM> within the cache table <NUM> because the amount of spare RAM within the memory hosts <NUM> has decreased to compensate for the computing processing increases. As depicted in this example, each leaf <NUM> includes leaf information, such as a leaf ID <NUM>A and a leaf address <NUM>. Each leaf <NUM> may further include storage blocks <NUM> of variable size less than a set size of the leaf <NUM>. In some examples, the size of the leaf <NUM> is a uniform size (e.g., <NUM> MiB long) or a multiple of the uniform size. In other examples, the cache manager <NUM> is programmed to allocate leaves 304a-n of any size depending on design parameters (e.g., a desired headroom, the threshold amount Fthresh, and/or the at least one free block <NUM>F). Generally, the leaf <NUM> may be free (i.e. an empty leaf) or occupied with data (e.g., the client data <NUM>) allocated by the cache manager <NUM>. In some examples, when occupied with data, the leaf <NUM> includes storage blocks <NUM>. In some implementations, the number of blocks <NUM> and the size (e.g., number of chunks) of each block <NUM> depends on the allocation of client data <NUM> by the cache manager <NUM>. In other implementations, such as <FIG>, each block <NUM> is a designated uniform size (e.g., uniform number of chunks). In some examples, each block <NUM> is a multiple of the designated uniform size. As the use of storage resources <NUM> within the storage abstraction layer <NUM> is fluid, previously allocated and occupied blocks 310ao-nO within the leaf <NUM> may become free blocks 310aF-nF. For example, <FIG> illustrates five free cache blocks <NUM>F, 310aF-eF of varying sizes and five occupied blocks <NUM>o, <NUM>0ao-eO of varying sizes.

Each occupied block 310o within the leaf <NUM> may include block metadata <NUM>, a block metadata key <NUM>, and a block metadata hash set <NUM> as shown in examples <FIG>. When the cache manager <NUM> allocates client data <NUM> to a free cache block <NUM>F within the leaf <NUM>, the cache manager <NUM> may map client metadata <NUM> associated with the client data <NUM> to the block metadata <NUM>. Some examples of block metadata <NUM> include a hash, a leaf ID <NUM>A, a leaf offset, a length, a priority P (e.g., high priority Phigh, low priority Plow), a time to live (TTL), and read permissions. In some examples, the cache manager <NUM> maps metadata associated with the client data <NUM> to the block metadata <NUM> with the block metadata hash set <NUM>. The metadata associated with the client data <NUM> may be client information, such as who the client is or other sourcing information. Generally, the block metadata hash set <NUM> is a hash map such as a standard hash table.

Additionally or alternatively, client metadata <NUM> and/or corresponding block metadata <NUM> may be modified by a request <NUM>, such as a write request. Some examples of these modifications are that the client <NUM> modifies the priority P or time to live TTL of the client data <NUM> (e.g., after an initial write request for the client data <NUM>). In other words, the client <NUM> may change the priority P of the client data <NUM> from a high priority Phigh to a low priority Plow. In some examples, the client <NUM> defines client metadata <NUM> related to client data <NUM> at a time of a request <NUM> (e.g., initial request with the cache manager <NUM>). In other examples, the client <NUM> opts to identify and/or modify the client metadata <NUM> based on requests <NUM> related to the client data <NUM> (e.g., requests <NUM> for the client data <NUM>). Here, a client <NUM> identifies a number of requests <NUM> related to the client data <NUM> and may modify the time of life TTL or priority P. This may allow clients <NUM> to update and to prioritize client data <NUM> according to request activity. For example, a client <NUM> later realizes that a resource related to the client data <NUM> is more important (e.g., subject to more requests <NUM>) or less important (e.g., subject to less requests <NUM>). Additionally or alternatively, the cache manager <NUM> is configured to modify block metadata <NUM> corresponding to client metadata <NUM> based requests <NUM>. When the cache manager <NUM> modifies or determines various block metadata <NUM>, the cache manager <NUM> may operate independent of further input from the client <NUM> regarding the client data <NUM>. Moreover, modification generally has an advantage that it may permit the related block metadata <NUM> to be dynamic and/or potentially prevent the cache manager <NUM> from deleting or removing client data <NUM> that increases in value.

As a form of protection, the block metadata key <NUM> is configured to guard the block metadata <NUM> and/or the corresponding block metadata hash set <NUM> to ensure thread safety. The block metadata key <NUM> may operate similar to the permission key <NUM> such that a unique name or ID is obtained by the client <NUM> to lock the block metadata <NUM> from other threads while the block metadata <NUM> in use (e.g., being written and/or read). One such example of a block metadata key <NUM> is a mutex.

Referring to <FIG>, the cache manager <NUM> is configured to write the client data <NUM> with the client data hash <NUM> and client metadata <NUM> to the free cache block <NUM>F, 310aF upon request <NUM> of the client <NUM>. Here, once allocated, the free cache block <NUM>F, 310aF becomes an occupied block 310o with block metadata <NUM> corresponding to client metadata <NUM> of the allocated client data <NUM>. In some examples, such as <FIG>, the cache manager <NUM> further includes a cache validator <NUM>. After the client <NUM> and/or the cache manager <NUM> writes the block of client data <NUM> to generate the occupied block 310cO, the cache validator <NUM> is configured to validate the client metadata <NUM> and/or the client data hash <NUM> with the block metadata <NUM>. Although any block metadata <NUM> may be validated by the cache validator <NUM> against the client metadata <NUM> and/or client data hash <NUM>, one such example entails the cache validator <NUM> validating the client metadata <NUM> based on a length of the client data <NUM>. In some examples, the cache validator <NUM> is configured to approve the request <NUM> (e.g., write request or read request) based on the validation of metadata discussed above as shown in <FIG>.

<FIG> are examples where the cache manager <NUM> further includes a cache allocator <NUM> and/or a cache deallocator <NUM>. In some examples, the cache manager <NUM> is configured to determine the amount of spare RAM available on the memory host <NUM>. The cache manager <NUM> may be configured to independently determine the amount of spare RAM or utilize a thread (e.g., from operating systems of the distributed storage system <NUM>) that checks a level of free memory <NUM>F within the storage abstraction layer <NUM>. In either configuration, the cache manager <NUM> may use a status request <NUM> to determine the amount of spare RAM (e.g., the number of free blocks <NUM>F of RAM). The status request <NUM> may occur at a set frequency (e.g., <NUM>), periodically, or according to triggering functions, such as cache manager functions or processing functions of the distributed storage system <NUM>. For example, as an extreme case, the status request <NUM> is triggered by an out of memory kill process.

<FIG>, <FIG>, and <FIG> are basic examples of the functionality of the cache manager <NUM>. In the examples of <FIG>, <FIG>, and <FIG>, the storage abstraction layer <NUM> includes three memory hosts <NUM> with memory <NUM>. Each memory <NUM> includes blocks (e.g., chunks) of RAM that, for simplicity, are either free blocks <NUM>F of RAM contributing to the amount of spare RAM or occupied blocks 114o tied to processes of the distributed storage system <NUM>. With the status request <NUM>, the cache manager <NUM> determines whether the amount of spare RAM (e.g., free blocks <NUM>F of RAM) satisfies a threshold amount Fthresh. When the amount of spare RAM <NUM>F satisfies the threshold amount Fthresh, the cache manager <NUM> allocates at least one free block <NUM>F of RAM to the cache queue <NUM> of the cache table <NUM>. Optionally, the cache manager <NUM> also determines whether at least one free block <NUM>F of RAM has been allocated by the cache allocator <NUM> to the cache queue <NUM> of the cache manager <NUM>. In some examples, the threshold amount Fthresh corresponds to a predetermined amount of headroom within for the storage resources <NUM> of distributed storage system <NUM>. The predetermined amount of headroom may correspond to a size of the distributed storage system <NUM> and/or typical processing requirements (e.g., workload) of the distributed storage system <NUM>. Additionally or alternatively, the threshold amount Fthresh accounts for a size of the at least one free block <NUM>F. For example, the threshold amount Fthresh includes the predetermined amount of headroom along with the size of the at least one free block <NUM>F to be allocated. In this example, accounting for the allocation of the at least one free block <NUM>F by the cache manager <NUM> ensures that the cache manager <NUM> does not subsequently deallocate the at least one free block <NUM>F.

<FIG> is an example of when the cache manager <NUM> determines the amount of free blocks <NUM>F of RAM satisfies a threshold amount Fthresh. Here, each of the memory hosts <NUM> have about a third of their RAM to spare as shown by nine of eighteen total blocks <NUM> of RAM as free blocks <NUM>F of RAM. A dotted box throughout <FIG> may indicate that a selection within processes of the cache manager <NUM>. As indicated in <FIG>, the cache manager <NUM>, based on the determination that the amount of free blocks <NUM>F of RAM satisfies a threshold amount Fthresh, allocates data to the cache queue <NUM> of the cache table <NUM> by the cache allocator process of <FIG>.

<FIG> is an example of the process of cache allocation by the cache allocator <NUM> of the cache manager <NUM>. In these examples, the cache allocator <NUM> preserves physical memory within the storage resources <NUM> of the distributed storage system <NUM> as indicated by the free blocks <NUM>F of RAM transforming to cache blocks 114c. The cache allocator <NUM> is also configured to generate a leaf <NUM> within the cache queue <NUM> of the cache table <NUM> based on the at least one free block <NUM>F of RAM. As shown in the example <FIG> the cache allocator <NUM> generates the leaf 304n. In some examples cache allocator <NUM> uses a mmap operating system call to allocate at least one free block <NUM>F of RAM to the cache table <NUM>.

<FIG> is similar to <FIG> except that when the cache manager <NUM> determines whether the amount of free blocks <NUM>F of RAM satisfies the threshold amount Fthresh, the amount of free blocks <NUM>F of RAM actually equals the threshold amount Fthresh. In this case, the cache manager <NUM> does not allocate free space to the cache table <NUM>. Rather, the cache manager <NUM> here maintains status quo. The cache manager <NUM> maintains status quo because the cache manager <NUM>, after determining that the amount of free blocks <NUM>F of RAM does not satisfy the threshold amount Fthresh, inquires whether the amount of free blocks <NUM>F of RAM is less than the threshold amount Fthresh. When this inquiry is false (e.g., indicated as "NO") the cache manager <NUM> ends the status request process.

<FIG> is similar to <FIG> except that when the cache manager <NUM> determines whether the amount of free blocks <NUM>F of RAM satisfies the threshold amount Fthresh, the amount of free blocks <NUM>F of RAM fails to satisfy the threshold amount Fthresh. In this case, the cache manager <NUM> does not allocate free space to the cache table <NUM>. After determining the amount of free blocks <NUM>F of RAM does not satisfy the threshold amount Fthresh, the cache manager <NUM> may additionally inquire whether the amount of free blocks <NUM>F of RAM is less than the threshold amount Fthresh When this inquiry is true (e.g., indicated as "YES") the cache manager <NUM> begins a deallocation process <NUM> with the cache deallocator <NUM> as shown in <FIG>. As an example, the cache manager <NUM> may remove, deallocate, or delete a storage resource <NUM> within the cache table <NUM> in order for that storage resource <NUM> to be utilized elsewhere in the distributed storage system <NUM> (e.g., the host memory <NUM> requires additional computing and storage resources <NUM>, <NUM> to operate a process).

As illustrated by <FIG>, the deallocation process <NUM> may include several options as indicated by each branch 262a-c of the deallocation process <NUM> within the cache deallocator <NUM>. <FIG> indicates removal, deallocation, or deletion of a storage resource within the cache table <NUM> by indication of an "X" through the resource. The deallocation process <NUM> may also trigger a cache updater <NUM> of the cache manager <NUM> to update information related to the cache manager <NUM> due to removal, deallocation, or deletion of a storage resource within the cache table <NUM>. In other examples, the cache updater <NUM> is be configured to operate simultaneous to the cache deallocator <NUM> and/or periodically scan the cache table <NUM> of the cache manager <NUM> for changes.

In some examples, when the amount of spare RAM (e.g., free blocks <NUM>F) fails to satisfy the threshold amount Fthresh, the cache deallocator <NUM> deallocates at least one free block <NUM>F of RAM that has been allocated to the cache table <NUM>. In some implementations, the cache dealloactor <NUM> releases any portion of at least one free block <NUM>F of RAM between an end of the client data <NUM> and an end of the at least one free block <NUM>F of RAM. This may occur by freeing an allocation on a heap while still retaining it as owner for another process. As shown by branch 262a, the cache deallocator <NUM> in this circumstance may simply remove a free block cache <NUM>F within a leaf <NUM>. This option 262a may arise, for example, when the difference from failure to satisfy the threshold amount Fthresh is marginal and proportional to a free cache block <NUM>F within the cache table <NUM> rather than an entire leaf <NUM> or more. In this example, the cache updater <NUM> updates the block metadata <NUM> and the block metadata hash set <NUM> based on the removal of the free cache block <NUM>F within the leaf <NUM>.

Similar to option 262a to deallocate a free cache block <NUM>F of the cache table <NUM>, option 262b deallocates at least one occupied block 310o within the cache table <NUM> according to priority. The priority P (e.g. the retention priority) is generally stored in block metadata <NUM>. In some examples, the block metadata <NUM> corresponds to the client metadata <NUM>. Although the priority P may be a more complicated indication, for the ease of illustration, <FIG> depicts the priority as a basic low priority Plow and high priority Phigh. At branch 262b of the deallocation process <NUM>, before deallocation, the leaf <NUM> includes a first occupied block <NUM>O1 with low priority Plow and a second occupied block <NUM>O2 with high priority Phigh. When the amount of spare RAM fails to satisfy the threshold amount Fthresh, the cache deallocator <NUM> may remove at least one block of client data <NUM> stored within an occupied block 310o according to priority. Here, the cache deallocator <NUM> removes the first occupied block <NUM>O1 of low priority Plow. In some implementations, the order of priority regarding the deletion of a block <NUM> is as follows: first, expired low priority client data <NUM>, Plow; second, expired high priority client data <NUM>, Phigh; third, unexpired low priority client data <NUM>, Plow; and fourth, unexpired high priority client data <NUM>, Phigh. In some examples, the cache deallocator <NUM> removes blocks <NUM> of data from the cache table <NUM> following this priority process until the amount of spare RAM satisfies the threshold amount Fthresh. Much like branch 262a, the cache updater <NUM> updates the block metadata <NUM> and the block metadata hash set <NUM> based on the removal of the occupied block 310o within the leaf <NUM>.

In some examples, deletion or removal of client data <NUM> stored within an occupied block 310o relates to the time of life TTL of the block metadata <NUM>. For example, the cache manager <NUM> or the client <NUM> identifies the time of life TTL corresponding to when the client data <NUM> expires (e.g., temporary client data). The cache deallocator <NUM> may therefore prioritize the removal or the deletion of expired client data <NUM>. In some examples where the cache deallocator <NUM> must remove unexpired client data <NUM>, the cache deallocator <NUM> is configured to prioritize client data <NUM> by the client metadata <NUM> (e.g., time of life TTL or priority P) such that client data <NUM> that will expire sooner has a greater likelihood of being deleted or removed than client data <NUM> identified to expire later. In some examples, the cache manager <NUM> is configured to determine removal and/deletion based on multiple variables of block metadata <NUM> and/or client metadata <NUM> (e.g., not solely time of life TTL or priority P). This may be particularly helpful when the client <NUM> may change the client metadata <NUM> and may therefore biasedly protect its own client data <NUM> within the distributed storage system <NUM>.

The third branch 262c of the deallocation process <NUM> entails the cache deallocator <NUM>, in order to satisfy the threshold amount Fthresh, optionally removing an entire leaf <NUM>. In some implementations, the cache deallocator <NUM> removes the entire leaf <NUM> only when the amount of spare RAM indicates such and/or after the cache deallocator <NUM> determines the removal of a cache block(s) <NUM> is insufficient. For example, the demands of the computing processing suddenly ramp up and indicate massive data removal at the cache table <NUM>. In examples where the cache deallocator <NUM> removes an entire leaf <NUM>, the cache updater <NUM> updates block metadata <NUM>, block metadata hash set <NUM> and leaf information, such as information related to the status indicator <NUM>, and the cache maps <NUM>, <NUM>.

In some examples for leaf <NUM> removal, the cache deallocator <NUM> also determines leaves 304a-n eligible for deallocation. Examples of factors affecting leaf eligibility for deallocation are the age of stored data within a leaf <NUM>, the amount of free cache blocks <NUM>F within a leaf <NUM>, current use of a leaf <NUM> (e.g., permission key <NUM> in use), etc. Additionally or alternatively, the deallocation of a leaf <NUM> may be considered a write request <NUM> that requires acquisition of a permission key <NUM> associated with the leaf <NUM> to be deallocated. Here, when the permission key <NUM> is acquired, the cache deallocator <NUM> releases the memory <NUM> associated with the leaf <NUM> (e.g., with a munmap operating system call) and also may release the permission key <NUM> (e.g., for a spinlock).

<FIG> illustrates some non-exhaustive updates the cache updater <NUM> undertakes to maintain the cache manager <NUM>. In some implementations, the cache updater <NUM> updates and/or maintains the cache manager <NUM> based on a change to the cache manager <NUM>, but in other implementations, the cache updater <NUM> periodically maintains the cache manager <NUM> by scanning each leaf <NUM> and associated blocks <NUM> within the cache table <NUM>. This periodic scanning is a type of garbage collection process. The garbage collection process of the cache manager <NUM> may scan the block metadata hash set <NUM> and remove expired blocks <NUM> from the corresponding hash table. In addition to removing expired blocks <NUM>, the garbage process may also remove block metadata <NUM> associated with leaves 304a-n that no longer exist within the cache table <NUM> and/or release empty leaf IDs <NUM>A into the free leaf ID pool. For example, the garbage collection process communicates with the status indicator <NUM> to categorize empty leaf IDs as free leaf IDs.

<FIG> is an example of more than one client interacting within the distributed storage system <NUM>. In some examples, a first client <NUM>, 120a sends more than one request <NUM> to more than one cache manager <NUM>. An advantage of interacting with more than one cache manager <NUM>, such as storing client data <NUM> in more than one cache manager <NUM>, is that the client <NUM> may have redundancies for when data gets removed (e.g., deallocated) by the cache manager <NUM>. Clients <NUM> are generally aware that client data <NUM> is being stored in a potentially unreliable medium, a cache, and therefore, the client <NUM> may make trade-offs between replication and ease of access. In some implementations, the cache manager <NUM> is configured to determine priorities of stored client data <NUM> because the priority may indicate a likelihood of data replication. For example, high priority Phigh client data <NUM> results in more replications of the client data <NUM> across multiple memory hosts <NUM> as compared to low priority Plow client data <NUM>. Additionally or alternatively, the first client <NUM>, 120a may send requests <NUM> to several cache managers <NUM> to determine which cache manager <NUM> is least utilized. In this example, a less utilized cache manager <NUM> is unlikely, in several circumstances, to deallocate the client data <NUM> related to the request <NUM>.

Referring further to <FIG>, the first client <NUM>, 120a sends two requests <NUM>, 122a<NUM>-<NUM> to a first cache manager <NUM>, 200a and a second cache manager <NUM>, 200b. In this example, the first client <NUM>, 120a sends two write requests <NUM>, 122a<NUM>-<NUM>. The first client <NUM>, 120a also sends client data <NUM> (i.e. "block A") along with a corresponding client data hash <NUM> (shown as hash 'B'). Here, each cache manager <NUM>, 200a-b has allowed the first client <NUM>, 120a to write to corresponding caches <NUM>, 300a-b of each cache manager <NUM>, 200a-b. Each cache manager <NUM>, 200a-b updates the hash map (e.g., the block metadata hash set <NUM>) for the client data hash <NUM> associated with the client data <NUM>. As an out-of-process system, the first client <NUM>, 120a stores information regarding the data transaction, such as the respective client data hash <NUM> along with the cache manager address <NUM> and may propagate this transaction information as the client <NUM> sees fit. Here, the first client <NUM>, 120a shares the client data hash <NUM> (i.e. "hash B") and the cache manager addresses <NUM>, 204a-b with a second client <NUM>, 120b. In this example, the second client <NUM>, 120b communicates a request <NUM>, 122b to read the client data hash <NUM> (e.g., get 'B') from the second cache manager <NUM>, 200b. <FIG> depicts that as a result of that read request <NUM>, 122b, the second client <NUM>, 120b receives as a return, "block A. " In other words, the second manager <NUM>, 200b maps the communicated client data hash <NUM> (e.g., 'B') with the block metadata hash set <NUM> to identify a storage location or address associated with the client data hash <NUM> (e.g., occupied block <NUM>O, 310bO. Furthermore, although <FIG> depicts two clients <NUM>, 120a-b and two cache managers <NUM>, 200a-b, this cache manager <NUM> is scalable such that the distributed storage system <NUM> includes multiple clients <NUM>, cache managers <NUM>, and potential cache resources.

In some implementations, the client <NUM> decides which cache manager <NUM> to request (e.g., read/write request) based on a location and/or proximity of the cache manager <NUM>. For example, the second client <NUM>, 120b chose to send a read request <NUM>, 122b for the client data <NUM> because the second cache manager <NUM>, 200b has a location of Detroit, Michigan, which is relatively close to a location of the second client <NUM>, 120b, Grand Rapids, MI. Similarly, the first client <NUM>, 120a may have chosen to write the client data <NUM> to the first cache manager <NUM>, 200a and the second cache manager <NUM>, 200b because of proximity to the cache managers <NUM>, 200a-b. An advantage of proximity to cache managers <NUM> and/or memory hosts <NUM> is that the proximity may reduce data access latency and computational resources associated with access latency.

<FIG> and <FIG> illustrate more detailed examples of when the cache manager <NUM> determines the amount of spare RAM (designated as "capacity"). <FIG> is an example where the cache manager <NUM> determines the amount of space RAM with respect to at least one free block <NUM>F in addition to the threshold amount Fthresh; whereas <FIG> is an example where the threshold amount Fthresh includes the at least one free block <NUM>F. There are different advantages to each of these configurations. Referring to the examples of <FIG> and <FIG>, the cache manager <NUM> determines the capacity for five different requests <NUM>(<NUM>-<NUM>). Each request <NUM> corresponds to a capacity that may trigger the cache manager <NUM> to perform different functions based on the determination of spare RAM (i.e. capacity).

Referring further to <FIG>, at the first request <NUM><NUM>, the cache manager <NUM> determines that the capacity exceeds the threshold amount Fthresh in addition to the at least one free block <NUM>F. In this circumstance, the cache manager <NUM> may allocate at least one free block <NUM>F of RAM. At the second request <NUM><NUM>, the cache manager <NUM> determines that the capacity exceeds the threshold amount Fthresh, but, in excess of the threshold amount Fthresh, equals the at least one free block <NUM>F. Here the cache manager <NUM> may not allocate at least one free block <NUM>F of RAM and/or may monitor the capacity of allocated blocks <NUM> (or leaves <NUM>) in the queue <NUM>. At the third request <NUM><NUM>, the cache manager <NUM> determines that the capacity exceeds the threshold amount Fthresh, but is less than the at least one free block <NUM>F. In this instance, similar to the second request <NUM><NUM>, the cache manager <NUM> may not allocate a free block <NUM>F of RAM and/or may monitor the capacity of allocated blocks <NUM> (or leaves <NUM>) in the queue <NUM> to determine if the capacity later also exceeds the at least one block <NUM>F or later falls below the threshold amount Fthresh. In some examples where the capacity exceeds the threshold amount Fthresh, but is less than the at least one free block <NUM>F, the cache manager <NUM> is configured to perform alternative functions such as reducing a size of the at least one block <NUM>F for allocation based on the amount exceeding the threshold amount Fthresh. At a fourth and a fifth request <NUM><NUM>, <NUM>, the cache manager <NUM> determines that the capacity is less than the threshold amount Fthresh and, compared to the third request <NUM><NUM>, may additionally deallocate free block(s) <NUM>F and remove client data <NUM>. The fourth request <NUM><NUM>, more specifically represents that when the cache manager <NUM> determines a capacity equal to the threshold amount Fthresh the cache manager <NUM> may only deallocate free block(s) <NUM>F but not remove client data <NUM> at this time.

<FIG> is similar to <FIG> except that the cache manager <NUM> has less granularity to distinguish between both the free block <NUM>F and the threshold amount Fthresh. For example, in the third, fourth and fifth requests <NUM><NUM>-<NUM>, the cache manager <NUM> of <FIG> can only distinguish that the capacity is less than the threshold amount Fthresh rather than also determine if there is capacity in excess of the headroom, but less than and/or equal to the at least one block <NUM>F Depending on a desired design or a desired computational complexity of the cache manager <NUM>, the cache manager <NUM> may have some functional advantages with increased granularity (e.g., <FIG>) or with less granularity (<FIG>). For example, less granularity increases the potential computing speed of the cache manager <NUM>.

<FIG> is an example method <NUM> of operating an in-memory distributed cache. At 702a, the method <NUM> includes receiving a write request <NUM> from a client device <NUM> to write a block of client data <NUM> in RAM of the memory host <NUM>. At 702b, the method <NUM> includes sending a write request <NUM> from a client device <NUM> to a memory host <NUM> of a distributed storage system <NUM>. At <NUM>, the method <NUM> further includes determining whether to allow the write request <NUM>. At 704a-d, the method also includes determining whether the client device <NUM> has permission to write the block f client data <NUM> at the memory host <NUM>; whether the block of client data <NUM> is currently saved at the memory host <NUM>; and whether a free block <NUM>F block of RAM is available. At <NUM>, the method <NUM> allows the write request <NUM> when the client device <NUM> has permission to write the block of client data <NUM>, the block of client data <NUM> is not currently saved, and a free block <NUM>F of RAM is available. At <NUM>, when the write request is allowed, the method <NUM> includes allowing the client <NUM> to write the block of client data <NUM> to the free block <NUM>F of RAM.

For example, it may be implemented as a standard server 800a or multiple times in a group of such servers 800a, as a laptop computer 800b, or as part of a rack server system 800c.

Claim 1:
A method (<NUM>) comprising:
receiving, at a memory host (<NUM>) of a distributed storage system (<NUM>), a write request (<NUM>) from a client device (<NUM>) to write a block of client data (<NUM>) in random access memory, RAM, (<NUM>) of the memory host (<NUM>);
determining by the memory host (<NUM>), whether to allow the write request (<NUM>) by:
determining whether the client device (<NUM>) has permission to write the block of client data (<NUM>) at the memory host (<NUM>);
determining whether the block of client data (<NUM>) is currently saved at the memory host (<NUM>); and
determining whether a free block of RAM (<NUM>) is available,
wherein when the client device (<NUM>) has permission to write the block of client data (<NUM>) at the memory host (<NUM>), the block of client data (<NUM>) is not currently saved at the memory host (<NUM>), and a free block of RAM (<NUM>) is available, the write request (<NUM>) is allowed; and
when the write request (<NUM>) is allowed, allowing, at the memory host (<NUM>), the client device (<NUM>) to write the block of client data (<NUM>) to the free block of RAM (<NUM>);
periodically determining, at the memory host (<NUM>), an amount of spare RAM (<NUM>) available on the memory host (<NUM>);
determining, at the memory host (<NUM>), whether the amount of spare RAM (<NUM>) satisfies a threshold amount comprising at least one free block of RAM (<NUM>); and
when the amount of spare RAM (<NUM>) satisfies the threshold amount, allocating, at the memory host (<NUM>), the at least one free block of RAM (<NUM>) to a free block queue (<NUM>), wherein determining whether a free block of RAM (<NUM>) is available comprises determining whether at least one free block of RAM (<NUM>) has been allocated to the free block queue (<NUM>); and characterized in that:
when the amount of spare RAM (<NUM>) fails to satisfy the threshold amount, selecting and deleting one or more blocks of client data (<NUM>) from the memory host (<NUM>), wherein a selection criterion includes a priority indicating a likelihood of data replication of the one or more blocks of client data (<NUM>) across multiple memory hosts of the distributed storage system (<NUM>), wherein a lower priority increases a likelihood of selection.