GSoC/2009-Hashed

This is a timeline for Petr Rockai’s hashed-storage GSoC project

Overview

Darcs supports ‘hashed’ repositories in which each file in the pristine cache is associated with a cryptographic hash. Hashed repositories help Darcs to resist some forms of corruption and also allow for nice features such as a global patch cache and lazy patch fetching. Unfortunately, our implementation can be rather slow.

Petr has some nice ideas for making these repositories work a lot faster. He will be producing a library he calls ‘hashed-storage’ which generalises the idea of storing files associating them with a cryptographic hash and furthermore improves on the current implementation used by Darcs. The hashed-storage library is general purpose and may find a use in other applications that need to manage a large number of files.

For more information, see http://mornfall.net/blog/summer_of_code.html

This project was completed and passed. :-)

Timeline

Note that Petr started a week earlier than the official dates, so everything is shifted back one.

  1. (ending 25 May)

  2. (1 Jun)

  3. (8 Jun)

    • Darcs format mechanism extended to deal with hashed-storage verions? [do we need this?]
    • Future-proofing strategy elucidated - Petr already has written up email about this, so maybe just links

  4. (15 Jun) - format documentation published (at least for index)

    • TODO hashed-storage:
      • without bytestring-mmap dependency
      • the Diff module made optional
    • TODO darcs-hs:
      • darcs wh filename spends 80% of time in announce_files, since it slurps pristine to check if the files given are in the repository (this can be avoided using hashed-storage)
    • context: Darcs 2.3 freeze

  5. (22 Jun) - rough benchmarking infrastructure in place (‘’status?’’)

    • done: API stabilising for darcs 2.3
    • thought about: packing, and requirements for packed repository
    • done: post darcs 2.3; all pristine -> working diffing using hashed-storage

  6. (29 Jun)

    • hashed-storage 0.3.4
    • done: endianitiy
    • done: magic word in index (index upgrade)
    • Aribtrary Tree (QC)

  7. (6 Jul)

  8. (13 Jul)

    • context: Darcs 2.3 release!
    • context: Mid-term evaluations deadline

  9. (20 Jul)

  10. (27 Jul) - future work roadmap complete

  11. (3 Aug)

  12. (10 Aug)

  13. (17 Aug) - nothing [ends at 12]

    • context: GSoC pencils down deadline

Bigger picture neighbourhood

  • Hacking sprint: 2009-09
  • Darcs 2.4: 2010-01
  • Darcs 2.5: 2010-07
  • Summer of Code 2010

Deliverables

  • hashed-storage

  • documentation on formats used by hashed-storage (e.g. camp repo format)

  • API docs

  • unit tests

  • benchmarking infrastructure

    • ./go.sh script or similar
    • ./publish-benchmarks.sh or similar

  • published benchmarks

  • Darcs 2.3 integration!

    • extension to Darcs format mechanism (numerical versions?)

  • Darcs 2.4 integration

  • future work roadmap and hints (e.g. ideas for how packs might work)

Design goals

  • Future proofing

    • design in such a way that lets old hashed-storage read (and write to?) stores created by new hashed-storage
    • versioning mechanism - hopefully one that we can avoid using

  • Facilitation of future work

    • how would hashed-storage development work if you had contributors?
    • is there anything you could spin off, e.g. into undergrad student projects?

  • Portability

    • endianness issues?
    • can the same store be read to, written by different kinds of systems?

  • Safety

    • atomicity of operations

  • Robustness

    • tolerant IO in working directories?

  • Good interactions with other systems

    • patch application
    • network code
    • cache mechanism

Technical details

  • index file (timestamps)
  • can we combine small files into one? (see `camp repo format <http://projects.haskell.org/camp/repository>` offset mechanism)
  • avoiding creating large directories
  • could hashed-storage easily implement other formats, e.g. camp? e.g. git [relevant?]

Worries and questions for the roadmap

Note: for general design questions, see `hashed-storage <>`

  • Darcs 2.4 integration sounds tricky - hard to do in an incremental fashion.

    We already do this incrementally (see darcs 2.3 integration patches). – Petr

  • Do we implement HashedStorageIO akin to DarcsIO and HashedIO?

    See Storage.Hashed.Monad – I think that may cover what you mean? – Petr

  • What is the minimum set of features hashed-storage needs to work for darcs?

  • Why does hashed-storage need a diff mechanism?

    It’s proof of concept, really. TODO make it optional. – Petr