Various implementations disclosed herein provide fault-tolerant enterprise object storage system that can store small objects. In various implementations, the fault-tolerant enterprise object storage system writes a small object into an aggregate object that is distributed across a plurality of storage entities. In some implementations, the small object is at least an order of magnitude smaller than the aggregate object, and the small object is within the same order of magnitude of a block unit addressable within each of the storage entities. In some implementations, based on the small object, the storage system updates the parity data associated with the aggregate object in response to writing the small object into the aggregate object. In various implementations, the storage system updates a processed data end offset indicator that indicates that the parity data for the aggregate object includes valid data up to and including the small object.