kbucket

README

go-libp2p-kbucket

Fork of libp2p/go-libp2p-kbucket by DAOT Labs.

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

Documentation

API docs:

Contribute

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

Want to hack on libp2p?

License

MIT

Copyright for the modified portions of this fork are held by [DAOT Labs, 2020]. All other portions of this fork are held by [Protocol Labs, 2016] as part of the original go-libp2p-kbucket project. All right reserved.

Documentation

Overview

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

Index

• Constants
• Variables
• func Closer(a, b peer.ID, key string) bool
• func CommonPrefixLen(a, b ID) int
• func EstimatedAvgBitsImprovedPerStepFromBucketSize(bucketSize int) float64
• func SortClosestPeers(peers []peer.ID, target ID, considerLatency bool, metrics peerstore.Metrics, ...) ([]peer.ID, error)
• func SortClosestPeersByDistance(peers []peer.ID, target ID) []peer.ID
• func SortClosestPeersByDistanceAndLatency(peers []peer.ID, target ID, metrics peerstore.Metrics, dialer network.Dialer, ...) ([]peer.ID, error)
• 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) AvgPeerRTTMicroSecs() int64
  • 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) 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) SortClosestPeers(peers []peer.ID, target ID) ([]peer.ID, error)
  • 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

Constants

const (
	AvgRoundTripsPerStepWithNewPeer_TCP_TLS = 4.0
	AvgRoundTripsPerStepWithNewPeer_QUIC    = 2.0
)

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 EstimatedAvgBitsImprovedPerStepFromBucketSize

func EstimatedAvgBitsImprovedPerStepFromBucketSize(bucketSize int) float64

EstimatedAvgBitsImprovedPerStepFromBucketSize calculates the estimated average number of bits improved per lookup step. Reference: D. Stutzbach and R. Rejaie, "Improving Lookup Performance Over a Widely-Deployed DHT," Proceedings IEEE INFOCOM 2006. For the basic Kademlia approach D(1,1,k), m(1,k) approaches log(2,k)+0.3327, the number of bits improved on average is 1+m(1,k)=1.3327+log(2,k)

func SortClosestPeers

func SortClosestPeers(
	peers []peer.ID,
	target ID,
	considerLatency bool,
	metrics peerstore.Metrics,
	dialer network.Dialer,
	local ID,
	avgBitsImprovedPerStep float64,
	avgRoundTripsPerStepWithNewPeer float64,
	avgPeerRTTMicroSecs int64,
) ([]peer.ID, error)

Sort the given peers with SortClosestPeersByDistanceAndLatency if consideraLatency is true, otherwise sort them with SortClosestPeersByDistance.

func SortClosestPeersByDistance

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

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

func SortClosestPeersByDistanceAndLatency

func SortClosestPeersByDistanceAndLatency(
	peers []peer.ID,
	target ID,
	metrics peerstore.Metrics,
	dialer network.Dialer,
	local ID,
	avgBitsImprovedPerStep float64,
	avgRoundTripsPerStepWithNewPeer float64,
	avgPeerRTTMicroSecs int64,
) ([]peer.ID, error)

Sort the given peers by their ascending closeness by taking into account both the distance to the target and the latency (measured by RTT) to the local peer. Fallback to SortClosestPeers if `metrics` is nil. 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,
	dialer network.Dialer, usefulnessGracePeriod time.Duration, df *peerdiversity.Filter,
	considerLatency bool, avgBitsImprovedPerStep float64, avgRoundTripsPerStepWithNewPeer float64,
) (*RoutingTable, error)

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

func (*RoutingTable) AvgPeerRTTMicroSecs

func (rt *RoutingTable) AvgPeerRTTMicroSecs() int64

AvgPeerRTTMicroSecs computes average RTT of peers in the RoutingTable to the local peer in microseconds.

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) 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.

#DAOT If rt.considerLatency is enabled, this will take into account not only the xor distance to the target, but also the latency to the local peer (measured in RTT).

For algorithm details, see section 3.7.3 of the paper "Design and Implementation of Low-latency P2P Network for Graph-Based Distributed Ledger" by Wang Xiang. "面向图式账本的低延迟P2P 网络的设计与实现" by 向往

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) SortClosestPeers

func (rt *RoutingTable) SortClosestPeers(peers []peer.ID, target ID) ([]peer.ID, error)

SortClosestPeers just calls kbucket.SortClosestPeers() with the options of the RoutingTable.

func (*RoutingTable) TryAddPeer

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

It 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

UpdateLastSuccessfulOutboundQuery 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.