Load balancing and auto scaling are important services in the cloud. Traditionally, load balancing is achieved through either hardware or software appliances. Hardware appliances perform well but have several drawbacks. They are fairly expensive and are typically bought for managing peaks even if average volumes are 10%of peak. Further, they lack flexibility in terms of adding custom load balancing algorithms. They also lack multi-tenancy support. To address these concerns, most public clouds have adopted software load balancers that typically also comprise an auto scaling service. However, software load balancers do not match the performance of hardware load balancers. In order to avoid a single point of failure, they also require complex clustering solutions which further drives their cost higher. In this context, we present HAVEN - a system for holistic load balancing and auto scaling in a multi-tenant cloud environment that is naturally distributed, and hence scalable. It supports multi-tenancy and takes into account the utilization levels of different resources as part of its load balancing and auto scaling algorithms. HAVEN leverages software-defined networking to ensure that while the load balancing algorithm (control plane) executes on a server running network controller software, the packets to be load balanced never leave the data plane. For this reason, HAVEN is able to provide performance at par with a hardware load balancer while still providing the flexibility and customizability of a software load balancer. We validate HAVEN on a hardware setup and our experiments confirm that it achieves high performance without any significant overheads.