11 ms·
Cache invalidation really is one of the hardest problems in computer science
- taeric 4y agoI was initially disappointed by not seeing a discussion of jargon in the field. Specifically, I think you have to discuss eviction and expiration as two distinct things with many caches. That said, I enjoyed the article and highly recommend it. With the obvious caveat of "this is the kind of problem that you are likely to never be impacted by," I think it is a fascinating incident that I'm very grateful for the analysis to have been shared. Having another pass at explaining the analysis was a pleasant surprise and a fun read.
- inkeddeveloper 4y agoI don’t know. It’s pretty easy if you just don’t use cache.
- ohiovr 4y agoJust flush it down the toilet when it stinks.
- wkdneidbwf 4y agowe take a clean-room approach to computation.
- ramraj07 4y agoAs much as folks are downvoting you there’s a nugget of beauty in your demand - our systems should abstract caching. Ideally your web server framework should cache results itself. Your db too. If Postgres was good at it you wouldn’t need redis as well right?
- GenerocUsername 4y agoSounds like you might like a server based framework like wordpress
- ganbatekudasai 4y agoCPUs already do, except for when the abstraction breaks down for performance reasons.
- mjfl 4y agoand orders of magnitude slower!
- swagasaurus-rex 4y agoThe amount of inefficiency in code these days is a testament to the enormous computational power of modern computers. We're talking billions of multiplications or additions per second and millions of division per second. A mad genius could code most business logic to never be greater than o(n) outside of the most complex of problems. At that point a cache would become a liability due to cache invalidation errors, one of the hardest problems. Not that I recommend this approach. Caches are good tools and can help with DOS.
- anyfoo 4y agoI think you vastly underestimate just how much slower DRAM is compared to cache (SRAM). Your super fast CPU will be sitting idly doing nothing if it were not for the caches between it and DRAM, which keep it fed with data and instructions.
- deleted 4y ago[deleted]
- Stratoscope 4y agoThis of course requires a citation of the old joke... There are two hard problems in computer science: naming things, cache invalidation, and off by one errors.
- MontyCarloHall 4y agoThere are three hard problems in CS: naming cache things, invalidation, off by one and concurrency. errors,
- djbusby 4y agoI thought off by one always had to go at the end.
- Closi 4y agoI think that’s the joke - that concurrency errors is in the wrong place.
- balls187 4y agoIt’s that the “errors” from “off by one errros” comes after concurrency (the hard things being: cache invalidation, off by one errors, naming, and concurrency—not concurrency errors)
- dbcurtis 4y agocan’t tell if meta or whoosh
- Stratoscope 4y agoA thought, reasonable but that how you is fail concurrency. at
- anyfoo 4y agoI think it’s like those tired old UDP multicast jokes which some people don’t get.
- joshsyn 4y ago
- PaulHoule 4y agoThis is an aphorism I got tired of a long time ago. There was a batch job that I sped up about 40 times with a cache. The invalidation strategy I used was "dump the whole cache and start a new one" which wasn't too bad because the system got about 10% through the job when it ran out of RAM and it had a pattern of a long-tail distribution plus locality which fit that model well. If I'd been memory-constrained, or had a distributed system, it would have been a different story, but it's not unusual for caching to be a win with a simple invalidation strategy.
- anyfoo 4y agoTo be fair, rocket science is also hard, but not very much when all you plan to do is hitting a barn door with fireworks. Same with prime factorization when the number to factor is “15”, spontaneously sketching out the pole-zero diagram of f(x)=0… you get the gist. Usually when people talk about a topic being hard, they don’t mean the very constrained cases that are easy.
- bombcar 4y agoIt’s amusing because rocket science is pretty easy. Rocket mechanics is the tricky part.
- rapind 4y agoRocket scientists can be heard saying "It's not like it's cache invalidation!".
- PaulHoule 4y agoIt's the other way around. 90% of the cases are easy cases, where thinking too hard about invalidation (as opposed to testing what works) is likely to give you worse performance. There are a rare set of cases that are devilishly hard such as synchronizing the caches across an SMP microprocessor or making a system like Cloudflare really speed up your web site as opposed to slowing it down.
- 4y ago
- Supermancho 4y agoRe: cache coherency and mixing in tiering, blah blah - This looks more like a CAP problem than a cache invalidation problem.
- ganbatekudasai 4y agoHow is partition tolerance relevant to CPU cache hierarchies? How is cache coherency not a question of when and how to perform cache invalidation?
- Supermancho 4y ago> How is partition tolerance relevant to CPU cache hierarchies? It's not. Hope that answers the question. A lot of this article is about additional concerns that are being leveraged, while avoiding the core issue. Cache coherency and consistency are equivalent, in this case. > How is cache coherency not a question of when and how to perform cache invalidation? It's a consistency concern, for which you have to make a tradeoff. Cache invalidation is incidental, not specifically relevant to the problem at hand. It just happens to take place in memory that has the name cache.
- ganbatekudasai 4y ago> A lot of this article is about additional concerns that are being leveraged, while avoiding the core issue. What’s the core issue that is being avoided here?
- Supermancho 4y agoThey are trying to optimize for what hardware they are stuck with, then characterizing it as if it's a cache invalidation problem. At the core, it is not a problem with when to do cache invalidation. Their "problem" (which isn't a problem, they just want to see a different use profile) is a consequence of what they have decided to stick with due to concerns that are not reasoned and wouldn't be very interesting anyway. I don't understand why anyone would want to belabor this further.
- mxkopy 4y agoCS looks so much like biology sometimes Sometimes the relevant phenomenon lies at the scale of cache-lines, of which there is a whole zoo of possible specifications
- djbusby 4y agoI've made lots of headway with MBA types explaining software as a lifeform. Care and feeding and mutations and cancer.
- bch 4y agoEmergent behavior…
- code_biologist 4y agoGreat article from a few years ago "A Codebase is an Organism": https://meltingasphalt.com/a-codebase-is-an-organism/ https://meltingasphalt.com/a-codebase-is-an-organism/ HN discussion: https://news.ycombinator.com/item?id=20787848 https://news.ycombinator.com/item?id=20787848
- sedeki 4y agoOff topic: What level of sophistication about modern CPUs is _good_ to have? And where does one learn it? Resources? Say that I want to work with HPC-type applications and otherwise just squeeze the most out of the processor, e.g. quant finance / trading systems.
- anonymoushn 4y agoThere are a lot of issues here, so I can share some stuff about some of them and hope that some helpful internet commenters come along and point out where I have neglected important things. A single modern CPU core is superscalar and has a deep instruction pipeline. With your help, it will decode and reorder many instructions and execute many instructions concurrently. Each of those instructions can operate on a lot of data. As famous online controversial opinion haver Casey Muratori tells us, most software just sucks, like really really bad (e.g. commonly people will post hash table benchmarks of high-performance hash tables that do bulk inserts in ~100ns/op, but you can do <10ns/op easily if you try), and using SIMD instructions is table stakes for making good use of the machinery inside of a single CPU core. SIMD instructions are not just for math! They are tools for general purpose programming. When your program needs to make decisions based on data that does not contain obvious patterns, it is often a lot cheaper to compute both possible outcomes and have a data dependency than to have a branch. Instructions like pshufb or blendv or just movemask and then using a dang lookup table can replace branches. Often these instructions can replace 32 or 64 branches at a time[0]. Wojciech Muła's web site[1] is the best collection of notes about using SIMD instructions for general-purpose programming, but I have found some of the articles to be a bit terse or sometimes incorrect, and I have not yet done anything to fix the issue. "Using SIMD" ends up meaning that you choose the low-level layout of your data to be more suitable to processing using the instructions available. Inside your single CPU core there is hardware for handling virtual -> physical address translation. This is a special cache called the translation lookaside buffer (TLB). Normally, chips other than recent Apple chips have a couple hundred entries of 1 4KiB page each in the TLB, and recent Apple chips have a couple hundred entries of 1 16KiB page each. Normal programs deal with a bit more than 1 meg of RAM today, and as a result they spend a huge portion of their execution time on TLB misses. You can fix this by using explicit huge pages on Linux. This feature nominally exists on Windows but is basically unusable for most programs because it requires the application to run as administrator and because the OS will never compact memory once it is fragmented (so the huge pages must be obtained at startup and never released, or they will disappear until you reboot). I have not tried it on Mac. As an example of a normal non-crazy program that is helped by larger pages, one person noted[2] that Linux builds 16% faster on 16K vs on 4K pages. Inside your single CPU core is a small hierarchy of set-associative caches. With your help, it will have the data it needs in cache almost all the time! An obvious aspect of this is that when you need to work on some data repeatedly, if you have a choice, you should do it before you have worked on a bunch of other data and caused that earlier data to be evicted (that is, you can rearrange your work to avoid "capacity misses"). A less obvious aspect of this is that if you operate on data that is too-aligned, you will greatly reduce the effective size of your cache, because all the data you are using will go into the same tiny subset of your cache! An easy way to run into this issue is to repeatedly request slabs of memory from an allocator that returns pretty-aligned slabs of memory, and then use them all starting at the beginning. That this could cause problems at all seems relatively unknown, so I would guess lots and lots of software is losing 5-10% of its performance because of this sort of thing. Famous online good opinion haver Dan Luu wrote about this here[3]. The links included near the bottom of that post are also excellent resources for the topics you've asked about. When coordinating between multiple CPU cores, as noted in TFA, it is helpful to avoid false sharing[4]. People who write trading systems have mostly found that it is helpful to avoid sharing *at all*, which is why they have work explicitly divided among cores and communicate over queues rather than dumping things into a concurrent hash map and hoping things work out. In general this is not a popular practice, and if you go online and post stuff like "Well, just don't allocate any memory after startup and don't pass any data between threads other than by using queues" you will generally lose imaginary internet points. There are some incantations you may want to apply if you would like Linux to prioritize running your program, which are documented in the Red Hat Low Latency Performance Tuning guide[5] and Erik Rigtorp's web site[6]. Some other various resources are highload.fun[7], a web site where you can practice this sort of thing, a list of links associated with highload.fun[8], Sergey Slotin's excellent online book Algorithms for Modern Hardware[9], and Dendi Bakh's online course Perf Ninja[10] and blog easyperf[11]. > Off topic: What level of sophistication about modern CPUs is _good_ to have? Probably none? These skills are basically unemployable as far as I can tell. [0]: https://github.com/lemire/despacer https://github.com/lemire/despacer [1]: http://0x80.pl/articles/index.html http://0x80.pl/articles/index.html [2]: https://twitter.com/AtTheHackOfDawn/status/1333895115174187011 https://twitter.com/AtTheHackOfDawn/status/13338951151741870... [3]: https://danluu.com/3c-conflict/ https://danluu.com/3c-conflict/ [4]: https://rigtorp.se/ringbuffer/ https://rigtorp.se/ringbuffer/ [5]: https://access.redhat.com/sites/default/files/attachments/201501-perf-brief-low-latency-tuning-rhel7-v2.1.pdf https://access.redhat.com/sites/default/files/attachments/20... [6]: https://rigtorp.se/low-latency-guide/ https://rigtorp.se/low-latency-guide/ [7]: https://highload.fun/ https://highload.fun/ [8]: https://github.com/Highload-fun/platform/wiki https://github.com/Highload-fun/platform/wiki [9]: https://en.algorithmica.org/hpc/ https://en.algorithmica.org/hpc/ [10]: https://github.com/dendibakh/perf-ninja https://github.com/dendibakh/perf-ninja [11]: https://easyperf.net/notes/ https://easyperf.net/notes/
- MontyCarloHall 4y agoDespite the complexity of the cause of the problem, the fix was really simple: they just introduced 64 bytes of padding between the two struct members to guarantee that they never could fall within the same cache line. Sometimes the best solution is brute force!
- almost_usual 4y agoThey still saw the same performance though due to “true sharing” or CPU enforced memory ordering on a highly contended variable. Patching the JDK to skip the secondary cache altogether was the real solution.
- pestatije 4y agoWeird they added 64 bytes and not 56, which is the minimum required to have the two variables in different cache lines.
- basilgohar 4y agoMaybe the 64 bytes was better for some kind of alignment with other architectural structures....
- greenyoda 4y agoHere's the HN discussion of the original Netflix TechBlog article that this one references: https://news.ycombinator.com/item?id=33540091 https://news.ycombinator.com/item?id=33540091
- dragontamer 4y ago> Cache coherency ensures that the behavior is correct, but every time a cache is invalidated and the same memory has to be retrieved from main memory again, it pays the performance penalty of reading from main memory. 1. First no. If any such rereads occur, they will be from the LLC (last-level cache, or L3 cache for Intel/AMD CPUs). 2. Second no. IIRC, modern caches are snooping and/or directory caches. This means that when Core#0 says "I'm changing cacheline X", Core#0 knows that Core#1 has it in its L2 (or deeper) caches. So Core#0 will publish the results of that change to Core#1 3. The examples they gave are missing read/write barriers, which are rather important. #2 will only happen during read/write barriers. That is to say: your code is memory-unsafe by default. If order and cache-invalidation matters, you actually need a barrier instruction (!!!) to make sure all these messages are passed to the right place at the right time. --------- For better or for worse, modern CPU design is about doing things thread-unsafe by default. If the programmer recognizes a problem may occur, it is the responsibility of the programmer to put the memory barriers in the right place. This is because the CPU is not the only thing that can reorder things... but also the cache system... as well as the compiler. So memory barriers inform the compiler + CPU + cache system when to synchronize. The original Netflix article is more precisely worded. > This consistency is ensured with so-called “cache coherency protocol.” With a link to MESIF (F for Forwarding state, which is one such protocol / way to share L1 cache info without going all the way to LLC or DRAM) I'm pretty sure that GPUs actually invalidate the cache dumbly, without any MESI / MESIF (or whatever). GPUs are actually really bad at these kinds of ping-pong operations and synchronization... preferring thread-fences and other synchronization mechanisms instead. ------ That being said, I think the blogpost is a good introduction to the subject. But note that its a bit imprecise with some of the low level details. I guess its correct for the GPU-world though, so its not completely inaccurate... ----- The original Netflix article has an even more difficult problem revolving around Java's Superclass cache and how it is affecting "true sharing" of caches. I'm not very familiar with JVM internals, so I lost track of the discussion at that point.
- bluGill 4y agoNot all the world is x86, arm doesn't do as much.
- tbrownaw 4y ago> false sharing Usually the "cache invalidation" remark is about correctness and knowing when to invalidate, like for example making sure all your login tokens get expired when you change your password. This is about performance impacts from having multiple logical entities in one shared cached entity.
- stingraycharles 4y agoYes I’d say this is more along the lines of concurrency problems than caching problems: it’s about synchronizing access to memory (cache) between multiple cores.
- tremon 4y agoMore generally, it's about making sure that no consumer uses stale data, in the presence of multiple concurrent producers and consumers.
- stevefan1999 4y agoThere are only two hard things in Computer Science: cache invalidation and naming things. -- Phil Karlton
- prabhu-yu 4y agoIn the fix, they have padded. instead of padding, do we have compiler directive, that forces the a variable starting using a fresh cache line (instead of putting it in the last cache line?) Reason I am asking this, it will make the fix independent of the architecture of cache lines, size of cache lines. Also, the compiler directive/annotation would help developer to use it more liberally when they think, false sharing can happen.
- int0x80 4y agoThere is __attribute__((aligned)) that some compilers provide (e.g. gcc, clang) but it's non-standard.
- prabhu-yu 4y agoThank you for the respone. Can we write like this? Klass ssc __attribute__((64)); This could convey more info than padding. Further, I wish, gcc could have provided an attribute that explicitly forces for the cache line alignment than just generic alignment. Generic scalar type alignment is not same as the cache line alignment. Example: Klass sc __attribute__((start_at_cache_line));
- account42 4y agoalignas() has been standard for a decade now.
- psurge 4y ago
- bornfreddy 4y agoIn the fix in the original Netflix blogpost, shouldn't they pad with 56 instead of 64 bytes? Otherwise they are wasting some cache space. I would also expect the fix to reflect the platform it is applicable for, but maybe they simplified it for the blog post...
- stingraycharles 4y agoYou’re correct as far as I know, and now I wonder why the Netflix people didn’t elaborate on this choice.
- eric4smith 4y agoSlightly off topic... Back before my Phoenix/Elixir days, we used to have to cache almost everything. Now we don't cache anything -- even with more traffic and less servers. Now, the projects I work on are not getting millions of views every day. But they are still important for many customers. We don't really design anything that needs to be cached anymore. Just better access patterns and table design as we get wiser. Take Wordpress as an example. There really should not be a need to cache a Wordpress site. But some of the most popular plugins are those that cache. To be fair, I suppose, their legacy non-optimal database design access pattern and code is responsible for this. Just getting something up and aiming for product-market fit is priority #1 and then struggling with caching if it gets popular, at which point, more resources can be thrown at it.
- withinboredom 4y agoWordPress by itself isn’t so bad. It’s the plugin/theme developers who likely have no idea what they’re doing or why what they’re doing is bad.
- andai 4y agoMy client is running 21 plugins :(
- withinboredom 4y agoAt Automattic, I think the mu-plugins folder for WordPress.com had at least a hundred directories and at least another count's worth of the same in files. It was massive.
- taskforcegemini 4y agoJust throwing more ressources at it will make your hosting company happy. I am working for one, so I will not disagree with you. If I were to mention its name, I would though, since a lot of what we do is help our clients to make their webapplications run more efficently (and thus saving them a lot of money in the long run).
- 4y ago
- beambot 4y agoIt has earned its title as "one of the two hardest problems in computer science": cache invalidation, naming things, and off-by-one errors.
- jdthedisciple 4y agothe multiple layers of irony in this one just always amaze me
- mklepaczewski 4y agoYou may also like this one (from https://twitter.com/mathiasverraes/status/632260618599403520 https://twitter.com/mathiasverraes/status/632260618599403520): There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery
- moring 4y agoIMHO off-by-one errors only deserve to be there for the irony. In reality, they are orders of magnitude easier then the other two.
- samsquire 4y agoRecommend reading about CPU cache coherence protocols such as MESI https://en.m.wikipedia.org/wiki/MESI_protocol https://en.m.wikipedia.org/wiki/MESI_protocol
- _8j50 4y agoCache invalidation really sounds to me like a math problem. Instead of a Processor, let's say it is a jewel store with limited display space at the front of the store and a lot of inventory in the back, instead of cache misses you have window shoppers and walk-ins that won't engage with sales staff or have limited time so you have lost sales/customer and a catch hit is the opposite of that. At what point so you invalidate a jewel displayed at the front to rotate it with an inventory item? Let's also assume customers buy multiple jewels if the same type and will not buy in less quantities than they desire or wait for staff to get more at the back because you have a competing store across the street. Is that about right the way I described the problem? If so, this really might be a math problem like the travelling sales man, not exclusive to compsci.
- darkerside 4y agoIt's CS, they are all math problems
- ysleepy 4y agoWhat you are talking about is not really cache invalidation but a cache algorithm/policy. Invalidation means to remove a potentially inconsistent element from the cache, like after the original or a part of the inputs of the function were changed. Both problems are important with huge effects, but different.
- canarypilot 4y agoI like a good analogy challenge, let me try to shape something around your framework! We sell particularly high-value, unique jewels, that are seated in jewellery. In fact, our jewels are so valuable to us, that our stores are able to modify the case around the jewel even before they sell to a customer. Each customer will be offered the last casing the jewel was in, and be given the opportunity to change it - though they might still choose not to buy. We have a set of stores that we can sell from, and of course only one store can have the jewel in it at a time. We’re losing customers by only having the local stock available to sell, so we instigate a new policy; every store takes a picture of the casing for the jewel when they have it in store, they can show this last copy of the jewel in their catalogue. If a customer wants the jewel from the catalogue, we call around the other stores asking for the physical jewel to be brought to us. This works well a lot of the time, but we find a new problem. Sometimes the customer really liked the casing the jewel was in for the photograph in the catalogue, but when the physical jewel arrives the casing has changed. The customer mutters something about false advertising and storms out disgusted by the stale photo shown. So we add a new policy. If a store changes the casing for a jewel it has to send a picture to every other store of the new casing so they can all update their catalogues. Well! Now we have chaos! Every store owner is so busy updating catalogues and sending pictures around the other stores that they’re getting less real work done. We look at our catalogue, sometimes we’re updating the same page many times without a customer even seeing it! So we come up with a new policy - instead of immediately changing the catalogue when we get told that another store has changed the physical jewel, we’re just going to mark the catalogue page as out of date. If eventually a customer asks to see that jewel, we’ll apologise to them for the wait, we’ll ask the other stores who has the jewel right now, then we’ll go get the physical jewel from them, take a picture for our catalogue, and show it to the customer. (As a minor optimisation, if we think the customer will want to change the casing we’ll politely inform the store we picked it up from that they can now mark their catalogue out of date). It is all going well, but there’s a lot of overhead in our catalogue with only one jewel per page, so we start putting multiple jewels on each page. That makes our catalogue page update a bit difficult so we declare that a store must always collect all physical jewels for any given catalogue page. One day we find that two stores are sending the same two jewels backwards and forwards all day. We investigate and find that the two jewels are on the same catalogue page, one jewel is being changed by a particularly indecisive customer in one store, and the other is being change by an equally determined customer in the other store. Neither cares about the jewel the other is trying to change, but both customers are getting frustrated by the wait as our policy requires both jewels in the same location before an update can be made. The store managers bemoan ever putting the two jewels on the same page to create this false sharing nightmare. They agree that even if wasteful, for these particular jewels they’ll leave blank space in the catalogue, the two jewels land on different pages, and the shuffling of jewels between stores stops.
- pclmulqdq 4y agoNetflix and others are discovering one of the reasons why I think one socket servers are the future. Single sockets are big enough for almost every workload, and come with a ~10% perf uplift from not having inter-socket cache coherence nonsense.
- pdpi 4y agoModern x86 CPUs typically have three layers of caching, where L1 and L2 are per-core, and only L3 is shared across all cores. You still have to solve all the cache coherency issues, and everything in the article still applies, even with just one socket.
- pclmulqdq 4y agoWhile that is true, and AMD CPUs are even worse thanks to chiplets, the latency and bandwidth of the inter-chip cache coherent interconnect is a lot worse than the on-chip (or on-socket in AMD's case) buses. That is the expensive part of it. Cache line sharing (false and true sharing) still hurts in 1S configurations, but it hurts a lot less.
- pmarreck 4y agoIsn't anything functional (i.e. its computation only depends on its known inputs/input state) inherently trivially cacheable by hashing the input state?
- ysleepy 4y agoYes, but most use-cases are not pure functions.
- osigurdson 4y agoWhat is interesting to me is how cache controllers can signal all other caches when shared data is modified in a single clock cycle.