Spotting and avoiding heap fragmentation in Rust applications • Hacker News Board

Re: Spotting and avoiding heap fragmentation in Rust applications

#31

Post by scottlamb » Thu, Apr 06, 2023, 8:23 PM UTC

mcronce wrote: post #13

MuffinFlavored wrote: post #2

This article would've been a bit cooler if the conclusion wasn't "switch from default allocator to jemalloc" but instead "use jemalloc to prove something is wrong in the default allocator and track down + find a fix for what's wrong in the default allocator" Unless I misunderstood that the default Rust allocator, with high request bodies and concurrency, is always going to suffer unfixable heap fragmentation like dis…

I agree that there could have been a more satisfying conclusion, but it is worth noting that jemalloc isn't a panacea. I've seen issues similar to Svix in both Rust and C++ applications that were heavy on ephemeral allocations, and have fixed it by doing all of the following, depending on the specific process: * Switching from libc malloc to jemalloc * Switching from libc malloc to tcmalloc (dating myself a little bi…

> * Switching from libc malloc to tcmalloc (dating myself a little bit)

If you think of tcmalloc as an old crusty allocator, you've probably only seen the gperftools version of it.

This is the version Google now uses internally: https://github.com/google/tcmalloc

It's worth a fresh look. In particular, it supports per-CPU caches as an alternative to per-thread caches. Those are fantastic if you have a lot more threads than CPUs. I haven't checked if it's been adapted for the latest upstream kernel API, but there's also the idea of "vcpu"-based caches: basically rather than a physical cpu id, it's an (optionally per-numa-node-based) dense id assigned to active threads, so that it still works well if you have a small cpu allocation for this process on a many-core machine.

Re: Spotting and avoiding heap fragmentation in Rust applications

#32

Post by Narishma » Thu, Apr 06, 2023, 8:53 PM UTC

adrianmonk wrote: post #28

> Gaps that are too small and scattered throughout the heap can lead to new "fresh" blocks of memory being allocated to accommodate a new value that won’t fit otherwise. Though unfortunately because of how memory management works a "defrag" is not possible. This is how memory management works now, but some older systems like classic Mac OS and Palm OS used a design that did make it possible to compact the heap. See h…

Early Windows version worked like that too.

Re: Spotting and avoiding heap fragmentation in Rust applications

#33

Post by Asooka » Thu, Apr 06, 2023, 8:57 PM UTC

adrianmonk wrote: post #28

> Gaps that are too small and scattered throughout the heap can lead to new "fresh" blocks of memory being allocated to accommodate a new value that won’t fit otherwise. Though unfortunately because of how memory management works a "defrag" is not possible. This is how memory management works now, but some older systems like classic Mac OS and Palm OS used a design that did make it possible to compact the heap. See h…

Rust's borrow checker should make it impossible to reference an unlocked pointer in safe code. I suspect it should be possible to have a compacting heap as a library.

Re: Spotting and avoiding heap fragmentation in Rust applications

#34

Post by astrange » Thu, Apr 06, 2023, 9:19 PM UTC

tasn wrote: post #26

jamboca wrote: post #20

"The specific cause for the fragmentation could be any number of things: JSON parsing with serde, something at the framework-level in axum, something deeper in tokio, or even just a quirk of the specific allocator implementation for the given system. Even without knowing the root cause (if there is such a thing) the behavior is observable in our environment and somewhat reproducible in a bare-bones app." So what is t…

Our assumption, which turned out to be true, is that it's due to the JSON parsing code. Rust (serde) is very efficient with parsing JSON to a predefined structure, but when it comes to parsing to a "generic object", which we need for part of the payload, it's not as much. We are going to deploy a full fix for this issue too, but jemalloc already solved it as well. Though I disagree with saying it's "just slapping jem…

Heap fragmentation often comes from allocating objects with different lifetimes at the same time on the same pages. Parsing is a common case of this because you allocate the whole object tree then only keep some of it.

Re: Spotting and avoiding heap fragmentation in Rust applications

#35

Post by astrange » Thu, Apr 06, 2023, 9:20 PM UTC

Tuna-Fish wrote: post #22

jamboca wrote: post #20

"The specific cause for the fragmentation could be any number of things: JSON parsing with serde, something at the framework-level in axum, something deeper in tokio, or even just a quirk of the specific allocator implementation for the given system. Even without knowing the root cause (if there is such a thing) the behavior is observable in our environment and somewhat reproducible in a bare-bones app." So what is t…

The gold standard for avoiding fragmentation is what jemalloc does, that is, only allocating objects of similar size from a chunk of memory. That is, instead of a single global heap there exists a pool for every valid size of object (and to keep the numbers low, object sizes are rounded up to some set of buckets). This means that there is more memory wasted for small programs, but as memory use grows the wastage caus…

This isn't good enough because size of an allocation says nothing about what its lifetime is. If you know lifetimes or types then you can segregate those and it does help.

(It does help in that if you have fixed size slabs, you can't waste space on that page, but you can still waste the entire page.)

Re: Spotting and avoiding heap fragmentation in Rust applications

#36

Post by cryptonector » Thu, Apr 06, 2023, 9:24 PM UTC

yakubin wrote: post #17

dgacmu wrote: post #10

Earlier quoted context omitted.

No - heap fragmentation actually leaves memory unusable by the workload. It may or may not slow down allocation depending on the design of the allocator. (The analogy to file system fragmentation for memory is that when physical pages are allocated in a discontinuous manner, it prevents some optimizations like coalescing them into hugepages, which for some workloads can help with TLB hit rate.)

Filesystem may also run out of inodes, even though there is still plenty of space.

Or you should use ZFS and not worry about that.

Re: Spotting and avoiding heap fragmentation in Rust applications

#37

Post by tasn » Thu, Apr 06, 2023, 9:26 PM UTC

astrange wrote: post #34

tasn wrote: post #26

Earlier quoted context omitted.

Our assumption, which turned out to be true, is that it's due to the JSON parsing code. Rust (serde) is very efficient with parsing JSON to a predefined structure, but when it comes to parsing to a "generic object", which we need for part of the payload, it's not as much. We are going to deploy a full fix for this issue too, but jemalloc already solved it as well. Though I disagree with saying it's "just slapping jem…

Heap fragmentation often comes from allocating objects with different lifetimes at the same time on the same pages. Parsing is a common case of this because you allocate the whole object tree then only keep some of it.

Not in the context of an HTTP server. As we just parse, use it in the request, and then return (freeing all the memory). I think the problem is because we have multiple requests being handled in tandem and Rust doesn't know it's probably better off allocating all of the data together and then freeing this big block.

That's what's nice about jemalloc, it has a more generic algorithm for reusing allocated blocks.

Re: Spotting and avoiding heap fragmentation in Rust applications

#38

Post by magicalhippo » Thu, Apr 06, 2023, 10:03 PM UTC

wongarsu wrote: post #27

yakubin wrote: post #17

Earlier quoted context omitted.

Filesystem may also run out of inodes, even though there is still plenty of space.

I don't think either FAT32 or NTFS suffer this problem, they allow metadata to become fragmented instead. Certainly a different design philosophy to the unixy file systems.

NTFS most definitely suffers from this[1]. We ran into it with a customer who had a particularly fragmented database file.

IIRC it's due to a combination of relying on fixed-sized "pages" to hold fragment pointers and a limited number of page indirections. That is the root page can point to a sub-pages, which again can point to sub-pages, but those sub-sub-pages have to point to the actual fragments. Or something along those lines.

[1]: https://support.microsoft.com/en-au/topic/a-heavily-fragment...

Re: Spotting and avoiding heap fragmentation in Rust applications

#39

Post by tayo42 » Thu, Apr 06, 2023, 10:13 PM UTC

was curious about

> When services exit abruptly, this can lower availability... which is bad for business.

interesting company

> Do you offer SLAs? We offer uptime SLAs of 99.999% for our enterprise customers, 99.99% for our business tier customers, and 99.9% for our startup tier users.

99.999 is miserable to support. how do you even get the granularity to measure, freedom to try anything? i dont think cloud services even provide slas like that for their services.

>Can you handle our scale? We process billions of webhooks a year for our customers,

1 billion a year would average out to 32 a second. if its 10 billion? 320/second. surprising to see rust for this. gc languages should be able to handle it.

would have been interesting to see how much fragmentation there is. reads like there was a debugging step missing.

Re: Spotting and avoiding heap fragmentation in Rust applications

#40

Post by tasn » Thu, Apr 06, 2023, 10:24 PM UTC

tayo42 wrote: post #39

was curious about > When services exit abruptly, this can lower availability... which is bad for business. interesting company > Do you offer SLAs? We offer uptime SLAs of 99.999% for our enterprise customers, 99.99% for our business tier customers, and 99.9% for our startup tier users. 99.999 is miserable to support. how do you even get the granularity to measure, freedom to try anything? i dont think cloud services…

> 99.999 is miserable to support. how do you even get the granularity to measure, freedom to try anything? i dont think cloud services even provide slas like that for their services.

A lot of redundancies and testing.

> 1 billion a year would average out to 32 a second. if its 10 billion? 320/second. surprising to see rust for this. gc languages should be able to handle it.

This assumes even distribution, though traffic is much much more spiky than this. We started with Python and switched to Rust. FWIW, Rust is great for many other reasons, not just the efficiency. For example, we absolutely love the type system.

> would have been interesting to see how much fragmentation there is. reads like there was a debugging step missing.

I'm not the engineer that did the investigation, so can't comment directly about what he checked. Maybe it's not written there, but he also measured allocator statistics and indeed saw that the memory used according to the US was much higher than what the allocator stats said.