Kademlia RecordStore

[jnicholls]

I'll start by suggesting that this may be a naive question as I am not intimately familiar with the overall Kademlia protocol...so please bear with me :)

Premise

I'm looking to implement a DHT that will have an arbitrarily large number of keys...say, in the millions. In practice, I expect the key space to be distributed over a wide number of nodes, but initially and in contrived testing scenarios, they will be only on a handful of nodes. Additionally, this DHT will only be storing provider information, i.e. "for key X, you can connect to peer Y to go get it." It will not be storing nor obviously serving data records itself. So think of it as only being used as a routing table for keys.

Situation

Looking at the rust-libp2p implementation of KAD-DHT, I'm seeing this concept of a RecordStore that stores both Records and ProviderRecords. This trait has one canned implementation, MemoryStore. Looking at the definition of RecordStore and the implementation of MemoryStore and its default configuration, I noticed a few things:

1. MemoryStore's default configuration is fairly constrained, i.e. a small max number of keys and providers.
2. RecordStore operations are defined to only be fallible in ways that exceed configured constraints (number of keys/providers, size of value). It doesn't allow for any other implementation-defined fallibility semantics.

Problem

Due to my premise, where I will have many many keys, and any particular node could serve an arbitrarily high number of these keys (including all of them), I am running into a few issues with the current implementation.

First, MemoryStore's default config is obviously too low. Bumping that number up is easy enough. But, it begs the question why have integrated constraints like this at all? Is there protocol-level semantics for "value too large" and "max keys reached" or was that just a rust-libp2p decision, and really there could be any implementation-defined way a key may fail to store/be retrieved/etc.?

Second, as mentioned each node will potentially be providing a large number of keys. It is safe to assume that this list of keys will be fairly expensive to re-load into memory every time the node starts up and joins the network. So rather than using the MemoryStore, I wanted to implement my own RecordStore backed by something persistent, like RocksDB. A node will always have a consistent view of what keys it can provide to the rest of the DHT network, and I thought it might be prudent to have a RecordStore implementation that could persist and stay consistent with that view; if the node is recycled (e.g. an upgrade to the software) it can pick back up where it left off without an expensive startup to prime the RecordStore.

Well, that isn't very conducive given the current RecordStore trait definition, going back to my earlier point. The trait methods are defined as if they could never fail, with the exception of the "too large"/"too many" constraints. So if I fail to load up my underlying persistent store, fail to retrieve a key, fail to store a key, etc...with the current trait definition, those errors would have to be silently ignored. And given that a DHT has to be robust and self-correcting anyways, that's probably fine conceptually. But still, I wondered why the trait is designed the way it currently is, if not for that exact reason?

Lastly, I wonder if what I am doing is completely ludicrous for KAD-DHT. I figured if it can power IPFS, it would certainly work for my use case. Surely IPFS has some notion of persistent state for its DHT and what keys a node advertises as a provider. Is there another approach I should take with KAD-DHT instead? I essentially am only going to use it for two operations:

1. Each time a key is available on a node, I'll call Kademlia::start_providing. And many nodes will do the same for the same key.
2. Each time a node needs to get the data for a particular key, it will start a Kademlia::get_providers query for the key, and if one is found, will contact that node using a separate protocol to attempt to retrieve the data (and if that fails, try another provider, and so on and so forth).

Thanks in advance for any help and advice!

[jnicholls]

@mxinden @thomaseizinger Sorry in advance for the tag if you already get notifications on discussions, but I wanted to make sure the SMEs were notified 😄 Thanks in advance!

[jnicholls]

I was taking a look at rust-ipfs' use of Kademlia and was surprised to see it's blissfully using the MemoryStore as-is. I clearly do not understand IPFS or Kademlia. The default MemoryStore config of a max of 1024 records and 1024 providers of keys would mean an IPFS server could only advertise itself as holding 1024 files addressable by their multihash, no?

I think I need a lesson on how Kademlia is being used in IPFS, and how this default configuration is satisfactory for a DHT network that could have millions of keys; and in my case, where each node could itself hold all of the keys.

[mxinden]

I think I need a lesson on how Kademlia is being used in IPFS, and how this default configuration is satisfactory for a DHT network that could have millions of keys; and in my case, where each node could itself hold all of the keys.

Instead of looking at rust-ipfs, I recommend looking at https://github.com/ipfs/go-ipfs/. The former is still in alpha stage.

[mxinden]

But, it begs the question why have integrated constraints like this at all?

I see it as a safe default. As a node in a large network, one only needs to store a small amount of data.

really there could be any implementation-defined way a key may fail to store/be retrieved/etc.?

I don't think this use-case ever came up. Actually, I don't think libp2p-kad has been used much with custom RecordStore implementations by now. Happy to discuss e.g. making the error type generic. Also //CC @rubdos who might be interested in that discussion as well.

Lastly, I wonder if what I am doing is completely ludicrous for KAD-DHT.

:D Not at all.

[jnicholls]

Thanks @mxinden for the reply! I'm interested in a fallible RecordStore setup, so we can discuss this.

I may work around the issue in the meantime with a MemoryStore configured with a large maximum provider count, and optimize the loading of provider records into the memory store on startup.

[rubdos]

Thanks for the mention, @mxinden. The sole reason that I didn't bring fallible storage up yet, is that my use-case is even broader than that, and it is not fully laid out yet. I'll gladly follow the discussion here though.

Maybe it's an idea to separate the types for in and out for a memory store, such that you can push T to nodes and on retrieval receive Result<T, E>? Just a quick thought, I haven't looked at the current structure in a while now.

[laptou]

While we're talking about modifying RecordStore, I also think it could be useful to have an async RecordStore, because any implementation that is not memory-based is going to be doing I/O. I am storing my kad records in a SQLite database using sqlx, for example, and I just ended up wrapping all of my code in futures::block_on

[thomaseizinger]

Closing this in favor of #3035. Open to discussing new APIs and usecases there: #3035