Opened 20 months ago

Closed 5 weeks ago

Last modified 5 weeks ago

#9321 closed project (implemented)

Load balance right when we have higher guard rotation periods

Reported by: arma Owned by:
Priority: major Milestone: Tor: 0.2.6.x-final
Component: Tor Version:
Keywords: needs-proposal, tor-auth, tor-client, 026-triaged-1, unfrozen, nickm-review Cc: amj703, NickHopper, isis
Actual Points: Parent ID: #11480
Points:

Description (last modified by arma)

Here's our plan:

1) Directory authorities need to track how much of the past n months each relay was around and had the Guard flag.
2) They vote a percentage for each relay in their vote, and the consensus has a new keyword on the w line so clients can learn how Guardy each relay has been.
3) Clients change their load balancing algorithm to consider how Guardy you've been, rather than just treating Guard status as binary (#8453).
4) Raise the guard rotation period a lot (#8240).

Child Tickets

Attachments (1)

results (435.7 KB) - added by asn 8 months ago.
some initial results

Download all attachments as: .zip

Change History (56)

comment:1 Changed 20 months ago by arma

  • Keywords needs-proposal added

comment:2 Changed 20 months ago by arma

  • Keywords tor-auth tor-client added

comment:3 Changed 20 months ago by arma

  • Description modified (diff)

comment:4 Changed 20 months ago by mikeperry

  • Parent ID set to #8453

comment:5 follow-up: Changed 20 months ago by hsn

take into account available bw on relay: advertised bw - actual bw used. Slow guard is really bad for user experience.

exit nodes should not be used as guard too often, it wastes their bw.

comment:6 in reply to: ↑ 5 Changed 20 months ago by arma

Replying to hsn:

take into account available bw on relay: advertised bw - actual bw used. Slow guard is really bad for user experience.

I don't think we have quick enough feedback to make this work right. Instead, I think something like conflux's "adapt which circuit you use based on round-trip times" is going to serve us better for this one.

exit nodes should not be used as guard too often, it wastes their bw.

I agree.

comment:7 Changed 20 months ago by hsn

You need to know GB/day from relay, there is not much day to day variance. This is for load balancing enough. Bit problematic can be relays with not fixed bw limit, their GB/day depends on weight assigned way more then relays with fixed bw limit.

You need to watch for trends in young relays < 1month. They continually increasing their traffic, increase rate seems to be constant.

If you plan to have just 2 guards and long cycle time, then its important to prefer guards with spare bandwidth.

comment:8 Changed 16 months ago by amj703

  • Cc amj703 added

comment:9 Changed 13 months ago by nickm

  • Milestone changed from Tor: 0.2.5.x-final to Tor: 0.2.6.x-final

comment:10 Changed 9 months ago by nickm

  • Keywords 026 added
  • Parent ID changed from #8453 to #11480

comment:11 Changed 9 months ago by nickm

  • Keywords 026-triaged-1 added; 026 removed

comment:12 Changed 8 months ago by asn

FWIW, here is our plan from proposal 236 wrt this ticket:

   A guard N that has been visible for V out of NNN*30*24 consensuses
   has had the opportunity to be chosen as a guard by approximately
   F = V/NNN*30*24 of the clients in the network, and the remaining
   1-F fraction of the clients have not noticed this change.  So when
   being chosen for middle or exit positions on a circuit, clients
   should treat N as if F fraction of its bandwidth is a guard
   (respectively, dual) node and (1-F) is a middle (resp, exit) node.
   Let Wpf denote the weight from the 'bandwidth-weights' line a
   client would apply to N for position p if it had the guard
   flag, Wpn the weight if it did not have the guard flag, and B the
   measured bandwidth of N in the consensus.  Then instead of choosing
   N for position p proportionally to Wpf*B or Wpn*B, clients should
   choose N proportionally to F*Wpf*B + (1-F)*Wpn*B.

   Similarly, when calculating the bandwidth-weights line as in
   section 3.8.3 of dir-spec.txt, directory authorities should treat N
   as if fraction F of its bandwidth has the guard flag and (1-F) does
   not.  So when computing the totals G,M,E,D, each relay N with guard
   visibility fraction F and bandwidth B should be added as follows:

   G' = G + F*B, if N does not have the exit flag
   M' = M + (1-F)*B, if N does not have the exit flag
   D' = D + F*B, if N has the exit flag
   E' = E + (1-F)*B, if N has the exit flag

comment:13 follow-up: Changed 8 months ago by asn

I've done a bit of progress on this. I have a stupid Python script
that you can point to a directory with consensus documents. It will
parse them all (using stem), and for each guard it will spit out the
number of consensuses it was mentioned in, as well as when was the
earliest and the latest consensus it was in.

The idea is that this script will have to be finished, and then
somehow executed in the authorities. The script will spit out an
output file that can be parsed by little-t-tor in the same fashion as
the bandwidth authorities do (see measured_bw_line_parse()).

Few questions that will need to be answered:

  • Will the script be called periodically and the authorities will have to parse the output file every once in a while? Or will the script be ran once, and then it's the job of the authorities to internally update their state with new information?

I'm currently aiming for the former behavior, to minimize the amount
of code that needs to be written for little-t-tor. OTOH, this means
that authorities will need to keep 9 months worth of consensuses in
their filesystem. As we move closer to completion of this task we
will see if the former behavior is indeed better.

  • Where will the consensuses be fetched from? To run this script we need to have a directory filled with consensuses. How are we going to get those documents? rsync cronjob from metrics? Does this scale? What else can we do?
  • What should we do about consensus signatures? If we are fetching consensuses from metrics, it's reasonable that we don't want to trust them blindly. It would be nice if the script (or the auth) could validate the consensus signatures, but it's not an easy task:

How will the script get the public keys of the auths? What if the
auths set change? What if (as part of an attack) we are given a
consensus with only one or two auth signatures? Should it be
accepted even though it's signed by a minority of auths? Should our
stupid script understand all these consesus security details?

  • What should happen if we are missing a few consensuses? Sometimes the auths fail to establish a consensus, so it's reasonable that a few consesuses will be missing if we look 9 months back. Should our Python script recognize their absense? What if half of the consesuses are missing? What if just one is missing? How should our script react?
  • We need to think how the guardiness information will be passed to clients (since clients need to change their path selection procedure according to the guardiness). Proposal 236 simply says:
     The authorities include the age of each guard by appending
     '[SP "GV=" INT]' in the guard's "w" line.
    
    But I don't think that's enough. What is an age anyway?

Should we pass to clients information like "Node was a guard for
3031/6574 consensuses during the past 9 months"? Should this be
passed in the consensus as part of the 'w' line or something?

  • How should this be deployed?

In the beginning it should parse 2-3 months worth of consesuses (the
current guard lifetime period), and then as more clients upgrade we
should make it parse 9-10 months (or whatever we decide) worth of
consesuses?

I'm planning to tackle these questions soon. Any feedback is helpful!

comment:14 follow-up: Changed 8 months ago by asn

Also, any ideas on the format of the file that the script should output?
What would be the easiest format for little-t-tor to parse these days?

I'm looking at dirserv_read_measured_bandwidths() but the file format of the bw auths looks a bit arbitrary. It's pretty easy to parse but it's not something that can be reused. Can I reuse a file parser of little-t-tor, or should I write yet another file format?

The information that needs to be transmitted could be something like
this (maybe I'm forgetting some info, or adding redundant info):

<date and time>
<number of consesuses parsed> <number of months considered>

<guard fpr 1> <number of times seen in a consensus>
<guard fpr 2> <number of times seen in a consensus>
<guard fpr 3> <number of times seen in a consensus>
<guard fpr 4> <number of times seen in a consensus>
<guard fpr 5> <number of times seen in a consensus>
...

Changed 8 months ago by asn

some initial results

comment:15 Changed 8 months ago by asn

I also attached some initial results in attachment:results just to get an idea of what's going on.
It's 3 months worth of consensuses, and the computation took around 15 minutes on a decent box.

comment:16 in reply to: ↑ 13 ; follow-up: Changed 8 months ago by NickHopper

Replying to asn:

Few questions that will need to be answered:

  • Will the script be called periodically and the authorities will have

to parse the output file every once in a while? Or will the script
be ran once, and then it's the job of the authorities to internally
update their state with new information?

I'm currently aiming for the former behavior, to minimize the amount
of code that needs to be written for little-t-tor. OTOH, this means
that authorities will need to keep 9 months worth of consensuses in
their filesystem. As we move closer to completion of this task we
will see if the former behavior is indeed better.

FWIW, I agree this is probably the right design, though parsing 9 months worth of consensuses with stem is no mean feat. An alternative would be to have the script keep a summary file that is updated as new consensuses are fetched; it might store, e.g. the number of consensuses a relay appeared in for each day, and then could get batch updated.

  • What should we do about consensus signatures? If we are fetching

consensuses from metrics, it's reasonable that we don't want to
trust them blindly. It would be nice if the script (or the auth)
could validate the consensus signatures, but it's not an easy task:

I recently submitted a patch to stem (#11045) that can check consensus signatures, and certificates, so that part should be simple. Getting the certificates should also be easy -- every directory server serves the list of current certs at http://<hostname>:<dirport>/tor/keys/all.z and every tor client stores the list in .tor/cached-certs . stem will happily parse these with parse_file(), though you might need to give it a hint about the file type. Getting historical keys is more problematic; the script probably needs to retain a cache of old certs. (Incidentally, metrics serves this, it's not very big.)

  • What should happen if we are missing a few consensuses? Sometimes

the auths fail to establish a consensus, so it's reasonable that a
few consesuses will be missing if we look 9 months back. Should our
Python script recognize their absense? What if half of the
consesuses are missing? What if just one is missing? How should our
script react?

These are good questions. At the winter dev meeting, I think Nick suggested that when the auths fail to establish a consensus, there should be a signed "consensus failed" message. I guess this requires another proposal, but if we had it going forward, then there shouldn't be a missing consensus.

  • We need to think how the guardiness information will be passed to

clients (since clients need to change their path selection procedure
according to the guardiness). Proposal 236 simply says:

The authorities include the age of each guard by appending
'[SP "GV=" INT]' in the guard's "w" line.

But I don't think that's enough. What is an age anyway?

Should we pass to clients information like "Node was a guard for
3031/6574 consensuses during the past 9 months"? Should this be
passed in the consensus as part of the 'w' line or something?

Agreed that the number of consensuses counted for GV should appear in the consensus; it could be in the w line or could also appear once in the document, e.g. before 'bandwidth-weights' there could be a line of the form

"guard-visibility-max" INT NL

And this would help with the deployment also; we could start with 3 months' worth of consensuses and just add consensuses as they are produced.

comment:17 Changed 8 months ago by NickHopper

  • Cc NickHopper added

comment:18 in reply to: ↑ 14 Changed 8 months ago by nickm

Replying to asn:

Also, any ideas on the format of the file that the script should output?
What would be the easiest format for little-t-tor to parse these days?

I'm looking at dirserv_read_measured_bandwidths() but the file format of the bw auths looks a bit arbitrary. It's pretty easy to parse but it's not something that can be reused. Can I reuse a file parser of little-t-tor, or should I write yet another file format?

The information that needs to be transmitted could be something like
this (maybe I'm forgetting some info, or adding redundant info):

<date and time>
<number of consesuses parsed> <number of months considered>

<guard fpr 1> <number of times seen in a consensus>
<guard fpr 2> <number of times seen in a consensus>
<guard fpr 3> <number of times seen in a consensus>
<guard fpr 4> <number of times seen in a consensus>
<guard fpr 5> <number of times seen in a consensus>
...

Generally, a file full of "key value\n" lines are easiest to parse with Tor right now. So let me suggest:

written-at <date and time>
n-inputs <number of consesuses parsed> <number of months considered>

guard-seen <guard fpr 1> <number of times seen in a consensus> ...
guard-seen <guard fpr 2> <number of times seen in a consensus> ...
guard-seen <guard fpr 3> <number of times seen in a consensus> ...
guard-seen <guard fpr 4> <number of times seen in a consensus> ...
guard-seen <guard fpr 5> <number of times seen in a consensus> ...
...

comment:19 in reply to: ↑ 16 ; follow-up: Changed 8 months ago by asn

Replying to NickHopper:

Replying to asn:

Few questions that will need to be answered:

  • Will the script be called periodically and the authorities will have

to parse the output file every once in a while? Or will the script
be ran once, and then it's the job of the authorities to internally
update their state with new information?

I'm currently aiming for the former behavior, to minimize the amount
of code that needs to be written for little-t-tor. OTOH, this means
that authorities will need to keep 9 months worth of consensuses in
their filesystem. As we move closer to completion of this task we
will see if the former behavior is indeed better.

FWIW, I agree this is probably the right design, though parsing 9 months worth of consensuses with stem is no mean feat. An alternative would be to have the script keep a summary file that is updated as new consensuses are fetched; it might store, e.g. the number of consensuses a relay appeared in for each day, and then could get batch updated.

Some thoughts on how the script should be ran by Tor.

*Ideally*, the script should be ran every hour: everytime the Tor
authorities are making a vote. This means that the script should
be *quick*: Parsing 9 months worth of consensuses with stem takes
about 1.5 hours on a decent box, which makes it impossible to run
every hour.

To work around this, we might try to use some sort of "summary file"
that our script can keep updated with compact guard info about the
past months, so that it doesn't need to parse all those consensuses
every time.

Unfortunately, summary files are not trivial in our case:

a)

We are considering 9 *rolling* months of consensuses and we run the
script for every new consensus, this means that in every run we
need to subtract the data of the oldest consensus (the one from 9
months ago) since it has expired.

Hence the "summary file" can't be a simple summary of the past 9
months, because then we wouldn't know the exact values of the
oldest consensus (that we need to subtract from our summary since
newer observations took their place)

b)

Also, for every consensus (from the past 9 months), we need to keep
track of _all_ guards; not only the ones that were referenced in
recent consensuses. The reason for that, is that a guard might be
taking a break for 6 months and then suddenly reappear in the
consensus. If a guard's identity key has made an appearance in the
past 9 months, we should have its data.

With that in mind, here are some ideas on summary files:

  • We keep a summary file for every consensus.

The idea here is that our summary files will be much faster to parse
than full fledged consensuses. Ideally, the parsing time would be
reduced from 1.5 hours to a few seconds/minutes, but I'm not sure if
that's realistic.

To get an idea of the data size, for a 9 months period, we are
talking about 6480 summary files (consensuses) and about 2500 guards
per summary file.

This seems like the most easy to implement and understand scheme,
but I'm not sure if it will be efficient enough.

  • We try to be smarter with summary files.

For example, we could keep an 8-months summary file, and for the
oldest month (the one 9 months ago) we actually parse the
consensuses one-by-one, which allows us to know which consensus
to ignore in every run.

This idea seems like much harder engineering work: For example, in
the beginning of each month, we will need to use a directory with
consensuses for the new oldest month (since we no longer use a
summary file for it).

This plan seems doable but hefty engineering work, but it might give
us the results we want fast: an 8-months summary file should be easy
to parse, and 1 month of consensus should take about 10 minutes.

We can imagine optimizations where we keep weekly summary files for
the oldest month, etc.

I also wonder how much of a speed up (or is that only space
efficiency) we could gain by using some membership data structures
like bloom filters.

Also, the above ideas assume that we need to run the script (get
updated about guardiness data) for every new vote, which is the best
behavior. If we relax this requirement, and e.g. only run the script
every week, we could potentially just suck it and parse the
consensuses manually even if it takes 2 hours.

comment:20 in reply to: ↑ 19 Changed 8 months ago by asn

Replying to asn:

  • We keep a summary file for every consensus.

The idea here is that our summary files will be much faster to parse
than full fledged consensuses. Ideally, the parsing time would be
reduced from 1.5 hours to a few seconds/minutes, but I'm not sure if
that's realistic.

To get an idea of the data size, for a 9 months period, we are
talking about 6480 summary files (consensuses) and about 2500 guards
per summary file.

This seems like the most easy to implement and understand scheme,
but I'm not sure if it will be efficient enough.

I experimented a bit with this idea to see what's the speed improvement.

FWIW, my initial summary files map 1-1 to consensuses, and they look like this:

<summary file header>
<consensus valid-after time>
<guard fpr 1>
<guard fpr 2>
...

this is trivial to parse in Python.

So, for the measurements, I parsed 10 consensuses. When parsed normally, the time was:

real	0m13.193s
user	0m12.960s
sys	0m0.072s

When I preprocessed them to create summary files for each consensus, and then parsed the summary files, the time was:

real	0m0.776s
user	0m0.708s
sys	0m0.064s

This is a 17x improvement in time. This means that 9 months of consesuses that would originally be parsed in 2 hours, will take about 7 minutes when summary files are used.

UPDATE:
I also parsed 3 months of consensuses using summary files. Parsing 3 months of consensuses with stem takes about 35 minutes. When using summary files it took:

real	0m6.394s
user	0m6.188s
sys	0m0.208s

The preprocessing stage, which used stem, took about 32 mins for 1968 consensuses.

Last edited 8 months ago by asn (previous) (diff)

comment:21 Changed 8 months ago by asn

FWIW, my main fear with summary files is the extra file/directory management that is involved. For example, how to delete the old summary files, what to do with the preprocessed consensuses, etc.

And wrt file sizes, 3 months of microdescriptor consensuses are about 2.0GB. 3 months of summary files are about 170MB.

This is probably linear, so 9 months of md consensuses will be about 6GB, and the summary files will be about 0.5GB.

Last edited 8 months ago by asn (previous) (diff)

comment:22 follow-up: Changed 8 months ago by asn

OK, I have some ideas on how this might get deployed to directory authorities.

I now have two scripts: One script (summizer.py) summarizes consensuses into compact summary files, and the next script (guardiness.py) calculates the guardiness of nodes given a bunch of summary files. In the end, guardiness.py outputs a file with the guardiness information that is to be read by little-t-tor before forming a vote.

When a directory authority operator wants to start using the guardiness system (bootstrap), she makes a consensus directory and downloads 3 months worth of consensuses in there (probably from metrics). Then she runs the summizer.py script which reads the consensuses from that directory, and saves a summary file for each consensus in a separate summary file directory. This step is expected to take 30 minutes or so.

Then the dirauth operator will add a cron job, similar to the one for bw auths, that triggers in the 35th minute of each hour (or something). This cron job does the following:

  • Download latest consensus from metrics.
  • Run summizer.py to summarize the new consensus (This should be instant since its just one consensus).
  • Run guardiness.py 3 months to calculate guardiness of all summary files in the summary directory from the past 3 months (This will take between a few seconds to 2 minutes of intense computation).

Then 5 minutes before the hour, little-t-tor will read the guardiness output file and consider its data when voting.

Some notes:

  • Instead of downloading the latest consensus from metrics, maybe we could add little-t-tor code that would save new consensuses into a directory. This way, we don't need to download bulk from metrics, apart from during the bootstrap procedure.
  • To avoid keeping old summary/consensus files around that take over disk space, I added some optional cleanup switches to the scripts. Specifically, the summizer.py script can delete the consensus files that got summarized and can also delete consensus files older than 3 months (or N months). Similarly, the guardiness.py script can delete summary files older than 3 months (or N months). The idea is that every time the cron job triggers, the summizer.py and guardiness.py scripts will auto-delete the oldest summary/consensus file, keeping in disk only the useful files.

comment:23 in reply to: ↑ 22 Changed 8 months ago by nickm

Replying to asn:
[...]

Then 5 minutes before the hour, little-t-tor will read the guardiness output file and consider its data when voting.

This all seems plausible; can any dirauth ops comment on whether this is a reasonable thing to set up?

Some notes:

  • Instead of downloading the latest consensus from metrics, maybe we could add little-t-tor code that would save new consensuses into a directory. This way, we don't need to download bulk from metrics, apart from during the bootstrap procedure.

This seems plausible and not terribly hard. The only thing to deal with here would be getting rid of old files. (see below.)

I guess you could have a "KeepOldConsensuses 90 days" option along with "OldConsensusDir /var/xyzzy" that would store the last 90 days of consensuses in some directory of your choice.

  • To avoid keeping old summary/consensus files around that take over disk space, I added some optional cleanup switches to the scripts. Specifically, the summizer.py script can delete the consensus files that got summarized and can also delete consensus files older than 3 months (or N months). Similarly, the guardiness.py script can delete summary files older than 3 months (or N months). The idea is that every time the cron job triggers, the summizer.py and guardiness.py scripts will auto-delete the oldest summary/consensus file, keeping in disk only the useful files.

This also seems plausible. Except instead of deleting the oldest unconditionally, it's probably best for them to delete any consensus whose valid-until time is more than N days before the current time. That way, if you have to re-run them, or if you mess up mtimes on your disk, they don't wind up deleting things they shouldn't.

(Do you have more questions? If so, please make sure they end with a ? or I am likely not to realize that they are questions. :) )

comment:24 Changed 7 months ago by Sebastian

So, we just got rid of the naming thing because it was an extra thing to run, and only 2 out of 9 dirauth ops could be bothered to set it up. Similarly, only 5 of 9 can be bothered to set up bwauths. This makes me sad, but I worry about features like this that add extra code which doesn't get auto-installed with the dirauth. Maybe we need to kick our dirauth ops more, too - tho I tried that recently and it took a long time, too.

For the keeping around of consensuses and deletion stuff, mvdan has just written all of this inside Tor. Don't write it again, improve his stuff with options if you need :)

How much space are we talking about, btw? I would estimate around 10GB. I suppose that should be managable for all dirauths, but I don't know.

On another note, I'm not sure how valuable making the time you keep consensuses configurable would be - what are the dirauth interactions here if they have different timespans?

comment:25 Changed 7 months ago by Sebastian

Oh. Forgot to say something. The bwauth stuff I run is horribly unmaintained. How will we make sure this new thing won't be the same? It's problematic if feature completely vital to the Tor network are implemented outside of the Tor repository, where people take care of it.

That said, personally I would deem it acceptable and in line with my dirauth ops duties to run this.

comment:26 Changed 7 months ago by asn

FWIW, you can see my python script in the guardiness branch of https://git.torproject.org/user/asn/hax.git. You need stem to run it, some (incomplete) instructions can be found in the README.

comment:27 Changed 6 months ago by asn

  • Status changed from new to needs_review

I published an initial cleaned up version of my little-t-tor branch at bug9321_draft in https://git.torproject.org/user/asn/tor.git.

It has a few XXXs that I would like some feedback from reviewers. And I also need to tone down the logging severities; I'm currently using this branch in chutney and I'm looking at those logs.

Feedback is very welcome.

comment:28 follow-up: Changed 6 months ago by nickm

Notes on file format:

  • A bad line in the file should probably get ignored, not cause the whole file to be unparseable.
  • Errors while parsing the file should probably get reported by line number.
  • Right now, applying the file to your vote is O(file_size * log (n_elts_in_vote)). As the file gets bigger and bigger, this will take more and more time. I wonder whether it matters.

Notes on guardfraction voting:

  • Shouldn't we include GuardFraction in consensus votes for all nodes, regardless of whether we think they're a Guard? After all, other authorities might decide to vote on whether the node should be a Guard.
  • Why are guardfraction_percentage and its related flag duplicated in routerstatus_t and vote_routerstatus_t? Remember, vote_routerstatus_t contains a routerstatus_t.
  • In routerstatus_parse_guardfraction , I'd be more comfortable if we checked the return value of strchr.

Notes on bw calculation:

  • Maybe guard_get_guardfraction_bandwidth should fill in a structure rather than allocating one; it's going to get called a lot.

I need to go back and look at the bandwidth formulas; I didn't check them this time around.

On XXXs:

  • I don't think floor/ceiling matters.
  • It's okay not to assert for that invariant.
  • I don't know about applying guardfraction to weight_for_dir. Does that mean it would apply to choice of directory guards or not?
  • is_possible_guard is not quite equivalent to is_guard; what did you mean there?
  • IMO it's fine to ignore smartlist_choose_node_by_bandwidth for now.

Notes on tests:

  • test_helpers.h needs an #ifdef guard.

comment:29 in reply to: ↑ 28 Changed 5 months ago by asn

Replying to nickm:

Thanks for the review. I pushed some more commits that fix your comments.
Here are some comments on your comments comments:

Notes on file format:

  • A bad line in the file should probably get ignored, not cause the whole file to be unparseable.

Good point. Done.

I changed it so that errors in all lines will get ignored. However, the first header line (the one containing the date) needs to be correct. I don't see any reason for omitting that line in future versions of the script and it also allows us to detect expired guardfraction files (which in turn allows us to find bugs in the guardfraction script in dirauths)

To achieve this, I had to change the interface of the parsing function and its unittests.

  • Errors while parsing the file should probably get reported by line number.

Good point. Done.

  • Right now, applying the file to your vote is O(file_size * log (n_elts_in_vote)). As the file gets bigger and bigger, this will take more and more time. I wonder whether it matters.

Yes, I've been wondering about that too. It seems quite fast atm, and the file size should not increase very fast (except if 100k guards enter the Tor network). Let's leave it like this, and maybe optimize it in the future if there is a need to? (famous last words?)

Notes on guardfraction voting:

  • Shouldn't we include GuardFraction in consensus votes for all nodes, regardless of whether we think they're a Guard? After all, other authorities might decide to vote on whether the node should be a Guard.

Yes, you are very right. Thanks for catching this. Done.

This also kills some code, which is even better :)

  • Why are guardfraction_percentage and its related flag duplicated in routerstatus_t and vote_routerstatus_t? Remember, vote_routerstatus_t contains a routerstatus_t.

Hm, that's how the measured bw file parsing code worked, and I duplicated the logic.
In my new commits, I started using the routerstatus_t of the vote to save this info, and it seems to work fine in my Chutney network. I don't see any reason yet for this to be bad.

This makes the code cleaner.

  • In routerstatus_parse_guardfraction , I'd be more comfortable if we checked the return value of strchr.

Done.

Notes on bw calculation:

  • Maybe guard_get_guardfraction_bandwidth should fill in a structure rather than allocating one; it's going to get called a lot.

Good point. Done.

BTW, please check update_total_bandwidth_weights(). This function will be called for each router so it will be called a lot. For now, I placed the guardfraction_bandwidth_t in the stack even though the function will be called many times. I think that's better performance than mallocating it everytime it gets called (because it's just going to push the stack a few more bytes down in the function prologue). Is that right?

If not, I can pass the guardfraction_bandwidth_t as an argument to that function.

I need to go back and look at the bandwidth formulas; I didn't check them this time around.

On XXXs:

  • I don't think floor/ceiling matters.
  • It's okay not to assert for that invariant.

OK.

  • I don't know about applying guardfraction to weight_for_dir. Does that mean it would apply to choice of directory guards or not?

Yeah, I was a bit confused about this. Proposal 236 only suggested to use guardfraction info when picking middles/exits. However, I think considering guardfraction info for directory requests too is a good idea so that we load balance those as well.

As far as directory guards are concerned, since they are sharing the same list as the circuit guards, I suspect that most of the nodes in that list will have been picked by the circuit path selection algorithm, so it doesn't really matter. I think.

For now, I'm checking that rule != WEIGHT_FOR_GUARD which includes picks for middle/exit/directory and also NO_WEIGHTING which seems to be unused in the code.

  • is_possible_guard is not quite equivalent to is_guard; what did you mean there?

Hm, I wanted to assert that the node we are applying guardfraction info on is a guard. This should be true because routerstatus_parse_guardfraction() only sets guardfraction info to guards.

To do that, I would have to assert for is_guard in that function. However, is_guard = node->is_possible_guard which is fine in general, but it causes assert failures in directory authorities because the node_t is not initialized properly (#13297). Hence, I checked for node->rs->is_possible_guard which I think should be the same since the rs is assigned in nodelist_set_consensus() and then it does node->is_possible_guard = rs->is_possible_guard.

:/

  • IMO it's fine to ignore smartlist_choose_node_by_bandwidth for now.

OK.

Notes on tests:

  • test_helpers.h needs an #ifdef guard.

Done.

comment:30 follow-up: Changed 5 months ago by asn

Discussed this a bit more with Nick on IRC.

We want to add two more things:
a) Have a consensus parameter variable that turns on/off whether clients should look at guardfraction. We will start that as 'off' and turn it to 'on' when the code has been deployed to more clients.

b) Add a torrc option UseGuardFraction that can be on/off/auto. If it's auto, clients look at the consensus parameter. This will allow individual users to test the feature before we deploy it everywhere.

We are hoping for a merge during November or early/mid December.

comment:31 in reply to: ↑ 30 Changed 4 months ago by asn

Replying to asn:

Discussed this a bit more with Nick on IRC.

We want to add two more things:
a) Have a consensus parameter variable that turns on/off whether clients should look at guardfraction. We will start that as 'off' and turn it to 'on' when the code has been deployed to more clients.

b) Add a torrc option UseGuardFraction that can be on/off/auto. If it's auto, clients look at the consensus parameter. This will allow individual users to test the feature before we deploy it everywhere.

We are hoping for a merge during November or early/mid December.

OK. Please look at the bug9321_draft branch again. I implemented the above concepts and wrote some unittests. Please review :)

FWIW, if the UseGuardFraction consensus/torrc parameter is disabled, we are not going to apply any guardfraction information found in consensuses.

comment:32 Changed 3 months ago by teor

Review of git diff 390ec9154c58d6c7acaecd5e575adf575ab2f1fe^ asn/bug9321_draft by reading through the modified code:

Impacts on other changes

If dirserv_read_guardfraction_file can handle reading an empty (zero-length) file, and we merge #13111 in 0.2.6 as well, this code:

+      if (file_status(options->GuardfractionFile) != FN_FILE) {
+        REJECT("GuardfractionFile set but not a file? Failing");
+      }
+
+      dirserv_read_guardfraction_file(options->GuardfractionFile, NULL);

will need to be updated to:

+      if (file_status(options->GuardfractionFile) != FN_FILE && file_status(options->GuardfractionFile) != FN_EMPTY) {
+        REJECT("GuardfractionFile set but not a file? Failing");
+      }
+
+      dirserv_read_guardfraction_file(options->GuardfractionFile, NULL);

Or maybe we should just fail if the guardfraction file is truncated to zero-length?

Minor Picky Things

Log Severities:

I'd downgrade log_warn(LD_GENERAL, "%s: Guardfraction weight %f instead of %f (%s)", to a log_debug, given it may be called several thousand times.

Integer ranges:
I think this code could cause an integer overflow on insane inputs when SIZEOF_LONG == SIZEOF_INT:

version =
+        (unsigned int) tor_parse_long(line->value, 10, 0, UINT_MAX, &num_ok, NU
LL);

tor_parse_long function prototype is:

long
tor_parse_long(const char *s, int base, long min, long max,
               int *ok, char **next)

I suggest we use tor_parse_long(line->value, 10, 0, INT_MAX, ....

Capitalisation:

  • UseGuardFraction vs GuardfractionFile vs Guardfraction: in log messages
    • I suggest GuardFractionFile and GuardFraction: (all Fs capitalised), but I don't care much either way about Guard[Ff]raction:

comment:33 Changed 3 months ago by teor

When I merge with 0.2.6.2 master, I get the following conflict:

<<<<<<< HEAD
    uint32_t *bandwidths_kb = tor_calloc(smartlist_len(votes),
                                         sizeof(uint32_t));
    uint32_t *measured_bws_kb = tor_calloc(smartlist_len(votes),
                                           sizeof(uint32_t));
=======
    uint32_t *bandwidths_kb = tor_calloc(sizeof(uint32_t),
                                         smartlist_len(votes));
    uint32_t *measured_bws_kb = tor_calloc(sizeof(uint32_t),
                                           smartlist_len(votes));
    uint32_t *measured_guardfraction = tor_calloc(sizeof(uint32_t),
                                               smartlist_len(votes));
>>>>>>> asn/bug9321_draft

The tor_calloc_ prototype is:

void *
tor_calloc_(size_t nmemb, size_t size

We can resolve it by changing each tor_calloc call to use nmemb then size:

    uint32_t *bandwidths_kb = tor_calloc(smartlist_len(votes),
                                         sizeof(uint32_t));
    uint32_t *measured_bws_kb = tor_calloc(smartlist_len(votes),
                                           sizeof(uint32_t));
    uint32_t *measured_guardfraction = tor_calloc(smartlist_len(votes),
                                                  sizeof(uint32_t));

comment:34 follow-up: Changed 3 months ago by teor

I have the following unit tests fail on an OS X 10.9.5 i386 build, but not on the x86_64 build:

guardfraction/parse_guardfraction_file_bad: [forking] 
  FAIL src/test/test_guardfraction.c:116: assert(retval == 2): -1 vs 2
  [parse_guardfraction_file_bad FAILED]
guardfraction/parse_guardfraction_file_good: [forking] 
  FAIL src/test/test_guardfraction.c:218: assert(retval == 1): -1 vs 1
  [parse_guardfraction_file_good FAILED]

Anything in particular I should look for to diagnose, asn?

comment:35 Changed 3 months ago by teor

#13111 now has unit tests, so it's likely that the changes I mention above to dirserv_read_guardfraction_file in comment 32 will need to be made when we merge this branch in.

comment:36 in reply to: ↑ 34 Changed 2 months ago by asn

Replying to teor:

I have the following unit tests fail on an OS X 10.9.5 i386 build, but not on the x86_64 build:

guardfraction/parse_guardfraction_file_bad: [forking] 
  FAIL src/test/test_guardfraction.c:116: assert(retval == 2): -1 vs 2
  [parse_guardfraction_file_bad FAILED]
guardfraction/parse_guardfraction_file_good: [forking] 
  FAIL src/test/test_guardfraction.c:218: assert(retval == 1): -1 vs 1
  [parse_guardfraction_file_good FAILED]

Anything in particular I should look for to diagnose, asn?

Yes, it would be great if you could diagnose this.

What I would do is go to dirserv_read_guardfraction_file_from_str() and add some printf in the places where it can return -1. IIRC, that's all the places where goto done; is called. Then run the tests again, and see which printf triggers to see what causes the error.

IIRC, -1 can be returned if config_get_lines() fails, or if the date was wrong, or if the version was wrong. I'm wondering what's the case here for i386. (If the version check is wrong, then maybe you want to fix the overflow you mentioned above.)

Thanks!

Last edited 2 months ago by asn (previous) (diff)

comment:37 Changed 2 months ago by isis

  • Cc isis added

comment:38 Changed 2 months ago by nickm

  • Keywords unfrozen added

comment:39 Changed 8 weeks ago by asn

OK!

I addressed teor's comments, and rebased the branch to the latest master. You can find the new branch at bug9321_rebase in my repo. This is now ready for the final review.

I'm confident that the overflow that teor mentioned also fixes the unittest failure in 32-bit machines. David ran the tests in an i386 and they passed.

BTW, in this new branch I have rebased and squashed the various fix commits so that they look nicer and they are easier to review. If you still prefer the old commit format, check out bug9321_rebase2 which is only rebased and not squashed.

comment:40 Changed 8 weeks ago by nickm

  • Priority changed from normal to major

comment:41 Changed 7 weeks ago by nickm

  • Keywords nickm-review added

comment:42 Changed 7 weeks ago by asn

BTW, there is now this code in options_validate():

    /* same for guardfraction file */
    if (options->GuardfractionFile && !old_options) {
      file_status_t fs = file_status(options->GuardfractionFile);
      if (fs == FN_EMPTY) {
        REJECT("GuardfractionFile set but it's an empty file? Failing");
      } else if (fs != FN_FILE) {
        REJECT("GuardfractionFile set but not a file? Failing");
      }

      dirserv_read_guardfraction_file(options->GuardfractionFile, NULL);
    }
  }

Nick, do you think we should be less strict and not REJECT if we can't find the file?
We could just issue a warning and proceed with our business, without considering guard fraction at all.

This seems to be the behavior of the V3BandwidthsFile option, and it might be better because Tor won't refuse to start if the guardfraction script is misbehaving and doesn't output a file.

comment:43 follow-up: Changed 7 weeks ago by nickm

Sure, that behavior (warn and continue) seems fine.

comment:44 in reply to: ↑ 43 Changed 7 weeks ago by asn

Replying to nickm:

Sure, that behavior (warn and continue) seems fine.

ACK. Implemented and pushed in bug9321_rebase.
I also tested it and it seems to work.

comment:45 follow-up: Changed 6 weeks ago by teor

Apologies for my absence - life has been very chaotic for a few weeks.

Reviewing asn/bug9321_rebase:
Merging with b101f4e98ce811aee729c31f62ec5dd1cfe44e85 from tor git

CONFLICT (content): Merge conflict in src/or/dirvote.h

Resolved conflict by including both #defines:

<<<<<<< HEAD
/** Lowest consensus method where we include "package" lines*/
#define MIN_METHOD_FOR_PACKAGE_LINES 19
=======
/** Lowest consensus method where authorities may include
 * GuardFraction information in microdescriptors. */
#define MIN_METHOD_FOR_GUARDFRACTION 19
>>>>>>> asn/bug9321_rebase

Is this the right approach?
(Running tests now...)

comment:46 in reply to: ↑ 45 Changed 6 weeks ago by asn

Replying to teor:

Apologies for my absence - life has been very chaotic for a few weeks.

Reviewing asn/bug9321_rebase:
Merging with b101f4e98ce811aee729c31f62ec5dd1cfe44e85 from tor git

CONFLICT (content): Merge conflict in src/or/dirvote.h

Resolved conflict by including both #defines:

<<<<<<< HEAD
/** Lowest consensus method where we include "package" lines*/
#define MIN_METHOD_FOR_PACKAGE_LINES 19
=======
/** Lowest consensus method where authorities may include
 * GuardFraction information in microdescriptors. */
#define MIN_METHOD_FOR_GUARDFRACTION 19
>>>>>>> asn/bug9321_rebase

Is this the right approach?
(Running tests now...

Oh more conflicts...

The correct approach here I think is to bump the MIN_METHOD_FOR_GUARDFRACTION to 20, so that they don't conflict.

comment:47 Changed 6 weeks ago by teor

I left out the context of the conflict, the correct bump is 21:

/** Lowest consensus method where we include "package" lines*/
#define MIN_METHOD_FOR_PACKAGE_LINES 19

/** Default bandwidth to clip unmeasured bandwidths to using method >=
 * MIN_METHOD_TO_CLIP_UNMEASURED_BW */
#define DEFAULT_MAX_UNMEASURED_BW_KB 20

/** Lowest consensus method where authorities may include
 * GuardFraction information in microdescriptors. */
#define MIN_METHOD_FOR_GUARDFRACTION 21

comment:48 Changed 6 weeks ago by teor

Unit tests have run fine for me on several variations of configure options on OS X 10.10.2 i386 (and x86_64).

As far as I can tell, it was the overflow that was causing unit test failures for me on i386.
This may be because I build with clang's undefined behavior sanitizer on.
(It makes life more interesting...)

comment:49 Changed 5 weeks ago by nickm

8f4563048534cddcc67e34de76a3935dfdaaf9c6

  • document in guardfraction_line_apply that vote_routerstatuses must be sorted.

ef3bec7f62c901ec62445703a16177b49df397e1

  • enougn -> enough

7b6eed0320b4955d9b252adb2833c7cbabf6523a

  • This is going to sound a bit silly, but I think that we should be using lround rather than cast-to-int to convert the float to int in guard_get_guardfraction_bandwidth, and we should be using subtraction to get non_guard_bw, so that non_guard_bw + guard_bw == orig_bandwidth

769246b014f98b146a636acd06febced1fc72940

  • In update_total_bandwidth_weights(), I am not 100% sure that the comment matches the code. Are you? For example, I don't see anything in the comment about *M += default_bandwidth.

2eaa9b7c778d8314dbe341b56da67f9a641908ee:

  • An empty or missing file should not keep us from checking the file again later, shoult it?

comment:50 Changed 5 weeks ago by nickm

961caad304b752bbe659bd3b4f751a62b6b4094b:

  • It's a little weird that should_apply_guardfraction() applies changes only when we next parse the networkstatus, but that probably won't hurt anything, right?

comment:51 Changed 5 weeks ago by nickm

I've addressed all comments except for the one pertaining to 769246b014 and the one pertaining to 961caad in my branch "bug931_rebase_nm" in my public repository. Needs review.

comment:52 follow-up: Changed 5 weeks ago by asn

OK, please check the bug9321_rebase branch again. I improved the comment wrt the total bandwidth weights. Hopefully the situation is more clear now.

Your comment:

It's a little weird that should_apply_guardfraction() applies changes only when we next parse the networkstatus, but that probably won't hurt anything, right? 

is interesting. You mean that because we call should_apply_guardfraction() during consensus parsing, networkstatus_get_param() will actually check the previous consensus and not the one we are currently parsing, right? That's true.

I don't think it's tera-bad, except if we plan to be toggling the UseGuardFraction consensus parameter frequently. Under normal circumstances, it will delay the effect of UseGuardFraction by one hour.

However, I understand that it's wrong behavior and it should be fixed. I can see two ways here:

We can try to pass the consensus that is currently getting parsed to should_apply_guardfraction(). This might be OK even though that networstatus_t is not completely populated, since in networkstatus_parse_vote_from_string() we set net_params before we call routerstatus_parse_entry_from_string().

The other way would be to pass the net_params smartlist to the should_apply_guardfraction() function and let it use the smartlist directly instead of calling networkstatus_get_param(). This is more messy and I don't like it.

comment:53 in reply to: ↑ 52 ; follow-up: Changed 5 weeks ago by nickm

Replying to asn:

OK, please check the bug9321_rebase branch again. I improved the comment wrt the total bandwidth weights. Hopefully the situation is more clear now.

Your comment:

It's a little weird that should_apply_guardfraction() applies changes only when we next parse the networkstatus, but that probably won't hurt anything, right? 

is interesting. You mean that because we call should_apply_guardfraction() during consensus parsing, networkstatus_get_param() will actually check the previous consensus and not the one we are currently parsing, right? That's true.

I don't think it's tera-bad, except if we plan to be toggling the UseGuardFraction consensus parameter frequently. Under normal circumstances, it will delay the effect of UseGuardFraction by one hour.

I agree that it is wrong but not so bad. Either approach is fine, though the former needs lots of documentation so that the relevant functions are explicit that they accept a partially constructd consensus.

Could you please make a new ticket for this, targeting 0.2.7? I'm going to merge what's here now and close.

comment:54 Changed 5 weeks ago by nickm

  • Resolution set to implemented
  • Status changed from needs_review to closed

merged; please make a new ticket for the should_apply_guardfraction() issue?

comment:55 in reply to: ↑ 53 Changed 5 weeks ago by asn

Replying to nickm:

Replying to asn:

OK, please check the bug9321_rebase branch again. I improved the comment wrt the total bandwidth weights. Hopefully the situation is more clear now.

Your comment:

It's a little weird that should_apply_guardfraction() applies changes only when we next parse the networkstatus, but that probably won't hurt anything, right? 

is interesting. You mean that because we call should_apply_guardfraction() during consensus parsing, networkstatus_get_param() will actually check the previous consensus and not the one we are currently parsing, right? That's true.

I don't think it's tera-bad, except if we plan to be toggling the UseGuardFraction consensus parameter frequently. Under normal circumstances, it will delay the effect of UseGuardFraction by one hour.

I agree that it is wrong but not so bad. Either approach is fine, though the former needs lots of documentation so that the relevant functions are explicit that they accept a partially constructd consensus.

Could you please make a new ticket for this, targeting 0.2.7? I'm going to merge what's here now and close.

Thanks for the merge.

Opened ticket at #14957.

Note: See TracTickets for help on using tickets.