contrib/parity-gen

   1 #!/usr/bin/python
   2 #
   3 # Generate parity blocks for backup segments, so that the corruption or loss of
   4 # some segment data can be recovered, and does not render a snapshot
   5 # unreadable.
   6 #
   7 # par2 is used to generate the parity blocks.  This script merely automates the
   8 # creation and maintenance of these parity files.
   9 #
  10 # This program will incrementally update parity files.  Input files which are
  11 # not protected will have parity files generated.  If there are many new files,
  12 # they will be grouped into about 16-file blocks and parity files generated for
  13 # each block.  If files have been deleted, obsolete parity sets will be
  14 # removed.
  15 #
  16 # The generated parity files are given a name of parity-<hexdigits>.par2.
  17 # Associated with each is a parity-<hexdigits>.manifest file which specifies
  18 # how many file losses are protected against, and which files specifically are
  19 # protected by that set.
  20
  21 import md5, os, re, sys
  22 from subprocess import Popen
  23
  24 SEG_REGEXP = r"^([0-9a-f]{8}-[0-9a-f]{4}-[0-9a-f]{4}-[0-9a-f]{4}-[0-9a-f]{12})(\.\S+)?$"
  25
  26 def build_parity_set(files, recoverycount):
  27     """Low-level function to call out to par2 to generate parity files.
  28
  29     Given a specific list of files, use par2 to generate a set of checksums for
  30     recovery of that exact file list.  Arrange so that at least recoverycount
  31     files can be lost from the set and still recover the data.
  32     """
  33
  34     files.sort()
  35     name = md5.md5()
  36     for f in files: name.update(f)
  37     name = name.hexdigest()
  38
  39     maxsize = max([os.stat(os.path.join(basedir, f)).st_size for f in files])
  40     blocksize = (maxsize + 15) // 16
  41     blocksize = (blocksize + 3) & ~3
  42
  43     print name, blocksize, files
  44
  45     p = Popen(["par2", "create", "-s%d" % (blocksize,),
  46                "-c%d" % (recoverycount * 16), "-n%d" % (recoverycount,),
  47                "-u", "-v", "parity-%s" % (name,)] + files,
  48               cwd=basedir)
  49     retcode = p.wait()
  50     if retcode:
  51         raise RuntimeError("Nonzero return code from par2: %s" % (retcode,))
  52
  53     descfile = open(os.path.join(basedir, "parity-%s.manifest" % (name,)), 'w')
  54     descfile.write("%d\n" % (recoverycount,))
  55     for f in files:
  56         descfile.write(f + "\n")
  57     descfile.close()
  58
  59 def generate_parity(files):
  60     """Generate parity files for the given list of input files.
  61
  62     This will automatically break the list of input files into smaller chunks,
  63     and generate separate parity files for each chunk.
  64     """
  65
  66     files = list(files)
  67     files.sort()
  68
  69     while files:
  70         count = min(16, len(files))
  71         redundancy = 1 + count // 4
  72         build_parity_set(files[0:count], redundancy)
  73         files = files[count:]
  74
  75 def remove_parity(manifest):
  76     """Delete the given set of parity files and associated metadata."""
  77
  78     suffix = '.manifest'
  79     if manifest.endswith(suffix):
  80         manifest = manifest[:-len(suffix)]
  81     matches = [f for f in file_list if f.startswith(manifest)]
  82     print "Delete", matches
  83     for f in matches:
  84         os.unlink(os.path.join(basedir, f))
  85
  86 basedir = sys.argv[1]
  87 file_list = os.listdir(basedir)
  88
  89 parity_list = [f for f in file_list if re.match(r"^parity-.*\.manifest$", f)]
  90 segment_list = set(f for f in file_list if re.match(SEG_REGEXP, f))
  91
  92 to_delete = []
  93
  94 for p in parity_list:
  95     files = [l.strip() for l in open(os.path.join(basedir, p))]
  96     redundancy = int(files[0])
  97     files = files[1:]
  98     missing = 0
  99     for f in files:
 100         if not os.access(os.path.join(basedir, f), os.F_OK):
 101             missing += 1
 102     min_redundancy = 1 + len(files) // 8
 103     if missing:
 104         print "Parity set %s is missing %d files, can recover %d more" \
 105             % (p, missing, redundancy - missing)
 106     if redundancy - missing < min_redundancy or missing:
 107         to_delete.append(p)
 108     else:
 109         segment_list.difference_update(files)
 110
 111 print "Need parity:", list(segment_list)
 112 generate_parity(segment_list)
 113
 114 print "Deleting:", to_delete
 115 for p in to_delete:
 116     remove_parity(p)