软件即服务(SaaS)是云计算的一种重要的应用交付形式,被服务提供商广泛采用,且已经成为中小企业使用先进软件技术的重要渠道。SaaS模式下,成熟的服务运营商一般采用单实例多租赁的方式,启动一个应用实例为众多租户提供有共性的服务,这种应用被称为多租户应用。服务提供商将多租户应用部署在云中,供租户以按需付费的方式来租赁这些应用。服务提供商根据租户的需求及支付能力,提供不同服务质量的SaaS应用以备不同租户所租赁。租户为确保获得稳定服务质量,与SaaS提供商签订服务水平协议(SLA,Service-Level Agreement)。查询响应时间是SLA中重要的性能指标,若查询响应时间超出了SLA规定的截止时间,租户则无法及时得到数据查询结果,导致较低的SaaS体验。当查询响应时间违背服务水平目标时,服务提供商需须根据签订的SLA向租户支付一定的罚金。服务提供商根据每个租户的需求及支付的应用租赁费用与租户签订不同等级的SLA。如何有效的进行查询优化,提高查询效率,满足不同用户的SLA,以最小化SLA惩罚成本,已成为服务提供商关注的问题。服务提供商从成本与收益的角度希望用较少的资源成本尽可能满足所有租户的查询SLA,因此多租户数据库需在租户间共享查询处理资源,优化资源利用率。共享资源的多租户数据查询处理结构必然会出现多个租户查询争用资源,进而导致一些租户查询违反SLA。为最小化服务提供商SLA惩罚成本最小化,需在云计算环境下对SaaS多租户数据查询进行优化,其所面临的主要问题和挑战包括：(1)多租户数据处理需要良好的云组织架构。多租户数据库有着租户数量多,数据量大的特点,同时租户不断加入与离开数据库,这就需要依赖云计算平台来完成多租户数据处理。大量的节点与数据需要良好的数据组织、节点组织及数据定位方法,从而为查询SLA惩罚成本的优化提供基础。然而,目前给出清晰有效的多租户数据云组织架构的文献较少。(2)以租户为单位的资源分配粒度过大,仍有需进一步优化的空间。以租户的单位的资源的分配较易实现,目前多以租户粒度对SLA惩罚进行优化。然而,一个租户的诸多查询在惩罚成本、访问频率、占用资源量方面也有不同的属性。因此,需要以查询为单位对处理资源进行分配与调度,更加精细的进行查询优化。(3)多租户应用用户众多,查询并发数量多,易造成处理的性能瓶颈。特别是在负载较高时,云中众多节点负载不平衡,会导致一些查询无法在截止时间前完成,增加SLA的惩罚成本。云中去中心化的组织结构是避免性能瓶颈较为有效的手段。因此,降低SLA惩罚成本的查询优化需基于云中去中心化的组织结构。(4)当查询处理节点处于满负荷运行时,容易造成较多查询违约。当云中各处理节点配置完毕后,多租户的数据查询到达率并不稳定,当处于查询到达高峰时,各查询会对有限的处理资源竞争占用。这时若采用开辟新的处理节点或者租户数据迁移的方式为租户分配资源,无法敏捷、及时地解决资源争用问题。因此,需要设计一种高峰时期的查询处理应急机制,使违约的惩罚最小。本文在云计算环境下,以服务提供商的惩罚成本最小化为目标,结合租户数据的隔离性、定制性特点,对多租户的数据查询优化的索引、缓存、调度环节展开研究与讨论,主要工作和贡献包括：(1)针对多租户数据处理需要良好的云组织架构的问题,建立了一个支持P2P结构的多租户索引机制,该机制对云中的多租户数据及索引、节点进行组织,避免了集中式索引的性能瓶颈,同时为后续基于SLA的查询处理优化提供了良好的数据组织基础。该索引支持租户查询对隔离性的需求,即在利用索引获取数据时避免获取到其他租户无效数据。该机制支持索引项的顺序存储,支持SaaS应用常见的比较查询、范围查询。该机制将属于一个租户的索引与数据集中地存储在尽可能少的节点上,避免了租户查询处理时大量数据传输。该机制提供了动态扩展性,可以利用云计算平台的伸缩性为无限数量的租户提供索引服务。实验结果表明,在租户数量与节点数量达到一定规模时,该机制的单点查询时间与范围查询时间比集中式索引分别至少节省50%与75%,惩罚成本至少可以降低20%。(2)针对资源分配粒度过大问题,建立了一个SLA感知的多租户数据缓存管理机制,在P2P结构下根据不同租户查询的特征及违约惩罚值对多租户数据库的缓存进行优化,降低服务提供商的惩罚成本。建立了缓存数据与查询惩罚成本的量化关系,为选取缓存数据提供了依据。该机制为每个节点生成缓存数据,能够较大幅度降低总体惩罚成本。可以较高效率完成跨节点的缓存数据调整。在该机制中,任意节点都可以迅速完成租户查询的分发,使租户查询在处理时间最短的节点上被处理。通过实验验证了在云计算平台上,其惩罚成本比基准算法至少减少30%。(3)针对当查询处理节点处于满负荷运行时,容易造成较多查询违约的问题,建立了一个最小化SLA惩罚成本的多租户查询去中心化调度机制,通过确定每个查询的处理节点与处理时间,在处理资源紧张的条件下,优先保证关键查询在截止时间前返回,从而达到惩罚成本最小化。该机制根据租户查询的违约惩罚值、截止时间的急迫性,赋予每个租户查询一个优先级,优先级高的租户查询会被先处理,从而达到总体惩罚成本最小化。该机制基于P2P结构使每个节点都参与调度,避免了调度的性能瓶颈。改进了租户查询等待调度队列的数据结构,可以在大量的租户查询快速地完成查询的查找、插入与删除操作,提高了调度的效率。实验表明,在租户查询达到一定数量时,该调度机制的惩罚成本至少比基准方案低50%。该机制将调度的时间复杂度从O(N)降低到O(log~2N),实验表明一个租户查询的调度时间稳定在2ms左右,且不随租户查询数量增加而变化。