A ref change was pushed to the repository containing the project "Grayskull Repository". The branch, master has been updated via e234731a3c9e6ed2297aaf44d3b9331f3cfb2647 (commit) via e27655c32d09f5225b869204065527066e6b8805 (commit) via 4d46057703c5895fa225caca46d58b4531175c3a (commit) via 0cf37928aafbd27ddf15cf85a40ff2ce347865c0 (commit) from 1c87e343de209fe99fd950f961640437a8eaec68 (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 e234731a3c9e6ed2297aaf44d3b9331f3cfb2647 Author: Justin Wozniak <[email protected]> Date: Fri Jul 31 17:31:20 2009 -0500 Corrections and cleanups. commit e27655c32d09f5225b869204065527066e6b8805 Author: Justin Wozniak <[email protected]> Date: Fri Jul 31 16:35:57 2009 -0500 Improved output for replica replacement. Normal distance metric. Trying to improve readability of replica movement output. Added Nearest, a PlacementScheme based on the subtraction distance metric (Chord, Pastry, etc.). commit 4d46057703c5895fa225caca46d58b4531175c3a Author: Justin Wozniak <[email protected]> Date: Fri Jul 31 15:14:28 2009 -0500 Places primaries and secondaries before and after a fault. commit 0cf37928aafbd27ddf15cf85a40ff2ce347865c0 Author: Justin Wozniak <[email protected]> Date: Fri Jul 31 15:10:00 2009 -0500 Now places secondary replicas explicitly. ----------------------------------------------------------------------- Summary of changes: sim/gobs/GOBS.java | 71 ++++++++++++++---------------- sim/gobs/Kademlia.java | 88 +++++++++++++++++++++++++++++++------ sim/gobs/MapSorter.java | 22 +++++++++ sim/gobs/Nearest.java | 97 +++++++++++++++++++++++++++++++++++++++++ sim/gobs/Node.java | 50 +++++++++++++++++++++- sim/gobs/Obj.java | 18 +++++++- sim/gobs/PlacementScheme.java | 80 ++++++++++++++++++++++++++++++++- sim/gobs/Primary.java | 20 ++++++++ sim/gobs/RandomLayout.java | 48 -------------------- sim/gobs/Secondary.java | 24 ++++++++++ 10 files changed, 411 insertions(+), 107 deletions(-) create mode 100644 sim/gobs/Nearest.java create mode 100644 sim/gobs/Primary.java delete mode 100644 sim/gobs/RandomLayout.java create mode 100644 sim/gobs/Secondary.java Diff of changes: diff --git a/sim/gobs/GOBS.java b/sim/gobs/GOBS.java index d54b8cb..e99108c 100644 --- a/sim/gobs/GOBS.java +++ b/sim/gobs/GOBS.java @@ -11,7 +11,7 @@ import java.util.*; * nodes: Number of nodes <br> * fileCount: Number of files <br> * fileSize: Size of each file <br> - * objSize: Size of each object + * chunk: Size of a contiguous chunk * */ class GOBS @@ -45,32 +45,24 @@ class GOBS System.out.println(node); } - /* Debugging sortMap(): - - public static void main(String[] args) + static void printFiles(Map<Integer,List<Obj>> files) { - int B = 4; - - Map<Node,Integer> table = new Hashtable<Node,Integer>(); - - table.put(new Node(B, new BigInteger("3")), 2); - table.put(new Node(B, new BigInteger("5")), 1); - table.put(new Node(B, new BigInteger("8")), 4); - table.put(new Node(B, new BigInteger("3")), 3); - - Map<Node,Integer> sorted = (Map<Node,Integer>) sortMap(table); - for (Node node : sorted.keySet()) + for (Integer i : files.keySet()) { - System.out.println(node.toString() + " " + sorted.get(node)); + System.out.println("file: " + i); + List<Obj> set = files.get(i); + for (Obj object : set) + System.out.print(object + " "); + System.out.println(""); } } - */ - + public static void main(String[] args) { String layoutName; - int N, fileCount, fileSize, objSize; - + int N, fileCount, fileSize, chunk; + int uniqueFile = 1; + Bits.init(); if (args.length < 5) @@ -87,23 +79,16 @@ class GOBS N = Integer.parseInt(args[arg++]); fileCount = Integer.parseInt(args[arg++]); fileSize = Integer.parseInt(args[arg++]); - objSize = Integer.parseInt(args[arg++]); + chunk = Integer.parseInt(args[arg++]); - PlacementScheme placer = new Kademlia(); - LayoutScheme layout = null; + //PlacementScheme placer = new Kademlia(B); + PlacementScheme placer = new Nearest(B); NodeScheme hub = new RandomNodes(B); - - layout = new RandomLayout(B); - - if (layout == null) - { - System.out.println("unknown layout!"); - System.exit(1); - } List<Node> nodes = new ArrayList<Node>(N); - Set<Integer> files = new HashSet<Integer>(fileCount); List<Obj> objects = new ArrayList<Obj>(); + Map<Integer,List<Obj>> + files = new HashMap<Integer,List<Obj>>(fileCount); // Initialize node addresses... hub.generate(N, nodes); @@ -111,18 +96,25 @@ class GOBS // Initialize object addresses... for (int i = 0; i < fileCount; i++) { - int fid = Bits.nextInt(fileCount*10); - if (files.add(fid)) - objects.addAll(layout.generate(fileSize,objSize)); + int fid = uniqueFile++; + if (! files.containsKey(fid)) + { + List<Obj> set = placer.allocateFile(fileSize, chunk, 4, + 3, nodes); + files.put(fid, set); + objects.addAll(set); + } } + + printFiles(files); // Place objects and add up load... placer.place(objects, nodes); Map<Node,Integer> origCount = countObjects(nodes); // printNodes(nodes); - // printNodeObjects(nodes); - + printNodeObjects(nodes); + // Cause a fault and reallocate objects... int index = Bits.nextInt(nodes.size()); Node failed = nodes.remove(index); @@ -130,9 +122,12 @@ class GOBS " (" + failed.objects.size() + ")"); List<Obj> replacements = failed.objects; - placer.place(replacements, nodes); + for (Obj object : replacements) + placer.rebuild(object, nodes); Map<Node,Integer> faultCount = countObjects(nodes); + printNodeObjects(nodes); + // Find the load difference from before the fault... Map<Node,Integer> diffs = new Hashtable<Node,Integer>(); for (Node node : faultCount.keySet()) diff --git a/sim/gobs/Kademlia.java b/sim/gobs/Kademlia.java index 886da8d..30c0f2b 100644 --- a/sim/gobs/Kademlia.java +++ b/sim/gobs/Kademlia.java @@ -1,39 +1,97 @@ import java.math.BigInteger; -import java.util.List; +import java.util.*; /** * Places objects on the nearest node using the XOR distance metric. * */ class Kademlia - implements PlacementScheme + extends PlacementScheme { + Kademlia(int B) + { + super(B); + } + public void place(List<Obj> objects, List<Node> nodes) { + System.out.println("placing: " + objects.size()); for (Obj object : objects) placeObject(object, nodes); } - + + /** + Allocate replicas for object and place all on nodes. + */ void placeObject(Obj object, List<Node> nodes) { - Node closest = null; - BigInteger diff = null; - for (Node node : nodes) + List<Node> closest = closestNodes(object, nodes); + Primary primary = object.toPrimary(); + closest.remove(0).add(primary); + for (Node node : closest) + { + node.add(object.toSecondary(primary)); + } + } + + /** + Place this object to rebuild. + */ + void rebuild(Obj object, List<Node> nodes) + { + List<Node> closest = closestNodes(object, nodes); + Secondary secondary; + Node source = null, destination = null; + if (object instanceof Primary) { - BigInteger d = node.id.xor(object.id); - if (diff == null || - diff.compareTo(d) > 0) + Primary primary = object.toPrimary(); + source = closest.remove(0); + secondary = (Secondary) source.remove(primary.id); + source.add(primary); + } + else + { + source = closest.remove(0); + Primary primary = (Primary) source.get(object.id); + secondary = primary.toSecondary(primary); + } + + for (Node node : closest) + { + if (! node.contains(secondary.id)) { - closest = node; - diff = d; + destination = node; + destination.add(secondary); + break; } } - closest.objects.add(object); + System.out.println("rebuild: " + object.toString() + ": " + + source.bitString() + " -> " + + destination.bitString()); } - - long xor(long i, long j) + + List<Node> closestNodes(Obj object, List<Node> nodes) { - return i ^ j; + List<Node> closest = new ArrayList<Node>(object.replicas*2); + + for (int i = 0; i < object.replicas; i++) + { + BigInteger closestDiff = null; + Node closestNode = null; + for (Node node : nodes) + { + BigInteger d = node.id.xor(object.id); + if ((closestDiff == null || + closestDiff.compareTo(d) > 0) && + ! closest.contains(node)) + { + closestNode = node; + closestDiff = d; + } + } + closest.add(closestNode); + } + return closest; } } diff --git a/sim/gobs/MapSorter.java b/sim/gobs/MapSorter.java index 7f7931a..b92e4cf 100644 --- a/sim/gobs/MapSorter.java +++ b/sim/gobs/MapSorter.java @@ -27,3 +27,25 @@ class MapSorter<T> return result; } } + + /* Debugging sortMap(): + + public static void main(String[] args) + { + int B = 4; + + Map<Node,Integer> table = new Hashtable<Node,Integer>(); + + table.put(new Node(B, new BigInteger("3")), 2); + table.put(new Node(B, new BigInteger("5")), 1); + table.put(new Node(B, new BigInteger("8")), 4); + table.put(new Node(B, new BigInteger("3")), 3); + + Map<Node,Integer> sorted = (Map<Node,Integer>) sortMap(table); + for (Node node : sorted.keySet()) + { + System.out.println(node.toString() + " " + sorted.get(node)); + } + } + */ + diff --git a/sim/gobs/Nearest.java b/sim/gobs/Nearest.java new file mode 100644 index 0000000..a4f78a1 --- /dev/null +++ b/sim/gobs/Nearest.java @@ -0,0 +1,97 @@ + +import java.math.BigInteger; +import java.util.*; + +/** + * Places objects on the nearest node using the XOR distance metric. + * */ + +class Nearest + extends PlacementScheme +{ + Nearest(int B) + { + super(B); + } + + public void place(List<Obj> objects, List<Node> nodes) + { + System.out.println("placing: " + objects.size()); + for (Obj object : objects) + placeObject(object, nodes); + } + + /** + Allocate replicas for object and place all on nodes. + */ + void placeObject(Obj object, List<Node> nodes) + { + List<Node> closest = closestNodes(object, nodes); + Primary primary = object.toPrimary(); + closest.remove(0).add(primary); + for (Node node : closest) + { + node.add(object.toSecondary(primary)); + } + } + + /** + Place this object to rebuild. + */ + void rebuild(Obj object, List<Node> nodes) + { + List<Node> closest = closestNodes(object, nodes); + Secondary secondary; + Node source = null, destination = null; + if (object instanceof Primary) + { + Primary primary = object.toPrimary(); + source = closest.remove(0); + secondary = (Secondary) source.remove(primary.id); + source.add(primary); + } + else + { + source = closest.remove(0); + Primary primary = (Primary) source.get(object.id); + secondary = primary.toSecondary(primary); + } + + for (Node node : closest) + { + if (! node.contains(secondary.id)) + { + destination = node; + destination.add(secondary); + break; + } + } + System.out.println("rebuild: " + object.toString() + ": " + + source.bitString() + " -> " + + destination.bitString()); + } + + List<Node> closestNodes(Obj object, List<Node> nodes) + { + List<Node> closest = new ArrayList<Node>(object.replicas*2); + + for (int i = 0; i < object.replicas; i++) + { + BigInteger closestDiff = null; + Node closestNode = null; + for (Node node : nodes) + { + BigInteger d = node.id.subtract(object.id).abs(); + if ((closestDiff == null || + closestDiff.compareTo(d) > 0) && + ! closest.contains(node)) + { + closestNode = node; + closestDiff = d; + } + } + closest.add(closestNode); + } + return closest; + } +} diff --git a/sim/gobs/Node.java b/sim/gobs/Node.java index 71d1859..680d9db 100644 --- a/sim/gobs/Node.java +++ b/sim/gobs/Node.java @@ -22,6 +22,52 @@ class Node objects.add(object); } + /** + @return An Obj with this id. + */ + Obj get(BigInteger id) + { + for (Iterator<Obj> it = objects.iterator(); it.hasNext(); ) + { + Obj object = it.next(); + if (object.id.equals(id)) + { + return object; + } + } + return null; + } + + /** + Remove and return an Obj with this id. + */ + Obj remove(BigInteger id) + { + for (Iterator<Obj> it = objects.iterator(); it.hasNext(); ) + { + Obj object = it.next(); + if (object.id.equals(id)) + { + it.remove(); + return object; + } + } + return null; + } + + /** + @return true iff this node has an object with the given id. + */ + boolean contains(BigInteger id) + { + for (Obj object : objects) + { + if (object.id.equals(id)) + return true; + } + return false; + } + String loadReport() { return bitString() + " " + objects.size(); @@ -33,7 +79,9 @@ class Node result.append(bitString()); result.append(":\t"); for (Obj object : objects) - result.append(" " + bitString(B, object.id)); + { + result.append(object.toString()).append(" "); + } result.append("\n"); return result.toString(); } diff --git a/sim/gobs/Obj.java b/sim/gobs/Obj.java index c3ce9a2..2fb7025 100644 --- a/sim/gobs/Obj.java +++ b/sim/gobs/Obj.java @@ -9,14 +9,28 @@ import java.math.BigInteger; class Obj extends Addressable { - int size; + /** Simulated size in bytes. */ + int size; + /** Number of replicas, including primary. */ + int replicas; - Obj(int B, BigInteger id, int size) + Obj(int B, BigInteger id, int size, int replicas) { super(B, id); this.size = size; + this.replicas = replicas; } + Primary toPrimary() + { + return new Primary(B, id, size, replicas); + } + + Secondary toSecondary(Primary primary) + { + return new Secondary(B, id, size, replicas, primary); + } + public String toString() { return bitString() + "(" + size + ")"; diff --git a/sim/gobs/PlacementScheme.java b/sim/gobs/PlacementScheme.java index 2b58b60..989aee9 100644 --- a/sim/gobs/PlacementScheme.java +++ b/sim/gobs/PlacementScheme.java @@ -1,11 +1,85 @@ -import java.util.List; +import java.math.BigInteger; +import java.util.*; /** * Interface to place a list of objects on a set of nodes. * */ -interface PlacementScheme +abstract class PlacementScheme { - void place(List<Obj> objects, List<Node> nodes); + int B; + BigInteger M; + + PlacementScheme(int B) + { + this.B = B; + + BigInteger two = new BigInteger("2"); + M = two.pow(B); + } + + /** + Generate an object set for a file. + */ + public List<Obj> allocateFile(int size, int chunk, int width, + int replicas, List<Node> nodes) + { + List<Obj> result = new ArrayList<Obj>(width*2); + + BigInteger p = randomID(); + + BigInteger two = new BigInteger("2"); + BigInteger bigWidth = new BigInteger("" + width); + BigInteger bigWidth2 = new BigInteger("2"); + while (bigWidth2.compareTo(bigWidth) < 0) + { + bigWidth2 = bigWidth2.multiply(two); + } + + BigInteger s = M.divide(bigWidth2); + + int chunks = size/chunk; + int extras = chunks % width; + + int i; + for (i = 0; i < extras; i++) + { + BigInteger id = p; + int bytes = (1 + chunks/width)*chunk; + Obj obj = new Obj(B, id, bytes, replicas); + result.add(obj); + p = p.add(s); + } + for ( ; i < width; i++) + { + BigInteger id = p; + int bytes = (chunks/width)*chunk; + Obj obj = new Obj(B, id, bytes, replicas); + result.add(obj); + p = p.add(s); + } + + /* + for (Obj o : result) + System.out.println(o); + */ + + return result; + } + + /** + Place a set of objects. + */ + abstract void place(List<Obj> objects, List<Node> nodes); + + /** + Find a new node to hold this object replica and place it. + */ + abstract void rebuild(Obj object, List<Node> nodes); + + BigInteger randomID() + { + return new BigInteger(B, Bits.rng); + } } diff --git a/sim/gobs/Primary.java b/sim/gobs/Primary.java new file mode 100644 index 0000000..ecc90a7 --- /dev/null +++ b/sim/gobs/Primary.java @@ -0,0 +1,20 @@ + +import java.math.BigInteger; + +/** + * Simulates a single primary object. + * */ + +class Primary + extends Obj +{ + Primary(int B, BigInteger id, int size, int replicas) + { + super(B, id, size, replicas); + } + + public String toString() + { + return bitString() + "[P](" + size + ")"; + } +} diff --git a/sim/gobs/RandomLayout.java b/sim/gobs/RandomLayout.java deleted file mode 100644 index 675325e..0000000 --- a/sim/gobs/RandomLayout.java +++ /dev/null @@ -1,48 +0,0 @@ - -import java.math.BigInteger; -import java.util.*; - -/** - * Generates random object ids. - * */ - -class RandomLayout - extends LayoutScheme -{ - RandomLayout(int B) - { - super(B); - } - - BigInteger randomID() - { - return new BigInteger(B, Bits.rng); - } - - public List<Obj> generate(int fileSize, int objSize) - { - List<Obj> result; - - int n = fileSize/objSize + 1; - result = new ArrayList<Obj>(fileSize/objSize+1); - - for (int i = 0; i < n-1; i++) - result.add(new Obj(B, randomID(), objSize)); - result.add(new Obj(B, randomID(), fileSize % objSize)); - - return result; - } - - /** - Debugging only. - */ - public static void main(String[] args) - { - Bits.init(); - int B = 128; - RandomLayout rl = new RandomLayout(B); - BigInteger i = rl.randomID(); - System.out.println(i); - System.out.println(Addressable.bitString(B, i)); - } -} diff --git a/sim/gobs/Secondary.java b/sim/gobs/Secondary.java new file mode 100644 index 0000000..8f691fc --- /dev/null +++ b/sim/gobs/Secondary.java @@ -0,0 +1,24 @@ + +import java.math.BigInteger; + +/** + * Simulates a single secondary object. + * */ + +class Secondary + extends Obj +{ + Primary primary; + + Secondary(int B, BigInteger id, int size, int replicas, + Primary primary) + { + super(B, id, size, replicas); + this.primary = primary; + } + + public String toString() + { + return bitString() + "[S](" + size + ")"; + } +} hooks/post-receive -- Grayskull Repository