Cost-Oblivious Storage Reallocation

Free registration required

Executive Summary

Databases allocate and free blocks of storage on disk. Freed blocks introduce holes where no data is stored. Allocation systems attempt to reuse such de-allocated regions in order to minimize the footprint on disk. When previously allocated blocks cannot be moved, this problem is called the memory allocation problem. It is known to have a logarithmic overhead in the footprint size. This paper defines the storage reallocation problem, where previously allocated blocks can be moved, or real-located, but at some cost. This cost is determined by the allocation/reallocation cost function.

  • Format: PDF
  • Size: 2.12 KB