Abstract:

A primary challenge to building reliable and secure computer systems is managing the persistent state of the system: all the executable files, configuration settings and other data that govern how a system functions. The difficulty comes from the sheer volume of this persistent state, the frequency of changes to it, and the variety of workloads and requirements that require customization of persistent state. The cost of not managing a system’s persistent state effectively is high: configuration errors are the leading cause of downtime at Internet services, troubleshooting configuration problems is a leading component of total cost of ownership in corporate environments, and malware—effectively, unwanted persistent state—is a serious privacy and security concern on personal computers.
In this paper, we analyze how computer systems dynamically interact with files and configuration settings in an attempt to gain insights into the problem of persistent state management. We analyze over 3648 machine days of these persistent state interactions, collected over an 8 month period from 193 machines. These machines are under real workloads and include Internet servers, corporate desktops, and home machines. We characterize the scope and magnitude of the persistent state management problem today, measuring not only the gross characteristics of persistent state, but also analyzing how it is used by applications, and when administrators and users modify it. We find that monitoring persistent state interactions provides important visibility and show how it can be used as a foundation for building better persistent state management tools.

Abstract:

Since the Internet's popular emergence in the mid-1990's, Internet services such as e-mail and messaging systems, search engines, e-commerce, news and financial sites, have become an important and often mission-critical part of our society. Unfortunately, managing these systems and keeping them running is a signicant challenge. Their rapid rate of change as well as their size and complexity mean that the developers and operators of these services usually have only an incomplete idea of how the system works and even what it is supposed to do. This results in poor fault management, as operators have a hard time diagnosing faults and an even harder time detecting them.

This dissertation argues that statistical monitoring|the use of statistical analysis and machine learning techniques to analyze live observations of a system's behavior| can be an important tool in improving the manageability of Internet services. Statistical monitoring has several important features that are well suited to managing Internet services. First, the dynamic analysis of a system's behavior in statistical monitoring means that there is no dependency on specications or descriptions that might be stale or incorrect. Second, monitoring a live, deployed system gives insight into system behavior that cannot be achieved in QA or testing environments. Third, automatic analysis through statistical monitoring can better cope with larger and more complex systems, aiding human operators as well as automating parts of the system management process.

The first half of this thesis focuses on a methodology to detect failures in Internet services, including high-level application failures, by monitoring structural behaviors that reflect the high-level functionality of the service. We implemented prototype fault monitors for a testbed Internet service and a clustered hashtable system. We also present encouraging early results from applying these techniques to two real, large Internet services.

In the second half of this thesis, we apply statistical monitoring techniques to two other problems related to fault detection: automatically inferring undocumented system structure and invariants and localizing the potential cause of a failure given its symptoms. We apply the former to theWindows Registry, a large, poorly documented and error-prone conguration database used by the Windows operating system and Windows-based applications. We describe and evaluate the latter in the context of our testbed Internet service.

Our experiences provide strong support for statistical monitoring, and suggest that it may prove to be an important tool in improving the manageability and reliability of Internet services.

Abstract:

Most Internet services (e-commerce, search engines, etc.) suffer faults. Quickly detecting these faults can be the largest bottleneck in improving availability of the system. We present Pinpoint, a methodology for automatic fault detection in Internet services by (1) observing low-level, internal structural behaviors of the service; (2) modeling the majority behavior of the system as correct; and (3) detecting anomalies in these behaviors as possible symptoms of failures. Without requiring any a priori application-specific information, Pinpoint correctly detected 89-96% of major failures in our experiments, as compared to 20-70% detected by current application-generic techniques.

Abstract:

Root cause localization, the process of identifying the source of problems in a system using purely external observations, is a significant challenge in many large-scale systems. In this paper, we propose an abstract model that captures the common issues underlying root cause localization and hence provides the ability to leverage solutions across different systems.

Abstract:

In this paper we show how to reduce downtime of J2EE applications by rapidly and automatically recovering from transient and intermittent software failures, without requiring application modifications. Our prototype combines three application-agnostic techniques: macroanalysis for fault detection and localization, microrebooting for rapid recovery, and external management of recovery actions. The individual techniques are autonomous and work across a wide range of componentized Internet applications, making them well-suited to the rapidly changing software of Internet services. The proposed framework has been integrated with JBoss, an open-source J2EE application server. Our prototype provides an execution platform that can automatically recover J2EE applications within seconds of the manifestation of a fault. Our system can provide a subset of a system's active end users with the illusion of continuous uptime, in spite of failures occurring behind the scenes, even when there is no functional redundancy in the system.

Abstract:

It is by now motherhood-and-apple-pie that complex distributed Internet services form the basis not only of e-commerce but increasingly of mission-critical network-based applications. What is new is that the workload and internal architecture of three-tier enterprise applications presents the opportunity for a new approach to keep them running in the face of both "natural" failures and adversarial attacks. The core of the approach is anomaly detection and localization based on statistical machine learning techniques. Unlike previous approaches, we propose anomaly detection and pattern mining not only for operational statistics such as mean response time, but also for structural behaviors of the system---what parts of the system, in what combinations, are being exercised in response to different kinds of external stimuli. In addition, rather than building baseline models a priori, we extract them by observing the behavior of the system over a short period of time during normal operation. We explain the necessary underlying assumptions and why they can be realized by systems research, report on some early sucesses using the approach, describe benefits of the approach that make it competitive as a path towards self-managing systems, and outline some research challenges. Our hope is that this approach will enable "new science" in the design of self-managing systems by allowing the rapid and widespread application of statistical learning theory techniques (SLT) to problems of system dependability.

Abstract:

Managing the configuration of computer systems today is a difficult task. Too easily, a computer user or administrator can make a simple mistake or lapse and misconfigure a system, causing instabilities, unexpected behavior, and general unreliability. Bugs in software that changes these configurations, such as installers, only worsen the situation. A self-managing configuration system should be continuously monitoring itself for invalid settings, preventing the bugs from harming the system. Unfortunately, while there are many constraints which can differentiate between valid and invalid settings, few of these constraints are explicitly written down, much less written down in a form usable by an automatic monitor. We propose an approach to automatically infer these correctness constraints based on samples of known good configurations. In this paper we present Glean, a system for analyzing the structure of configurations and automatically inferring four types of correctness constraints on that structure.

Abstract:

We present a new approach to managing failures and evolution in large, complex distributed systems using runtime paths. We use the paths that requests follow as they move through the system as our core abstraction, and our "macro" approach focuses on component interactions rather than the details of the components themselves. Paths record component performance and interactions, are user- and request-centric, and occur in sufficient volume to enable statistical analysis, all in a way that is easy reusable across applications. Automated statistical analysis of multiple paths allows for the detection and diagnosis of complex failures and the assessment of evolution issues. In particular, our approach enables significantly stronger capabilities in failure detection, failure diagnosis, impact analysis, and understanding system evolution. We explore these capabilities with three real implementations, two of which service millions of requests per day. Our contributions include the approach; the maintainable, extensible, and reusable architecture; the various statistical analysis engines; and the discussion of our experience with a high-volume production service over several years.

Abstract:

The cost and complexity of adminstration of large systems has come to dominate their total cost of ownership. Stateless and soft-state components, e.g. Web servers or network routers, are easy to manage: capacity can be scaled incrementally by adding more nodes, rebalancing of load after failover is easy, and reactive or proactive ("rolling") reboots can be used to handle transient failures. We show that it is possible to achieve the same ease of management for the state-storage subsystem by subdividing persistent state according to the specific guarantees needed by each type. While other systems have addressed persistent-until deleted state, we describe SSM, a store for a previously unaddressed class of state--user-session state--that exhibits the same manageability properties as stateless nodes while providing firm storage guarantees. ANy node can be proactively or reactively rebooted at any time to recover from transient faults, without impacting online performance or losing data. We exploit this simplified manageability by pairig SSM with an application-generic, statistical-anomaly-based framework that detects crashes, hangs, and performance failures, and automatically attempts to recover from them by rebooting faulty nodes. ALthough the detection techniques generate some false positives, the cost of recovery is so low that the false positives have low impact. We provide microbenchmarks to demonstrate SSM's built-in overload protection, failure management and self-tuning. We benchmark SSM integrated into a production enterprise-scale interactive service to demonstrate that these benefits need not come at the cost of significantly decreased throughput or response time.

Abstract:

This paper demonstrates that the dependability of generic, evolving J2EE applications can be enhanced through a combination of a few recovery-oriented techniques. Our goal is to reduce downtime by automatically and efficiently recovering from a broad class of transient software failures without having to modify applications. We describe here the integration of three new techniques into JBoss, an open-source J2EE application server. The resulting system is JAGR---JBoss with Application-Generic Recovery---a self-recovering execution platform.

JAGR combines application-generic failure-path inference (AFPI), path-based failure detection, and micro-reboots. AFPI uses controlled fault injection and observation to infer paths that faults follow through a J2EE application. Path-based failure detection uses tagging of client requests and statistical analysis to identify anomalous component behavior. Micro-reboots are fast reboots we perform at the sub-application level to recover components from transient failures; by selectively rebooting only those components that are necessary to repair the failure, we reduce recovery time. These techniques are designed to be autonomous and application-generic, making them well-suited to the rapidly changing software of Internet services.

Abstract:

We introduce macro analysis, an approach used to infer the high-level properties of dynamic, distributed systems, and an indispensable tool when faced with tasks where local context and individual component details are insufficient. We present a new methodology, runtime path analysis, where paths are traced through software components and then aggregated to understand global system behavior via statistical inference. Our approach treats components as gray boxes and complements existing micro analysis tools, such as code-level debuggers. We use runtime paths to deduce application state, detect failures, and diagnose problems, all in an application-generic fashion.

Abstract:

A major challenge in building ubiquitous computing systems is the large variety of heterogeneous devices. Building applications that cope with this heterogeneity requires managing massive amounts of quickly evolving information, mapping among the various semantically-equivalent functionalities of devices. We advocate using Internet services to store and collect these mappings. We are implementing this hypothesis in the IMHome project, focusing on the spontaneous interaction of media creation, storage, and playback devices. To evaluate IMHome, we are developing metrics to measure the dependability of IMHome-based applications.

Abstract:

The design constraints in ubiquitous computing (ubicomp) differ from those traditionally emphasized by the systems community: evolvability, long-term maintainability, and robustness to transient failures are essential, while scalability and performance are lesser concerns, due to the nature of ubicomp itself and the performance of today's commodity equipment. We show how these observations are reflected in the design of iROS, a ubicomp software framework in production use. In particular, we show that a centralized architecture directly enables the ubicomp programming abstractions needed while providing the best solution for evolvability and maintainability/deployability, and that we can achieve the required robustness through a fast-recovery strategy, which allows a simple centralized implementation of the architecture. Throughout, we achieve performance, scalability, and recovery behavior sufficient for typical operation.

Abstract:

High dependability in Internet services is a difficult challenge: new features are constantly added, the systems are being scaled to support more users, and these systems are subject to unpredictable workloads and inputs. To deal with these challenges, operators must constantly adapt and evolve their system in response to its dynamic behavior. We argue that this online evolution is necessary for the development and deployment of dependable Internet services. This paper presents a conceptual model of online evolution consisting of three phases--monitoring, analysis, and modification--and presents techniques we have found useful in speeding the process of online evolution.

Abstract:

It is time to broaden our performance-dominated research agenda. A four order of magnitude increase in performance since the first ASPLOS in 1982 means that few outside the CS&E research community believe that speed is the only problem of computer hardware and software. Current systems crash and freeze so frequently that people become violent. Fast but flaky should not be our 21st century legacy.

Recovery Oriented Computing (ROC) takes the perspective that hardware faults, software faults, software bugs, and operator errors are facts to be coped with, not problems to be solved. By concentrating on Mean Time to Repair (MTTR) rahter than Mean Time to Failure (MTTF), ROC reduces recovery time and thus offers higher availability. Since a large portion of system administration is dealing with failures, ROC may also reduce total cost of ownership. One to two orders of magnitude reduction in cost mean that the purchase price of hardware and software is now a small part of the total cost of ownership.

In addition to giving the motication and definition of ROC, we introduce failure data for Internet sites that shows that the leading cause of outages is operator error. We also demonstrate five ROC techniques in five case studies, which we hope will influence designers of architectures and operating systems.

If we embrace availability and maintainability, systems of the future may compete on recovery performance rather than just SPEC performance, and on total cost of ownership rather than just system price. Such a change may restore our pride in the architectures and operating systems we craft.

Mike Chen, Emre Kiciman, Eugene Fratkin, Eric Brewer, and Armando Fox
In Proceedings of International Conference on Dependable Systems, (International Performance and Dependability Track) 2002.

Abstract:

Traditional problem determination techniques rely on static dependency models that are difficult to generate accurately in today's large, distributed, and dynamic application environments such as e-commerce systems. In this paper, we present a dynamic analysis methodology that automates problem determination in these environments by 1) coarse-grained tagging of numerous real client requests as they travel through the system and 2) using data mining techniques to correlate the believed failures and successes of these requests to determine which components are most likely to be at fault. To validate our methodology, we have implemented Pinpoint, a framework for root cause analysis on the J2EE platform that requires no knowledge of the application components. Pinpoint consists of three parts: a communications layer that traces client requests, a failure detector that uses traffic-sniffing and middleware instrumentation, and a data analysis engine. We evaluate Pinpoint by injecting faults into various application components and show that Pinpoint identifies the faulty components with high accuracy and produces few false-positives.

Brad Johanson, Shankar Ponnekanti, Emre Kiciman, Caesar Sengupta, Armando Fox
Stanford University Interactive Workspaces Project Technical Note 2001-1, July, 2001

Abstract:

While work has been done on connectivity, mobility and general rendezvous systems for ubiquitous computing environments, research has been hampered by the lack of higher level application abstractions. To identify what these might be, we constructed a prototype ubiquitous computing environment which we call an Interactive Workspace, and observed how application writers attempted to use its facilities. We also identify system support issues for ubiquitous computing that differ from their counterparts in "traditional" single-node computing, and use them to guide the design of a set of abstractions to support ubiquitous computing applications deployed in spaces such as ours. Our implemented prototype meta-operating-system, iROS, and several applications in daily use on top of it, suggest that we have made progress toward the goal of pro-viding support for application-level ubiquitous computing abstractions in a way that is robust to transient failures, extensible, portable across installations, and easy to program. Finally, as we consider future work, we argue that the abstractions we identified (moving data around, moving interfaces around, and coordinating the behavior of existing monolithic applications) are fundamental to this style of ubiquitous computing generally.

Emre Kiciman, Laurence Melloul, Armando Fox
In Proceedings of the Eighth Workshop in Hot Topics in Operating Systems (HotOS VIII)

Abstract:

For many years, people have been trying to develop systems from modular, reusable components. The ideal goal is zero-code composition: building an application out of existing components without having to write code. By investigating zero-code composition, our goal is to make composition easy enough to be of practical use to systems reseawrchers and developers. We are focusing on identifying and removing systemic impediments to composition, and on exploiting composition to achieve system-wide properites, such as performance, scalability, and reliability.

Edward Swierk, Emre Kiciman, Vince Laviano, and Mary Baker
Proceedings of the 3rd IEEE Workshop on Mobile Computing Systems and Applications, December 2000

Abstract:

People now have available to them a diversity of digital storage devices, including palmtops, cell phone address books, laptops, desktop computers and web-based services. Unfortunately, as the number of personal data repositories increases, so does the management problem of ensuring that the most up-to-date version of any document is available to the user on the storage device he is currently using. We introduce the Roma personal metadata service to make it easier to locate current file versions and ensure their availability across different repositories. This centralized service stores information about each of a user's files, such as name, location, timestamp and keywords, on behalf of mobility-aware applications. Separating out these metadata from the data repositories makes it practical to keep the metadata store on a highly available, portable device. In this paper we describe the design requirements, architecture and current prototype implementation of Roma.

Emre Kiciman and Armando Fox
Proceedings of the Second International Symposium on Handheld and Ubiquitous Computing 2000 (Lecture Notes in Computer Science, Springer Verlag)

Abstract:

The original vision of ubiquitous computing is about enabling people to more easily accomplish tasks through the seamless interworking of the physical environment and a computing infrastructure. A major challenge to the practical realization of this vision involves the integration of commercial-off-the-shelf (COTS) hardware and software components: consider the awkwardness of such a mundane task as exporting a textual memo written on a Palm Pilot to a Microsoft Word document. It is not enough to overcome the protocol and data format mismatches that currently impede the interoperation of these entities: for the user experience to be truly seamless, we must provide a framework for the dynamic connection of such endpoints on demand, to support the ad-hoc interactions that are an integral part of ubiquitous computing. To this end, we offer a dynamic mediation framework called Paths. A Path consists of dynamically instantiated, automatically composable operators that bridge datatype and protocol mismatches between components wishing to communicate. Because operator composability is inferred from the type system, adding support for a new type of endpoint requires only incremental work; because the control and data flow for Paths are largely decoupled from the communicating endpoints, it is easy to connect COTS or legacy components. We describe the Paths architecture, our prototype implementation, and our experience and lessons based on several production applications built with the framework, and outline some continuing work on Paths in the context of the Stanford Interactive Workspaces project.

Helen J. Wang, Bhaskaran Raman, Chen-nee Chuah, Rahul Biswas, Ramakrishna Gummadi, Barbara Hohlt, Xia Hong, Emre Kiciman, Zhuoqing Mao, Jimmy S. Shih, Lakshminarayanan Subramanian, Ben Y. Zhao, Anthony D. Joseph, and Randy Katz
IEEE Personal Communications (2000): Special Issue on IP-based Mobile Telecommunications Networks

Abstract:

In the ICEBERG project at U.C. Berkeley, we are developing an Internet-based integration of telephony and data services spanning diverse access networks. Our primary goals are extensibility, scalability, robustness and personalized communication. We leverage the Internet's low cost of entry for service creation, provision, deployment, and integration. In this article, we present our solutions to signaling, easy service creation, resource reservation, admission control, billing and security in the ICEBERG network architecture.

Anthony Joseph, Barbara Hohlt, Randy Katz, and Emre Kiciman
Workshop on Mobile Computing and Systems and Applications, February 1999, work-in-progress

Abstract:

Technological progress is yielding a convergence of communication technologies, mobile devices, and "smart spaces" (environments that contain computer-controllable sensors, actuators, and I/O devices). Empowered by these advances, users are demanding access to and control of existing and new environments, information repositories, and applications.

There are many interesting complications associated with taking advantage of this progress: each of the communication networks has very different characteristics from the others (e.g., bandwidth, latency, cost, quality of service, etc.), the new devices have user interfaces that are quite different from their predecessor's graphical interfaces (e.g., they may have constrained screen sizes, no screens at all, or include new interfaces, such as audio or speech), and one significant complication is that every smart space is unique--no two have the same devices or interfaces.

It is the challenge and task of a user interface developer to provide users with many devices and many modes of interactions with a single, uniform interaction environment. Users should be able to choose the device that they want to use to interact with their information or environment--multi-modal user interfaces enable this choice.

There are two requirements in addressing the challenge of building multi-modal interfaces: application-level tools for describing and constructing interface components and system-level tools for automatically composing the components. Given these tools, user interface developers will be able to implement transcoding or transformational operators along with multi-modal interfaces, and then rely upon the environment to dynamically copmose operators and interfaces to serve new and existing devices.

One of the goals of the University of California, Berkeley's Iceberg project is to provide user interface developers with the system-level tools that they need, by exploring how to merge the different design philosophies and requirements that are associated with each of the communication networks, devices, and smart spaces. The project is constructing a large-scale testbed that will incorporate current and prototype technology. Once it is deployed, the testbed will provide a proving ground where one can explpore ideas for ubiquitous access to information, anywhere, anyplace, anytime, and using any I/O device.