Embodiments of compression and formatting of data for data storage systems are disclosed. In some embodiments, a data storage system can compress fixed sized data before storing it on a media and format obtained variable sized compressed data for storing on the media that typically has fixed size storage granularity. One or more modules compress the incoming host data and create an output stream of fixed sized storage units that contain compressed data. The storage units are stored on the media. Capacity, reliability, and performance are thereby increased.