Research On Component Scheduling Algorithm For User Satisfaction

With the development of the Internet,the scale of online service system has rapidly expanded.However,Moore's Law has gradually lost efficacy.Traditional monolithic architecture cannot satisfy the ever-growing demand for computing.Distributed component architecture has gradually become the mainstream of the industry.The monolithic program of online service system is divided into several independent and single-function components,which are deployed in a virtual machine cluster and provide external services through message communication.This model is known as Micro-service Model.User satisfaction is one of the core indicators of online service systems.Nevertheless,research on component scheduling for user satisfaction is still lacking.For online service system with distributed component architecture,the satisfaction requirements of end user and service provider are analyzed in this thesis.Corresponding satisfaction model and quantification method are proposed separately.For each request of end user,the satisfaction is modeled as a score based on response time.Depending on the level of end user,requests are given different weight.The satisfaction utility is defined as the weighted sum of satisfaction score of all requests.The satisfaction of service provider is modeled as the operating cost under the premise of guaranteeing the satisfaction of end user.The operating cost is quantified as the number of machine hours,which is the product of the number of running nodes and the holding time.This thesis proposes a scheduling goal that minimizes the number of running machines when maximizing the satisfaction utility.According to whether the node pool has available nodes,the scheduling goal is decomposed into two cases:(1)When the node pool is sufficient,the system can ensure that all requests need not to be queued by dynamic scaling up.In this case,the response time only contains the processing time inherent in the business logic.Therefore,the satisfaction utility will achieve maximum and only the number of running machines is required to be minimized.(2)When the node pool is depleted,the system cannot dynamically scale up and some requests have to queue.Since the service provider has already devoted all nodes into the system,only the satisfaction utility of the request queue needs to be maximized.Traditional component deployment strategy requires single component per node.Generally,a single component is incapable to use different node resources evenly.Consequently,this strategy will result in resource wasting.A new strategy,which requires single component group per node,is proposed in this thesis.Components are divided into multiple groups and one component group is deployed on each node.In order to ensure that the component group leverages various resources in a balanced way,this thesis designs an affinity model,which is based on the coefficient of variation.For the reason that the dividing problem of components is NP-complete,a genetic algorithm named RBGA is designed to generate grouping scheme.To accommodate changes in traffic intensity,this thesis gives a dynamic node scaling algorithm named RBS.In order to maximize the satisfaction utility of request queue,a queue scheduling algorithm named MLPQ is brought up.Based on PhxRPC,we have developed a prototype system and have evaluated the above algorithms through simulation experiments.The experimental results show that the approximate ratio of RBGA fluctuates around 1.2.Compared with the single-component-pernode strategy,RBS has reduced the number of running nodes by 50%;MLPQ is able to obtain 30% more satisfaction utility than static priority scheduling algorithm.When MLPQ is combined with RBS,the satisfaction utility of the system will further increase by 45%.