In multi-tenant clouds, service providers offer services to tenants and generate profits by deploying network function (e.g., NAT, VPN) instances. Tenants access services by forwarding their requests to corresponding instances. In practice, traffic dynamics typically result in load imbalances and overloads among instances, severely impacting QoS. Existing works primarily address these issues through request updating and elastic resource scaling. Request updating is a fast and feasible method but may incur significant costs since these methods need prepurchasing enough servers. Elastic resource scaling is an approach to save infrastructure costs but may degrade user QoS when adjusting the number of instances. This paper presents a problem called ESRU, aimed at providing a QoS-guaranteed and cost-effective elastic resource scaling and request updating in clouds. Furthermore, we propose the ESRU-A algorithm, which features a bounded approximation factor based on randomized rounding and a greedy strategy. Performance analysis indicates our algorithm can achieve optimal value with high certainty. Experiments conducted across various topologies and traffic dynamic scenarios have demonstrated that our proposed algorithm reduces infrastructure costs by up to 45.17% while increasing throughput by 58.17%, compared to state-of-the-art benchmarks.