Opened 8 years ago

Closed 8 years ago

Last modified 6 years ago

#3630 closed task (implemented)

Reduce token bucket refill interval

Reported by: Flo Owned by:
Priority: High Milestone:
Component: Core Tor/Tor Version:
Severity: Keywords: performance flowcontrol tor-relay
Cc: scheuermann@… Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

With respect to ticket #2536 (Disable outgoing token bucket...) and in order to meet Nick's suggestion to split up the original proposal, this new ticket deals with the token bucket refill intervals only.

In particular we propose to reduce the refill intervals (see attached proposal).

To some extent the implementation of an additional parameter that sets the refill intervals has already been reviewed by Karsten and Sebastian. I attached a patch that is based on Tor's git repository (commit e98e1c836106b325aeeb9977a657ef98739ffff1) as basis for discussion.


Child Tickets

Attachments (3)

xxx-refillintervals.txt (4.4 KB) - added by Flo 8 years ago.
Proposal for reduced refill intervals
refill.patch (14.2 KB) - added by Flo 8 years ago.
Patch for a new parameter 'TokenBucketRefillInterval'
refill-revised-001.patch (14.5 KB) - added by Flo 8 years ago.
revised refill patch

Download all attachments as: .zip

Change History (26)

Changed 8 years ago by Flo

Attachment: xxx-refillintervals.txt added

Proposal for reduced refill intervals

Changed 8 years ago by Flo

Attachment: refill.patch added

Patch for a new parameter 'TokenBucketRefillInterval'

comment:1 Changed 8 years ago by Flo

Type: defectenhancement

comment:2 Changed 8 years ago by arma

Profiling fast Tor relays in the past showed that they spent 5-10% of their cpu time refilling buckets.

If we refill buckets 100 times as often, will we spend 90% of our cpu time refilling buckets?

Also, are we removing any realistic chance that we would flush more than one cell at once? If MTUs are often 1500, sending a second cell could be much cheaper than the earlier analysis implies.

That's not to mean we shouldn't make a change like this. But it would be great to better understand what results we expect to see, so we can check to make sure that we actually see them.

comment:3 in reply to:  2 ; Changed 8 years ago by Bjoern

Thanks for the comments.

Replying to arma:

Profiling fast Tor relays in the past showed that they spent 5-10% of their cpu time refilling buckets.
If we refill buckets 100 times as often, will we spend 90% of our cpu time refilling buckets?

We implemented this, played a lot with different refill intervals, and explicitly assessed the CPU load on our own relay. We didn't notice any impact on the server load. (And after all, why should there be any? Refilling buckets is a trivially simple operation...)

That doesn't mean that it wouldn't be worth looking at this again - do you have a pointer to the results that you mention?

Also, are we removing any realistic chance that we would flush more than one cell at once? If MTUs are often 1500, sending a second cell could be much cheaper than the earlier analysis implies.

Apparently you are implying that everything flushed to a TCP socket will immediately be sent. This is, in general, not the case, as TCP's congestion and flow control comes into play (as well as the queue management algorithms of the specific TCP implementation). As soon as the network path capacity is (nearly) used, a queue will build up at the TCP layer and the problem will solve itselve, as TCP will then have enough data in its queue to build large segments. If the capacity is not used - well, there's no problem in this case.

In any case, today's TCP implementations are quite clever about building suitable segments. There's no need for us to mess with that.

Again, though, we could do a practice check and see whether we see significant differences in the sizes of the TCP segments that an onion router generates if we reduce the refill interval.

That's not to mean we shouldn't make a change like this. But it would be great to better understand what results we expect to see, so we can check to make sure that we actually see them.

I think we already made quite some progress in that direction, in the context of ticket #2536 (where this one here is coming from). We built a simulation model of Tor and ran network simulations (with ns-3), we performed real-world lab measurements in the context of TCP behavior in an onion routing setting, and we also did real-world measurements on an active onion router with various changes in the context of cell queueing and bandwidth management.

Nevertheless, we'll definitely look at the points that you raise once again. To this end, a pointer to the profiling results that you mention would really be very helpful (because they appear to heavily contradict our own results).

Thanks again!

comment:4 Changed 8 years ago by nickm

Milestone: Tor: 0.2.3.x-final
Status: newneeds_review

comment:5 in reply to:  3 ; Changed 8 years ago by nickm

Replying to Bjoern:

Thanks for the comments.

Replying to arma:

Profiling fast Tor relays in the past showed that they spent 5-10% of their cpu time refilling buckets.
If we refill buckets 100 times as often, will we spend 90% of our cpu time refilling buckets?

We implemented this, played a lot with different refill intervals, and explicitly assessed the CPU load on our own relay. We didn't notice any impact on the server load. (And after all, why should there be any? Refilling buckets is a trivially simple operation...)

How much bandwidth was the relay pushing?

comment:6 in reply to:  5 ; Changed 8 years ago by Bjoern

We implemented this, played a lot with different refill intervals, and explicitly assessed the CPU load on our own relay. We didn't notice any impact on the server load. (And after all, why should there be any? Refilling buckets is a trivially simple operation...)

How much bandwidth was the relay pushing?

The configured bandwidth limit should have been around 2 MBit at that time. Maybe Flo knows more?

In any case, as I wrote before: it is worth looking into this again. But refilling buckets is trivial, so if it really turns out that lots of CPU time go into that, this can only be a problem with a non-optimal implementation, and not a fundamental issue.

comment:7 in reply to:  6 Changed 8 years ago by Flo

Replying to Bjoern:

We implemented this, played a lot with different refill intervals, and explicitly assessed the CPU load on our own relay. We didn't notice any impact on the server load. (And after all, why should there be any? Refilling buckets is a trivially simple operation...)

How much bandwidth was the relay pushing?

The configured bandwidth limit should have been around 2 MBit at that time. Maybe Flo knows more?

We did measurments on our onion router which was configured with 1MBit. For refill intervals of 100ms, 10ms and 1ms, we observed that Tor's process takes about 5-6% of cpu, independent from the configured refill interval.

comment:8 Changed 8 years ago by nickm

Priority: normalmajor

Reading through the patch, it looks mostly good. There's some stuff that should get fixed up (either you could do that or I could get to it eventually), and a few bigger issues to think about.

Big stuff the needs to get fixed pre-merge:

  • The round-offs with the division when doing refills seem pretty broken. Consider that most of of the calculations for "bandwidthrate" make a new "rate per millisecond" by calculating rate / 1000. This means that the real rate of bytes per second you'll see is not the rate you configured, but 'rate - (rate % 1000)'.
  • By specification, controller bandwidth events must be sent at about a once/second rate. We shouldn't be flooding them at the refill interval rate, as this patch makes us do when running in non-bufferevent mode.

Answers to questions:

  • Libevent doesn't currently launch any callbacks in parallel. If it gains the ability to do so in the future, it won't do so by default unless it is told to do so.
  • The right way to find out the time in a timer callback is not gettimeofday() [windows doesn't have that]. Nor does it involve looking at periodic_timer_t.tv: that's only present when we're building with Libevent versions before 2.0. Instead, either use tor_gettimeofday() or event_base_gettimeofday_cached(), depending on how much accuracy you need.

Smaller stuff, easier to fix:

  • The configuration should probably disallow any refill interval of greater than 1000 msec.

Stuff I don't understand:

  • What is going on with the revised burst calculations? It seems to be that the burst should remain unchanged: it is the maximum number of bytes in the bucked, regardless of how often the bucked refills. Yet lots of places in the new connection.c do something like "burst = configured_burst / 1000 * RefillInterval".

Stuff that can get fixed after the merge:

  • Whatever this option is, it should apply to bufferevents as well as older token buckets.

comment:9 in reply to:  8 Changed 8 years ago by Flo

Replying to nickm:

  • The round-offs with the division when doing refills seem pretty broken. Consider that most of of the calculations for "bandwidthrate" make a new "rate per millisecond" by calculating rate / 1000. This means that the real rate of bytes per second you'll see is not the rate you configured, but 'rate - (rate % 1000)'.

I definitly see your point. My pragmatic approach to solve this issue would be to restrict precision in which users can specify the rate and burst parameter to a magnitude of kilobytes. By doing so we avoid round-offs in the calculations because in this case rate % 1000 = 0. In my opinion a higher precision than kilobyte doesn't make sense to me anyway. Does this sound feasible to you?

  • By specification, controller bandwidth events must be sent at about a once/second rate. We shouldn't be flooding them at the refill interval rate, as this patch makes us do when running in non-bufferevent mode.

If I got you right, you would like to see control_event_bandwidth_used() and control_event_stream_bandwidth_used() also decoupled from the refill_callback. Consider it as done.

  • The right way to find out the time in a timer callback is not gettimeofday() [windows doesn't have that]. Nor does it involve looking at periodic_timer_t.tv: that's only present when we're building with Libevent versions before 2.0. Instead, either use tor_gettimeofday() or event_base_gettimeofday_cached(), depending on how much accuracy you need.

I changed it to tor_gettimeofday() as suggested.

  • The configuration should probably disallow any refill interval of greater than 1000 msec.

Done.

  • What is going on with the revised burst calculations? It seems to be that the burst should remain unchanged: it is the maximum number of bytes in the bucked, regardless of how often the bucked refills. Yet lots of places in the new connection.c do something like "burst = configured_burst / 1000 * RefillInterval".

You are absolutely right. Changed that too.

I added an revised version of the patch to this ticket, which considers your comments. Just let me know about the round-offs and I will change that too.

Changed 8 years ago by Flo

Attachment: refill-revised-001.patch added

revised refill patch

comment:10 Changed 8 years ago by nickm

Okay, moving forward!

The check in options_act() should probably move to options_validate(): That way, we can reject attempts to change TokenBucketRefillInterval to something unacceptable. Also, the check doesn't match the manpage, which says it must be a divisor or multiple of 1 second. Easy enough to fix.

The floor for TokenBucketRefillInterval should probably be 1, not 0. (What would a refill interval of 0 mean, anyway?)

I definitly see your point. My pragmatic approach to solve this issue would be to restrict precision in which users can specify the rate and burst parameter to a magnitude of kilobytes. By doing so we avoid round-offs in the calculations because in this case rate % 1000 = 0. In my opinion a higher precision than kilobyte doesn't make sense to me anyway. Does this sound feasible to you?

I think so. My personal preference would be to instead have rate be tracked in in terms of "bytes per tick", where tokenbucketrefillinterval is defined to be one tick.

This all looks fixable; I'll start working on a branch here.

comment:11 Changed 8 years ago by nickm

Okay, please have a close look at branch feature3630 in my public repository (https://gitweb.torproject.org/nickm/tor.git).

First, be sure to sanity-check my application of your patch: it had conflicts with the master branch, and I needed to apply part of it manually.

I also fixed the issues mentioned in the commit above, and made it work with bufferevents.

If it looks good, let's rebase it (to handle the autosquash stuff) and merge it.

comment:12 in reply to:  11 Changed 8 years ago by Flo

Replying to nickm:

Okay, please have a close look at branch feature3630 in my public repository (https://gitweb.torproject.org/nickm/tor.git).

First, be sure to sanity-check my application of your patch: it had conflicts with the master branch, and I needed to apply part of it manually.

I also fixed the issues mentioned in the commit above, and made it work with bufferevents.

If it looks good, let's rebase it (to handle the autosquash stuff) and merge it.

Thanks for fixing and resolving conflicts. The patch looks great.
Hence, thumbs up from my side.

comment:13 Changed 8 years ago by karsten

Patch looks good. I didn't compile or test anything, but I read the code. Here are a few comments:

  • The documentation of connection_bucket_refill_helper in connection.c says the burst value is measured per refill interval, but connection_bucket_refill passes the value from options->BandwidthBurst which is still per second. Are we sure we're using the right burst value?
  • There's a copy-paste error in the calls of connection_bucket_refill_helper where one of the "global_read_bucket"s should be "global_write_bucket".
  • The documentation in or.h says that TokenBucketRefillInterval is ignored when bufferevents are enabled. This isn't the case anymore, right?

comment:14 in reply to:  13 ; Changed 8 years ago by nickm

Replying to karsten:

Patch looks good. I didn't compile or test anything, but I read the code. Here are a few comments:

  • The documentation of connection_bucket_refill_helper in connection.c says the burst value is measured per refill interval, but connection_bucket_refill passes the value from options->BandwidthBurst which is still per second. Are we sure we're using the right burst value?

Ah; that comment was wrong. Fixing.

There is *no such thing* as a "burst per second" or "burst per millisecond" or "burst per anything." In a leaky-bucket rate limiting system, the "rate" is the rate at which the bucket fills up, and the "burst" is the maximum size of the bucket. The units for rate are data-amount per time, but the units for burst are just in data-amount.

  • There's a copy-paste error in the calls of connection_bucket_refill_helper where one of the "global_read_bucket"s should be "global_write_bucket".

Fixed

  • The documentation in or.h says that TokenBucketRefillInterval is ignored when bufferevents are enabled. This isn't the case anymore, right?

Fixed.

I'm going to commit a change for those on feature3630, then rebase into a feature3630-rebased branch, and then merge that in a bit. Thanks for the review!

comment:15 in reply to:  14 Changed 8 years ago by arma

Replying to nickm:

I'm going to commit a change for those on feature3630, then rebase into a feature3630-rebased branch, and then merge that in a bit. Thanks for the review!

I looked over the rebased branch. Looks fine. I'm eager to find out if it works. :)

While looking at it, I opened #4085 (mostly unrelated) and #4086 ("use experimentor/shadow to learn whether this feature works as expected and if we picked a good config value").

comment:16 Changed 8 years ago by nickm

Resolution: implemented
Status: needs_reviewclosed

As a bare minimum, we should watch bandwidth and CPU load on a busy server once this is merged, so that we can learn whether we picked a really bad configuration value.

Merging. Thanks, everybody!

comment:17 Changed 7 years ago by arma

Keywords: performance added

comment:18 Changed 7 years ago by arma

Keywords: flowcontrol added

comment:19 Changed 7 years ago by karsten

Milestone: Tor: 0.2.3.x-finalSponsor F: March 15, 2012
Type: enhancementproject

Making this the new project ticket for Sponsor F: March 15, 2012 task 1, because it more accurately reflects the deliverable.

comment:20 Changed 7 years ago by karsten

Keywords: SponsorF20120315 added
Milestone: Sponsor F: March 15, 2012

Switching from using milestones to keywords for sponsor deliverables. See #6365 for details.

comment:21 Changed 7 years ago by karsten

Keywords: SponsorF20120315 removed
Type: projecttask

Roger told me at the Florence hackfest that this ticket technically counts as completing deliverable 1 of sponsor F year 2, but that we should aim for completing #4465, too. Removing the sponsor keyword.

comment:22 Changed 6 years ago by nickm

Keywords: tor-relay added

comment:23 Changed 6 years ago by nickm

Component: Tor RelayTor
Note: See TracTickets for help on using tickets.