> Attached patch implements the above, phase 1 of GJ's overload fix plan, > and a crude approximation to phase 2 (it just accepts the requests in the > most successful bucket, if it's partly overloaded). In need of > optimization, and rather coarse (only 16 buckets). Not yet thoroughly > tested, due to network difficulties. > > Future work: > * combine requestDistribution, successDistribution, pSuccess, > binMostSuccessful into a single, more efficient object > * increase to 256 buckets, possibly more, possibly customizable. Keep > smaller numbers of buckets for displaying histograms, and larger numbers > of buckets for overload triage decisions. > * do we want these structures to persist? Do we want them to forget > about hits after a certain time? > * commit after all the above dealt with to minimize disruption due to > resetting datastores etc > * implement phase 2 properly - how to determine Psmin? > * possibly make a histogram out of P(success) > * get CVS write access :)
D'oh.
? noderefs.txt
? src/freenet/.Core.java.swp
? src/freenet/support/KeySizeHistogram.java
Index: src/freenet/Core.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/Core.java,v
retrieving revision 1.10
diff -u -r1.10 Core.java
--- src/freenet/Core.java 25 Apr 2002 05:02:37 -0000 1.10
+++ src/freenet/Core.java 23 Jun 2002 01:39:52 -0000
@@ -211,6 +211,44 @@
/** Distribution of inbound requests over the keyspace. **/
public static KeyHistogram requestDistribution = null;
+ /** Distribution of successful inbound requests over the keyspace **/
+ public static KeyHistogram successDistribution = null;
+
+ /**
+ * Returns the probability of success of a request that would go into
+ * a given bin for stats purposes
+ */ /* fixme: can we optimize these somehow? */
+ public static float pSuccess(int bin)
+ {
+ int x = requestDistribution.getBin(bin);
+ //if(x == 0) return 0;
+ return ((float)successDistribution.getBin(bin) / (float)x);
+ }
+
+ /** Returns the most successful bin
+ */
+ public static int binMostSuccessful()
+ {
+ int ret = -1;
+ float pHighest = 0;
+ for(int i=0;i<successDistribution.length();i++)
+ {
+ int x = requestDistribution.getBin(i);
+ if(requestDistribution.getBin(i)>0)
+ {
+ float p = (float)successDistribution.getBin(i)/(float)x;
+ if(p>pHighest ||
+ (p == pHighest && ret != -1 &&
+ x>requestDistribution.getBin(ret)))
+ {
+ pHighest = p;
+ ret = i;
+ }
+ };
+ }
+ return ret;
+ }
+
/**
* Sets the logging object to be used for logging messages
* @param log a Logger object that will log messages to an output stream.
Index: src/freenet/client/http/NodeStatusServlet.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/client/http/NodeStatusServlet.java,v
retrieving revision 1.26
diff -u -r1.26 NodeStatusServlet.java
--- src/freenet/client/http/NodeStatusServlet.java 30 May 2002 23:56:51 -0000
1.26
+++ src/freenet/client/http/NodeStatusServlet.java 23 Jun 2002 01:39:56 -0000
@@ -41,6 +41,7 @@
import freenet.support.StringMap;
import freenet.support.SimpleStringMap;
import freenet.support.KeyHistogram;
+import freenet.support.KeySizeHistogram;
import freenet.support.graph.BitmapEncoder;
/*
@@ -141,6 +142,11 @@
return;
}
+ if (uri.endsWith("ds_size_histogram.txt")) {
+ sendDSSizeHistogram(resp, false);
+ return;
+ };
+
if (uri.endsWith("inbound_request_histogram.txt")) {
int[] bins = null;
if (node.requestDistribution != null) {
@@ -149,10 +155,21 @@
sendKeyHistogram(resp, false, bins,
"Histogram of requested keys.",
"This count has nothing to do with keys in your
datastore",
- MSG_NO_REQUEST_DIST);
+ MSG_NO_REQUEST_DIST, "keys", false);
return;
}
+ if(uri.endsWith("inbound_success_histogram.txt")) {
+ int [] bins = null;
+ if (node.successDistribution != null) {
+ bins = node.successDistribution.getBins();
+ }
+ sendKeyHistogram(resp, false, bins,
+ "Histogram of successfully requested keys.",
+ "This count has nothing to do with keys in your
+datastore",
+ MSG_NO_REQUEST_DIST, "keys", false);
+ return;
+ }
if (uri.endsWith("key_histogram_data.txt")) {
sendRTHistogram(resp, true);
@@ -164,6 +181,11 @@
return;
}
+ if (uri.endsWith("ds_size_histogram_data.txt")) {
+ sendDSSizeHistogram(resp, true);
+ return;
+ }
+
if (uri.endsWith("inbound_request_histogram_data.txt")) {
int[] bins = null;
if (node.requestDistribution != null) {
@@ -173,11 +195,29 @@
sendKeyHistogram(resp, true, bins,
"Histogram of requested keys.",
"This count has nothing to do with keys in your
datastore",
- MSG_NO_REQUEST_DIST);
+ MSG_NO_REQUEST_DIST, "keys", false);
return;
}
+ if (uri.endsWith("inbound_success_histogram_data.txt")) {
+ int[] bins = null;
+ if (node.successDistribution != null) {
+ bins = node.successDistribution.getBins();
+ }
+
+ sendKeyHistogram(resp, true, bins,
+ "Histogram of successfully requested keys.",
+ "This count has nothing to do with keys in your
+datastore",
+ MSG_NO_REQUEST_DIST, "keys", false);
+ return;
+ }
+
+ if (uri.endsWith("psuccess_data.txt")) {
+ sendPSuccessList(resp);
+ return;
+ }
+
if (uri.endsWith("noderefs.txt")) {
sendRefList(req, resp);
}
@@ -338,13 +378,23 @@
pw.println(" <li> <a href=\"" + baseURL + "ds_histogram.txt\"> " +
" Histogram of keys in the local DataStore. </a>" +
"     <em>Note: Slow. Be patient. </em> ");
- pw.println(" <a href= \"" + baseURL +
- "ds_histogram_data.txt\">" +
+ pw.println(" <li> <a href= \"" + baseURL +
+ "ds_histogram_data.txt\"> " +
"<br>(flat ascii)</a><br>");
-
- pw.println(" <li> <em> TODO: We need distribution data for
succcessful requests. </em>");
- pw.println(" <br>I'm really busy these days. It would be
cool if someone could code");
- pw.println(" this up. --gj");
+ pw.println(" <li> <a href=\"" + baseURL + "ds_size_histogram.txt\">
+" +
+ " Histogram of sizes of keys in local DataStore. </a>");
+ pw.println(" <li> <a href= \"" + baseURL +
+ "ds_size_histogram_data.txt\">" +
+ "<br>(flat ascii)</a><br>");
+
+ pw.println(" <li> <a href=\"" + baseURL +
+"inbound_success_histogram.txt\"> " +
+ " Histogram of successful inbound request search keys </a>");
+ pw.println(" <li> <a href=\"" + baseURL +
+ "inbound_success_histogram_data.txt\">" +
+ "<br>(flat ascii)</a><br>");
+ pw.println(" <li> <a href=\"" + baseURL +
+ "psuccess_data.txt\">" +
+ " Probability of success of an incoming request </a><br>");
pw.println(" </ul> <p>");
pw.println(" <li> <a href=\"" + baseURL +"diagnostics/index.html\">
Diagnostics Values </a> <p>");
pw.println(" <li> <a href=\"" + baseURL +"inboundContacts.txt\"> Inbound
Contact Attempts </a> <br>");
@@ -392,7 +442,7 @@
}
private final static String drawLine(int binNum, int freq) {
- String ret = Integer.toString(binNum, 16) + " |";
+ String ret = "";
for (int i = 0; i < freq; i++) {
ret += "=";
}
@@ -486,7 +536,8 @@
"Histogram of keys in in fred's Routing table",
"This count has nothing to do with keys in your datastore, "
+
"these keys are used for routing",
- MSG_OOPS /* bins should always be non-null */);
+ MSG_OOPS /* bins should always be non-null */,
+ "keys", false);
}
@@ -499,13 +550,57 @@
"Histogram of keys in in fred's data store",
"These are the keys to the data in your node's " +
"local cache (DataStore)",
- MSG_OOPS /* bins should always be non-null */);
+ MSG_OOPS /* bins should always be non-null */,
+ "keys", false);
}
+ private void sendDSSizeHistogram(HttpServletResponse resp, boolean justData)
+throws IOException {
+
+ FSDataStore ds = (FSDataStore) node.ds;
+ KeySizeHistogram histogram = ds.getSizeHistogram();
+
+ sendKeyHistogram(resp, justData, histogram.getBins(),
+ "Histogram of sizes of keys in fred's data store",
+ "These are the numbers of keys in your DataStore" +
+ " of (roughly) each size",
+ MSG_OOPS /* bins should always be non-null */, "keys",
+ true);
+ }
+
+ private void sendPSuccessList(HttpServletResponse resp) throws IOException
+ {
+ resp.setStatus(HttpServletResponse.SC_OK);
+ resp.setContentType("text/plain");
+ PrintWriter pw = resp.getWriter();
+ pw.println("Probability of success of an incoming request");
+ DateFormat df = DateFormat.getDateTimeInstance();
+ String date = df.format(new Date(System.currentTimeMillis()));
+ pw.println(date);
+ float pMax = 0;
+ for (int i = 0; i < node.requestDistribution.length(); i++) {
+ float p = node.pSuccess(i);
+ if(Float.isNaN(p))
+ {
+ pw.println(Integer.toString(i, 16) + " | -");
+ }
+ else
+ {
+ pw.println(Integer.toString(i, 16) + " | " + p);
+ }
+ if(p > pMax) pMax = p;
+ };
+ pw.println("");
+ pw.println("Max: " + pMax);
+ int x = node.binMostSuccessful();
+ if(x != -1) pw.println("Most successful: " + node.binMostSuccessful());
+ resp.flushBuffer();
+ }
+
private void sendKeyHistogram(HttpServletResponse resp, boolean justData, int[]
bins,
String title, String comment,
- String complaint) throws IOException {
+ String complaint, String commodity,
+ boolean exponential) throws IOException {
if (bins == null) {
resp.setStatus(HttpServletResponse.SC_OK);
@@ -526,7 +621,7 @@
}
}
- float scale = 1.0f;
+ double scale = 1.0f;
if (maximum > 64) {
// REDFLAG: test
// Scale factor for ASCII limits line lengths to 64
@@ -543,24 +638,40 @@
if (justData) {
pw.println("# " + title);
pw.println("# " + date);
- pw.println("# keys: " + count);
+ pw.println("# " + commodity + ": " + count);
}
else {
pw.println(title);
pw.println(comment);
pw.println(date);
- pw.println("keys: " + count);
+ pw.println(commodity + ": " + count);
pw.println("scale factor: " + scale + " (This is used to keep lines < 64
characters)");
pw.println("");
}
for (i = 0; i < bins.length; i++) {
+ String line;
+ if(exponential)
+ {
+ line = shortPowerString(10+i);
+ if(i == (bins.length-1))
+ {
+ line += "+";
+ };
+ }
+ else
+ {
+ line = Integer.toString(i, 16);
+ };
if (justData) {
- pw.println(i + "\t" + bins[i] );
+ line += "\t" + bins[i];
}
else {
- pw.println(drawLine(i, ((int)(bins[i] * scale))));
+ if(!exponential || (i != (bins.length-1))) line += " ";
+ while(line.length()<5) { line = " " + line; };
+ line += "|" + drawLine(i, ((int)(bins[i] * scale)));
}
+ pw.println(line);
}
pw.println("");
@@ -572,6 +683,19 @@
resp.flushBuffer();
}
+ private String shortPowerString(int power)
+ {
+ int x = power % 10;
+ if(x==10) x = 0;
+ String ret = Integer.toString(1 << x);
+ char SI[] = {'k','M','G','T','P','E'};
+ if(power >= 10)
+ {
+ ret += SI[(power/10)-1];
+ };
+ return ret;
+ };
+
private void sendStatusPage(HttpServletResponse resp) throws IOException {
long now = System.currentTimeMillis();
DateFormat df = DateFormat.getDateTimeInstance();
Index: src/freenet/node/Main.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/Main.java,v
retrieving revision 1.44
diff -u -r1.44 Main.java
--- src/freenet/node/Main.java 1 Jun 2002 22:01:03 -0000 1.44
+++ src/freenet/node/Main.java 23 Jun 2002 01:40:01 -0000
@@ -635,6 +635,10 @@
Core.requestDistribution = new KeyHistogram();
}
+ // Non-optional because we want to use it for request
+ // triage in overload
+ Core.successDistribution = new KeyHistogram();
+
// the FCP interface
SessionHandler clientSh = new SessionHandler();
clientSh.register(new FnpLinkManager(), 10);
Index: src/freenet/node/Node.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/Node.java,v
retrieving revision 1.22
diff -u -r1.22 Node.java
--- src/freenet/node/Node.java 8 Jun 2002 02:35:45 -0000 1.22
+++ src/freenet/node/Node.java 23 Jun 2002 01:40:04 -0000
@@ -969,7 +969,11 @@
// Node is overloaded, but we can handle it
if (ft.contains(req.searchKey) ||
((activeJobs() < succcessfulThreadCutoff) &&
- ds.contains(req.searchKey))) {
+ (ds.contains(req.searchKey) ||
+ (((int)req.searchKey.getVal()[0]) & 0xff) >>> ((byte)4) ==
+ binMostSuccessful()))
+ )
+ {
if (inboundRequests != null) {
inboundRequests.incSuccesses(diagAddr);
}
Index: src/freenet/node/ds/FSDataStore.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/ds/FSDataStore.java,v
retrieving revision 1.6
diff -u -r1.6 FSDataStore.java
--- src/freenet/node/ds/FSDataStore.java 25 Apr 2002 05:02:37 -0000 1.6
+++ src/freenet/node/ds/FSDataStore.java 23 Jun 2002 01:40:04 -0000
@@ -261,6 +261,27 @@
return histogram;
}
+ public KeySizeHistogram getSizeHistogram() {
+ KeySizeHistogram histogram = new KeySizeHistogram();
+
+ synchronized (dir.semaphore()) {
+ Enumeration keys = dir.keys(true);
+ while (keys.hasMoreElements()) {
+ FileNumber fn = (FileNumber) keys.nextElement();
+ Buffer buffer = dir.fetch(fn);
+ try {
+ histogram.add( new Key(fn.getByteArray()), buffer.length() );
+ }
+ finally
+ {
+ buffer.release();
+ }
+ }
+ }
+
+ return histogram;
+ }
+
private static final class KeyWalk implements Walk {
private final Walk fnw;
KeyWalk(Walk fnw) {
Index: src/freenet/node/states/request/AwaitingStoreData.java
===================================================================
RCS file:
/cvsroot/freenet/freenet/src/freenet/node/states/request/AwaitingStoreData.java,v
retrieving revision 1.5
diff -u -r1.5 AwaitingStoreData.java
--- src/freenet/node/states/request/AwaitingStoreData.java 25 Mar 2002 22:18:44
-0000 1.5
+++ src/freenet/node/states/request/AwaitingStoreData.java 23 Jun 2002 01:40:05
+-0000
@@ -76,7 +76,17 @@
}
// yay!
routes.routeSucceeded();
- // Update global network load estimate stats.
+
+ // Update successful request distribution
+ if (n.successDistribution != null)
+ {
+ if(origPeer != null)
+ {
+ n.successDistribution.add(searchKey);
+ };
+ };
+
+ // Update global network load estimate stats.
n.loadStats.storeRequestRateForNode(sd.dataSource(), sd.requestsPerHour());
relayStoreData(n, sd);
Index: src/freenet/node/states/request/SendingReply.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/states/request/SendingReply.java,v
retrieving revision 1.4
diff -u -r1.4 SendingReply.java
--- src/freenet/node/states/request/SendingReply.java 25 Mar 2002 22:18:44 -0000
1.4
+++ src/freenet/node/states/request/SendingReply.java 23 Jun 2002 01:40:05 -0000
@@ -48,8 +48,17 @@
n.logger.log(this,
"Failed to send back StoreData to peer " + e.peer,
e, Logger.MINOR);
+ // Not our fault, so still counts
}
- return new RequestDone(this);
+ // Update successful request distribution
+ if (n.successDistribution != null)
+ {
+ if(origPeer != null)
+ {
+ n.successDistribution.add(searchKey);
+ };
+ };
+ return new RequestDone(this);
case Presentation.CB_CACHE_FAILED:
fail(n, "Cache failed");
Index: src/freenet/support/KeyHistogram.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/support/KeyHistogram.java,v
retrieving revision 1.1
diff -u -r1.1 KeyHistogram.java
--- src/freenet/support/KeyHistogram.java 25 Apr 2002 05:02:37 -0000 1.1
+++ src/freenet/support/KeyHistogram.java 23 Jun 2002 01:40:06 -0000
@@ -18,5 +18,13 @@
return ret;
}
+ public synchronized int getBin(int bin) {
+ return bins[bin];
+ }
+
+ public synchronized int length() {
+ return bins.length;
+ }
+
private int bins[] = new int[16];
}
package freenet.support;
import freenet.Key;
public class KeySizeHistogram {
public synchronized void add(Key key, long len) {
int binNumber = 0;
int i = 2048;
for(binNumber=0; i<len;)
{
i <<= 1;
binNumber++;
};
if(binNumber < 0) binNumber = 0;
if(binNumber > 15) binNumber = 15;
bins[binNumber]++;
}
// Distribution of keys with most significant nibbles 0-f.
public synchronized int[] getBins() {
int[] ret = new int[bins.length];
System.arraycopy(bins, 0, ret, 0, bins.length);
return ret;
}
private int bins[] = new int[21];
}
msg03324/pgp00000.pgp
Description: PGP signature
