Features/QED/OnlineDefrag

QED's performance characteristics are very similar to raw except that it causes additional fragmentation. The following discusses how to implement online defragmentation in QED to attempt to address this over the life time of the VM

Identify Defragmentation Candidates

Search the L2 cache to find two clusters that when swapped will lead to less fragmentation. The following algorithm could be used for this:

def is_fragmented(l2e):
    if (l2e.file_offset - header_size) != l2e.virtual_offset:
        return True
    return False

def schedule_defrag(l2e, target_l2e):
    new_cluster = allocate_new_cluster()

    freeze_future_writes(target_l2e)
    copy_cluster(target_l2e, new_cluster)
    update_l2e_entry(target_l2e, new_cluster)

    freeze_future_writes(l2e)
    copy_cluster(l2e, target_l2e)
    old_cluster = l2e.file_offset
    update_l2e_entry(l2e, target_l2e.file_offset)

    copy_cluster(target_l2e, l2e)
    update_l2e_entry(target_l2e, old_cluster)

    unfreeze_future_writes(target_l2e)
    unfreeze_future_writes(l2e)
    free_cluster(new_cluster)

def try_to_defrag(l2e):
    target_l2e = qed_find_l2_cache_entry(l2e.file_offset - header_size)
    if target_l2e:
        schedule_defrag(l2e, target_l2e)
        return True
    return False

def defrag():
    for l2_table in l2_cache:
        for l2e in l2_table:
            if is_fragmented(l2e) and try_to_defrag(l2e):
                return True
    return False

Considerations

If power is lost during the schedule_defrag() routine, a block will be leaked. If we have support in the header for detecting an disk image that is not closed properly, we can identify the leaked block during fsck and attempt to allocate to it

L1 and L2 entries will never be defragmented with this algorithm. Meta data represents a small portion of the disk though so it's not clear that it's worth it initially.

Blocks are only defragmented if their metadata is cached. The current L2 cache will completely cache the meta data for a 100GB image.

This algorithm only works when it's possible to put a block at an exact location. A more sophisticated algorithm could attempt to not achieve best placement but merely achieve better placement in order to optimize contiguous regions.