Cost-oblivious storage reallocation

Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, Seth Gilbert

    Research output: Contribution to journalArticlepeer-review

    Abstract

    Databases allocate and free blocks of storage on disk. Freed blocks introduce holes where no data is stored. Allocation systems attempt to reuse such deallocated regions in order to minimize the footprint on disk. When previously allocated blocks cannot be moved, this problem is called the memory allocation problem. The competitive ratio for this problem has matching upper and lower bounds that are logarithmic in the number of requests and in the ratio of the largest to smallest requests. This article defines the storage reallocation problem, where previously allocated blocks can be moved, or reallocated, but at some cost. This cost is determined by the allocation/reallocation cost function. The objective is to minimize the storage footprint, that is, the largest memory address containing an allocated object, while simultaneously minimizing the reallocation costs. This article gives asymptotically optimal algorithms for storage reallocation, in which the storage footprint is atmost (1+∈) times optimal, and the reallocation cost is O((1/∈) log(1/∈)) times the original allocation cost, that is, it is within a constant factor of optimal when ∈ is a constant. The algorithms are cost oblivious, which means they achieve these bounds with no knowledge of the allocation/reallocation cost function, as long as the cost function is subadditive.

    Original languageEnglish (US)
    Article number38
    JournalACM Transactions on Algorithms
    Volume13
    Issue number3
    DOIs
    StatePublished - May 2017

    Keywords

    • Cost oblivious
    • Physical layout
    • Reallocation
    • Scheduling
    • Storage allocation

    ASJC Scopus subject areas

    • Mathematics (miscellaneous)

    Fingerprint

    Dive into the research topics of 'Cost-oblivious storage reallocation'. Together they form a unique fingerprint.

    Cite this