kbucket

README

go-libp2p-kbucket

A kbucket implementation for use as a routing table in go-libp2p-kad-dht

Documenation

See https://godoc.org/github.com/libp2p/go-libp2p-kbucket.

Contribute

Feel free to join in. All welcome. Open an issue!

This repository falls under the libp2p Code of Conduct.

Want to hack on libp2p?

License

MIT

---

The last gx published version of this module was: 2.2.23: QmSNE1XryoCMnZCbRaj1D23k6YKCaTQ386eJciu1pAfu8M

Documentation

Overview

Package kbucket implements a kademlia 'k-bucket' routing table.

Index

• Variables
• func Closer(a, b peer.ID, key string) bool
• func CommonPrefixLen(a, b ID) int
• func SortClosestPeers(peers []peer.ID, target ID) []peer.ID
• type ID
  • func ConvertKey(id string) ID
  • func ConvertPeerID(id peer.ID) ID
• type PeerInfo
• type RoutingTable
  • func NewRoutingTable(bucketsize int, localID ID, latency time.Duration, m peerstore.Metrics, ...) (*RoutingTable, error)
  • func (rt *RoutingTable) Close() error
  • func (rt *RoutingTable) Find(id peer.ID) peer.ID
  • func (rt *RoutingTable) GenRandPeerID(targetCpl uint) (peer.ID, error)
  • func (rt *RoutingTable) GenRandomKey(targetCpl uint) (ID, error)
  • func (rt *RoutingTable) GetDiversityStats() []peerdiversity.CplDiversityStats
  • func (rt *RoutingTable) GetPeerInfos() []PeerInfo
  • func (rt *RoutingTable) GetTrackedCplsForRefresh() []time.Time
  • func (rt *RoutingTable) ListPeers() []peer.ID
  • func (rt *RoutingTable) MarkAllPeersIrreplaceable()
  • func (rt *RoutingTable) NPeersForCpl(cpl uint) int
  • func (rt *RoutingTable) NearestPeer(id ID) peer.ID
  • func (rt *RoutingTable) NearestPeers(id ID, count int) []peer.ID
  • func (rt *RoutingTable) Print()
  • func (rt *RoutingTable) RemovePeer(p peer.ID)
  • func (rt *RoutingTable) ResetCplRefreshedAtForID(id ID, newTime time.Time)
  • func (rt *RoutingTable) Size() int
  • func (rt *RoutingTable) TryAddPeer(p peer.ID, queryPeer bool, isReplaceable bool) (bool, error)
  • func (rt *RoutingTable) UpdateLastSuccessfulOutboundQueryAt(p peer.ID, t time.Time) bool
  • func (rt *RoutingTable) UpdateLastUsefulAt(p peer.ID, t time.Time) bool
  • func (rt *RoutingTable) UsefulNewPeer(p peer.ID) bool

Variables

var ErrLookupFailure = errors.New("failed to find any peer in table")

ErrLookupFailure is returned if a routing table query returns no results. This is NOT expected behaviour

var ErrPeerRejectedHighLatency = errors.New("peer rejected; latency too high")

var ErrPeerRejectedNoCapacity = errors.New("peer rejected; insufficient capacity")

Functions

func Closer

func Closer(a, b peer.ID, key string) bool

Closer returns true if a is closer to key than b is

func CommonPrefixLen

func CommonPrefixLen(a, b ID) int

func SortClosestPeers

func SortClosestPeers(peers []peer.ID, target ID) []peer.ID

SortClosestPeers Sort the given peers by their ascending distance from the target. A new slice is returned.

Types

type ID

type ID []byte

ID for IpfsDHT is in the XORKeySpace

The type dht.ID signifies that its contents have been hashed from either a peer.ID or a util.Key. This unifies the keyspace

func ConvertKey

func ConvertKey(id string) ID

ConvertKey creates a DHT ID by hashing a local key (String)

func ConvertPeerID

func ConvertPeerID(id peer.ID) ID

ConvertPeerID creates a DHT ID by hashing a Peer ID (Multihash)

type PeerInfo

type PeerInfo struct {
	Id peer.ID

	// LastUsefulAt is the time instant at which the peer was last "useful" to us.
	// Please see the DHT docs for the definition of usefulness.
	LastUsefulAt time.Time

	// LastSuccessfulOutboundQueryAt is the time instant at which we last got a
	// successful query response from the peer.
	LastSuccessfulOutboundQueryAt time.Time

	// AddedAt is the time this peer was added to the routing table.
	AddedAt time.Time
	// contains filtered or unexported fields
}

PeerInfo holds all related information for a peer in the K-Bucket.

type RoutingTable

type RoutingTable struct {

	// notification functions
	PeerRemoved func(peer.ID)
	PeerAdded   func(peer.ID)
	// contains filtered or unexported fields
}

RoutingTable defines the routing table.

func NewRoutingTable

func NewRoutingTable(bucketsize int, localID ID, latency time.Duration, m peerstore.Metrics, usefulnessGracePeriod time.Duration,
	df *peerdiversity.Filter) (*RoutingTable, error)

NewRoutingTable creates a new routing table with a given bucketsize, local ID, and latency tolerance.

func (*RoutingTable) Close

func (rt *RoutingTable) Close() error

Close shuts down the Routing Table & all associated processes. It is safe to call this multiple times.

func (*RoutingTable) Find

func (rt *RoutingTable) Find(id peer.ID) peer.ID

Find a specific peer by ID or return nil

func (*RoutingTable) GenRandPeerID

func (rt *RoutingTable) GenRandPeerID(targetCpl uint) (peer.ID, error)

GenRandPeerID generates a random peerID for a given Cpl

func (*RoutingTable) GenRandomKey

func (rt *RoutingTable) GenRandomKey(targetCpl uint) (ID, error)

GenRandomKey generates a random key matching a provided Common Prefix Length (Cpl) wrt. the local identity. The returned key matches the targetCpl first bits of the local key, the following bit is the inverse of the local key's bit at position targetCpl+1 and the remaining bits are randomly generated.

func (*RoutingTable) GetDiversityStats

func (rt *RoutingTable) GetDiversityStats() []peerdiversity.CplDiversityStats

GetDiversityStats returns the diversity stats for the Routing Table if a diversity Filter is configured.

func (*RoutingTable) GetPeerInfos

func (rt *RoutingTable) GetPeerInfos() []PeerInfo

GetPeerInfos returns the peer information that we've stored in the buckets

func (*RoutingTable) GetTrackedCplsForRefresh

func (rt *RoutingTable) GetTrackedCplsForRefresh() []time.Time

GetTrackedCplsForRefresh returns the Cpl's we are tracking for refresh. Caller is free to modify the returned slice as it is a defensive copy.

func (*RoutingTable) ListPeers

func (rt *RoutingTable) ListPeers() []peer.ID

ListPeers takes a RoutingTable and returns a list of all peers from all buckets in the table.

func (*RoutingTable) MarkAllPeersIrreplaceable

func (rt *RoutingTable) MarkAllPeersIrreplaceable()

MarkAllPeersIrreplaceable marks all peers in the routing table as irreplaceable This means that we will never replace an existing peer in the table to make space for a new peer. However, they can still be removed by calling the `RemovePeer` API.

func (*RoutingTable) NPeersForCpl

func (rt *RoutingTable) NPeersForCpl(cpl uint) int

NPeersForCpl returns the number of peers we have for a given Cpl

func (*RoutingTable) NearestPeer

func (rt *RoutingTable) NearestPeer(id ID) peer.ID

NearestPeer returns a single peer that is nearest to the given ID

func (*RoutingTable) NearestPeers

func (rt *RoutingTable) NearestPeers(id ID, count int) []peer.ID

NearestPeers returns a list of the 'count' closest peers to the given ID

func (*RoutingTable) Print

func (rt *RoutingTable) Print()

Print prints a descriptive statement about the provided RoutingTable

func (*RoutingTable) RemovePeer

func (rt *RoutingTable) RemovePeer(p peer.ID)

RemovePeer should be called when the caller is sure that a peer is not useful for queries. For eg: the peer could have stopped supporting the DHT protocol. It evicts the peer from the Routing Table.

func (*RoutingTable) ResetCplRefreshedAtForID

func (rt *RoutingTable) ResetCplRefreshedAtForID(id ID, newTime time.Time)

ResetCplRefreshedAtForID resets the refresh time for the Cpl of the given ID.

func (*RoutingTable) Size

func (rt *RoutingTable) Size() int

Size returns the total number of peers in the routing table

func (*RoutingTable) TryAddPeer

func (rt *RoutingTable) TryAddPeer(p peer.ID, queryPeer bool, isReplaceable bool) (bool, error)

TryAddPeer returns a boolean value set to true if the peer was newly added to the Routing Table, false otherwise. It also returns any error that occurred while adding the peer to the Routing Table. If the error is not nil, the boolean value will ALWAYS be false i.e. the peer wont be added to the Routing Table it it's not already there.

A return value of false with error=nil indicates that the peer ALREADY exists in the Routing Table.

func (*RoutingTable) UpdateLastSuccessfulOutboundQueryAt

func (rt *RoutingTable) UpdateLastSuccessfulOutboundQueryAt(p peer.ID, t time.Time) bool

UpdateLastSuccessfulOutboundQueryAt updates the LastSuccessfulOutboundQueryAt time of the peer. Returns true if the update was successful, false otherwise.

func (*RoutingTable) UpdateLastUsefulAt

func (rt *RoutingTable) UpdateLastUsefulAt(p peer.ID, t time.Time) bool

UpdateLastUsefulAt updates the LastUsefulAt time of the peer. Returns true if the update was successful, false otherwise.

func (*RoutingTable) UsefulNewPeer

func (rt *RoutingTable) UsefulNewPeer(p peer.ID) bool

UsefulNewPeer verifies whether the given peer.ID would be a good fit for the routing table. It returns true if the peer isn't in the routing table yet, if the bucket corresponding to peer.ID isn't full, if it contains replaceable peers or if it is the last bucket and adding a peer would unfold it.