Update of /cvsroot/freenet/freenet/src/freenet/node
In directory sc8-pr-cvs1:/tmp/cvs-serv4685/src/freenet/node
Modified Files:
Node.java FailureTable.java SmartFailureTable.java Main.java
Log Message:
6297:
Lots of Iakin's stuff, but on this commit:
New FailureTable - not secondary failtable yet, but new and improved plain fail table.
Have individual FailItem's, within a FailureEntry, for different HTLs, with a separate
LRU queue,
Use LinkedList's, rather than Heap's, because we don't need an ADT.
Generally a fairly deep rewrite of the same methods.
Initial specs: 20,000 keys, 100,000 items (item is an HTL:time pair).
Don't pass in time - we don't need it, use the current time, and since we are
synchronized this means we always start at the end of the queue.
Index: Node.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/Node.java,v
retrieving revision 1.238
retrieving revision 1.239
diff -u -w -r1.238 -r1.239
--- Node.java 1 Nov 2003 18:50:38 -0000 1.238
+++ Node.java 1 Nov 2003 22:05:36 -0000 1.239
@@ -110,7 +110,8 @@
config.addOption("messageStoreSize", 1, 10000, 1350); // 10000 live
chains
config.addOption("failureTableSize", 1, 20000, 1360); // 20000 failed
keys - uses ~ 2.7MB
- config.addOption("failureTableTime", 1, 1800000l, 1361); // 30 min
+ config.addOption("failureTableItems", 1, 100000, 1361);
+ config.addOption("failureTableTime", 1, 1800000l, 1362); // 30 min
// ARK stuff
config.addOption("minCP", 1, 0.01F, 1370);
Index: FailureTable.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/FailureTable.java,v
retrieving revision 1.16
retrieving revision 1.17
diff -u -w -r1.16 -r1.17
--- FailureTable.java 31 Oct 2003 21:45:34 -0000 1.16
+++ FailureTable.java 1 Nov 2003 22:05:37 -0000 1.17
@@ -3,15 +3,16 @@
import java.io.PrintWriter;
import java.util.Date;
import java.util.Hashtable;
+import java.util.Iterator;
+import java.util.LinkedList;
import java.util.Random;
import freenet.Core;
import freenet.Key;
import freenet.support.Checkpointed;
-import freenet.support.Heap;
-import freenet.support.Heap.Element;
-import freenet.support.sort.ArraySorter;
-import freenet.support.sort.QuickSorter;
+import freenet.support.DoublyLinkedList;
+import freenet.support.DoublyLinkedListImpl;
+import freenet.support.DoublyLinkedListImpl.Item;
/**
* Keeps track of keys that have been failed recently, and automatically
@@ -25,7 +26,7 @@
public static void main(String[] args) {
// Determine memory usage for FT of a given size
final int KEYS = 20000;
- FailureTable ft = new FailureTable(KEYS, 1800000);
+ FailureTable ft = new FailureTable(KEYS, 5*KEYS, 1800000);
Random r = new Random();
Runtime rt = Runtime.getRuntime();
rt.gc();
@@ -39,7 +40,7 @@
byte[] keyval = new byte[20];
r.nextBytes(keyval);
Key k = new Key(keyval);
- ft.failedToFind(k, 10, startTime);
+ ft.failedToFind(k, 10);
}
long endTime = System.currentTimeMillis();
rt.gc();
@@ -77,23 +78,29 @@
}
protected int maxSize;
+ protected int maxItemsSize;
protected long maxMillis;
protected long lastCp = 0;
- protected Hashtable failedKeys;
- protected Heap queue;
+ protected Hashtable failedKeys; // of FailureEntry's
+ // In both cases, most recent is First(), LRU is Last()
+ // Push()/Pop(): MRU
+ // Unshift()/Shift(): LRU
+ DoublyLinkedList entries; // of FailureEntry's
+ DoublyLinkedList items; // of FailItem's
/**
* Creates a new.
* @param size The number of entries to hold.
* @param millis The max amount of time to keep an entry.
*/
- public FailureTable(int size, long millis) {
+ public FailureTable(int size, int itemSize, long millis) {
maxSize = size;
maxMillis = millis;
-
+ maxItemsSize = itemSize;
failedKeys = new Hashtable();
- queue = new Heap();
+ entries = new DoublyLinkedListImpl();
+ items = new DoublyLinkedListImpl();
}
/**
@@ -102,27 +109,31 @@
* @param hopsToLive The hopsToLive when it could not be found.
* @param time The time at which it could not be retreived.
*/
- public synchronized void failedToFind(Key k, int hopsToLive,
- long time) {
+ public synchronized void failedToFind(Key k, int hopsToLive) {
+ long time = System.currentTimeMillis();
+ // Not an argument because it must be NOW - we don't want to mess with ADTs
+
FailureEntry fe = (FailureEntry) failedKeys.get(k);
+
if (fe == null) {
- fe = new FailureEntry(k, hopsToLive, time);
+ fe = new FailureEntry(k, time);
+ fe.failed(hopsToLive, time);
failedKeys.put(k, fe);
+ entries.push(fe);
} else {
- fe.remove();
- if (hopsToLive > fe.hopsToLive) {
- fe.time = time;
- fe.hopsToLive = hopsToLive;
+ entries.remove(fe);
+ fe.failed(hopsToLive, time);
+ entries.push(fe);
}
- }
-
- queue.put(fe);
- while (queue.size() > maxSize) {
- fe = (FailureEntry) queue.pop();
+ while (entries.size() > maxSize) {
+ fe = (FailureEntry) entries.shift();
failedKeys.remove(fe.key);
Core.diagnostics.occurrenceContinuous("failureTableBlocks",
(double) fe.blocks);
}
+ while (items.size() > maxItemsSize) {
+ FailItem fi = (FailItem) items.shift();
+ }
}
/**
@@ -134,16 +145,9 @@
FailureEntry fe = (FailureEntry) failedKeys.get(k);
long time = System.currentTimeMillis();
- if (fe != null && fe.hopsToLive >= hopsToLive &&
- fe.time > (time - maxMillis)) {
+ if (fe == null) return -1;
- fe.blocks++;
- Core.diagnostics.occurrenceContinuous("timeBetweenFailedRequests",
- (double)(time - fe.lastHit));
- fe.lastHit = time;
- return fe.time;
- } else
- return -1;
+ return fe.shouldFail(hopsToLive, time);
}
/**
@@ -169,18 +173,19 @@
* Purges the queue.
*/
public synchronized void checkpoint() {
- lastCp = System.currentTimeMillis();
- long thresh = lastCp - maxMillis;
- while (queue.size() > 0) {
- FailureEntry fe = (FailureEntry) queue.top();
- if (fe.time > thresh) {
- break;
- }
- queue.pop();
- failedKeys.remove(fe.key);
- Core.diagnostics.occurrenceContinuous("failureTableBlocks",
- (double) fe.blocks);
- }
+ // Will need old stuff later, don't bother
+// lastCp = System.currentTimeMillis();
+// long thresh = lastCp - maxMillis;
+// while (queue.size() > 0) {
+// FailureEntry fe = (FailureEntry) queue.top();
+// if (fe.time > thresh) {
+// break;
+// }
+// queue.pop();
+// failedKeys.remove(fe.key);
+// Core.diagnostics.occurrenceContinuous("failureTableBlocks",
+// (double) fe.blocks);
+// }
}
public String getCheckpointName() {
@@ -201,51 +206,161 @@
+ "<th>Age</th><th># of Blocks</th>"
+ "<th>lastHit</th></tr>");
- Element[] elementArray = queue.elementArray();
- QuickSorter.quickSort(new ArraySorter(elementArray));
-
+ FailureEntry fe = (FailureEntry)(entries.head());
long time = System.currentTimeMillis();
- for (int i = 0 ; i < elementArray.length ; i++) {
- FailureEntry fe = (FailureEntry) elementArray[i];
- boolean active = (time - fe.time) < maxMillis;
+ while(fe != null) {
+ fe.toHtml(pw, time);
+ fe = (FailureEntry)fe.getNext();
+ }
+ pw.println("</table>");
+ }
+
+ protected class FailItem extends Item {
+ FailureEntry fe;
+ public int hopsToLive;
+ private long time;
+
+ public FailItem(FailureEntry fe, int hopsToLive, long time) {
+ this.fe = fe;
+ this.hopsToLive = hopsToLive;
+ this.time = time;
+ }
+
+ boolean matches(int htl, long now) {
+ if(htl <= hopsToLive && time + maxMillis < now) {
+ return true;
+ } else return false;
+ }
+
+ /**
+ * @param pw
+ */
+ public void toHtml(PrintWriter pw, long time) {
+ boolean active = (time - fe.lastFail) < maxMillis;
pw.println("<tr><td><font color=\"" + (active ? "red" : "green")
- + "\">" + fe.key + "</font></td><td>" + fe.hopsToLive
- + "</td><td>" + (time - fe.time) / 1000
+ + "\">" + fe.key + "</font></td><td>" +
hopsToLive
+ + "</td><td>" + (time - this.time) / 1000
+ "</td><td>" + fe.blocks
+ "</td><td>" + new Date(fe.lastHit) + "</td></tr>");
+
}
- pw.println("</table>");
}
-
- protected class FailureEntry extends Element {
- public int hopsToLive; //screw getters...
+ protected class FailureEntry extends Item {
private Key key;
- private long time;
private int blocks;
private long lastHit;
+ private long lastFail;
+ private int failures;
- public FailureEntry(Key key, int hopsToLive, long time) {
- this.hopsToLive = hopsToLive;
+ LinkedList myItems;
+ // java.util.LinkedList, NOT DoublyLinkedList, because we are already in
items DLList
+
+ public FailureEntry(Key key, long time) {
+ myItems = new LinkedList();
this.key = key;
- this.time = time;
- this.lastHit = time;
this.blocks = 0;
+ lastHit = time;
+ }
+
+ /**
+ * @param pw
+ */
+ public void toHtml(PrintWriter pw, long time) {
+ for(Iterator i = myItems.iterator();i.hasNext();) {
+ FailItem fi = (FailItem)(i.next());
+ fi.toHtml(pw, time);
+ }
+ }
+
+ /**
+ *
+ */
+ public void remove() {
+ // TODO Auto-generated method stub
+ for(Iterator i = myItems.iterator();i.hasNext();) {
+ FailItem fi = (FailItem)(i.next());
+ myItems.remove(fi);
+ items.remove(fi);
+ }
+ entries.remove(this);
+ }
+
+ /**
+ * Add a FailItem, or update an existing one
+ * @param hopsToLive the HTL of the request when it failed
+ * @param time the time when it failed (must not be
+ * lower than the previous time - intended to be the time when
+ * the enclosing synchronized method was entered).
+ */
+ public void failed(int hopsToLive, long time) {
+ failures++;
+ lastFail = time;
+ boolean found = false;
+ for(Iterator i = myItems.iterator();i.hasNext();) {
+ FailItem fi = (FailItem)(i.next());
+ if(fi.hopsToLive == hopsToLive) {
+ fi.time = time;
+ items.remove(fi);
+ items.push(fi); // MRU
+ found = true;
+ break;
+ }
+ if(fi.time + maxMillis < time) {
+ // Remove it
+ items.remove(fi);
+ i.remove();
+ }
+ }
+ if(!found) {
+ FailItem fi = new FailItem(this, hopsToLive, time);
+ items.push(fi);
+ myItems.addLast(fi);
+ }
+ }
+
+ /**
+ * Checks whether a query should fail.
+ * @return The time at which the query that failed to find the key
+ * occured, or < 0 if no such query is known.
+ */
+ public long shouldFail(int hopsToLive, long now) {
+ for(Iterator i = myItems.iterator();i.hasNext();) {
+ FailItem fi = (FailItem)(i.next());
+ if(fi.time + maxMillis < now) {
+ items.remove(fi);
+ i.remove();
+ continue;
+ }
+ if(fi.hopsToLive >= hopsToLive) {
+ blocks++;
+
Core.diagnostics.occurrenceContinuous("timeBetweenFailedRequests",
+
(double)(now - lastHit));
+ lastHit = now;
+ return fi.time;
+ }
+ }
+ return -1;
+ }
+ /**
+ * @param item
+ */
+ public void add(FailItem item) {
+ myItems.add(item);
}
public int compareTo(Object o) {
//FailureEntry fe = (FailureEntry) o;
//return (int) (fe.time - time);
// older is "bigger"
- long ot = ((FailureEntry) o).time;
- return time == ot ? 0 : (time > ot ? -1 : 1);
+ long ot = ((FailureEntry) o).lastFail;
+ return lastFail == ot ? 0 : (lastFail > ot ? -1 : 1);
}
public String toString() {
- return key.toString() + " " + hopsToLive + " " + new Date(time);
+ return key.toString();
}
-
}
Index: SmartFailureTable.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/SmartFailureTable.java,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -w -r1.4 -r1.5
--- SmartFailureTable.java 30 Oct 2003 01:34:02 -0000 1.4
+++ SmartFailureTable.java 1 Nov 2003 22:05:37 -0000 1.5
@@ -9,57 +9,61 @@
* on devl. (yeah I know such description is lame --zab)
*/
public class SmartFailureTable extends FailureTable {
- final int treshold;
-
- /**
- * reuse the constructor
- * @param treshold - the number of hits before the key
- * is marked irrelevant to pDNF calculation
- */
- public SmartFailureTable(int size, int treshold){
- super(size,-1); //keys don't expire, do they?
- this.treshold = treshold;
- }
-
- public synchronized void checkpoint() {
- lastCp = System.currentTimeMillis();
- //override and do nothing, keys don't expire
- }
-
- //contains a list of FailureEntries, doesn't extend it, aggregates it instead.
- private class ExtendedFailureEntry {
- Key key;
- LinkedList history;
- public ExtendedFailureEntry(Key key, int hopsToLive, long time) {
- this.key = key;
- history = new LinkedList();
- history.add(new FailureEntry(key, hopsToLive, time));
- }
- public FailureEntry getOldestEntry() {
- return (FailureEntry) history.getFirst();
- }
-
- public FailureEntry getNewestEntry() {
- return (FailureEntry) history.getLast();
- }
-
- public void update(int hopsToLive, long time) {
- history.addLast(new FailureEntry(key,hopsToLive,time));
- }
- }
-
- /**
- * override...
- */
- public synchronized void failedToFind(Key k, int hopsToLive, long time) {
- ExtendedFailureEntry efe = (ExtendedFailureEntry) failedKeys.get(k);
- if (efe==null){
- efe = new ExtendedFailureEntry(k, hopsToLive, time);
- failedKeys.put(k,efe);
- } else
- if (hopsToLive >= efe.getNewestEntry().hopsToLive) //FIXME: > or >=???
- efe.update(hopsToLive,time);
-
- //FINISHUP: decide if the heap is needed.
- }
+ SmartFailureTable() {
+ super(-1,-1,-1);
+ throw new UnsupportedOperationException();
+ }
+// final int treshold;
+//
+// /**
+// * reuse the constructor
+// * @param treshold - the number of hits before the key
+// * is marked irrelevant to pDNF calculation
+// */
+// public SmartFailureTable(int size, int treshold){
+// super(size,-1); //keys don't expire, do they?
+// this.treshold = treshold;
+// }
+//
+// public synchronized void checkpoint() {
+// lastCp = System.currentTimeMillis();
+// //override and do nothing, keys don't expire
+// }
+//
+// //contains a list of FailureEntries, doesn't extend it, aggregates it instead.
+// private class ExtendedFailureEntry {
+// Key key;
+// LinkedList history;
+// public ExtendedFailureEntry(Key key, int hopsToLive, long time) {
+// this.key = key;
+// history = new LinkedList();
+// history.add(new FailureEntry(key, hopsToLive, time));
+// }
+// public FailureEntry getOldestEntry() {
+// return (FailureEntry) history.getFirst();
+// }
+//
+// public FailureEntry getNewestEntry() {
+// return (FailureEntry) history.getLast();
+// }
+//
+// public void update(int hopsToLive, long time) {
+// history.addLast(new FailureEntry(key,hopsToLive,time));
+// }
+// }
+//
+// /**
+// * override...
+// */
+// public synchronized void failedToFind(Key k, int hopsToLive, long time) {
+// ExtendedFailureEntry efe = (ExtendedFailureEntry) failedKeys.get(k);
+// if (efe==null){
+// efe = new ExtendedFailureEntry(k, hopsToLive, time);
+// failedKeys.put(k,efe);
+// } else
+// if (hopsToLive >= efe.getNewestEntry().hopsToLive) //FIXME: > or >=???
+// efe.update(hopsToLive,time);
+//
+// //FINISHUP: decide if the heap is needed.
+// }
}
Index: Main.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/Main.java,v
retrieving revision 1.289
retrieving revision 1.290
diff -u -w -r1.289 -r1.290
--- Main.java 31 Oct 2003 21:09:11 -0000 1.289
+++ Main.java 1 Nov 2003 22:05:37 -0000 1.290
@@ -816,6 +816,7 @@
FailureTable ft =
new FailureTable(params.getInt("failureTableSize"),
+ params.getInt("failureTableItems"),
params.getLong("failureTableTime"));
_______________________________________________
cvs mailing list
[EMAIL PROTECTED]
http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/cvs
