1 of 50

Tapestry Gearup

CS1380: Distributed Systems S22

By: March & Arvind

Slides link available on Website

2 of 50

Motivations

Distributed key-value store implemented on top of a peer-to-peer routing system
Possible use cases: decentralized applications, Interplanetary File System
The peer-to-peer routing system is the main thing we want you to learn about

3 of 50

System Overview

Key-value pair

<K, V>

Node

1

Node

2

Node

3

Node

X

Node

Y

Well-known Root of K

Node

Z

Where is K?

K is here!

...

Node 3 tells me it has K.

Node storing <K,V>

FindRoot(k)

Publish(k)

Tapestry is a collection of nodes, where each node may only know about a subset of other nodes. Nodes store key-value pairs, and advertise themselves to nearby servers as owning a specific key. We will talk more about how they advertise later on, but some key concepts here:

Nodes may join and leave the network at any time.
Any node can advertise (publish) that they own some data, and must continuously publish this information as other nodes can join and leave
All nodes have a unique ID. The keys can be thought of as object IDs also.
To do lookups, nodes must use a custom protocol called FindRoot to identify a node who knows where the object is located. Important terminology: the root server is the server who knows where the publishing node is, not the publishing node. Here, Node 2 is the root server, but Node 3 is the publishing server.
FindRoot is a recursive resolver: it doesn’t identify the root server right away, it successively identifies better and better candidates for root server, asks them to identify better candidates, until finally we reach the actual root server, where the identification process terminates.

4 of 50

Data Structure Overview

Node A

BlobStore

Storing bytes of data. → <K, V>

LocationMap

Key K1 is stored at Node X1
Key K2 is stored at Node X2
...

Routing Table

Backpointers

Node B

BlobStore
LocationMap
Routing Table
Backpointers


	Node B


Node A

Nodes have four major components:

The data storage itself. We represent this as the BlobStore. Blobs here just mean that the data that is stored is not typed - we don’t store “hashes”, or “lists”, or “sets”, we just store the raw binary representation of data itself as a collection of bytes. For this project, the data storage layer has been given to you.
The root server’s knowledge of who is publishing what. This is represented by the LocationMap. When a node discovers it is the root server for a query, it means, it is responsible for consulting LocationMap and returning the address of the server that actually contains the data. Since any node can be a root server for other nodes, every node must have a LocationMap. LocationMap is an expiring cache so the map values are not guaranteed to exist at all times - this is done because it is expected other nodes will die and prevents us from storing obsolete data - publishing nodes must always republish themselves to the root server so that this cache is kept fresh. For this project, the LocationMap layer has been given to you, but the mechanics of initial and periodic data publication or republication to a root server is something you have to implement
The routing table. This is the linchpin of the entire system. Queries for data can be received on any node, and nodes must consult this table to discover who the root server is. Only when the lookup discovers we are the root server do we consult the LocationMap. Routing tables are built by nodes communicating and sharing their knowledge with each other. The routing table itself is a three-dimensional array - we’ll go over what it looks like in more detail further on. This is the main part of the project you will implement. You are responsible for populating it, depopulating it and deciding when you’re a root server from it. We’ll go over some of the main components below.
The backpointers set. Backpointers are the main failure-prevention mechanism in Tapestry. A backpointer is “just” a node address, but it is stored in a very specific way: if Node A decides to store Node B in its routing table, Node A should always ask node B to put A in B's backpointer set. If Node A decides to remove Node B from its routing table, Node A should always ask node B to remove A from B's backpointer set. You can think of B’s backpointer list as a list of nodes that rely on you to be around. When node B shuts down, it can tell node A to forget it exists and purge it from the routing table. Backpointers are really useful as they let you separate the question of existence of node from liveness of node, which we’ve previously seen were tightly coupled when using heartbeats. Note that nodes can still die in such a way that they fail to notify their backpointers - perhaps a network partition happened at the time - so that’s something you have to work around also.

5 of 50

Finding Root: FindRoot(id ID, level int32)

Finds root node of key (via FindRootRPC), also returns a set of nodes to remove

First check local Routing Table for nextHop
If nextHop is self, then local node is the root. Return
Else call FindRootRPC on nextHop
If timeout or error on FindRootRPC to nextHop, remove nextHop from local Routing Table and add nextHop to removeNodes set → Important for notifying upstream nodes of nodes to remove from their routing tables. GOTO step 1
Remove nodes from Routing Table that are returned from FindRootRPC

6 of 50

Finding Root: FindRoot(id ID, level int32)

Local Node

Tap 1 (ID: 01)

Tap 2 (ID: 21)

Tap 3 (ID: 22)

FindRoot(12, 0)

	0	1	2
xx	01		21
0x		01

	0	1	2
xx	01		21
2x		21	22

	0	1	2
xx	01		22
2x		21	22

Check local Routing Table for nextHop

So it seems FindRoot is all about consulting the routing table. Here you see three different routing tables corresponding to three different nodes with different IDs. The way we use the level argument is very crucial here. Level always starts at 0 on the first node you query.. It is incremented on every subsequent FindRootRPC call. Note that you could set level on the first node to be the shared prefix length of the key ID and the node ID - that also works, (and in this example would lead to the same outcome)

The routing table is just a 3d table - you should all be very familiar with it by now, but just to ensure we all know it - the rows correspond to the possible lengths of shared prefixes between any two nodes. This can go from 0 to at most (node ID length - 1); the columns correspond to the digits in the base we are using. If we use hexadecimal, there are 16 digits and so 16 columns. Remember length does not depend on base, you can have 100-digit long hex strings and 40-digit long hex strings, so the routing table can grow vertically downwards. One special feature here is that we don’t store just one node in a single cell, we actually store multiple nodes in a single cell. These are all sorted by `Closer` function, and we’ve shared the algorithm for that in the handout.

7 of 50

Finding Root: FindRoot(id ID, level int32)

Local Node

Tap 1 (ID: 01)

Tap 2 (ID: 21)

Tap 3 (ID: 22)

FindRoot(12, 0)

	0	1	2
xx	01		21
0x		01

	0	1	2
xx	01		21
2x		21	22

	0	1	2
xx	01		22
2x		21	22

Check local Routing Table for nextHop

12

8 of 50

Finding Root: FindRoot(id ID, level int32)

Local Node

Tap 1 (ID: 01)

Tap 2 (ID: 21)

Tap 3 (ID: 22)

FindRoot(12, 0)

	0	1	2
xx	01		21
0x		01

	0	1	2
xx	01		21
2x		21	22

	0	1	2
xx	01		22
2x		21	22

Check local Routing Table for nextHop

12

nextHop

9 of 50

Finding Root: FindRoot(id ID, level int32)

Local Node

Tap 1 (ID: 01)

Tap 2 (ID: 21)

Tap 3 (ID: 22)

FindRoot(12, 0)

	0	1	2
xx	01		21
0x		01

	0	1	2
xx	01		21
2x		21	22

	0	1	2
xx	01		22
2x		21	22

FindRootRPC to nextHop

12

nextHop

tap2.FindRootRPC(12, 1)

FindRoot(12, 1)

10 of 50

Finding Root: FindRoot(id ID, level int32)

Local Node

Tap 1 (ID: 01)

Tap 2 (ID: 21)

Tap 3 (ID: 22)

FindRoot(12, 0)

	0	1	2
xx	01		21
0x		01

	0	1	2
xx	01		21
2x		21	22

	0	1	2
xx	01		22
2x		21	22

Check local Routing Table for nextHop

12

nextHop

tap2.FindRootRPC(12, 1)

FindRoot(12, 1)

12

nextHop

11 of 50

Finding Root: FindRoot(id ID, level int32)

Local Node

Tap 1 (ID: 01)

Tap 2 (ID: 21)

Tap 3 (ID: 22)

FindRoot(12, 0)

	0	1	2
xx	01		21
0x		01

	0	1	2
xx	01		21
2x		21	22

	0	1	2
xx	01		22
2x		21	22

FindRootRPC to nextHop

12

nextHop

tap2.FindRootRPC(12, 1)

FindRoot(12, 1)

12

nextHop

tap3.FindRootRPC(12, 2)

FindRoot(12, 2)

2 >= DIGITS → ROOT!

12 of 50

Finding Root: FindRoot(id ID, level int32)

Local Node

Tap 1 (ID: 01)

Tap 2 (ID: 21)

Tap 3 (ID: 22)

FindRoot(12, 0)

	0	1	2
xx	01		21
0x		01

	0	1	2
xx	01		21
2x		21	22

	0	1	2
xx	01		22
2x		21	22

Return root

12

nextHop

tap2.FindRootRPC(12, 1)

FindRoot(12, 1)

12

nextHop

tap3.FindRootRPC(12, 2)

FindRoot(12, 2)

2 >= DIGITS → ROOT!

Root = tap3 (ID: 22)

13 of 50

Storing Object: Store(key string, value []byte)

Publish key

Find root node of key (FindRootRPC)
Register local node and object key with root node (via RegisterRPC(key string, replica RemoteNode))

When root node receives RegisterRPC request, confirm that it is root of key (remember to hash key)
If root node is indeed root of key, register key and replica to its LocationMap (via LocationMap.Register(key string, replica RemoteNode, timeout time.Duration))
Return to caller whether root node was the root of the key

Let’s talk about publishing data. Any node may store data locally - a client can ask any node in the system to do this. Storing data is easy - you just save it locally to your own BlobStore, it requires no fancy mechanics. The most interesting part is when you start advertising the key to other nodes. Here, the node that’s publishing the data has no control over what data it stores, but it does have control over identifying who the likelist root server is - it does the same algorithm FindNextHop did, and finds out who the candidate root server is. It then tells this candidate root server that it owns this key (using RegisterRPC) - note that the root server this node thinks may not be the best root server overall, though, so this candidate root server also does FindNextHop, and returns the next root server, and so on. Note how similar lookup and publishing is - they both compute root servers and try to make them the final authority in the system. This core concept of comparing prefixes of object hashes with server hashes is very similar to consistent hashing, which we’ve covered in class - it allows you to ensure every node, whether it is publisher or lookup, can converge on the same node for final answers.

But let’s continue. Once the root is found, the root stores the value in its location map. Since the root server can die, the node must continuously run Publish in a separate goroutine, so that newer root servers learn about this data. We also allow clients to remove data from this node, so we give them a cancel chan that will stop this goroutine from publishing. Importantly, cancelling only cancels republication - it does not actually remove data or notify the root servers that it is no longer hosting the data, that is done separately.

14 of 50

Storing Object: Store(key string, value []byte)

Publish key

Find root node of key (FindRootRPC)
Register local node and object key with root node (via RegisterRPC(key string, replica RemoteNode))

When root node receives RegisterRPC request, confirm that it is root of key (remember to hash key)
If root node is indeed root of key, register key and replica to its LocationMap (via LocationMap.Register(key string, replica RemoteNode, timeout time.Duration))
Return to caller whether root node was the root of the key

If error on initial publish (e.g Cannot contact root or root was not actually the root), propagate error
Periodically publish key on a ticker on a separate goroutine
Return to user a cancel chan that allows local node storing object to stop publishing

Store object in local node’s BlobStore

Let’s talk about publishing data. Any node may store data locally - a client can ask any node in the system to do this. Storing data is easy - you just save it locally to your own BlobStore, it requires no fancy mechanics. The most interesting part is when you start advertising the key to other nodes. Here, the node that’s publishing the data has no control over what data it stores, but it does have control over identifying who the likelist root server is - it does the same algorithm FindNextHop did, and finds out who the candidate root server is. It then tells this candidate root server that it owns this key (using RegisterRPC) - note that the root server this node thinks may not be the best root server overall, though, so this candidate root server also does FindNextHop, and returns the next root server, and so on. Note how similar lookup and publishing is - they both compute root servers and try to make them the final authority in the system. This core concept of comparing prefixes of object hashes with server hashes is very similar to consistent hashing, which we’ve covered in class - it allows you to ensure every node, whether it is publisher or lookup, can converge on the same node for final answers.

But let’s continue. Once the root is found, the root stores the value in its location map. Since the root server can die, the node must continuously run Publish in a separate goroutine, so that newer root servers learn about this data. We also allow clients to remove data from this node, so we give them a cancel chan that will stop this goroutine from publishing. Importantly, cancelling only cancels republication - it does not actually remove data or notify the root servers that it is no longer hosting the data, that is done separately.

15 of 50

Storing Object: Store(key string, value []byte)

Local Node

Tap 1

Tap 2

Tap 3

Tapestry CLI: Store(key string, value []byte)

16 of 50

Storing Object: Store(key string, value []byte)

Tapestry CLI: Store(key string, value []byte)

Local Node

Tap 1

Tap 2

Tap 3

1. Publish Key

publish(key)

17 of 50

Storing Object: Store(key string, value []byte)

Tapestry CLI: Store(key string, value []byte)

Local Node

Tap 1

Tap 2

Tap 3

2. Find root of key

publish(key)

findRootOnRemoteNode(local.node, key)

18 of 50

Storing Object: Store(key string, value []byte)

Tapestry CLI: Store(key string, value []byte)

Local Node

Tap 1

Tap 2

Tap 3

3. FindRootRPC

publish(key)

findRootOnRemoteNode(local.node, key)

FindNextHop?

FindRootRPC

19 of 50

Storing Object: Store(key string, value []byte)

Tapestry CLI: Store(key string, value []byte)

Local Node

Tap 1

Tap 2

Tap 3

3. FindRootRPC

publish(key)

findRootOnRemoteNode(local.node, key)

FindNextHop?

FindRootRPC

20 of 50

Storing Object: Store(key string, value []byte)

Tapestry CLI: Store(key string, value []byte)

Local Node

Tap 1

Tap 2

Tap 3

3. FindRootRPC

publish(key)

findRootOnRemoteNode(local.node, key)

FindNextHop?

FindRootRPC

FindNextHop?

FindNextHop?�

Nope.�We are the root!

Register key to LocationMap

FindRootRPC

21 of 50

Storing Object: Store(key string, value []byte)

Tapestry CLI: Store(key string, value []byte)

Local Node

Tap 1

Tap 2

Tap 3

3. FindRootRPC

publish(key)

root := findRootOnRemoteNode(local.node, key)

FindNextHop?

FindRootRPC

FindNextHop?

FindNextHop?�

Nope.�We are the root!

Register key to LocationMap

FindRootRPC

Root

22 of 50

Storing Object: Store(key string, value []byte)

Tapestry CLI: Store(key string, value []byte)

Local Node

Tap 1

Tap 2

Tap 3

4. RegisterRPC

publish(key)

root := findRootOnRemoteNode(local.node, key)

FindNextHop?

FindRootRPC

FindNextHop?

FindNextHop?�

Nope.�We are the root!

Register key to LocationMap

FindRootRPC

Root

root.RegisterRPC(key, local.node)

RegisterRPC

23 of 50

Storing Object: Store(key string, value []byte)

Tapestry CLI: Store(key string, value []byte)

Local Node

Tap 1

Tap 2

Tap 3

4. RegisterRPC

publish(key)

root := findRootOnRemoteNode(local.node, key)

FindNextHop?

FindRootRPC

FindNextHop?

FindNextHop?�

Nope.�We are the root!

Register key to LocationMap

FindRootRPC

Root

root.RegisterRPC(key, local.node)

RegisterRPC

Yup, we’re the root of this key

return true

24 of 50

Storing Object: Store(key string, value []byte)

Tapestry CLI: Store(key string, value []byte)

Local Node

Tap 1

Tap 2

Tap 3

4. Republish

publish(key)

root := findRootOnRemoteNode(local.node, key)

FindNextHop?

FindRootRPC

FindNextHop?

FindNextHop?�

Nope.�We are the root!

Register key to LocationMap

FindRootRPC

Root

root.RegisterRPC(key, local.node)

RegisterRPC

Yup, we’re the root of this key

return true

Republish = publish → Cannot simply just call RegisterRPC for Republish. Must first find Root of Object on every Republish and then call RegisterRPC

Periodically republish

25 of 50

Joining Node: Join(otherNode RemoteNode)

Find Root for joining Node
AddNodeRPC to Root node
Joining node receives neighbor set in response to AddNodeRPC
Add neighbor set to joining Node routing table
Populate rest of joining Node Routing Table by getting backpointers of neighbor set

26 of 50

Joining Node: Join(otherNode RemoteNode)

Local Node

Tap 1 (Joining Node)

Tap 2

Tap 3

Join(Tap2)

1. Find Root for joining Node

27 of 50

Joining Node: Join(otherNode RemoteNode)

Local Node

Not root

Root!

Tap 1 (Joining Node)

Tap 2

Tap 3

Join(Tap2)

1. Find Root for joining Node

tap2.FindRootRPC(tap1ID, 0)

tap3.FindRootRPC(tap1ID, 1)

28 of 50

Joining Node: Join(otherNode RemoteNode)

Local Node

Not root

Root!

Tap 1 (Joining Node)

Tap 2

Tap 3

Join(Tap2)

root := tap3

1. Find Root for joining Node

tap2.FindRootRPC(tap1ID, 0)

tap3.FindRootRPC(tap1ID, 1)

Root = tap3

29 of 50

Joining Node: Join(otherNode RemoteNode)

Local Node

Not root

Root!

Tap 1 (Joining Node)

Tap 2

Tap 3

Join(Tap2)

root := tap3

2. AddNodeRPC to Root Node

tap2.FindRootRPC(tap1ID, 0)

tap3.FindRootRPC(tap1ID, 1)

Root = tap3

root.AddNodeRPC(local.Node)

30 of 50

Joining Node: Join(otherNode RemoteNode)

Root!

Tap 3

root.AddNodeRPC(local.Node)

3. AddNodeMulticast

AddNodeMulticast(newNode, level)

targets = routingtable.get(level) // Must include local node

results = []

for target in targets

results.append(target.AddNodeMulticast(newNode, level + 1))

self.addRoute(newNode)

transferRelevantObjects(newNode)

return merge(results, targets)

31 of 50

Joining Node: Join(otherNode RemoteNode)

Root!

Tap 3

	0	1	...
xx...	...	..	..
1x…	..	..	..
11x..	110..		112..

P := SharedPrefix(self, addNode)

3. AddNodeMulticast

Get shared prefix with addNode

root.AddNodeRPC(local.Node)

32 of 50

Joining Node: Join(otherNode RemoteNode)

Root!

Tap 3

	0	1	...
xx...	...	..	..
1x…	..	..	..
11x..	110..		112..

P := SharedPrefix(self, addNode)

3. AddNodeMulticast

110..

112..

...

AddNodeMulticastRPC(addNode, P + 1) to all nodes at level P in local RT

Why P+1? Why not P?

root.AddNodeRPC(local.Node)

33 of 50

Joining Node: Join(otherNode RemoteNode)

Root!

Tap 3

	0	1	...
xx...	...	..	..
1x…	..	..	..
11x..	110..		112..

P := SharedPrefix(self, addNode)

3. AddNodeMulticast

110..

112..

...

AddNodeMulticastRPC(addNode, P + 1) to all nodes at level P in local RT

Repeat AddNodeMulticastRPC for next level down

root.AddNodeRPC(local.Node)

34 of 50

Joining Node: Join(otherNode RemoteNode)

Root!

Tap 3

	0	1	...
xx...	...	..	..
1x…	..	..	..
11x..	110..		112..

P := SharedPrefix(self, addNode)

3. AddNodeMulticast

110..

112..

...

AddNodeMulticastRPC(addNode, P + 1) to all nodes at level P in local RT

Repeat AddNodeMulticastRPC for next level down

Continue AddNodeMulticastRPC until last level

root.AddNodeRPC(local.Node)

And we continue until the last level at this node. Remember that we’re looking at this diagram in the context of the surrogate root node, but since at each level we’re triggering the multicast on all nodes in that level on this node and so forth, we’ll eventually contact all nodes that share the common prefix length with the new node.

All of these contacted nodes are need to know nodes, or current nodes in the network with a missing cell that this new node fills in. Remember that the tapestry network is like a tree, we start at some the surrogate root node since it has the maximum overlap with the new node, and then we go down the tree.

Nodes upstream don't need to know, because the root node likely already fills a spot in their table, so upstream nodes do not need to know that a new node has joined the network

35 of 50

Joining Node: Join(otherNode RemoteNode)

Root!

Tap 3

	0	1	...
xx...	...	..	..
1x…	..	..	..
11x..	110..		112..

P := SharedPrefix(self, addNode)

3. AddNodeMulticast

Reached end of routing table

In the last step:

Add addNode to local routing table
Transfer applicable Location Map objects from self to addNode

root.AddNodeRPC(local.Node)

36 of 50

Joining Node: Join(otherNode RemoteNode)

Root!

Tap 3

	0	1	...
xx...	...	..	..
1x…	..	..	..
11x..	110..		112..

P := SharedPrefix(self, addNode)

3. AddNodeMulticast

Wait for all downstream AddNodeMulticastRPC to finish

...

Return neighbors

110..

112..

root.AddNodeRPC(local.Node)

37 of 50

Joining Node: Join(otherNode RemoteNode)

Populate local Routing Table at level P with initial neighbor set

Local Node

Tap 1 (Joining Node)

neighbors := root.AddNodeRPC(local.Node)

4. Construct New Routing Table

	0	1	...
xx...
1x…
P	..	..	..

P := SharedPrefix(self, addNode)

Neighbors

38 of 50

Joining Node: Join(otherNode RemoteNode)

Local Node

neighbors := root.AddNodeRPC(local.Node)

5. Populate rest of Routing Table (Levels: P → 0) (Backpointer Traversal)

	0	1	...
xx...
1x…
P	..	..	..

P := SharedPrefix(self, addNode)

From the entire neighbors set, trim to K closest unique keys, as determined by Closer() (but do not modify Routing Table)
For each neighbor after trimming, call neighbor.GetBackpointersRPC(self, P)

Tap 1 (Joining Node)

39 of 50

Joining Node: Join(otherNode RemoteNode)

Local Node

neighbors := root.AddNodeRPC(local.Node)

5. Populate rest of Routing Table (Levels: P → 0) (Backpointer Traversal)

	0	1	...
xx...
1x…
P	..	..	..

P := SharedPrefix(self, addNode)

From the entire neighbors set, trim to K closest unique keys, as determined by Closer() (but do not modify Routing Table)
For each neighbor after trimming, call neighbor.GetBackpointersRPC(self, P)
Result will be used to populate the whole table
Append result to neighbors set
Decrement level; GOTO step 1

Tap 1 (Joining Node)

40 of 50

Joining Node: Join(otherNode RemoteNode)

Local Node

neighbors := root.AddNodeRPC(local.Node)

Tap 1 (Joining Node)

6. Populate Backpointers

During AddNodeMulticast, whenever a remote node added local node to its Routing Table, it called joiner.AddBackpointerRPC(self)

This is implemented in addRoute()

41 of 50

Debugging

Delve: basically a GDB for Golang
Checkout lab 2
go tool trace, not covered in lab 2, but is also helpful. Run in the same way as pprof

go test -run <test name> -trace trace.out
go tool trace trace.out

trace demo

42 of 50

gRPC

Lab 3 handout on gRPC will be released early (likely around March 1-2) with the original due date in case you need a reference to gRPC for Tapestry
"Context Deadline Exceeded" error in gRPC

generic error, means that the caller timed out waiting for a reply from callee
go tool trace can help with debugging these errors

43 of 50

Tapestry Paper

https://sites.cs.ucsb.edu/~ravenben/classes/papers/tapestry-jsac04.pdf
Reading paper is hard
three passes approach

how to read a paper
first pass -> general idea ~ 10 minutes
second pass -> key points ~ 1 hour
third pass (if needed to) -> in depth analysis

44 of 50

Closing Remarks

Expected lines of code: 500 ~ 700

→ Start early!

→ Read the handout/paper!

→ Come to TA hours.

→ Project Due: Sunday March 11th, 11:59 PM

45 of 50

FAQs from Years Past

How does FindNextHop(id, level) work?

Jump to row number level
Find the cell corresponding to id[level]th digit (assuming 0-indexing!)
Scan a row starting from here for the first remote node you can get; if you only find the local node first in that row, jump down to the next row and repeat
If you run out of rows, return the local node

In a particular slot in a row, the nodes in the slot should already be sorted by Closer()

46 of 50

FAQs from Years Past

How does id.IsNewRoute(newId, currentId) work?

From code comment: Given IDs newId and currentId, will id now route to newId?

Let i be an index variable.
Keep comparing newId[i] to currentId[i] until newId[i] != currentId[i]
When newId[i] != currentId[i] (i.e. when their shared prefix is exhausted), then

Compare ((newId[i] - id[i]) modulo BASE) to ((currentId[i] - id[i]) modulo BASE)
The one with the smaller value in the previous comparison is what you return

47 of 50

FAQs from Years Past

From the paper: N uses the neighbor set to fill routing level p, trims the list to the closest k nodes and requests these nodes send their backpointers. What measure of closeness should we use for the k nodes during this backpointer traversal stage?

> Use Closer()!

48 of 50

FAQs from Years Past

Remove/AddBackpointer RPC clarifications:

If AddBackpointerRPC fails, remove the new node from the routing table and add the evicted node back (if there is one). Here "evicted" node is the node removed by RoutingTable.Add() when slot capacity is exceeded.

When RemoveBackpointerRPC is called on an evicted node, you can ignore the error returned.

49 of 50

FAQs from Years Past

FindRootonRemoteNode vs. FindRoot:

FindRoot traverses the routing table of the node locally
FindRootOnRemoteNode asks a remote node to traverse their routing table remotely and return the results

Implemented with FindRootRPC
Level argument to FindRootRPC should be zero
This function is used by new nodes when they’re just joined since they have an empty routing table.

50 of 50

FAQs from Years Past

FindRoot has an argument `toRemove`. When should list of nodes in `toRemove` be removed in FindRoot?

When FindRoot makes recursive calls, all the toRemove sets returned are

removed from the local routing table, and
merged and returned to caller.�

The initial invoker of FindRoot (e.g. in Publish) can disregard toRemove.

tl;dr toRemove sets returned by all subcalls should be merged, removed and returned