Instanciating an AMI image

When one creates an instance from an AMI image in an OpenStack cloud:

• the kernel is copied to the virtualization host,
• the initial ramdisk is copied to the virtualization host,
• the root FS image is copied to the virtualization host,
• then, the root FS image is :
  • duplicated (instanciated),
  • resized (the file is increased if needed) to the size of the asked instance flavor,
  • the file system is resized to the new size of the file,
  • the contained filesystem is mounted (using qemu-nbd) and the configured SSH acces key is added to /root/.ssh/authorized_keys
  • the nbd volume is then unmounted
• a libvirt domain is created, configured to boot from the given kernel and init ramdisk, using the resized and modified image disk as root filesystem,
• the libvirt domain is then booted.

Instantiating a BARE image

When one creates an instance from a BARE image in an OpenStack cloud:

• the VM image file is copied on the virtualization host,
• the VM image file is duplicated (instantiated),
• a libvirt domain is created, configured to boot from this copied image disk as root filesystem,
• the libvirt domain is then booted.

Differences between the 2 instantiation methods

Instantiating a BARE image:

• Involves a much simpler process.
• Allows to boot a non-linux system (depends on the virtualization system, especially true when using kvm vitualization).
• Is slower to boot and consumes more resources, since the virtual machine image must be the size of the required/wanted virtual machine (but can remain minimal if using a qcow2 image format). If you use a 10G raw image, then 10G of data will be copied from the image provider to the virtualization host, and this big file will be duplicated each time you instantiate this image.
• The root filesystem size corresponding to the flavor of the instance is not honored; the filesystem size is the one of the BARE images.

Instantiating an AMI image:

• Honours the flavor.
• Generally allows quicker instance creation process.
• Less resource consumption.
• Can only boot Linux guests.

If one wants to boot a Windows guest in OpenStack, the only solution (as far as I know) is to use a BARE image of an installed Windows system. It works (I have succeeded in doing so), but a minimal Windows 7 install is several GB, so instantiating such a BARE image is very slow, because the image needs to be uploaded on the virtualization host.

1. Install a Debian system in a standard libvirt/kvm guest.

david@host:~$ virt-install  --connect qemu+tcp://virthost/system   \
                 -n openstack-squeeze-amd64 -r 512 \
                 -l http://ftp2.fr.debian.org/pub/debian/dists/stable/main/installer-amd64/ \
                 --disk pool=default,bus=virtio,type=qcow2,size=5 \
                 --network bridge=vm7,model=virtio  --nographics  \
                 --extra-args='console=tty0 console=ttyS0,115200'

This creates a new virtual machine, launch the Debian installer directly downloaded from a Debian mirror, and start the usual Debian installer in a virtual serial console (I don't like VNC very much).

I then followed the installation procedure. When asked for the partitioning and so, I chose to create only one primary partition (ie. with no swap partition; it wont be necessary here). I also chose only "Default system" and "SSH server" to be installed.

2. Configure the system

After the installation process, the VM is rebooted, I log into it (by SSH or via the console), so I can configure a bit the system.

david@host:~$ ssh root@openstack-squeeze-amd64.vm.logilab.fr
Linux openstack-squeeze-amd64 2.6.32-5-amd64 #1 SMP Sun Sep 23 10:07:46 UTC 2012 x86_64

The programs included with the Debian GNU/Linux system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.

Debian GNU/Linux comes with ABSOLUTELY NO WARRANTY, to the extent
permitted by applicable law.
Last login: Sun Dec 23 20:14:24 2012 from 192.168.1.34
root@openstack-squeeze-amd64:~# apt-get update
root@openstack-squeeze-amd64:~# apt-get install vim curl parted # install some must have packages
[...]
root@openstack-squeeze-amd64:~# dpkg-reconfigure locales # I like to have fr_FR and en_US in my locales
[...]
root@openstack-squeeze-amd64:~# echo virtio_baloon >> /etc/modules
root@openstack-squeeze-amd64:~# echo acpiphp >> /etc/modules
root@openstack-squeeze-amd64:~# update-initramfs -u
root@openstack-squeeze-amd64:~# apt-get clean
root@openstack-squeeze-amd64:~# rm /etc/udev/rules.d/70-persistent-net.rules
root@openstack-squeeze-amd64:~# rm .bash_history
root@openstack-squeeze-amd64:~# poweroff

What we do here is to install some packages, do some configurations. The important part is adding the acpiphp module so the volume attachment will work in our instances. We also clean some stuffs up before shutting the VM down.

3. Convert the image into an AMI image

Since I created the VM image as a qcow2 image, I needed to convert it back to a raw image:

david@host:~$ scp root@virthost:/var/lib/libvirt/images/openstack-squeeze-amd64.img .
david@host:~$ qemu-img convert -O raw openstack-squeeze-amd64.img openstack-squeeze-amd64.raw

Then, as I want a minimal-sized disk image, the filesystem must be resized to minimal. I did this like described below, but I think there are simpler methods to do so.

david@host:~$ fdisk -l openstack-squeeze-amd64.raw  # display the partition location in the disk

Disk openstack-squeeze-amd64.raw: 5368 MB, 5368709120 bytes
149 heads, 8 sectors/track, 8796 cylinders, total 10485760 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x0001fab7

                   Device Boot      Start         End      Blocks   Id  System
debian-squeeze-amd64.raw1            2048    10483711     5240832   83  Linux
david@host:~$ # extract the filesystem from the image
david@host:~$ dd if=openstack-squeeze-amd64.raw of=openstack-squeeze-amd64.ami bs=1024 skip=1024 count=5240832
david@host:~$ losetup /dev/loop1 openstack-squeeze-amd64.ami
david@host:~$ mkdir /tmp/img
david@host:~$ mount /dev/loop1 /tmp/img
david@host:~$ cp /tmp/img/boot/vmlinuz-2.6.32-5-amd64 .
david@host:~$ cp /tmp/img/boot/initrd.img-2.6.32-5-amd64 .
david@host:~$ umount /tmp/img
david@host:~$ e2fsck -f /dev/loop1 # required before a resize

e2fsck 1.42.5 (29-Jul-2012)
Pass 1: Checking inodes, blocks, and sizes
Pass 2: Checking directory structure
Pass 3: Checking directory connectivity
Pass 4: Checking reference counts
Pass 5: Checking group summary information
/dev/loop1: 26218/327680 files (0.2% non-contiguous), 201812/1310208 blocks
david@host:~$ resize2fs -M /dev/loop1 # minimize the filesystem

resize2fs 1.42.5 (29-Jul-2012)
Resizing the filesystem on /dev/loop1 to 191461 (4k) blocks.
The filesystem on /dev/loop1 is now 191461 blocks long.
david@host:~$ # note the new size ^^^^ and the block size above (4k)
david@host:~$ losetup -d /dev/loop1 # detach the lo device
david@host:~$ dd if=debian-squeeze-amd64.ami of=debian-squeeze-amd64-reduced.ami bs=4096 count=191461

4. Upload in OpenStack

After all this, you have a kernel image, a init ramdisk file and a minimized root filesystem image file. So you just have to upload them to your OpenStack image provider (glance):

david@host:~$ glance add disk_format=aki container_format=aki name="debian-squeeze-uec-x86_64-kernel" \
                 < vmlinuz-2.6.32-5-amd64
Uploading image 'debian-squeeze-uec-x86_64-kernel'
==================================================================================[100%] 24.1M/s, ETA  0h  0m  0s
Added new image with ID: 644e59b8-1503-403f-a4fe-746d4dac2ff8
david@host:~$ glance add disk_format=ari container_format=ari name="debian-squeeze-uec-x86_64-initrd" \
                 < initrd.img-2.6.32-5-amd64
Uploading image 'debian-squeeze-uec-x86_64-initrd'
==================================================================================[100%] 26.7M/s, ETA  0h  0m  0s
Added new image with ID: 6f75f1c9-1e27-4cb0-bbe0-d30defa8285c
david@host:~$ glance add disk_format=ami container_format=ami name="debian-squeeze-uec-x86_64" \
                 kernel_id=644e59b8-1503-403f-a4fe-746d4dac2ff8 ramdisk_id=6f75f1c9-1e27-4cb0-bbe0-d30defa8285c \
                 < debian-squeeze-amd64-reduced.ami
Uploading image 'debian-squeeze-uec-x86_64'
==================================================================================[100%] 42.1M/s, ETA  0h  0m  0s
Added new image with ID: 4abc09ae-ea34-44c5-8d54-504948e8d1f7

And that's it (!). I now have a working Debian squeeze image in my cloud that works fine:

Simple case

1. Let's define alignset and targetset as simple python lists.

alignset = ['Victor Hugo', 'Albert Camus']
targetset = ['Albert Camus', 'Guillaume Apollinaire', 'Victor Hugo']

2. Now, we have to compute the similarity between each items. For that purpose, the Levenshtein distance [1], which is well accurate to compute the distance between few words, is used. Such a function is provided in the nazca.distance module.

   The next step is to compute the distance matrix according to the Levenshtein distance. The result is given in the following table.

   	Albert Camus	Guillaume Apollinaire	Victor Hugo
   Victor Hugo	6	9	0
   Albert Camus	0	8	6

3. The alignment process is ended by reading the matrix and saying items having a value inferior to a given threshold are identical.

A more complex one

The previous case was simple, because we had only one attribute to align (the name), but it is frequent to have a lot of attributes to align, such as the name and the birth date and the birth city. The steps remain the same, except that three distance matrices will be computed, and items will be represented as nested lists. See the following example:

alignset = [['Paul Dupont', '14-08-1991', 'Paris'],
            ['Jacques Dupuis', '06-01-1999', 'Bressuire'],
            ['Michel Edouard', '18-04-1881', 'Nantes']]
targetset = [['Dupond Paul', '14/08/1991', 'Paris'],
             ['Edouard Michel', '18/04/1881', 'Nantes'],
             ['Dupuis Jacques ', '06/01/1999', 'Bressuire'],
             ['Dupont Paul', '01-12-2012', 'Paris']]

In such a case, two distance functions are used, the Levenshtein one for the name and the city and a temporal one for the birth date [2].

The cdist function of nazca.distances enables us to compute those matrices :

• For the names:

>>> nazca.matrix.cdist([a[0] for a in alignset], [t[0] for t in targetset],
>>>                    'levenshtein', matrix_normalized=False)
array([[ 1.,  6.,  5.,  0.],
       [ 5.,  6.,  0.,  5.],
       [ 6.,  0.,  6.,  6.]], dtype=float32)

• For the birthdates:

>>> nazca.matrix.cdist([a[1] for a in alignset], [t[1] for t in targetset],
>>>                    'temporal', matrix_normalized=False)
array([[     0.,  40294.,   2702.,   7780.],
       [  2702.,  42996.,      0.,   5078.],
       [ 40294.,      0.,  42996.,  48074.]], dtype=float32)

• For the birthplaces:

>>> nazca.matrix.cdist([a[2] for a in alignset], [t[2] for t in targetset],
>>>                    'levenshtein', matrix_normalized=False)
array([[ 0.,  4.,  8.,  0.],
       [ 8.,  9.,  0.,  8.],
       [ 4.,  0.,  9.,  4.]], dtype=float32)

The next step is gathering those three matrices into a global one, called the global alignment matrix. Thus we have :

Allowing some misspelling mistakes (for example Dupont and Dupond are very closed), the matching threshold can be set to 1 or 2. Thus we can see that the item 0 in our alignset is the same that the item 0 in the targetset, the 1 in the alignset and the 2 of the targetset too : the links can be done !

It's important to notice that even if the item 0 of the alignset and the 3 of the targetset have the same name and the same birthplace they are unlikely identical because of their very different birth date.

You may have noticed that working with matrices as I did for the example is a little bit boring. The good news is that Nazca makes all this job for you. You just have to give the sets and distance functions and that's all. An other good news is the project comes with the needed functions to build the sets !

The Goncourt prize

On wikipedia, we can find the Goncourt prize winners, and we would like to establish a link between the winners and their URI on dbpedia (Let's imagine the Goncourt prize winners category does not exist in dbpedia)

We simply copy/paste the winners list of wikipedia into a file and replace all the separators (- and ,) by #. So, the beginning of our file is :

1903#John-Antoine Nau#Force ennemie (Plume)

1904#Léon Frapié#La Maternelle (Albin Michel)

1905#Claude Farrère#Les Civilisés (Paul Ollendorff)

1906#Jérôme et Jean Tharaud#Dingley, l'illustre écrivain (Cahiers de la Quinzaine)

When using the high-level functions of this library, each item must have at least two elements: an identifier (the name, or the URI) and the attribute to compare. With the previous file, we will use the name (so the column number 1) as identifier (we don't have an URI here as identifier) and attribute to align. This is told to python thanks to the following code:

alignset = aldio.parsefile('prixgoncourt', indexes=[1, 1], delimiter='#')

So, the beginning of our alignset is:

>>> alignset[:3]
[[u'John-Antoine Nau', u'John-Antoine Nau'],
 [u'Léon Frapié', u'Léon, Frapié'],
 [u'Claude Farrère', u'Claude Farrère']]

Now, let's build the targetset thanks to a sparql query and the dbpedia end-point. We ask for the list of the French novelists, described by their URI and their name in French:

query = """
     SELECT ?writer, ?name WHERE {
       ?writer  <http://purl.org/dc/terms/subject> <http://dbpedia.org/resource/Category:French_novelists>.
       ?writer rdfs:label ?name.
       FILTER(lang(?name) = 'fr')
    }
 """
 targetset = aldio.sparqlquery('http://dbpedia.org/sparql', query)

Both functions return nested lists as presented before. Now, we have to define the distance function to be used for the alignment. This is done thanks to a python dictionary where the keys are the columns to work on, and the values are the treatments to apply.

treatments = {1: {'metric': ald.levenshtein}} # Use a levenshtein on the name
                                              # (column 1)

Finally, the last thing we have to do, is to call the alignall function:

alignments = ala.alignall(alignset, targetset,
                       0.4, #This is the matching threshold
                       treatments,
                       mode=None,#We'll discuss about that later
                       uniq=True #Get the best results only
                      )

This function returns an iterator over the different alignments done. You can see the results thanks to the following code :

for a, t in alignments:
    print '%s has been aligned onto %s' % (a, t)

It may be important to apply some pre-treatment on the data to align. For instance, names can be written with lower or upper characters, with extra characters as punctuation or unwanted information in parenthesis and so on. That is why we provide some functions to normalize your data. The most useful may be the simplify() function (see the docstring for more information). So the treatments list can be given as follow:

def remove_after(string, sub):
    """ Remove the text after ``sub`` in ``string``
        >>> remove_after('I like cats and dogs', 'and')
        'I like cats'
        >>> remove_after('I like cats and dogs', '(')
        'I like cats and dogs'
    """
    try:
        return string[:string.lower().index(sub.lower())].strip()
    except ValueError:
        return string


treatments = {1: {'normalization': [lambda x:remove_after(x, '('),
                                    aln.simply],
                  'metric': ald.levenshtein
                 }
             }

Cities alignment

The previous case with the Goncourt prize winners was pretty simply because the number of items was small, and the computation fast. But in a more real use case, the number of items to align may be huge (some thousands or millions…). In such a case it's unthinkable to build the global alignment matrix because it would be too big and it would take (at least...) fews days to achieve the computation. So the idea is to make small groups of possible similar data to compute smaller matrices (i.e. a divide and conquer approach). For this purpose, we provide some functions to group/cluster data. We have functions to group text and numerical data.

This is the code used, we will explain it:

targetset = aldio.rqlquery('http://demo.cubicweb.org/geonames',
                           """Any U, N, LONG, LAT WHERE X is Location, X name
                              N, X country C, C name "France", X longitude
                              LONG, X latitude LAT, X population > 1000, X
                              feature_class "P", X cwuri U""",
                           indexes=[0, 1, (2, 3)])
alignset = aldio.sparqlquery('http://dbpedia.inria.fr/sparql',
                             """prefix db-owl: <http://dbpedia.org/ontology/>
                             prefix db-prop: <http://fr.dbpedia.org/property/>
                             select ?ville, ?name, ?long, ?lat where {
                              ?ville db-owl:country <http://fr.dbpedia.org/resource/France> .
                              ?ville rdf:type db-owl:PopulatedPlace .
                              ?ville db-owl:populationTotal ?population .
                              ?ville foaf:name ?name .
                              ?ville db-prop:longitude ?long .
                              ?ville db-prop:latitude ?lat .
                              FILTER (?population > 1000)
                             }""",
                             indexes=[0, 1, (2, 3)])


treatments = {1: {'normalization': [aln.simply],
                  'metric': ald.levenshtein,
                  'matrix_normalized': False
                 }
             }
results = ala.alignall(alignset, targetset, 3, treatments=treatments, #As before
                       indexes=(2, 2), #On which data build the kdtree
                       mode='kdtree',  #The mode to use
                       uniq=True) #Return only the best results

Let's explain the code. We have two files, containing a list of cities we want to align, the first column is the identifier, and the second is the name of the city and the last one is location of the city (longitude and latitude), gathered into a single tuple.

In this example, we want to build a kdtree on the couple (longitude, latitude) to divide our data in few candidates. This clustering is coarse, and is only used to reduce the potential candidats without loosing any more refined possible matchs.

So, in the next step, we define the treatments to apply. It is the same as before, but we ask for a non-normalized matrix (ie: the real output of the levenshtein distance). Thus, we call the alignall function. indexes is a tuple saying the position of the point on which the kdtree must be built, mode is the mode used to find neighbours [3].

Finally, uniq ask to the function to return the best candidate (ie: the one having the shortest distance below the given threshold)

The function outputs a generator yielding tuples where the first element is the identifier of the alignset item and the second is the targetset one (It may take some time before yielding the first tuples, because all the computation must be done…)