A data storage apparatus includes an interface and one or more processors. The interface is configured for communicating with a cloud-based object storage system 5 having a built-in versioning mechanism that assigns version numbers to objects stored therein. The one or more processors are configured to receive data for storage from one or more workloads, to store the data as objects in the cloud-based object storage system, and to 10 update and record reference counts for at least some of the objects, by forcing the built-in versioning mechanism of the cloud-based object storage system to update the version numbers so as to match the reference counts.