commit 9b1e4846c3d602f8097f2700cf228c3df3765e98 Author: Karsten Loesing <karsten.loesing@gmx.net> Date: Mon Feb 6 15:54:16 2012 +0100 Add #4499 sources and tech report draft. --- task-4499/.gitignore | 9 + .../GenerateSampleBridgeDescriptorTarballs.java | 266 ++++++++++++++++++++ task-4499/README | 56 ++++ task-4499/bridge-scaling.R | 23 ++ task-4499/bridge-scaling.csv | 24 ++ task-4499/bridge-scaling.tex | 117 +++++++++ 6 files changed, 495 insertions(+), 0 deletions(-) diff --git a/task-4499/.gitignore b/task-4499/.gitignore new file mode 100644 index 0000000..44c09e8 --- /dev/null +++ b/task-4499/.gitignore @@ -0,0 +1,9 @@ +*.class +*.jar +in/ +out/ +*.png +*.aux +*.log +*.pdf + diff --git a/task-4499/GenerateSampleBridgeDescriptorTarballs.java b/task-4499/GenerateSampleBridgeDescriptorTarballs.java new file mode 100755 index 0000000..a43fd73 --- /dev/null +++ b/task-4499/GenerateSampleBridgeDescriptorTarballs.java @@ -0,0 +1,266 @@ +import java.io.*; +import java.util.*; +import org.apache.commons.codec.*; +import org.apache.commons.codec.digest.*; +import org.apache.commons.codec.binary.*; + +/* Generate sample bridge descriptor tarball contents for metrics-db and + * BridgeDB load tests. Accept an extracted, non-sanitized bridge + * descriptor tarball as input and generate sample tarball contents with + * multiples of bridges up to a given maximum multiplier as output. + * Descriptors are multiplied by overwriting the first four hex characters + * of bridge fingerprints with 0000, 0001, etc., keeping references + * between descriptors intact. + * + * NOTE THAT THE OUTPUT TARBALL CONTENTS ARE NOT SANITIZED! + * + * The changes are only sufficient to trick metrics-db and BridgeDB that + * bridges are distinct. Descriptors may still contain original IP + * addresses in exit policies and other contact information. Sanitized + * descriptors could not be used as input, because they may have skewed + * results too much. */ +public class GenerateSampleBridgeDescriptorTarballs { + public static void main(String[] args) throws Exception { + if (args.length != 3) { + System.err.println("Usage: java " + + GenerateSampleBridgeDescriptorTarballs.class.getName() + + " in-directory out-directory max-multiplier"); + System.exit(1); + } + File inDirectory = new File(args[0]); + File outDirectory = new File(args[1]); + int maxMultiplier = Integer.parseInt(args[2]); + readDescriptors(inDirectory); + for (int multiplier = 1; multiplier <= maxMultiplier; + multiplier *= 2) { + writeDescriptors(new File(outDirectory, String.format("%04d", + multiplier)), multiplier); + } + } + + private static void readDescriptors(File inDirectory) throws Exception { + readNetworkstatusBridges(new File(inDirectory, + "networkstatus-bridges")); + readBridgeDescriptors(new File(inDirectory, "bridge-descriptors")); + readCachedExtrainfos(new File(inDirectory, "cached-extrainfo")); + readCachedExtrainfos(new File(inDirectory, "cached-extrainfo.new")); + } + + private static SortedMap<String, String> networkstatusEntries = + new TreeMap<String, String>(); + private static void readNetworkstatusBridges( + File networkstatusBridgesFile) throws Exception { + BufferedReader br = new BufferedReader(new FileReader( + networkstatusBridgesFile)); + String line, fingerprint = null, published = null; + StringBuilder sb = null; + while ((line = br.readLine()) != null) { + if (line.startsWith("r ")) { + if (sb != null) { + networkstatusEntries.put(fingerprint + " " + published, + sb.toString()); + } + sb = new StringBuilder(); + String[] parts = line.split(" "); + fingerprint = Hex.encodeHexString(Base64.decodeBase64( + parts[2] + "=")).toUpperCase(); + published = parts[4] + " " + parts[5]; + } + sb.append(line + "\n"); + } + if (sb != null) { + networkstatusEntries.put(fingerprint + " " + published, + sb.toString()); + } + br.close(); + } + + private static SortedMap<String, String> bridgeDescriptors = + new TreeMap<String, String>(); + private static void readBridgeDescriptors(File bridgeDescriptorsFile) + throws Exception { + BufferedReader br = new BufferedReader(new FileReader( + bridgeDescriptorsFile)); + String line, fingerprint = null, published = null; + StringBuilder sb = null; + while ((line = br.readLine()) != null) { + if (line.startsWith("@purpose ")) { + if (sb != null) { + bridgeDescriptors.put(fingerprint + " " + published, + sb.toString()); + } + sb = new StringBuilder(); + } else if (line.startsWith("published ")) { + published = line.substring("published ".length()); + } else if (line.startsWith("opt fingerprint ")) { + fingerprint = line.substring("opt fingerprint ".length()). + replaceAll(" ", ""); + } + sb.append(line + "\n"); + } + if (sb != null) { + bridgeDescriptors.put(fingerprint + " " + published, sb.toString()); + } + br.close(); + + } + + private static SortedMap<String, String> cachedExtrainfos = + new TreeMap<String, String>(); + private static void readCachedExtrainfos(File cachedExtrainfoFile) + throws Exception { + BufferedReader br = new BufferedReader(new FileReader( + cachedExtrainfoFile)); + String line, fingerprint = null, published = null; + StringBuilder sb = null; + while ((line = br.readLine()) != null) { + if (line.startsWith("extra-info ")) { + if (sb != null) { + cachedExtrainfos.put(fingerprint + " " + published, + sb.toString()); + } + sb = new StringBuilder(); + fingerprint = line.split(" ")[2]; + } else if (line.startsWith("published ")) { + published = line.substring("published ".length()); + } + sb.append(line + "\n"); + } + if (sb != null) { + cachedExtrainfos.put(fingerprint + " " + published, sb.toString()); + } + br.close(); + } + + private static void writeDescriptors(File outDirectory, int multiplier) + throws Exception { + outDirectory.mkdirs(); + for (File file : outDirectory.listFiles()) { + file.delete(); + } + for (int i = 0; i < multiplier; i++) { + String fingerprintPrefix = String.format("%04x", i); + SortedMap<String, String> extraInfoDigests = writeCachedExtrainfos( + outDirectory, fingerprintPrefix); + SortedMap<String, String> descriptorDigests = + writeBridgeDescriptors(outDirectory, extraInfoDigests, + fingerprintPrefix); + writeNetworkstatusBridges(outDirectory, descriptorDigests, + fingerprintPrefix); + } + } + + private static SortedMap<String, String> writeCachedExtrainfos( + File outDirectory, String fingerprintPrefix) throws Exception { + SortedMap<String, String> extraInfoDigests = + new TreeMap<String, String>(); + BufferedWriter bw = new BufferedWriter(new FileWriter(new File( + outDirectory, "cached-extrainfo"), true)); + for (Map.Entry<String, String> e : cachedExtrainfos.entrySet()) { + String fingerprintPublished = e.getKey(); + String cachedExtrainfo = e.getValue(); + BufferedReader br = new BufferedReader(new StringReader( + cachedExtrainfo)); + String line; + StringBuilder sb = new StringBuilder(); + while ((line = br.readLine()) != null) { + if (line.startsWith("extra-info ")) { + String[] parts = line.split(" "); + sb.append(parts[0] + " " + parts[1] + " " + fingerprintPrefix + + parts[2].substring(4) + "\n"); + } else if (line.equals("router-signature")) { + sb.append(line + "\n"); + String digest = DigestUtils.shaHex(sb.toString()).toUpperCase(); + extraInfoDigests.put(fingerprintPublished, digest); + } else { + sb.append(line + "\n"); + } + } + bw.write(sb.toString()); + } + bw.close(); + return extraInfoDigests; + } + + private static SortedMap<String, String> writeBridgeDescriptors( + File outDirectory, SortedMap<String, String> extraInfoDigests, + String fingerprintPrefix) throws Exception { + SortedMap<String, String> descriptorDigests = + new TreeMap<String, String>(); + BufferedWriter bw = new BufferedWriter(new FileWriter(new File( + outDirectory, "bridge-descriptors"), true)); + for (Map.Entry<String, String> e : bridgeDescriptors.entrySet()) { + String fingerprintPublished = e.getKey(); + String bridgeDescriptor = e.getValue(); + BufferedReader br = new BufferedReader(new StringReader( + bridgeDescriptor)); + String line; + StringBuilder sb = new StringBuilder(); + while ((line = br.readLine()) != null) { + if (line.startsWith("@purpose ")) { + } else if (line.startsWith("opt fingerprint ")) { + sb.append("opt fingerprint " + fingerprintPrefix + + line.substring("opt fingerprint 0000".length()) + "\n"); + } else if (line.startsWith("opt extra-info-digest ")) { + String extraInfoDigest = null; + if (extraInfoDigests.containsKey(fingerprintPublished)) { + extraInfoDigest = extraInfoDigests.get(fingerprintPublished); + } else { + extraInfoDigest = fingerprintPrefix + + line.split(" ")[2].substring(4); + } + sb.append("opt extra-info-digest " + extraInfoDigest + "\n"); + } else if (line.equals("router-signature")) { + sb.append(line + "\n"); + String digest = DigestUtils.shaHex(sb.toString()).toUpperCase(); + descriptorDigests.put(fingerprintPublished, digest); + } else { + sb.append(line + "\n"); + } + } + bw.write("@purpose bridge\n" + sb.toString()); + } + bw.close(); + return descriptorDigests; + } + + private static void writeNetworkstatusBridges(File outDirectory, + SortedMap<String, String> descriptorDigests, + String fingerprintPrefix) throws Exception { + BufferedWriter bw = new BufferedWriter(new FileWriter(new File( + outDirectory, "networkstatus-bridges"), true)); + for (Map.Entry<String, String> e : networkstatusEntries.entrySet()) { + String fingerprintPublished = e.getKey(); + String networkstatusEntry = e.getValue(); + BufferedReader br = new BufferedReader(new StringReader( + networkstatusEntry)); + String line; + StringBuilder sb = new StringBuilder(); + while ((line = br.readLine()) != null) { + if (line.startsWith("r ")) { + String[] parts = line.split(" "); + String fingerprint = parts[2], descriptorDigest = parts[3]; + String newFingerprint = Base64.encodeBase64String(Hex.decodeHex( + (fingerprintPrefix + fingerprintPublished.split(" ")[0]. + substring(4)).toCharArray())).substring(0, 27); + String newDescriptorDigest = null; + if (descriptorDigests.containsKey(fingerprintPublished)) { + newDescriptorDigest = Base64.encodeBase64String(Hex.decodeHex( + descriptorDigests.get(fingerprintPublished). + toCharArray())).substring(0, 27); + } else { + newDescriptorDigest = "AA" + descriptorDigest.substring(2); + } + sb.append("r " + parts[1] + " " + newFingerprint + " " + + newDescriptorDigest + " " + parts[4] + " " + parts[5] + + " " + parts[6] + " " + parts[7] + " " + parts[8] + "\n"); + } else { + sb.append(line + "\n"); + } + } + bw.write(sb.toString()); + } + bw.close(); + } +} + diff --git a/task-4499/README b/task-4499/README new file mode 100644 index 0000000..4bf9264 --- /dev/null +++ b/task-4499/README @@ -0,0 +1,56 @@ +1 Generating sample bridge descriptors +======================================= + +This is a simple Java class to generate sample bridge descriptors for +metrics-db and BridgeDB load tests. + +========================================================================== +======== NOTE THAT THE OUTPUT TARBALL CONTENTS ARE NOT SANITIZED! ======== +========================================================================== + +The changes are only sufficient to trick metrics-db and BridgeDB that +bridges are distinct. Descriptors may still contain original IP addresses +in exit policies and other contact information. Sanitized descriptors +could not be used as input, because they may have skewed results too much. + +Here's how you generate sample bridge descriptors from original +descriptors. + +Extract a non-sanitized bridge descriptor tarball to in/, so that there +are four files: + + in/bridge-descriptors + in/cached-extrainfo.new + in/cached-extrainfo + in/networkstatus-bridges + +Download the Apache Commons Codec .jar file and put in the root directory, +e.g., + + commons-codec-1.4.jar + +Compile the Java class: + + $ javac -cp commons-codec-1.4.jar \ + GenerateSampleBridgeDescriptorTarballs.java + +Run the Java class to generate sample data up to a factor of 256 times the +descriptors in the in/ directory: + + $ java -cp .:commons-codec-1.4.jar \ + GenerateSampleBridgeDescriptorTarballs in out 256 + +Find the generated sample data in the out/ directory. + + +2 Building the tech report +=========================== + +Generate the graph: + + $ R --slave -f bridge-scaling.R + +Build the PDF: + + $ pdflatex bridge-scaling.tex + diff --git a/task-4499/bridge-scaling.R b/task-4499/bridge-scaling.R new file mode 100644 index 0000000..972f240 --- /dev/null +++ b/task-4499/bridge-scaling.R @@ -0,0 +1,23 @@ +library(ggplot2) +d <- read.csv("bridge-scaling.csv", header = TRUE) +t <- d[d$variable == "1tarball", ] +b <- d[d$variable == "2bridgedb", ] +m <- d[d$variable == "3metricsdb", ] +d <- rbind( + data.frame(x = t$x, y = t$y, colour = t$colour, + variable = "Tarball size in GiB/day"), + data.frame(x = b$x, y = b$y, colour = b$colour, + variable = "BridgeDB time in min"), + data.frame(x = m$x, y = m$y, colour = m$colour, + variable = "metrics-db time in min")) +ggplot(d, aes(x = x, y = y, colour = colour)) + +geom_line(colour = "black") + +geom_point() + +facet_grid(variable ~ ., scales = "free_y") + +scale_x_continuous(name = "\nRunning bridges (2012-01-31 = 838, red)") + +scale_y_continuous(name = "") + +scale_colour_manual(name = "", value = c("black", "red")) + +opts(legend.position = "none", + title = "Scalability of Tor's bridge infrastructure\n") +ggsave("bridge-scaling.png", width = 7, height = 6, dpi = 100) + diff --git a/task-4499/bridge-scaling.csv b/task-4499/bridge-scaling.csv new file mode 100644 index 0000000..24bbbf3 --- /dev/null +++ b/task-4499/bridge-scaling.csv @@ -0,0 +1,24 @@ +x,y,variable,colour +NA,0,1tarball,black +838,0.103,1tarball,red +1676,0.206,1tarball,black +3352,0.412,1tarball,black +6704,0.843,1tarball,black +13408,1.64,1tarball,black +26816,3.281,1tarball,black +53632,6.562,1tarball,black +NA,0,2bridgedb,black +838,0.0833,2bridgedb,red +1676,0.1833,2bridgedb,black +3352,0.3833,2bridgedb,black +6704,0.7666,2bridgedb,black +13408,1.5833,2bridgedb,black +26816,3.3,2bridgedb,black +53632,6.283,2bridgedb,black +NA,0,3metricsdb,black +838,0.583,3metricsdb,red +1676,1.366,3metricsdb,black +3352,3.816,3metricsdb,black +6704,7.9,3metricsdb,black +13408,20.216,3metricsdb,black +26816,44.75,3metricsdb,black diff --git a/task-4499/bridge-scaling.tex b/task-4499/bridge-scaling.tex new file mode 100644 index 0000000..14dae1a --- /dev/null +++ b/task-4499/bridge-scaling.tex @@ -0,0 +1,117 @@ +\documentclass{article} +\usepackage{url} +\usepackage[pdftex]{graphicx} +\usepackage{graphics} +\usepackage{color} +\begin{document} +\title{Investigating scaling points to handle more bridges} +\author{Karsten Loesing\\{\tt karsten@torproject.org}} + +\maketitle + +\section{Introduction} + +The current bridge infrastructure relies on a central bridge authority to +collect, distribute, and publish bridge relay descriptors. +We believe the current infrastructure can handle up to 10,000 bridges. + +The scaling points involve the database of descriptors, the metrics portal +and its ability to handle this many descriptors for analysis, and the +reachability testing part of the code for the bridge authority. +We should investigate scaling points to handle more than 10,000 bridge +descriptors. + +\section{Early results} + +We started this analysis by writing a small tool to generate sample data +for BridgeDB and metrics-db. +This tool takes the contents from one of Tonga's bridge tarball as input, +copies them a given number of times, and overwrites the first two bytes of +relay fingerprints in every copy with 0000, 0001, etc. +The tool also fixes references between network statuses, server +descriptors, and extra-info descriptors. +This is sufficient to trick BridgeDB and metrics-db into thinking that +relays in the copies are distinct relays. +We used the tool to generate tarballs with 2, 4, 8, 16, 32, and 64 times +as many bridge descriptors in them. + +In the next step we fed the tarballs into BridgeDB and metrics-db. +BridgeDB reads the network statuses and server descriptors from the latest +tarball and writes them to a local database. +metrics-db sanitizes two half-hourly created tarballs every hour, +establishes an internal mapping between descriptors, and writes sanitized +descriptors with fixed references to disk. + +Figure~\ref{fig:bridgescaling} shows the results. + +\begin{figure}[t] +\includegraphics[width=\textwidth]{bridge-scaling.png} +%\caption{} +\label{fig:bridgescaling} +\end{figure} + +The upper graph shows how the tarballs grow in size with more bridge +descriptors in them. +This growth is, unsurprisingly, linear. +One thing to keep in mind here is that bandwidth and storage requirements +to the hosts transferring and storing bridge tarballs are growing with the +tarballs. +We'll want to pay extra attention to disk space running out on those +hosts. + +The middle graph shows how long BridgeDB takes to load descriptors from a +tarball. +This graph is linear, too, which indicates that BridgeDB can handle an +increase in the number of bridges pretty well. +One thing we couldn't check is whether BridgeDB's ability to serve client +requests is in any way affected during the descriptor import. +We assume it'll be fine. +We should ask Aaron, if there are other things in BridgeDB that we +overlooked that may not scale. + +The lower graph shows how metrics-db can or cannot handle more bridges. +The growth is slightly worse than linear. +In any case, the absolute time required to handle 25K bridges is worrisome +(we didn't try 50K). +metrics-db runs in an hourly cronjob, and if that cronjob doesn't finish +within 1 hour, we cannot start the next run and will be missing some data. +We might have to sanitize bridge descriptors in a different thread or +process than the one that fetches all the other metrics data. +We can also look into other Java libraries to handle .gz-compressed files +that are faster than the one we're using. +So, we can probably handle 25K bridges somehow, and maybe even 50K. +Somehow. + +Finally, note that we left out the most important part of this analysis: +can Tonga, or more generally, a single bridge authority handle this +increase in bridges? +We're not sure how to test such a setting, or at least without running 50K +bridges in a private network. +We could imagine this requires some more sophisticated sample data +generation including getting the crypto right and then talking to Tonga's +DirPort. +If there's an easy way to test this, we'll do it. +If not, we can always hope for the best. +What can go wrong. + +\section{Work left to do} + +If we end up with way too many bridges, here are a few things we'll want +to look at updating: + +\begin{itemize} +\item Tonga still does a reachability test on each bridge every 21 minutes +or so. +Eventually the number of TLS handshakes it's doing will overwhelm its cpu. +\item The tarballs we make every half hour have substantial overlap. +If we have tens of thousands of descriptors, we would want to get smarter +at sending diffs over to bridgedb. +\item Somebody should check whether BridgeDB's interaction with users +freezes while it's reading a new set of data. +\end{itemize} + +%\bibliography{bridge-scaling} +%\bibliographystyle{plain} + +\end{document} +