[0:14]Hotspot mitigation for virtual machine migration. Preface: content of this lecture. We will discuss hotspot mitigation techniques and algorithms to automate the task of monitoring and detecting hotspots in the cloud system. By determining new mapping of physical to virtual resources and initiating the necessary virtual machine migration. This all we will discuss in the topic hotspot mitigation techniques for virtualized data centers. Here, we will cover two different schemes. One is called black box approach that is fully operating system and application agnostic. The other approach is called as a gray box approach that exploits operating system and application level statistics. We will also see the paper which has given these two approaches to solve the hotspot mitigation problem. Using virtual machine migration for virtualized data center. Enterprise data centers are composed of large number of clusters of servers. So in a typical example you can see here two pictures, which shows the racks full of these servers. And it comprises a large cluster and this all is packed in a room and this is called data center. This data center has along with the servers the storage devices are also there along with them and sufficient network devices are there to connect with the outside world. These particular data centers are used to run many applications and many applications are running on a particular server. Or a particular application is running on a spanning multiple servers also. So this will provide a shared hosting environment for the applications to run in this environment. This becomes a multi-tier and may span over multiple servers those applications. Now another important thing is the allocation of resources to these applications has to meet to the service level agreements. Which is a contract between the customer and the application provider and that application in turn will require these resources from the data center to be allocated to the application. Hence, the allocation of the resources has to meet the service level agreements. And in this environment of sharing the data center resources across many applications is done only with the help of the technique which is called virtualization. Let us see the benefits of virtualization.
[4:09]It will enable to run multiple applications on one server, that means the server will be multiplexed across different applications.
[4:39]Second benefit of virtualization is that it will maintain the isolation across different applications which sits together in a particular machine. So the co-located applications are provided with sufficient isolation and the security provisions.
[5:12]So that they may not interfere with each other and yet they will be multiplexing and sharing the resources of the of the physical machines or the servers. Third benefit here is that it will rapidly adjust the resource allocation to the application. For example, the application may require additional CPU on a priority basis or it will require more memory to be allocated to the application, all these are possible in the scenario of virtualized data center. Fourth benefit of virtualization is the virtual machine migration, that will be the transparent to the application. So the application will not know about where this particular, which server is being used for running that particular application and it is all transparent. Virtual machine migration will support the cause of adjusting the resource allocation. If let us say more resources are required and that server which is currently running the application doesn't have that many number of resources, so it will be migrated. This is called virtual machine migration and in this migration, there will not be any downtime for the applications and also it will incur the less overhead. This is all possible with the help of virtualization techniques. So how can we use virtualization to more efficiently utilize the data center resource becomes a very, very important task for the researchers. To ponder with, let us see the data center workloads. These data centers are very popular to host wide variety of applications such as web applications, enterprise systems, e-commerce sites, which are running for the customers. So they these all applications requires the data center to be used and they will generate the dynamic workloads of different workloads. This dynamic workload will fluctuate due to the incremental growth of the workloads and also during the time of the day effects. For example, there are some peak hours when many customers are accessing these e-commerce website or doing the navigation during the office hours, maybe the peak time.
[8:12]So the time of the day also affects this dynamic workload fluctuations and also due to the flash crowds, sometimes will generate lot of workload.
[8:31]And this will guarantee or this will generate the dynamic workload fluctuations which are basically due to the incremental growth or during the day time of the day effects or during or due to the flash crowds. So how can we provision these resources to meet these challenging demands while meeting the service level agreements is not a trivial task.
[9:14]Now we will see the provisioning methods which will allocate the resources as per the workload or a dynamic workload demand. And what are the issues involved, we will call it as the provisioning methods. Now if the resource demands exceed the provisioned capacity, then we say that the hotspots will form. Over-provisioning of the resources means that they are the resources are allocated as per their peak load calculations. And they have to be ensured as per the service level agreement, SLAs. So over-provisioning, though wastes lot of resources and also is not very suitable for dynamic workloads and also very difficult to predict the peak resource requirements. So here we will see this over-provisioning methods which will basically, how we will ensure it according to the service level agreements. Another thing is called dynamic provisions. That means due to the workload fluctuations, a dynamic provisioning also is required to be in place. So this will adjust the resource allocation based on the dynamic workload fluctuation. Often it is done manually but it lacks with the agility if it is done through the in a manual way. We will understand this way that why manually will lack the agility. Therefore, dynamic provisioning has to be done in an automatic manner. Now let us understand the problem for this particular discussion.
[11:25]So given this particular scenario, how can we automatically monitor for the resource usage and how can we detect the hotspots. And then mitigate the hotspots after finding them that is how to determine the new mapping and initiate the necessary virtual machines migration. Therefore, the problem for this particular discussion is to detect and mitigate the hotspots in a virtualized data center environment. So again we will recall this word hotspot means that if the resource demands exceeds the provision capacity. So hotspot mitigation problem is that once we have to detect the hotspot, that also is not trivial. We will see some of the methods how we can detect the hotspots and having detected the hotspots then we have to involve a new allocation strategy to deal with the overloaded virtual machines. And maybe sometimes requires the virtual machine migration, that is all contained in the hotspot mitigation algorithms. So mitigation of the hotspot algorithms will determine which virtual servers have that many that sufficient resources required by or provisioned virtual machines or required by the virtual machines. Therefore, it has to be migrated in order to mitigate the hotspots. So determining a new mapping of virtual machine to the physical machine that avoids the threshold violations specified as per the service level agreement is an NP-hard problem. That means there exists an NP-complete problem that is called multi-dimensional bin packing problem which can be reduced to the hotspot mitigation problem that we have just described. So if it is reduced, that means multiple multi-dimensional bin packing problem can be reduced to the hotspot mitigation problem where each server is a bin with the multiple dimension corresponding to the resource constraints and each virtual machine is an object that need to be packed with the equal with the size equal to its resource requirements. Even the problem of determining if a valid packing of multi-dimensional bin exists, to determine itself is a NP-hard problem. So this will pose the research challenges for this particular discussion. We will see some of the intricacies and we will also see what are the solutions available in the literature in this part of the discussion. So the research challenges for hotspot mitigation is to automatically detect and mitigate hotspot through the virtual machine migration. To do this, we have to decide when to migrate, where to migrate, and how much of these resources will be needed to allocate after the migration. This all migration problem is now is published in a paper which has proposed the method which is called sandpiper which is inspired from that bird called sandpiper which is a migratory bird.
[15:40]So how much information is needed to make these particular decisions? Let us see some of the terminologies as a background. Dynamic replication means that a dynamic provisioning approaches which are focused on dynamic replication where the number of servers allocated to an application is varied.
[16:13]A dynamic slicing, in a dynamic slicing a fraction of a server allocated to an application is varied. Application migration, in the virtualized scenario virtual machine migration is performed for dynamic provisioning. And this migration is transparent to the applications executing within the virtual machine. Let us understand the architecture of sandpiper scheme for hotspot mitigation problem. The entire architecture can be understood by looking at the physical machines that is nothing but the server. Server is we assume that it is virtualized using Zen virtual machine monitor or an hypervisor. Therefore, the entire server can run virtual machine on top of it which is shown over here as virtual machine one, virtual machine two. Now there is another virtual machine or that is a control virtual machine which is called a nucleus. So nucleus will monitor the resources of that particular server. This will report to the control plane. This is the control plane that is a global control plane across the data center. This particular nucleus will be per machine per server that we see that there are two different servers and every server is running a nucleus. This particular nucleus will run inside a special virtual server which is called domain zero in the Zen hypervisor. So nucleus is nothing but a monitoring engine of that particular server or a physical machine. Next comes the control plane. Control plane is a global plane or you can say that it's a global intelligence. Which comprises of this particular data center. So this intelligence will have the complete information about all the servers running in that particular data center and this information will be sent by the special virtualized server which is called as a nucleus. Now let us see the details of control plane, which is a centralized server. This particular control plane has three different components, the first one is called profiling engine. This profiling engine will get the profile of all the resources which are collected by the nucleus. And then it will decide using that particular profile of the resources how much of these resources are available and how much they are allocated. The next one is called hotspot detector. So it will detect when the hotspots are formed. We will see how this particular detection of hotspots are done in this part of the discussion, but let us see in the architecture where these algorithms will work. Finally, there is a manager which is called a migration manager. After detecting the hotspot, the migration manager has to decide about how to mitigate that hotspot. Therefore, it has to choose a physical machine where sufficient resources required by the hotspot virtual machine can be made available for the migration plan. This all will be decided by the migration manager where to where to migrate that particular virtual machine to mitigate the hotspots. This particular architecture has given also two different strategies or schemes for hotspot mitigation.
[21:01]The first one is called black box method.
[21:07]Here in the black box method this particular operating system and the application is agnostic. Therefore, only it has to collect the data from outside the virtual machine. It cannot go and see what is happening or the resource profile within that virtual machine. So outside the virtual machine it will collect the data or the profile and therefore it is called a black box. The other method is called the gray box. Here it is possible to look into inside the virtual machine and to collect the information of operating system statistics and application logs of that virtual machine. This particular information will generate a profile and also detect the request level data which will be required in the detection method. Now the question is is that black box good enough to solve all the problem? If not then what do we gain from the gray box method? Let us understand these methods in more detail to answer these particular question. Black box scheme for monitoring of hotspots. In this method since it is operating system and application agnostic, therefore it uses the profile and the information from the outside that is it will depend on the Zen hypervisor. So Zen hypervisor will require to have a special virtual machine which will collect the data from network and disk drivers and the nucleus will run based on that particular information. This will be an outside monitoring without looking into the details of what virtual machine is doing. Therefore, hypervisor will collect the scheduler statistics, it will collect the network device information statistics, it will also collect the memory, but memory will be detected only through the swapping from the disk IOs. And this will only be known when the performance is poor, why because it is only allowed to collect from the outside information. So black box monitoring will perform the CPU monitoring that is by incrementing the Zen hypervisor, it is possible to provide the virtual machine, that is domain zero, special control virtual machine. With access to the CPU scheduling events which is available with the hypervisor.
[24:21]These events are tracked to determine the duration for which each virtual machine is scheduled and the measurements of that interval when the CPU was allocated or being used by running that particular virtual machine. Similarly, the network monitoring will be done by the special control virtual machine that is domain zero in the Zen hypervisor by collecting the data from the network interface driver for this particular purpose.
[25:07]This particular information will be collected in black box for monitoring purposes. So black box monitoring is useful in the scenarios where it is not feasible to peek inside the virtual machine to gather the usage statistics, that is possible in most of the applications. So the hosting environments for instance runs the third party application and for example Amazon's Elastic computing cloud EC2 service provides a bare bone virtual server where customer can load their operating system images. So in such scenarios it is feasible to gather the operating system level statistics and also the logs to enhance the quality. Therefore, it is possible to do gray box monitoring. So gray box monitoring can be supported when feasible using a light-weight monitoring daemon that is installed inside each virtual server.
[26:10]This particular daemon can process the logs of the applications and to derive the statistics such as request rate, request drop and service times. These direct monitoring of application level statistics will enable the explicit detection of service level violations. So that means in a gray box has more access inside the statistics of the virtual machine in contrast to the black box approach. So what is a hotspot? So hotspot indicates a resource deficits on the underlying physical server to service the collective workloads of the resident virtual machine. So if there is a resource deficits then it will be called hotspot, why because that current server will not be able to allocate the physical resources to to handle the workloads of the resident virtual machine. So before the hotspots can be resolved through the migration, the service first determine the estimate how much such additional resources are needed by the overloaded virtual machine to fulfill their service level agreements. These estimates are then used to locate the servers with sufficient idle resources and then will initiate the virtual machine migration for hotspot mitigation. So let us see the hotspot detection, how this is done. This is very important algorithm. The hotspot detection algorithm is responsible for signaling a need for virtual machine migration when service level agreements are detected implicitly by the black box approach or explicitly by the gray box approach. The hotspot detection is performed on a per physical server basis in a black box approach. That is a hotspot is flagged if the aggregate CPU network utilization exceeds the threshold or if the total swap activities exceeds the threshold. The explicit service level agreement violations must be detected on a per-server basis in a gray box approach. A hotspot is flagged if the memory utilization of virtual machine exceeds a threshold or if the response time or the request drop rate exceeds the service level agreement specified values. To ensure a small transient spike need less trigger needless migration. A hotspot is flagged only if thresholds or SLAs are exceeded for a sustained time.
[29:07]Given a time series profile a hotspot is flagged if at least K out of N recent observations as well as the next predicted value exceed a threshold. With this constraint, we can filter out transient spikes and avoid needless migrations. The values of K and N can be chosen to make hotspot detection aggressive or conservative. For a given N, small values of K cause aggressive hotspot detection, while large values of K imply a need for more sustained threshold violations and thus a more conservative approach. In the extreme, N = K = 1 is the most aggressive approach that flags a hotspot as soon as the threshold is exceeded. Finally, the threshold itself also determines how aggressively hotspots are flagged; lower thresholds imply more aggressive migrations at the expense of lower server utilizations, while higher thresholds imply higher utilizations with the risk of potentially higher service level agreements violations.
[30:27]Let us see the hotspot detection that in addition to requiring K out of N violations, we also require that the next predicted value exceed the threshold. The additional requirement ensures that the hotspot is likely to persist in the future based on current observed trends. Also, predictions capture rising trends while preventing declining ones from triggering a migration. Sandpiper employs time series prediction techniques to predict future values. Specifically, the system relies on the auto-regressive family of predictors, where the Nth order predictor AR(N) uses N prior observations in conjunction with other statistics of the time series to make a prediction.
[31:19]To illustrate the first order AR(1) predictor, consider a sequence of observations U1, U2 to UK. Given this time series, we wish to predict the demand in the K + 1th interval. Then the first order AR(1) predictor makes a prediction using the previous value UK, the mean of the time series values μ and the parameter which captures the variation in the time series.
[31:53]The prediction UK + 1 is given by this particular formula shown over here.
[32:06]It depends upon the mean of the time series values μ and also the previous K different observations to predict the K + 1th possible value. Using this, it will detect it will conclude about the hotspot detection. Now when this hotspot detection will be done? Hotspot detection will be done when this particular resource requirements, they will touch their thresholds. So the potential thresholds if utilization exceeds the threshold then it will be flagged and the hotspot detection will be triggered. It's not to be triggered during a transient spikes, therefore it will only trigger for sustained overloads and it must be overloaded for K out of N measurements.
[33:09]To avoid the outliers of the spikes. So auto regression time series model we will see or we have been or it has been used here in hotspot detection which will be based on the historical data to predict the future values and also minimize in this process the impact of transient spikes. So here in this particular example, that if there is a transient spike, this will not trigger detection into the hotspot. But this particular K out of N observation will smooth this and only whenever there is a real sustained over load then only it will be triggered as an hotspot detection. So let us see the resource provisioning in black box method. So the provisioning components needed to estimate the peak CPU, network and memory requirement for each overloaded virtual machine to ensure that service level agreements are not violated even in the presence of peak workloads. So estimating the peak CPU network bandwidth will need the distribution profiles to estimate the peak CPU and network bandwidth needs of each virtual machine. That will be the tail of the usage distribution which will represent the peak usage over the recent past and is used as an estimate for the future peak needs. Now this particular estimation can be achieved by computing the high percentile of CPU and network bandwidth distribution as the initial estimate of the peak needs. To understand this, there is an example shown over here. If there are two virtual machines that are assigned the CPU weights 1:1 resulting in a fair share of 50% each. Assume that VM1 is overloaded and requires 70% now to meet its peak needs, whereas virtual machine two is underloaded which requires only 20% of the CPU. Then the work conserving Zen scheduler will allocate 70% to the virtual machine one. In this case, the tail of the observed distribution is a good indicator of virtual machine one's peak need. In contrast to the virtual machine two is using its entire fair share of 50%, then virtual machine one will be allocated exactly its fair share. In this case, the peak observed usage will only be 50%, an underestimation of the actual peak need. Since the system can detect the CPU as fully utilized, it will estimate the peak to be 50 + delta.
[36:12]Similarly, it is possible to estimate the peak memory needs where Zen hypervisor allows fixed amount of physical memory to be assigned to each resident virtual machine. This allocation represents a hard upper bound that cannot be exceeded regardless of the memory demand and regardless of the memory usage in other virtual machines. Therefore, the swap activity exceeds the threshold indicating memory pressure then the current allocation is deemed insufficient and is increased by the constant amount of memory requirement.
[36:55]Let us see the resource provisioning in the gray box method. Since the gray box method has access to the application level logs, information contained in the logs can be utilized to estimate the peak resource needs of the application. To estimate the peak needs, the peak request arrival rate is first estimated. Since the number of service requests as well as the number of dropped request are typically logged, the incoming request rate is the summation of these two quantities. Given the distribution profile of arrival rate, the peak rate is simply a high percentile of the distribution which is modeled as the G G1 queuing system. The behavior of such queuing system can be captured using the formula which is available in the in the theory of queues. This way the peak CPU can be estimated. Similarly, the peak network also can be estimated in this manner. Now having estimated all that requirement that is having detected the hotspot, let us see the virtual machine migration will take place. Before that, let us see what are the steps in a live virtual machine migration stages. So stage zero will say that during the pre-migration when the virtual machine running normally on a host A. So that means it will ensure that which are the active VMs on the host A and what are the alternative alternative physical host maybe preselected for the migration and what are the block devices which are mirrored and free resources which are maintained. This is basically a stage zero that is pre-migration. The next stage will be stage one will call reservation that is it will initialize the container in the target host. Now the overhead due to the copying that is stage two, what it will do? It will do a iterative pre-copy, it will enable the shadow paging and then it will keep on copying the dirty pages in the successive rounds. Then stage number three is called stop and copy. That means it will suspend the VM on the host A and it will generate the network traffic to redirect to the host B over the network and it will synchronize all the remaining virtual machine state to the host B.
[39:40]That is called stop and copy on the host B. Stage four is called commitment.
[39:50]So virtual machine state on host A is released. Finally, in stage five, this is called activation. So virtual machine will now start running on host B. It will connect to the local devices and resumes its local operations. So these stages we can understand in more details in this particular figure.
[40:55]The placement algorithm will first try the migration, displace the virtual machine from the high volume servers use the volume RAM to minimize the overhead.
[41:10]It will swap if necessary, swap a high volume virtual machine to a low volume one. Requires three different migrations. This entire paper is published in the form of black box and gray box strategies for virtual machine migration. This is published by the author Timothy Wood, Prashant Shenoy, Arun Venkataramani and Mazin Yousuf of University of Massachusetts Amherst and Intel Portland. This is published in NSDI 2007. There is another paper which is referred here is called Live virtual machine, live migration of virtual machines. This is by Christopher Clark and is published in NSDI 2005. Conclusion. Virtual machine migration is a viable tool for dynamic data center provisioning. In this lecture, we have covered an approach to rapidly detect and eliminate hotspots while treating each virtual machine as a black box. A gray box method which wherein we can look inside the virtual machine statistics. Gray box information can further be used to improve the performance in some scenarios. We can also do the proactive memory allocations in the gray box to make the virtual machines migration more efficient. There are several future work possible in this particular direction and this is going to be very useful topic in automating the virtualized data center and for building the cloud computing system. The future work entails as the improved black box memory based monitoring and also support for the replicated services. Thank you.
