《报告人:王振坤 201556》由会员分享,可在线阅读,更多相关《报告人:王振坤 201556(17页珍藏版)》请在金锄头文库上搜索。
1、报告人:王振坤 2015.5.6,Tenant Placement in Multitenant Databases forProfit Maximization,介绍,作者 Ziyang Liu, Hakan Hacgms, Hyun Jin Moon, Yun Chi NEC Laboratories America 出处 EDBT/ICDT 13, March 18 - 22 2013,报告提纲,论文意义,多租户SLA利益最大化问题,前期租户规划,节点间负载均衡,节点内任务调度,报告提纲,论文算法,主要内容 通过减少成本和SLA违约赔偿来最大化收益 两种情况 Uniform query
2、processing time and the SLA penalty General case,论文算法,系统模型 Tenant and server load 租户: 表示:节点处理查询的能力/查询到达的速率 节点: 表示:f(T) 租户共存的影响因子 load(s)=1 表示处理能力与到达速率一致,箱子,石头,石头,石头,节点,租户,租户,租户,石头大小,租户load,箱子大小,节点load,注意: 1、箱子装满了不能再装,但是节点还可以 2、装箱是箱子最少,该问题还包括违约赔偿最少,论文算法,论文算法,租户放置算法 Baseline greedy algorithm based on
3、best fit Approximation algorithm for TP-Uniform Approximation algorithm for TP-General Dynamic programming,论文算法,Baseline greedy algorithm based on best fit 原理:任何一个租户,找大小最合适的节点放置 问题: 租户可以分解,如果租户足够小,即使节点的load接近1,添加一个小租户,也比新增一个节点花费少。另外在一个负载接近1的节点上,迁移多个租户到新的节点最终花费可能比迁移一个要少。(也就是说节点的load并不是越接近1越好,原因是违反了SL
4、A会有赔偿,论文算法,论文算法,论文算法,j=1 MP(i,1)说明前i个租户放在一个节点上 C(1,i) 表示1-i号租户放置在一起 j1 前i个放在j上的最小花费就是前k-1个租户放置在前j-1个节点 和 k到i 个租户放在一个节点上,报告提纲,个人研究思路,租户放置是大论文的第一个研究问题。 租户放置-危机探测消除-任务排工 使用算法一确定服务器的个数,动态规划算法向服务器分配租户 危机探测与消除(滑动窗口协议) 之前的论文汇报过 任务排工(简单有效才是合理,研究思路,任务排工 以查询任务为粒度进行排工 Slack time: 排工算法,研究思路,任务排工 SLO 1.相同租户的查询有相
5、同的SLA约束,所以到达的顺序就是deadline的顺序 2.查询请求到来,如果松弛时间大于队列里所有任务的执行时间,查询请求入队(说明该查询有足够的时间等待) 3.如果松弛时间小于队列里所有任务的执行时间(说明肯定有查询要违约) 反向遍历队里,找到第一个执行时间大于该查询的相同租户得作业,进行替换。 (一、替换使队列里的整体执行时间减少,二、替换以后不会影响其他作业的执行,三、虽然替换执行时间最大的那个比较好,但是队列太长为了提高速度替换第一个执行时间大的) 4.如果某个请求松弛时间小于0或者不能加入队列,就拒绝 SLA 上述的过程,差别是每个租户一个队列,根据租户得资源请求和SLA收益的高低分配相应的资源。并且VIP用户优先级高