Increasingly, Software-as-a-Service (SaaS) is becoming a dominant mechanism for the consumption of software by end users. From a vendor's perspective, the benefits of SaaS arise from leveraging economies of scale, by serving a large number of customers ("tenants") through a shared instance of a centrally hosted software service. Consequently, a SaaS provider would, in general, try to drive commonality amongst the requirements of different tenants, and at best, offer a fixed set of customization options. However, many tenants would also come with custom requirements, which may be a pre-requisite for them to adopt the SaaS system. These requirements should then be addressed by evolving the SaaS system in a controlled manner, while still supporting the needs of existing tenants. This need to balance tenant variability and commonality, and to optimize on development and testing effort, can make the evolution of multi-tenant SaaS systems an interesting engineering challenge; this has strong economic undertones as well, given the "pay-per-use" subscription model of SaaS, and the cost of incremental development and maintenance to cater to new tenant needs. In this paper, we outline a set of research issues in the design, testing and maintenance of multi-tenant SaaS systems, and highlight some of the interesting optimization questions that arise in the process. Presenting specific technical solutions is beyond the scope of this paper - instead, our goal is to help shape a research agenda for multi-tenant SaaS that can provide stimulus for further investigation into this area by the software and service engineering research community. © 2011 ACM.