Opened 7 years ago

Closed 2 years ago

#7009 closed project (duplicate)

Handle unstable relays better

Reported by: arma Owned by:
Priority: Medium Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-relay, SponsorJ, tor-03-unspecified-201612
Cc: Actual Points:
Parent ID: Points:
Reviewer: Sponsor: Sponsor4

Description

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.

Child Tickets

Attachments (1)

7009-scripts.tgz (2.9 KB) - added by nickm 6 years ago.

Download all attachments as: .zip

Change History (22)

comment:1 Changed 7 years ago by 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"

comment:2 in reply to:  1 Changed 7 years ago by rransom

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’.

comment:3 Changed 6 years ago by nickm

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 856168

Note 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 144902

The "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 141450

That helps a little, but it's sure not an obviously wonderful idea.

Next step: ersatz microdesc consensuses.

comment:4 Changed 6 years ago by nickm

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.

comment:5 Changed 6 years ago by nickm

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 96913

Next I'll do this one last time, with microdescriptor consensuses *and* weight rounding. Then conclusions.

comment:6 Changed 6 years ago by nickm

Milestone: Tor: unspecifiedTor: 0.2.5.x-final

Changed 6 years ago by nickm

Attachment: 7009-scripts.tgz added

comment:7 Changed 6 years ago by nickm

Just added an attachment of the scripts that I used to do this stuff. They are UGLY.

comment:8 Changed 6 years ago by nickm

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

comment:9 Changed 6 years ago by 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.)
  • 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.

comment:10 Changed 6 years ago by nickm

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?

comment:11 in reply to:  9 ; Changed 6 years ago by 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.

  • 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.

comment:12 in reply to:  11 Changed 6 years ago by karsten

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.

  • 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

comment:13 in reply to:  10 ; Changed 6 years ago by arma

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?

comment:14 in reply to:  13 ; Changed 6 years ago by 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.

comment:15 in reply to:  10 ; Changed 6 years ago by arma

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. 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?)

comment:16 in reply to:  15 Changed 6 years ago by nickm

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

comment:17 in reply to:  14 Changed 6 years ago by karsten

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.

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 in a week from now.

comment:18 Changed 5 years ago by nickm

Milestone: Tor: 0.2.5.x-finalTor: 0.2.???

comment:19 Changed 3 years ago by teor

Milestone: Tor: 0.2.???Tor: 0.3.???

Milestone renamed

comment:20 Changed 3 years ago by nickm

Keywords: tor-03-unspecified-201612 added
Milestone: Tor: 0.3.???Tor: unspecified

Finally admitting that 0.3.??? was a euphemism for Tor: unspecified all along.

comment:21 Changed 2 years ago by nickm

Resolution: duplicate
Severity: Normal
Sponsor: Sponsor4
Status: newclosed

The remaining work here is superseded by the sponsor4 work now ongoing.

Note: See TracTickets for help on using tickets.