A data storage device includes a data store optimized organized into allocation units sized according to an sequential writing unit or garbage collection unit of the data store. Information is written to the allocation units as either coarse or fine-grained packets, which are packets of data that are self-describing and written together. Random writes received from a host to data already written into allocation units is written to another allocation unit, and a coarse-grained forward map is updated to reflect the physical location of the valid data that superseded data in the allocation unit until the allocation unit can be rewritten. Promotion operations are disclosed to compact data and garbage collect data by rewriting allocation units.