I'd like to be able to capture and validate checksums for large-scale collections of files, typically nested within a complex directory hierarchy.
Does every single file need a checksum? Are there ways to leverage the existing directory structure to, say, validate only a node in the file tree and not necessarily every file within?
The most efficient way to use checksums is to make the computer do it all. Use a filesystem such as ZFS which checksums (actually it uses hashes, which are stronger than a checksum) all data when it's written, and verifies them every time the data is read. Of course, the downside is that ZFS doesn't know when deleting or overwriting a file is a mistake and when it's normal operation, but because ZFS uses copy-on-write semantics for everything, you can use it's snapshotting feature to mitigate the risk.
ZFS can also automatically restore data that fails a hash check by using any redundancy you've set up, whether raid5-style parity, drive mirrors or duplicate copies (add the copies=N property to any ZFS filesystem and it'll store N copies of any data you write). It also stores the hashes in a Merkle tree, where the hash value of a file depends on the hashes of the blocks, the hash of a directory entry depends on the hash values of the files and directories it contains, the hash of a filesystem depends on the hash of the root directory, etc.
Regardless of what solution you end up with, you'll invariably find that the process is limited by the speed of your disks, not by the speed of your CPU.
Also, don't forget to take into account the BER of your disks. They are, after all, mere plates of spinning rust. A consumer-level drive has a an error rate of 1 incorrectly-read bit for every 10^14 bits read, which works out to 1 bit out of every 11 terabytes you read. If you have an 11 terabyte data set and you compute the hash of every file in it, you will have computed one of those checksums incorrectly and permanently damaged one block of one of the files in the data set. ZFS, however, knows the hash of every block it wrote to every disk in your pool, and therefore knows which block was lost. It can then use the redundancy (parity, mirrors or extra copies) in your pool to rewrite the data in that block with the correct values. These safety features also apply when you use zfs send or receive to copy data from your primary system to the backups.
Ben brings up a good point in the comments however. ZFS doesn't expose any of the hash values that it computes to the user, so data that enters or leaves a ZFS system should be accompanied by hashes. I like the way the Internet Archive does this with an xml file that accompanies every item in the archive. See https://ia801605.us.archive.org/13/items/fakebook_the-firehouse-jazz-band-fake-book/fakebook_the-firehouse-jazz-band-fake-book_files.xml as an example.
Maybe this is a good time to bring up BagIt. This is a very simple yet powerful file packaging format intended for archiving, long term preservation, and transfer of digital objects. Users include the Library of Congress and the California Digital Library.
A BagIt tool (they exist in several programming languages) puts your files into a certain directory structure and does the checksumming/hashing for you. That is all.
PS: Of course, BagIt tools can also verify bags against the included checksums/hashes, and you can add some metadata to bags. But that's as complex as bags get.
I would generate checksum for each file. Checksums are very small, and generating checksum for the whole directory would require you to process every file as well (at least if you are not speaking about directory checksum, made only from directory entries - I would make them as well, to ensure no data is deleted).
Assume you have one checksum for the whole archive. You know the data is corrupted, but you don't know if this is only one file, and, more important, which of them. Having separate checksums give you more flexibility. You can detect single file that is corrupted, and replace it from the file from other backup (which can, in turn, have other file corrupted).
In that way your data is more likely to survive.
This answer is a combination of that of @lechlukasz and @db48x, also incorporating some points made in comments as well as some of my own thoughts.
The simple path forward is a combined file-system and separate-metadata approach.
By using a file system that does on-the-fly data hashing and validation, such as ZFS or Btrfs (do note that although great advances have been made, Btrfs is not considered ready for production use at this time), you can be reasonably sure that if the data can be read off the disk without the operating system erroring out, then the data read was written to disk in the way intended by the file system. By running periodic "scrub" operations, all data is read and verified against the file system's idea of what it should be.
However, that only protects against on-disk corruption (unreadable blocks, outright hardware write errors, invalid writes that corrupt parts of the data directly on the block device, etc.). It does not protect against a software bug, incorrect user operation, or malicious software which works through the intended operating system facilities for working with files, assuming that those facilities are free of such bugs.
To protect against the latter, you need another layer of protection. Checksumming or hashing data from a user application's perspective will help protect against many of the above-mentioned risks, but needs to be performed separately (either as a built-in process action in the software, or as a completely separate process).
With today's hardware and what's practical for storing large amounts of data (spinning platter hard disks as opposed to solid-state disks/SSDs), even complex hashing algorithms such as SHA1 will be largely I/O-bound -- that is, the speed at which the data is hashed will be a function of the storage system's read speed, rather than the ability of the computer's processor to calculate the hash. I did an experiment with running a user-space MD5 hashing process over approximately 150 GB of data on what in 2012 was a mid-tier consumer PC, and it finished after exercising the disk basically without interruption for about 40 minutes. Scaling those figures up 100-fold, you'd get the MD5 hashes of a 15 TB collection in about three days' time on that same hardware. By adding read transfer rate (which can be easily accomplished e.g. using RAID; RAID 0 for example is striping without redundancy, commonly used to achieve higher read/write performance possibly in combination with RAID 1 forming RAID 10), the time to completion can be lowered for the same amount of data.
By combining the two, you get the best of both worlds: the file system gives you assurance that what you received when reading the file is what was actually written, and a separate fixity-checking process can run over the entire collection ensuring that the data stored still matches what was ingested into the archive. Any inconsistency between the two (file system says the file is OK, fixity checking says it's not) will indicate a file that has been modified outside of the archive's intended mode of operation but from within the operating system's facilities, prompting a restore from a secondary copy (backup). The fixity check can thus run at a longer time interval, which becomes essential for very large archives, but any online accesses are still guaranteed to not be corrupted on the hardware if the reads succeed. In principle, the archive software could rely on the file system to report inconsistencies as read errors, and perform a separate fixity check in the background as the user is working with the file and displaying an appropriate message should that indicate that the file does not match what was ingested into the archive. Using a block-hashing file system, such a scheme would have minimal impact on perceived performance while still providing assurance that the content is correct.
I've gone through the answers, and even though I like the idea of relying on ZFS to handle the data-layer errors, there's still the problem of the files getting changed, either by mistake or maliciously. ZFS won't protect you in that case, and like somebody else mentioned, it won't give you the a user-viewable "hash" to store somewhere else for external validation.
There's a Linux application called TripWire that was used extensively for monitoring system executables, to validate they haven't been changed after an attack. That project is apparently now abandoned, but there's a new one called AIDE (Advanced Intrusion Detection Environment), recommended over on ServerFault:
https://serverfault.com/questions/62539/tripwire-and-alternatives
When you install, it would run every x minutes, user-configurable, and it would check all the folders you specify for changes in the files. It needs to run once to calculate all the file hashes, and then after that, it checks all the hashes against the current file, and makes sure they're still the same. You can specify which type of hash or combination of hashes to use (I wouldn't recommend anything weaker than SHA-256), which file attributes to use (contents, size, modified timestampst, etc), the frequency at which it checks, how/where to store the hash database, etc.
Some might consider this overkill, but depending on the OP's requirements, it might give him more peace of mind that the data he's storing will stay the same after a certain point of time.
The National Archives of Australia has developed [Checksum Checker] (http://checksumchecker.sourceforge.net/) which is freely available under GPLv3.
It reads a checksum and algorithm from a database, then recalculates the checksum for the file, compares the two values and reports if there is an error. It supports MD5, SHA1, SHA2, SHA256 and SHA512 algorithms.
Other software in their digital repository [DPR] (http://dpr.sourceforge.net/) generates the initial checksum (as well as doing all other processing activities)
