java.lang.Object
net.i2p.router.JobImpl
net.i2p.router.networkdb.kademlia.FloodSearchJob
net.i2p.router.networkdb.kademlia.IterativeSearchJob
All Implemented Interfaces:
Job
public class IterativeSearchJobextends FloodSearchJob
Traditional Kademlia iterative search with enhanced robustness.

Continues searching when initial lookup fails by iteratively querying closer-to-the-key peers returned in DatabaseSearchReplyMessages. Unlike traditional Kademlia, doesn't stop when no closer keys are available - keeps searching until timeout or maximum search limit is reached.

Key differences from FloodOnlySearchJob: - Chases peers in DSRM immediately rather than waiting - Searches one peer at a time with individual per-search timeouts - Uses total timeout rather than per-search timeouts - Longer overall timeout for better success rates - Reduces search traffic by half compared to parallel approaches

Advantages over flood-only approaches: - More robust in large networks with incomplete floodfill knowledge - Better success rates through sequential searching - Reduced network traffic through single-peer queries.

  • Field Details

    • _toTry

      private final SortedSet<Hash> _toTry
      Peers not sent to yet, sorted closest-to-the-routing-key.

    • _unheardFrom

      private final Set<Hash> _unheardFrom
      Query sent, no reply yet.

    • _failedPeers

      private final Set<Hash> _failedPeers
      Query sent, failed, timed out, or got DSRM.

    • _sawReply

      private volatile boolean _sawReply
      True once any peer replied (DSRM); distinguishes definitive fails from pure timeouts.

    • _sentTime

      private final Map<Hash,Long> _sentTime
      The time the query was sent to a peer, which we need to update profiles correctly.

    • _rkey

      private final Hash _rkey
      The routing key.

    • _out

      private OutNetMessage _out
      This is a marker to register with the MessageRegistry, it is never sent.

    • _fromLocalDest

      private final Hash _fromLocalDest
      The local destination to search from, null if none.

    • _alwaysQueryHash

      private static Hash _alwaysQueryHash
      Hash to always query first, set from a router property for testing.

    • _totalSearchLimit

      private final int _totalSearchLimit
      Max number of peers to query.

    • _maskedIPs

      private final Set<Long> _maskedIPs
      Masked-IP keys, ports and family options of the peers already queried by this search, used to avoid querying several peers of one entity. The three key spaces stay separate, so a masked IP can never collide with a port or a family. See collectFingerprint(RouterContext, Hash, int) for the encoding.

    • _ports

      private final Set<Integer> _ports
      The service ports the results must match.

    • _families

      private final Set<String> _families
      The families the results must match.

    • _fingerprintIPs

      private final long[] _fingerprintIPs
      Scratch buffers for one candidate's keys, filled by collectFingerprint(RouterContext, Hash, int) and consumed by fingerprintClaimed() / claimFingerprint(). The IP and port key spaces are counted separately, so neither array can hold a stale entry from the previous candidate. Sized by MAX_FINGERPRINT_ENTRIES, a hard cap on the keys any one peer can contribute. Reused across candidates.

    • _fingerprintPorts

      private final int[] _fingerprintPorts
      Ports used for the fingerprint matching.

    • _fingerprintFamily

      private String _fingerprintFamily
      The one family option of the current candidate, or null.

    • _fingerprintIPCount

      private int _fingerprintIPCount
      Number of entries used in _fingerprintIPs.

    • _fingerprintPortCount

      private int _fingerprintPortCount
      Number of entries used in _fingerprintPorts.

    • _skippedPeers

      private final Set<Hash> _skippedPeers
      The peers left out of the search.

    • _queriedFloodfills

      private final Set<Hash> _queriedFloodfills
      Floodfill peers we've sent queries to in this search — for active-query tracking.

    • _widened

      private boolean _widened
      Set once the candidate set has been widened for beta confirmation. Guarded by this. @since 0.9.71+.

    • MAX_NON_FF

      private static final int MAX_NON_FF
      Most non-floodfill peers queried.
      See Also:

    • TOTAL_SEARCH_LIMIT

      private static final int TOTAL_SEARCH_LIMIT
      Max number of peers to query.
      See Also:

    • TOTAL_SEARCH_LIMIT_WHEN_FF

      private static final int TOTAL_SEARCH_LIMIT_WHEN_FF
      Max number of peers to query if we are ff.
      See Also:

    • EXTRA_PEERS

      private static final int EXTRA_PEERS
      Extra peers to get from peer selector, as we may discard some before querying.
      See Also:

    • IP_CLOSE_BYTES

      private static final int IP_CLOSE_BYTES
      Leading IP bytes counted as close.
      See Also:

    • BETA_CONFIRM

      private static final int BETA_CONFIRM
      Kademlia's beta: before a search may die with candidates exhausted, at least this many of the closest known peers must have been actually queried. When candidates run out first, the candidate set is widened once (see widenCandidatesLocked()).
      See Also:

    • PROP_MAX_SEARCH_TIME

      public static final String PROP_MAX_SEARCH_TIME
      Config key for the total search time cap.
      See Also:

    • MAX_SEARCH_TIME_DEFAULT

      private static final long MAX_SEARCH_TIME_DEFAULT
      Default total search time cap (15s).
      See Also:

    • _maxSearchTime

      private static volatile long _maxSearchTime
      Total search time cap - dynamically loadable.

    • MAX_RI_ADDRESSES

      private static final int MAX_RI_ADDRESSES
      Upper bound on the keys one peer can contribute: the comm system's address plus at most MAX_RI_ADDRESSES netDb addresses. RouterInfo rejects a longer parsed or assigned address list, so this is a hard cap.
      See Also:

    • MAX_FINGERPRINT_ENTRIES

      private static final int MAX_FINGERPRINT_ENTRIES
      Fingerprint entries we can store in a reply.
      See Also:

    • COMPLETED_CACHE_SIZE

      private static final int COMPLETED_CACHE_SIZE
      Cache size for recently completed peer replies to avoid false positive bans.
      See Also:

    • PROP_LATE_REPLY_GRACE

      private static final String PROP_LATE_REPLY_GRACE
      Config key for the late reply grace period.
      See Also:

    • LATE_REPLY_GRACE_PERIOD_DEFAULT

      private static final long LATE_REPLY_GRACE_PERIOD_DEFAULT
      Default grace period for late replies (5 min).
      See Also:

    • _lateReplyGracePeriod

      private static volatile long _lateReplyGracePeriod
      Grace period for late replies - dynamically loadable.

    • _recentlyCompleted

      private static final ConcurrentHashMap<Hash,Long> _recentlyCompleted
      Static cache of recently completed searches: peer hash -> expiration timestamp.

    • _singleSearchTime

      private final long _singleSearchTime
      The time before we give up and start a new search - much shorter than the message's expire time Longer than the typ. response time of 1.0 - 1.5 sec, but short enough that we move on to another peer quickly.

    • SINGLE_SEARCH_TIME

      private static final long SINGLE_SEARCH_TIME
      The default single search time.
      See Also:

    • MIN_SINGLE_SEARCH_TIME

      private static final long MIN_SINGLE_SEARCH_TIME
      Smallest single search time, in ms.
      See Also:

    • SINGLE_SEARCH_MSG_TIME

      private static final long SINGLE_SEARCH_MSG_TIME
      The actual expire time for a search message.
      See Also:

    • _maxConcurrent

      private int _maxConcurrent
      Use instead of CONCURRENT_SEARCHES in super() which is final. For now, we don't do concurrent, but we keep SINGLE_SEARCH_TIME very short, so we have effective concurrency in that we fail a search quickly.

    • _maxConcurrentDefault

      private static volatile int _maxConcurrentDefault
      The default _maxConcurrent, 4 on a slow system, otherwise 16.

    • _maxLeaseSetLookupTime

      private static volatile int _maxLeaseSetLookupTime
      Adaptive deadline cap (ms) for LeaseSet lookups only. RouterInfo lookups continue to use getMaxSearchTime(). Tuned live by the Tuner toward ~4x the observed netDb.successTime, floored so healthy-but-slow searches aren't abandoned. Defaults to the max search time so behavior is unchanged until the Tuner adjusts it.

    • _maxRouterInfoLookupTime

      private static volatile int _maxRouterInfoLookupTime
      Adaptive deadline cap (ms) for RouterInfo lookups. Used for transit next-hop lookups, where a message is held until the lookup completes or times out; a long hold during a spike tanks transit throughput. Defaults to a shorter cap than the max search time so a missing or unreachable RouterInfo fails fast and the source can reroute. Tuned live by the Tuner toward ~4x the observed netDb.successTime.

    • PROP_ENCRYPT_RI

      public static final String PROP_ENCRYPT_RI
      Property toggling encryption of the RouterInfo sent in a lookup.
      See Also:

    • DEFAULT_ENCRYPT_RI

      public static final boolean DEFAULT_ENCRYPT_RI
      Only on fast boxes, for now.

    • _tunedSearchLimit

      private static volatile int _tunedSearchLimit
      Tuner-set search limit, negative if unset.

    • _tunedSingleSearchTime

      private static volatile int _tunedSingleSearchTime
      Tuner-set single search time, negative if unset.

  • Constructor Details

    • IterativeSearchJob

      public IterativeSearchJob(RouterContext ctx, FloodfillNetworkDatabaseFacade facade, Hash key, Job onFind, Job onFailed, int timeoutMs, boolean isLease)
      Lookup using exploratory tunnels.
      Parameters:
      ctx - the router context
      facade - the network database the key is looked up in
      key - the hash to search for, a RouterInfo or LeaseSet hash
      onFind - run when the search returns a result
      onFailed - run when the search fails or the timeout expires
      timeoutMs - milliseconds to search for, before the per-type deadline caps are applied
      isLease - true to search for a LeaseSet, false for a RouterInfo

    • IterativeSearchJob

      public IterativeSearchJob(RouterContext ctx, FloodfillNetworkDatabaseFacade facade, Hash key, Job onFind, Job onFailed, int timeoutMs, boolean isLease, Hash fromLocalDest)
      Lookup using the client's tunnels. Do not use for RI lookups down client tunnels, as the response will be dropped in InboundMessageDistributor.
      Parameters:
      ctx - the router context
      facade - the network database the key is looked up in
      key - the hash to search for, a RouterInfo or LeaseSet hash
      onFind - run when the search returns a result
      onFailed - run when the search fails or the timeout expires
      timeoutMs - milliseconds to search for, before the per-type deadline caps are applied
      isLease - true to search for a LeaseSet, false for a RouterInfo
      fromLocalDest - use these tunnels for the lookup, or null for exploratory

  • Method Details

    • shouldSkipPeer

      static boolean shouldSkipPeer(boolean recentlyQueried, boolean overloaded, boolean ipClose, int remainingCandidates)
      Skip policy for candidate floodfill peers: a peer is skipped only when at least one other candidate remains, so a starved search always makes progress. Cooldown, overload, and IP-closeness are soft signals.
      Parameters:
      recentlyQueried - true if the peer was queried within the cooldown period
      overloaded - true if the peer already has MAX_CONCURRENT_PER_FLOODFILL active queries
      ipClose - true if the peer shares IPs with an already-queried peer
      remainingCandidates - number of candidate peers left after this one is removed
      Returns:
      true if the peer should be skipped

    • lookupRIUnvalidated

      private static RouterInfo lookupRIUnvalidated(RouterContext ctx, Hash peer)
      Look up a peer's RouterInfo in the router's main NetDb, skipping the full validation performed by NetworkDatabaseFacade.lookupRouterInfoLocally(Hash). The main NetDb is used rather than this job's facade, which may be a client NetDb.
      Parameters:
      ctx - the router context
      peer - the peer hash
      Returns:
      the RouterInfo, or null if not held as a RouterInfo

    • collectFingerprint

      private void collectFingerprint(RouterContext ctx, Hash peer, int mask)
      Collect one candidate's fingerprint keys into the reusable scratch buffers, without claiming them.

      Masked IPs are packed into a long via FloodfillPeerSelector.maskedIPKey(byte[], int) (whose IPv4/IPv6 marker bit keeps the address families apart), ports into an int, and the family option kept as the String it is.

      Parameters:
      ctx - the router context
      peer - hash of the candidate to fingerprint
      mask - byte count to match

    • fingerprintClaimed

      private boolean fingerprintClaimed()
      Is any key of the candidate collected by collectFingerprint(RouterContext, Hash, int) already claimed by a peer this search has queried?

      Test-only: the caller may still reject the candidate on other grounds and must then claim nothing.

      Returns:
      true if any key was already claimed

    • claimFingerprint

      private void claimFingerprint()
      Claim every key collected by collectFingerprint(RouterContext, Hash, int), so later candidates of the same entity are skipped.

    • getMaxSearchTime

      public static long getMaxSearchTime()
      The current total search time cap.
      Returns:
      the cap in ms

    • setMaxSearchTime

      public static void setMaxSearchTime(int val)
      Total search time cap. Tuner may call this.
      Parameters:
      val - ms, clamped to [10s, 30s]

    • reloadGracePeriod

      public static long reloadGracePeriod(RouterContext ctx)
      Reload grace period from properties (for dynamic tuning). Console may call this.
      Parameters:
      ctx - router context for property lookup
      Returns:
      current grace period in ms

    • getGracePeriod

      private static long getGracePeriod()
      Reads the grace period for late replies.
      Returns:
      the period, in ms

    • getMaxConcurrentDefault

      public static int getMaxConcurrentDefault()
      Maximum concurrent default value.
      Returns:
      the max concurrent default

    • setMaxConcurrentDefault

      public static void setMaxConcurrentDefault(int val)
      Maximum concurrent default value, clamped to [1, 64].
      Parameters:
      val - the new default

    • getMaxRouterInfoLookupTime

      public static int getMaxRouterInfoLookupTime()
      The RouterInfo lookup deadline cap in effect, adjusted live by the Tuner.
      Returns:
      the current RouterInfo lookup deadline cap in ms

    • setMaxRouterInfoLookupTime

      public static void setMaxRouterInfoLookupTime(int val)
      Set the RouterInfo lookup deadline cap, normally called by the Tuner.
      Parameters:
      val - RouterInfo lookup deadline cap in ms, clamped to [5000, max search time]

    • getMaxLeaseSetLookupTime

      public static int getMaxLeaseSetLookupTime()
      The LeaseSet lookup deadline cap in effect, adjusted live by the Tuner.
      Returns:
      the current LeaseSet lookup deadline cap in ms

    • setMaxLeaseSetLookupTime

      public static void setMaxLeaseSetLookupTime(int val)
      Set the LeaseSet lookup deadline cap, normally called by the Tuner.
      Parameters:
      val - LeaseSet lookup deadline cap in ms, clamped to [3000, max search time]

    • setSearchLimit

      public static void setSearchLimit(int limit)
      Set the search limit (called by Tuner).
      Parameters:
      limit - the total search request limit

    • setSingleSearchTime

      public static void setSingleSearchTime(int ms)
      Set the single search time (called by Tuner).
      Parameters:
      ms - the single-search time in milliseconds

    • getSearchLimit

      public static int getSearchLimit(RouterContext ctx, int def)
      The search limit in effect, tuned value if set else config.
      Parameters:
      ctx - the router context
      def - fallback when neither tuned nor configured
      Returns:
      the total search request limit

    • getSingleSearchTime

      public static int getSingleSearchTime(RouterContext ctx, int def)
      The single search time in effect, tuned value if set else config.
      Parameters:
      ctx - the router context
      def - fallback when neither tuned nor configured
      Returns:
      the single-search time in milliseconds

    • runJob

      public void runJob()
      Execute the iterative search, selecting floodfill peers from the k-buckets and sending DatabaseLookupMessages to each. Continues until a reply is received or the search time expires.
      Specified by:
      runJob in interface Job
      Overrides:
      runJob in class FloodSearchJob

    • retry

      private void retry()
      Send lookups to one or more peers, up to the configured concurrent and total limits.

    • widenCandidatesLocked

      private void widenCandidatesLocked()
      When fewer than BETA_CONFIRM peers have been queried and the candidate list is exhausted, widen the candidate set once with the closest known non-floodfill peers, so a failure is confirmed against beta closest peers rather than declared after one or two misses. One-shot: a search widens at most once. Caller must hold this lock.

    • addClosest

      static void addClosest(Collection<Hash> candidates, Collection<Hash> allRouters, Hash rkey, Hash us, Hash key, int cap)
      Add the closest cap peers of allRouters, by XOR distance from rkey, excluding us and key. Package private for testing.

      Selects the cap closest rather than sorting everything: allRouters is the whole netdb (up to 10 000 hashes) and this runs on the first failed lookup of a key, so a full O(n log n) sort bought an ordering of entries nobody reads. A bounded farthest-first heap keeps the cap closest in O(n log cap), and us and the target are skipped while walking instead of by two O(n) list removals afterwards.

      Parameters:
      candidates - the search's candidate set to add to
      allRouters - known router hashes
      rkey - the routing key the search is chasing
      us - our router hash
      key - the lookup target
      cap - max peers to add; nothing is added when it is not positive

    • sendQuery

      private void sendQuery(Hash peer, int previouslyTried)
      Send a DLM to the peer.
      Parameters:
      peer - who to send to
      previouslyTried - how many did we send to before this one?

    • getName

      public String getName()
      Name of this job.
      Specified by:
      getName in interface Job
      Overrides:
      getName in class FloodSearchJob
      Returns:
      the name this job is listed under in the job queue

    • markSawReply

      void markSawReply()
      Note that a peer replied (DSRM processed); subsequent total failure counts as definitive toward the negative cache, not a pure timeout.

    • failed

      void failed(Hash peer, boolean timedOut)
      Note that the peer did not respond with a DSM (either a DSRM, timeout, or failure). This is not necessarily a total failure of the search.
      Parameters:
      peer - the peer that failed
      timedOut - if true, will blame the peer's profile

    • newPeerToTry

      void newPeerToTry(Hash peer)
      A new (floodfill) peer was discovered that may have the answer.
      Parameters:
      peer - may not actually be new

    • getFromHash

      public Hash getFromHash()
      Hash of the dest this query is from.
      Returns:
      null for router

    • wasQueried

      public boolean wasQueried(Hash peer)
      Did we send a request to this peer?
      Parameters:
      peer - the peer hash to check
      Returns:
      true if a query was sent to this peer

    • wasRecentlyQueried

      public static boolean wasRecentlyQueried(Hash peer)
      Was this peer recently queried (within grace period)? Used to avoid false positive bans for late but legitimate replies.
      Parameters:
      peer - the peer hash to check
      Returns:
      true if the peer was queried recently and is in the grace period

    • clearRecentlyQueried

      public static void clearRecentlyQueried(Hash peer)
      Clear peer from grace period cache (received their response).
      Parameters:
      peer - the peer hash to forget

    • timeSent

      long timeSent(Hash peer)
      When did we send the query to the peer?
      Parameters:
      peer - the peer to check
      Returns:
      context time, or -1 if never sent

    • cancelJob

      void cancelJob()
      Cancels the search and delivers failure to all registered waiters. Cancellation is terminal for callers - negative-cache skip, banlist skip, exhausted search window - so this fires the onFailed jobs.

    • releaseFloodfillQueries

      private void releaseFloodfillQueries()
      Decrement active floodfill query counters for all peers queried by this search. Called when the search completes, fails, or cancels.

    • dropped

      public void dropped()
      Dropped by the job queue.
      Specified by:
      dropped in interface Job
      Overrides:
      dropped in class JobImpl

    • failed

      void failed()
      Total failure.
      Overrides:
      failed in class FloodSearchJob

    • success

      void success()
      Called when the search completes successfully. Credits the responding peer in the profile manager, records timing stats, and queues any follow-up jobs.
      Overrides:
      success in class FloodSearchJob