Internals/HashedStorage
Update (March 2016)
The following integration has been done of hashed-storage into Darcs:
./src/Storage/Hashed/Hash.hs -> ./src/Darcs/Util/Hash.hs
./src/Storage/Hashed/Tree.hs -> ./src/Darcs/Util/Tree.hs
./src/Storage/Hashed/Darcs.hs -> ./src/Darcs/Util/Tree/Hashed.hs
./src/Storage/Hashed/Plain.hs -> ./src/Darcs/Util/Tree/Plain.hs
./src/Storage/Hashed/Monad.hs -> ./src/Darcs/Util/Tree/Monad.hs
./src/Storage/Hashed/Index.hs -> ./src/Darcs/Util/Index.hsOld documentation
This page aims to provide high-level, informal documentation on hashed-storage
The hashed-storage library provides support code for reading and manipulating hashed file storage (where each file and directory is associated with a cryptographic hash, for corruption-resistant storage and fast comparisons).
The supported storage formats include darcs hashed pristine, a plain filesystem tree and an indexed plain tree (where the index maintains hashes of the plain files and directories). darcs’ pristine.hashed.
Right now we’re using it as a staging area for suggestions in improving the documentation.
Dream documentation
This stuff could be hard to pull off, but if we had it, wow, hashed-storage documentation would be really good!
- More examples
- More explanation of details, especially efficiency concerns
- Tutorials or example programs on how to use hashed-storage right
- Complexities of various functions (cf ByteString haddock)
- A pony
Papercuts
But maybe we can at least fix some easy stuff first…
The documentation says
The on-disk format is best described by peekItem.
but peekItem is not in the index. Actually, this is due to peekItem being not exported. (Fixed in hashed-storage HEAD, 0.5.3)
There is a dead link to http://hackage.haskell.org/packages/archive/hashed-storage/0.5.2/doc/html/indexFormatValid.html (maybe something in the haddock specifically). Minor haddock syntax problem; (Fixed in hashed-storage HEAD, 0.5.3)
There is a dead link to http://hackage.haskell.org/packages/archive/hashed-storage/0.5.2/doc/html/Storage-Hashed-Diff.html (this is because the Storage.Hashed.Diff module is optionally compiled in with -fdiff … module to be nuked in hashed-storage 0.6)
Improvements to structure
Also a little bit more signposting could be useful.
Where is the starting point? What is the first page of the hashed-storage documentation I should read?
What is the bigger picture? If I’m an application developer, when should I use hashed-storage, what-for? Also particularly, when might I be tempted to use hashed-storage but actually find it’s a bad idea
Questions
And finally the following points may need clarification
Why store hashes? What are they used for?
What is the hash of empty files and empty directories? Hash of directory of empty files?
What is the memory usage of the following behaviour?
When a file in a directory changes hash, this triggers recomputation of all of its parent directory hashes; moreover this is done efficiently – each directory is updated at most once during an update run
Why somebody would ask that is that they may think maybe files are mmap’d to be read. How are the files read? Are they read strictly or lazily, streamed? iteratee?
Design questions
Why does hashed storage use a binary format instead of a text-based one?
To avoid the performance issues caused by having to parse the index file
How large will the index file get if there are a lot of files in the repository?
For 80893 pristine.hashed items, the index is about 7.2M.
How long does reading a large index file take?
To answer this question: reading the file is done with mmap, we don’t do any parsing and we have a length mechanism that lets us skip parts of the index file that we’re not interested in. More concrete numbers to follow, but for now, we feel that reading the index is fairly fast.
Where do the timestamps (that we put into the index file) ultimately come from? Do we copy them from working?
See Storage.Hashed.Index inline documentation. – Petr