python/cumulus/metadata.py

   1 """Advanced metadata iterator for Cumulus snapshots.
   2
   3 Allow fast random access to Cumulus metadata logs.  This requires that the
   4 underlying metadata log have been generated by a depth-first-search traversal
   5 of the filesystem, in sorted order.
   6 """
   7
   8 import cumulus
   9
  10 class Metadata:
  11     def __init__(self, object_store, root):
  12         self.store = object_store
  13         self.root = root
  14
  15     def _load(self, ref):
  16         """Return the contents of the given object, as a list of text lines."""
  17
  18         data = self.store.get(ref)
  19         return data.splitlines()
  20
  21     def _read(self, ptr):
  22         """Parse the metadata item at the given address and return it."""
  23
  24         if ptr is None or ptr == []: return {}
  25
  26         (ref, n) = ptr[-1]
  27         lines = self._load(ref)[n:]
  28
  29         try:
  30             return cumulus.parse(lines, lambda l: len(l) == 0).next()
  31         except StopIteration:
  32             return {}
  33
  34     def _advance(self, ptr):
  35         """Advance the specified metadata pointer to the next metadata item."""
  36
  37         if ptr == None:
  38             return None
  39
  40         advanced = False
  41         ptr = list(ptr)
  42         if ptr == []:
  43             ptr.append((self.root, 0))
  44             advanced = True
  45
  46         while True:
  47             last = ptr.pop(-1)
  48             lines = self._load(last[0])
  49
  50             # Reached the end of the current object?  Advance pointer by one
  51             # line in the containing object (or return None if reached the very
  52             # end of input).
  53             if last[1] >= len(lines):
  54                 if ptr == []: return None
  55                 last = ptr.pop(-1)
  56                 ptr.append((last[0], last[1] + 1))
  57                 advanced = True
  58                 continue
  59
  60             # Reached a line with an indirect reference?  Recurse.
  61             line = lines[last[1]]
  62             if line.startswith('@'):
  63                 ptr.append(last)
  64                 ptr.append((line[1:], 0))
  65                 advanced = True
  66                 continue
  67
  68             # Skip over blank lines.
  69             if line == "":
  70                 ptr.append((last[0], last[1] + 1))
  71                 advanced = True
  72                 continue
  73
  74             # Skip over the remainder of a metadata stanza, if we started in
  75             # the middle of one.
  76             if not advanced:
  77                 ptr.append((last[0], last[1] + 1))
  78                 continue
  79
  80             # Done!  Found a non-blank line which is not an indirect reference.
  81             ptr.append(last)
  82             return ptr
  83
  84     def _cmp(self, ptr1, ptr2):
  85         if ptr1 is None and ptr2 is None: return 0
  86         if ptr1 is None: return 1
  87         if ptr2 is None: return -1
  88         return cmp(ptr1, ptr2)
  89
  90     def _get_path(self, metadata):
  91         if metadata is None or 'name' not in metadata:
  92             return None
  93         path = metadata['name']
  94         path = cumulus.MetadataItem.decode_str(path)
  95         if path == '.': return []
  96         return path.split('/')
  97
  98     def _midpoint(self, ptr1, ptr2):
  99         """Return a pointer to some metadata item in the range [ptr1, ptr2)."""
 100
 101         if ptr1 == []: ptr1 = self._advance([])
 102         if ptr1 is None: return None
 103         if self._cmp(ptr1, ptr2) > 0: return None
 104
 105         #print "ptr1:", ptr1
 106         #print "ptr2:", ptr2
 107
 108         level = 0
 109         while True:
 110             if level >= len(ptr1): return ptr1
 111
 112             if ptr2 is not None and level < len(ptr2) and ptr1[level] == ptr2[level]:
 113                 level += 1
 114                 continue
 115
 116             midpoint = ptr1[0:level]
 117             lastref = ptr1[level][0]
 118             limit = len(self._load(lastref))
 119             if ptr2 is not None and level < len(ptr2) \
 120                     and ptr1[level][0] == ptr2[level][0]:
 121                 limit = ptr2[level][1]
 122             midpoint.append((lastref, (ptr1[level][1] + limit) // 2))
 123
 124             if self._cmp(midpoint, ptr1) < 0:
 125                 #print "    ...descend"
 126                 level += 1
 127                 continue
 128
 129             #print "Guess midpoint:", midpoint
 130             midpoint = self._advance(midpoint)
 131             #print "    ...advanced to", midpoint
 132
 133             if self._cmp(midpoint, ptr2) >= 0:
 134                 #print "    ...overshoot, trying again"
 135                 level += 1
 136                 continue
 137
 138             return midpoint
 139
 140     def search(self, searchfunc, ptr1=[], ptr2=None):
 141         """Perform a binary search for name.
 142
 143         The search is restricted to the interval [ptr1, ptr2).  Return either a
 144         pointer to the item for name, or if it doesn't exist the pointer to the
 145         item which follows where it would have been (assuming the original
 146         search interval included that location)."""
 147
 148         def _printable(ptr):
 149             if ptr is None: return None
 150             return tuple(x[1] for x in ptr)
 151
 152         while True:
 153             #print _printable(ptr1), "...", _printable(ptr2)
 154             if self._cmp(ptr1, ptr2) >= 0:
 155                 #print "    X", _printable(ptr1)
 156                 return ptr1
 157
 158             mid = self._midpoint(ptr1, ptr2)
 159             midpath = self._get_path(self._read(mid))
 160
 161             c = searchfunc(midpath)
 162             if c == 0:
 163                 #print "    =", _printable(mid), midpath
 164                 return mid
 165             elif c < 0:
 166                 #print "    >", _printable(mid), midpath
 167                 ptr1 = self._advance(mid)
 168             else:
 169                 #print "    <", _printable(mid), midpath
 170                 ptr2 = mid
 171
 172 if __name__ == '__main__':
 173     import cumulus
 174
 175     store = cumulus.ObjectStore(cumulus.LowlevelDataStore('/backups/lbs/turin'))
 176     root = '9e0be287-a74c-4527-aa26-0a10e8f40f7d/00000243(sha1=316e034bb5b86e5ba00b1d54335427d7b742f4f9)'
 177
 178     metadata = Metadata(store, root)
 179     ptr = metadata.search(['home', 'mvrable', 'docs'])
 180     print ptr
 181     print metadata._read(ptr)
 182     store.cleanup()