With the advent of cloud computing and emergence of big data, scale-out data caching systems are widely deployed and their horizontal scalability [1] becomes increasingly important. As an effective solution, consistent hashing [2] has been commonly used by key-value caching systems, e.g., Dynamo [3], Aerospike [4], Memcached [5], Redis [6]. Using consistent hashing, a large number of servers are organized together to form a cooperative cluster. These servers jointly provide a unified but distributed hash table to serve swift and voluminous data item requests. Once a data item is hashed to one of the hosting servers, most key-value caching systems use the least-recently-used (LRU) caching algorithm, or its variations, e.g., LRU Clock [7], to decide which data items should be kept in its own individual cache space. These data caching systems play a critical role in optimizing the way information is delivered in Web services.
With consistent hashing, the total amount of cache spaces in the cluster can be easily expanded (scaled horizontally) through the addition of new cache servers. However, these individual cache spaces on different servers are not simply This work was supported by the National Science Foundation under Grant No. 1717060. added together to achieve an overall request miss ratio. Although LRU caching on a single server has already been extensively studied, theoretically characterizing the miss ratio of a LRU cluster organized by consistent hashing still remains an unexplored problem. One difficulty in analysis is that the data item requests are shuffled to a large number of servers according to a random hash function. This random hashing complicates the system behavior. Due to the fundamental role and predominant usage in practice, LRU caching with consistent hashing merits a deep investigation.
Characterizing the cache miss behavior of a cluster in such a complex setting not only helps resource planning but also improves the way a cache cluster is organized. To this end, we derive the asymptotic miss ratio of a LRU caching cluster with consistent hashing under the independent reference model (IRM) [8]. Interestingly, these individual cache spaces on different servers, though isolated physically but logically connected through a hash function, can be effectively viewed as if they could be pooled together to form a single virtual LRU cache space. Interestingly, this virtual LRU cache has a equivalent cache size determined by the distribution of the random hash function. This equivalence can be established when the cache sizes of the individual servers are large. Our result provides a convenient abstraction that can rigorously relate the more complex LRU caching with consistent hashing to the relatively simpler single LRU cache. Based on this abstraction, many known results on a single LRU cache can be directly translated to a LRU cluster with consistent hashing. Specifically, we prove a characteristic time approximation, previously established for a single LRU cache, for a LRU cluster. Notably, the characteristic time approximation has the same form for almost all of the random hash functions. This result is not straightforward in view that the miss ratio of each of the server is a random variable conditional on the random hash function. However, the overall conditional asymptotic miss ratio of the cluster is always the same almost surely, depending on the probability distribution of the random hash function. Due to this equivalence, we comment that the engineering implications discussed in [9] for a single LRU cache can also be extended to a LRU cluster.
To put the analysis on a concrete basis, we first summarize the important features of consistent hashing and LRU caching.
1) Consistent hashing: Data items are usually organized in a key value pair, and the entire data are stored in the whole cluster as a distributed hash table according to keys. To Fig. 1: Illustration of consistent hashing scale out the system horizontally, each server is maintained independent, e.g., by using consistent hashing [2] to select a unique server for each key. The basic idea is to first hash the data items to a large number of partitions at random. These partitions form a ring, as illustrated in Fig. 1. The physical servers, with a total number that is much smaller than the number of partitions, are also hashed to a subset of the partitions. A data item, after being hashed to a partition, will be stored on the server that is closest in the clockwise direction to its associated partition. For example, partitions A, B and C are all stored on server S 1 in Fig. 1. Therefore, when the server locations are fixed, each server hosts a certain number of partitions that are determined by the hash function.
2) LRU caching: Each data item is hashed to one of the hosting servers. A cache replacement algorithm is needed to manage the cache space on an individual server. Due to the low cost of tracking access history, LRU caching algorithm has been widely used, e.g., for Memcached [5], [10]. A data item is added to the cache after a client has requested it and failed. When the cache is full, the LRU caching algorithm evicts a data item that has not been used for the longest time in order to accommodate the newly requested one.
(I) For a family H of hash functions under the Simple Uniform Hashing Assumption (SUHA) [11], we characterize the asymptotic miss ratio of data item requests on a cluster with consistent hashing. This asymptotic result, expressed as a conditional probability, holds almost surely for all random hash functions in H. It provides a new analytical framework to study LRU caching with consistent hashing by conditioning on the random hash function, which is an interesting feature that most existing asymptotic results do not have. (II) We rigorously establish a one-to-one equivalence between a cluster with consistent hashing and a single virtual LRU cache space with a proper size parametrized by the distribution of the random hash function. Conveniently, this equivalence translates the analytic results from the well-studied single server to the complex cluster with consistent hashing. Based on this equivalence, we prove the characteristic time approximation for a cluster to characterize the miss probability. (III) Extensive simulations show that our asymptotic results match with the empirical results accurately even for relatively small cache sizes.
Consistent hashing has gained much popularity in recent years due to the increasing demand of processing large data sets on a scale-out infrastructure. It has been successfully used in a number of real-world applications, e.g., web caches [12], [13], peer-to-peer networks [14] and distributed storage systems [15]. Most theoretical studies on consistent hashing focus on characterizing the randomized partitioning algorithms to balance data allocation [16], memory sharing [17] and perfect hashing [18]. These algorithms are usually analyzed under SUHA. Some works circumvent this assumption using realistic hash functions through simulations [19], [20]. However, none of these works investigate the miss probabilities of a cluster with consistent hashing.
There is a large body of work on the miss ratio of a single LRU server. Different methods have been proposed, e.g., approximation by iterative algorithms [21], mean field analysis [22] and the characteristic time approximation [23], [24]. To obtain insights, asymptotic results for Zipf's popularity distributions have been derived [25], [26], [27]. The characteristic time approximation is also a common approach, which has been shown to be accurate in practical applications [28], [29]. Its success has been supported by the analysis [30], [31]. Nevertheless, these results cannot be directly extended to a cluster with consistent hashing.
Although single LRU caches have been studied in depth, characterizing the miss behavior of cache networks with general topologies remains difficult. Instead, some existing works, e.g., [32], [33], focus on offline optimization problems (e.g., content placement) in cache networks. Some specially structured cache networks (e.g., tree or line networks) have been studied [34], [35] using a TTL-based eviction scheme. With consistent hashing, the cache network can be viewed as a one-hop network, which is the focus of this paper. II. MODEL DESCRIPTION Consider a cluster C with N servers {S 1 , S 2 , • • • , S N } organized by consistent hashing. Assume that the data item requests hosted on C can access an infinite number of distinct data items of unit size that are represented by a sequence
i , together with all requests that ask for d • i , are hashed to server m by the hash function H(•). Thus, a subsequence of data items, denoted by (d
To characterize the hash function H, we assume the Simple Uniform Hashing Assumption (SUHA) to facilitate the analysis. In practice, the ideal SUHA property is not feasible, and people resort to a (strongly) universal hash family [36] or a k-independent hash family [37] as approximations. Actually, it has been shown that 2-independent hash functions under mild conditions approximate truly random functions [38]. Specifically, we consider a family of hash functions H = {h w (•), w = 1, 2, • • • }. Assume that, with H chosen from H uniformly at random, each data item d • i , i = 1, 2, • • • is dispatched also uniformly at random to one of the partitions.
Note that although H(•) is random, it becomes one of the deterministic hash function h w (•) once the random selection is completed. Using consistent hashing, the involved servers store the data items from mutually exclusive subsets of the partitions, as shown in Fig. 1. Since the number of partitions assigned to each of the servers could be different, we can equivalently assume that each data item d • i is independently hashed to server S m , 1 ≤ m ≤ N with probability µ m by H(•). In other words, we have the following assumption.
Assume that the arrivals of the data item requests occur at time points {τ n , -∞ < n < +∞}. Let J n be the index of the server for the request at time τ n . The event {J n = m} represents that the request at time τ n is processed on server S m . Denote by R n the requested data item at time τ n . Thus, the event
on server S m . In order to compute the miss ratio when the system reaches stationarity, we consider the request at time τ 0 . It has been shown [26] that the miss ratio is equal to the probability that the data item requested by R 0 is not in the cache. For cluster C, define
Note that q (m) i
, i ≥ 1 is a random sequence determined by the random hash function H. We assume that the data items
. This is a typical distribution that has been empirically observed in web pages [39], contentcentric network [40], and video systems [41]. To simplify the analysis, this paper only considers a Zipf's distribution with α • > 1. For α • < 1, we can conduct a similar analysis based on existing results [42], [43], [44].
LRU is equivalent to the move-to-front (MTF) policy [26], [45], which sorts the data items in an increasing order of their last access time. When a data item is requested under MTF, it is moved to the first position of the list and all the other data items that were in front of this one increase their positions by one. Define C n to be the position of the data item requested by R n in the sorted list under MTF on the server that processes the request R n . Then, the miss probability of the requests on server S m with a cache size x m is given by P[C 0 > x m J 0 = m, H], which is conditional on the random hash function H and the event that R 0 occurs on server S m , i.e., J 0 = m. Combining the miss ratios of the servers, we obtain the overall miss probability of the cluster C, conditional on H ∈ H,
In the analysis, we assume
In this section, we first derive the miss ratio for each of the servers of the LRU cluster with consistent hashing conditional on the random hash function. Then, we show that these individual cache servers can be regarded as a single virtual LRU server with a proper cache size. This connection also proves the characteristic time approximation for a cluster.
We derive the miss probabilities for the servers of the cluster by conditioning on the random hash function H. Note that H uniquely determines W m , 1 ≤ m ≤ N . The gamma function is given by Γ
Theorem 1. Under the assumptions in Section II, we obtain, for all 1 ≤ m ≤ N , almost surely for all H, as x m → ∞,
which implies, almost surely for all H,
Proof. The proof is presented in Section VI-A.
This asymptotic result in (4) involves random variables W m , 1 ≤ m ≤ N that are determined by H. Interestingly, the overall asymptotic miss ratio of the whole cluster in (5) is independent of H since W m = 1/P[J 0 = m H]. These asymptotic results hold a.s. for all H. See Experiments in Section IV. If there is only one server in the cluster C, i.e., N = 1, Theorem 1 reproduces the results in [25], [26] for a Zipf's distribution, e.g., Theorem 3 of [26] on an asymptotic miss probability of a single LRU server. However, extending this result from a single server to a cluster is complicated. We discuss two main issues that cause the difficulty: 1) Theorem 3 of [26] assumes a deterministic popularity distribution on a server. This condition is not satisfied in our model due to the random hash function; 2) the proofs of [25], [26] cannot be used to prove the characteristic time approximation for a cluster. Because of these reasons, we use a different approach to derive the miss probability of a LRU cluster with consistent hashing, which also proves the characteristic time approximation for a cluster. Now, suppose that we have a single virtual LRU cache server of size x that serves the entire data item requests {R n }, which at the same time are also served on the cluster C. Based on Theorem 1, we establish an equivalence between the cluster C and the virtual LRU cache. Denote by P [C 0 > x ] the miss probability of the virtual LRU cache conditional on H. Recall that the server S m has a cache capacity x m = b m x.
Theorem 2. Under the assumptions in Section II, we obtain, almost surely for all H,
where
Proof. The proof is presented in Section VI-B.
This theorem shows that the miss probability on the cluster C is asymptotically equal to the miss ratio of a LRU server with the cache size given by (7). Interestingly, as illustrated in Experiment 2, this asymptotic equivalence is accurate even when the cache size of each individual server of cluster C is relatively small. Using this connection, existing results and insights that have been established for a single server seem to be also true for a LRU cluster with consistent hashing. This could be useful for resource planning and cluster optimization.
The characteristic time approximation [24] has been widely used in estimating the miss ratio of a LRU server. Based on Theorem 2, we derive the characteristic time approximation for a cluster.
Theorem 1 shows that, although the miss ratio of each server is random, determined by H, the overall asymptotic miss ratio of the cluster is independent of H. This interesting result motivates us to define the characteristic time approximation for the cluster C as
where x is given by ( 7) and t C is the unique solution of the equation
Theorem 3. Under the assumptions of Theorem 2, we have, almost surely for all H,
Proof. The proof is presented in Section VI-C.
In this section, we conduct extensive simulations using C++ to verify the main results in Section III. Notably, all simulations match with our theoretical results even for relatively small cache sizes.
Experiment 1. This experiment verifies Theorem 1. Consider a cluster of 100 heterogeneous servers {S 1 , S 2 , • • • , S 100 } that have distinct cache sizes and different hashing probabilities. The server S m , 1 ≤ m ≤ 100 has a cache capacity x m = (1 + 0.1z m ) x with z m selected uniformly at random from [-0.5, 0.5]. Thus, x is the average cache size across all of the servers. Recall that µ m is the probability that a data item is hashed to server S m . Let µ m =
Set the total number of data items M = 10 7 , and the popularity distribution
For each x ∈ {40, 60, 80, 100, 120, 140, 160, 180, 200}, we first simulate 10 8 requests to ensure that the entire system reaches stationary, and then 10 9 more requests to compute the empirical miss probabilities of the cluster C and the individual servers. To verify (4), we need to show that it holds for all 1 ≤ m ≤ 100. To visualize the results, we only plot the miss probabilities of five servers {S 11 , S 30 , S 61 , S 71 , S 96 } in Fig. 2. The empirical results match well with the the theoretical results by (4) and (5) even when x is small. Experiment 2. This experiment verifies the equivalence between the cluster C and a virtual LRU cache described in Theorem 2, by using the same setting as in Experiment 1. We Fig. 3: [Left] Miss ratios of the cluster C, a virtual LRU cache and the characteristic time approximation. [Right] The probability to hash a request to server S m conditional on H demonstrate the accuracy of the characteristic time approximationin, which also verifies Theorem 3. By computing (7), we obtain the equivalent size of the virtual LRU caching space x = 91.1784x. For the characteristic time approximation of the cluster C, we use a binary search to find the solution t C of the equation ∞ i=1 (1-e -q • i t C ) = 91.1784x and then calculate the miss probability by (8). It can be shown from the left figure in Fig. 3 that the empirical results match well with the theoretical results for the miss probabilities of the virtual LRU caching server and the cluster C even for x = 40. In addition, the characteristic time approximation (8) provides an accurate estimation of the miss ratio of the cluster C. Experiment 3. This experiment moves beyond the assumptions of this paper and considers a realistic setting. Thus, we cannot explicitly compute the equivalent virtual cache size by Theorem 2. However, we still demonstrate an equivalence between the cluster C and a virtual cache. We set α • = 0.8 and use a 2-independent hash function [38]. For a cluster of 100 servers {S 1 , S 2 , • • • , S 100 } described in Experiment 1, we hash each server to one of 2000 partitions using the 2independent hash function h a,b (S i ) = N i = ((a × i + b) mod p) mod 2000, where a, b are chosen from {1, 2, • • • , p} uniformly at random with a large prime p = 15881. Using the same hash function, each data item d • i is hashed to one of these partitions. The data items from partition k are stored on the server that has an index arg min i {N i : N i ≥ k} if the set {i : N i ≥ k} = ∅ and arg min i {N i } otherwise. We set the total number of data items M = 10 4 , and the
For the virtual LRU caching space, we find the equivalent x = 70.0212x. It can be shown from Fig. 4 that the empirical miss ratios of the cluster C and the virtual LRU cache match very well.
Driven by the trend to scale out caching systems for processing big data, LRU caching with consistent hashing has been widely deployed. We develop a theoretical framework to investigate the miss ratio of a LRU cluster for a family of hash functions satisfying the Simple Uniform Hashing Assumption (SUHA). We derive a close-form asymptotic miss probability that holds almost surely for all of the random hash functions from this family. This result also establishs a oneto-one equivalence between a LRU cluster and a single virtual LRU server. provides a convenient abstraction to understand the LRU cluster using the insights obtained from a LRU server. Based on this connection, we also prove the characteristic approximation for a cluster with consistent hashing.
This section contains the proofs of our main theorems.
We rely on the following Lemma 1 to prove Theorem 1. To this end, we use Lemmas 5, 6 and 7 to study the three quantities in Lemma 1, i.e., q i /q i+1 , Φ(•) and T (x). Specifically, we first note that the variables I (m) k , k ≥ 1 can be regarded as the indices of data items on server S m and show that 1 ≤ q (m)
in Lemma 5. Then, we prove that the functional relationship
and q (m)
∞ and Borel-Cantelli lemma, we prove that Theorem 1 holds almost surely for all H ∈ H.
Lemma 1 is a direct consequence of Theorem 1 in [9]. Let the data item popularity distribution on a server be (q i , i ≥ 1). Consider the following functional relationship
Define an increasing function
with an inverse T ← (x). We say that f (x) g(x) as x → ∞ if lim sup x→∞ f (x)/g(x) ≤ 1; f (x) g(x) has a complementary definition.
Proof. The proof is based on Theorem 1 in [9]; see the technical report [46] for the details.
We introduce some necessary definitions. Define mutually independent Bernoulli random variables {X
, which represents the number of data items hashed to server S m from (d
. We quote the Bernstein's inequality in Lemma 2, and establish the following Lemma 3 to estimate Y (m) k , which will be used to estimate
Lemma 2 (Theorem 2.8 in [47]). For independent random variables
Lemma 3. There exist n 0 ∈ N + and c 0 > 0 such that for ∀ n > n 0 ,
Noting that E[(Z
Applying (12) for the random variable
and using ( 14) and ( 15), we have, there exist n i1 ∈ N + and v > 0 such that for ∀ n > n i1 ,
In the meanwhile, applying (12) for -Y
which, in conjunction with (16), implies, for n > n i1
Using (18) and a union bound, we obtain, for ∀n > n i1
There exist n i2 and c 0 > 0 such that ∞ n exp(-x 1/3 v)dx < c 0 /n 2 holds for n > n i2 . Using (19) and letting n 0 max{n i1 n i2 }, we finish the proof.
We establish the following lemma 4 to estimate q (m)
, which is used to estimate Φm (z) and the ratio q (m)
Proof. Define events B k {q (m)
Next, we will show that B k and C k are equivalent.
Since both q (m) i and q • i are non-increasing with respect to i, the event B k implies,
Moreover, based on the definition of
Combining ( 21) and ( 22) yields B k ⊆ C k . On the other side, the event
k and using a union bound, we obtain,
There exist a large integer n 1 and a constant c
which, in conjunction with (23), completes the proof.
We use the following Lemma 5 to estimate q (m)
The proof is straightforward by using Lemma 4. Lemma 5. For any q > 0, there exists n 2 > n 1 such that, for all n > n 2
where the constant c 1 is the same as in Lemma 4.
Proof. Define an event D k q (m)
k , and hence the complement
Using a similar approach to Lemma 4, we obtain
and for all n > n 1
which, togehter with (23), we obtain
which implies
Using q • k-k 1/2 +1 /q • k+ k 1/2 → 1, we finish the proof. Next, we establish the following lemma to estimate the functional relationship between
and q (m)
based on Lemma 3 and Lemma 4. Lemma 6. For p > 0, there exists n 3 > max{n 0 , n 1 } and c 2 > 0 such that, for all n > n 3 ,
where
Combining (20) and (27), we obtain, for n > n 1
Noting that {d
Combining (29) and Lemma 3, we obtain, for n > n 0 ,
Combining (30) and (31), we have, there exist constants τ 1,k , τ 2,k satisfying lim k→∞ τ 1,k , τ 2,k → 1 such that, for n > n 0 ,
Combining ( 26) and ( 28) implies, for n > max{n 0 , n 1 },
where constants δ 1,k , δ 2,k → 1 as k → ∞. Using a union bound to ( 32) and ( 33), we obtain, for n > max{n 0 , n 1 },
which, together with (34), completes the proof.
To use Lemma 1, we define
We now derive an approximation of T m (•) using Lemma 7.
On the proof, we first rewrite random variable
. For W m1 , using Lemma 4, we show that for n large enough, W m2 ≈ c(n) (35) and obtain the estimation (41). By noting that the bound in (41) is independent of the hashing function H, unconditional on {H(d • i ), 1 ≤ i ≤ n}, we finish the proof. Lemma 7. For any 2 > 0, there exists x 0 > 0, such that for all x ≥ x 0 ,
where c 3 is a positive constant.
Proof. For n x = x σ with σ < α -1 0 , we define
nx+1 , which, together with ( 18) and (31), we obtain, for > 0, there exists a large x 1 > 0 such that for all x > x 1
where
and ν is the same constant as in (18). Noting W m = 1/(W m1 + W m2 ) and using ( 35) and ( 37), we have
where
and I 2 is defined by replacing (1 -
x } be an event that the first n x data items are hashed to servers S m1 , . . . , S mn x . Let
= 0 otherwise. Thus, without changing the expression of T m (x), we assume 0 < W m q • i < 1 for all i ≥ 1. Note that p i → W m q • i as n x → ∞. Then, for n x large enough and conditional on M nx , we have p i ∼ c 1 /i α• and 0 < p i < 1, where the constant c 1 = c • /(W m1 + (1 -)K(n x )). Similar to the derivation of Lemma 3, applying Lemma 2 to
x ) x -1/α• X (m) i and using Lemma 1 in [9], we obtain, for ∀ 1 > 0, there exists a large x 2 such that for all x > x 2 ,
where W 1-= W m1 + (1 -)K(n x ) and c 4 is a positive constant. A similar result holds for I 2 by replacing (1 -) and c 4 in (40) with (1 + ) and c 5 , respectively. Recalling the definition (35) and conditional on the event M nx , we have I 1 ≤ n x , which, in conjunction with n x < x σ and σ < 1/α • , implies that lim x→∞ I 1 /x 1 α• = 0. Then, conditional on M nx , we have for ∀ 2 > 1 , there exists a sufficiently large x 3 such that for all x > x 3 ,
which, using (38) and (40) and a union bound, implies that for all x > x 4 max{x 1 , x 2 , x 3 },
where W 1+ = W m1 + (1 + )K(n x ) and c 3 is a positive constant related to c 4 , c 5 and ν. Note that 1-c 3 /n 2 on the right side of ( 41) is independent of M nx and W 1+ , W 1-→ W m as x → ∞. Thus, for x large enough, unconditional on M nx and passing 1 , → 0, we obtain (36). Now, we use Lemmas 1, 5, 6 and 7 to prove Theorem 1 by applying the Borel-Cantelli lemma.
Proof of Theorem 1. For the two bounds proved in Lemma 5 and Lemma 6, it is easy to verify that ∞ n=1 (2c 1 + c 2 ) /n 2 < ∞, which, by the Borel-Cantelli lemma, implies that, almost surely for each H ∈ H, there exists a finite n H , such that for all n > n H , we have 1 ≤ q (m)
, where Φm is defined in Lemma 6. Now, note that x in Lemma 7 represents the cache size, which also takes integer values. For the bound in Lemma 7, we have ∞ x=1 c 3 /x 2 < ∞, which, by Borel-Cantelli lemma, implies that, almost surely for each H ∈ H, there exists a finite x H , such that for all x > x H , we have (1 -
These two facts, using Lemma 1 and passing q , p , 2 → 0, implies that, almost surely for all H,
which finishes the proof of Theorem 1.
Proof. By Theorem 1, the miss ratio of cluster C satisfies
which holds almost surely for all H. Noting that q • i ∼ c • /i α• and using Theorem 3 of [26], we can obtain
, which, in conjunction with (7), yields (6).