Change in vdsm[master]: fileSD: Optimize getAllVolumes on file storage

Monday, 5 January 2015

Nir Soffer has uploaded a new change for review.

Change subject: fileSD: Optimize getAllVolumes on file storage
......................................................................

fileSD: Optimize getAllVolumes on file storage

The previous implemantion was using O(N^2) search to detect template
images and volumes. This patch replaces it with O(N) search, improving
the 5000 disks test from 9 seconds to 0.65 seconds.

Change-Id: Idc19ce272b7e0b9c91d2f90aa46b5ddd21d69ece
Bug-Url: https://bugzilla.redhat.com/1177634
Signed-off-by: Nir Soffer <nsoffer(a)redhat.com&gt;
---
M tests/fileSDTests.py
M vdsm/storage/fileSD.py
2 files changed, 41 insertions(+), 28 deletions(-)


  git pull ssh://gerrit.ovirt.org:29418/vdsm refs/changes/93/36593/1

diff --git a/tests/fileSDTests.py b/tests/fileSDTests.py
index 9e0a1a5..0ab0ff1 100644
--- a/tests/fileSDTests.py
+++ b/tests/fileSDTests.py
@@ -123,7 +123,6 @@
         self.assertEqual(res["volume-3"], (("image-1",), None))
         self.assertEqual(res["volume-4"], (("image-2",), None))
 
-    @brokentest("too slow in current code")
     def test_scale(self):
         # For this test we want real world strings
         images_count = 5000
@@ -153,6 +152,6 @@
         elapsed = time.time() - start
         print "%f seconds" % elapsed
 
-        # This task should take no time using decent algorithm, using one
-        # second to make sure it will not fail on a overloaded test slave.
+        # This takes 0.065 seconds on my laptop, 1 second should be enough even
+        # on overloaded jenkins slave.
         self.assertTrue(elapsed < 1.0)
diff --git a/vdsm/storage/fileSD.py b/vdsm/storage/fileSD.py
index 127ec9a..f75c171 100644
--- a/vdsm/storage/fileSD.py
+++ b/vdsm/storage/fileSD.py
@@ -18,6 +18,7 @@
 # Refer to the README and COPYING files for full details of the license
 #
 
+import collections
 import os
 import errno
 import logging
@@ -408,41 +409,54 @@
         """
         Return dict {volUUID: ((imgUUIDs,), parentUUID)} of the domain.
 
-        Template self image is the 1st term in template volume entry images.
-        The parent can't be determined in file domain without reading the
-        metadata.
+        Template self image is the first item in template volume images tuple.
+        The parent uuid is available only for template volumes.
+
         Setting parent = None for compatibility with block version.
         """
         volMetaPattern = os.path.join(self.mountpoint, self.sdUUID,
                                       sd.DOMAIN_IMAGES, "*",
"*.meta")
         volMetaPaths = self.oop.glob.glob(volMetaPattern)
-        volumes = {}
+
+        # First create mapping from images to volumes
+        images = collections.defaultdict(list)
         for metaPath in volMetaPaths:
             head, tail = os.path.split(metaPath)
             volUUID, volExt = os.path.splitext(tail)
             imgUUID = os.path.basename(head)
-            if volUUID in volumes:
-                # Templates have no parents
-                volumes[volUUID]['parent'] = sd.BLANK_UUID
-                # Template volumes are hard linked in every image directory
-                # which is derived from that template, therefore:
-                # 1. a template volume which is in use will appear at least
-                # twice (in the template image dir and in the derived image
-                # dir)
-                # 2. Any volume which appears more than once in the dir tree is
-                # by definition a template volume.
-                # 3. Any image which has more than 1 volume is not a template
-                # image. Therefore if imgUUID appears in more than one path
-                # then it is not a template.
-                if len(tuple(vPath for vPath in volMetaPaths
-                             if imgUUID in vPath)) > 1:
-                    # Add template additonal image
-                    volumes[volUUID]['imgs'].append(imgUUID)
+            images[imgUUID].append(volUUID)
+
+        # Using images to volumes mapping, we can create volumes to images
+        # mapping, detecting template volumes and template images, based on
+        # these rules:
+        #
+        # Template volumes are hard linked in every image directory
+        # which is derived from that template, therefore:
+        #
+        # 1. A template volume which is in use will appear at least twice
+        #    (in the template image dir and in the derived image dir)
+        #
+        # 2. Any volume which appears more than once in the dir tree is
+        #    by definition a template volume.
+        #
+        # 3. Any image which has more than 1 volume is not a template
+        #    image.
+
+        volumes = {}
+        for imgUUID, volUUIDs in images.iteritems():
+            for volUUID in volUUIDs:
+                if volUUID in volumes:
+                    # This must be a template volume (rule 2)
+                    volumes[volUUID]['parent'] = sd.BLANK_UUID
+                    if len(volUUIDs) > 1:
+                        # This image is not a template (rule 3)
+                        volumes[volUUID]['imgs'].append(imgUUID)
+                    else:
+                        # This image is a template (rule 3)
+                        volumes[volUUID]['imgs'].insert(0, imgUUID)
                 else:
-                    # Insert at head the template self image
-                    volumes[volUUID]['imgs'].insert(0, imgUUID)
-            else:
-                volumes[volUUID] = {'imgs': [imgUUID], 'parent': None}
+                    volumes[volUUID] = {'imgs': [imgUUID], 'parent':
None}
+
         return dict((k, sd.ImgsPar(tuple(v['imgs']), v['parent']))
                     for k, v in volumes.iteritems())
 


-- 
To view, visit http://gerrit.ovirt.org/36593
To unsubscribe, visit http://gerrit.ovirt.org/settings

Gerrit-MessageType: newchange
Gerrit-Change-Id: Idc19ce272b7e0b9c91d2f90aa46b5ddd21d69ece
Gerrit-PatchSet: 1
Gerrit-Project: vdsm
Gerrit-Branch: master
Gerrit-Owner: Nir Soffer <nsoffer(a)redhat.com&gt;

    

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011