kademlia

package
v0.0.0-...-d4b7e32 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 12, 2023 License: MPL-2.0 Imports: 9 Imported by: 1

README

Kademlia

This package implements the Kademlia Distributed Hash Table (DHT) algorithm. It aims for simplicity and applicability, rather than protocol level compliance with any other particular implementation.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func DHTJoin 

func DHTJoin(params DHTJoinParams) int

DHTJoin joins a node to the rest of the DHT.

func Distance 

func Distance(a, b []byte) []byte

Distance is the Kademlia distance metric. Distance(a, b) == Distance(b, a) len(Distance(a, b)) == min(len(a), len(b))

func DistanceCmp 

func DistanceCmp(x []byte, a, b []byte) int

DistanceCmp is equivalent to bytes.Compare(Distance(x, a), Distance(x, b))

func DistanceGt 

func DistanceGt(x []byte, a, b []byte) bool

DistanceGt returns true if Distance(x, a) > Distance(x, b)

func DistanceLt 

func DistanceLt(x []byte, a, b []byte) bool

DistanceLt returns true if Distance(x, a) < Distance(x, b)

func DistanceLz 

func DistanceLz(a, b []byte) (ret int)

DistanceLz returns the number of leading zeros in the distance between a and b DistanceLz == LeadingZeros(Distance(a, b))

func HasPrefix 

func HasPrefix(x []byte, prefix []byte, nbits int) bool

HasPrefix returns true if the first `nbits` bits of x match the first `nbits` bits of prefix.

func LeadingZeros 

func LeadingZeros(x []byte) int

LeadingZeros returns the number of 0s that occur before the first 1 when iterating bit by bit, most significant bit first, low indexed byte to high indexed byte.

func XORBytes 

func XORBytes(dst, a, b []byte) int

XORBytes writes the XOR of a and b, byte-wise into dst.

Types

type Cache 

type Cache[V any] struct {
	// contains filtered or unexported fields
}

Cache stores data and evicts based on the Kademlia distance metric, and the CreatedAt time. Entries closer to the locus, that have existed for longer are more likely to remain in the cache.

func NewCache 

func NewCache[V any](locus []byte, max, minPerBucket int) *Cache[V]

NewCache returns a Cache with the provided parameters NewCache will panic if max is < minPerBucket * 8 * len(locus) i.e. If the locus is 256 bits long, then you can have anywhere from 0 to 256 buckets, and max must be sufficiently large to respect each of those 256 buckets having a minimum number of keys.

func (*Cache[V]) AcceptingPrefixLen 

func (kc *Cache[V]) AcceptingPrefixLen() int

func (*Cache[V]) Closest 

func (kc *Cache[V]) Closest(key []byte) (ret *Entry[V])

Closest returns the Entry in the cache where e.Key is closest to key.

func (*Cache[V]) Contains 

func (kc *Cache[V]) Contains(key []byte, now time.Time) bool

Contains returns true if the key is in the cache

func (*Cache[V]) Count 

func (kc *Cache[V]) Count() int

Count returns the number of entries in the cache.

func (*Cache[V]) Delete 

func (kc *Cache[V]) Delete(key []byte) *Entry[V]

Delete removes the entry at the given key

func (*Cache[V]) Expire 

func (kc *Cache[V]) Expire(out []Entry[V], now time.Time) []Entry[V]

Expire expires items from the cache and appends them to out

func (*Cache[V]) ForEach 

func (kc *Cache[V]) ForEach(k []byte, fn func(e Entry[V]) bool)

ForEach calls fn with entries. All of the entries with n bits in common with k will be emitted before any of the entries with n-1 bits in common with k.

func (*Cache[V]) ForEachCloser 

func (kc *Cache[V]) ForEachCloser(x []byte, fn func(Entry[V]) bool)

ForEachCloser calls fn with all the entries in the Cache which are closer to x than they are to the locus.

func (*Cache[V]) ForEachMatching 

func (kc *Cache[V]) ForEachMatching(prefix []byte, nbits int, fn func(Entry[V]) bool)

ForEachMatching calls fn with every entry where the key matches prefix for the leading nbits. If nbits < len(prefix/8) it panics.

func (*Cache[V]) Get 

func (kc *Cache[V]) Get(key []byte, now time.Time) (ret V, exists bool)

Get returns the value at key

func (*Cache[V]) IsFull 

func (kc *Cache[V]) IsFull() bool

IsFull returns whether the cache is full further calls to Put will attempt an eviction.

func (*Cache[V]) Locus 

func (kc *Cache[V]) Locus() []byte

func (*Cache[V]) Put 

func (kc *Cache[V]) Put(key []byte, v V, now, expiresAt time.Time) (evicted *Entry[V], affected bool)

Put puts an entry in the cache, replacing the entry at that key. Put returns the evicted entry if there was one, and whether or not the Put had an effect.

func (*Cache[V]) Update 

func (kc *Cache[V]) Update(key []byte, fn func(v Entry[V], exists bool) Entry[V]) (evicted *Entry[V], added bool)

Update calls fn with the entry in the cache at key if it exists.

func (*Cache[V]) WouldAdd 

func (kc *Cache[V]) WouldAdd(key []byte, now time.Time) bool

WouldAdd returns true if the key would add a new entry

func (*Cache[V]) WouldPut 

func (kc *Cache[V]) WouldPut(key []byte) bool

WouldPut returns true if a call to Put with key would add or overwrite an entry.

type DHTFindNodeParams 

type DHTFindNodeParams struct {
	Initial  []NodeInfo
	Target   p2p.PeerID
	Ask      FindNodeFunc
	Validate func(NodeInfo) bool
}

type DHTFindNodeResult 

type DHTFindNodeResult struct {
	Info []byte

	Closest   p2p.PeerID
	Contacted int
}

func DHTFindNode 

func DHTFindNode(params DHTFindNodeParams) (*DHTFindNodeResult, error)

type DHTGetParams 

type DHTGetParams struct {
	Key      []byte
	Initial  []NodeInfo
	Validate func([]byte) bool
	Ask      GetFunc
}

type DHTGetResult 

type DHTGetResult struct {
	// Value is the value associated with the key
	Value []byte
	// From is the node that returned the value
	From p2p.PeerID
	// ExpiresAt is when the entry expires
	ExpiresAt time.Time
	// Closest is the peer closest to the key that we contacted.
	Closest      p2p.PeerID
	NumContacted int
	NumResponded int
}

func DHTGet 

func DHTGet(params DHTGetParams) (*DHTGetResult, error)

DHTPGet performs the Kademlia FIND_VALUE operation.

type DHTJoinParams 

type DHTJoinParams struct {
	Initial []NodeInfo
	Target  p2p.PeerID
	Ask     FindNodeFunc
	AddPeer func(p2p.PeerID, []byte) bool
}

type DHTNode 

type DHTNode struct {
	// contains filtered or unexported fields
}

DHTNode is the state of a single node in a DHT.

func NewDHTNode 

func NewDHTNode(params DHTNodeParams) *DHTNode

func (*DHTNode) AddPeer 

func (node *DHTNode) AddPeer(id p2p.PeerID, info []byte) bool

func (*DHTNode) Count 

func (node *DHTNode) Count() int

func (*DHTNode) Get 

func (node *DHTNode) Get(key []byte) []byte

func (*DHTNode) GetPeer 

func (node *DHTNode) GetPeer(x p2p.PeerID) ([]byte, bool)

GetPeerInfo returns information associated with the peer, if it exists.

func (*DHTNode) HandleFindNode 

func (n *DHTNode) HandleFindNode(from p2p.PeerID, req FindNodeReq) (FindNodeRes, error)

func (*DHTNode) HandleGet 

func (n *DHTNode) HandleGet(from p2p.PeerID, req GetReq) (GetRes, error)

func (*DHTNode) HandlePut 

func (node *DHTNode) HandlePut(from p2p.PeerID, req PutReq) (PutRes, error)

HandlePut handles a put from another node.

func (*DHTNode) HasPeer 

func (node *DHTNode) HasPeer(x p2p.PeerID) bool

func (*DHTNode) ListNodeInfos 

func (node *DHTNode) ListNodeInfos(key []byte, n int) (ret []NodeInfo)

ListNodeInfos returns the n nodes closest to key.

func (*DHTNode) ListPeers 

func (node *DHTNode) ListPeers(limit int) (ret []p2p.PeerID)

func (*DHTNode) LocalID 

func (node *DHTNode) LocalID() p2p.PeerID

func (*DHTNode) Put 

func (node *DHTNode) Put(key, value []byte, ttl time.Duration) bool

Put attempts to insert the key into the nodes's data cache.

func (*DHTNode) RemovePeer 

func (node *DHTNode) RemovePeer(localID p2p.PeerID) bool

func (*DHTNode) String 

func (n *DHTNode) String() string

func (*DHTNode) WouldAdd 

func (node *DHTNode) WouldAdd(key []byte) bool

type DHTNodeParams 

type DHTNodeParams struct {
	LocalID                      p2p.PeerID
	PeerCacheSize, DataCacheSize int
	Now                          func() time.Time
	MaxPeerTTL                   time.Duration
	MaxDataTTL                   time.Duration
}

type DHTPutParams 

type DHTPutParams struct {
	Initial    []NodeInfo
	Key, Value []byte
	TTL        time.Duration

	Ask         PutFunc
	MinAccepted int
}

type DHTPutResult 

type DHTPutResult struct {
	Closest  p2p.PeerID
	Accepted int

	Contacted int
	Responded int
}

func DHTPut 

func DHTPut(params DHTPutParams) (*DHTPutResult, error)

DHTPut performs the Kademlia STORE operation

type Entry 

type Entry[V any] struct {
	Key       []byte
	Value     V
	CreatedAt time.Time
	ExpiresAt time.Time
}

Entry is an entry in the cache.

func (Entry[V]) IsExpired 

func (e Entry[V]) IsExpired(now time.Time) bool

func (Entry[V]) String 

func (e Entry[V]) String() string

type ErrNotFound 

type ErrNotFound struct {
	Key []byte
}

func (ErrNotFound) Error 

func (e ErrNotFound) Error() string

type FindNodeFunc 

type FindNodeFunc = func(NodeInfo, FindNodeReq) (FindNodeRes, error)

FindNodeFunc is the type of functions implementing the FindNode rpc.

type FindNodeReq 

type FindNodeReq struct {
	Target p2p.PeerID `json:"target"`
	Limit  int        `json:"limit"`
}

FindNodeReq is the request in the FindNode rpc

type FindNodeRes 

type FindNodeRes struct {
	Nodes []NodeInfo `json:"nodes"`
}

FindNodeRes it the response in the FindNode rpc

type GetFunc 

type GetFunc = func(NodeInfo, GetReq) (GetRes, error)

GetFunc is the type of functions implementing the Get rpc.

type GetReq 

type GetReq struct {
	Key []byte `json:"key"`
}

GetReq is the request in the Get rpc.

type GetRes 

type GetRes struct {
	Value     []byte       `json:"value"`
	ExpiresAt tai64.TAI64N `json:"expires_at"`
	Closer    []NodeInfo   `json:"closer"`
}

GetRes is the response in the Get rpc.

type NodeInfo 

type NodeInfo struct {
	ID   p2p.PeerID `json:"id"`
	Info []byte     `json:"info"`
}

NodeInfo is information about a node, and its ID.

type PingReq 

type PingReq struct{}

type PingRes 

type PingRes struct {
	Timestamp tai64.TAI64N `json:"timestamp"`
}

type PutFunc 

type PutFunc = func(NodeInfo, PutReq) (PutRes, error)

PutFunc is the type of functions implementing the Put rpc.

type PutReq 

type PutReq struct {
	Key   []byte `json:"key"`
	Value []byte `json:"value"`
	TTLms uint64 `json:"ttl_ms"`
}

PutReq is the request in the Put rpc.

type PutRes 

type PutRes struct {
	Accepted bool       `json:"accepted"`
	Closer   []NodeInfo `json:"closer"`
}

PutRes is the response in the Put rpc.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.