source: trunk/misc/simulators/simulate_load.py

Last change on this file was 4ac60c5, checked in by Alexandre Detiste <alexandre.detiste@…>, at 2024-12-21T13:57:09Z

vendor cmp()

  • Property mode set to 100644
File size: 4.9 KB
Line 
1#!/usr/bin/env python
2
3# WARNING. There is a bug in this script so that it does not simulate the actual Tahoe Two server selection algorithm that it was intended to simulate. See http://allmydata.org/trac/tahoe-lafs/ticket/302 (stop permuting peerlist, use SI as offset into ring instead?)
4
5import random
6
7SERVER_CAPACITY = 10**12
8
9def cmp(a, b):
10    return (a > b) - (a < b)
11
12class Server(object):
13    def __init__(self):
14        self.si = random.randrange(0, 2**31)
15        self.used = 0
16        self.max = SERVER_CAPACITY
17        self.full_at_tick = None
18
19    def __repr__(self):
20        if self.full_at_tick is not None:
21            return "<%s %s full at %d>" % (self.__class__.__name__, self.si, self.full_at_tick)
22        else:
23            return "<%s %s>" % (self.__class__.__name__, self.si)
24
25SERVERS = 4
26K = 3
27N = 10
28
29def make_up_a_file_size():
30    return (2 ** random.randrange(8, 31))
31
32def go(permutedpeerlist):
33    servers = [ Server() for x in range(SERVERS) ]
34    servers.sort(cmp=lambda x,y: cmp(x.si, y.si))
35
36    doubled_up_shares = 0
37    tick = 0
38    fullservers = 0
39    while True:
40        nextsharesize = make_up_a_file_size() / K
41        if permutedpeerlist:
42            random.shuffle(servers)
43        else:
44            # rotate a random number
45            rot = random.randrange(0, len(servers))
46            servers = servers[rot:] + servers[:rot]
47
48        i = 0
49        wrapped = False
50        sharestoput = N
51        while sharestoput:
52            server = servers[i]
53            if server.used + nextsharesize < server.max:
54                server.used += nextsharesize
55                sharestoput -= 1
56                if wrapped:
57                    doubled_up_shares += 1
58            else:
59                if server.full_at_tick is None:
60                    server.full_at_tick = tick
61                    fullservers += 1
62                    if fullservers == len(servers):
63                        # print("Couldn't place share -- all servers full.  Stopping.")
64                        return (servers, doubled_up_shares)
65
66            i += 1
67            if i == len(servers):
68                wrapped = True
69                i = 0
70
71        tick += 1
72
73def div_ceil(n, d):
74    """
75    The smallest integer k such that k*d >= n.
76    """
77    return (n/d) + (n%d != 0)
78
79DESIRED_COLUMNS = 70
80
81START_FILES = 137000
82STOP_FILES = 144000
83
84def test(permutedpeerlist, iters):
85    # The i'th element of the filledat list is how many servers got full when the i'th file was uploaded.
86    filledat = []
87    for test in range(iters):
88        (servers, doubled_up_shares) = go(permutedpeerlist)
89        print("doubled_up_shares: ", doubled_up_shares)
90        for server in servers:
91            fidx = server.full_at_tick
92            filledat.extend([0]*(fidx-len(filledat)+1))
93            filledat[fidx] += 1
94
95    startfiles = 0
96    while filledat[startfiles] == 0:
97        startfiles += 1
98    filespercolumn = div_ceil(len(filledat) - startfiles, (DESIRED_COLUMNS - 3))
99
100    # to make comparisons between runs line up:
101    # startfiles = START_FILES
102    # filespercolumn = div_ceil(STOP_FILES - startfiles, (DESIRED_COLUMNS - 3))
103
104    # The i'th element of the compressedfilledat list is how many servers got full when the filespercolumn files starting at startfiles + i were uploaded.
105    compressedfilledat = []
106    idx = startfiles
107    while idx < len(filledat):
108        compressedfilledat.append(0)
109        for i in range(filespercolumn):
110            compressedfilledat[-1] += filledat[idx]
111            idx += 1
112            if idx >= len(filledat):
113                break
114
115    # The i'th element of the fullat list is how many servers were full by the tick numbered startfiles + i * filespercolumn (on average).
116    fullat = [0] * len(compressedfilledat)
117    for idx, num in enumerate(compressedfilledat):
118        for fidx in range(idx, len(fullat)):
119            fullat[fidx] += num
120
121    for idx in range(len(fullat)):
122        fullat[idx]  = fullat[idx] / float(iters)
123
124    # Now print it out as an ascii art graph.
125    import sys
126    for serversfull in range(40, 0, -1):
127        sys.stdout.write("%2d " % serversfull)
128        for numfull in fullat:
129            if int(numfull) == serversfull:
130                sys.stdout.write("*")
131            else:
132                sys.stdout.write(" ")
133        sys.stdout.write("\n")
134
135    sys.stdout.write(" ^-- servers full\n")
136    idx = 0
137    while idx < len(fullat):
138        nextmark  = "%d--^ " % (startfiles + idx * filespercolumn)
139        sys.stdout.write(nextmark)
140        idx += len(nextmark)
141
142    sys.stdout.write("\nfiles uploaded --> \n")
143
144
145
146if __name__ == "__main__":
147    import sys
148    iters = 16
149    for arg in sys.argv:
150        if arg.startswith("--iters="):
151            iters = int(arg[8:])
152    if "--permute" in sys.argv:
153        print("doing permuted peerlist, iterations: %d" % iters)
154        test(True, iters)
155    else:
156        print("doing simple ring, iterations: %d" % iters)
157        test(False, iters)
Note: See TracBrowser for help on using the repository browser.