A ref change was pushed to the repository containing the project "Grayskull Repository". The branch, master has been updated via 8301a12376500b6ae95e6d62b41f8741d197024b (commit) via 5a65b716ec7b0d33d097e424887fa72e80c65654 (commit) via 130512557b288c7c2c2fcdc5f8976c69ca9741f1 (commit) via 1816431b20550afe8fa723f985801bcbed2875ca (commit) via bbc8a410d34bc0f6a84f23f2c1808f141a1fcb68 (commit) from b968196f03039954f969f3699666391b36bfd909 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit 8301a12376500b6ae95e6d62b41f8741d197024b Author: Justin Wozniak <[email protected]> Date: Mon Nov 30 15:22:10 2009 -0600 New 3-phase rebuild. Now: after the fault is inflicted, build a list of copies to be performed, run them in the event-driven model, then actually copy objects that successfully copied. Allows us to interrupt the event-driven model with a successive fault. commit 5a65b716ec7b0d33d097e424887fa72e80c65654 Author: Justin Wozniak <[email protected]> Date: Mon Nov 30 12:22:27 2009 -0600 New avg(). commit 130512557b288c7c2c2fcdc5f8976c69ca9741f1 Author: Justin Wozniak <[email protected]> Date: Mon Nov 30 12:17:34 2009 -0600 Add $classpath for main build to enable colt. commit 1816431b20550afe8fa723f985801bcbed2875ca Author: Justin Wozniak <[email protected]> Date: Mon Nov 30 12:17:05 2009 -0600 Display mean for exponential test. commit bbc8a410d34bc0f6a84f23f2c1808f141a1fcb68 Author: Justin Wozniak <[email protected]> Date: Mon Nov 30 12:00:47 2009 -0600 Link Exponential into Simulator and improve docs. ----------------------------------------------------------------------- Summary of changes: sim/gobs/build.xml | 3 +- sim/gobs/gobs/sim/Copy.java | 51 +++++++++++++ sim/gobs/gobs/sim/Event.java | 21 +++++ sim/gobs/gobs/sim/Metric.java | 24 ++++-- sim/gobs/gobs/sim/ParallelRUSH.java | 5 +- sim/gobs/gobs/sim/Placement.java | 59 +++++++-------- sim/gobs/gobs/sim/RUSHp.java | 5 +- sim/gobs/gobs/sim/Rebuild.java | 123 ++++++------------------------ sim/gobs/gobs/sim/Replicated.java | 13 +--- sim/gobs/gobs/sim/Simulator.java | 59 ++++++++++++--- sim/gobs/gobs/test/TestExponential.java | 6 +- sim/gobs/gobs/util/Stats.java | 8 ++ 12 files changed, 208 insertions(+), 169 deletions(-) create mode 100644 sim/gobs/gobs/sim/Copy.java create mode 100644 sim/gobs/gobs/sim/Event.java Diff of changes: diff --git a/sim/gobs/build.xml b/sim/gobs/build.xml index 5aa1299..f5c57cf 100644 --- a/sim/gobs/build.xml +++ b/sim/gobs/build.xml @@ -35,7 +35,7 @@ <target name="compile_sim" depends="compile_plot,compile_util"> <javac srcdir="gobs/sim" - classpath="." + classpath="${classpath}" listfiles="${lf}" debug="true" debuglevel="source,lines,vars"> @@ -98,6 +98,7 @@ includes="**/*.java"/> <link href="http://java.sun.com/javase/6/docs/api" /> <link href="http://www.jfree.org/jfreechart/api/javadoc" /> + <link href="http://acs.lbl.gov/~hoschek/colt/api" /> </javadoc> </target> diff --git a/sim/gobs/gobs/sim/Copy.java b/sim/gobs/gobs/sim/Copy.java new file mode 100644 index 0000000..6db2e98 --- /dev/null +++ b/sim/gobs/gobs/sim/Copy.java @@ -0,0 +1,51 @@ + +package gobs.sim; + +import java.text.DecimalFormat; +import java.util.*; + +import gobs.util.Bits; + +class Copy + extends Event +{ + gobs.sim.Object object; + Node source; + Node destination; + boolean complete = false; + double start = 0; + + static DecimalFormat df = new DecimalFormat("0.000000000"); + + Copy(gobs.sim.Object object, Node source, Node destination) + { + this.object = object; + this.source = source; + this.destination = destination; + } + + void startAt(double start) + { + this.start = start; + finish = start + object.size/Rebuild.rate; + } + + public String toString() + { + return log(); + } + + String log() + { + StringBuilder sb = new StringBuilder(128); + sb.append("copy: ") + .append(object).append(": ") + .append(source).append(" -> ").append(destination) + .append("(").append(df.format(start)); + if (finish == -1) + sb.append(")"); + else + sb.append(",").append(df.format(finish)).append(")"); + return sb.toString(); + } +} diff --git a/sim/gobs/gobs/sim/Event.java b/sim/gobs/gobs/sim/Event.java new file mode 100644 index 0000000..b1c5d3e --- /dev/null +++ b/sim/gobs/gobs/sim/Event.java @@ -0,0 +1,21 @@ + +package gobs.sim; + +class Event + implements Comparable<Event> +{ + double finish = -1; + + Event() + {} + + Event(double finish) + { + this.finish = finish; + } + + public int compareTo(Event event) + { + return new Double(finish).compareTo(new Double(event.finish)); + } +} diff --git a/sim/gobs/gobs/sim/Metric.java b/sim/gobs/gobs/sim/Metric.java index d3ad748..a541a98 100644 --- a/sim/gobs/gobs/sim/Metric.java +++ b/sim/gobs/gobs/sim/Metric.java @@ -35,8 +35,9 @@ public abstract class Metric return result; } - void rebuild(SingleObject object, List<Node> nodes) + Copy regimen(SingleObject object, List<Node> nodes) { + Copy result; List<Node> sites = sites(object, nodes); // System.out.println("sites.size(): " + sites.size()); Secondary secondary; @@ -44,6 +45,8 @@ public abstract class Metric Node primaryNode = sites.get(sites.size()-1); Node source = removeSource(object, sites); Node destination = null; + SingleObject payload; + if (object instanceof Primary) { Primary primary = (Primary) object; @@ -52,21 +55,22 @@ public abstract class Metric if (primarySite.contains(object.id)) { destination = locateDestination(object, sites); - secondary = (Secondary) primarySite.remove(object.id); - destination.add(secondary); + secondary = (Secondary) primarySite.remove(object.id); + primarySite.add(primary); + payload = secondary; } else { - destination = primarySite; + destination = primarySite; + payload = primary; } - primarySite.add(primary); } else { Primary primary = (Primary) primaryNode.get(object.id); secondary = primary.toSecondary(); - destination = locateDestination(object, sites); - destination.add(secondary); + destination = locateDestination(object, sites); + payload = secondary; } if (source == null) @@ -74,13 +78,15 @@ public abstract class Metric System.out.println("rebuild: lost: " + object.bitString(simulator.B)); simulator.lost(); - return; + return null; } source.pushes++; destination.pulls++; printRebuild(object, source, destination); - simulator.currentRebuild.add(object, source, destination); + // simulator.currentRebuild.add(object, source, destination); + result = new Copy(payload, source, destination); + return result; } } diff --git a/sim/gobs/gobs/sim/ParallelRUSH.java b/sim/gobs/gobs/sim/ParallelRUSH.java index 2fa345c..9fc315a 100644 --- a/sim/gobs/gobs/sim/ParallelRUSH.java +++ b/sim/gobs/gobs/sim/ParallelRUSH.java @@ -153,9 +153,10 @@ public class ParallelRUSH return nodes.get(index); } - void rebuild(SingleObject object, List<Node> nodes) + Copy regimen(SingleObject object, List<Node> nodes) { - place(object, nodes); + // place(object, nodes); + return null; } /** diff --git a/sim/gobs/gobs/sim/Placement.java b/sim/gobs/gobs/sim/Placement.java index 515da79..8612d5f 100644 --- a/sim/gobs/gobs/sim/Placement.java +++ b/sim/gobs/gobs/sim/Placement.java @@ -27,52 +27,45 @@ public abstract class Placement /** Generate an object set for a file. */ - // public Collection<SingleObject> allocateFile(File file, List<Node> nodes) - public abstract Collection<gobs.sim.Object> allocateFile(File file, List<Node> nodes); - /* - { - ArrayList<gobs.sim.Object> result = - new ArrayList<gobs.sim.Object>(file.width+2); - - BigInteger bigWidth = new BigInteger("" + file.width); - BigInteger s = M.divide(bigWidth); - BigInteger p = randomID(); - for (int i = 0; i < file.width; i++) - { - BigInteger id = p; - int bytes = file.objectSize(i); - gobs.sim.Object obj = - (gobs.sim.Object) new SingleObject(id, bytes, file.replicas); - result.add(obj); - p = p.add(s).mod(M); - } - - result.trimToSize(); - return result; - } -*/ - // public abstract Node lookup(BigInteger id, List<Node> nodes); - - void rebuild(gobs.sim.Object object, List<Node> nodes) + /** + Obtain a Copy that will repair the loss of this Object. + @return The Copy or null if the Object is lost. + */ + Copy regimen(gobs.sim.Object object, List<Node> nodes) { + Copy result; if (object instanceof SingleObject) - rebuild((SingleObject) object, nodes); + result = regimen((SingleObject) object, nodes); else if (object instanceof ObjectStrip) - rebuild((ObjectStrip) object, nodes); + result = regimen((ObjectStrip) object, nodes); + else + throw new IllegalArgumentException(); + return result; } /** - Simulate a rebuild. + Obtain a Copy that will repair the loss of this SingleObject. */ - abstract void rebuild(SingleObject object, List<Node> nodes); + abstract Copy regimen(SingleObject object, List<Node> nodes); - void rebuild(ObjectStrip object, List<Node> nodes) + /** + Obtain a Copy that will repair the loss of this ObjectStrip. + */ + Copy regimen(ObjectStrip object, List<Node> nodes) { throw new UnsupportedOperationException - ("rebuild(ObjectStrip) not supported!"); + ("regimen(ObjectStrip) not supported!"); + } + + /** + Actually perform this Copy. + */ + void copy(Copy copy) + { + copy.destination.add(copy.object); } /** diff --git a/sim/gobs/gobs/sim/RUSHp.java b/sim/gobs/gobs/sim/RUSHp.java index 3a0fbcc..e004738 100644 --- a/sim/gobs/gobs/sim/RUSHp.java +++ b/sim/gobs/gobs/sim/RUSHp.java @@ -103,9 +103,10 @@ public class RUSHp return nodes.get(index); } - void rebuild(SingleObject object, List<Node> nodes) + Copy regimen(SingleObject object, List<Node> nodes) { - place(object, nodes); + // place(object, nodes); + return null; } /** diff --git a/sim/gobs/gobs/sim/Rebuild.java b/sim/gobs/gobs/sim/Rebuild.java index a60314e..01c3382 100644 --- a/sim/gobs/gobs/sim/Rebuild.java +++ b/sim/gobs/gobs/sim/Rebuild.java @@ -4,14 +4,13 @@ package gobs.sim; import java.text.DecimalFormat; import java.util.*; -import gobs.util.Bits; +import gobs.util.*; /** Manages a rebuild after a fault. */ class Rebuild { - List<Copy> copies = new ArrayList<Copy>(); NavigableSet<Event> schedule = null; /** @@ -41,39 +40,30 @@ class Rebuild } /** - Add this copy to the Rebuild. + Schedule the next fault. */ - void add(Copy copy) + void nextFault(double t) { - copies.add(copy); - } - - /** - Construct a Copy and add it to this rebuild. - */ - void add(gobs.sim.Object object, Node source, Node destination) - { - Copy copy = new Copy(object, source, destination); - add(copy); + } /** - Actually perform the rebuild. + Actually perform the rebuild. + TODO: Handle cases where more than one copy is needed. @param time The time at which the copies start. @return The time at which all copies finished. */ - double rebuild(double time) + double rebuild(double time, Map<gobs.sim.Object,Copy> copies, + Set<gobs.sim.Object> todo, Set<gobs.sim.Object> done) { start = time; - Collections.shuffle(copies, Bits.rng); schedule = new TreeSet<Event>(); - Queue<Copy> todo = new LinkedList<Copy>(copies); - Set<Node> busy = new HashSet<Node>(copies.size()); + Queue<Copy> queue = order(copies); + Set<Node> busy = new HashSet<Node>(copies.size()); NavigableSet<Copy> inflight = new TreeSet<Copy>(); - int done = 0; - while (done < copies.size()) + while (done.size() < copies.size()) { - Copy copy = select(todo, busy); + Copy copy = select(queue, busy); if (copy != null) { copy.startAt(time); @@ -87,7 +77,6 @@ class Rebuild dumpInflight(inflight); time += selectTime; copy.startAt(time); - // System.exit(2); } if (simulator.bool("print.rebuilds")) System.out.println("start: " + copy.log()); @@ -96,20 +85,15 @@ class Rebuild { // dumpInflight(inflight); Copy finished = inflight.pollFirst(); - if (finished == null) - { - System.out.println("inflight.pollFirst(): null"); - System.out.println("inflight.size(): " + inflight.size()); - try { Thread.sleep(1000); } - catch (Exception e) {} - continue; - } + Tools.check(finished != null, + "inflight.pollFirst(): null"); busy.remove(finished.source); - busy.remove(finished.destination); + busy.remove(finished.destination); + todo.remove(finished.object); + done.add(finished.object); time = finished.finish; if (simulator.bool("print.rebuilds")) System.out.println("finish: " + finished.log()); - done++; } } return time; @@ -138,6 +122,13 @@ class Rebuild System.out.println("\t" + it.next()); } } + + Queue<Copy> order(Map<gobs.sim.Object,Copy> copies) + { + LinkedList<Copy> result = new LinkedList<Copy>(copies.values()); + Collections.shuffle(result, Bits.rng); + return result; + } Copy select(Queue<Copy> todo, Set<Node> busy) throws NoSuchElementException @@ -153,69 +144,5 @@ class Rebuild } } return null; - } - - class Event - implements Comparable<Event> - { - double finish = -1; - - Event() - {} - - Event(double finish) - { - this.finish = finish; - } - - public int compareTo(Event event) - { - return new Double(finish).compareTo(new Double(event.finish)); - } - } - - class Copy - extends Event - { - gobs.sim.Object object; - Node source; - Node destination; - boolean complete = false; - double start = 0; - - Copy(gobs.sim.Object object, Node source, Node destination) - { - - this.object = object; - this.source = source; - this.destination = destination; - } - - void startAt(double start) - { - this.start = start; - finish = start + object.size/rate; - } - - public String toString() - { - return log(); - } - - String log() - { - StringBuilder sb = new StringBuilder(128); - sb.append("copy: ") - .append(object).append(": ") - .append(source).append(" -> ").append(destination) - .append("(").append(df.format(start)); - if (finish == -1) - sb.append(")"); - else - sb.append(",").append(df.format(finish)).append(")"); - return sb.toString(); - } - } - - + } } diff --git a/sim/gobs/gobs/sim/Replicated.java b/sim/gobs/gobs/sim/Replicated.java index f1cdf21..2ac5e65 100644 --- a/sim/gobs/gobs/sim/Replicated.java +++ b/sim/gobs/gobs/sim/Replicated.java @@ -101,18 +101,7 @@ public abstract class Replicated ": does not support place(ObjectStrip)!"); } - /** - Obtain a list of nodes that may host the given object - with respect to the replica placement scheme used here. - - Closest node should be last. - */ - // abstract List<Node> sites(Object object, List<Node> nodes); - - /** - Place this object to rebuild. - */ - abstract void rebuild(SingleObject object, List<Node> nodes); + abstract Copy regimen(SingleObject object, List<Node> nodes); /** Locate a replica of the given object on one of the given nodes diff --git a/sim/gobs/gobs/sim/Simulator.java b/sim/gobs/gobs/sim/Simulator.java index cf8001d..79ef979 100644 --- a/sim/gobs/gobs/sim/Simulator.java +++ b/sim/gobs/gobs/sim/Simulator.java @@ -5,13 +5,16 @@ import java.math.BigInteger; import java.text.DecimalFormat; import java.util.*; +import cern.jet.random.engine.DRand; +import cern.jet.random.Exponential; + import gobs.util.*; import static gobs.util.Tools.bail; /** * <h3> GOBS placement simulator. </h3> * - * Command-line arguments: <br> + * Command-line arguments: {@link #main} * */ public class Simulator @@ -25,6 +28,8 @@ public class Simulator int faults; int reads; int writes; + + double mttf; public Placement placer; public NodeFactory hub; @@ -91,10 +96,16 @@ public class Simulator Cached value of printAccesses property */ boolean printAccesses = false; + + /** + Source of exponentially distributed random numbers + for MTTF samples. + */ + Exponential exponential; public Simulator() { - File.unique = 0; + File.unique = 0; } public Simulator(Properties properties) @@ -102,7 +113,13 @@ public class Simulator this(); initialize(properties); } - + + /** + Run a single Simulator instance. <br> + Command-line arguments: <br> + -p : Change properties file path <br> + key=value : Set property key to value + */ public static void main(String[] args) { if (args.length < 1) @@ -186,7 +203,12 @@ public class Simulator fileCount = integer("files"); faults = integer("faults"); reads = integer("reads"); - writes = integer("writes"); + writes = integer("writes"); + + mttf = decimal("mttf"); + DRand engine = new DRand(Bits.nextInt()); + double lambda = 1.0/mttf; + exponential = new Exponential(lambda, engine); } void setupFileFactory() @@ -400,28 +422,43 @@ public class Simulator void induceFaults() { System.out.println("faults: " + faults); - + Set<gobs.sim.Object> todo = + new LinkedHashSet<gobs.sim.Object>(); + Set<gobs.sim.Object> done = + new LinkedHashSet<gobs.sim.Object>(); for (int fault = 0; fault < faults; fault++) { - startRebuild(); + double nextFault = exponential.nextDouble(); + startRebuild(nextFault); int index = Bits.nextInt(nodes.size()); Node failed = nodes.remove(index); System.out.println("failed: " + failed.name(this) + " (" + failed.objects.size() + ")"); - Collection<gobs.sim.Object> replacements = failed.collection(); - for (gobs.sim.Object object : replacements) - placer.rebuild(object, nodes); + todo.addAll(failed.collection()); + Map<gobs.sim.Object,Copy> copies = + new HashMap<gobs.sim.Object,Copy>(); + for (gobs.sim.Object object : todo) + { + Copy copy = placer.regimen(object, nodes); + copies.put(object, copy); + } + currentRebuild.rebuild(time, copies, todo, done); + for (gobs.sim.Object object : done) + { + Copy copy = copies.get(object); + placer.copy(copy); + } if (string("print.nodes").equals("true")) printNodeObjects(nodes); - currentRebuild.rebuild(time); completeRebuild(); } } - Rebuild startRebuild() + Rebuild startRebuild(double nextFault) { Rebuild rebuild = new Rebuild(this); currentRebuild = rebuild; + rebuild.nextFault(nextFault); return rebuild; } diff --git a/sim/gobs/gobs/test/TestExponential.java b/sim/gobs/gobs/test/TestExponential.java index 312fdda..ab8e7e7 100644 --- a/sim/gobs/gobs/test/TestExponential.java +++ b/sim/gobs/gobs/test/TestExponential.java @@ -8,7 +8,9 @@ import cern.jet.random.Exponential; import org.jfree.data.xy.XYSeries; -import gobs.plot.SimplePlot; +import gobs.plot.SimplePlot; +import gobs.util.Stats; + import static gobs.util.Tools.check; /** @@ -43,6 +45,8 @@ class TestExponential { series.add(i, results.get(i)); } + + System.out.println("avg: " + Stats.avg(results)); SimplePlot.plot(series, "TestExponential", "step", "length", "testexponential.eps"); diff --git a/sim/gobs/gobs/util/Stats.java b/sim/gobs/gobs/util/Stats.java index 7c8792c..0de594f 100644 --- a/sim/gobs/gobs/util/Stats.java +++ b/sim/gobs/gobs/util/Stats.java @@ -19,6 +19,14 @@ public class Stats result = list.size(); return result; } + + public static double avg(List<Double> data) + { + double sum = 0.0; + for (Double d : data) + sum += d; + return sum/data.size(); + } /** Return the average of the corresponding hooks/post-receive -- Grayskull Repository