sr_overlaps.py - playing with SR ranges overlap and gap detection

sr_overlaps.py

from swift.common.utils import Timestamp, ShardRange
from collections import defaultdict
from pprint import pprint


range_list_sharded = (('', 'b'), ('b', 'c'), ('c','d'), ('b', 'd'), ('d', 'l'), ('l', 'q'), ('q', ''))

range_list_good = (('', 'c'), ('c', 'f'), ('f', 't'), ('t', ''))
range_list_extra = (('', 'd'), ('d', 'g'), ('g', 's'), ('s', ''))

range_list_missing = (('', 'b'), ('b', 'c'), ('c','d'), ('l', 'q'), ('q', ''))

ts = Timestamp.now()
sr_sharded = [ShardRange("account/container", ts, lower, upper)
              for lower, upper in range_list_sharded]

sr_good = [ShardRange("account/container", ts, lower, upper)
           for lower, upper in range_list_good]
ts = Timestamp.now()
sr_split_brain = list(sr_good)
sr_split_brain.extend([ShardRange("account/container", ts, lower, upper)
       for lower, upper in range_list_extra])

sr_missing = [ShardRange("account/container", ts, lower, upper)
              for lower, upper in range_list_missing]

print('done')

def check_overlaps(ranges):
    lowers = defaultdict(list)
    uppers = defaultdict(list)
    ranges_left = list(ranges)
    complete_ranges = []
    range_fragments = []
    overlaps = False
    gaps = False

    for sr in ranges:
        lowers[sr.lower_str].append(sr)
        uppers[sr.upper_str].append(sr)
        if  len(lowers[sr.lower_str]) > 1 or len(uppers[sr.upper_str]) > 1:
            overlaps = True

    # Quick check for gaps
    if set(lowers.keys()).difference(set(uppers.keys())):
        gaps = True

    # Short cut
    if not overlaps and not gaps:
        return ranges, []

    def walk_range(lower, l=None, complete=True):
        if not l:
            l = []
        if lower in lowers:
            multiple = len(lowers[lower]) > 1
            for sr in lowers[lower]:
                if sr in ranges_left:
                    ranges_left.remove(sr)
                if sr.upper_str == "":
                    l.append(sr)
                    if complete:
                        complete_ranges.append(l)
                    else:
                        range_fragments.append(l)
                    return
                if multiple:
                    new_l = list(l)
                    new_l.append(sr)
                    walk_range(sr.upper_str, new_l, complete)
                else:
                    l.append(sr)
                    walk_range(sr.upper_str, l, complete)
        elif l:
            range_fragments.append(l)
            return

    walk_range('')
    while ranges_left:
        ranges_left.sort()
        walk_range(ranges_left[0].lower, complete=False)

    return complete_ranges, range_fragments


complete, frags = check_overlaps(sr_sharded)
print("== sharded (b-d to b-c, b-d) (need to do a set difference probably) ==")
print("complete:")
pprint(complete)
print("frags:")
pprint(frags)

complete, frags = check_overlaps(sr_good)
print("== Good case ==")
print("complete:")
pprint(complete)
print("frags:")
pprint(frags)

complete, frags = check_overlaps(sr_split_brain)
print("== split brain (full range - 2 ranges) ==")
print("complete:")
pprint(complete)
print("frags:")
pprint(frags)

complete, frags = check_overlaps(sr_missing)
print("== missing range (fragement paths) ==")
print("complete:")
pprint(complete)
print("frags:")
pprint(frags)