Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

My experience with using cp to copy 432 million files (39 TB)

lists.gnu.org

Post reply on HN
Print view View original

121–130 of 267 posts

Re: My experience with using cp to copy 432 million files (39 TB)

#121

Post by Rapzid »

__david__ wrote: post #7
gaius wrote: post #2

I would probably have used tar|tar for this, or rsync.

Rsync has similar issues when you are copying hard links. It has to keep a table of all the inodes/filename pairs it sees so it can detect hard links and relink them on the destination. This can be big if you have a ton of hard links (say in a backup situation). Rsync at least acts reasonably idempotent, so you can just run it again if it gets interrupted, which is usually why I use it for large copies. I don't remem…

Wouldn't it only need to track the inodes with a link count above 1?

Re: My experience with using cp to copy 432 million files (39 TB)

#122

Post by rwg »

Disassembling data structures nicely can take much more time than just tearing them down brutally when the process exits.

A wonderful trend I've noticed in Free/Open Source software lately is proudly claiming that a program is "Valgrind clean." It's a decent indication that the program won't doing anything silly with memory during normal use, like leak it. (There's also a notable upswing in the number of projects using static analyzers on their code and fixing legitimate problems that turn up, which is great, too!)

While you can certainly just let the OS reclaim all of your process's allocated memory at exit time, you're technically (though intentionally) leaking memory. When it becomes too hard to separate the intentional leaks from the unintentional leaks, I'd wager most programmers will just stop looking at the Valgrind reports. (I suppose you could wrap free() calls in "#ifdef DEBUG ... #endif" blocks and only run Valgrind on debug builds, but that seems ugly.)

A more elegant solution is to use an arena/region/zone allocator and place potentially large data structures (like cp's hard link/inode table) entirely in their own arenas. When the time comes to destroy one of these data structures, you can destroy its arena with a single function call instead of walking the data structure and free()ing it piece by piece.

Unfortunately, like a lot of useful plumbing, there isn't a standard API for arena allocators, so actually doing this in a cross-platform way is painful:

• Windows lets you create multiple heaps and allocate/free memory in them (HeapCreate(), HeapDestroy(), HeapAlloc(), HeapFree(), etc.).

• OS X and iOS come with a zone allocator (malloc_create_zone(), malloc_destroy_zone(), malloc_zone_malloc(), malloc_zone_free(), etc.).

• glibc doesn't have a user-facing way to create/destroy arenas (though it uses arenas internally), so you're stuck using a third-party allocator on Linux to get arena support.

• IRIX used to come with an arena allocator (acreate(), adelete(), amalloc(), afree(), etc.), so if you're still developing on an SGI Octane because you can't get enough of that sexy terminal font, you're good to go.

Re: My experience with using cp to copy 432 million files (39 TB)

#123

Post by pflanze »

mrb wrote: post #114
pflanze wrote: post #100

Earlier quoted context omitted.

Let's assume we change your algorithm to use inode+device as key instead of the content hash, to make it behave as it 'should'. > constant RAM Well, definitely not constant space . The only reason for it to use less RAM than the hash table is if it uses disk instead of RAM, and that's what happened in op's post, too, by way of swap. You're trading a hash table implemented in user-space for a hash table or b-tree or s…

In fact, 17e9/432e6=39.35 B/file, pretty spot on. Seems like there's some room for optimization It does not suggest there is a possible optimization. cp needs to store the pointer and the path itself in memory, so it is more than 8 bytes. ~39 bytes/file means the average path length was 15 bytes (8-byte source device + 8-byte source inode + 8-byte pointer + ~15-byte path = ~39 bytes). I guess one theoretical optimiza…

Yes, you're right, I made a jump in my thinking; I wanted to make the point that you could exclude the storage for the paths from the working set size, if there is only rarely a match. Problem is we don't have a number for the working set size (except that it must be between 10 GB and 17 GB), and my brain just used the 17 GB.

But your calculation is missing the empty space in the hash table. When using open addressing (with the table being a flat array), there must be something like 10-30% empty slots (and in any case, twice the space during rehashing). That would leave just about 39.35 - 8 * 3 / 0.8 = 9.35 bytes per path. So, likely cp already optimizes by using per-device hash tables at least, then 39.35 - 8 * 2 / 0.8 = 19.35 bytes will remain for the path. The pointer could be shortened to 5 or perhaps even 4 bytes. Paths could be stored as an 'inverted' tree (linked lists of segments while sharing equal tails), which should be very natural since cp gets them piecewise from readdir anyway, so the 19.35 bytes just need to describe a parent path pointer (5 bytes?) plus some shared storage and the space for the filename.

Probably there are better hash table algorithms for low memory use, too. (Using buckets in arrays (instead of linked lists as is often done), and resize those on every append, trading CPU for space?) I wonder if there's a way to avoid temporary doubling of the hash table storage during resizing.

Edit: I've checked the GNU coreutils-8.23 sources, oddly cp is not using any of those optimizations; it uses both dev and ino as a key, concatenates every filename to its parent path and stores that (and a normal pointer in the table), and uses linked lists for the buckets in its hash tables.

Edit 2: a different solution that should really lower RAM requirements a lot would be to separate the walking of the source tree from the copying. When walking the source tree, just create a list of dev/ino/path; then sort this list according to dev/ino (there are optimized sort algorithms that keep RAM usage small, I remember them being in Knuth's TAOCP); then walk the list, while linking all the paths with the same dev/ino which you will now encounter in a group.

Re: My experience with using cp to copy 432 million files (39 TB)

#124

Post by Rapzid »

angry_octet wrote: post #96
steveh73 wrote: post #78

Earlier quoted context omitted.

"Normally I'd have copied/moved the files at block-level (eg. using dd or pvmove), but suspecting bad blocks, I went for a file-level copy because then I'd know which files contained the bad blocks."

I was simplifying... dump backs up inodes not blocks. Some inodes point to file data and some point to directory data. Hard links are references to the same inode in multiple directory entries, so when you run xfsrestore, the link count increments as the FS hierarchy is restored. xfsdump/zfs send are file system aware, unlike dd, and can detect fs corruption (ZFS especially having extensive checksums). In fact, any i…

If the risk of keeping the system running while the array rebuilt was deemed to high, I would have just gone with a dd/ddrescue of the remaining disks onto new disks and then moved on from there.

+1 for mentioning ZFS. It's really quite amazing. Almost like futuristic alien technology compared to the other freely available file systems.

Re: My experience with using cp to copy 432 million files (39 TB)

#125

Post by derefr »

bakul wrote: post #117
derefr wrote: post #92

Earlier quoted context omitted.

If you cp your data onto a Plan9 machine, what results is pretty much exactly the process you've outlined. Plan9's default filesystem is made up of two parts: Fossil, and Venti. - Fossil is a content-addressable on-disk object store. Picture a disk "formatted as" an S3 bucket, where the keys are strictly the SHAsums of the values. - Venti is a persistent graph database that holds what would today be called "inode met…

1. Plan9 has no hard links so if you copy unix dir. tree to a plan9 machine you'd lose all the hard link info. 2. Venti doesn't use fossil or inodes. Venti is just content addressable storage system; not a fileserver/system. 3. Fossil is a fileserver.

Ah, I was going off an explanation I was given myself at one point--but this makes more sense, thanks.

Re: My experience with using cp to copy 432 million files (39 TB)

#126

Post by otakucode »

craigyk wrote: post #83
LeoPanthera wrote: post #40

Earlier quoted context omitted.

How does the rebuild time of ZFS's raidz compare to RAID5/6?

My largest ZFS pool is currently ~64TB ( 3 X 10 3TB (raidz2) ) The pool has ranged from 85%-95% full (it's mostly at 85% now and used mostly for reads). Resilvering one drive usually takes Something else cool: When I was planning this out I wrote a little script to calculate the chance of failure. With a drive APF of 10% (which is pretty high), and a rebuild speed of 50MB/sec (very low compared to what I typically ge…

What is APF? And why not use the typical URRE rate to calculate your stats?

I'm always mystified at how stupid our storage systems are. Even very expensive SAN solutions from EMC and the like area just... stupid. We've got loads of metrics on every drive, but figuring out that those things should be aggregated and subjected to statistical analysis just seems to have not been done yet.

What I really want is a "pasture" system - a place I can stick old drives of totally random sizes and performance characteristics and have the system figure out where to put the data in order to maintain a specific level of reliability. Preferrably backed by an online database that tracks the drive failure rate of every drive on every deployed system, noting patterns in 'bad batches' of certain models and the like. If one of my drives would have to beat 3-standard-deviations odds to survive for the next week, move the damn data to somewhere better. And if you've got 2 150GB drives and 1 300GB drive, then each block on those drives has a rating of 2.0 - adjusted for the age and metrics of the drive.

Oh well, maybe when I retire in 30 years storage systems will still be as stupid as they've remained for the past 30 years and I'll have another project to add to the pile I don't have time to work on now.

Re: My experience with using cp to copy 432 million files (39 TB)

#127

Post by otakucode »

mjn wrote: post #50
ritchiea wrote: post #43

Earlier quoted context omitted.

Why exactly is it necessary to to free each hash entry instead of exiting the process?

If it's the last thing you do before you exit the process, it isn't necessary, because the OS will reclaim your process's memory in one fell swoop. I believe that's what the linked post is advocating 'cp' should do. (At least on modern systems that's true; maybe there are some exotic old systems where not freeing your data structures before exit causes permanent memory leaks?) It's seen as good C programming practice…

Is cleaning up after yourself memory-wise considered part of the POSIX standard?

Re: My experience with using cp to copy 432 million files (39 TB)

#128

Post by _delirium »

rwg wrote: post #122

Disassembling data structures nicely can take much more time than just tearing them down brutally when the process exits. A wonderful trend I've noticed in Free/Open Source software lately is proudly claiming that a program is "Valgrind clean." It's a decent indication that the program won't doing anything silly with memory during normal use, like leak it. (There's also a notable upswing in the number of projects usi…

Adding some kind of arena-allocation library to both the build & runtime dependencies solely to keep valgrind happy, with no actual improvement in functionality or performance, doesn't seem like a great tradeoff on the software engineering front. I'd rather see work on improving the static analysis. For example if some memory is intended to be freed at program cleanup, Valgrind could have some way of being told, "this is intended to be freed at program cleanup". Inserting an explicit (and redundant) deallocation as the last line of the program just to make the static analyzer happy is a bit perverse.

(That is, assuming that you don't need portability to odd systems that don't actually free memory on process exit.)

Re: My experience with using cp to copy 432 million files (39 TB)

#130

Post by jschwartzi »

robotresearcher wrote: post #87
lgg wrote: post #37

Earlier quoted context omitted.

This is system C the memory is manually managed with malloc(). You can't simply nil the reference and expect GC to come through and clean it for you, you have to issue a free() for each malloc() that was called. While it might be possible to write a custom disposal routine that does that efficiently for the structure, the simpler way is to just use the normal functions you use for removing single items and call it ag…

> You can't simply nil the reference and expect GC to come through and clean it for you This is exactly what happens when your process exits and its private memory space is freed in its entirety. Hence the discussion. There's no need to clean up before exit, except if you want to (i) use a leak checker; or (ii) run on a machine with no MMU.

It's funny that ii is even an issue because Linux does not support platforms without MMUs without some serious modifications.
Post reply on HN