《计算机科学》相关教学资源（参考文献）Ranged hash functions and the price of churn

Ranged Hash Functions and the price of Churn James Aspnes* Muli Safra Yitong Yin*S Abstract 1 Introduction Ranged hash functions generalize hash tables to the set-Hash tables are one of the oldest tools in computer ting where hash buckets may come and go over time,a science.In the classic model of a hash table,an typical case in distributed settings where hash buckets unknown data set from a large domain is assigned may correspond to unreliable servers or network connec-to a fixed number of buckets,through a consistent tions.Monotone ranged hash functions are a particular mapping(the hash function)from the data domain to class of ranged hash functions that minimize item reas- the buckets.However,in many applications in today's signments in response to churn:changes in the set of computing systems,such as peer-to-peer systems [22], available buckets.The canonical example of a mono- or Internet routers [3],not only is the current data set tone ranged hash function is the ring-based consistent (keys,network flows)unknown,but the availability of hashing mechanism of Karger et al.[13].These hash buckets(peers,peer links)also changes over time.This functions give a maximum load of(logm)when n change in the set of participants of the system is called is the number of items and m is the number of buckets.churn [5],and it is a serious concern for any large The question of whether some better bound could be distributed system. obtained using a more sophisticated hash function has Hashing has been applied to distributed systems remained open. via ranged hash functions,introduced by Karger et We resolve this question by showing two lower al.13.Ranged hash functions are hash functions that bounds.First,the maximum load of any randomized depend on the set of available buckets.A typical ranged monotone ranged hash function is (In m)when hash function hashes items to positions in some space, n =o(mlogm).This bound covers almost all of the and then assigns each item to the nearest available nontrivial case,because when n=(m logm)simple bucket;as the set of buckets changes,an item may random assignment matches the trivial lower bound of move to a new nearest available bucket.Such hash (n/m).We give a matching(though impractical)up-functions have the property of being monotone,[13] per bound that shows that our lower bound is tight over meaning that each data item has its own preference list almost all of its range.Second,for randomized mono-and hashes to the first available bucket in this list.This tone ranged hash functions derived from metric spaces, property minimizes reassignment costs [3],and perhaps there is a further trade-off between the expansion factor because of this,all practical ranged hash functions have of the metric and the load balance,which for the spe- this monotonicity property.This includes systems that cial case of growth-restricted metrics gives a bound of already do load balancing by,for example,creating (n logm),asymptotically equal to that of consistent multiple virtual locations for each bucket [13,22]. hashing.These are the first known non-trivial lower We are interested in obtaining lower bounds on the bounds for ranged hash functions.They also explain maximum load for any these monotone ranged hash why in ten years no better ranged hash functions have functions,parameterized in terms of the number of data arisen to replace consistent hashing. items n and the number of available buckets m.Our lower bounds hold even if:(a)the hash function is optimal for the given n and m;(b)the data set is optimal for the given hash function;and (c)the only power given to the adversary is the worst-case choice of available buckets.Furthermore,though our lower Department of Computer Science,Yale University. bounds are stated for a worst-case choice of buckets, TSupported in part by NSF grant CNS-0435201. Email: the proof technique used means that they continue to aspnescs.yale.edu. School of Mathematical Sciences,Tel-Aviv University.Email: hold with 1 -o(1)probability for a uniform random safraOpost.tau.ac.il. choice of buckets. SSupported by a Yale University Fellowship. Email: Randomization is fundamental to our problem,be- yitong.yineyale.edu

Ranged Hash Functions and the Price of Churn James Aspnes∗† Muli Safra‡ Yitong Yin∗§ Abstract Ranged hash functions generalize hash tables to the set￾ting where hash buckets may come and go over time, a typical case in distributed settings where hash buckets may correspond to unreliable servers or network connec￾tions. Monotone ranged hash functions are a particular class of ranged hash functions that minimize item reas￾signments in response to churn: changes in the set of available buckets. The canonical example of a mono￾tone ranged hash function is the ring-based consistent hashing mechanism of Karger et al. [13]. These hash functions give a maximum load of Θ ￾ n m log m
when n is the number of items and m is the number of buckets. The question of whether some better bound could be obtained using a more sophisticated hash function has remained open. We resolve this question by showing two lower bounds. First, the maximum load of any randomized monotone ranged hash function is Ω(p n m ln m) when n = o(m log m). This bound covers almost all of the nontrivial case, because when n = Ω(m log m) simple random assignment matches the trivial lower bound of Ω(n/m). We give a matching (though impractical) up￾per bound that shows that our lower bound is tight over almost all of its range. Second, for randomized mono￾tone ranged hash functions derived from metric spaces, there is a further trade-off between the expansion factor of the metric and the load balance, which for the spe￾cial case of growth-restricted metrics gives a bound of Ω ￾ n m log m
, asymptotically equal to that of consistent hashing. These are the first known non-trivial lower bounds for ranged hash functions. They also explain why in ten years no better ranged hash functions have arisen to replace consistent hashing. ∗Department of Computer Science, Yale University. †Supported in part by NSF grant CNS-0435201. Email: aspnes@cs.yale.edu. ‡School of Mathematical Sciences, Tel-Aviv University. Email: safra@post.tau.ac.il. §Supported by a Yale University Fellowship. Email: yitong.yin@yale.edu. 1 Introduction Hash tables are one of the oldest tools in computer science. In the classic model of a hash table, an unknown data set from a large domain is assigned to a fixed number of buckets, through a consistent mapping (the hash function) from the data domain to the buckets. However, in many applications in today’s computing systems, such as peer-to-peer systems [22], or Internet routers [3], not only is the current data set (keys, network flows) unknown, but the availability of buckets (peers, peer links) also changes over time. This change in the set of participants of the system is called churn [5], and it is a serious concern for any large distributed system. Hashing has been applied to distributed systems via ranged hash functions, introduced by Karger et al. [13]. Ranged hash functions are hash functions that depend on the set of available buckets. A typical ranged hash function hashes items to positions in some space, and then assigns each item to the nearest available bucket; as the set of buckets changes, an item may move to a new nearest available bucket. Such hash functions have the property of being monotone, [13] meaning that each data item has its own preference list and hashes to the first available bucket in this list. This property minimizes reassignment costs [3], and perhaps because of this, all practical ranged hash functions have this monotonicity property. This includes systems that already do load balancing by, for example, creating multiple virtual locations for each bucket [13, 22]. We are interested in obtaining lower bounds on the maximum load for any these monotone ranged hash functions, parameterized in terms of the number of data items n and the number of available buckets m. Our lower bounds hold even if: (a) the hash function is optimal for the given n and m; (b) the data set is optimal for the given hash function; and (c) the only power given to the adversary is the worst-case choice of available buckets. Furthermore, though our lower bounds are stated for a worst-case choice of buckets, the proof technique used means that they continue to hold with 1 − o(1) probability for a uniform random choice of buckets. Randomization is fundamental to our problem, be-

cause no lower bounds have been shown for randomized 2 Model ranged hash functions.Randomization is also important Items and buckets.Given a domain of items for practical algorithms.For the deterministic case,it is I=N,and a domain of buckets =M,where the easy to obtain terrible load balancing.In the full paper, buckets may become available and unavailable,we refer we show that all deterministic monotone ranged hash to the set S of available buckets as the state.A ranged functions experience a load of (Vn)in the worst case hash function is a function in the form of h 24xTu. when n=m.A naive deterministic implementation of We denote by hs the assignment of items to buckets consistent hashing would be even worse:an adversary imposed by h for a specific state S.Naturally,we require deleting all buckets outside of some very narrow interval that hs(T)C S for any SCu. can get nearly all n items in the first remaining bucket For any data set DCT,and any state S,the load With randomization,the hash function can do much of bucket beu is denoted as (b)=Ihs(b)nDl,and better.Nonetheless,we give two lower bounds.For we let e=maxese(b)be the maximum load of state a general monotone ranged hash function,we show a S.If the data set D is the entire domain Z,we omit D lower bound of2(√=logm)when n=o(m log m月 and write es(b)for e(b)and es for e. when n=(mlog m)the trivial lower bound of (n/m) Besides load balance,another critical performance matches the upper bound obtained from random as- parameter of ranged hash functions is smoothness, signment.We give a tight matching upper bound for which is characterized by the number of reassigned items the small-n case based on finding nearest neighbors in going from one state to another.Smoothness represents a hypercube;unfortunately,because of the difficulty a natural requirement for a data structure that the of nearest-neighbors in a hypercube,this upper bound maintenance cost should be small when the state of the does not give a practical implementation of a distributed data structure changes.In 13,the property of being hash function. monotone is introduced to characterize those ranged Our second lower bound applies to the more prac- hash functions with optimal smoothness.This property tical setting of ranged hash functions based on as- says that removing buckets only changes the position signing each item to the nearest bucket in a metric of items in the removed buckets:formally,a ranged space,where the choice of how to embed both items hash function h is monotone if for all S C T CW and buckets in the space may be based on an ar- hs(i)=hr(i)if hr(i)E S.For a monotone ranged bitrary joint distribution.We show a trade-off be- hash function,items are reassigned only if necessary. tween KR-dimension [6,12,16],a counting measure of Monotone ranged hash functions can always be doubling dimension and load balance:in a space described by a preference matrix.A preference with KR-dimension K,no randomized monotone ranged matrix a is an N x M matrix where each row mi is a hash function-even one where the embedding of items permutation of In [13],it is shown that a ranged hash and buckets is chosen according to a non-uniform non- function h is monotone if and only if there is a preference independent distribution-can do better than Q(2-2K matrix元，such that(hs()=minesπl(b)for In m).As with our general lower bound,the result every S and i,i.e.,if and only if every item possesses an continues to hold with a uniform choice of buckets with ordering of buckets,and is always assigned to the first probability 1-o(1). available bucket according to its order.Throughout this The interesting case is when the KR-dimension is paper,we use the notations of a monotone ranged hash constant,since such a growth-restricted metric al- function h and its corresponding preference matrix m lows finding nearest neighbors quickly using known tech- interchangeably. niques [12].Our lower bound shows that in this case In many applications of ranged hash functions,it is even a hash function based on a very cleverly chosen impractical to store a complete list of M possible buck- metric space,embedding,and probability distribution ets for every item.A general and natural methodology cannot beat the O(m Inm)upper bound of simple con- to efficiently represent a monotone ranged hash func- sistent hashing using a uniform independent distribu- tion is to embed I and w in a metric space and assign tion on a one-dimensional ring.Our lower bound thus each item i to the closest available bucket in the cur- hints at the reason for the continued practical use of rent state.An implementation of ranged hash function this technique. then involves a specific embedding of items and buckets Organization.We give a formal description of in a metric space,and a mechanism supporting nearest our model in Section 2.Previous work is described neighbor search (NNS)9,12 in that metric. in Section 3.Our results are described formally in Performance measures.We consider the effect Section 4,and the details are given in the following on load balance of two important properties of a ranged sections. hash function:(a)the requirement of optimal smooth-

cause no lower bounds have been shown for randomized ranged hash functions. Randomization is also important for practical algorithms. For the deterministic case, it is easy to obtain terrible load balancing. In the full paper, we show that all deterministic monotone ranged hash functions experience a load of Ω(√ n) in the worst case when n = m. A naive deterministic implementation of consistent hashing would be even worse: an adversary deleting all buckets outside of some very narrow interval can get nearly all n items in the first remaining bucket. With randomization, the hash function can do much better. Nonetheless, we give two lower bounds. For a general monotone ranged hash function, we show a lower bound of Ω ￾p n m log m
when n = o(m log m); when n = Ω(m log m) the trivial lower bound of Ω(n/m) matches the upper bound obtained from random as￾signment. We give a tight matching upper bound for the small-n case based on finding nearest neighbors in a hypercube; unfortunately, because of the difficulty of nearest-neighbors in a hypercube, this upper bound does not give a practical implementation of a distributed hash function. Our second lower bound applies to the more prac￾tical setting of ranged hash functions based on as￾signing each item to the nearest bucket in a metric space, where the choice of how to embed both items and buckets in the space may be based on an ar￾bitrary joint distribution. We show a trade-off be￾tween KR-dimension [6, 12, 16], a counting measure of doubling dimension and load balance; in a space with KR-dimension K, no randomized monotone ranged hash function—even one where the embedding of items and buckets is chosen according to a non-uniform non￾independent distribution—can do better than Ω(2−2K · n m ln m). As with our general lower bound, the result continues to hold with a uniform choice of buckets with probability 1 − o(1). The interesting case is when the KR-dimension is constant, since such a growth-restricted metric al￾lows finding nearest neighbors quickly using known tech￾niques [12]. Our lower bound shows that in this case, even a hash function based on a very cleverly chosen metric space, embedding, and probability distribution cannot beat the O( n m ln m) upper bound of simple con￾sistent hashing using a uniform independent distribu￾tion on a one-dimensional ring. Our lower bound thus hints at the reason for the continued practical use of this technique. Organization. We give a formal description of our model in Section 2. Previous work is described in Section 3. Our results are described formally in Section 4, and the details are given in the following sections. 2 Model Items and buckets. Given a domain of items I = [N], and a domain of buckets U = [M], where the buckets may become available and unavailable, we refer to the set S of available buckets as the state. A ranged hash function is a function in the form of h : 2U×I → U. We denote by hS the assignment of items to buckets imposed by h for a specific state S. Naturally, we require that hS(I) ⊆ S for any S ⊆ U. For any data set D ⊆ I, and any state S, the load of bucket b ∈ U is denoted as ` D S (b) = |h −1 S (b) ∩ D|, and we let ` D S = maxb∈S ` D S (b) be the maximum load of state S. If the data set D is the entire domain I, we omit D and write `S(b) for ` D S (b) and `S for ` D S . Besides load balance, another critical performance parameter of ranged hash functions is smoothness, which is characterized by the number of reassigned items going from one state to another. Smoothness represents a natural requirement for a data structure that the maintenance cost should be small when the state of the data structure changes. In [13], the property of being monotone is introduced to characterize those ranged hash functions with optimal smoothness. This property says that removing buckets only changes the position of items in the removed buckets: formally, a ranged hash function h is monotone if for all S ⊆ T ⊆ U, hS(i) = hT (i) if hT (i) ∈ S. For a monotone ranged hash function, items are reassigned only if necessary. Monotone ranged hash functions can always be described by a preference matrix. A preference matrix π is an N × M matrix where each row πi is a permutation of U. In [13], it is shown that a ranged hash function h is monotone if and only if there is a preference matrix π, such that π −1 i (hS(i)) = minb∈S π −1 i (b) for every S and i, i.e., if and only if every item possesses an ordering of buckets, and is always assigned to the first available bucket according to its order. Throughout this paper, we use the notations of a monotone ranged hash function h and its corresponding preference matrix π interchangeably. In many applications of ranged hash functions, it is impractical to store a complete list of M possible buck￾ets for every item. A general and natural methodology to efficiently represent a monotone ranged hash func￾tion is to embed I and U in a metric space and assign each item i to the closest available bucket in the cur￾rent state. An implementation of ranged hash function then involves a specific embedding of items and buckets in a metric space, and a mechanism supporting nearest neighbor search (NNS) [9, 12] in that metric. Performance measures. We consider the effect on load balance of two important properties of a ranged hash function: (a) the requirement of optimal smooth-

ness (i.e.being monotone);and (b)the expansion prop-15,17,19.All of these methods involve evenly cutting erties of the underlying metric space(which may dra-the unit circle by enforcing a certain pattern by which matically affect the hardness of searching nearest neigh-points in the unit circle are occupied.With this bors). method,the systems sacrifice the "off-line"property of For this purpose,we define a measure called the a hash function;the location of buckets now depends price of churn.We define this in terms of a class of on the order in which they arrive and depart,requiring ranged hash functions sharing a particular property.For coordination mechanisms to manage the assignment. a class H of ranged hash functions,let P:H denote an The question of whether such coordination is neces- arbitrary probability distribution over hash functions in sary has remained open.No new ranged hash function H.The price of churn for H is defined formally as with better performance has been proposed since consis- tent hashing.No non-trivial lower bound is known to us en(N,M,n,m) for ranged hash functions either.Although ranged hash =路期即{gg≥-1-} functions as a class of meaningful mathematical objects have been known for a decade,we have little knowledge This represents the lower bound on the maximum load about their structure,and the relation between their of all randomized ranged hash functions with property parameters. H.With I [N]and u=[M],for any randomized ranged hash function with some property H,for any 4 Our results data set D∈(A),there exists a stateS∈()，such We prove that for the class of monotone ranged hash that the maximum load e is at least (N,M,n,m) functions monotone(N,M,n,m）=2(√-Inm)for the with high probability. case that n=o(mlogm)and lzonotone(N,M,n,m)= Note that in this notion of lower bound,the data (m)for the case that n =(mlogm).This bound is set D is fixed by us,and then the state S is chosen tight for almost all settings of n and m.This shows by an adversary.This is different from a lower bound a similar property as the price of unknown data set against both a worst-case S and a worst-case D.We (in general we can do no better than random-balls- use this alternative formulation because our purpose into-bins [18]against a worst-case data set):they both is to understand specifically how a changing set of approach the asymptotic optimum O()as n grows participants may affect a system:thus we focus on the to (m log m).However,the price of churn is much costs caused solely by the unknown state,rather than smaller than the skew induced by a random balls-into- other issues such as an unknown data set (which has bins assignment. been covered by the study of hash tables).Our lower We then look at ranged hash functions arising from bound states that even if the system is fully optimized metric spaces.We explore the relation between the towards the current data set,there is still some price load balance and the expansion properties of the metric. we have to pay for unpredictable participation in the We adopt a counting measure of doubling dimension system.Giving this additional power to the ranged hash introduced in 12,which is called KR-dimension in the function only strengthens our lower bounds. literature [6,16],namely,we say the embedding of u has KR-dimension K if doubling the radius may increase 3 Previous work the size of the balls in by at most a factor of 2 So far the only practical construction of ranged hash We prove that for the class of ranged hash functions function is consistent hashing,which was introduced by implemented via metric-space embedding where w has Karger et al.13 along with the notion of a ranged KR-dimension K,ek-dimge(N,M,n,m)=(2-2K. hash function.Here items and buckets are mapped 产lnm)ifK≤}log2(是lnm).Combining with a to a uniformly random place in the continuous unit widely believed conjecture for nearest neighbor search, circle [0,1),and each item is assigned to the closet "the curse of dimensionality"[9],this trade-off provides available bucket.For any data setD=n and any state us a very interesting insight:although dimensionality S=m,the maximum load e2 is with high probability curses search.it blesses load balance. θ（是lnm): When the KR-dimension is O(1),the metric is Consistent hashing was originally designed for web called growth-restricted.In this case,the trade-off caching;however,through its utility in a wide variety becomes lo(1)-dimkR(N,M,n,m)=(n In m),which is of distributed settings,it has become the foundation exactly the bound for the maximum load of consistent of many modern distributed systems 2,8,11,21,22. hashing. Many systems that implement consistent hashing have Despite the fact that the original 0,1)metric used tried different ways to improve load balance 1,4,14, in consistent hashing is not in general growth-restricted

ness (i.e. being monotone); and (b) the expansion prop￾erties of the underlying metric space (which may dra￾matically affect the hardness of searching nearest neigh￾bors). For this purpose, we define a measure called the price of churn. We define this in terms of a class of ranged hash functions sharing a particular property. For a class H of ranged hash functions, let P : H denote an arbitrary probability distribution over hash functions in H. The price of churn for H is defined formally as `H(N, M, n, m) = max S∈( U m) min D∈( I n) min P:H supn L    Pr P [` D S ≥ L] = 1 − o(1)o . This represents the lower bound on the maximum load of all randomized ranged hash functions with property H. With I = [N] and U = [M], for any randomized ranged hash function with some property H, for any data set D ∈ ￾ I n
, there exists a state S ∈ ￾U m
, such that the maximum load ` D S is at least `H(N, M, n, m) with high probability. Note that in this notion of lower bound, the data set D is fixed by us, and then the state S is chosen by an adversary. This is different from a lower bound against both a worst-case S and a worst-case D. We use this alternative formulation because our purpose is to understand specifically how a changing set of participants may affect a system: thus we focus on the costs caused solely by the unknown state, rather than other issues such as an unknown data set (which has been covered by the study of hash tables). Our lower bound states that even if the system is fully optimized towards the current data set, there is still some price we have to pay for unpredictable participation in the system. Giving this additional power to the ranged hash function only strengthens our lower bounds. 3 Previous work So far the only practical construction of ranged hash function is consistent hashing, which was introduced by Karger et al. [13] along with the notion of a ranged hash function. Here items and buckets are mapped to a uniformly random place in the continuous unit circle [0, 1), and each item is assigned to the closet available bucket. For any data set |D| = n and any state |S| = m, the maximum load ` D S is with high probability Θ( n m ln m). Consistent hashing was originally designed for web caching; however, through its utility in a wide variety of distributed settings, it has become the foundation of many modern distributed systems [2, 8, 11, 21, 22]. Many systems that implement consistent hashing have tried different ways to improve load balance [1, 4, 14, 15, 17, 19]. All of these methods involve evenly cutting the unit circle by enforcing a certain pattern by which points in the unit circle are occupied. With this method, the systems sacrifice the “off-line” property of a hash function; the location of buckets now depends on the order in which they arrive and depart, requiring coordination mechanisms to manage the assignment. The question of whether such coordination is neces￾sary has remained open. No new ranged hash function with better performance has been proposed since consis￾tent hashing. No non-trivial lower bound is known to us for ranged hash functions either. Although ranged hash functions as a class of meaningful mathematical objects have been known for a decade, we have little knowledge about their structure, and the relation between their parameters. 4 Our results We prove that for the class of monotone ranged hash functions `monotone(N, M, n, m) = Ω(p n m ln m) for the case that n = o(m log m) and `monotone(N, M, n, m) = Ω( n m ) for the case that n = Ω(m log m). This bound is tight for almost all settings of n and m. This shows a similar property as the price of unknown data set (in general we can do no better than random-balls￾into-bins [18] against a worst-case data set): they both approach the asymptotic optimum O( n m ) as n grows to Ω(m log m). However, the price of churn is much smaller than the skew induced by a random balls-into￾bins assignment. We then look at ranged hash functions arising from metric spaces. We explore the relation between the load balance and the expansion properties of the metric. We adopt a counting measure of doubling dimension introduced in [12], which is called KR-dimension in the literature [6,16], namely, we say the embedding of U has KR-dimension K if doubling the radius may increase the size of the balls in U by at most a factor of 2K. We prove that for the class of ranged hash functions implemented via metric-space embedding where U has KR-dimension K, `K-dimKR (N, M, n, m) = Ω(2−2K · n m ln m) if K ≤ 1 4 log2 ( n m ln m). Combining with a widely believed conjecture for nearest neighbor search, “the curse of dimensionality” [9], this trade-off provides us a very interesting insight: although dimensionality curses search, it blesses load balance. When the KR-dimension is O(1), the metric is called growth-restricted. In this case, the trade-off becomes `O(1)-dimKR (N, M, n, m) = Ω( n m ln m), which is exactly the bound for the maximum load of consistent hashing. Despite the fact that the original [0, 1) metric used in consistent hashing is not in general growth-restricted

for uniformly distributed buckets,our lower bound ap-and any n min(M,N)and m n, plies to consistent hashing because we can-without changing the structure of the algorithm-replace this 1.if H is I-hereditary,then lH(N,M,n,m)> metric with a (growth-restricted)discrete counting met- EH(n,M,n,m); ric that simply counts the number of bucket locations 2.if H is probabilistically U-hereditary,then between any two buckets.Our result thus shows that eH(N,M,n,m) ≥CH(N,,n,m)for any consistent hashing is optimal for all constructions aris- m≤x≤M. ing from growth-restricted metrics.This is particularly interesting for distributed computing for two reasons. Proof.1.Observe that for any randomized ranged First,growth-restricted metrics are among the strongest hash function h with I-hereditary property H,if metrics for which efficient exact nearest-neighbor search for some data set D∈（月）that Pr[唱<L)=2(l) is currently possible.Second,as argued in [12],a for all S∈()，the restriction ofh on the new growth-restricted metric holds in the case of many typi- item domain I'=D is still a randomized ranged cal Internet applications.Our results thus demonstrate hash functions with property H(since H is I- that consistent hashing is optimal for such applications. hereditary),and it still holds for the new ranged Besides these specific results,we contribute new hash function that Pr[es <L]=(1)for all S E techniques to analyzing ranged hash functions.Pre- ()Therefore,assuming that (n,M.n,m)= vious approaches [13,19]can be seen as bounding the L,i.e.for any randomized ranged hash functions maximum volume of Voronoi cells governed by random defined on I'=[n]and u'=[M]with property centers.This technique works fine for restricted cases H,it holds that Pr[es >L]=1-o(1)for such as constructions arising from 1-dimensional metric some state S∈()，according to the converse- space,but does not appear to generalize to more gen- negative proposition to the above observation,for eral classes of(randomized)ranged hash functions.Our all randomized ranged hash functions defined on method is to explore directly the structure of the pref- I=[N]and u [M]with property H,for erence matrices.By bounding certain measures of the all data sets D ()there must exist some richness of this structure,we can prove lower bounds for state S∈(（such that Pr[eg≥)=1 general monotone ranged hash functions.For ranged o(1),i.e.(N,M,n,m)>L,which implies that hash function arising from metric spaces,we consider the connection between load balance and the density en(N,M,n,m)zEn(n,M,n,m). of balls in the metric space;using this we can prove a 2.We assume that (N,z,n,m)=L,i.e.for any trade-off between load balance and the expansion rate. randomized ranged hash functions defined on Z'= [N]and '=[x]with property H,for all data set 5 Domain reduction D∈()，it holds that Pre≥)=1-o(1) In order to avoid considering too many possibilities,it for some state S).For any randomized is helpful to be able to reduce the problem of churn to ranged hash functions h defined on I =[N]and a few representative special cases.In this section,we =[M]with property H,if H is probabilistically describe how to do so. u-hereditary,we can randomly pick x buckets, We say a property H of ranged hash functions is say []such that the restriction of h on the new Z-hereditary,if for any h e H,and any T'I, bucket domain '=[z]has property H with high the restriction of h on the domain I'still belongs to probability,therefore according to the previous H.We say a property H of ranged hash functions is assumption,for the new ranged hash function, probabilistically W-hereditary,if for any h E H,and with high probability,for all data set D ()it any M<M,there is some distribution of u( holds that Pr[e>L]=1-o(1)for some state such that the restriction of h on the domain belongs to H with high probability. ()()ie.for h,for all data set De(, it holds that Pr[e >L]=1-o(1)for some state It is easy to see that the property of being mono- S∈()，which means that er(N,M,n,m)≥L,so tone is both Z-hereditary and u-hereditary,since any we prove that H(N,M,n,m)zH(N,n,m). restriction of a preference matrix is still a preference matrix. 6 Load balance vs.monotonicity The following lemma allows reducing the price of churn to a base case with small parameters. In this section,we prove the following theorem. THEOREM 6.1.For any randomized monotone ranged LEMMA 5.1.For any class H of ranged hash functions hash function with domain I =N and U =M,for

for uniformly distributed buckets, our lower bound ap￾plies to consistent hashing because we can—without changing the structure of the algorithm—replace this metric with a (growth-restricted) discrete counting met￾ric that simply counts the number of bucket locations between any two buckets. Our result thus shows that consistent hashing is optimal for all constructions aris￾ing from growth-restricted metrics. This is particularly interesting for distributed computing for two reasons. First, growth-restricted metrics are among the strongest metrics for which efficient exact nearest-neighbor search is currently possible. Second, as argued in [12], a growth-restricted metric holds in the case of many typi￾cal Internet applications. Our results thus demonstrate that consistent hashing is optimal for such applications. Besides these specific results, we contribute new techniques to analyzing ranged hash functions. Pre￾vious approaches [13, 19] can be seen as bounding the maximum volume of Voronoi cells governed by random centers. This technique works fine for restricted cases such as constructions arising from 1-dimensional metric space, but does not appear to generalize to more gen￾eral classes of (randomized) ranged hash functions. Our method is to explore directly the structure of the pref￾erence matrices. By bounding certain measures of the richness of this structure, we can prove lower bounds for general monotone ranged hash functions. For ranged hash function arising from metric spaces, we consider the connection between load balance and the density of balls in the metric space; using this we can prove a trade-off between load balance and the expansion rate. 5 Domain reduction In order to avoid considering too many possibilities, it is helpful to be able to reduce the problem of churn to a few representative special cases. In this section, we describe how to do so. We say a property H of ranged hash functions is I-hereditary, if for any h ∈ H, and any I 0 ⊆ I, the restriction of h on the domain I 0 still belongs to H. We say a property H of ranged hash functions is probabilistically U-hereditary, if for any h ∈ H, and any M0 < M, there is some distribution of U 0 ∈ ￾ U M0
such that the restriction of h on the domain U 0 belongs to H with high probability. It is easy to see that the property of being mono￾tone is both I-hereditary and U-hereditary, since any restriction of a preference matrix is still a preference matrix. The following lemma allows reducing the price of churn to a base case with small parameters. Lemma 5.1. For any class H of ranged hash functions and any n ≤ min(M, N) and m ≤ n, 1. if H is I-hereditary, then `H(N, M, n, m) ≥ `H(n, M, n, m); 2. if H is probabilistically U-hereditary, then `H(N, M, n, m) ≥ `H(N, x, n, m) for any m ≤ x ≤ M. Proof. 1. Observe that for any randomized ranged hash function h with I-hereditary property H, if for some data set D ∈ ￾ I n
that Pr[` D S < L] = Ω(1) for all S ∈ ￾U m
, the restriction of h on the new item domain I 0 = D is still a randomized ranged hash functions with property H (since H is I￾hereditary), and it still holds for the new ranged hash function that Pr[`S < L] = Ω(1) for all S ∈ ￾U m
. Therefore, assuming that `H(n, M, n, m) = L, i.e. for any randomized ranged hash functions defined on I 0 = [n] and U 0 = [M] with property H, it holds that Pr[`S ≥ L] = 1 − o(1) for some state S ∈ ￾U 0 m
, according to the converse￾negative proposition to the above observation, for all randomized ranged hash functions defined on I = [N] and U = [M] with property H, for all data sets D ∈ ￾ I n
, there must exist some state S ∈ ￾U m
such that Pr[` D S ≥ L] = 1 − o(1), i.e. `H(N, M, n, m) ≥ L, which implies that `H(N, M, n, m) ≥ `H(n, M, n, m). 2. We assume that `H(N, x, n, m) = L, i.e. for any randomized ranged hash functions defined on I 0 = [N] and U 0 = [x] with property H, for all data set D ∈ ￾ I 0 n
, it holds that Pr[` D S ≥ L] = 1 − o(1) for some state S ∈ ￾U 0 m
. For any randomized ranged hash functions h defined on I = [N] and U = [M] with property H, if H is probabilistically U-hereditary, we can randomly pick x buckets, say [x], such that the restriction of h on the new bucket domain U 0 = [x] has property H with high probability, therefore according to the previous assumption, for the new ranged hash function, with high probability, for all data set D ∈ ￾ I n
, it holds that Pr[` D S ≥ L] = 1 − o(1) for some state S ∈ ￾U 0 m
⊆ ￾U m
, i.e. for h, for all data set D ∈ ￾ I n
, it holds that Pr[` D S ≥ L] = 1 − o(1) for some state S ∈ ￾U m
, which means that `H(N, M, n, m) ≥ L, so we prove that `H(N, M, n, m) ≥ `H(N, x, n, m). 6 Load balance vs. monotonicity In this section, we prove the following theorem. Theorem 6.1. For any randomized monotone ranged hash function with domain I = [N] and U = [M], for

any sufficiently large n and m that N>2n.M>2m,show that in this case we can get a large disjoint subfam- and n m,for any data set D E(),there erists a ily of neighborhoods by applying the Hajnal-Szemeredi state S(),such that the marimum load(L)Theorem [7.After that the standard analysis of devia- with high probability,where tion can be applied. Let Aj(b)denote the number of b-entries in column m≤n<o(n log m) L= nm jofπ，i.e.入(b)={i|π=bl: n=n(mlogm) LEMMA 6.2.Let L=m.For any constants An equivalent statement is that lsonotone(N,M,n,m)=(L),where L is defined <B<and <a<v-B,if for a n x m! as above. preference matrix n,it holds that for every b E u and According to Lemma 5.1,it is sufficient to consider every column j≤aL,入(b)=O(n),then esonotone(n,m',n,m)for m'=max(n,2m).For the rest of this section,we assume that I=[n]and u=[m'], Pr[Ls≥aL=1-o(1) se) that is,we only consider the n x m'preference matrices. Since the (bound is trivial,we are only interested Proof.We first construct a family of disjoint aL-wide in the case where m n<o(m log m). neighborhood [AA (b)}bEU,where Ul=(n1-28),and Instead of directly proving the lower bound for ran- for any b∈U,l△A(bl≤a2L2.Then we apply domized ranged hash functions,we look at an arbitrary the second moment method to argue that with high deterministic m,and show a probabilistic bound on max-probability,at least one of such neighborhoods has imum load for a uniformly random state s().The(b= same bound for randomized hash functions with worst- We only consider the first aL columns of a.Since case S follows from Yao's min-max principle. Aj(b)=O(n3)for every b,there are at least (n1-3) Given a monotone ranged hash function for any buckets b,each of which appears at least aL times in bucket bE and any set of items AC Z,we define the the first aL columns;it follows that there is set V of A-neighborhood△A(b)={πi|i∈A and j≤π；'(b),such bs that|W|=(nl-),and for every b∈V,there i.e.AA(b)is the union of the set of buckets preferred is aA that Al=aL and the whole neighborhood by each item from A over b,including b.We say Al as AA(b)is in the first aL columns.This guarantees that the width of the neighborhood.It is easy to see that AA(b)<aLAl=a212. the concept of neighborhood characterizes the load of a We define a graph G(V,E)with the above V as bucket the vertex set,and (a,b)EE if AA (a)intersects with △A.(b).Since入(b)=O(n)and the size of each LEMMA 6.1.For any state s cu,the load es(b)of AA (b)is bounded by a212 =O(Inn),the degree of bucket b at state S is at least L,if and only if there is G(V,E)is at most O(nB).According to the Hajnal- some A≤I such that A=Land△A(b)nS={b}. Szemeredi Theorem 7,there is an independent set U of size (n1-28).Translating back from the graph to the It is thus sufficient to look at the collection of L-neighborhood structure,this says that there is a family wide neighborhoods△L={△a(b)|b∈l4,lAl=L}, of disjoint neighborhoods {AA (b)e of cardinality which is a set system with ground set u,and show 72(n1-29),such that|△Ab(b)⑥l≤a2L2 for every b∈U. that for the uniformly random s∈(%)，with high For any bucket b E U.let Xo be the indicator that probability there exists some△A(b)∈△L such that X =1 if AA (b)nS=[b},and Xo=0 if otherwise. △A()⑥nS={b}.However,the intersection between Let=∑beUX.Due to Lemma6.l,Prls≥al≥ neighborhoods can be extremely complicated for arbi-PrU,A(6)n=()]=1-Pr[X0]. trary m,which makes the deviation hard to analyze.To overcome this,we extend the combinatorial deletion For any constant 0<a<-B, method introduced in [10,20],namely,we sequentially E(X)=IU1·Pr△A(b)nS={b】 delete those buckets which cause the correlations,un- til the remaining family of neighborhoods has a suffi- 2(n1-290 m-a2L2\ ciently large disjoint subfamily.We do this in such a m-1 m way that,conditioning on the previous deletions,the ≥2(n1-28-2a) presence of each deleted bucket can only increase the =w(1) maximum load. We first investigate the case where the entries in For any a,bU,AA.(a)and AA(b)are disjoint,thus each column of r do not include many duplicates.We cov(Xa,X)<0,therefore var(X)=>be var(X)+

any sufficiently large n and m that N > 2n, M > 2m, and n ≥ m, for any data set D ∈ ￾ I n
, there exists a state S ∈ ￾U m
, such that the maximum load ` D S = Ω(L) with high probability, where L =  p n m ln m m ≤ n < o(m log m) n m n = Ω(m log m) . An equivalent statement is that `monotone(N, M, n, m) = Ω(L), where L is defined as above. According to Lemma 5.1, it is sufficient to consider `monotone(n, m0 , n, m) for m0 = max(n, 2m). For the rest of this section, we assume that I = [n] and U = [m0 ], that is, we only consider the n×m0 preference matrices. Since the Ω( n m ) bound is trivial, we are only interested in the case where m ≤ n < o(m log m). Instead of directly proving the lower bound for ran￾domized ranged hash functions, we look at an arbitrary deterministic π, and show a probabilistic bound on max￾imum load for a uniformly random state S ∈ ￾U m
. The same bound for randomized hash functions with worst￾case S follows from Yao’s min-max principle. Given a monotone ranged hash function π, for any bucket b ∈ U and any set of items A ⊆ I, we define the A-neighborhood ∆A(b) = {πij | i ∈ A and j ≤ π −1 i (b)}, i.e. ∆A(b) is the union of the set of buckets preferred by each item from A over b, including b. We say |A| as the width of the neighborhood. It is easy to see that the concept of neighborhood characterizes the load of a bucket. Lemma 6.1. For any state S ⊆ U, the load `S(b) of bucket b at state S is at least L, if and only if there is some A ⊆ I such that |A| = L and ∆A(b) ∩ S = {b}. It is thus sufficient to look at the collection of L￾wide neighborhoods ∆L = {∆A(b) | b ∈ U, |A| = L}, which is a set system with ground set U, and show that for the uniformly random S ∈ ￾U m
, with high probability there exists some ∆A(b) ∈ ∆L such that ∆A(b) ∩ S = {b}. However, the intersection between neighborhoods can be extremely complicated for arbi￾trary π, which makes the deviation hard to analyze. To overcome this, we extend the combinatorial deletion method introduced in [10, 20], namely, we sequentially delete those buckets which cause the correlations, un￾til the remaining family of neighborhoods has a suffi- ciently large disjoint subfamily. We do this in such a way that, conditioning on the previous deletions, the presence of each deleted bucket can only increase the maximum load. We first investigate the case where the entries in each column of π do not include many duplicates. We show that in this case we can get a large disjoint subfam￾ily of neighborhoods by applying the Hajnal-Szemeredi Theorem [7]. After that the standard analysis of devia￾tion can be applied. Let λj (b) denote the number of b-entries in column j of π, i.e. λj (b) = |{i | πij = b}|. Lemma 6.2. Let L = q m0 m ln m. For any constants 0 < β < 1 2 and 0 < α < q 1 2 − β, if for a n × m0 preference matrix π, it holds that for every b ∈ U and every column j ≤ αL, λj (b) = O˜(n β ), then Pr S∈( [m0] m ) [`S ≥ αL] = 1 − o(1). Proof. We first construct a family of disjoint αL-wide neighborhood {∆Ab (b)}b∈U , where |U| = Ω( ˜ n 1−2β ), and for any b ∈ U, |∆Ab (b)| ≤ α 2L 2 . Then we apply the second moment method to argue that with high probability, at least one of such neighborhoods has ∆Ab (b) ∩ S = {b}. We only consider the first αL columns of π. Since λj (b) = O˜(n β ) for every b, there are at least Ω( ˜ n 1−β ) buckets b, each of which appears at least αL times in the first αL columns; it follows that there is set V of such bs that |V | = Ω( ˜ n 1−β ), and for every b ∈ V , there is a Ab that |Ab| = αL and the whole neighborhood ∆Ab (b) is in the first αL columns. This guarantees that |∆Ab (b)| ≤ αL|Ab| = α 2L 2 . We define a graph G(V, E) with the above V as the vertex set, and (a, b) ∈ E if ∆Aa (a) intersects with ∆Ab (b). Since λj (b) = O˜(n β ) and the size of each ∆Ab (b) is bounded by α 2L 2 = O(ln n), the degree of G(V, E) is at most O˜(n β ). According to the Hajnal￾Szemeredi Theorem [7], there is an independent set U of size Ω( ˜ n 1−2β ). Translating back from the graph to the neighborhood structure, this says that there is a family of disjoint neighborhoods {∆Ab (b)}b∈U of cardinality Ω( ˜ n 1−2β ), such that |∆Ab (b)| ≤ α 2L 2 for every b ∈ U. For any bucket b ∈ U, let Xb be the indicator that Xb = 1 if ∆Ab (b) ∩ S = {b}, and Xb = 0 if otherwise. Let X = P b∈U Xb. Due to Lemma 6.1, Pr[`S ≥ αL] ≥ Pr[∃b ∈ U, ∆Ab (b) ∩ S = {b}] = 1 − Pr[X = 0]. For any constant 0 < α < q 1 2 − β, E(X) = |U| · Pr[∆Ab (b) ∩ S = {b}] ≥ Ω( ˜ n 1−2β )  m − α 2L 2 m − 1 . m0 m  ≥ Ω( ˜ n 1−2β−2α 2 ) = ω(1). For any a, b ∈ U, ∆Aa (a) and ∆Ab (b) are disjoint, thus cov(Xa, Xb) ≤ 0, therefore var(X) = P b∈U var(Xb) +