virt-similarity: Find clusters of similar/cloned virtual machines
Copyright (C) 2013 Red Hat Inc.
======================================================================

Compiling from source
---------------------

If checking out from git, then:
  autoreconf -i

Build it:
  ./configure
  make

Optionally:
  sudo make install

Requirements
------------

- ocaml >= 3.12.0
- ocaml findlib
- libguestfs >= 1.14
- ocaml libguestfs bindings

Developers
----------

The upstream git repo is:

http://git.annexia.org/?p=virt-similarity.git;a=summary

Please send patches to the virt-tools mailing list:

http://www.redhat.com/mailman/listinfo/virt-tools-list

Notes on the technique used
---------------------------

(1) We use libguestfs to open each disk image.  This allows us to get
at the raw data, in case the disk image is stored in some format like
qcow2 or vmdk.  Also you could extend this program so it could
understand encrypted disks.

http://libguestfs.org/
http://libguestfs.org/guestfs-java.3.html

(2) For each disk, we split it into 64K blocks and hash each block.
The reason for choosing 64K blocks is that it's the normal cluster
size for qcow2, and the block size used by qemu-img etc.  The reason
for doing the hashing is so that we can compare the disk images for
similarity by holding the complete set of hashes in memory.  The
hashing reduces each disk by a factor of 4096 (MD5) or 2048 (SHA-256)
times, so for example a 10 GB disk image is reduced to a more
manageable 2.5 or 5 MB.

NB: For speed the hashes are saved in a cache file called
'similarity-cache' in the local directory.  You can just delete this
file when done.

(3) We then compare each disk image, block by block, and record the
difference between each pair of images.

Note that we DON'T do advanced Cluster Analysis on the disk images.
There's not any point since the rebasing operation used by qemu-img
can only handle simple differences at the block level; it cannot, for
example, move blocks around or do fuzzy matches.
http://en.wikipedia.org/wiki/Cluster_analysis

(4) We then output a tree (technically a 'Cladogram') showing a
hierarchy of guests, using a simple hierarchical clustering algorithm,
where we group the two closest guests, then that group with the next
closest guest, and so forth.

http://en.wikipedia.org/wiki/Cladogram
http://en.wikipedia.org/wiki/Hierarchical_clustering