Author: toad
Date: 2008-02-06 20:33:23 +0000 (Wed, 06 Feb 2008)
New Revision: 17611
Added:
trunk/freenet/src/freenet/node/TimedOutNodesList.java
Modified:
trunk/freenet/src/freenet/node/AnnounceSender.java
trunk/freenet/src/freenet/node/CHKInsertSender.java
trunk/freenet/src/freenet/node/FailureTable.java
trunk/freenet/src/freenet/node/FailureTableEntry.java
trunk/freenet/src/freenet/node/NetworkIDManager.java
trunk/freenet/src/freenet/node/NodeDispatcher.java
trunk/freenet/src/freenet/node/PeerManager.java
trunk/freenet/src/freenet/node/RequestSender.java
trunk/freenet/src/freenet/node/ResettingHTLProbeRequestSender.java
trunk/freenet/src/freenet/node/SSKInsertSender.java
Log:
Per-node failure tables. Untested. Basically, if we've recently routed a
specific key to a specific node, and we got a DNF, don't do it again unless we
have no other option (a bit more complex though). Benefits:
- Significant improvement in security against cancer nodes or nodes which fail
all requests for a specific key for some other reason.
- Significant improvement in performance for very popular keys (frequently
requested).
Modified: trunk/freenet/src/freenet/node/AnnounceSender.java
===================================================================
--- trunk/freenet/src/freenet/node/AnnounceSender.java 2008-02-06 20:07:51 UTC
(rev 17610)
+++ trunk/freenet/src/freenet/node/AnnounceSender.java 2008-02-06 20:33:23 UTC
(rev 17611)
@@ -115,7 +115,7 @@
PeerNode next;
if(onlyNode == null) {
// Route it
- next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1, null);
+ next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1, null, null);
} else {
next = onlyNode;
if(nodesRoutedTo.contains(onlyNode)) {
Modified: trunk/freenet/src/freenet/node/CHKInsertSender.java
===================================================================
--- trunk/freenet/src/freenet/node/CHKInsertSender.java 2008-02-06 20:07:51 UTC
(rev 17610)
+++ trunk/freenet/src/freenet/node/CHKInsertSender.java 2008-02-06 20:33:23 UTC
(rev 17611)
@@ -279,7 +279,7 @@
PeerNode next;
// Can backtrack, so only route to nodes closer than we are to
target.
double nextValue;
- next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1, null);
+ next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1, null, null);
if(next == null) {
// Backtrack
Modified: trunk/freenet/src/freenet/node/FailureTable.java
===================================================================
--- trunk/freenet/src/freenet/node/FailureTable.java 2008-02-06 20:07:51 UTC
(rev 17610)
+++ trunk/freenet/src/freenet/node/FailureTable.java 2008-02-06 20:33:23 UTC
(rev 17611)
@@ -125,46 +125,6 @@
}
}
- /**
- * Called when a request is made. Determine whether we should fail the
request, and add the requestors to the list
- * of interested nodes.
- * @param key The key to fetch.
- * @param htl The HTL it will be fetched at.
- * @param requestor The node requesting it.
- * @return True if the request should be failed with an
FNPRecentlyFailed.
- */
- public synchronized boolean shouldFail(Key key, short htl, PeerNode
requestor) {
- long now = System.currentTimeMillis();
- FailureTableEntry entry = (FailureTableEntry)
entriesByKey.get(key);
- if(entry == null) {
- // Don't know anything about the key
- return false;
- }
- entry.addRequestor(requestor, now);
- if(htl > entry.htl) {
- // If the HTL is higher this time, let it through
- entriesByKey.push(key, entry);
- return false;
- }
- if(now > entry.timeoutTime) {
- // If it's more than 10 minutes since we sent a
request, let it through
- return false;
- }
- /*
- * If the best node available now is closer than the best
location we have routed to so far, out of those
- * nodes which are still connected, then accept the request.
- *
- * Note that this means we can route to the same node twice -
but only if its location improves.
- */
- double bestLiveLocDiff = entry.bestLiveLocDiff();
-
- PeerNode p = peers.closerPeer(requestor, null, null,
key.toNormalizedDouble(), true, false, 0, null, bestLiveLocDiff);
-
- if(p != null) return false; // there is a better route now / we
want to retry an old one
-
- return true; // kill the request
- }
-
private final class BlockOfferList {
private BlockOffer[] offers;
final FailureTableEntry entry;
@@ -477,4 +437,10 @@
public void onDisconnect(final PeerNode pn) {
// FIXME do something (off thread if expensive)
}
+
+ public TimedOutNodesList getTimedOutNodesList(Key key) {
+ synchronized(this) {
+ return (FailureTableEntry) entriesByKey.get(key);
+ }
+ }
}
Modified: trunk/freenet/src/freenet/node/FailureTableEntry.java
===================================================================
--- trunk/freenet/src/freenet/node/FailureTableEntry.java 2008-02-06
20:07:51 UTC (rev 17610)
+++ trunk/freenet/src/freenet/node/FailureTableEntry.java 2008-02-06
20:33:23 UTC (rev 17611)
@@ -10,7 +10,7 @@
import freenet.support.Logger;
import freenet.support.StringArray;
-class FailureTableEntry {
+class FailureTableEntry implements TimedOutNodesList {
/** The key */
Key key; // FIXME should this be stored compressed somehow e.g. just
the routing key?
@@ -475,4 +475,13 @@
return true;
}
+ public synchronized long getTimeoutTime(PeerNode peer) {
+ for(int i=0;i<requestedNodes.length;i++) {
+ if(requestedNodes[i].get() == peer) {
+ return requestedTimeouts[i];
+ }
+ }
+ return -1; // not timed out
+ }
+
}
\ No newline at end of file
Modified: trunk/freenet/src/freenet/node/NetworkIDManager.java
===================================================================
--- trunk/freenet/src/freenet/node/NetworkIDManager.java 2008-02-06
20:07:51 UTC (rev 17610)
+++ trunk/freenet/src/freenet/node/NetworkIDManager.java 2008-02-06
20:33:23 UTC (rev 17611)
@@ -100,7 +100,7 @@
if (htl > dawnHtl &&
routedTo.isEmpty()) {
next=node.peers.getRandomPeer(source);
} else {
-
next=node.peers.closerPeer(source, routedTo, notIgnored, target, true,
node.isAdvancedModeEnabled(), -1, null);
+
next=node.peers.closerPeer(source, routedTo, notIgnored, target, true,
node.isAdvancedModeEnabled(), -1, null, null);
}
if (next==null) {
Modified: trunk/freenet/src/freenet/node/NodeDispatcher.java
===================================================================
--- trunk/freenet/src/freenet/node/NodeDispatcher.java 2008-02-06 20:07:51 UTC
(rev 17610)
+++ trunk/freenet/src/freenet/node/NodeDispatcher.java 2008-02-06 20:33:23 UTC
(rev 17611)
@@ -566,7 +566,7 @@
// Forward
m = preForward(m, htl);
while(true) {
- PeerNode next = node.peers.closerPeer(pn, ctx.routedTo,
ctx.notIgnored, target, true, node.isAdvancedModeEnabled(), -1, null);
+ PeerNode next = node.peers.closerPeer(pn, ctx.routedTo,
ctx.notIgnored, target, true, node.isAdvancedModeEnabled(), -1, null, null);
if(logMINOR) Logger.minor(this, "Next: "+next+"
message: "+m);
if(next != null) {
// next is connected, or at least has been =>
next.getPeer() CANNOT be null.
Modified: trunk/freenet/src/freenet/node/PeerManager.java
===================================================================
--- trunk/freenet/src/freenet/node/PeerManager.java 2008-02-06 20:07:51 UTC
(rev 17610)
+++ trunk/freenet/src/freenet/node/PeerManager.java 2008-02-06 20:33:23 UTC
(rev 17611)
@@ -30,6 +30,7 @@
import freenet.io.comm.Peer;
import freenet.io.comm.PeerParseException;
import freenet.io.comm.ReferenceSignatureVerificationException;
+import freenet.keys.Key;
import freenet.node.useralerts.PeerManagerUserAlert;
import freenet.support.Logger;
import freenet.support.ShortBuffer;
@@ -48,6 +49,7 @@
public class PeerManager {
private static boolean logMINOR;
+ private static boolean logDEBUG;
/** Our Node */
final Node node;
@@ -108,6 +110,7 @@
public PeerManager(Node node) {
Logger.normal(this, "Creating PeerManager");
logMINOR = Logger.shouldLog(Logger.MINOR, this);
+ logDEBUG = Logger.shouldLog(Logger.DEBUG, this);
peerNodeStatuses = new HashMap();
peerNodeStatusesDarknet = new HashMap();
peerNodeRoutingBackoffReasons = new HashMap();
@@ -359,6 +362,7 @@
public void addConnectedPeer(PeerNode pn) {
logMINOR = Logger.shouldLog(Logger.MINOR, this);
+ logDEBUG = Logger.shouldLog(Logger.DEBUG, this);
if(!pn.isRoutable()) {
if(logMINOR) Logger.minor(this, "Not ReallyConnected: "+pn);
return;
@@ -571,6 +575,7 @@
// reconnect, and they can't do it yet as we are synchronized.
Vector v = new Vector(connectedPeers.length);
logMINOR = Logger.shouldLog(Logger.MINOR, this);
+ logDEBUG = Logger.shouldLog(Logger.DEBUG, this);
for(int i=0;i<myPeers.length;i++) {
PeerNode pn = myPeers[i];
if(pn == exclude) continue;
@@ -691,8 +696,8 @@
return closestDist < nodeDist;
}
- public PeerNode closerPeer(PeerNode pn, Set routedTo, Set notIgnored,
double loc, boolean ignoreSelf, boolean calculateMisrouting, int minVersion,
Vector addUnpickedLocsTo) {
- return closerPeer(pn, routedTo, notIgnored, loc, ignoreSelf,
calculateMisrouting, minVersion, addUnpickedLocsTo, 2.0);
+ public PeerNode closerPeer(PeerNode pn, Set routedTo, Set notIgnored,
double loc, boolean ignoreSelf, boolean calculateMisrouting, int minVersion,
Vector addUnpickedLocsTo, Key key) {
+ return closerPeer(pn, routedTo, notIgnored, loc, ignoreSelf,
calculateMisrouting, minVersion, addUnpickedLocsTo, 2.0, key);
}
/**
@@ -704,8 +709,10 @@
* @param addUnpickedLocsTo Add all locations we didn't choose which we
could have routed to to
* this array. Remove the location of the peer we pick from it.
* @param maxDistance If a node is further away from the target than
this distance, ignore it.
+ * @param key The original key, if we have it, and if we want to
consult with the FailureTable
+ * to avoid routing to nodes which have recently failed for the same
key.
*/
- public PeerNode closerPeer(PeerNode pn, Set routedTo, Set notIgnored,
double target, boolean ignoreSelf, boolean calculateMisrouting, int minVersion,
Vector addUnpickedLocsTo, double maxDistance) {
+ public PeerNode closerPeer(PeerNode pn, Set routedTo, Set notIgnored,
double target, boolean ignoreSelf, boolean calculateMisrouting, int minVersion,
Vector addUnpickedLocsTo, double maxDistance, Key key) {
PeerNode[] peers;
synchronized (this) {
peers = connectedPeers;
@@ -715,6 +722,15 @@
if(!ignoreSelf)
maxDiff = Location.distance(node.lm.getLocation(), target);
+ /**
+ * Routing order:
+ * - Non-timed-out non-backed-off peers, in order of closeness to the
target.
+ * - Timed-out, non-backed-off peers, least recently timed out first.
+ * - Non-timed-out backed-off peers, in order of closeness to the
target.
+ * - Timed out, backed-off peers, least recently timed out first.
+ * -
+ */
+
PeerNode closest = null;
double closestDistance = Double.MAX_VALUE;
@@ -724,6 +740,19 @@
PeerNode closestNotBackedOff = null;
double closestNotBackedOffDistance = Double.MAX_VALUE;
+ PeerNode leastRecentlyTimedOut = null;
+ long timeLeastRecentlyTimedOut = Long.MAX_VALUE;
+
+ PeerNode leastRecentlyTimedOutBackedOff = null;
+ long timeLeastRecentlyTimedOutBackedOff = Long.MAX_VALUE;
+
+ TimedOutNodesList entry = null;
+
+ if(key != null) {
+ entry = node.failureTable.getTimedOutNodesList(key);
+ }
+
+ long now = System.currentTimeMillis();
int count = 0;
for(int i=0;i<peers.length;i++) {
PeerNode p = peers[i];
@@ -743,6 +772,10 @@
if(logMINOR) Logger.minor(this, "Skipping old version:
"+p.getPeer());
continue;
}
+ long timeout = Long.MAX_VALUE;
+ if(entry != null)
+ timeout = entry.getTimeoutTime(p);
+ boolean timedOut = timeout > now;
//To help avoid odd race conditions, get the location
only once and use it for all calculations.
double loc = p.getLocation();
double diff = Location.distance(loc, target);
@@ -754,25 +787,38 @@
count++;
if(logMINOR) Logger.minor(this, "p.loc="+loc+", target="+target+",
d="+Location.distance(loc, target)+" usedD="+diff+" for "+p.getPeer());
boolean chosen=false;
- if(diff < closestDistance) {
+ if(diff < closestDistance && !timedOut) {
closestDistance = diff;
closest = p;
chosen=true;
if(logMINOR) Logger.minor(this, "New best: "+diff+" ("+loc+"
for "+p.getPeer());
}
boolean backedOff=p.isRoutingBackedOff();
- if(backedOff && (diff < closestBackedOffDistance)) {
+ if(backedOff && (diff < closestBackedOffDistance) &&
!timedOut) {
closestBackedOffDistance = diff;
closestBackedOff = p;
chosen=true;
if(logMINOR) Logger.minor(this, "New best-backed-off: "+diff+"
("+loc+" for "+p.getPeer());
}
- if(!backedOff && (diff < closestNotBackedOffDistance)) {
+ if(!backedOff && (diff < closestNotBackedOffDistance)
&& !timedOut) {
closestNotBackedOffDistance = diff;
closestNotBackedOff = p;
chosen=true;
if(logMINOR) Logger.minor(this, "New best-not-backed-off:
"+diff+" ("+loc+" for "+p.getPeer());
}
+ if(timedOut) {
+ if(!backedOff) {
+ if(timeout < timeLeastRecentlyTimedOut)
{
+ timeLeastRecentlyTimedOut =
timeout;
+ leastRecentlyTimedOut = p;
+ }
+ } else {
+ if(timeout <
timeLeastRecentlyTimedOutBackedOff) {
+
timeLeastRecentlyTimedOutBackedOff = timeout;
+ leastRecentlyTimedOutBackedOff
= p;
+ }
+ }
+ }
if(addUnpickedLocsTo != null && !chosen) {
Double d = new Double(loc);
// Here we can directly compare double's because they
aren't processed in any way, and are finite and (probably) nonzero.
@@ -783,8 +829,18 @@
PeerNode best = closestNotBackedOff;
- if (best==null)
- best = closestBackedOff;
+ if (best==null) {
+ if(leastRecentlyTimedOut != null) {
+ best = leastRecentlyTimedOut;
+ if(logDEBUG) Logger.debug(this, "Using least
recently timed out peer for key: "+best.shortToString());
+ } else if(closestBackedOff != null) {
+ best = closestBackedOff;
+ if(logDEBUG) Logger.debug(this, "Using best
backed-off peer for key: "+best.shortToString());
+ } else if(leastRecentlyTimedOutBackedOff != null) {
+ best = leastRecentlyTimedOutBackedOff;
+ if(logDEBUG) Logger.debug(this, "Using least
recently timed out backed-off peer for key: "+best.shortToString());
+ }
+ }
//racy... getLocation() could have changed
if (calculateMisrouting) {
Modified: trunk/freenet/src/freenet/node/RequestSender.java
===================================================================
--- trunk/freenet/src/freenet/node/RequestSender.java 2008-02-06 20:07:51 UTC
(rev 17610)
+++ trunk/freenet/src/freenet/node/RequestSender.java 2008-02-06 20:33:23 UTC
(rev 17611)
@@ -391,7 +391,7 @@
// Route it
PeerNode next;
- next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1, null);
+ next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1, null, key);
if(next == null) {
if (logMINOR && rejectOverloads>0)
Modified: trunk/freenet/src/freenet/node/ResettingHTLProbeRequestSender.java
===================================================================
--- trunk/freenet/src/freenet/node/ResettingHTLProbeRequestSender.java
2008-02-06 20:07:51 UTC (rev 17610)
+++ trunk/freenet/src/freenet/node/ResettingHTLProbeRequestSender.java
2008-02-06 20:33:23 UTC (rev 17611)
@@ -104,7 +104,7 @@
// Route it
PeerNode next;
- next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1, null);
+ next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1, null, null);
if(next == null) {
if (logMINOR && rejectOverloads>0)
Modified: trunk/freenet/src/freenet/node/SSKInsertSender.java
===================================================================
--- trunk/freenet/src/freenet/node/SSKInsertSender.java 2008-02-06 20:07:51 UTC
(rev 17610)
+++ trunk/freenet/src/freenet/node/SSKInsertSender.java 2008-02-06 20:33:23 UTC
(rev 17611)
@@ -136,7 +136,7 @@
// Can backtrack, so only route to nodes closer than we are to
target.
double nextValue;
synchronized(node.peers) {
- next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1, null);
+ next = node.peers.closerPeer(source, nodesRoutedTo,
nodesNotIgnored, target, true, node.isAdvancedModeEnabled(), -1, null, null);
if(next != null)
nextValue = next.getLocation();
else
Added: trunk/freenet/src/freenet/node/TimedOutNodesList.java
===================================================================
--- trunk/freenet/src/freenet/node/TimedOutNodesList.java
(rev 0)
+++ trunk/freenet/src/freenet/node/TimedOutNodesList.java 2008-02-06
20:33:23 UTC (rev 17611)
@@ -0,0 +1,15 @@
+/* This code is part of Freenet. It is distributed under the GNU General
+ * Public License, version 2 (or at your option any later version). See
+ * http://www.gnu.org/ for further details of the GPL. */
+package freenet.node;
+
+/**
+ * Interface which returns the time at which the failure table timeout on any
given node will
+ * expire for a specific key.
+ * @author toad
+ */
+public interface TimedOutNodesList {
+
+ long getTimeoutTime(PeerNode peer);
+
+}
