A quick review of distributed hash tables, and why they’re a pretty cool idea!
It is pretty easy to start taking a given tool, algorithm, idea, or technology for granted after you have become intimately familiar with it, use it frequently, or have known about it for a long time. It is similarly easy to start believing that, because you understand something well, it must be simple or boring. But every now and then, I’m reminded of the awesomeness of a tool or algorithm that has lost its luster for me along the way…
Recently, I had the privilege of participating in one of the best explanations of one such algorithm (Kademlia distributed hash tables), I have ever heard (Oli Evans’ explanation involved some hands-on role playing, and lots of really nice, intuitive examples), and it reminded me of just how ‘magical’ decentralized systems can be.
It also inspired me to revisit some of my old posts, to make sure I’d captured the essence of the algorithm(s). I found that I had glossed over a lot of the cool details, so in this article — which is perhaps the sequel to a previous article on adding data to IPFS — I’d like to explore what’s so cool about the IPFS DHT.
Distributed Hash Tables
IPFS and other decentralized content systems use something called a distributed hash table (DHT) to support routing and discovery of content and peers on the network. So when you hear someone say something like: “query the network”, “ask the network”, or “get it from the network”, what they’re actually saying is “query the distributed hash table”. This allows peers on the network to find content or peers without any centralized coordination. We’ve written about distributed hash tables in IPFS before, and even written a little bit about the underlying DHT algorithm(s) that IPFS uses.
As a quick refresher, jump on over to the Wikipedia article for Distributed Hash Tables — it gives a great overview of some core concepts, and also highlights many of the benefits of using a DHT. Also in that article, you’ll find this figure:
which describes a relatively simple decentralized data structure that provides similar functionality to a basic hash table (fast key/value pair lookup), where “keys are unique identifiers which map to particular values, which in turn can be anything from addresses, to documents, to arbitrary data”. You’ll also find that projects such as BitTorrent, IPFS, and others rely on DHTs to provide logically centralized access to content physically distributed across the Internet.
Quick recap: IPFS and similar projects use a (logically centralized) DHT to share information about who has what content, and where it can be retrieved from, on the network. Conceptually pretty simple. But how exactly this data structure is distributed across peers can vary greatly between implementations, so let’s dig a little deeper into that aspect of the system.
Currently, IPFS uses a variant of a Kademlia DHT (check out the paper if you want to dig into the details) for its routing etc (in particular, Kademlia with Coral DSHT and S/Kademlia extensions). So that we’re all on the same page, read this really great overview and explanation of Kademlia DHTs. It’s a little more technical than I’m aiming for here, but provides a lot of the necessary underlying knowledge to appreciate the algorithm(s). So go ahead, read that one, and then come back here for a final summary.
Ok, thanks for coming back. Now, one of the key features of the IPFS implementation of Kad-DHT, is that the Peer Ids are directly mapped to content Ids (CIDs), and that the peers actually store information about where to physically locate a given piece of content. This is great and all — I mean, we need to know where to fetch all those cat photos from — but what you might not ‘groc’ from the above article (or various other descriptions of Kademlia DHTs), is which peers store which bits of the DHT. In other words, how do we decide who stores a given Key/Value pair?
Who Stores What?
To assign key-value pairs to particular Peers, Kademlia relies on the notion of a distance between two identifiers. In particular, it uses the exclusive or (XOR) distance, which happens to be a useful general metric that is cheap to compute (and fun to say). But that’s not the cool part. The cool part is that since Keys and Peer Ids have the same format and length (the current default in IPFS is a SHA2–256 based multi-hash), ‘distance’ can be calculated among them in exactly the same way as distance can be computed between a given set of Peers or between a given set of CIDs. Why this is cool, is because it means that we can use this fact to decide where to store Key/Value pairs… we just store them in the ‘hash table’ of the Peer(s) that are XOR close to the Key being stored. Of course!
So in theory, if I’m trying to find the location of a given file with the CID QmHash, I simply need to find the Peer with the Id that is closest (in XOR distance) to QmHash. In practice, we might not be able to find the Peer with the closest Peer Id to QmHash, but it’ll be close-ish. Conceptually, this works by first querying Peers that I’m directly connected to see if they have QmHash, and if not, if they know of any Peers with an Id that is closer than theirs to QmHash. I’ll keep performing this query as I move through Peers with Ids that are closer and closer to QmHash. Eventually, I should end up at a Peer that is relatively close to QmHash, and that is storing the location of QmHash’s content. Then with that information in hand, my Peer will go and fetch the actual content behind QmHash. Done.
Obviously, there’s a lot more going on behind the scenes to make this magic work. For instance, you don’t want to store a given Key/Value pair just once in the DHT, otherwise, the second the Peer storing that Key/Value pair goes offline, we’ll lose that information. IPFS currently ensures sufficient redundancy by ‘putting’ a given Key/Value pair into the DHT ~20 times, spread across 20 different peers that are all relatively close to the given hash Key. Again, the cool thing about hash functions, XOR distances, and Kademlia in general, is that there’s no correlation between content, Peer Id, and hash values, so in general these Key/Value pairs should be uniformly randomly distributed across all active Peers in the network… without overburdening any one Peer in particular. As with all things its not quite that simple, as Kademlia prefers long-lived peers, but you get the idea.
What Did We Learn?
Honestly, we haven’t covered anything that hasn’t been said before. But I think sometimes the cleverness of something like Kademlia DHTs gets lost in the maze of other important concepts that one might want to learn about when one is learning about IPFS in general. I mean, we have directed acyclic graphs, layer upon layer of protocols, hashing algorithms, layers of encryption and PKI, and so much more to contend with. So hopefully you’ve managed to find something interesting in how DHTs (mostly) work. Re-learning things you already know about is such a good practice, and I know I benefited from doing it recently at IPFS Camp. So at the very least, I hope you’ll be inspired — as I was — to revisit some old concepts, and maybe rediscover why something you took for granted, was actually pretty cool.