Kevalin - Distributed Hash Table
Routing table
The Kademlia routing algorithm is used to maintain a table of other nodes in the network which maintains complete connectivity of the node graph. See Message Routing.
DHT
The DHT sits on top of the overlay network and consists of a set of key-value pairs stored at and retrieved from each node in the network. Values are stored at the K nodes closest (as measured by the XOR metric) to the hash of their key.
Keys have a ‘type’ which determines some behaviours of the DHT. For some types, multiple entries can be published to a single key, they will all be returned in the event of a lookup request for that key.
Example types:
- Document - a document
- Subscription - nodes participating in a subscription
- Mail - messages sent to a mailbox for later retrieval
Future extensible DHT types
A long term plan is that the type is a pointer to a cryptographically signed document which defines the characteristics of that entry type. The document can be either a built-in type, or a custom type which can be fetched via the built-in mechanisms of the network. This allows nodes to correctly support new value types without needing them to be hard-coded into the node’s software.
Security
Each value can include a public key which allows the author to publish updates to the DHT entry.
Scaling and Persistence
When fetching values from the DHT receiving nodes may re-store the value at the closest node to the key which did not return any results. This allows popular values to be cached further away from the authoritative nodes and shed load from incoming requests to the rest of the network. 1
Note: If value update/removal is implemented, the cache purging might be effectively implemented using a broadcast message, but this might be open to abuse
Footnotes
-
Maymounkov, P., & Mazières, D. ( 2002). Kademlia: A Peer-to-Peer Information System Based on the XOR Metric. International Workshop on Peer-to-Peer Systems. ↩