[tahoe-dev] stop permuting the peerlist per storage index? (was: repairer work)

[zooko]

On Jul 12, 2008, at 14:11 PM, zooko wrote:

 > I'll bet that a simple simulation could clarify for me and for
 > others what effects the permuted peerlist has on load distribution.
 > Perhaps I'll cook one up in Python and post it to this list to
 > server as an aid to reasoning.

http://allmydata.org/trac/tahoe/browser/misc/simulate_load.py

Well, I don't know if this is simulating the right things, but here is
a script that simulates 40 empty servers, each of which can hold up to
1 TiB, and then adds shares to the servers until the server is out of
space, and keeps track of how many files got uploaded before each
server got filled up, and then prints out ASCII art graphs of how many
servers were full (y axis) when a certain number of files had been
uploaded (x axis).

Note that the origin point on the graph, the lower-left-hand corner,
is where 137,000 files have already been uploaded to the grid, and no
server are yet full.  The upper-right hand point is where about
143,000 files have been uploaded and all the servers are full.  So to
get a linear, rooted-at-zero perspective, just imagine a graph like
this where the left-hand 96% of it is a flat line showing 0 servers
full, and then the right-hand 4% is one of the following graphs.  The
linear, rooted-at-zero perspective is important to keep in mind,
because it shows that any differences between the graphs you see below
apply only to the last 4% of the files that get uploaded.


Here is the result of "simulate_load.py --iters=128 --permute":

doing permuted peerlist, iterations: 128
40
39                                                            ********
38                                                       *****
37                                                    ***
36                                                  **
35                                                 *
34                                               **
33                                             **
32                                            *
31
30                                           *
29                                         **
28
27                                        *
26                                       *
25                                      *
24                                     *
23                                    *
22
21                                   *
20                                  *
19                                 *
18                                *
17                               *
16                              *
15
14                             *
13                            *
12                           *
11                          *
10                         *
  9                        *
  8                       *
  7                     **
  6                    *
  5                  **
  4                **
  3              **
  2           ***
  1       ****
  ^-- servers full
137000--^ 138050--^ 139100--^ 140150--^ 141200--^ 142250--^ 143300--^
files uploaded -->
And here is the result of "simulate_load.py --iters=128":

doing simple ring, iterations: 128
40
39                                                        *****
38                                                   *****
37                                                ***
36                                              **
35                                             *
34                                            *
33                                          **
32                                         *
31
30                                        *
29                                       *
28                                      *
27                                     *
26                                    *
25                                   *
24
23                                  *
22                                 *
21                                *
20
19                               *
18                              *
17                             *
16
15                            *
14                           *
13                          *
12                         *
11                        *
10                       *
  9                      *
  8                     *
  7                   **
  6                  *
  5                **
  4              **
  3            **
  2          **
  1      ****
  ^-- servers full
137000--^ 138050--^ 139100--^ 140150--^ 141200--^ 142250--^
files uploaded -->

I'm not sure that I can see any difference between those two.
Actually the permuted peerlist one shows that it was able to store
more files than the simple ring one, but that can't possibly make any
sense so it must be an artifact of my simulator.

Is this the kind of data that can help me understand the use of this
technique?

A more realistic simulation would have us add in a bunch of new
servers once the existing servers got to be mostly full.  Perhaps that
would show a bigger difference between the two techniques.  Is there
any other metric that I should output from this simulation?


Whoops!  Stop the presses!  I misled myself by running many iterations
(128 of them), averaging the results together, and plotting just the
average.  If you run "simulate_load.py --iters=1" and look at the
output of a single actual run you'll see that the results from any
given run are all over the map, and that the variability of the system
totally swamps any subtle difference in the average behavior between
permuted and simple variants.  (There are a couple of examples of
--iters=1 runs appended.)

Hm.  I still don't know if I'm actually measuring the right thing, but
so far this reinforces my prejudice that the advantage of the permuted
peerlist approach is hard to spot.


Regards,

Zooko

doing permuted peerlist, iterations: 1
40
39
38
37                                 *
36
35
34                                *
33
32
31
30                               *
29
28                              *
27
26
25                             *
24
23
22
21
20                            *
19
18
17                           *
16
15
14                          *
13                         *
12                        *
11                       *
10                      *
  9                  ****
  8
  7                 *
  6                *
  5               *
  4             **
  3
  2          ***
  1
  ^-- servers full
137000--^ 138050--^ 139100--^ 140150--^
files uploaded -->

doing simple ring, iterations: 1
40                                                 *
39
38
37                                                *
36
35
34                                               *
33
32
31
30                                              *
29                                           ***
28                                          *
27
26                                         *
25
24                                        *
23
22                                       *
21
20
19
18                                      *
17                                     *
16
15
14
13
12                                    *
11
10
  9
  8                                   *
  7                                  *
  6                                 *
  5                               **
  4                              *
  3                            **
  2
  1                    ********
  ^-- servers full
137000--^ 138050--^ 139100--^ 140150--^ 141200--^
files uploaded -->