Cloud computing services are growing at an exponential rate and with it the cost of providing these services. For cost effectiveness, providers need to rely on multi-tenancy and resource sharing among tenants, since statically reserving resources for a tenant is prohibitively expensive. A major consequence of resource sharing is that the performance of one tenant can be adversely affected by resource demands of other co-located tenants. I will talk about the problem of effectively sharing resources such as memory and CPU in multi-tenant settings. Service level agreement (SLA) gives a framework that defines and enforces accountability of the service provider to the tenant even when the resource is not statically reserved on behalf of the tenant. We model the resource allocation problem as an online optimization problem that incorporates a rich variety of SLAs representing the diversity of clients’ requirements for resources as well as quality of service. We then design easy to implement algorithms that build on classical caching algorithms as well multiplicative weight update methods. The algorithms work under multi-tenant scenarios involving SLAs and overbooking. We use the framework of competitive analysis to analyze the performance of the algorithm. We will also describe results based on experiments that demonstrate the effectiveness of our solution in practice.