6 ms·

Negative dentries, 20 years later

63 points by bitcharmer 5y ago

PaulHoule 5y ago
... hmmm, makes me want to write a script that looks up 5 files that aren't there in every directory in the system.
- zokier 5y ago
  something like? find / -type d -exec sh -c 'for i in $(seq 5); do stat {}/"$(head -c 15 /dev/urandom | base32)" 2> /dev/null; done' \;
alyandon 5y ago
So much fun it is to have multiple servers with 1.5 TB of ram slowly fill up with negative cache dentries to the point that the server kernel finally decides that memory pressure is a thing and purges the negative entries all at once - which results in the server being locked up and unresponsive for about ~3 minutes. Oh yeah, and no tunables to control the negative dentry specific behavior.
- throwaway2048 5y ago
  In general the linux kernel seems extremely badly behaved under ram pressure, see how it reacts to swapping.
  - alyandon 5y ago
    It wasn't even actual ram pressure - there was ~500 GB of unused ram but something like 800 GB or so of negative cache dentries. So, it was over some threshold that the kernel decided it was time to start reclaiming all those entries and locked up the entire server while it was doing so. Madness.
bjourne 5y ago
How could a process accumulate hundreds of negative dentries during normal operation? If that happens something fishy is going on.
- pdonis 5y ago
  The third paragraph in the article addresses this. Most of the negative dentries a process generates are going to be invisible to the user.
  - Groxx 5y ago
    Yeah, my immediate thought was of stuff like "ask nginx to give me this misspelled webpage" -> look up that file -> bam, dentry. Expose practically anything on the internet that leads to a piece of user input causing a filesystem operation (which is going to be extremely common and often unavoidable), and "hundreds" isn't the concern. Millions to billions is.
    - bjourne 5y ago
      That's what I meant with "fishy". If nginx fills up your negative dentry cache with millions to billions of misspelled urls you are being dos:ed.
      - pdonis 5y ago
        What if your C compiler fills up your negative dentry cache during, say, a kernel compile, because it's looking for a huge number of include files that don't exist, since the C preprocessor uses a very simplistic algorithm to decide where it needs to look for include files? (This is one of the examples in the paragraph in the article that I referred to.)
        bjourne 5y ago
        Even in the worst case, that shouldn't amount to more than a few thousand files. Millions of missing include files is unrealistic.
pdonis 5y ago
Aren't there already well-tested LRU cache algorithms out there? It seems like adapting one of those to the general problem of kernel cache management would be a good way to address the general problem described in the article.
- Groxx 5y ago
  tbh this was my thought too. No need for background processing either, there are quite a few options for amortized-constant-time old-value deletion at lookup time. Or do that cleanup while checking the disk on a cache miss - if you have no misses, the cache is working fantastically and probably shouldn't be pruned. Or is there some reason those aren't acceptable in-kernel, while apparently a lack of cleanup is fine? Maybe CPU use is too high...?
- tedunangst 5y ago
  And how many entries will you keep in the LRU?
- MBCook 5y ago
  LRU works by by using a specific cache size. How big should that be? Will that number work for small microcontrollers and giant servers? Is that per disc? Per directory? Per system? Per kernel? Should that size expand and contract overtime somehow? The article gets into a little bit of that stuff, but they’re all real problems.
  - pdonis 5y ago
    Sure, I get that there are still decisions to be made, but the discussion in the article makes it seem like nobody has even thought of using an LRU cache and then having a discussion about how to tune the cache size.
  - zaphirplane 5y ago
    There is a million configurable variables already this can be another Not me I’m watching Netflix :)
jjoonathan 5y ago
NXDOMAIN caching has been the bane of my existence recently and I have been meaning to survey how other cache implementations deal with the problem. Looks like everyone suffers from it. I've heard edgy teenagers say that existence is suffering, but I suppose caches teach us that non-existence is suffering too.
- trashcan 5y ago
  NXDOMAIN at least has a TTL so it will not grow forever. What problem are you referring to, not being able to invalidate a cached NXDOMAIN? Or something else?
  - jjoonathan 5y ago
    Yeah, well, if the TTL in the SOA were being respected it wouldn't be a problem. Tomorrow we're going to run some experiments to find out which godforsaken layer of "smart" infrastructure is responsible.
Archelaos 5y ago
"It's hard to ... design a heuristic for an acceptable amount of negative dentries: it won't scale from small to large systems well" Has an AIMD algorithms[1] been considered to dynamically adjust the limit? [1] https://en.wikipedia.org/wiki/Additive_increase/multiplicative_decrease https://en.wikipedia.org/wiki/Additive_increase/multiplicati...
bawolff 5y ago
> "Repeated file-name lookups are common — consider...~/.nethackrc" Lol, <3 LWN
jdub 5y ago
My favourite interaction with negative dentries was with PHP's curl library, built with NSS for encryption. NSS would do some kind of filesystem performance check, intentionally opening lots of files that didn't exist. At one point, every server in a large autoscaling group was spending 10GB EACH just on the dentry cache. :-) https://twitter.com/jdub/status/875570760361811973 https://twitter.com/jdub/status/875570760361811973
cespare 5y ago
I became intimately familiar with negative dentries while debugging a slow service deploy a few years ago. A deploy that was normally very fast would sometimes hang for a few minutes during a phase where all it had to do was delete the old application directory and move the new one into place. Turned out that the application was writing a bunch of tempfiles into the cwd and then immediately deleting them. Nothing ever touched that directory while the negative dentries accumulated for weeks or months. When someone finally deployed, the first rmdir that came along bore the cost of deleting all those negative dentries. It hung for seconds or minutes while the kernel essentially cleared out the entire dcache, deleting linked list elements one by one. It showed up in perf as being stuck inside shrink_dcache_parent. This is actually easy to reproduce: $ mkdir /tmp/foo $ touch /tmp/nodelete # create and delete 100k files $ for i in $(seq 1 10); do bash -c 'for i in $(seq 1 10000); do rm $(mktemp /tmp/foo/XXXXXX); done' &; done; wait ... $ time rmdir /tmp/foo rmdir: failed to remove '/tmp/foo': Directory not empty rmdir /tmp/foo 0.00s user 0.02s system 91% cpu 0.024 total $ time rmdir /tmp/foo rmdir: failed to remove '/tmp/foo': Directory not empty rmdir /tmp/foo 0.00s user 0.00s system 81% cpu 0.003 total Both rmdirs fail, but the first one takes 24ms. If you create and delete more files, it takes longer and longer. At some point we probably would've noticed the memory leak as well (I found an 18 GB slab on one host while this was happening) but the machines in question have huge amounts of ram. I worked around the issue by making the application reuse tempfile names.
- thaumasiotes 5y ago
  > Turned out that the application was writing a bunch of tempfiles into the cwd and then immediately deleting them. > I worked around the issue by making the application reuse tempfile names. Knowing nothing about the issue beyond what you've written here... why not make the application create a directory for its tempfiles, and then remove that directory along with the tempfiles?
  - ungamedplayer 5y ago
    additionally, there may be a security issue in reusing temporary filenames.
  - 5y ago

63 points by bitcharmer 5y ago

PaulHoule 5y ago

... hmmm, makes me want to write a script that looks up 5 files that aren't there in every directory in the system.

zokier 5y ago
something like? find / -type d -exec sh -c 'for i in $(seq 5); do stat {}/"$(head -c 15 /dev/urandom | base32)" 2> /dev/null; done' \;

alyandon 5y ago

So much fun it is to have multiple servers with 1.5 TB of ram slowly fill up with negative cache dentries to the point that the server kernel finally decides that memory pressure is a thing and purges the negative entries all at once - which results in the server being locked up and unresponsive for about ~3 minutes. Oh yeah, and no tunables to control the negative dentry specific behavior.

throwaway2048 5y ago
In general the linux kernel seems extremely badly behaved under ram pressure, see how it reacts to swapping.
- alyandon 5y ago
  It wasn't even actual ram pressure - there was ~500 GB of unused ram but something like 800 GB or so of negative cache dentries. So, it was over some threshold that the kernel decided it was time to start reclaiming all those entries and locked up the entire server while it was doing so. Madness.

bjourne 5y ago

How could a process accumulate hundreds of negative dentries during normal operation? If that happens something fishy is going on.

pdonis 5y ago
The third paragraph in the article addresses this. Most of the negative dentries a process generates are going to be invisible to the user.
- Groxx 5y ago
  Yeah, my immediate thought was of stuff like "ask nginx to give me this misspelled webpage" -> look up that file -> bam, dentry. Expose practically anything on the internet that leads to a piece of user input causing a filesystem operation (which is going to be extremely common and often unavoidable), and "hundreds" isn't the concern. Millions to billions is.
  - bjourne 5y ago
    That's what I meant with "fishy". If nginx fills up your negative dentry cache with millions to billions of misspelled urls you are being dos:ed.
    - pdonis 5y ago
      What if your C compiler fills up your negative dentry cache during, say, a kernel compile, because it's looking for a huge number of include files that don't exist, since the C preprocessor uses a very simplistic algorithm to decide where it needs to look for include files? (This is one of the examples in the paragraph in the article that I referred to.)
      - bjourne 5y ago
        Even in the worst case, that shouldn't amount to more than a few thousand files. Millions of missing include files is unrealistic.

pdonis 5y ago

Aren't there already well-tested LRU cache algorithms out there? It seems like adapting one of those to the general problem of kernel cache management would be a good way to address the general problem described in the article.

Groxx 5y ago
tbh this was my thought too. No need for background processing either, there are quite a few options for amortized-constant-time old-value deletion at lookup time. Or do that cleanup while checking the disk on a cache miss - if you have no misses, the cache is working fantastically and probably shouldn't be pruned. Or is there some reason those aren't acceptable in-kernel, while apparently a lack of cleanup is fine? Maybe CPU use is too high...?
tedunangst 5y ago
And how many entries will you keep in the LRU?
MBCook 5y ago
LRU works by by using a specific cache size. How big should that be? Will that number work for small microcontrollers and giant servers? Is that per disc? Per directory? Per system? Per kernel? Should that size expand and contract overtime somehow? The article gets into a little bit of that stuff, but they’re all real problems.
- pdonis 5y ago
  Sure, I get that there are still decisions to be made, but the discussion in the article makes it seem like nobody has even thought of using an LRU cache and then having a discussion about how to tune the cache size.
- zaphirplane 5y ago
  There is a million configurable variables already this can be another Not me I’m watching Netflix :)

jjoonathan 5y ago

NXDOMAIN caching has been the bane of my existence recently and I have been meaning to survey how other cache implementations deal with the problem. Looks like everyone suffers from it. I've heard edgy teenagers say that existence is suffering, but I suppose caches teach us that non-existence is suffering too.

trashcan 5y ago
NXDOMAIN at least has a TTL so it will not grow forever. What problem are you referring to, not being able to invalidate a cached NXDOMAIN? Or something else?
- jjoonathan 5y ago
  Yeah, well, if the TTL in the SOA were being respected it wouldn't be a problem. Tomorrow we're going to run some experiments to find out which godforsaken layer of "smart" infrastructure is responsible.

Archelaos 5y ago

"It's hard to ... design a heuristic for an acceptable amount of negative dentries: it won't scale from small to large systems well" Has an AIMD algorithms[1] been considered to dynamically adjust the limit? [1] https://en.wikipedia.org/wiki/Additive_increase/multiplicative_decrease https://en.wikipedia.org/wiki/Additive_increase/multiplicati...

bawolff 5y ago

> "Repeated file-name lookups are common — consider...~/.nethackrc" Lol, <3 LWN

jdub 5y ago

My favourite interaction with negative dentries was with PHP's curl library, built with NSS for encryption. NSS would do some kind of filesystem performance check, intentionally opening lots of files that didn't exist. At one point, every server in a large autoscaling group was spending 10GB EACH just on the dentry cache. :-) https://twitter.com/jdub/status/875570760361811973 https://twitter.com/jdub/status/875570760361811973

cespare 5y ago

I became intimately familiar with negative dentries while debugging a slow service deploy a few years ago. A deploy that was normally very fast would sometimes hang for a few minutes during a phase where all it had to do was delete the old application directory and move the new one into place. Turned out that the application was writing a bunch of tempfiles into the cwd and then immediately deleting them. Nothing ever touched that directory while the negative dentries accumulated for weeks or months. When someone finally deployed, the first rmdir that came along bore the cost of deleting all those negative dentries. It hung for seconds or minutes while the kernel essentially cleared out the entire dcache, deleting linked list elements one by one. It showed up in perf as being stuck inside shrink_dcache_parent. This is actually easy to reproduce: $ mkdir /tmp/foo $ touch /tmp/nodelete # create and delete 100k files $ for i in $(seq 1 10); do bash -c 'for i in $(seq 1 10000); do rm $(mktemp /tmp/foo/XXXXXX); done' &; done; wait ... $ time rmdir /tmp/foo rmdir: failed to remove '/tmp/foo': Directory not empty rmdir /tmp/foo 0.00s user 0.02s system 91% cpu 0.024 total $ time rmdir /tmp/foo rmdir: failed to remove '/tmp/foo': Directory not empty rmdir /tmp/foo 0.00s user 0.00s system 81% cpu 0.003 total Both rmdirs fail, but the first one takes 24ms. If you create and delete more files, it takes longer and longer. At some point we probably would've noticed the memory leak as well (I found an 18 GB slab on one host while this was happening) but the machines in question have huge amounts of ram. I worked around the issue by making the application reuse tempfile names.

thaumasiotes 5y ago
> Turned out that the application was writing a bunch of tempfiles into the cwd and then immediately deleting them. > I worked around the issue by making the application reuse tempfile names. Knowing nothing about the issue beyond what you've written here... why not make the application create a directory for its tempfiles, and then remove that directory along with the tempfiles?
- ungamedplayer 5y ago
  additionally, there may be a security issue in reusing temporary filenames.
- 5y ago