May 08, 2008
Similarity-Enhanced Transfer (SET) looks like it could prove very useful for efficiently sharing collections of Live-Spins without having to re-download an entire ISO image for every desired Live-Spin.
What is Similarity-Enhanced Transfer?After a brief skim, it seems that SET is a concept similar to BitTorrent but without arbitrary chunking of data. By using handprinting both similar and exact match chunks can be identified and utilized in the download process. The concept looks very interesting and I'm hoping to set aside some time to work on proof of concept code in the near future. I would also like to extend an invitation to the community to help develop and prove the viability of such a solution for mass-hosting of Live-Spins and Live-Spin collections, such as localized spins based on the same package set. We could easily setup an upstream git repo (likely on fedorahosted) or we could just add a branch to the existing pyJigdo repo and get right to work.
Why should this Concept Even be Considered?
Well, I'll quote the abstract and hope it's enough to encourage reading the entire paper:
"Many contemporary approaches for speeding up large file transfers attempt to download chunks of a data object from multiple sources. Systems such as BitTorrent quickly locate sources that have an exact copy of the desired object, but they are unable to use sources that serve similar but non-identical objects. Other systems automatically exploit cross-file similarity by identifying sources for each chunk of the object. These systems, however, require a number of lookups proportional to the number of chunks in the object and a mapping for each unique chunk in every identical and similar object to its corresponding sources. Thus, the lookups and mappings in such a system can be quite large, limiting its scalability.
This paper presents a hybrid system that provides the best of both approaches, locating identical and similar sources for data objects using a constant number of lookups and inserting a constant number of mappings per object. We first demonstrate through extensive data analysis that similarity does exist among objects of popular file types, and that making use of it can sometimes substantially improve download times. Next, we describe handprinting, a technique that allows clients to locate similar sources using a constant number of lookups and mappings. Finally, we describe the design, implementation and evaluation of Similarity-Enhanced Transfer (SET), a system that uses this technique to download objects. Our experimental evaluation shows that by using sources of similar objects, SET is able to significantly out-perform an equivalently configured BitTorrent."
Himabindu Pucha, David G. Andersen, Michael Kaminsky
Purdue University, Carnegie Mellon University, Intel Research Pittsburgh
Feb 27, 2008
bsdiff and bspatch are tools for building and applying patches to binary files. When looking for a solution to create a shared pool for squashfs images, I ran across bsdiff. Even if it's not going to work for Jigdo-style live image pools, it's still very interesting.
Upon reading Colin Percival's doctoral thesis I ran into a statement that I thoroughly enjoyed and it was this statement that convinced me to try using bsdiff to solve distribution concerns with tens, if not hundreds, of similar Live-Spins.
"If a mathematician is a machine for turning coffee into theorems, a computer scientist is a machine for converting caffeine into algorithms. As with mathematicians and theorems, the output of these machines may bear little resemblance to that which was originally sought, but I hope the reader will find this particular body of output to be both interesting and useful."- Colin Percival, Doctoral Thesis, http://www.daemonology.net/bsdiff/, 2006.
After doing some brief testing on how to slice up a squashfs image for sharing multiple live images using some base of binary data, I found this is no easy task. The Fedora Project has been planning on using BitTorrent to share custom live images with their Community. As a Fedora Unity member, I've been involved in trying to find [or create] a solution to efficiently share localized spins where the primary difference in the squashfs is just localization data. When gzipping (the compression for squashfs is gzip) even identical zeroed files, the end result is a different file:
[jon@damaestrojr ~]$ dd if=/dev/zero of=test.img bs=1024 count=100; cp test.img test2.img; gzip *.img; diff test.img.gz test2.img.gz 100+0 records in 100+0 records out 102400 bytes (102 kB) copied, 0.00317973 s, 32.2 MB/s Binary files test.img.gz and test2.img.gz differ [jon@damaestrojr ~]$ md5sum *.img.gz ffa2865fe4cce1abdd18ea62af86cd1f test2.img.gz 80a93fda63cb0908817d520db12cbc79 test.img.gz
After testing this very simple example, I knew we were in trouble.
SquashFS - What is it and why do we use it?
" Squashfs is a compressed read-only filesystem for Linux. Squashfs is intended for general read-only filesystem use, for archival use (i.e. in cases where a .tar.gz file may be used), and in constrained block device/memory systems (e.g. embedded systems) where low overhead is needed."- http://squashfs.sourceforge.net/
Most of the Live-Spins the Fedora Project, and most other Live-Spins, will be doing are ~700MB (the size of a CD.) Due to this size constraint, the Live-Spin rootfs is squashed. Live-Spins can be created without a compressed filesystem, but in most cases it is.
What about Jigdo?! Why wont it work?
Jigdo does a lot of things well and is a really neat concept. The only way jigdo [concepts] would be able to help us is if we recreated the squashfs with data that is downloaded from rpm packages and dumped into the squashfs. At this point of complexity, it's almost easier to just rebuild the Live-Spin from a definition (the kickstart) rather then trying to piece it back together. It's understandable that some people don't have the resources or desire to learn and utilize the live toolchain but recreation of [essentially] the same process is a mis-use of volunteer effort and the computational resources needed to achieve this process.
Okay, Okay, Where does bsdiff fit in?
bsdiff [concepts] could be used to isolate binary changes in the squashfs filesystem, for example. This would enable localized versions of Live-Spins to be distributed as a "patch" to the base Live-Spin. These patches would be trivial in size compared to an entirely additional Live-Spin. The one test that was done on a machine with 8 cores and 8GB of RAM, caused the entire system to crash. This is not a great sign, but oh well; it is fun to try things.
Will this ever work?
Maybe. Much more testing and input is needed. Please, ideas are welcome.
-  http://www.daemonology.net/papers/thesis.pdf