"deleting unused links" GC phase is too slow

‘LocalStore::removeUnusedLinks’ traverses all the entries in

/gnu/store/.links and calls lstat(2) on each one of them and checks

‘st_nlink’ to determine whether they can be deleted.

There are two problems: lstat(2) can be slow on spinning disks as found

on hydra.gnu.org, and the algorithm is proportional in the number of

entries in /gnu/store/.links, which is a lot on hydra.gnu.org.

Ludo’.

ludo@gnu.org (Ludovic Courtès) skribis:

On Dec. 2 on guix-sysadmin@gnu.org, Mark described an improvement that

noticeably improved performance:

The idea is to read the entire /gnu/store/.links directory, sort the

entries by inode number, and then iterate over the entries by inode

number, calling 'lstat' on each one and deleting the ones with a link

count of 1.

The reason this is so much faster is because the inodes are stored on

disk in order of inode number, so this leads to a sequential access

pattern on disk instead of a random access pattern.

The difficulty is that the directory is too large to comfortably store

all of the entries in virtual memory. Instead, the entries should be

written to temporary files on disk, and then sorted using merge sort to

ensure sequential access patterns during sorting. Fortunately, this is

exactly what 'sort' does from GNU coreutils.

So, for now, I've implemented this as a pair of small C programs that is

used in a pipeline with GNU sort. The first program simply reads a

directory and writes lines of the form "<inode> <name>" to stdout.

(Unfortunately, "ls -i" calls stat on each entry, so it can't be used).

This is piped through 'sort -n' and then into another small C program

that reads these lines, calls 'lstat' on each one, and deletes the

non-directories with link count 1.

Regarding memory usage, I replied:

Really?

For each entry, we have to store roughly 70 bytes for the file name (or

52 if we consider only the basename), plus 8 bytes for the inode number;

let’s say 64 bytes.

If we have 10 M entries, that’s 700 MB (or 520 MB), which is a lot, but

maybe acceptable?

At worst, we may still see an improvement if we proceed by batches: we

read 10000 directory entries (7 MB), sort them, and stat them, then read

the next 10000 entries. WDYT?

Ludo’.

severity 24937 important

Hello!

Here’s a proposed patch that follows your suggestion, Mark, but places

an upper bound on the number of directory entries loaded in memory.

On my laptop, which has ~500k entries in /gnu/store/.links, the result

is something like this (notice the inode numbers in ‘lstat’ calls):

I can’t tell exactly how this affects performance because my machine has

an SSD where this operation takes ~3 seconds on a cold cache. I suspect

it has performance comparable to that of doing all the ‘readdir’ at once

followed by all the ‘lstat’.

Mark, how does that sound?

I’d like to commit it soon if there are no objections.

Thanks,

Ludo’.

ludo@gnu.org (Ludovic Courtès) writes:

I think we should sort the entire directory using merge sort backed to

disk files. If we load chunks of the directory, sort them and process

them individually, I expect that this will increase the amount of I/O

required by a non-trivial factor. In each pass, we would load blocks of

inodes from disk, almost all of which are likely to be present in the

store and thus linked from the directory, but in this scheme we will

process only a small number of them and drop the rest on the floor to be

read again in the next pass. Given that even my fairly optimal

implementation takes about 35 minutes to run on Hydra, I'd prefer to

avoid multiplying that by a non-trivial factor.

Why not just use GNU sort? It already exists, and does exactly what we

need.

If you object to using an external program for some reason, I would

prefer to re-implement a similar algorithm in the daemon.

Thanks,

Mark

Mark H Weaver <mhw@netris.org> skribis:

Sure, though it’s not obvious to me how much of a difference it makes;

my guess is that processing in large chunks is already a win, but we’d

have to measure.

Does ‘sort’ manage to avoid reading whole files in memory? If not, I

think it wouldn’t buy us anything to use it.

Yeah, I’d rather avoid serializing the list of file names/inode number

pairs just to invoke ‘sort’ on that.

Also, what algorithm are you referring to?

Thanks for the quick feedback!

Ludo’.

ludo@gnu.org (Ludovic Courtès) writes:

I agree, it would surely be a win. Given that it currently takes on the

order of a day to run this phase on Hydra, if your proposed method takes

2 hours, that would be a huge win, but still not good, IMO. Even 35

minutes is slower than I'd like.

Yes, it does. I monitored the 'sort' process when I first ran my

optimized pipeline. It created about 10 files in /tmp, approximately 70

megabytes each as I recall, and then read them all concurrently while

writing the sorted output.

My guess is that it reads a manageable chunk of the input, sorts it in

memory, and writes it to a temporary file. I guess it repeats this

process, writing multiple temporary files, until the entire input is

consumed, and then reads all of those temporary files, merging them

together into the output stream.

Sure, I agree that it would be better to avoid that, but IMO not at the

cost of using O(N) memory instead of O(1) memory, nor at the cost of

multiplying the amount of disk I/O by a non-trivial factor.

The algorithm I described above, which I guess is close to what GNU sort

does.

Thanks,

Mark

Mark H Weaver <mhw@netris.org> skribis:

Of course.

I did some measurements with the attached program on chapters, which is

a Xen VM with spinning disks underneath, similar to hydra.gnu.org. It

has 600k entries in /gnu/store/.links.

Here’s a comparison of the “optimal” mode (bulk stats after we’ve

fetched all the dirents) vs. the “semi-interleaved” mode (doing bulk

stats every 100,000 dirents):

Semi-interleaved is ~12% slower here (not sure how reproducible that is

though).

OK. That seems to be that the comment above ‘sortlines’ in sort.c

describes.

Understood.

sort.c in Coreutils is very big, and we surely don’t want to duplicate

all that. Yet, I’d rather not shell out to ‘sort’.

Do you know how many entries are in .links on hydra.gnu.org? If it

performs comparably to chapters, the timings suggests it should have

around 10.5M entries.

Thanks!

Ludo’.

#include <unistd.h>

#include <dirent.h>

#include <sys/types.h>

#include <stdlib.h>

#include <stdio.h>

#include <sys/time.h>

#include <string.h>

#include <sys/stat.h>

#include <assert.h>

#define STAT_INTERLEAVED 1

#define STAT_SEMI_INTERLEAVED 2

#define STAT_OPTIMAL 3

struct entry

{

char *name;

ino_t inode;

};

#define MAX_ENTRIES 1000000

static struct entry dir_entries[MAX_ENTRIES];

int

main ()

{

struct timeval start, end;

/* For useful timings, do:

sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches' */

gettimeofday (&start, NULL);

DIR *links = opendir ("/gnu/store/.links");

size_t count = 0;

#if MODE != STAT_INTERLEAVED

void sort_entries (void)

{

int entry_lower (const void *a, const void *b)

{

return ((struct entry *)a)->inode < ((struct entry *)b)->inode;

}

qsort (dir_entries, count, sizeof (struct entry),

entry_lower);

}

#endif

void stat_entries (void)

{

for (size_t i = 0; i < count; i++)

{

struct stat st;

lstat (dir_entries[i].name, &st);

}

}

for (struct dirent *entry = readdir (links);

entry != NULL;

entry = readdir (links))

{

assert (count < MAX_ENTRIES);

dir_entries[count].name = strdup (entry->d_name);

dir_entries[count].inode = entry->d_ino;

#if MODE == STAT_INTERLEAVED

struct stat st;

lstat (entry->d_name, &st);

#endif

#if MODE == STAT_SEMI_INTERLEAVED

if (count++ >= 100000)

{

sort_entries ();

stat_entries ();

count = 0;

}

#else

count++;

#endif

}

#if MODE == STAT_SEMI_INTERLEAVED

sort_entries ();

stat_entries ();

#endif

gettimeofday (&end, NULL);

printf ("%zi dir_entries, %zi seconds"

#if MODE != STAT_OPTIMAL

" (including stat)"

#endif

"\n", count,

end.tv_sec - start.tv_sec);

#if MODE == STAT_OPTIMAL

sort_entries ();

gettimeofday (&start, NULL);

stat_entries ();

gettimeofday (&end, NULL);

printf ("stat took %zi seconds\n", end.tv_sec - start.tv_sec);

#endif

return EXIT_SUCCESS;

}

Do as you wish. I don't have time to continue discussing this.

Mark

ludo@gnu.org (Ludovic Courtès) writes:

I just want to point out that 600k inodes use 150 megabytes of disk

space on ext4, which is small enough to fit in the cache, so the disk

I/O will not be multiplied for such a small test case.

This directory you're testing on is more than an order of magnitude

smaller than Hydra's when it's full. Unlike in your test above, all of

the inodes in Hydra's store won't fit in the cache.

In my opinion, the reason Hydra performs so poorly is because efficiency

and scalability are apparently very low priorities in the design of the

software running on it. Unfortunately, I feel that my advice in this

area is discarded more often than not.

Also, see https://en.wikipedia.org/wiki/External_sorting. This is a

well-studied problem with a long history.

I'm fairly sure that the overhead of serializing the file names and

inode numbers is *far* less than the overhead you would add by iterating

over the inodes in multiple passes.

The "shell" would not be involved here at all, just the "sort" program.

I guess you dislike launching external processes? Can you explain why?

Guix-daemon launches external processes for building derivations, so why

is using one for garbage collection a problem? Emacs, a program that

you cite in your talks as having many qualities that we seek to emulate,

does not shy away from using external programs.

"df -i /gnu" indicates that it currently has about 5.5M inodes, but

that's with only 29% of the disk in use. A few days ago, when the disk

was full, assuming that the average file size is the same, it may have

had closer to 5.5M / 0.29 ~= 19M inodes, which is over 30 times as many

as used in your measurements above. On ext4, which uses 256-byte

inodes, that's about 5 gigabytes of inodes.

Mark

Hello Mark,

Mark H Weaver <mhw@netris.org> skribis:

Right. That’s the only spinning-disk machine I could access without

problem. :-/

Ricardo, Roel: would you be able to run that links-traversal.c from

on a machine with a big store, as described at

https://debbugs.gnu.org/cgi/bugreport.cgi?bug=24937#25?

Good point. I’m trying my best to get performance figures, there’s no

doubt we could do better!

Well, as you know, I’m currently traveling, yet I take the time to

answer your email at night; I think this should suggest that far from

discarding your advice, I very much value it.

I’m a maintainer though, so I’m trying to understand the problem better.

It’s not just about finding the “optimal” solution, but also about

finding a tradeoff between the benefits and the maintainability costs.

I find that passing strings around among programs is inelegant

(subjective), but I don’t think you’re really looking to argue about

that, are you? :-)

It remains that, if invoking ‘sort’ appears to be preferable *both* from

performance and maintenance viewpoints, then it’s a good choice. That

may be the case, but again, I prefer to have figures to back that.

OK, good to know.

Thanks!

Ludo’.

Ludovic Courtès <ludo@gnu.org> writes:

I just ran this on my workstation in the office where I regularly build

packages. Here’s the output of “df -i /gnu”

Filesystem Inodes IUsed IFree IUse% Mounted on

/dev/mapper/fedora-root 3301376 1098852 2202524 34% /

Probably not large enough to derive conclusions about hydra’s behaviour.

[I can’t run it on the shared store at the MDC because NFS performance is

too poor. I recently ran “guix gc --optimize” to dedupe the shared

store (post-build deduplication is disabled since a few weeks) and it’s

at 3,197,489 used inodes.]

Here are the results of running the link-traversal code on my

workstation:

--

Ricardo

I apologize for losing my patience earlier.

Mark

Ricardo Wurmus <ricardo.wurmus@mdc-berlin.de> writes:

I ran this for the first time on ci.guix.gnu.org, which has a very big

store (currently at around 29TB).

df -i /gnu:

Filesystem Inodes IUsed IFree IUse% Mounted on

/dev/sdb1 610021376 132350406 477670970 22% /gnu

I had to increase the number of MAX_ENTRIES to 135000000.

I forgot to drop caches initially. This is the first run:

I aborted the run after I dropped caches after 67 minutes.

I’m going to continue testing on one of the build nodes, and I’ll try

using statx.

--

Ricardo

Here are more benchmarks on one of the build nodes. It doesn’t nearly

have as many used inodes as ci.guix.gnu.org, but I could fill it up if

necessary.

root@hydra-guix-127 ~# df -i /gnu/

Filesystem Inodes IUsed IFree IUse% Mounted on

/dev/sda3 28950528 2796829 26153699 10% /

root@hydra-guix-127 ~# ls -1 /gnu/store/.links | wc -l

2017395

I tested all three modes with statx and with lstat. The

links-traversal-statx.c is attached below.

Now with just lstat:

They are all very close, so I think I need to work with a bigger store

to see a difference.

Or perhaps I did something silly because I don’t know C… If so please

let me know.

--

Ricardo

Hi Ricardo,

Thanks for running this benchmark!

Ricardo Wurmus <rekado@elephly.net> skribis:

That’s not a lot, my laptop has 2.8M links.

It’s interesting to see that system time remains at ~4.2s in all modes.

So the only thing that modes 2 and 3 achieve is increasing CPU time.

It’s as if the order in which files are stat’d had no impact on I/O

performance.

Ludo’.

Ludovic Courtès <ludo@gnu.org> writes:

Let me rerun this after copying a few thousand store items from

ci.guix.gnu.org over. Maybe we’ll see the different times diverge then.

--

Ricardo

Hi!

ludo@gnu.org (Ludovic Courtès) skribis:

Taking a step back, we could perhaps mitigate this with heuristics to

reduce the number of entries in .links:

1. Do not deduplicate files with a size lower than some threshold;

2. Delete links with st_nlink <= 3 (instead of <= 2); that would

prevent *further* deduplication of those files, but they’d already

have two instances sharing the same inode;

3. Stop deduplicating once the number of entries in .links has reached

a certain threshold.

For #1, a key insight is that about 30% of the files actually

deduplicated (in my store, where /gnu/store/.links has 2.2M entries) are

smaller than 1 KiB:

… but 85% of them have at most 4 links (thus, saving up to 2 KiB by

deduplicating):

On my laptop, we’re talking about space savings of 325 MiB, a tiny

fraction of my store:

Files smaller than 1 KiB represent 35% of the entries in .links:

By not deduplicating files smaller than 1 KiB, we’d reduce the number of

entries by 35%, which should already have a tangible impact on

performance. It’d be a “mitigation” more than a “fix”, but it has a

good work/reward ratio.

We could conduct a similar analysis for #2.

#3 is more difficult to implement because you cannot know the number of

entries in .links until you’ve traversed it (note that currently

deduplication stops when link(2) returns ENOSPC in .links).

I’m attaching the script I’ve used for that, derived from an earlier

experiment¹. You’re welcome to give it a spin!

Thoughts?

Ludo’.

¹ https://lists.gnu.org/archive/html/guix-devel/2014-09/msg00422.html

Ludovic Courtès <ludo@gnu.org> skribis:

For files < 4 KiB, the savings are ~2 GiB, roughly 1% of my store.

Ludo’.

Hi Ludovic,

I haven't done any analysis, just grabbed the result, but here it what

it looks for me:

That's for 3631356 links.

Thank you!

Maxim

Hi,

Maxim Cournoyer <maxim.cournoyer@gmail.com> skribis:

There’s a bit more than 35% of deduplicated files that are < 1KiB, and

not much to be gained by deduplicating them.

On IRC several people shared the results on their machine; several had

similar results, and one person had a lot more of those small files (50%

of deduplicated files were < 1KiB).

The chart (with a kinda bogus layout) below is perhaps more interesting:

it shows the contribution of files below a certain size to the overall

space savings.

In a nutshell:

• Files < 1KiB contribute to 0.3% of the space savings;

• Files < 4KiB contribute to 2.5% of the space savings;

• Files < 256KiB contribute to 42% of the space savings.

You can create this plot with:

You can also compute individual points like this:

Choosing a deduplication threshold of 2KiB or 4KiB would have a

negligible impact on disk usage on my machine.

Thanks,

Ludo’.

patch comparing inode numbers.

'file=?' procedure and use the one from (guix tests).

---

guix/tests.scm | 30 +++++++++++++++++-------------

tests/gexp.scm | 11 +++--------

2 files changed, 20 insertions(+), 21 deletions(-)

Files smaller than 4 KiB typically represent ~60% of the entries in

/gnu/store/.links but only contribute to ~2.5% of the space savings

afforded by deduplication.

Not considering these files for deduplication speeds up file insertion

in the store and, more importantly, leaves 'removeUnusedLinks' with

fewer entries to traverse, thereby speeding it up proportionally.

Partly fixes https://issues.guix.gnu.org/24937.

definition.

variable.

(deduplicate)[loop]: Do not recurse when FILE's size is below

%DEDUPLICATION-MINIMUM-SIZE.

(dump-port): New procedure.

(dump-file/deduplicate)[hash]: Turn into...

[dump-and-compute-hash]: ... this thunk.

Call 'deduplicate' only when SIZE is greater than

%DEDUPLICATION-MINIMUM-SIZE; otherwise call 'dump-port'.

st.st_size < deduplicationMinSize.

(LocalStore::optimisePath_): Return when PATH is a symlink or smaller

than 'deduplicationMinSize'.

files bigger than %DEDUPLICATION-MINIMUM-SIZE.

Likewise.

New test.

("deduplicate", "deduplicate, ENOSPC"): Produce files bigger than

%DEDUPLICATION-MINIMUM-SIZE.

---

config-daemon.ac | 11 -------

guix/store/deduplication.scm | 57 ++++++++++++++++++++++++++++------

nix/libstore/gc.cc | 4 ++-

nix/libstore/local-store.hh | 3 ++

nix/libstore/optimise-store.cc | 15 +++++----

tests/derivations.scm | 14 ++++++---

tests/nar.scm | 7 +++--

tests/store-deduplication.scm | 41 ++++++++++++++++++++----

tests/store.scm | 4 ++-

9 files changed, 114 insertions(+), 42 deletions(-)

Ludovic Courtès <ludo@gnu.org> skribis:

I get similar results on bayfront.guix.gnu.org (with 3.2M entries):

… and on guix.bordeaux.inria.fr (2.0M entries):

Files < 4KiB represent between 60% and 75% of the /gnu/store/.links

entries here.

I’ve sent patches that implement a cutoff threshold at 4 KiB.

Thanks,

Ludo’.

Hi,

Ludovic Courtès <ludo@gnu.org> skribis:

Pushed a variant of this as commit

472a0e82a52a3d5d841e1dfad6b13e26082a5750, with a threshold of 8 KiB.

Concretely, the number of .links entries shrinks by ~70%, from

2M to 700K on my laptop, and (presumably) from 64M to 19M on berlin.

I’ll deploy it within a few days on berlin. I hope the speedup will

reduce pressure there, though obviously it’ll still be an expensive

operation (but fundamentally I think it’ll always be linear in the size

of the store.)

I’m preparing an update of the ‘guix’ package to make this readily

available. When you deploy the new daemon, .links will be trimmed of

entries for files smaller than 8 KiB the first time you run ‘guix gc’.

Ludo’.

Hello,

A little late, but wanted to add my results here, from before the commit was made. I had reported some of this on IRC before and had some outlying results. Since then I finally did some generation deleting and gc-ing, though perhaps still have a bit of cruft. I've been on core-updates-frozen for a while, so keeping a lot from before making the branch switch, as well as lots of stuff piling up in trying to fix things or trying out changes in core-updates-frozen.

Anyway, attached are the plots from the above code. Running

ls -1A /gnu/store/.links | wc -l

showed 15776256 links at the time. Still quite a bit I think, but I've had 1.5-2x as much in the past, easily. (This had caused some earlier warnings on ext4 and enabling large_dir, which will make a system unbootable due to Grub not being up to speed on this old feature. I'm now on btrfs.)

John