thus distributed among those stored, providing load bal 160-bit id space 11.l ancing both within Coral and between servers using Coral 4.3 Hierarchical Operations level 2 For locality-optimized routing and data placement, Coral uses several levels of dshts called clusters. each level i cluster is named by a randomly-chosen 160-bit cluster .1 identifier; the level-0 cluster ID is predefined as060.Re- 2 call that a set of nodes should form a cluster if their aver Ca+. age, pair-wise RTTs are below some threshold. As men- level I tioned earlier, we describe a three-level hierarchy with thresholds of oo. 60 msec and 20 msec for level-0-1 and -2 clusters respectively. In Section 6, we present experi- 0人1 ental evidence to the client-side benefit of clustering Figure 3 illustrates Corals hierarchical routing Ciei tions. each coral node has the same node id in all clus- ters to which it belongs, we can view a node as projecting level 0 its presence to the same location in each of its clusters This structure must be reflected in Corals basic routing infrastructure, in particular to support switching between a node's distinct DSHTs midway through a lookup. 3 The Hierarchical Retrieval Algorithm. A requesting node R specifies the starting and stopping levels at which Figure 3: Coral's hierarchical routing structure. Nodes use the Coral should search. By default, it initiates the get query same IDs in each of their clusters; higher-level clusters are natu- on its highest (level-2)cluster to try to take advantage of rally sparser. Note that a node can be identifi ed in a cluster by its network locality. If routing RPCs on this cluster hit some shortest unique ID prefix, e.8,"1I for R in its level-2 cluster, node storing the key k(RPC I in Fig 3), the lookup halts nodes sharing ID prefi xes are located on common subtrees and and returns the corresponding stored value(s)a hi- are closer in the XOR metric. While higher-level neighbors without ever searching lower-level clusters ally share lower-level clusters as shown, this is not necessarily If a key is not found, the lookup will reach k's closest so RPCs for a retrieval on key k are sequentially numbered. node C2 in this cluster(RPC 2), signifying failure at this level. So node R continues the search in its level-1 clus- ter. As these clusters are very often concentric, C2 likely clusters,as shown. R begins searching e space in all However, this placement is only"correct"within the con- exists at the identical location in the identifier ard from C2 text of the local level-2 cluster. Thus, provided that the in its level-I cluster(RPC 3), having already traversed the key is not already loaded, the node continues its insertion ID-space up to C2s prefix in the level-I cluster from the point at which the key was Even if the search eventually switches to the global inserted in level 2, much as in the retrieval case. Again, cluster(RPC 4), the total number of RPCs required is Coral traverses the ID-space only once. As illustrated about the same as a single-level lookup service, as a in Figure 3, this practice results in a loose hierarchical lookup continues from the point at which it left off in cache, whereby a lower-level cluster contains nearly all the identifier space of the previous cluster. Thus, (1) data stored in the higher-level clusters to which its mem- all lookups at the beginning are fast,(2)the system can bers also belong tightly bound rPC timeouts, and (3)all pointers in higher- To enable such cluster-aware behavior. the headers of level clusters reference data within that local cluster every Coral rPC include the sender's cluster information the identifier, age. and a size estimate of each of its non- The Hierarchical Insertion Algorithm. A node starts global clusters. The recipient uses this information to de- by performing a put on its level-2 cluster as in Section4.2, multiplex requests properly, i.e., a recipient should only so that other nearby nodes can take advantage of locality. consider a put and get for those levels on which it shares e initially built Coral a cluster with the sender. Additionally, this information block-box diffi culties in maintaining distinct clusters and the complex. drives routing table management: (I)nodes are added or ity of the subsequent system caused us to scrap the implementation. removed from the local cluster-specific routing tables ac-thus distributed among those stored, providing load bal￾ancing both within Coral and between servers using Coral. 4.3 Hierarchical Operations For locality-optimized routing and data placement, Coral uses several levels of DSHTs called clusters. Each level￾i cluster is named by a randomly-chosen 160-bit cluster identifier; the level-0 cluster ID is predefined as 0 160 . Re￾call that a set of nodes should form a cluster if their aver￾age, pair-wise RTTs are below some threshold. As men￾tioned earlier, we describe a three-level hierarchy with thresholds of ∞, 60 msec, and 20 msec for level-0, -1, and -2 clusters respectively. In Section 6, we present experi￾mental evidence to the client-side benefit of clustering. Figure 3 illustrates Coral’s hierarchical routing opera￾tions. Each Coral node has the same node ID in all clus￾ters to which it belongs; we can view a node as projecting its presence to the same location in each of its clusters. This structure must be reflected in Coral’s basic routing infrastructure, in particular to support switching between a node’s distinct DSHTs midway through a lookup.3 The Hierarchical Retrieval Algorithm. A requesting node R specifies the starting and stopping levels at which Coral should search. By default, it initiates the get query on its highest (level-2) cluster to try to take advantage of network locality. If routing RPCs on this cluster hit some node storing the key k (RPC 1 in Fig. 3), the lookup halts and returns the corresponding stored value(s)—a hit— without ever searching lower-level clusters. If a key is not found, the lookup will reach k’s closest node C2 in this cluster (RPC 2), signifying failure at this level. So, node R continues the search in its level-1 clus￾ter. As these clusters are very often concentric, C2 likely exists at the identical location in the identifier space in all clusters, as shown. R begins searching onward from C2 in its level-1 cluster (RPC 3), having already traversed the ID-space up to C2’s prefix. Even if the search eventually switches to the global cluster (RPC 4), the total number of RPCs required is about the same as a single-level lookup service, as a lookup continues from the point at which it left off in the identifier space of the previous cluster. Thus, (1) all lookups at the beginning are fast, (2) the system can tightly bound RPC timeouts, and (3) all pointersin higher￾level clusters reference data within that local cluster. The Hierarchical Insertion Algorithm. A node starts by performing a put on its level-2 cluster as in Section 4.2, so that other nearby nodes can take advantage of locality. 3We initially built Coral using the Chord [31] routing layer as a block-box; difficulties in maintaining distinct clusters and the complex￾ity of the subsequent system caused us to scrap the implementation. C2 C1 C2 C1 C0 C2 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 10 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 160−bit id space 11...11 level 2 k level 0 1 3 2 4 R R R level 1 1 00...00 1 0 Figure 3: Coral’s hierarchical routing structure. Nodes use the same IDs in each of their clusters; higher-level clusters are natu￾rally sparser. Note that a node can be identified in a cluster by its shortest unique ID prefix, e.g., “11” for R in its level-2 cluster; nodes sharing ID prefixes are located on common subtrees and are closer in the XOR metric. While higher-level neighbors usu￾ally share lower-level clusters as shown, this is not necessarily so. RPCs for a retrieval on key k are sequentially numbered. However, this placement is only “correct” within the con￾text of the local level-2 cluster. Thus, provided that the key is not already loaded, the node continues its insertion in the level-1 cluster from the point at which the key was inserted in level 2, much as in the retrieval case. Again, Coral traverses the ID-space only once. As illustrated in Figure 3, this practice results in a loose hierarchical cache, whereby a lower-level cluster contains nearly all data stored in the higher-level clusters to which its mem￾bers also belong. To enable such cluster-aware behavior, the headers of every Coral RPC include the sender’s cluster information: the identifier, age, and a size estimate of each of its non￾global clusters. The recipient uses this information to de￾multiplex requests properly, i.e., a recipient should only consider a put and get for those levels on which it shares a cluster with the sender. Additionally, this information drives routing table management: (1) nodes are added or removed from the local cluster-specific routing tables ac- 7