4 ms·

Ask HN: Does hashing only part of a file make sense as unique checksum?

1 points by sandreas 4y ago

Hey HN, currently, I'm having a performance issue with my little side project `tonehub`[1]. It's a small Web API including a background indexer task for audio files in pretty early state. Introduction: Sometimes I move an audio file to another directory, because the metadata changed. This results in losing all of the files non-metadata history (playback count, current position, playlists, etc.). To overcome this, I implemented hashing via xxhash only for the audio-part of the file skipping the metadata part. If a file is indexed, but its location is not found in the database, it hashes the file, looks it up and if a unique match is present, it updates only the location keeping the history and releations. Now to my problem: It's too slow. I have many audio book files in m4b format, most of the time bigger than 200MB and hashing a file like this takes pretty long, long enough that indexing a whole library feels to slow in my opinion. So I thought about following alternatives to improve that: - Hashing only a fixed length part of of the file (e.g. 5MB around the midpoint position, because of intros and outros are often the same) - Hashing a percentage size part (e.g. 5% of the audio data size) - Combine one of these "partial" hashes with a size check (e.g. hash=0815471 + size=8340485bytes, because hash and size collision may be less likely)? It feels like that won't work. So I ask HN: Would one of these alternatives be enough to avoid collisions? If so, what would be a "sufficient" part of the file and which alternative is the best? Thank you [1] https://github.com/sandreas/tonehub

h2odragon 4y ago
In this instance, it seems to me that a hash that only samples the input data would be just as useful as one that runs over the whole set. Sample every 128th byte, for example, to build your hash. or you could put your metadata into your audio files so it sticks with them when they move.
- sandreas 4y ago
  Thank you for your quick response... > In this instance, it seems to me that a hash that only samples the input data would be just as useful as one that runs over the whole set. So if I understand this correctly, hashing a set of bytes of a percentage of the file size would be a possible approach that could work. In your suggestion 1/128th of the file size, so a little less that 1 percent? But the difference is, that you instead of one chunk would hash a set of bytes always skipping a fixed amount? > or you could put your metadata into your audio files so it sticks with them when they move. That is already the case. The audio files are casual files like in every library. But I know, where the metadata starts and ends, so I can build a only-audio hash, that does not change, if the metadata changes. That is the point of this whole feature...
compressedgas 4y ago
I would recommend not moving around files that are under program control. Have a means to do so through the program. If the program must support files being moved underneath it, use an extended attribute to mark the files with a UUID or equivalent such as NTFS's OBJECTID. If that is not possible, use a combination of the file's fileid or inode number and its mtime and size to match up the missing files with files found elsewhere.
- compressedgas 4y ago
  Note that this only can detect moved unmodified files, unless the program that did the modification preserved the extended attributes or OBJECTID by either modifying the file in-place or by copying the extended attributes or with OBJECTID by using ReplaceFile.
  - sandreas 4y ago
    That is exactly the problem... keeping a unique "file identifier" while changing everything else (date, size, location)... hashing is a slow but pretty accurate approach for this. But maybe not the best / right one. There is also `chromaprint`[1] in ffmpeg - maybe this can be utilized, too... but I still think it is too slow. I think I have to test this out and provide the "don't lose your history" as experimental approach. Performance is king... especially when indexing or importing. Nobody wants to wait 3 days until his library is indexed :-) [1]: http://underpop.online.fr/f/ffmpeg/help/chromaprint-1.htm.gz http://underpop.online.fr/f/ffmpeg/help/chromaprint-1.htm.gz
- sandreas 4y ago
  > I would recommend not moving around files that are under program control. Have a means to do so through the program. Thank you. That is something I thought of, too. Maybe this requires sort of an "import procedure" with a frontend. Nice idea, but the hashing question still is important to me, just to understand, if this would be enough to avoid collisions > use an extended attribute to mark the files with a UUID or equivalent such as NTFS's OBJECTID Yeah that could work... inode number and mtime may be a problem in a docker environment - size is already part of my question (more accurate: audiodata size because the file size often changes when metadata does). I'll check that again. A custom metadata tag (like TXXX:tonehubid for id3) would also work, but I don't wanna embed this information directly into the file, because if I share files with a friend and he also uses tonehub, it could end in a conflict or data loss...
beardyw 4y ago
No checksum is unique. Your problem is to do with the probability of collision. My guess is that hashing a very small part of the file would suffice as long as it contains actual audio (not silence) maybe just a few seconds. If you are concerned that you may have different edits of the same audio, you could try skipping through taking a small sample from every n seconds.
- sandreas 4y ago
  > No checksum is unique. Your problem is to do with the probability of collision. Thanks :-) Yeah the question should be more accurate :-) In the description I already use "avoid collisions". > My guess is that hashing a very small part of the file would suffice as long as it contains actual audio (not silence) Yeah, I had that in mind. The problem is, that this would go deeply into audio analysis (silence detection would be slower than hashing the whole file), so this is all into probability. It also is important, how many files the libary contains and my question is exactly about that: How to avoid collsions while still being fast enough to index a libray with > 10000 audio files (audio books and music). > If you are concerned that you may have different edits of the same audio, you could try skipping through taking a small sample from every n seconds. That is more likely to happen on music than on audio books. Therefore I asked about hashing one big chunk of e.g. 5MB. If the file is smaller, it hashes the whole file, if it is bigger, it hashes only a part in the middle of the file... I also thought of a combination of properties: PartialHash and FullHash only calculating the full hash, if the PartialHash has an acutual collision. That would make it kind of robust for edge cases but also fast in the average case. But I'm trying to keep it simple...