# Building Something Like BitTorrent Part 4: The Search Algorithm + The DHT Interface (Again)

## Search

We're ready to implement the search algorithm that we roughly covered in Part 2. The paper refers to this as "node lookup" and will be used across multiple DHT API functions. The general node lookup algorithm performs a search across the DHT for a given Key; the specific implementation will vary in each use case but the algorithm has a common procedure below:

node_lookup(Key key) {
    // concurrency parameter
    alpha = 3 
    
    // tracks which peers we've already contacted
    queried_peers = Set.empty()
    
    // gets the k closest peers to k in the local router
    closest_peers = closest_peers(router, key, k)
    
    // record the size and closest peer distance to key
    closest_dist = minimum([dist(peer, key) for peer in closest_peers]) 
    closest_size = len(closest_peers)
    while true {
        // only contact peers we haven't queried yet
        contact_peers = closest_peers.filter(p -> p not in queried_peers)
        
        // terminate if there aren't any remaining peers to query
        if len(contact_peers) == 0 {
            return
        }
    
        // concurrent find_node RPC requests
        for peer in contact_peers[:alpha] {
            queried_peers.add(peer)
            new_peers = find_node(peer, key) // sends find_node RPC to peer
            closest_peers.add(new_peers)
        }
        
        // filter down to the k closest peers to key
        new_closest_peers = sort_and_remove_duplicates(contact_peers)[:k]
    }
}

TLDR; after initializing the search peers from the router, on each iteration of the search algorithm we:
- filter out peers we've already contacted
- terminate if there aren't any uncontacted peers
- send concurrent find_node requests to $\alpha$ peers and incorporate the result into our cache of search peers
- filter down the cache of search peers to the $k$ unique peers closest to the key

This algorithm will be modified with a few tweaks in each of the use cases below.

## Implementing the DHT interface

Now we can revisit the DHT interface and describe each method's implementation.

### join
`join(Peer self, Peer other)`: a peer (self) joins an existing DHT using the advertised endpoint of another peer (other)

After sending a`ping` RPC to the remote peer to join the session, the local peer
- runs `node_lookup` against its own Key - this populates its Router with all peers close to its own Key
- runs `node_lookup` for a random peer in each bucket

### get
- `get(Peer self, Key k)`: retrieves the chunk associated with the key (`k`) in the DHT via a peer (self)

The local peer runs `node_lookup` with 2 modifications
- the local peer calls `find_value` instead of `find_node`
- once a remote peer returns an actual value (i.e., the corresponding Chunk) terminate and return the Chunk
- if `node_lookup` terminates without finding a value then this means the Key does not have a corresponding Chunk in the DHT

### insert
- `insert(Peer self, Chunk c)`: inserts a chunk \(c\) into the DHT via a peer (self)

The local peer
- runs `node_lookup` against the Chunk's Key to get the $k$ closest peers to the Key
- sends `store` RPCs to the $k$ closest peers to store the Chunk (and also stores it locally if the local peer is one of the closest peers)

### leave
- `leave(Peer self)`: a peer (self) leaves the DHT

In general the peer can just leave the session without sending any RPCs - however to ensure all Chunks are distributed/replicated correctly the local peer can "republish" each Chunk it has stored locally (republishing is the same operation as insert above)

## Other Considerations

Besides the clear interface above the paper also describes several running background threads used to make sure Chunks don't expire. This part of the paper didn't make too much sense to me - my implementation of the requirements is as follows [1]:
- each Chunk has two timestamps associated with it:
- `original_publish` (fixed) - the timestamp of when the Chunk was originally added to the DHT
- `latest_publish` (not fixed) - the timestamp of the last time the Chunk was republished
- there are 2 background threads running on each node:
- a `republish` thread filters all Chunks stored locally where `now() - latest_publish >= 3600 s` and republishes these Chunks
- a `cleanup` thread filters all Chunks stored locally where `now() - original_publish >= 86400 s` and removes the Chunks from local storage
- additionally there is 1 background thread running on each node that selects a random peer from each Router kbucket and runs a `node_lookup` on the peer (identical to the final operation in the `join` method above)

---

[1] My interpretation of the publish/cleanup requirements above is that
- republishing every 1 hour allows Chunks to be periodically rebalanced among nodes in the DHT in case the "correct" (closest) peers have changed
- Chunks are not long-lived objects in the DHT - they are discarded (to avoid the need of an explicit delete operation) and for long-lived applications like persistent file storage (i.e., what I'm implementing) the top-level application should periodically republish Chunks it wants to keep alive

I'm not sure why this second responsibility (republishing Chunks after 24 hrs) is punted up to the top-level application - I didn't implement it since I don't plan on running an actual distft application for longer than 24 hrs.