26 ms·

Looks like the big challenge is managing a large, LRU cache, which tends to be a difficult problem for GC runtimes. I bet the JVM, with its myriad tunable GC a

Looks like the big challenge is managing a large, LRU cache, which tends to be a difficult problem for GC runtimes. I bet the JVM, with its myriad tunable GC algorithms, would perform better, especially Shenandoah and, of course, the Azul C4. The JVM world tends to solve this problem by using off-heap caches. See Apache Ignite [0] or Ehcache [1]. I can't speak for how their Rust cache manages memory, but the thing to be careful of in non-GC runtimes (especially non-copying GC) is memory fragmentation. Its worth mentioning that the Dgraph folks wrote a better Go cache [2] once they hit the limits of the usual Go caches. From a purely architectural perspective, I would try to put cacheable material in something like memcache or redis, or one of the many distributed caches out there. But it might not be an option. It's worth mentioning that Apache Cassandra itself uses an off-heap cache. [0]: https://ignite.apache.org/arch/durablememory.html https://ignite.apache.org/arch/durablememory.html [1]: https://www.ehcache.org/documentation/2.8/get-started/storage-options.html#bigmemory-(off-heap-store) https://www.ehcache.org/documentation/2.8/get-started/storag... [2]: https://blog.dgraph.io/post/introducing-ristretto-high-perf-go-cache/ https://blog.dgraph.io/post/introducing-ristretto-high-perf-...

pshc 7y ago
Great comment and thanks for the reading material. Now I'm wondering if there's a Rust library for a generational copying arena--one that compacts strings/blobs over time.
- steveklabnik 7y ago
  Generational arenas yes, but copying, I'm not aware of one. It's very hard to get the semantics correct, since you can't auto-re-write pointers/indices.
  - ithkuil 7y ago
    Perhaps such a library could help you record the location of the variables that contain pointers to the strings and keep that pointer up to data as the ownership of the string moves from variable to variable? I'm other words, doing some of the work a moving compacting collector would do during compaction but continuously during normal program execution.
    - steveklabnik 7y ago
      There's no way to hook into the move, so I don't see how it would be possible, or at least, not with techniques similar to compacting GCs.
      - masklinn 7y ago
        Maybe by reifying the indirection? The compacting arena would hand out smart pointers which would either always bounce through something (to get from an indentity to the actual memory location, at a cost) or it'd keep track and patch the pointers it handed out somehow. Possibly half and half, I don't remember what language it was (possibly obj-c?) which would hand out pointers, and on needing to move the allocations it'd transform the existing site into a "redirection table". Accessing pointers would check if they were being redirected, and update themselves to the new location if necessary. edit: might have been the global refcount table? Not sure.
        steveklabnik 7y ago
        Yeah so I was vaguely wondering about some sort of double indirection; the structure keeps track of "this is a pointer I've handed out", those pointers point into that, which then points into the main structure. I have no idea if this actually a good idea, seems like you get rid of a lot of the cache locality advantages.
        masklinn 7y ago
        I don't know that the cache locality would be a big issue (your indirection table would be a small-ish array), however you'd eat the cost of doubling the indirections, each pointer access would be two of them.
        mypalmike 7y ago
        This sounds a lot like classic MacOS (pre-Darwin) memory allocation. You were allocated a handle, which you called Lock on to get a real pointer. After accessing the memory, you called Unlock to release it. There was definitely a performance hit for that indirection.
dochtman 7y ago
One the one hand, yes. On the other hand, all of this sounds much more complex and fragile. This seems like an important point to me: "Remarkably, we had only put very basic thought into optimization as the Rust version was written. Even with just basic optimization, Rust was able to outperform the hyper hand-tuned Go version."
- novok 7y ago
  A C app will tend to outperform a Java or Golang app by 3x, so it isn't too surprising.
  - georgebarnett 7y ago
    Could you please provide a source for this? Java is very fast and 3X slower is a pretty wild claim.
    - squarefoot 7y ago
      3x might be a bit too much today, but it's definitely slower than C. Also to be considered is the VM overhead, not just the executed code. Here are some benchmarks; I'll leave to the experts out there to confirm or dismiss them. https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/java.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
      - robocat 7y ago
        However the memory usage difference is astonishing for some of those benchmarks - using 1000x more memory is only acceptable for some situations.
        iainmerrick 7y ago
        This may be overly cynical, but don’t you have it backwards? 1000x greater memory usage is acceptable for most applications. There are only a few applications for which it isn’t acceptable. Just look at all the massive apps built on Electron. People wouldn’t do that if it wasn’t effective.
stingraycharles 7y ago
> The JVM world tends to solve this problem by using off-heap caches. See Apache Ignite [0] or Ehcache [1]. For those who care, I was interested how off-heap caching works in Java and I did some quick searching around the Apache Ignite code. The meat is here: - GridUnsafeMemory, an implementation of access to entries allocated off-heap. This appears to implement some common Ignite interface, and invokes calls to a “GridUnsafe” class https://github.com/apache/ignite/blob/53e47e9191d717b3eec495e6246cd957a8d33c7d/modules/core/src/main/java/org/apache/ignite/internal/util/offheap/unsafe/GridUnsafeMemory.java https://github.com/apache/ignite/blob/53e47e9191d717b3eec495... - This class is the closest to the JVM’s native memory, and wraps sun.misc.Unsafe: https://github.com/apache/ignite/blob/53e47e9191d717b3eec495e6246cd957a8d33c7d/modules/core/src/main/java/org/apache/ignite/internal/util/GridUnsafe.java https://github.com/apache/ignite/blob/53e47e9191d717b3eec495... - And this, sun.misc.Unsafe, is what it’s all about: http://www.docjar.com/docs/api/sun/misc/Unsafe.html http://www.docjar.com/docs/api/sun/misc/Unsafe.html It’s very interesting because I did my fair share of JNI work, and context switches between JVM and native code are typically fairly expensive. My guess is that this class was likely one of the reasons why Sun ended up implementing their (undocumented) JavaCritical* etc functions and the likes.
- winrid 7y ago
  The idea is that that call is still less expensive than going over the wire and MUCH less expensive than having the GC go through that heap now and then.
  - stingraycharles 7y ago
    Yes sorry I should have elaborated, those Critical JNI calls avoid locking the GC and in general are much more lightweight. This is available for normal JNI devs as well, its just not documented. They were primarily intended for some internal things that Sun needed. I’m now guessing that this might actually have been those Unsafe classes as an intended use case. It makes total sense and I can see how that will be very fast.
- chrisseaton 7y ago
  > context switches between JVM and native code are typically fairly expensive Aren't these Unsafe memory read and write methods intrinsified by any serious compiler? I don't believe they're using JNI or doing any kind of managed/native transition, except in the interpreter. They turn into the same memory read and write operations in the compiler's intermediate representation as Java field read and writes do.
tsimionescu 7y ago
> I can't speak for how their Rust cache manages memory, but the thing to be careful of in non-GC runtimes (especially non-copying GC) is memory fragmentation. As far as I know, a mark-and-sweep collector like Go's doesn't have any advantage over malloc/free when it comes to memory fragmentation. Am I missing some way in which Go's GC helps with fragmentation?
- lossolo 7y ago
  Go GC implementation uses memory allocator that was based on TCMalloc (but derived from it quite a bit). They use a free list of multiple fixed allocatable size-classes, which helps in reducing fragmentation. That's why Go GC is non-copying.
  - haimez 7y ago
    I’m not sure I follow. GC implementations that don’t copy (relocate) are inherently subject to the performance cost of “fragmentation” (in the sense of scattering memory accesses over non-adjacent regions). This is a very high price to pay when you’re dealing with modern hardware.
    - andoriyu 7y ago
      Allocator underneath is keeping track of freed memory, so next allocation has high chance of being squeezed into memory region that has been used before. It's obviously not as good as say GC that relocates after sweep, but at least it doesn't leave gaping holes.
      - haimez 7y ago
        Indeed, but it also doesn’t maintain locality of access nearly as well for young objects (the most commonly manipulated ones) and even older ones that survive.
        jstrong 7y ago
deleted 7y ago
[deleted]
wpietri 7y ago
Maybe I've missed this, but why do they need a particularly large LRU cache? Surely this isn't all one process, so presumably they could reduce spikes by splitting the same load across yet more processes?
- Techies4Trump 7y ago
  Larger cache = faster performance and less load on the database. I only glossed over the article but the problem they had with Go seems to be the GC incurred from having a large cache. Their cache eviction algorithm was efficient, but every 2 minutes there was a GC run which slowed things down. Re-implementing this algorithm in Rust gave them better performance because the memory was freed right after the cache eviction. Splitting it across more processes will result in more cache misses and more DB calls.
  - wpietri 7y ago
    I am of course talking about the same amount of total cache RAM, just split among more processes. Depending on distribution of the calls, you might get more cache misses, but I don't think it's guaranteed, and if it is, I don't think we can assume it's significant. Heck, you could even use more cache RAM; the cost of a total rewrite plus ongoing maintenance in a new language covers a fair bit of hardware these days.
tlrobinson 7y ago
> From a purely architectural perspective, I would try to put cacheable material in something like memcache or redis, or one of the many distributed caches out there. But it might not be an option. Can you speak to why using something like memcache or redis may not be an option?
- otterley 7y ago
  For latency-sensitive services, having to traverse the network to access a shared cache may be too slow. To use the current story as an example, you'd be trading off an occasional 100-millisecond latency spike every 2 minutes for an added 1-2ms of latency for every request.
cft 7y ago
> From a purely architectural perspective, I would try to put cacheable material in something like memcache or redis You cannot use a caching server at that scale with those latency requirements. It has to be embedded
- toxicafunk 7y ago
  Something like rocksdb (https://rocksdb.org/ https://rocksdb.org/) then
  - cft 7y ago
    You cannot use that either, due to I/O block device saturation, even on enterprise PCIe NVMe. Not enough parallel IOPS. Only RAM can be used.
- deleted 7y ago
  [deleted]
adev_ 7y ago
> The JVM world tends to solve this problem by using off-heap caches. See Apache Ignite [0] or Ehcache [1]. Yeah, but I really do not bite your argument. When you are reduced to do manual memory management and fight the GC of your language, maybe you should simply not use a language with GC in the first place. They are right to use rust ( or C/C++) for that. It's not for nothing that redis (C) is so successful in the LRU domain. > It's worth mentioning that Apache Cassandra itself uses an off-heap cache. And still ScyllaDB (C++) is able to completely destroy Cassandra in term of AVG latency [0] [0]: https://www.scylladb.com/product/benchmarks/ https://www.scylladb.com/product/benchmarks/
mrjn 7y ago
Don't know enough about Rust, but I think Go would benefit immensely by allowing its users to disable GC and allow de-allocating memory by hand. GC is great for simpler applications, but more complex projects end up fighting so much with memory and GC in Go that all the benefits of automatic de-allocations are negated. Love every other aspect of Go.
PeterCorless 7y ago
Wow. We literally just published why to not put a cache in front of your server to mask its bad performance behind a layer of complexity. tl;dr: make sure you have a solid DB to begin with. (Forgive the gated asset, but it's a good read!) https://go.scylladb.com/7-reasons-no-external-cache-database-offer.html https://go.scylladb.com/7-reasons-no-external-cache-database...

pshc 7y ago

Great comment and thanks for the reading material. Now I'm wondering if there's a Rust library for a generational copying arena--one that compacts strings/blobs over time.

steveklabnik 7y ago
Generational arenas yes, but copying, I'm not aware of one. It's very hard to get the semantics correct, since you can't auto-re-write pointers/indices.
- ithkuil 7y ago
  Perhaps such a library could help you record the location of the variables that contain pointers to the strings and keep that pointer up to data as the ownership of the string moves from variable to variable? I'm other words, doing some of the work a moving compacting collector would do during compaction but continuously during normal program execution.
  - steveklabnik 7y ago
    There's no way to hook into the move, so I don't see how it would be possible, or at least, not with techniques similar to compacting GCs.
    - masklinn 7y ago
      Maybe by reifying the indirection? The compacting arena would hand out smart pointers which would either always bounce through something (to get from an indentity to the actual memory location, at a cost) or it'd keep track and patch the pointers it handed out somehow. Possibly half and half, I don't remember what language it was (possibly obj-c?) which would hand out pointers, and on needing to move the allocations it'd transform the existing site into a "redirection table". Accessing pointers would check if they were being redirected, and update themselves to the new location if necessary. edit: might have been the global refcount table? Not sure.
      - steveklabnik 7y ago
        Yeah so I was vaguely wondering about some sort of double indirection; the structure keeps track of "this is a pointer I've handed out", those pointers point into that, which then points into the main structure. I have no idea if this actually a good idea, seems like you get rid of a lot of the cache locality advantages.
        masklinn 7y ago
        I don't know that the cache locality would be a big issue (your indirection table would be a small-ish array), however you'd eat the cost of doubling the indirections, each pointer access would be two of them.
        mypalmike 7y ago
        This sounds a lot like classic MacOS (pre-Darwin) memory allocation. You were allocated a handle, which you called Lock on to get a real pointer. After accessing the memory, you called Unlock to release it. There was definitely a performance hit for that indirection.

dochtman 7y ago

One the one hand, yes. On the other hand, all of this sounds much more complex and fragile. This seems like an important point to me: "Remarkably, we had only put very basic thought into optimization as the Rust version was written. Even with just basic optimization, Rust was able to outperform the hyper hand-tuned Go version."

novok 7y ago
A C app will tend to outperform a Java or Golang app by 3x, so it isn't too surprising.
- georgebarnett 7y ago
  Could you please provide a source for this? Java is very fast and 3X slower is a pretty wild claim.
  - squarefoot 7y ago
    3x might be a bit too much today, but it's definitely slower than C. Also to be considered is the VM overhead, not just the executed code. Here are some benchmarks; I'll leave to the experts out there to confirm or dismiss them. https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/java.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
    - robocat 7y ago
      However the memory usage difference is astonishing for some of those benchmarks - using 1000x more memory is only acceptable for some situations.
      - iainmerrick 7y ago
        This may be overly cynical, but don’t you have it backwards? 1000x greater memory usage is acceptable for most applications. There are only a few applications for which it isn’t acceptable. Just look at all the massive apps built on Electron. People wouldn’t do that if it wasn’t effective.

stingraycharles 7y ago

> The JVM world tends to solve this problem by using off-heap caches. See Apache Ignite [0] or Ehcache [1]. For those who care, I was interested how off-heap caching works in Java and I did some quick searching around the Apache Ignite code. The meat is here: - GridUnsafeMemory, an implementation of access to entries allocated off-heap. This appears to implement some common Ignite interface, and invokes calls to a “GridUnsafe” class https://github.com/apache/ignite/blob/53e47e9191d717b3eec495e6246cd957a8d33c7d/modules/core/src/main/java/org/apache/ignite/internal/util/offheap/unsafe/GridUnsafeMemory.java https://github.com/apache/ignite/blob/53e47e9191d717b3eec495... - This class is the closest to the JVM’s native memory, and wraps sun.misc.Unsafe: https://github.com/apache/ignite/blob/53e47e9191d717b3eec495e6246cd957a8d33c7d/modules/core/src/main/java/org/apache/ignite/internal/util/GridUnsafe.java https://github.com/apache/ignite/blob/53e47e9191d717b3eec495... - And this, sun.misc.Unsafe, is what it’s all about: http://www.docjar.com/docs/api/sun/misc/Unsafe.html http://www.docjar.com/docs/api/sun/misc/Unsafe.html It’s very interesting because I did my fair share of JNI work, and context switches between JVM and native code are typically fairly expensive. My guess is that this class was likely one of the reasons why Sun ended up implementing their (undocumented) JavaCritical* etc functions and the likes.

winrid 7y ago
The idea is that that call is still less expensive than going over the wire and MUCH less expensive than having the GC go through that heap now and then.
- stingraycharles 7y ago
  Yes sorry I should have elaborated, those Critical JNI calls avoid locking the GC and in general are much more lightweight. This is available for normal JNI devs as well, its just not documented. They were primarily intended for some internal things that Sun needed. I’m now guessing that this might actually have been those Unsafe classes as an intended use case. It makes total sense and I can see how that will be very fast.
chrisseaton 7y ago
> context switches between JVM and native code are typically fairly expensive Aren't these Unsafe memory read and write methods intrinsified by any serious compiler? I don't believe they're using JNI or doing any kind of managed/native transition, except in the interpreter. They turn into the same memory read and write operations in the compiler's intermediate representation as Java field read and writes do.

tsimionescu 7y ago

> I can't speak for how their Rust cache manages memory, but the thing to be careful of in non-GC runtimes (especially non-copying GC) is memory fragmentation. As far as I know, a mark-and-sweep collector like Go's doesn't have any advantage over malloc/free when it comes to memory fragmentation. Am I missing some way in which Go's GC helps with fragmentation?

lossolo 7y ago
Go GC implementation uses memory allocator that was based on TCMalloc (but derived from it quite a bit). They use a free list of multiple fixed allocatable size-classes, which helps in reducing fragmentation. That's why Go GC is non-copying.
- haimez 7y ago
  I’m not sure I follow. GC implementations that don’t copy (relocate) are inherently subject to the performance cost of “fragmentation” (in the sense of scattering memory accesses over non-adjacent regions). This is a very high price to pay when you’re dealing with modern hardware.
  - andoriyu 7y ago
    Allocator underneath is keeping track of freed memory, so next allocation has high chance of being squeezed into memory region that has been used before. It's obviously not as good as say GC that relocates after sweep, but at least it doesn't leave gaping holes.
    - haimez 7y ago
      Indeed, but it also doesn’t maintain locality of access nearly as well for young objects (the most commonly manipulated ones) and even older ones that survive.
      - jstrong 7y ago

deleted 7y ago

[deleted]

wpietri 7y ago

Maybe I've missed this, but why do they need a particularly large LRU cache? Surely this isn't all one process, so presumably they could reduce spikes by splitting the same load across yet more processes?

Techies4Trump 7y ago
Larger cache = faster performance and less load on the database. I only glossed over the article but the problem they had with Go seems to be the GC incurred from having a large cache. Their cache eviction algorithm was efficient, but every 2 minutes there was a GC run which slowed things down. Re-implementing this algorithm in Rust gave them better performance because the memory was freed right after the cache eviction. Splitting it across more processes will result in more cache misses and more DB calls.
- wpietri 7y ago
  I am of course talking about the same amount of total cache RAM, just split among more processes. Depending on distribution of the calls, you might get more cache misses, but I don't think it's guaranteed, and if it is, I don't think we can assume it's significant. Heck, you could even use more cache RAM; the cost of a total rewrite plus ongoing maintenance in a new language covers a fair bit of hardware these days.

tlrobinson 7y ago

> From a purely architectural perspective, I would try to put cacheable material in something like memcache or redis, or one of the many distributed caches out there. But it might not be an option. Can you speak to why using something like memcache or redis may not be an option?

otterley 7y ago
For latency-sensitive services, having to traverse the network to access a shared cache may be too slow. To use the current story as an example, you'd be trading off an occasional 100-millisecond latency spike every 2 minutes for an added 1-2ms of latency for every request.

cft 7y ago

> From a purely architectural perspective, I would try to put cacheable material in something like memcache or redis You cannot use a caching server at that scale with those latency requirements. It has to be embedded

toxicafunk 7y ago
Something like rocksdb (https://rocksdb.org/ https://rocksdb.org/) then
- cft 7y ago
  You cannot use that either, due to I/O block device saturation, even on enterprise PCIe NVMe. Not enough parallel IOPS. Only RAM can be used.
deleted 7y ago
[deleted]

adev_ 7y ago

> The JVM world tends to solve this problem by using off-heap caches. See Apache Ignite [0] or Ehcache [1]. Yeah, but I really do not bite your argument. When you are reduced to do manual memory management and fight the GC of your language, maybe you should simply not use a language with GC in the first place. They are right to use rust ( or C/C++) for that. It's not for nothing that redis (C) is so successful in the LRU domain. > It's worth mentioning that Apache Cassandra itself uses an off-heap cache. And still ScyllaDB (C++) is able to completely destroy Cassandra in term of AVG latency [0] [0]: https://www.scylladb.com/product/benchmarks/ https://www.scylladb.com/product/benchmarks/

mrjn 7y ago

Don't know enough about Rust, but I think Go would benefit immensely by allowing its users to disable GC and allow de-allocating memory by hand. GC is great for simpler applications, but more complex projects end up fighting so much with memory and GC in Go that all the benefits of automatic de-allocations are negated. Love every other aspect of Go.

PeterCorless 7y ago

Wow. We literally just published why to not put a cache in front of your server to mask its bad performance behind a layer of complexity. tl;dr: make sure you have a solid DB to begin with. (Forgive the gated asset, but it's a good read!) https://go.scylladb.com/7-reasons-no-external-cache-database-offer.html https://go.scylladb.com/7-reasons-no-external-cache-database...