Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: runtime: smarter scavenging #30333

Open
mknyszek opened this Issue Feb 20, 2019 · 9 comments

Comments

Projects
None yet
3 participants
@mknyszek
Copy link
Contributor

mknyszek commented Feb 20, 2019

Proposal: Smarter Scavenging

Motivation & Purpose

Out-of-memory errors (OOMs) have been a pain-point for Go applications. A class of these errors come from the same underlying cause: a temporary spike in memory causes the Go runtime to grow the heap, but it takes a very long time (on the order of minutes) to return that unneeded memory back to the system. The system can end up killing the application in many situations, such as if the system has no swap space or if system monitors count this space against your application. In addition, if this additional space is counted against your application, you end up paying more for memory when you don’t really need it.

The Go runtime does have internal mechanisms to help deal with this, but they don’t react to changes in the application promptly enough. The way users solve this problem today is through a runtime library function called debug.FreeOSMemory. debug.FreeOSMemory performs a GC and subsequently returns all unallocated memory back to the underlying system. However, this solution is very heavyweight:

  • Returning all free memory back to the underlying system at once is expensive, and can lead to latency spikes as it holds the heap lock through the whole process.
  • It’s an invasive solution: you need to modify your code to call it when you need it.
  • Reusing free chunks of memory becomes more expensive. On UNIX-y systems that means an extra page fault (which is surprisingly expensive on some systems).

I believe the Go runtime should do better here by default, so that for most cases the scavenger is prompt enough and debug.FreeOSMemory is unnecessary.

See #16930 and #14045.

Background

Scavenging

Dynamic memory allocators typically obtain memory from the operating system by requesting for it to be mapped into their virtual address space. Sometimes this space ends up unused, and modern operating systems provide a way to tell the OS that certain virtual memory address regions won’t be used without unmapping them. This means the physical memory backing those regions may be taken back by the OS and used elsewhere. We in the Go runtime refer to this technique as “scavenging”.

Scavenging is especially useful in dealing with page-level external fragmentation, since we can give these fragments back to the OS, reducing the process’ resident set size (RSS). That is, the amount of memory that is backed by physical memory in the application’s address space.

Go 1.11

As of Go 1.11, the only scavenging process in the Go runtime was a periodic scavenger which runs every 2.5 minutes. This scavenger combs over all the free spans in the heap and scavenge them if they have been unused for at least 5 minutes. When the runtime coalesced spans, it would track how much of the new span was scavenged.

While this simple technique is surprisingly effective for long-running applications, the peak RSS of an application can end up wildly exaggerated in many circumstances, even though the application’s peak in-use memory is significantly smaller. The periodic scavenger just does not react quickly enough to changes in the application’s memory usage.

Go 1.12

As of Go 1.12, in addition to the periodic scavenger, the Go runtime also performs heap-growth scavenging. On each heap growth up to N bytes of the largest spans are scavenged, where N is the amount of bytes the heap grew by. The idea here is to “pay back” the cost of a heap growth. This technique helped to reduce the peak RSS of some applications (#14045).

Goals

The goal in scavenging smarter is two-fold:

  • Reduce the average and peak RSS of Go applications.
  • Minimize the CPU impact of keeping the RSS low.

The two goals go hand-in-hand. On the one hand, you want to keep the RSS of the application as close to its in-use memory usage as possible. On the other hand, doing so is expensive in terms of CPU time, having to make syscalls and handle page faults. If we’re too aggressive and scavenge every free space we have, then on every span allocation we effectively incur a hard page fault (or invoke a syscall), and we’re calling a syscall on every span free.

The ideal scenario, in my view, is that the RSS of the application “tracks” the peak in-use memory over time.

  • We should keep the RSS close to the actual in-use heap, but leave enough of a buffer such that the application has a pool of unscavenged memory to allocate from.
  • We should try to smooth over fast and transient changes in heap size.

The goal of this proposal is to improve the Go runtime’s scavenging mechanisms such that it exhibits the behavior described. Compared with today’s implementation, this behavior should reduce the average overall RSS of most Go applications with minimal impact on performance.

Proposal

Three questions represent the key policy decisions that describe a memory scavenging system.

  1. At what rate is memory scavenged?
  2. How much memory should we retain (not scavenge)?
  3. Which memory should we scavenge?

I propose that for the Go runtime, we:

  1. Scavenge at a rate proportional to the rate at which the application is allocating memory, in the same vein as proportional sweeping.
  2. Retain some constant times the peak heap goal over the last N GCs (same as #16930).
  3. Scavenge the unscavenged spans with the highest base addresses first.

Additionally, I propose we change the span allocation policy to prefer unscavenged spans over scavenged spans, and to be first-fit rather than best-fit.

A brief rationale is that:

  1. We get guarantees about when memory will get scavenged, and spread the expense of scavenging operations across a GC cycle, to avoid latency spikes.
  2. By retaining the max heap goal over N GCs we can smooth out latency spikes. Retaining a constant times that gives us the overhead to avoid page faults.
  3. Best-fit allocation is difficult to glean any trends out of. On the other hand, first-fit allocation trivially prefers lower address. First-fit allocation policies tend to perform just as well as best-fit allocation, and can be implemented efficiently. By picking higher addresses first with a first-fit scavenging policy, we're scavenging memory that is less likely to be used.

Detailed rationale and design available very soon.

@mknyszek mknyszek self-assigned this Feb 20, 2019

@gopherbot gopherbot added this to the Proposal milestone Feb 20, 2019

@gopherbot gopherbot added the Proposal label Feb 20, 2019

@gopherbot

This comment has been minimized.

Copy link

gopherbot commented Feb 20, 2019

Change https://golang.org/cl/163217 mentions this issue: design: add 30333-smarter-scavenging

@aclements

This comment has been minimized.

Copy link
Member

aclements commented Feb 21, 2019

Thus, I propose the following heuristic, borrowed from #16930: retain C*max(heap goal, max(heap goal over the last N GCs))

What happens in an application that has a huge heap spike (say, an initial loading phase) and then the heap drops significantly? In particular, let's say this is drastic enough that the runtime doesn't even notice the drop until a 2 minute GC kicks in. At that scale, it could take a while for N GCs to pass, and we won't reclaim the heap spike until they do.

One issue with this design is situations where the application goes idle. In that case, the scavenger will do at least one unit of work (scavenge one span) on wake-up to ensure it makes progress as long as there's work to be done.

I wonder if it makes sense to pace this to periodic GC. E.g., pace scavenging to the max of the heap growth and the two minute delay before the periodic GC..

The additional scavenging during allocation could prove expensive, given the costs associated with the madvise syscall. I believe we can dramatically reduce the amount of times this is necessary by reusing unscavenged memory before scavenged memory when allocating. Thus, where currently we try to find the best-fit span across both scavenged and unscavenged spans, I propose we prefer unscavenged to scavenged spans during allocation.

If we're switching to first-fit and scavenging from higher addresses, do we also need to prefer unscavenged spans during allocation?

@mknyszek

This comment has been minimized.

Copy link
Contributor Author

mknyszek commented Feb 21, 2019

Thus, I propose the following heuristic, borrowed from #16930: retain C*max(heap goal, max(heap goal over the last N GCs))

What happens in an application that has a huge heap spike (say, an initial loading phase) and then the heap drops significantly? In particular, let's say this is drastic enough that the runtime doesn't even notice the drop until a 2 minute GC kicks in. At that scale, it could take a while for N GCs to pass, and we won't reclaim the heap spike until they do.

This is something that came to my mind recently too. An alternative is to set a schedule to decrease the scavenge goal linearly, or according to a smoothstep function, which goes to zero over N GCs. If this schedule ever gets below C * the heap goal, we use that instead. We'll get smoother cliffs in general and still make progress in the case you describe. Smoothstep is preferred here since we won't over-fit to transient drops in heap size, but this also means we might be slower to react in the case you described. I prefer not to over-fit here because that carries a performance cost.

One issue with this design is situations where the application goes idle. In that case, the scavenger will do at least one unit of work (scavenge one span) on wake-up to ensure it makes progress as long as there's work to be done.

I wonder if it makes sense to pace this to periodic GC. E.g., pace scavenging to the max of the heap growth and the two minute delay before the periodic GC..

That makes a lot of sense to me, and I think this is the right call. Thanks!

The additional scavenging during allocation could prove expensive, given the costs associated with the madvise syscall. I believe we can dramatically reduce the amount of times this is necessary by reusing unscavenged memory before scavenged memory when allocating. Thus, where currently we try to find the best-fit span across both scavenged and unscavenged spans, I propose we prefer unscavenged to scavenged spans during allocation.

If we're switching to first-fit and scavenging from higher addresses, do we also need to prefer unscavenged spans during allocation?

There's a trade-off here: by preferring unscavenged spans we're cementing that we want to avoid page faults at all cost. By not preferring them, we may end up getting overall better cache locality ("first-fit at all costs") but we could incur more page faults. Given that the policy already works to our advantage it's hard to say what works better in practice. I'm trying to avoid additional syscalls and page faults to perhaps an excessive degree at this point, but in practice I hypothesize the performance would be similar either way.

Maybe only one thing has me leaning toward preferring unscavenged spans: the implementation for that is definitely simpler. While it's not much code, I definitely got global best-fit wrong a couple times. :) But if there's another reason to do a global first-fit allocation policy that I'm not seeing (perhaps stability of the policy?), I don't feel too strongly about this.

gopherbot pushed a commit to golang/proposal that referenced this issue Feb 25, 2019

design: add 30333-smarter-scavenging
This change adds a design document/proposal for improving the
scavenging mechanisms in the Go runtime.

For golang/go#30333.

Change-Id: I2dc2cad8d5585347574f893ace970523e9889a72
Reviewed-on: https://go-review.googlesource.com/c/163217
Reviewed-by: Austin Clements <austin@google.com>
@gopherbot

This comment has been minimized.

Copy link

gopherbot commented Feb 27, 2019

Change https://golang.org/cl/143157 mentions this issue: runtime: remove periodic scavenging

@gopherbot

This comment has been minimized.

Copy link

gopherbot commented Feb 27, 2019

Change https://golang.org/cl/142960 mentions this issue: runtime: add proportional background scavenger

@gopherbot

This comment has been minimized.

Copy link

gopherbot commented Feb 27, 2019

Change https://golang.org/cl/164099 mentions this issue: runtime: prefer unscavenged spans over scavenged spans

@gopherbot

This comment has been minimized.

Copy link

gopherbot commented Feb 27, 2019

Change https://golang.org/cl/164100 mentions this issue: runtime: add tests for runtime mTreap

@gopherbot

This comment has been minimized.

Copy link

gopherbot commented Feb 27, 2019

Change https://golang.org/cl/164101 mentions this issue: runtime: change the span allocation policy to first-fit

@gopherbot

This comment has been minimized.

Copy link

gopherbot commented Feb 27, 2019

Change https://golang.org/cl/142959 mentions this issue: runtime: track the last 16 heap goals

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.