A growing amount of data is produced daily resulting in a growing demand for storage solutions. While cloud storage providers offer a virtually infinite storage capacity, data owners seek geographical and provider diversity in data placement, in order to avoid vendor lock-in and to increase availability and durability. Moreover, depending on the customer data access pattern, a certain cloud provider may be cheaper than another. In this respect is provided a method and a system that facilitates allocation of data objects in a distributed data storage environment. The system continuously adapts the placement of data based on its access patterns and subject to optimization objectives, such as storage costs. The system efficiently considers repositioning of only selected objects that may significantly lower the storage cost.