Documentation
¶
Index ¶
- Constants
- func BucketIndex(self, peer a2al.NodeID) int
- func LessXORDistance(a, b, target a2al.NodeID) bool
- type EntryMeta
- type MaintenanceWork
- type PeerDebugRow
- type PingFunc
- type Table
- func (t *Table) Add(n protocol.NodeInfo, meta EntryMeta, addedAt time.Time) bool
- func (t *Table) AddPunched(n protocol.NodeInfo, meta EntryMeta, addedAt time.Time) bool
- func (t *Table) AllPeers() []protocol.NodeInfo
- func (t *Table) BucketDiscoveryCount(bi int) int
- func (t *Table) BucketIndexOf(peer a2al.NodeID) int
- func (t *Table) CollectMaintenanceWork(now, freshCutoff, staleCutoff time.Time) MaintenanceWork
- func (t *Table) Contains(id a2al.NodeID) bool
- func (t *Table) DebugPeerRows() []PeerDebugRow
- func (t *Table) EstimatedNetworkSize() int
- func (t *Table) EstimatedNetworkSizeFiltered(cutoff time.Time) (estimate int, confidence float64)
- func (t *Table) GetEntryMeta(id a2al.NodeID) (EntryMeta, bool)
- func (t *Table) IsPunched(peer a2al.NodeID) bool
- func (t *Table) Len() int
- func (t *Table) MarkPendingFailed(id a2al.NodeID)
- func (t *Table) MarkPendingVerified(id a2al.NodeID, meta EntryMeta, addedAt time.Time) bool
- func (t *Table) NearestN(target a2al.NodeID, n int) []protocol.NodeInfo
- func (t *Table) NearestNVerified(target a2al.NodeID, n int, cutoff time.Time) []protocol.NodeInfo
- func (t *Table) OldestInBucket(peer a2al.NodeID) (protocol.NodeInfo, bool)
- func (t *Table) OldestPunchedInBucket(peer a2al.NodeID) (protocol.NodeInfo, bool)
- func (t *Table) PeerBucketLen(peer a2al.NodeID) int
- func (t *Table) RecordRefillOutcome(bi int, improved bool)
- func (t *Table) Remove(id a2al.NodeID)
- func (t *Table) Self() a2al.NodeID
- func (t *Table) UpdateVerifiedAt(id a2al.NodeID, verifiedAt time.Time)
Constants ¶
const (
K = 16
)
Variables ¶
This section is empty.
Functions ¶
func BucketIndex ¶
BucketIndex is the K-bucket slot for peer relative to self: shared MSB prefix length in [0,255]. Returns -1 if peer equals self (spec §4.1, Step 5).
func LessXORDistance ¶
LessXORDistance reports whether a is strictly closer to target than b under XOR metric (lexicographic compare of Distance(a,target) vs Distance(b,target)).
Types ¶
type EntryMeta ¶ added in v0.1.7
type EntryMeta struct {
// VerifiedAt is the last moment at which we had direct-contact evidence
// for this node (inbound message or successful outbound RPC).
// Zero value means the node has never been directly verified by us.
VerifiedAt time.Time
// LearnedFrom is the NodeID of the peer that told us about this node via a
// FIND_NODE response. Zero value means we discovered the node directly
// (i.e., it contacted us or we contacted it successfully).
LearnedFrom a2al.NodeID
}
EntryMeta holds routing-quality metadata for a routing table entry. Values are supplied by the dht layer; the routing layer only stores and reads them. The routing layer never calls time.Now() directly.
type MaintenanceWork ¶ added in v0.1.7
type MaintenanceWork struct {
// PendingToProbe contains nodes in pending lists that need a PING to be
// verified and potentially promoted to the main bucket.
PendingToProbe []protocol.NodeInfo
// StaleToProbe contains main-bucket entries that have VerifiedAt.IsZero()
// and have been in the table long enough to warrant a probe.
StaleToProbe []protocol.NodeInfo
// BucketsToRefill holds bucket indices where the number of Verified-Fresh
// nodes is below K/2. The dht layer should issue FindNode(random-in-bucket)
// for each.
BucketsToRefill []int
}
MaintenanceWork holds work items collected by CollectMaintenanceWork for the dht layer's routing maintenance loop.
type PeerDebugRow ¶
type PeerDebugRow struct {
Bucket int `json:"bucket"`
XORDistToSelf string `json:"xor_distance_to_self_hex"`
AddressHex string `json:"address_hex"`
NodeIDHex string `json:"node_id_hex"`
IP string `json:"ip"`
Port uint16 `json:"port"`
VerifiedAgo string `json:"verified_ago,omitempty"` // human-readable age of VerifiedAt; empty if unverified
}
PeerDebugRow is a JSON-friendly routing row (spec §3.6).
type Table ¶
type Table struct {
// contains filtered or unexported fields
}
Table is a 256-bucket Kademlia routing table (Phase 1: single LRU zone per bucket).
func NewTable ¶
NewTable constructs an empty table for the local node. ping may be nil (treated as always true on eviction probe).
func (*Table) Add ¶
Add inserts or refreshes a peer. Returns false if the peer is self, invalid, or rejected (full bucket with a responsive LRU peer for direct contacts; added to the pending list for hearsay contacts).
meta.VerifiedAt should be the current time for direct-contact entries; leave zero for nodes learned from third-party FIND_NODE responses. addedAt is passed through to the bucket entry so the routing layer does not need to call time.Now().
func (*Table) AddPunched ¶ added in v0.1.8
AddPunched inserts or refreshes a punched entry into the appropriate bucket.
Punched entries are admitted only into spare slots (bucket len < K). A full bucket silently rejects the entry — the next time a direct-contact node arrives it will evict a punched entry (via Add), freeing a slot.
Returns true if the entry was admitted or refreshed.
func (*Table) AllPeers ¶
AllPeers returns every distinct peer in the main bucket table (unordered). Excludes self.
func (*Table) BucketDiscoveryCount ¶ added in v0.1.7
BucketDiscoveryCount returns the total number of distinct peers known to bucket bi, counting both main-bucket entries (verified or stale) and pending-list entries (unverified hearsay awaiting a probe).
This is the metric the dht layer uses before/after a refill FindNode to decide whether the query actually discovered new peers. verifiedFreshCount would be the wrong choice here: FindNode results enter the table as hearsay (VerifiedAt = 0) via absorbNodeInfo, so they cannot influence verifiedFreshCount until a later PING promotes them — by which point the outcome record is long since written.
Caller must hold the table lock.
func (*Table) BucketIndexOf ¶
BucketIndexOf returns BucketIndex(t.self, peer).
func (*Table) CollectMaintenanceWork ¶ added in v0.1.7
func (t *Table) CollectMaintenanceWork(now, freshCutoff, staleCutoff time.Time) MaintenanceWork
CollectMaintenanceWork scans all buckets and returns work items for the routing maintenance loop.
- now: current time (used for pending expiry)
- freshCutoff: entries with VerifiedAt.After(freshCutoff) are "fresh"
- staleCutoff: unverified main-bucket entries added before staleCutoff need probing
As a side effect this call expires pending entries older than pendingTTL.
func (*Table) DebugPeerRows ¶
func (t *Table) DebugPeerRows() []PeerDebugRow
DebugPeerRows returns a flat list of peers with bucket index and XOR distance. Caller must serialise table access if concurrent.
func (*Table) EstimatedNetworkSize ¶ added in v0.1.3
EstimatedNetworkSize estimates the total number of nodes using bucket density. For a bucket at CPL c with m nodes the estimate is m×2^(c+1). Includes all main-bucket entries (verified and unverified). For a freshness-filtered estimate with confidence, use EstimatedNetworkSizeFiltered.
func (*Table) EstimatedNetworkSizeFiltered ¶ added in v0.1.7
EstimatedNetworkSizeFiltered estimates network size using only fresh verified nodes (VerifiedAt.After(cutoff)). It scans up to 5 non-empty verified buckets from the highest CPL downward, computes m_i × 2^(c_i+1) for each, and returns the median estimate together with a confidence score in [0, 1] where 1 means 5 or more valid sample buckets were available.
cutoff is provided by the caller; pass time.Time{} to count all verified nodes regardless of age.
func (*Table) GetEntryMeta ¶ added in v0.1.7
GetEntryMeta returns the EntryMeta for a main-bucket entry. Returns false if the node is not in the main bucket.
func (*Table) IsPunched ¶ added in v0.1.8
IsPunched reports whether the given peer is currently in the main bucket and has its isPunched flag set (i.e., was admitted via ICE hole-punching rather than a direct UDP contact).
Returns false when the peer is not in any main bucket or when it has been promoted to a direct-contact entry (isPunched cleared by addOrTouch). Used by the dht layer to classify repSet members into XOR-set vs direct-set.
func (*Table) MarkPendingFailed ¶ added in v0.1.7
MarkPendingFailed removes a pending entry (called after a failed PING).
func (*Table) MarkPendingVerified ¶ added in v0.1.7
MarkPendingVerified attempts to promote a pending entry to the main bucket using meta (typically VerifiedAt=now after a successful PING). Returns true if the entry was moved; false if the main bucket is full (the entry remains in pending and the caller may retry after a slot opens).
func (*Table) NearestN ¶
NearestN returns up to n peers with smallest XOR distance to target (excluding self). Results sorted closest-first. Includes all main-bucket entries regardless of verification status.
func (*Table) NearestNVerified ¶ added in v0.1.7
NearestNVerified returns up to n main-bucket peers that have been directly verified (VerifiedAt != zero), sorted by freshness then XOR distance. Verified-Fresh entries (VerifiedAt.After(cutoff)) are returned before Verified-Stale entries. Unverified (VerifiedAt.IsZero()) entries are excluded.
cutoff is provided by the caller; the routing layer does not call time.Now().
func (*Table) OldestInBucket ¶
OldestInBucket returns the LRU entry in the main bucket that would hold peer.
func (*Table) OldestPunchedInBucket ¶ added in v0.1.8
OldestPunchedInBucket returns the NodeInfo of the oldest (LRU-position) punched entry in the bucket that would hold peer, together with its NodeID. Returns (NodeInfo{}, false) when no punched entry exists in that bucket.
Used by the dht layer's tabAdd to evict a punched node before triggering a liveness ping on a direct-contact entry (punched nodes are evicted first).
func (*Table) PeerBucketLen ¶
PeerBucketLen returns the number of entries in the main bucket for peer's CPL slot.
func (*Table) RecordRefillOutcome ¶ added in v0.1.7
RecordRefillOutcome updates the futile-attempt counter for bucket bi based on whether a recent FindNode improved its verifiedFreshCount.
- improved=true: reset futileCount to 0 (back to normal cadence)
- improved=false: increment futileCount (longer wait before next attempt)
Called by the dht layer after a maintenance FindNode goroutine completes. Caller must hold the table write lock.
func (*Table) UpdateVerifiedAt ¶ added in v0.1.7
UpdateVerifiedAt updates the VerifiedAt timestamp for an existing main-bucket entry. Called by the dht layer after a successful outbound RPC. No-op if the node is not currently in the main bucket.
Source Files