报告人：王振坤 201556.ppt

《报告人：王振坤 201556.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、报告人：王振坤2015.5.6TenantPlacementinMultitenantDatabasesforProfitMaximization介绍作者ZiyangLiu,HakanHacıgümü¸s,HyunJinMoon,YunChiNECLaboratoriesAmerica出处EDBT/ICDT’13,March18-222013报告提纲论文意义1论文算法2个人研究思路3论文意义多租户SLA利益最大化问题租户放置装箱、退火问题：不是面向收益的危机探测与消除广度优先搜索爬山算法租户迁移增加节点副本角色替换任务排工S

2、LA-TreeiCBS改进排工算法前期租户规划节点间负载均衡节点内任务调度报告提纲论文意义1论文算法2个人研究思路3论文算法主要内容通过减少成本和SLA违约赔偿来最大化收益两种情况UniformqueryprocessingtimeandtheSLApenaltyGeneralcase论文算法系统模型Tenantandserverload租户：表示：节点处理查询的能力/查询到达的速率节点：表示：f(T)租户共存的影响因子load(s)=1表示处理能力与到达速率一致箱子石头石头石头节点租户租户租户石头大小租户load箱子大小节点

3、load注意：1、箱子装满了不能再装，但是节点还可以2、装箱是箱子最少，该问题还包括违约赔偿最少论文算法论文算法租户放置算法BaselinegreedyalgorithmbasedonbestfitApproximationalgorithmforTP-UniformApproximationalgorithmforTP-GeneralDynamicprogramming论文算法Baselinegreedyalgorithmbasedonbestfit原理：任何一个租户，找大小最合适的节点放置问题：租户可以分解，如果租户足够小

4、，即使节点的load接近1，添加一个小租户，也比新增一个节点花费少。另外在一个负载接近1的节点上，迁移多个租户到新的节点最终花费可能比迁移一个要少。（也就是说节点的load并不是越接近1越好，原因是违反了SLA会有赔偿）论文算法论文算法论文算法j=1MP(i,1)说明前i个租户放在一个节点上C(1,i)表示1-i号租户放置在一起j>1前i个放在j上的最小花费就是前k-1个租户放置在前j-1个节点和k到i个租户放在一个节点上报告提纲论文意义1论文算法2个人研究思路3个人研究思路租户放置是大论文的第一个研究问题。租户放置->危机探

5、测消除->任务排工使用算法一确定服务器的个数，动态规划算法向服务器分配租户危机探测与消除（滑动窗口协议）之前的论文汇报过任务排工（简单有效才是合理）租户放置算法一动态规划危机探测与消除滑动窗口任务排工改进排工算法研究思路任务排工以查询任务为粒度进行排工Slacktime：排工算法：研究思路任务排工SLO1.相同租户的查询有相同的SLA约束，所以到达的顺序就是deadline的顺序2.查询请求到来，如果松弛时间大于队列里所有任务的执行时间，查询请求入队（说明该查询有足够的时间等待）3.如果松弛时间小于队列里所有任务的执行时间（说

6、明肯定有查询要违约）反向遍历队里，找到第一个执行时间大于该查询的相同租户得作业，进行替换。（一、替换使队列里的整体执行时间减少，二、替换以后不会影响其他作业的执行，三、虽然替换执行时间最大的那个比较好，但是队列太长为了提高速度替换第一个执行时间大的）4.如果某个请求松弛时间小于0或者不能加入队列，就拒绝SLA上述的过程，差别是每个租户一个队列，根据租户得资源请求和SLA收益的高低分配相应的资源。并且VIP用户优先级高