Distributed storage has attracted large interest lately from both industry and researchers as a flexible, cost-efficient, high performance, and potentially secure solution for geographically distributed data centers, edge caching or sharing storage among users. This paper studies the benefits of random linear network coding to exploit multiple commercially available cloud storage providers simultaneously with the possibility to constantly adapt to changing cloud performance in order to optimize data retrieval times. The main contribution of this paper is a new data distribution mechanisms that cleverly stores and moves data among different clouds in order to optimize performance. Furthermore, we investigate the trade-offs among storage space, reliability and data retrieval speed for our proposed scheme. By means of real-world implementation and measurements using well-known and publicly accessible cloud service providers, we can show close to 9x less network use for the adaptation compared to more conventional dense recoding approaches, while maintaining similar download time performance and the same reliability.