DHTs - illustrating how they work as an evolution

A WIP, feel free to ask questions, clarifications, give suggestions etc.

HashTables

HashTables are essentially key-value storage and retrieval systems. They work by basically hashing a key (O(1) operation for small keys) and then doing inserts/deletes into an array of buckets (also O(1)).

Distributing the Hash Tables

Instead of having an array stored in memory that backs the hash table let’s have an array but where each machine is a slot in the array. We now have an O(1) distributed hash table

Dynamically Growing and Shrinking the Network

Unfortunately, the above scheme does not allow the network to grow/shrink dynamically just as arrays cannot grow/shrink dynamically.

To support this we could swap out using an array as the backing data structure for the hashtable with a linked-list. Unfortunately, finding the i-th peer in a linked-list is O(N) instead of the O(1) that an array would take

Making Linked Lists Faster

Just as with standard linked lists we can use mechanisms such as skip lists which work essentially by giving each element in the linked list links to nodes that are exponentially far away from it (e.g. 1,2,4,8,16....) so that walking to the k-th peer takes log(N) time. This then gives us an O(log(N)) DHT.

Some Numbers for Intuition

Lookups should take log_k(N), which in the IPFS Public DHT k=20 and N is currently around 10-20000 so lookups should take ~3 hops/sequential queries. Hops (i.e. a libp2p connection and sending an initial message and receiving the response) should be in the several hundred ms range for a 100ms roundtrip-time (assuming nodes respond to requests quickly)

This means we should be expecting no more than a couple seconds for lookups. That it’s more than this means the implementation has problems. In the case of the standard go-libp2p-kad-dht implementation the biggest issue is not terminating queries early enough and waiting on nodes to respond that are not going to respond.

Caching ... it’s Good!

Say there are 10,000 nodes in the network and we need to make 10M queries. How many network hops should we need to make?

The answer is not log_20(10000) * 10 M = 3 * 10M = 30M since there are only 10000 nodes total in the network. Once we learn all 10000 nodes in the network we are back in the array backed hashtable world and do not need to make any more network requests to learn about the network.

If we need to make 10M queries we then need ~10k + 10M ~ 10M requests, not 30M.

Note: as with everything with caching it’s good, but you need to worry about having a good cache invalidation strategy

Algorithmic Sympathies ... They’re Also Good