To minimize tree saturation, each iteration of a Coral In the forward phase, Corals routing layer makes re- search prefers to correct only b bits at a time. 2 More peated RPCs to contact nodes successively closer to the specifically, let splice(k, r, i) designate the most signifi- key. Each of these remote nodes returns(1) whether the cant bi bits of k followed by the least significant 160- bi key is loaded and (2)the number of values it stores under bits of r. If node R with Id r wishes to search for key the key, along with the minimum expiry time of any such k. R first initializes a variable t +r. At each iteration. values. The client node uses this information to determine R updates plice(h, t, i), using the smallest value if the remote node can accept the store, potentially evict- of i that yields a new value of t. The next hop in the ing a value with a shorter TTL. This forward phase ter- lookup path is the closest node to t that already exists in minates when the client node finds either the node closest Rs routing table. As described below, by limiting the use to the key, or a node that is full and loaded with respect of potentially closer known hops in this way, Coral can to the key. The client node places all contacted nodes that avoid overloading any node, even in the presence of very are not both full and loaded on a stack, ordered by XOR heavily accessed key distance from the ke The potential downside of longer lookup paths is higher During the reverse phase, the client node attempts to lookup latency in the presence of slow or stale nodes. In insert the value at the remote node referenced by the order to mitigate these effects, Coral keeps a window of top stack element, i.e., the node closest to the key. If multiple outstanding RPCs during a lookup, possibly con- this operation does not succeed-perhaps due to others acting the closest few nodes to intermediary targett insertions--the client node pops the stack and tries to in- sert on the new stack top. This process is repeated until a 4.2 Sloppy storage store succeeds or the stack is empty Coral uses a sloppy storage technique that caches This two-phase algorithm avoids tree saturation by stor- key/value pairs at nodes whose IDs are close to the key ing values progressively further from the key. Still, evic- tion and the leakage rate B ensure that nodes close to being referenced. These cached values reduce hot-spot the key retain long-lived values, so that live keys remain congestion and tree saturation throughout the indexing reachable: B nodes per minute that contact an interme- at nodes other than those closest to the key. This charac- diate node(including itself will go on to contact nodes teristic differs from DHTs, whose put operations all pro. closer to the key. For a perfectly-balanced tree, the keys ceed to nodes closest to the key closest node receives only(3·(2b-1)·「21)sore requests per minute, when fixing b bits per iteration The Insertion Algorithm. Coral performs a two-phase Proof sketch. Each node in a system of n nodes can be operation to insert a key/value pair. In the first, or"for- uniquely identified by a string S of log n bits. Consider ward, "phase, Coral routes to nodes that are successively s to be a string of b-bit digits. A node will contact the closer to the key, as previously described. However, to closest node to the key before it contacts any other node avoid tree saturation, an insertion operation may terminate if and only if its id differs from the key in exactly one prior to locating the closest node to the key, in which case digit. There are [(log n)/bl digits in S. Each digit can the key/value pair will be stored at a more distant node. take on 2-l values that differ from the key. Every node More specifically, the forward phase terminates whenever that differs in one digit will throttle all but B requests per the storing node happens upon another node that is both minute. Therefore, the closest node receives a maximum full and loaded for the key Irregularities in the node id distribution may increase 1. A node is full with respect to some key k when it this rate slightly, but the overall rate of traffic is still loga- stores I values for k whose TTls are all at least one- rithmic while in traditional DHTs it is linear. Section 6.4 half of the new value provides supporting experimental evidence 2. A node is loaded with respect to k when it has re- ceived more than the maximum leakage rate B re- The Retrieval Algorithm. To retrieve the value quests for k within the past minute ated with a key k, a node simply traverses the ID space with RPCs. When it finds a peer storing k, the remote In our experiments, l=4 and 6=12, meaning that un- peer returns k,'s corresponding list of values. The node ter- der high load, a node claims to be loaded for all but one minates its search and get returns. The requesting client store attempt every 5 seconds. This prevents excessive application handles these redundant references numbers of requests from hitting the key s closest nodes, application-specific way, e. g, CoralProxy contacts mul- yet still allows enough requests to propagate to keep val- tiple sources in parallel to download cached content ues at these nodes fresh Multiple stores of the same key will be spread over mul EXperiments in this paper use b= 1. tiple nodes. The pointers retrieved by the application areTo minimize tree saturation, each iteration of a Coral search prefers to correct only b bits at a time.2 More specifically, let splice(k, r,i) designate the most signifi- cant bi bits of k followed by the least significant 160 − bi bits of r. If node R with ID r wishes to search for key k, R first initializes a variable t ← r. At each iteration, R updates t ← splice(k,t,i), using the smallest value of i that yields a new value of t. The next hop in the lookup path is the closest node to t that already exists in R’s routing table. As described below, by limiting the use of potentially closer known hops in this way, Coral can avoid overloading any node, even in the presence of very heavily accessed keys. The potential downside of longer lookup paths is higher lookup latency in the presence of slow or stale nodes. In order to mitigate these effects, Coral keeps a window of multiple outstanding RPCs during a lookup, possibly con￾tacting the closest few nodes to intermediary target t. 4.2 Sloppy Storage Coral uses a sloppy storage technique that caches key/value pairs at nodes whose IDs are close to the key being referenced. These cached values reduce hot-spot congestion and tree saturation throughout the indexing in￾frastructure: They frequently satisfy put and get requests at nodes other than those closest to the key. This charac￾teristic differs from DHTs, whose put operations all pro￾ceed to nodes closest to the key. The Insertion Algorithm. Coral performs a two-phase operation to insert a key/value pair. In the first, or “for￾ward,” phase, Coral routes to nodes that are successively closer to the key, as previously described. However, to avoid tree saturation, an insertion operation may terminate prior to locating the closest node to the key, in which case the key/value pair will be stored at a more distant node. More specifically, the forward phase terminates whenever the storing node happens upon another node that is both full and loaded for the key: 1. A node is full with respect to some key k when it stores l values for k whose TTLs are all at least one￾half of the new value. 2. A node is loaded with respect to k when it has re￾ceived more than the maximum leakage rate β re￾quests for k within the past minute. In our experiments, l =4 and β =12, meaning that un￾der high load, a node claims to be loaded for all but one store attempt every 5 seconds. This prevents excessive numbers of requests from hitting the key’s closest nodes, yet still allows enough requests to propagate to keep val￾ues at these nodes fresh. 2Experiments in this paper use b = 1. In the forward phase, Coral’s routing layer makes re￾peated RPCs to contact nodes successively closer to the key. Each of these remote nodes returns (1) whether the key is loaded and (2) the number of values it stores under the key, along with the minimum expiry time of any such values. The client node uses this information to determine if the remote node can accept the store, potentially evict￾ing a value with a shorter TTL. This forward phase ter￾minates when the client node finds either the node closest to the key, or a node that is full and loaded with respect to the key. The client node places all contacted nodes that are not both full and loaded on a stack, ordered by XOR distance from the key. During the reverse phase, the client node attempts to insert the value at the remote node referenced by the top stack element, i.e., the node closest to the key. If this operation does not succeed—perhaps due to others’ insertions—the client node pops the stack and tries to in￾sert on the new stack top. This process is repeated until a store succeeds or the stack is empty. This two-phase algorithm avoids tree saturation by stor￾ing values progressively further from the key. Still, evic￾tion and the leakage rate β ensure that nodes close to the key retain long-lived values, so that live keys remain reachable: β nodes per minute that contact an interme￾diate node (including itself) will go on to contact nodes closer to the key. For a perfectly-balanced tree, the key’s closest node receives only ￾ β · (2b − 1) · d log n b e
store requests per minute, when fixing b bits per iteration. Proof sketch. Each node in a system of n nodes can be uniquely identified by a string S of log n bits. Consider S to be a string of b-bit digits. A node will contact the closest node to the key before it contacts any other node if and only if its ID differs from the key in exactly one digit. There are d(log n)/be digits in S. Each digit can take on 2 b−1 values that differ from the key. Every node that differs in one digit will throttle all but β requests per minute. Therefore, the closest node receives a maximum rate of ￾ β · (2b−1) · d log n b e
RPCs per minute. Irregularities in the node ID distribution may increase this rate slightly, but the overall rate of traffic is still loga￾rithmic, while in traditional DHTs it is linear. Section 6.4 provides supporting experimental evidence. The Retrieval Algorithm. To retrieve the value associ￾ated with a key k, a node simply traverses the ID space with RPCs. When it finds a peer storing k, the remote peer returns k’s corresponding list of values. The node ter￾minates its search and get returns. The requesting client application handles these redundant references in some application-specific way, e.g., CoralProxy contacts mul￾tiple sources in parallel to download cached content. Multiple stores of the same key will be spread over mul￾tiple nodes. The pointers retrieved by the application are 6