Holochain Forum

DHT: rrDHT and Kademlia

Anything new in rrDHT? How is it different than KademliaDHT? Is the routing/searching algorithms are different?

1 Like

Hi @premjeet and welcome to the forum! Nice to see your familiar username.

The Holochain team started out with Kademlia, as you probably know, but felt like it wasn’t all that suited to their neighbourhood-based design. I don’t know all the details, so here is my understanding.

Here are some things that did work with Kademlia:

  • Peer selection for holding data is random (based on unpredictable output of hash function), which is great for randomised peer validation
  • Peers are sorted into neighbourhoods (overlapping shards) and know about more nearby peers than about faraway peers (but still keep a small list of faraway peers, which speeds lookup/discovery)

But there was just a bit of mismatch in how Kademlia’s neighbourhoods work, particularly as regards Holochain’s assumptions of resilience (a neighbourhood knows about each other and communicate regularly about data health). Nothing insurmountable — Holochain stuff could be bolted on — but they started to feel like they were working against Kademlia, not with it.

rrDHT takes Holochain’s agent-centric assumptions and embeds them deep into the design. The address space looks like a wheel, and (as with Kademlia) agents and data live in the same address space. Each agent has:

  • a ‘storage arc’, which is the portion of the DHT in which the agent claims to know about all data and enough peers whose storage arcs overlap
  • a ‘query arc’, which is the portion of the DHT in which the agent claims to know about enough peers whose storage arcs overlap
  • a few faraway peers to speed lookup times

The storage and query arcs can be thought of as small and large neighbourhoods. In the small neighbourhood, everyone knows each other well, takes care of each other, shovels snow off each other’s sidewalks, watches out for burglars, etc. And each person has a different opinion of who their close neighbours are — I might extend that status to someone seven houses away, but they might not extend the same status to me because they’re hardly ever home. In rrDHT terms, I might have more storage space and bandwidth but that person five houses away is just a smartphone and doesn’t have much resources to give away.

The large neighbourhood consists of the area where I know my way around, I know the street names, and I know who lives in each house. But we don’t look out for each other in the same way.

Within the small neighbourhood, agents gossip with each other to maintain resilience: if one of them goes offline, the others will try to contact slightly more distant neighbours to bring them into the small neighbourhood.

You can see a very oversimplified (and hence not 100% accurate) explanation here in some introductory material I’m writing: https://hackmd.io/JmPpIE0lT7qD8BYOaO6Lyw

5 Likes

Thanks @pauldaoust. So it’s more dynamic, multi-dimensional and like geometricDHT! It works with Chord, Am I correct?

@premjeet I’ve never heard of geometricDHT; please share more!

rrDHT is very Chord-like in its geometry, and there are some similarities in lookup method, but rrDHT appears to me to be much more flexible, and perhaps more resilient too. Chord doesn’t specify a resilience strategy but appears to suggest that nodes can map the neighbourhood around them in case one of their peers gets unreliable. rrDHT, on the other hand, is explicit about how to maintain resilience. Lookups should also be a bit faster; nodes can search both clockwise and counterclockwise at the same time.

1 Like

What’s rrDHT? Has this been built in-house or is it something external that is being used? :slight_smile: All sounds very interesting thanks… :slight_smile:

rrDHT is Holochain’s DHT implementation. It’s currently being built in-house.

1 Like

This was exactly what I was curious about regarding small-world networks in another post. Awesome!

1 Like

What does the rr stand for? :slight_smile:

rr = round robin
“Round Robin” Distributed Hash Table (rrDHT)

1 Like

Oh, of course! Thanks :wink:

We’ve also heard people calling it ‘roadrunner’ because theoretically it’s very fast :wink:

1 Like

cool, look forward to hearing more about it… is it in the latest builds yet? :slight_smile:

Not sure, to be honest — I’ve been trying to track networking development, and it’s hard because I don’t understand the language :sweat_smile: but my general impression is that most of the networking lib is still ‘full-sync’ (everyone gets a copy of everything) and there are a few rrDHT-ish components in R&D.