Improved Open Source Backup:
Incorporating inline deduplication and sparse indexing solutions

G. P. E. Keeling

3. Proof of concept programs

In order to ensure a solidly functional rabin algorithm and disk storage format before embarking on the complex asymetric network I/O that would be required for the first iteration of the software, I designed and implemented some proof of concept programs. I class this as 'release planning' in the XP process - my estimates were uncertain until I went through a 'spike' and experimented with rabin and disk storage. This made estimates more confident.

The idea for the prototype was to have programs that could use simple I/O so that data streams could simply be piped between them, or written to or read from files.

3.1. Design

Due to lack of space in the main project report, the design documents that I wrote for the proof of concept programs are reproduced in Appendix B.
The implementation of these programs was completed in the middle of June 2013.

3.2. Rabin fingerprinting

A reproduction of the C function containing the rabin algorithm that was produced for the proof of concept programs can be found in Appendix C. I judge this as being the most important outcome from that exercise, although it was modified slightly during later iterations in order to support slightly different usage required in the final software where asyncronous I/O had to be taken into account.

Note that the full code of the prototype can be found in the extra materials submitted with this report.