doc/spec/proposals/ideas/xxx-grand-scaling-plan.txt

   1
   2 Right now as I understand it, there are n big scaling problems heading
   3 our way:
   4
   5 1) Clients need to learn all the relay descriptors they could use. That's
   6 a lot of bytes through a potentially small pipe.
   7 2) Relays need to hold open TCP connections to most other relays.
   8 3) Clients need to learn the whole networkstatus. Even using v3, as
   9 the network grows that will become unwieldy.
  10 4) Dir mirrors need to mirror all the relay descriptors; eventually this
  11 will get big too.
  12
  13 Here's my plan.
  14
  15 --------------------------------------------------------------------
  16
  17 Piece one: download O(1) descriptors rather than O(n) descriptors.
  18
  19 We need to change our circuit extend protocol so it fetches a relay
  20 descriptor at every 'extend' operation:
  21   - Client fetches networkstatus, picks guards, connects to one.
  22   - Client picks middle hop out of networkstatus, asks guard for
  23     its descriptor, then extends to it.
  24   - Clients picks exit hop out of networkstatus, asks middle hop
  25     for its descriptor, then extends to it. Done.
  26
  27 The client needs to ask for the descriptor even if it already has a
  28 copy, because otherwise we leak too much. Also, the descriptor needs to
  29 be padded to some large (but not too large) size to prevent the middle
  30 hops from guessing about it.
  31
  32 The first step towards this is to instrument the current code to see
  33 how much of a win this would actually be -- I am guessing it is already
  34 a win even with the current number of descriptors.
  35
  36 We also would need to assign the 'Exit' flag more usefully, and make
  37 clients pay attention to it when picking their last hop, since they
  38 don't actually know the exit policies of the relays they're choosing from.
  39
  40 We also need to think harder about other implications -- for example,
  41 a relay with a tiny exit policy won't get the Exit flag, and thus won't
  42 ever get picked as an exit relay. Plus, our "enclave exit" model is out
  43 the window unless we figure out a cool trick.
  44
  45 More generally, we'll probably want to compress the descriptors that we
  46 send back; maybe 8k is a good upper bound? I wonder if we could ask for
  47 several descriptors, and bundle back all of the ones that fit in the 8k?
  48
  49 We'd also want to put the load balancing weights into the networkstatus,
  50 so clients can choose fast nodes more often without needing to see the
  51 descriptors. This is a good opportunity for the authorities to be able
  52 to put "more accurate" weights in if they learn to detect attacks. It
  53 also means we should consider running automated audits to make sure the
  54 authorities aren't trying to snooker everybody.
  55
  56 I'm aiming to get Peter Palfrader to tackle this problem in mid 2008,
  57 but I bet he could use some help.
  58
  59 --------------------------------------------------------------------
  60
  61 Piece two: inter-relay communication uses UDP
  62
  63 If relays send packets to/from other relays via UDP, they don't need a
  64 new descriptor for each such link. Thus we'll still need to keep state
  65 for each link, but we won't max out on sockets.
  66
  67 Clearly a lot more work needs to be done here. Ian Goldberg has a student
  68 who has been working on it, and if all goes well we'll be chipping in
  69 some funding to continue that. Also, Camilo Viecco has been doing his
  70 PhD thesis on it.
  71
  72 --------------------------------------------------------------------
  73
  74 Piece three: networkstatus documents get partitioned
  75
  76 While the authorities should be expected to be able to handle learning
  77 about all the relays, there's no reason the clients or the mirrors need
  78 to. Authorities should put a cap on the number of relays listed in a
  79 single networkstatus, and split them when they get too big.
  80
  81 We'd need a good way to have each authority come to the same conclusion
  82 about which partition a given relay goes into.
  83
  84 Directory mirrors would then mirror all the relay descriptors in their
  85 partition. This is compatible with 'piece one' above, since clients in
  86 a given partition will only ask about descriptors in that partition.
  87
  88 More complex versions of this design would involve overlapping partitions,
  89 but that would seem to start contradicting other parts of this proposal
  90 right quick.
  91
  92 Nobody is working on this piece yet. It's hard to say when we'll need
  93 it, but it would be nice to have some more thought on it before the week
  94 that we need it.
  95
  96 --------------------------------------------------------------------
  97