Ticket #28424: ChurnSim.2.java

File ChurnSim.2.java, 3.5 KB (added by akwizgran, 9 months ago)

Updated simulation code

Line 
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.Collections;
4import java.util.Comparator;
5import java.util.List;
6import java.util.Random;
7
8public class ChurnSim {
9
10        // Simulation parameters
11        private static final int NUM_RUNS = 1000;
12        private static final int NUM_HOURS = 100;
13        private static final double REPLACEMENT_PROBABILITY_PER_HOUR = 0.01;
14        private static final int LOOKUPS_PER_HOUR = 100;
15
16        // System parameters
17        private static final int NUM_DIRS = 3000;
18        private static final int NUM_REPLICAS = 2;
19        private static final int SPREAD_STORE = 4;
20        private static final int SPREAD_FETCH = 3;
21
22        private final Random random = new Random();
23        private final List<Dir> dirs = new ArrayList<>(NUM_DIRS);
24        private final List<List<Dir>> hashRings =
25                        new ArrayList<List<Dir>>(NUM_REPLICAS);
26        private final HashRingComparator[] comparators =
27                        new HashRingComparator[NUM_REPLICAS];
28
29        private ChurnSim() {
30                for (int dir = 0; dir < NUM_DIRS; dir++) {
31                        dirs.add(new Dir());
32                }
33                for (int replica = 0; replica < NUM_REPLICAS; replica++) {
34                        hashRings.add(new ArrayList<>(dirs));
35                        comparators[replica] = new HashRingComparator(replica);
36                        Collections.sort(hashRings.get(replica), comparators[replica]);
37                }
38        }
39
40        private void upload() {
41                for (int replica = 0; replica < NUM_REPLICAS; replica++) {
42                        for (int position = 0; position < SPREAD_STORE; position++) {
43                                hashRings.get(replica).get(position).hasDescriptor = true;
44                        }
45                }       
46        }
47
48        private void churn() {
49                for (int dir = 0; dir < NUM_DIRS; dir++) {
50                        if (random.nextDouble() < REPLACEMENT_PROBABILITY_PER_HOUR) {
51                                dirs.get(dir).replace();
52                        }
53                }
54                for (int replica = 0; replica < NUM_REPLICAS; replica++) {
55                        Collections.sort(hashRings.get(replica), comparators[replica]);
56                }
57        }
58
59        private int lookup() {
60                int succeeded = 0;
61                for (int lookup = 0; lookup < LOOKUPS_PER_HOUR; lookup++) {
62                        for (int replica = 0; replica < NUM_REPLICAS; replica++) {
63                                int position = random.nextInt(SPREAD_FETCH);
64                                if (hashRings.get(replica).get(position).hasDescriptor) {
65                                        succeeded++;
66                                        break;
67                                }
68                        }
69                }
70                return succeeded;
71        }
72
73        public static void main(String[] args) {
74                int[][] results = new int[NUM_HOURS][NUM_RUNS];
75                for (int run = 0; run < NUM_RUNS; run++) {
76                        ChurnSim sim = new ChurnSim();
77                        sim.upload();
78                        for (int hour = 0; hour < NUM_HOURS; hour++) {
79                                results[hour][run] = sim.lookup();
80                                sim.churn();
81                        }
82                }
83                for (int hour = 0; hour < NUM_HOURS; hour++) {
84                        Arrays.sort(results[hour]);
85                        int p1 = results[hour][NUM_RUNS / 100];
86                        int p99 = results[hour][NUM_RUNS / 100 * 99];
87                        double total = 0;
88                        for (int run = 0; run < NUM_RUNS; run++) {
89                                total += results[hour][run];
90                        }
91                        double mean = total / NUM_RUNS;
92                        System.out.println(hour + " " + mean + " " + p1 + " " + p99);
93                }
94        }
95
96        private class Dir {
97
98                private final double[] positions;
99
100                private boolean hasDescriptor = false;
101
102                private Dir() {
103                        positions = new double[NUM_REPLICAS];
104                        for (int replica = 0; replica < NUM_REPLICAS; replica++) {
105                                positions[replica] = random.nextDouble();
106                        }
107                }
108
109                private void replace() {
110                        hasDescriptor = false;
111                        for (int replica = 0; replica < NUM_REPLICAS; replica++) {
112                                positions[replica] = random.nextDouble();
113                        }
114                }
115        }
116
117        private static class HashRingComparator implements Comparator<Dir> {
118
119                private final int replica;
120
121                private HashRingComparator(int replica) {
122                        this.replica = replica;
123                }
124
125                @Override
126                public int compare(Dir d1, Dir d2) {
127                        return Double.compare(d1.positions[replica], d2.positions[replica]);
128                }
129        }
130}