3 ms·
one simple option might be to just use sha256 sums on files. if done incrementally, it's not that expensive computationally, unless files are very large (couple
by signa11 11y ago
one simple option might be to just use sha256 sums on files. if done incrementally, it's not that expensive computationally, unless files are very large (couple of gb's).
one way to mitigate that might be take a _few_ random, say, 1k chunks of file content, and hash those. as long as you have a map of (offset, hash) de-duping should be just fine.
the only thing is, i don't really know, what an upper bound on 'few samples' would be like. asymptotically, it should approach file-size/chunk-size, but ideally, it should be way less than that.
any ideas on how to determine a minimal but complete set ?
- Someone 11y agoThe minimal set is to use full content of the file. Consider the case of a log file and its backup made one short log message earlier. If you want to gamble on using only a partial hash, I would hash the last few kb of each file, as that (at least based on this 30-second 'analysis' of the problem domain) likely would work better in practice. Theoretically, it is as vulnerable, though. Edit: if you have a VM image on your disk, and that small append happens to a log file in the image, that small change can happen anywhere. It also can be even smaller; someone might run 'touch' on an already existing file. Theoretically, that could be a one-byte change.
- daurnimator 11y agoThe idea is to use a two stage process: 1. take a sha1 hash of the last 4KB of each file. 2. for any equal hashes, compare the whole file. With this method you should be able to skip reading many large files in their entirety.
- Someone 11y agoThat is an idea, and it would, in typical cases, avoid reading most large files in their entirety, but it is not what I read in signa11's comment.
- gpvos 11y agoA length check would catch the log file case. But really, just hash the whole file. As an optimization, you might want to check for files with holes in them ("sparse" files). Not sure how to do that, though.
- oever 11y agoMany filesystems compress data. Unless the compression is done on block level, reading the last bytes of file that is transiently compressed is much more expensive than reading the first part.