search

rust-p2p / s-kademlia

Implementation of the s/kademlia protocol
9 stars 2 forks source link

DHT Storage Layers and Requirements #4

Open 4meta5 opened 5 years ago

4meta5 commented 5 years ago

DHTs store a key-value store with keys as NodeIds. There is a lot of associated data at each layer of the record store that is used for incentivizing the network and managing the data stored therein.

Types of Data

Libp2p-kad supports two types of data:

  1. Regular (value-) records store an arbitrary value associated with a key which is distributed to the closest nodes to the key in the Kademlia DHT as per the "push model", subject to re-replication and re-publication as per Kademlia
  2. Provider records associate the NodeId of the peer with a key which can supposedly provide the associated value. These records are pointers to the data which can be followed by connecting providers to obtain the value. This follows a "pull model" (polling) -- distributed to the closest nodes to the key

Researched Paths/Strategies for Data Flow

red-blue consistency demonstrates how it is possible to partition the network based on the unique properties desired by different types of data. Some things to think about:

  1. how to describe/express the algorithm for partitioning the network based on data types (and expected access patterns)
  2. which queries can we parallelize? disjoint parallel lookups should converge (<= symmetricity of XOR)
4meta5 commented 5 years ago

ID Generation and Node Method Organization

One concern is that the strong signature for a Node requires using the sign_msg method on the NodeId element. This doesn't seem too clean, but I need the Node's other fields for the WeakSignature trait. I have an idea for how I want to structure this as traits implemented by Node by default. The default implementation of Node probably will use multihash::encode(hash: diso::DiscoHash, public_key: &[u8]) to calculate the id from the a public_key.

Routing Table

I changed NodeId from a trait and just made it a wrapper around DiscoHash. I'm fine with this, but now I think I will PR DiscoHash to add into_bytes and as_bytes and similar methods that will be necessary for smooth conversion. This is necessary in the context of verifying signed messages one level higher.