The what, The from, and The to: The Migration Games in Deduplicated Systems

1. Summary

Motivation of this paper

• motivation

  • the high-level management aspects of large-scale systems (e.g. capacity planning, caching and cost of service) still need to be adapted to deduplication storage

    • data migration: file are remapped between separate deduplication domains, or volumes

      • volumes: a single server within a large-scale system, or an independent set of servers dedicated to a customer or dataset

        • employ a separate fingerprint index in each physical server

    • optimize several possibly conflicting objectives

      • the physical size of the stored data (after migration)
      • the load balancing between the system's volumes
      • the network bandwidth generated by the migration

• the main goal

  • formulate the general migration problem for deduplicated systems as an optimization problem

    • minimize the system's size
    • ensuring that the storage load is evenly distributed between the system's volumes (load balancing consideration)
    • the network traffic required for the migration does not exceed its allocation (traffic consideration)

Migration Games

• problem statement

  • minimizing migration traffic

    • the amount of data that is transferred between volumes during migration

  • load balancing

    • trade-off between minimizing the total physical data size and maximizing load balancing

      • extreme case: map all files to a single volume

    • evenly distribute the capacity load between volumes

      • use fairness metric: the ratio between the size of the smallest volume in the system and that of the largest volume (perfect: 1)

  • traffic constraint, load balancing constraint

    • traffic constraint: the maximum traffic allowed during migration
    • load balancing constraint: a margin of the average volume size

• Greedy (extend SketchVolume)

  • iterates over all the files in each volume, and calculates the space-saving ratio from remapping a single file to each of the other volumes

    • each phase is allocated an even portion of the traffic allocated for migration

    • load-balancing step

      • remap files from large volumes to small ones, until the volume sizes are within the margin defined for this phase

    • capacity-reduction step

      • use remaining traffic to reduce the system's size

• ILP (extend GoSeed)

  • all varaibles are boolean

  • objective: maximize the sum of sizes of all blocks that are deleted minus all blocks that are copied

    • acceleration methods

      • fingerprint sampling: k leading zeroes, reducing the number of blocks in the problem
      • solver timeout: halts the ILP solver's execution after a pre-determined runtime

• Clustering

  • main idea: files are similar if they are share a large portion of their blocks

    • create clusters of similar files and to assign each cluster to a volume
    • remapping those files that were assigned to a volume different from their original location

  • hierarchical clustering

    • in each iteration, merge the most similar pair of clusters into a new cluster

  • file similarity

    • use Jaccard index for shared blocks

  • traffic and load-balancing consideration

    • determine the maximal cluster size by estimating the system's size after migration

  • sensitivity to sample

    • rather than merging the pair of clusters with the smallest distance, we merge a random pair from the set of pairs with the smallest distances

  • constructing the final migration plan

    • for the same given system and migration constraints, execute the clustering process with different parameters, use the best deletion as the final result

Implementation and Evaluation

• trace:

  • MS, FSL, Linux (all of them are public)

• evaluation

  • basic comparison between algorithms

    • the deletion percentage of the initial system's physical size
    • balance score
    • the total runtime

  • sensitivity to problem parameters

    • effect of sampling degree
    • effect of load balancing and traffic constraints
    • effect of randomization on Cluster
    • effect of the number of volumes

2. Strength (Contributions of the paper)

• formulate a general migration problem with three approaches

  • a greedy algorithm, an ILP-based approach, and hierarchical clustering

3. Weakness (Limitations of the paper)

• does not provide a system to apply its algorithm

  • how to collect metadata for solving the optimization problem?

• hard to follow as the data migration problem is not common yet

  • only happens in very large-scale storage system

4. Some Insights (Future work)

• related work

  • SketchVolume-FAST'19

    • a greedy algorithm

  • GoSeed-FAST'20

    • files are remapped into an initially empty target volume

  • Rangoli-SYSTOR'13

    • a greedy algorithm for space reclamation

      • a set of files is deleted to reclaim some of the system's capacity

• data migration in distributed deduplication systems

  • if a subsystem becomes full while another subsystem has available capacity, migration is quicker and cheaper than adding capacity to the full subsystem