Cloud-Service Providers (CSPs) can now handle heavy workloads by occasionally renting resources from public clouds. The capabilities and respective lease prices of such infrastructure may significantly vary over time. In this environment, two distinct types of SLAs have to work in tandem: a) the SLA furnished by the private cloud to the end user of the application (or database), and b) the SLA offered by the public cloud to the application through its host private cloud. This dual and continuously evolving relationship inherently complicates the computation of the operation of cloud applications. In this paper, we present a cost-aware resource provisioning algorithm for No SQL-databases that aims to meet Quality of Service (QoS) requirements while minimizing the total cost incurred by its deployment on multiple cloud tiers. Our method is based on look-ahead optimization and takes into account the costs incurred by potential database transitions to new configurations in a heterogeneous multi-cloud environment. Experimentation with a prototype shows that our approach reflects the total cost of a cloud application more accurately than the conventional technique of minimizing SLA violations. More importantly, it avoids thrashing of resources.