misc/simulators/simulate_load.py

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