Cloud Computing has emerged as a successful computing paradigm for efficiently utilizing managed compute infrastructure such as high speed rack-mounted servers, connected with high speed networking, and reliable storage. Usually such infrastructure is dedicated, physically secured and has reliable power and networking infrastructure. However, much of our idle compute capacity is present in unmanaged infrastructure like idle desktops, lab machines, physically distant server machines, and laptops. We present a scheme to utilize this idle compute capacity on a best-effort basis and provide high availability even in face of failure of individual components or facilities. We run virtual machines on the commodity infrastructure and present a cloud interface to our end users. The primary challenge is to maintain availability in the presence of node failures, network failures, and power failures. We run multiple copies of a Virtual Machine (VM) redundantly on geographically dispersed physical machines to achieve availability. If one of the running copies of a VM fails, we seamlessly switchover to another running copy. We use Virtual Machine Record Replay capability to implement this redundancy and switchover. In current progress, we have implemented VM Record Replay for uniprocessor machines over Linux KVM and are currently working on VM Record Replay on shared-memory multiprocessor machines. We report initial experimental results based on our implementation.
Our current prototype can efficiently record and replay a uniprocessor VM. We have also implemented record replay for multiprocessor VMs. Multiprocessor record replay is significantly harder due to the presence of race conditions on shared memory by multiple processors. We have implemented a page-ownership scheme based on CREW (concurrent read exclusive write) protocol @cite_8 to record and replay a guest OS. We can successfully replay an unmodified guest, albeit at high overheads. The overheads depend on the workload and could be as high as 2-3x slowdowns for 2-processor VMs. Another approach, DoublePlay @cite_6 , has been proposed to make multiprocessor record replay more performant. DoublePlay works by recording the order of all synchronization operations in the program being recorded. Because a guest OS could have arbitrary synchronization primitives, it is hard to directly use DoublePlay's ideas for VM Record Replay. We are currently working on approaches to make multiprocessor VM record replay faster.
@cite_6 @cite_8
2115855199 2167788414 2403712541 2130473288
Deterministic replay systems record and reproduce the execution of a hardware or software system. In contrast to replaying execution on uniprocessors, deterministic replay on multiprocessors is very challenging to implement efficiently because of the need to reproduce the order or values read by shared memory operations performed by multiple threads. In this paper, we present DoublePlay, a new way to efficiently guarantee replay on commodity multiprocessors. Our key insight is that one can use the simpler and faster mechanisms of single-processor record and replay, yet still achieve the scalability offered by multiple cores, by using an additional execution to parallelize the record and replay of an application. DoublePlay timeslices multiple threads on a single processor, then runs multiple time intervals (epochs) of the program concurrently on separate processors. This strategy, which we call uniparallelism, makes logging much easier because each epoch runs on a single processor (so threads in an epoch never simultaneously access the same memory) and different epochs operate on different copies of the memory. Thus, rather than logging the order of shared-memory accesses, we need only log the order in which threads in an epoch are timesliced on the processor. DoublePlay runs an additional execution of the program on multiple processors to generate checkpoints so that epochs run in parallel. We evaluate DoublePlay on a variety of client, server, and scientific parallel benchmarks; with spare cores, DoublePlay reduces logging overhead to an average of 15 with two worker threads and 28 with four threads. In the area of system architecture, there are two most significant trends: multi-core and system virtualization technology. Both of them have quite close relationship with energy efficient computing. Industry turns to integrate more cores on a single chip instead of increasing frequency to solve the heat problem. Meanwhile system virtualization could decrease the total power consumption by sharing the same platform among different operating systems. So the necessity of power management on the multi-core virtualization platform has become increasingly evident. However, traditional virtual machine monitor schedulers could not make efficient use of DVFS, and thus could not take it into considering that the guest OSes may run at different frequency. In order to address this problem, this paper designs a power efficient scheduler which uses the load and the power level of the guest OSes as feedback, and implements a prototype based on Xen virtual machine monitor. This scheduler allocates power credit to VCPU of each guest OS, accounts the power consumption of VCPU sat different speed levels and makes scheduler decision by integrating it to the credit oriented to CPU time slice sharing. It also uses utilization of processors as feedback and sets frequency according to the load change trends instead of the simple static relationship between load and frequency policies, so as to decrease the speed steps required by response to burst load change. Experiment results show that the scheduling fairness of guest OS improved when using DVFS as main power saving method, and the power consumption of the whole system can be reduced by 5 percent - 30 percent. Therefore, this framework for feedback scheduling could make efficient use of varieties of power saving methods and maintain ideal balance between overall system power saving and single core over heat. Many proposals for managing replicated data use sites running the Snapshot Isolation (SI) concurrency control mechanism, and provide 1-copy SI or something similar, as the global isolation level. This allows good scalability, since only ww-conflicts need to be managed globally. However, 1-copy SI can lead to data corruption and violation of integrity constraints [5]. 1-copy serializability is the global correctness condition that prevents data corruption. We propose a new algorithm Replicated Serializable Snapshot Isolation (RSSI) that uses SI at each site, and combines this with a certification algorithm to guarantee 1-copy serializable global execution. Management of ww-conflicts is similar to what is done in 1-copy SI. But unlike previous designs for 1-copy serializable systems, we do not need to prevent all rw-conflicts among concurrent transactions. We formalize this in a theorem that shows that many rw-conflicts are indeed false positives that do not risk non-serializable behavior. Our proposed RSSI algorithm will only abort a transaction when it detects a well-defined pattern of two consecutive rw-edges in the serialization graph. We have built a prototype that integrates our RSSI with the existing open-source PostgresR(SI) system. Our performance evaluation shows that there is a worst-case overhead of about 15 for getting full 1copy serializability as compared to 1-copy SI in a cluster of 8 nodes, with our proposed RSSI clearly outperforming the previous work [6] for update-intensive workloads. Bug reproduction is critically important for diagnosing a production-run failure. Unfortunately, reproducing a concurrency bug on multi-processors (e.g., multi-core) is challenging. Previous techniques either incur large overhead or require new non-trivial hardware extensions. This paper proposes a novel technique called PRES (probabilistic replay via execution sketching) to help reproduce concurrency bugs on multi-processors. It relaxes the past (perhaps idealistic) objective of "reproducing the bug on the first replay attempt" to significantly lower production-run recording overhead. This is achieved by (1) recording only partial execution information (referred to as "sketches") during the production run, and (2) relying on an intelligent replayer during diagnosis time (when performance is less critical) to systematically explore the unrecorded non-deterministic space and reproduce the bug. With only partial information, our replayer may require more than one coordinated replay run to reproduce a bug. However, after a bug is reproduced once, PRES can reproduce it every time. We implemented PRES along with five different execution sketching mechanisms. We evaluated them with 11 representative applications, including 4 servers, 3 desktop client applications, and 4 scientific graphics applications, with 13 real-world concurrency bugs of different types, including atomicity violations, order violations and deadlocks. PRES (with synchronization or system call sketching) significantly lowered the production-run recording overhead of previous approaches (by up to 4416 times), while still reproducing most tested bugs in fewer than 10 replay attempts. Moreover, PRES scaled well with the number of processors; PRES's feedback generation from unsuccessful replays is critical in bug reproduction.