kademlia

package
v1.3.6 Latest Latest
Warning

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

 Go to latest Published: May 25, 2022 License: BSD-3-Clause Imports: 35 Imported by: 0

Documentation

Overview

Package kademlia provides an implementation of the topology.Driver interface in a way that a kademlia connectivity is actively maintained by the node.

A thorough explanation of the logic in the `manage()` forever loop: The `manageC` channel gets triggered every time there's a change in the information regarding peers we know about. This can be a result of: (1) A peer has disconnected from us (2) A peer has been added to the list of known peers (from discovery, debugapi, bootnode flag or just because it was persisted in the address book and the node has been restarted).

So the information has been changed, and potentially upon disconnection, the depth can travel to a shallower depth in result. If a peer gets added through AddPeers, this does not necessarily infer an immediate depth change, since the peer might end up in the backlog for a long time until we actually need to connect to her.

The `manage()` forever-loop will connect to peers in order from shallower to deeper depths. This is because of depth calculation method that prioritizes empty bins That are shallower than depth. An in-depth look at `recalcDepth()` method will clarify this (more below). So if we will connect to peers from deeper to shallower depths, all peers in all bins will qualify as peers we'd like to connect to (see `binSaturated` method), ending up connecting to everyone we know about.

Another important notion one must observe while inspecting how `manage()` works, is that when we connect to peers depth can only move in one direction, which is deeper. So this becomes our strategy and we operate with this in mind, this is also why we iterate from shallower to deeper - since additional connections to peers for whatever reason can only result in increasing depth.

Empty intermediate bins should be eliminated by the `binSaturated` method indicating a bin size too short, which in turn means that connections should be established within this bin. Empty bins have special status in terms of depth calculation and as mentioned before they are prioritized over deeper, non empty bins and they constitute as the node's depth when the latter is recalculated. For the rationale behind this please refer to the appropriate chapters in the book of Aurora.

A special case of the `manage()` functionality is that when we iterate over peers and we come across a peer that has PO >= depth, we would always like to connect to that peer. This should always be enforced within the bounds of the `binSaturated` function and guarantees an ever increasing kademlia depth in an ever-increasing size of Aurora, resulting in smaller areas of responsibility for the nodes, maintaining a general upper bound of the assigned nominal area of responsibility in terms of actual storage requirement. See book of Aurora for more details.

Worth to note is that `manage()` will always try to initiate connections when a bin is not saturated, however currently it will not try to eliminate connections on bins which might be over-saturated. Ideally it should be very cheap to maintain a connection to a peer in a bin, so we should theoretically not aspire to eliminate connections prematurely. It is also safe to assume we will always have more than the lower bound of peers in a bin, why? (1) Initially, we will always try to satisfy our own connectivity requirement to saturate the bin (2) Later on, other peers will get notified about our advertised address and will try to connect to us in order to satisfy their own connectivity thresholds

We should allow other nodes to dial in, in order to help them maintain a healthy topolgy. It could be, however, that we would need to mark-and-sweep certain connections once a theorical upper bound has been reached.

Depth calculation explained: When we calculate depth we must keep in mind the following constraints: (1) A nearest-neighborhood constitutes of an arbitrary lower bound of the closest peers we know about, this is defined in `nnLowWatermark` and is currently set to `2` (2) Empty bins which are shallower than depth constitute as the node's area of responsibility

As of such, we would calculate depth in the following manner: (1) Iterate over all peers we know about, from deepest (closest) to shallowest, and count until we reach `nnLowWatermark` (2) Once we reach `nnLowWatermark`, mark current bin as depth candidate (3) Iterate over all bins from shallowest to deepest, and look for the shallowest empty bin (4) If the shallowest empty bin is shallower than the depth candidate - select shallowest bin as depth, otherwise select the candidate

Note: when we are connected to less or equal to `nnLowWatermark` peers, the depth will always be considered `0`, thus a short-circuit is handling this edge case explicitly in the `recalcDepth` method.

TODO: add pseudo-code how to calculate depth.

A few examples to depth calculation:

1. empty kademlia bin | nodes ------------- ==DEPTH== 0 0 1 0 2 0 3 0 4 0 depth: 0

2. less or equal to two peers (nnLowWatermark=2) (a) bin | nodes ------------- ==DEPTH== 0 1 1 1 2 0 3 0 4 0 depth: 0

3. less or equal to two peers (nnLowWatermark=2) (b) bin | nodes ------------- ==DEPTH== 0 1 1 0 2 1 3 0 4 0 depth: 0

4. less or equal to two peers (nnLowWatermark=2) (c) bin | nodes ------------- ==DEPTH== 0 2 1 0 2 0 3 0 4 0 depth: 0

5. empty shallow bin bin | nodes ------------- 0 1 ==DEPTH== 1 0 2 1 3 1 4 0 depth: 1 (depth candidate is 2, but 1 is shallower and empty)

6. no empty shallower bin, depth after nnLowerWatermark found bin | nodes ------------- 0 1 1 1 ==DEPTH== 2 1 3 1 4 0 depth: 2 (depth candidate is 2, shallowest empty bin is 4)

7. last bin size >= nnLowWatermark bin | nodes ------------- 0 1 1 1 2 1 ==DEPTH== 3 3 4 0 depth: 3 (depth candidate is 3, shallowest empty bin is 4)

8. all bins full bin | nodes ------------- 0 1 1 1 2 1 3 3 ==DEPTH== 4 2 depth: 4 (depth candidate is 4, no empty bins)

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Connected added in v1.3.0 

type Connected struct {
	FullNodes  int  `json:"full_nodes"`
	LightNodes uint `json:"light_nodes"`
	BootNodes  uint `json:"boot_nodes"`
}

type Kad 

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

Kad is the Aurora forwarding kademlia implementation.

func New 

func New(
	base boson.Address,
	addressbook addressbook.Interface,
	discovery discovery.Driver,
	p2ps p2p.Service,
	pinger pingpong.Interface,
	lightNodes *lightnode.Container,
	bootNodes *bootnode.Container,
	metricsDB *shed.DB,
	logger logging.Logger,
	subPub subscribe.SubPub,
	o Options,
) (*Kad, error)

New returns a new Kademlia.

func (*Kad) API added in v1.3.0 

func (k *Kad) API() rpc.API

func (*Kad) AddPeers 

func (k *Kad) AddPeers(addrs ...boson.Address)

AddPeers adds peers to the knownPeers list. This does not guarantee that a connection will immediately be made to the peer.

func (*Kad) Announce 

func (k *Kad) Announce(ctx context.Context, peer boson.Address, fullnode bool) error

Announce a newly connected peer to our connected peers, but also notify the peer about our already connected peers

func (*Kad) AnnounceTo 

func (k *Kad) AnnounceTo(ctx context.Context, addressee, peer boson.Address, fullnode bool) error

AnnounceTo announces a selected peer to another.

func (*Kad) Close 

func (k *Kad) Close() error

Close shuts down kademlia.

func (*Kad) ClosestPeer 

func (k *Kad) ClosestPeer(addr boson.Address, includeSelf bool, filter topology.Filter, skipPeers ...boson.Address) (boson.Address, error)

ClosestPeer returns the closest peer to a given address.

func (*Kad) ClosestPeers 

func (k *Kad) ClosestPeers(addr boson.Address, limit int, filter topology.Filter, skipPeers ...boson.Address) ([]boson.Address, error)

func (*Kad) Connected 

func (k *Kad) Connected(ctx context.Context, peer p2p.Peer, forceConnection bool) error

Connected is called when a peer has dialed in. If forceConnection is true `overSaturated` is ignored for non-bootnodes.

func (*Kad) ConnectedPeers added in v1.0.9 

func (k *Kad) ConnectedPeers() *pslice.PSlice

func (*Kad) Connection added in v1.2.0 

func (k *Kad) Connection(ctx context.Context, addr *aurora.Address) error

func (*Kad) DisconnectForce 

func (k *Kad) DisconnectForce(addr boson.Address, reason string) error

DisconnectForce only debug calls

func (*Kad) Disconnected 

func (k *Kad) Disconnected(peer p2p.Peer, reason string)

Disconnected is called when peer disconnects.

func (*Kad) EachKnownPeer 

func (k *Kad) EachKnownPeer(f model.EachPeerFunc) error

EachKnownPeer iterates from closest bin to farthest.

func (*Kad) EachKnownPeerRev 

func (k *Kad) EachKnownPeerRev(f model.EachPeerFunc) error

EachKnownPeerRev iterates from farthest bin to closest.

func (*Kad) EachNeighbor 

func (k *Kad) EachNeighbor(f model.EachPeerFunc) error

EachNeighbor iterates from closest bin to farthest of the neighborhood peers.

func (*Kad) EachNeighborRev 

func (k *Kad) EachNeighborRev(f model.EachPeerFunc) error

EachNeighborRev iterates from farthest bin to closest of the neighborhood peers.

func (*Kad) EachPeer 

func (k *Kad) EachPeer(f model.EachPeerFunc, filter topology.Filter) error

EachPeer iterates from closest bin to farthest.

func (*Kad) EachPeerRev 

func (k *Kad) EachPeerRev(f model.EachPeerFunc, filter topology.Filter) error

EachPeerRev iterates from farthest bin to closest.

func (*Kad) GetAuroraAddress added in v1.2.0 

func (k *Kad) GetAuroraAddress(overlay boson.Address) (addr *aurora.Address, err error)

func (*Kad) GetPeersWithLatencyEWMA added in v1.3.5 

func (k *Kad) GetPeersWithLatencyEWMA(list []boson.Address) (now []boson.Address)

func (*Kad) Halt 

func (k *Kad) Halt()

Halt stops outgoing connections from happening. This is needed while we shut down, so that further topology changes do not happen while we shut down.

func (*Kad) IsBalanced 

func (k *Kad) IsBalanced(bin uint8) bool

IsBalanced returns if Kademlia is balanced to bin.

func (*Kad) IsProtectPeer added in v1.3.3 

func (k *Kad) IsProtectPeer(peer boson.Address) bool

func (*Kad) IsSaturated 

func (k *Kad) IsSaturated(bin uint8) bool

func (*Kad) IsWithinDepth 

func (k *Kad) IsWithinDepth(addr boson.Address) bool

IsWithinDepth returns if an address is within the neighborhood depth of a node.

func (*Kad) KnownPeers added in v1.0.9 

func (k *Kad) KnownPeers() *pslice.PSlice

func (*Kad) Metrics 

func (k *Kad) Metrics() []prometheus.Collector

Metrics returns set of prometheus collectors.

func (*Kad) NeighborhoodDepth 

func (k *Kad) NeighborhoodDepth() uint8

NeighborhoodDepth returns the current Kademlia depth.

func (*Kad) NotifyPeerState added in v1.3.0 

func (k *Kad) NotifyPeerState(peer p2p.PeerInfo)

func (*Kad) Outbound added in v1.1.3 

func (k *Kad) Outbound(peer p2p.Peer)

func (*Kad) Pick 

func (k *Kad) Pick(peer p2p.Peer) bool

func (*Kad) PublishPeerState added in v1.3.5 

func (k *Kad) PublishPeerState(info p2p.PeerInfo)

func (*Kad) PublishPeersChange added in v1.3.5 

func (k *Kad) PublishPeersChange()

func (*Kad) RandomSubset added in v1.0.9 

func (k *Kad) RandomSubset(array []boson.Address, count int) ([]boson.Address, error)

func (*Kad) Reachable added in v1.3.2 

func (k *Kad) Reachable(addr boson.Address, status p2p.ReachabilityStatus)

Reachable sets the peer reachability status.

func (*Kad) RecordPeerLatency added in v1.3.2 

func (k *Kad) RecordPeerLatency(add boson.Address, t time.Duration)

func (*Kad) RefreshProtectPeer added in v1.3.3 

func (k *Kad) RefreshProtectPeer(peer []boson.Address)

func (*Kad) SetRadius 

func (k *Kad) SetRadius(r uint8)

func (*Kad) Snapshot 

func (k *Kad) Snapshot() *model.KadParams

func (*Kad) SnapshotAddr added in v1.3.2 

func (k *Kad) SnapshotAddr(addr boson.Address) *model.Snapshot

func (*Kad) SnapshotConnected added in v1.2.4 

func (k *Kad) SnapshotConnected() (connected int, peers map[string]*model.PeerInfo)

func (*Kad) Start 

func (k *Kad) Start(_ context.Context) error

func (*Kad) String 

func (k *Kad) String() string

String returns a string represenstation of Kademlia.

func (*Kad) SubscribePeerState added in v1.2.4 

func (k *Kad) SubscribePeerState(notifier subscribe.INotifier)

func (*Kad) SubscribePeersChange 

func (k *Kad) SubscribePeersChange(notifier subscribe.INotifier)

func (*Kad) UpdateReachability added in v1.3.2 

func (k *Kad) UpdateReachability(status p2p.ReachabilityStatus)

UpdateReachability updates node reachability status. The status will be updated only once. Updates to status p2p.ReachabilityStatusUnknown are ignored.

type KadInfo added in v1.3.0 

type KadInfo struct {
	Depth      uint8     `json:"depth"`
	Population int       `json:"population"`
	Connected  Connected `json:"connected"`
}

type Options 

type Options struct {
	SaturationFunc   binSaturationFunc
	Bootnodes        []ma.Multiaddr
	NodeMode         aurora.Model
	BitSuffixLength  int
	PruneFunc        pruneFunc
	StaticNodes      []boson.Address
	BinMaxPeers      int // every k bucket max connes
	ReachabilityFunc peerFilterFunc
}

Options for injecting services to Kademlia.

Source Files

View all Source files

Directories

Path Synopsis
internal
metrics
Package metrics provides service for collecting various metrics about peers.
 Package metrics provides service for collecting various metrics about peers.
waitnext
Package waitnext Package metrics provides service for collecting various metrics about peers.
 Package waitnext Package metrics provides service for collecting various metrics about peers.

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.