Handle unstable relays better
Here's what we promised: "The Tor Project will investigate and expand our research and designs for Consensus Diffs in Proposal 140. Tor clients and servers need a list of which relays are on the network. This list, the consensus, is created by authorities hourly and clients fetch a new copy of it every two to four hours. We will research, design, and implement approaches that allow clients to download diffs of the consensus at more frequent intervals. This improvement will save bandwidth on both the client and relay side, but more importantly it will allow clients to more quickly discover changes in relay addresses."
I think scheduling this work for 0.2.5 is a good timeframe (assuming we can stick to our 0.2.4 schedule).
This is intended to be a pretty broad scope of "better handle relays that aren't so stable", so we should brainstorm and add related topics that will also help -- such as "relays notice that their IP has changed faster so they republish faster", "the bwauths form an opinion quicker about new relays", "the dirauths should publish v3 interim votes between themselves more often", etc.
Activity
changed milestone to %Tor: unspecified
gnunet used this paper for its diff approach: http://conferences.sigcomm.org/sigcomm/2011/papers/sigcomm/p218.pdf "Efficient Set Reconciliation without Prior Context"
Replying to arma:
gnunet used this paper for its diff approach: http://conferences.sigcomm.org/sigcomm/2011/papers/sigcomm/p218.pdf "Efficient Set Reconciliation without Prior Context"
This seems overly complex (and susceptible to patent trolling) for use in a system where the participants do have ‘prior context’.
I've been doing some experiments on consensus diffs. These are performed against the current June archive of consensuses from metrics.tpo. Unfortunately, it seems that microdescriptor consensuses are not included in these archives, so my next step is to reconstruct/fake those, and run my analysis on them.
Here are the average compressed and uncompressed consensus sizes, for reference:
gz: mean 276414. median 276649 bz2: mean 229236. median 229452 xz: mean 248717. median 248908 uncompressed: mean 854707. median 856168Note that we could save over 15% of our consensus traffic just by switching our compression to bzip2.
First, I experimented with different diff formats, compressed both with "gzip -9" and "bzip -9". I tried standard diff, unified diff (expected to suck), and ed-style diff. Predictably, the ed style diff was the smallest. I did these comparisons between consensuses that were 1, 2, 4, 6, and 8 hours apart.
EXPERIMENT 1: REGULAR CONSENSUSES diff_gz: lag 1: mean 56833. median 55956 diff_gz: lag 2: mean 94252. median 93464 diff_gz: lag 4: mean 155933. median 155169 diff_gz: lag 6: mean 210275. median 209497 diff_gz: lag 8: mean 257186. median 257104 diff_bz2: lag 1: mean 54055. median 53210 diff_bz2: lag 2: mean 88863. median 88298 diff_bz2: lag 4: mean 146734. median 145987 diff_bz2: lag 6: mean 197943. median 197360 diff_bz2: lag 8: mean 242272. median 242403 diff_u_gz: lag 1: mean 173493. median 170642 diff_u_gz: lag 2: mean 233502. median 231120 diff_u_gz: lag 4: mean 296600. median 294960 diff_u_gz: lag 6: mean 335361. median 334571 diff_u_gz: lag 8: mean 361879. median 361714 diff_u_bz2: lag 1: mean 150857. median 148773 diff_u_bz2: lag 2: mean 202537. median 200466 diff_u_bz2: lag 4: mean 259363. median 257591 diff_u_bz2: lag 6: mean 299156. median 298317 diff_u_bz2: lag 8: mean 326355. median 326309 diff_e_gz: lag 1: mean 32380. median 31956 diff_e_gz: lag 2: mean 54258. median 53950 diff_e_gz: lag 4: mean 90962. median 90803 diff_e_gz: lag 6: mean 123734. median 123457 diff_e_gz: lag 8: mean 152219. median 152158 diff_e_bz2: lag 1: mean 29329. median 29017 diff_e_bz2: lag 2: mean 48470. median 48333 diff_e_bz2: lag 4: mean 80394. median 80229 diff_e_bz2: lag 6: mean 108689. median 108410 diff_e_bz2: lag 8: mean 133337. median 133124 condiff_gz: lag 1: mean 43806. median 35518 condiff_gz: lag 2: mean 70634. median 60643 condiff_gz: lag 4: mean 109675. median 112926 condiff_gz: lag 6: mean 140493. median 144589 condiff_gz: lag 8: mean 165163. median 167669 condiff_bz2: lag 1: mean 39425. median 32417 condiff_bz2: lag 2: mean 62459. median 53976 condiff_bz2: lag 4: mean 95757. median 98261 condiff_bz2: lag 6: mean 121948. median 125166 condiff_bz2: lag 8: mean 142900. median 144902The "conndiff" algorithm is a quick hack I tried myself to try to answer the question, "How bad would performance be if I hand-rolled a special-purpose solution?" It works by copying the header and the footer verbatim, and between them doing a router-by-router comparison. If a router has been removed, it emits "-\n". If a router has been added, it emits "* " and the new router entry. If a router has had its lines change, but not the first line, it emits ".\n" and then all changed lines. If a router has had lines change including the first line, it emits the new first line, followed by all changed lines.
Next, I looked at the results. Where were most of the lines in the diffs? Which lines and fields changed the most? What I found was that the most commonly changed line was "w", followed by "r", followed by "s". When the r lines changed, they most frequently changed in their descriptor digest and published fields.
To experiment with the effects of quantizing w a little harder (yes, I know that presents problems for bw measurement), I tried a variant experiment where I rounded all weights under 8 to 8, and retained only the 1 most significant bit of bandwidths under 128, only the 2 msb of bandwidths under 1024, and only the 3 msb of all other bandwidths.
EXPERIMENT 2: ROUNDED BANDWIDTHS gz: mean 273004. median 273213 bz2: mean 225879. median 226083 xz: mean 246151. median 246396 uncompressed: mean 854437. median 855888 diff_gz: lag 1: mean 47681. median 46928 diff_gz: lag 2: mean 82396. median 81765 diff_gz: lag 4: mean 141794. median 140603 diff_gz: lag 6: mean 194732. median 194116 diff_gz: lag 8: mean 240577. median 240687 diff_bz2: lag 1: mean 46906. median 46173 diff_bz2: lag 2: mean 79749. median 79272 diff_bz2: lag 4: mean 135840. median 134990 diff_bz2: lag 6: mean 185960. median 185280 diff_bz2: lag 8: mean 229477. median 229776 diff_u_gz: lag 1: mean 95696. median 90798 diff_u_gz: lag 2: mean 151455. median 147334 diff_u_gz: lag 4: mean 227687. median 224847 diff_u_gz: lag 6: mean 280858. median 278609 diff_u_gz: lag 8: mean 319106. median 318876 diff_u_bz2: lag 1: mean 86029. median 81964 diff_u_bz2: lag 2: mean 134455. median 131198 diff_u_bz2: lag 4: mean 201620. median 199355 diff_u_bz2: lag 6: mean 249981. median 247689 diff_u_bz2: lag 8: mean 288642. median 288522 diff_e_gz: lag 1: mean 27796. median 27497 diff_e_gz: lag 2: mean 48344. median 48051 diff_e_gz: lag 4: mean 83978. median 83712 diff_e_gz: lag 6: mean 116101. median 115716 diff_e_gz: lag 8: mean 144135. median 143900 diff_e_bz2: lag 1: mean 25905. median 25665 diff_e_bz2: lag 2: mean 44093. median 43915 diff_e_bz2: lag 4: mean 75155. median 74913 diff_e_bz2: lag 6: mean 102904. median 102554 diff_e_bz2: lag 8: mean 127088. median 126825 condiff_gz: lag 1: mean 41209. median 33046 condiff_gz: lag 2: mean 67233. median 57367 condiff_gz: lag 4: mean 105669. median 108934 condiff_gz: lag 6: mean 136169. median 140411 condiff_gz: lag 8: mean 160624. median 163230 condiff_bz2: lag 1: mean 37453. median 30484 condiff_bz2: lag 2: mean 59874. median 51744 condiff_bz2: lag 4: mean 92699. median 95425 condiff_bz2: lag 6: mean 118630. median 121854 condiff_bz2: lag 8: mean 139430. median 141450That helps a little, but it's sure not an obviously wonderful idea.
Next step: ersatz microdesc consensuses.
-
Another note on shorter/easier consensuses to meditate upon: We use the published_on field from the "r" line for very little. Videlicet:
- In networkstatus.c, in client_would_use_router, in a way that is basically nonsensical for microdescriptor consensuses.
- In router.c, in mark_my_descriptor_dirty_if_too_old, to tell whether we a router needs to upload a new descriptor.
- In routerlist.c, in routerlist_remove_old_routers, in a way that makes no sense for microdescriptor consensuses.
I'm not sure the best response to this information, though.
-
Okay, here's the third batch.
Since we don't appear to have microdescriptor consensus archives, I faked some. I took all the votes from the month in question, and built a table mapping descriptor digest to voted-on v8 microdescriptor digest. (I used v8 because everything has a v8; this will throw off results a little though.) And then I used another script to postprocess the regular conensuses into microdescriptor-consensus-like things, by removing the descriptor digest from the "r" line and adding a corresponding "m" line. Of course, the signatures aren't valid on those, but that shouldn't make the measurements wrong.
This table includes a set of "condiff2" measurements. These used an algorithm similar to "conndiff", except that they try harder to minimize "r" and "s" lines. The s lines now include only the changed flags (prefixed with a + or -), and the r lines now include only the changed fields (with the r suffixed with the field indices). This is still a kludge, even bigger than the last kludge.
EXPERIMENT 3: ERSATZ MICRODESCRIPTOR CONSENSUSES gz: mean 326449. median 326641 bz2: mean 277180. median 277835 xz: mean 297899. median 298140 uncompressed: mean 920397. median 921975 diff_gz: lag 1: mean 50356. median 49460 diff_gz: lag 2: mean 81220. median 80293 diff_gz: lag 4: mean 129828. median 128991 diff_gz: lag 6: mean 171407. median 170568 diff_gz: lag 8: mean 206859. median 206379 diff_bz2: lag 1: mean 47274. median 46564 diff_bz2: lag 2: mean 75232. median 74429 diff_bz2: lag 4: mean 119625. median 118888 diff_bz2: lag 6: mean 157949. median 157200 diff_bz2: lag 8: mean 190432. median 189854 diff_u_gz: lag 1: mean 169543. median 166231 diff_u_gz: lag 2: mean 232762. median 229722 diff_u_gz: lag 4: mean 301298. median 298904 diff_u_gz: lag 6: mean 343474. median 341967 diff_u_gz: lag 8: mean 371618. median 370834 diff_u_bz2: lag 1: mean 150566. median 147908 diff_u_bz2: lag 2: mean 205454. median 202992 diff_u_bz2: lag 4: mean 266339. median 264134 diff_u_bz2: lag 6: mean 307525. median 306157 diff_u_bz2: lag 8: mean 335207. median 334631 diff_e_gz: lag 1: mean 29085. median 28736 diff_e_gz: lag 2: mean 47697. median 47365 diff_e_gz: lag 4: mean 77821. median 77752 diff_e_gz: lag 6: mean 104169. median 104026 diff_e_gz: lag 8: mean 126932. median 126427 diff_e_bz2: lag 1: mean 25963. median 25667 diff_e_bz2: lag 2: mean 41830. median 41676 diff_e_bz2: lag 4: mean 67435. median 67218 diff_e_bz2: lag 6: mean 89650. median 89523 diff_e_bz2: lag 8: mean 108744. median 108210 condiff_gz: lag 1: mean 43394. median 32943 condiff_gz: lag 2: mean 69116. median 56412 condiff_gz: lag 4: mean 104882. median 112103 condiff_gz: lag 6: mean 131878. median 140190 condiff_gz: lag 8: mean 152803. median 159291 condiff_bz2: lag 1: mean 38842. median 29785 condiff_bz2: lag 2: mean 60713. median 49797 condiff_bz2: lag 4: mean 90748. median 97287 condiff_bz2: lag 6: mean 113359. median 120583 condiff_bz2: lag 8: mean 130878. median 136453 condiff2_gz: lag 1: mean 34492. median 23456 condiff2_gz: lag 2: mean 52918. median 38968 condiff2_gz: lag 4: mean 75948. median 87076 condiff2_gz: lag 6: mean 91545. median 104040 condiff2_gz: lag 8: mean 102485. median 112830 condiff2_bz2: lag 1: mean 31025. median 21394 condiff2_bz2: lag 2: mean 46673. median 34578 condiff2_bz2: lag 4: mean 65934. median 76072 condiff2_bz2: lag 6: mean 78876. median 89747 condiff2_bz2: lag 8: mean 87823. median 96913Next I'll do this one last time, with microdescriptor consensuses and weight rounding. Then conclusions.
-
Trac:
7009-scripts.tgz -
EXPERIMENT 4: ERSATZ CONSENSUSES, ROUNDED BANDWIDTHS. gz: mean 322894. median 323069 bz2: mean 273724. median 274286 xz: mean 295111. median 295356 uncompressed: mean 920127. median 921695 diff_gz: lag 1: mean 41129. median 40341 diff_gz: lag 2: mean 69318. median 68533 diff_gz: lag 4: mean 115704. median 114638 diff_gz: lag 6: mean 155998. median 154739 diff_gz: lag 8: mean 190471. median 189827 diff_bz2: lag 1: mean 39991. median 39290 diff_bz2: lag 2: mean 66028. median 65522 diff_bz2: lag 4: mean 108645. median 107787 diff_bz2: lag 6: mean 145728. median 144692 diff_bz2: lag 8: mean 177552. median 176963 diff_u_gz: lag 1: mean 95974. median 91003 diff_u_gz: lag 2: mean 152232. median 148482 diff_u_gz: lag 4: mean 229693. median 226527 diff_u_gz: lag 6: mean 284126. median 281542 diff_u_gz: lag 8: mean 323156. median 322321 diff_u_bz2: lag 1: mean 87438. median 83218 diff_u_bz2: lag 2: mean 136819. median 133732 diff_u_bz2: lag 4: mean 204971. median 202190 diff_u_bz2: lag 6: mean 253759. median 251444 diff_u_bz2: lag 8: mean 291965. median 291438 diff_e_gz: lag 1: mean 24500. median 24283 diff_e_gz: lag 2: mean 41771. median 41565 diff_e_gz: lag 4: mean 70823. median 70702 diff_e_gz: lag 6: mean 96538. median 96321 diff_e_gz: lag 8: mean 118815. median 118229 diff_e_bz2: lag 1: mean 22576. median 22362 diff_e_bz2: lag 2: mean 37485. median 37334 diff_e_bz2: lag 4: mean 62140. median 62018 diff_e_bz2: lag 6: mean 83808. median 83764 diff_e_bz2: lag 8: mean 102464. median 101987 condiff_gz: lag 1: mean 40820. median 30467 condiff_gz: lag 2: mean 65680. median 53088 condiff_gz: lag 4: mean 100733. median 108400 condiff_gz: lag 6: mean 127434. median 135817 condiff_gz: lag 8: mean 148174. median 154829 condiff_bz2: lag 1: mean 36884. median 27925 condiff_bz2: lag 2: mean 58159. median 47347 condiff_bz2: lag 4: mean 87716. median 94317 condiff_bz2: lag 6: mean 109993. median 117235 condiff_bz2: lag 8: mean 127244. median 132674 condiff2_gz: lag 1: mean 32068. median 21197 condiff2_gz: lag 2: mean 49722. median 35756 condiff2_gz: lag 4: mean 72140. median 83949 condiff2_gz: lag 6: mean 87432. median 99928 condiff2_gz: lag 8: mean 98180. median 108847 condiff2_bz2: lag 1: mean 29133. median 19605 condiff2_bz2: lag 2: mean 44176. median 32174 condiff2_bz2: lag 4: mean 62918. median 73406 condiff2_bz2: lag 6: mean 75558. median 86409 condiff2_bz2: lag 8: mean 84334. median 93443 
Interesting stuff. Two somewhat off-topic remarks:
-
Do you think we should include microdescriptor consensuses and microdescriptors in the archives? They're left out right now, because we can learn most/all of their relevant content from other descriptors. But if you think it would be convenient to archive them, I'll include them. (Needs a new ticket, just mentioning it here.)
-
Do you want me to add your attached scripts to metrics-tasks.git? That repository holds all kinds of one-off code, including ugly hacks, in case we want to do something similar in the future. Happy to add this code for you if you think it makes sense.
-
-
Comments:
- This doesn't really have much to do with dynamic IPs.
- There's a lot of space going to relays that clients mostly don't use. If we realizing that if we discarded all nodes with Bandwidth=X for X under 100 we'd dump 48% of the nodes in the md consensus, but only about half of a percent of the total capacity according to Bandwidth=X.
- If we decide to do that, though, we should re-run the measurements.
- bzip2 is a clear win.
- For diffs, the "diff -e" output is (as predicted) a clear winner, followed by a kludgey roll-our-own format.
- The main reason why diff -e wins is that my roll-my-own test kludge format doesn't handle headers and footers so nicely. In quick-and-dirty tests: if it were considering only the body, it would be within 3% of diff -e.
- There still isn't a good C library we can link for diff. Otherwise, we could do worse than exec as needed and require a working diff on every Tor directory, I suppose.
- If we don't need so much bandwidth weight granularity, we could win some space by dropping it.
- Rounding bandwidths off helps a little, but I'm not sure what we lose by doing so.
- We don't actually know what fraction of clients download a new consensus with what period. Sure, if you're online constantly, you get a new one every 2-4 hours... but is that typical?
-
Replying to karsten:
Interesting stuff. Two somewhat off-topic remarks:
- Do you think we should include microdescriptor consensuses and microdescriptors in the archives? They're left out right now, because we can learn most/all of their relevant content from other descriptors. But if you think it would be convenient to archive them, I'll include them. (Needs a new ticket, just mentioning it here.)
I would have found it convenient here.
- Do you want me to add your attached scripts to metrics-tasks.git? That repository holds all kinds of one-off code, including ugly hacks, in case we want to do something similar in the future. Happy to add this code for you if you think it makes sense.
Yes, please do, in a little subdirectory or something.
-
Replying to nickm:
Replying to karsten:
Interesting stuff. Two somewhat off-topic remarks:
- Do you think we should include microdescriptor consensuses and microdescriptors in the archives? They're left out right now, because we can learn most/all of their relevant content from other descriptors. But if you think it would be convenient to archive them, I'll include them. (Needs a new ticket, just mentioning it here.)
I would have found it convenient here.
Okay. Re-opened #2785 (moved).
- Do you want me to add your attached scripts to metrics-tasks.git? That repository holds all kinds of one-off code, including ugly hacks, in case we want to do something similar in the future. Happy to add this code for you if you think it makes sense.
Yes, please do, in a little subdirectory or something.
Done:
https://gitweb.torproject.org/metrics-tasks.git/tree/HEAD:/task-7009
-
Replying to nickm:
- We don't actually know what fraction of clients download a new consensus with what period. Sure, if you're online constantly, you get a new one every 2-4 hours... but is that typical?
This is a great other research question that we should investigate (probably with its own ticket).
In particular, I have the feeling that clients who are online constantly don't fetch a mean of 8 consensuses a day -- I think it's quite a bit more often than that, and I bet there are some bugs to explain it. We have the torperf logs as example Tor-clients-online-constantly, and I vaguely remember that I've had a discussion with Karsten about this topic in the past. Karsten?
-
Replying to arma:
In particular, I have the feeling that clients who are online constantly don't fetch a mean of 8 consensuses a day -- I think it's quite a bit more often than that, and I bet there are some bugs to explain it. We have the torperf logs as example Tor-clients-online-constantly, and I vaguely remember that I've had a discussion with Karsten about this topic in the past. Karsten?
Looks like #2963 (moved).
-
Replying to nickm:
- This doesn't really have much to do with dynamic IPs.
I think that's ok, so long as we decide it's a good and useful thing to do for Tor.
- There's a lot of space going to relays that clients mostly don't use. If we realizing that if we discarded all nodes with Bandwidth=X for X under 100 we'd dump 48% of the nodes in the md consensus, but only about half of a percent of the total capacity according to Bandwidth=X.
Sounds like #1854 (moved). I think the current direction there is that Paul et al have argued we should keep small relays in the consensus, even if clients don't use them, since this is a community and turning away half our volunteers simply because we don't currently need them will harm the community. (Also, there are future directions like path splitting that might be able to make use of them again.)
I admit that I'm intrigued by the notion of having them in some form of the consensus but maybe not all forms.
- There still isn't a good C library we can link for diff. Otherwise, we could do worse than exec as needed and require a working diff on every Tor directory, I suppose.
Don't the clients need a working diff program too, to combine their current consensus with the new update they fetched? I guess it depends on our design, but I always figured it would be clients who fetch diffs too.
- If we don't need so much bandwidth weight granularity, we could win some space by dropping it.
- Rounding bandwidths off helps a little, but I'm not sure what we lose by doing so.
It doesn't look like the win is enough to merit trying to answer this question. (Or alternatively, it does look like we can make that decision later, and any of these diff approaches will benefit from that change then, yes?)
-
Replying to arma:
Don't the clients need a working diff program too, to combine their current consensus with the new update they fetched? I guess it depends on our design, but I always figured it would be clients who fetch diffs too.
They need a working patch program, which is way easier and less error-prone than an efficient diff.
The "ed" diff format is especially simple: http://www.chemie.fu-berlin.de/chemnet/use/info/diff/diff_3.html#SEC32
-
Replying to arma:
Replying to arma:
In particular, I have the feeling that clients who are online constantly don't fetch a mean of 8 consensuses a day -- I think it's quite a bit more often than that, and I bet there are some bugs to explain it. We have the torperf logs as example Tor-clients-online-constantly, and I vaguely remember that I've had a discussion with Karsten about this topic in the past. Karsten?
Looks like #2963 (moved).
We had torperf info-level logs, but then disks ran full and we switched back to notice-level logs. Changed to info-level logs again on ferrinii. Will paste some stats on consensus downloads on #2963 (moved) in a week from now.
moved to tpo/core/tor#7009 (closed)