In a data storage system in which a full-size allocation unit is used for storage of uncompressed data, an optimal reduced size allocation unit is selected for storage of compressed data. Changes in the compressed size of at least one full-size allocation unit of representative data are monitored over time. The representative data may be selected based on write frequency, relocation frequency, or both. Compression size values are counted and weighted to calculate the optimal reduced allocation unit size. The optimal reduced size allocation unit is used for storage of compressed data. A full-size allocation unit of data that cannot be accommodated by a reduced size allocation unit when compressed is stored uncompressed.