This paper systematically studies the cost impact of distributed in-memory caches on datacenter services. While memory used for these caches is often perceived to be expensive, we find that the resulting CPU savings from these in-memory caches far outweigh the cost of added memory. In fact, across a variety of both synthetic and production workloads, we find that adding distributed in-memory caches can lower total operating costs by 3 – 4×, even without considering their latency benefits. These cost savings can vary significantly across various architectures, such as storage layer caches, remote lookaside caches, and in-memory linked caches. We additionally evaluate cost for two emerging scenarios: caching rich application objects and strongly consistent cache. For the former, we find that caching application objects provides outsized benefits compared to their denormalized, key-value-style variants, up to 8× compared to reading from storage. For the latter, we observe that even a minimal version check for consistency can eliminate most of the cost benefits, calling for new designs for cost-effective consistent cache.

This paper argues that publish-subscribe (pubsub) systems bundle both a messaging abstraction and a hard-state storage layer, and that this hurts their robustness, performance, and correctness for a variety of use cases. Pubsub fails to achieve its central goal of decoupling publishers and subscribers, violates the end-to-end principle, and exposes an ad hoc storage abstraction with a bespoke API and limited power.

Remote, in-memory key-value (RINK) stores such as Memcached [6] and Redis [7] are widely used in industry and are an active area of academic research. Coupled with stateless application servers to execute business logic and a databaselike system to provide persistent storage, they form a core component of popular data center service architectures. We argue that the time of the RINK store has come and gone: their domain-independent APIs (e.g., PUT/GET) push complexity back to the application, leading to extra (un)marshalling overheads and network hops. Instead, data center services should be built using stateful application servers or custom in-memory stores with domain-specific APIs, which offer higher performance than RINKS at lower cost. Such designs have been avoided because they are challenging to implement without appropriate infrastructure support. Given recent advances in auto-sharding [8, 9], we argue it is time to revisit these decisions. In this paper, we evaluate the potential performance improvements of stateful designs, propose a new abstraction, the linked, in-memory key-value (LINK) store, to enable developers to easily implement stateful services, and discuss areas for future research.

Ensuring the freshness of client data is a fundamental problem for applications that rely on cloud infrastructure to store data and mediate sharing. Thialfi is a notification service developed at Google to simplify this task. Thialfi supports applications written in multiple programming languages and running on multiple platforms, e.g., browsers, phones, and desktops. Applications register their interest in a set of shared objects and receive notifications when those objects change. Thialfi servers run in multiple Google data centers for availability and replicate their state asynchronously. Thialfi's approach to recovery emphasizes simplicity: all server state is soft, and clients drive recovery and assist in replication. A principal goal of our design is to provide a straightforward API and good semantics despite a variety of failures, including server crashes, communication failures, storage unavailability, and data center failures.

Translating data and data access operations between applications and databases is a longstanding data management problem. We present a novel approach to this problem, in which the relationship between the application data and the persistent storage is specified using a declarative mapping, which is compiled into bidirectional views that drive the data transformation engine. Expressing the application model as a view on the database is used to answer queries, while expressing the database schema as a view on the application model allows us to leverage view maintenance algorithms for update translation. This approach has been implemented in a commercial product. It enables developers to interact with a relational database via a conceptual schema and an object-oriented programming surface. We outline the implemented system and focus on the challenges of mapping compilation, which include rewriting queries under constraints and supporting nonrelational constructs.

Traditional client-server applications relegate query and persistence operations on their data to database systems. The database system operates on data in the form of rows and tables, while the application operates on data in terms of higher-level programming language constructs (classes, structures etc.). The impedance mismatch in the data manipulation services between the application and the database tier was problematic even in traditional systems. With the advent of service-oriented architectures (SOA), application servers and multi-tier applications, the need for data access and manipulation services that are well-integrated with programming environments and can operate in any tier has increased tremendously. Microsoft‘s ADO.NET Entity Framework is a platform for programming against data that raises the level of abstraction from the relational level to the conceptual (entity) level, and thereby significantly reduces the impedance mismatch for applications and data-centric services. This paper describes the key aspects of the Entity Framework, the overall system architecture, and the underlying technologies. Categories and Subject Descriptors:

The ADO.NET Entity Framework provides a persistence layer for .NET applications that allows developers to work at a higher level of abstraction when interacting with data and data-access interfaces. Developers can model and access their data using a conceptual schema that is mapped to a relational database via a flexible mapping. Interaction with the data can take place using a SQL-based data manipulation language and iterator APIs, or through an object-based domain model in the spirit of object-to-relational mappers.We demonstrate how the Entity Framework simplifies application development using sample scenarios. We illustrate how the data is modeled, queried and presented to the developer. We also show how the provided data programming infrastructure can result in easier-to-understand code by making its intent more explicit, as well as how it can help with maintenance by adding a level of indirection between the logical database schema and the conceptual model that applications operate on.

Translating data and data access operations between applications and databases is a longstanding data management problem. We present a novel approach to this problem, in which the relationship between the application data and the persistent storage is specified using a declarative mapping, which is compiled into bidirectional views that drive the data transformation engine. Expressing the application model as a view on the database is used to answer queries, while viewing the database in terms of the application model allows us to leverage view maintenance algorithms for update translation. This approach has been implemented in a commercial product. It enables developers to interact with a relational database via a conceptual schema and an object oriented programming surface. We outline the implemented system and focus on the challenges of mapping compilation, which include rewriting queries under constraints and supporting non-relational constructs.

Many stateful services use the replicated state machine approach for high availability. In this approach, a service runs on multiple machines to survive machine failures. This paper describes SMART, a new technique for changing the set of machines where such a service runs, i.e., migrating the service. SMART improves upon existing techniques in three important ways. First, SMART allows migrations that replace non-failed machines. Thus, SMART enables load balancing and lets an automated system replace failed machines. Such autonomic migration is an important step toward full autonomic operation, in which administrators play a minor role and need not be available twenty-four hours a day, seven days a week. Second, SMART can pipeline concurrent requests, a useful performance optimization. Third, prior published migration techniques are described in insufficient detail to admit implementation, whereas our description of SMART is complete. In addition to describing SMART, we also demonstrate its practicality by implementing it, evaluating our implementation’s performance, and using it to build a consistent, replicated, migratable file system. Our experiments demonstrate the performance advantage of pipelining concurrent requests, and show that migration has only a minor and temporary effect on performance.

We present a link layer protocol called the multi-radio unification protocol or MUP. On a single node, MUP coordinates the operation of multiple wireless network cards tuned to non-overlapping frequency channels. The goal of MUP is to optimize local spectrum usage via intelligent channel selection in a multihop wireless network. MUP works with standard-compliant IEEE 802.11 hardware, does not require changes to applications or higher-level protocols, and can be deployed incrementally. The primary usage scenario for MUP is a multihop community wireless mesh network, where cost of the radios and battery consumption are not limiting factors. We describe the design and implementation of MUP, and analyze its performance using both simulations and measurements based on our implementation. Our results show that under dynamic traffic patterns with realistic topologies, MUP significantly improves both TCP throughput and user perceived latency for realistic workloads.

The wide-scale deployment of IEEE 802.11 wireless networks has generated significant challenges for Information Technology (IT) departments in corporations. Users frequently complain about connectivity and performance problems, and network administrators are expected to diagnose these problems while managing corporate security and coverage. Their task is particularly difficult due to the unreliable nature of the wireless medium and a lack of intelligent diagnostic tools for determining the cause of these problems.This paper presents an architecture for detecting and diagnosing faults in IEEE 802.11 infrastructure wireless networks. To the best of our knowledge, ours is the first paper to address fault diagnostic issues for these networks. As part of our architecture, we propose and evaluate a novel technique called Client Conduit, which enables boot-strapping and fault diagnosis of disconnected clients. We describe techniques for analyzing performance problems faced in a wireless LAN deployment. We also present an approach for detecting unauthorized access points. We have built a prototype of our fault diagnostic architecture on the Windows operating system using off-the-shelf IEEE 802.11 cards. The initial results show that our mechanisms are effective; furthermore, they impose low overheads when clients are not experiencing problems.

We describe the design of a Windows file-system directory service that ensures the persistence, integrity, privacy, syntactic legality, and case-insensitive uniqueness of the names it indexes. Byzantine state replication provides persistence and integrity, and encryption imparts privacy. To enforce Windows' baroque name syntax - including restrictions on allowable characters, on the terminal character, and on several specific names - we develop a cryptographic process, called "exclusive encryption," that inherently excludes syntactically illegal names and that enables the exclusion of case-insensitively duplicate names without access to their plaintext. This process excludes entire names by mapping the set of allowed strings to the set of all strings, excludes certain characters through an amended prefix encoding, excludes terminal characters through varying the prefix coding by character index, and supports case-insensitive comparison of names by extracting and encrypting case information separately. We also address the issues of hiding name-length information and access-authorization information, and we report a newly discovered problem with enforcing case-insensitive uniqueness for Unicode names.

The Farsite distributed file system provides availability by replicating each file onto multiple desktop computers. Since this replication consumes significant storage space, it is important to reclaim used space where possible. Measurement of over 500 desktop file systems shows that nearly half of all consumed space is occupied by duplicate files. We present a mechanism to reclaim space from this incidental duplication to make it available for controlled file replication. Our mechanism includes: (1) convergent encryption, which enables duplicate files to be coalesced into the space of a single file, even if the files are encrypted with different users' keys; and (2) SALAD, a Self-Arranging Lossy Associative Database for aggregating file content and location information in a decentralized, scalable, fault-tolerant manner. Large-scale simulation experiments show that the duplicate-file coalescing system is scalable, highly effective, and fault-tolerant.

With the increasing popularity of handheld devices and wireless local area networks (LANs), real-time applications such as Internet telephony are poised to become ubiquitous. While there has been a substantial amount of research on quality of service problems in the Internet, most end-to-end bandwidth allocation approaches, such as RSVP, have had limited success due to scalability and deployment issues. Starting with the observation that reserving bandwidth in the Internet backbone requires substantial infrastructure support, but reserving bandwidth in the first hop does not, we only focus on the first-hop reservation. We evaluate several first hop allocation schemes and determine their effectiveness in improving end-to-end performance. Since utilization of the reserved first-hop bandwidth depends on the remaining Internet path throughput, we characterize this throughput using traces collected from a popular Web site. Our analysis shows that different clients experience widely different throughputs, and that a significant portion of the clients receive very low throughput (e.g. less than 20 Kbps). We then evaluate several bandwidth allocation schemes for various congestion scenarios. Our results show that the scheme which takes into account of both the application data rate and available Internet path bandwidth yields the best performance. Moreover, the scheme performs even better if it adapts to the changing path properties. We discuss how path bandwidth can be measured without active probing, how frequently it needs to be measured, and how this measurement is incorporated into the first-hop bandwidth allocation algorithm.

Commercial databases support different isolation levels to allow programmers to trade off consistency for a potential gain in performance. The isolation levels are defined in the current ANSI standard, but the definitions are ambiguous and revised definitions proposed to correct the problem are too constrained since they allow only pessimistic (locking) implementations. This paper presents new specifications for the ANSI levels. Our specifications are portable: they apply not only to locking implementations, but also to optimistic and multi-version concurrency control schemes. Furthermore, unlike earlier definitions, our new specifications handle predicates in a correct and flexible manner at all levels.

Cooperative caching is a promising technique to avoid the increasingly formidable disk bottleneck problem in distributed storage systems; it reduces the number of disk accesses by servicing client cache misses from the caches of other clients. However, existing cooperative caching techniques do not provide adequate support for fine grained sharing. We describe a new storage system architecture, split caching, and a new cache coherence protocol, fragment reconstruction, that combine cooperative caching with efficient support for fine grained sharing and transactions. We also present the results of performance studies that show that our scheme introduces little overhead over the basic cooperative caching mechanism and provides better performance when there is fine grained sharing.

This paper describes a new scheme for guaranteeing that transactions in a clientlserver system observe consistent state while they are running.Thescheme ispresented inconjunction with at'toptimistic concurrency control algorithm, but could also be used to prevent read-only transactions from conflicting with read/write transactions in a multi-version system.The scheme is lazy about the consistency it provides forruming transactions and also in the way it generates theconsistency information.Thepaper presents results of simulation experiments showing that the cost of the scheme is negligible.The scheme uses multipart timestamps to inform nodes about information they need to know.Today the utility of such schemes is limited beeause timestamp size is proportional to system size and therefore the schemes don't scale to very large systems.We show how to solve this problem.Our multipart timestamps are based on real rather thm logical clocks; we assume clocks in the system are loosely synchronized.Clocks allow us to keep multipart timestamps small with minimal impact on performance: we remove old information that is likely to be known while retaining recent information.Only performance and not correctness is affected if clocks get out of synch.

This paper presents HAC, a novel technique for managing the client cache in a distributed, persistent object storage system.I-k2 is a hybrid between page and object caching that combines the virtues of both while avoiding their disadvantages.,It achieves the low miss penalties of a page-caching system, but is able to perform well even when locality is poor, since it can discard pages while retaining their hot objects.It realizes the potentially lower miss rates of object-caching systems, yet avoids their problems of fragmentation and high overheads.Furthermore, HAC is adaptive: when locality is good it behaves like a page-caching system, while if locality is poor it behaves like an object-caching system.It is able to adjust the amount of cache space devoted to pages dynamically so that space in the cache can be used in the way that Fcst matches tbe needs of the application.The paper also presents results of experiments that indicate that HAC outperforms other object storage systems across a wide range of cache sizes and workloads; it performs substantially better on the expected workloads, which have low to moderate locality.Thus we show that our hybrid, adaptive approach is the cache management technique of choice for distributed, persistent object systems.This research was supported in

Thor is an object-oriented database system designed for use in a heterogeneous distributed environment. It provides highly-reliable and highly-available persistent storage for objects, and supports safe sharing of these objects by applications written in different programming languages.Safe heterogeneous sharing of long-lived objects requires encapsulation: the system must guarantee that applications interact with objects only by invoking methods. Although safety concerns are important, most object-oriented databases forgo safety to avoid paying the associated performance costs.This paper gives an overview of Thor's design and implementation. We focus on two areas that set Thor apart from other object-oriented databases. First, we discuss safe sharing and techniques for ensuring it; we also discuss ways of improving application performance without sacrificing safety. Second, we describe our approach to cache management at client machines, including a novel adaptive prefetching strategy.The paper presents performance results for Thor, on several OO7 benchmark traversals. The results show that adaptive prefetching is very effective, improving both the elapsed time of traversals and the amount of space used in the client cache. The results also show that the cost of safe sharing can be negligible; thus it is possible to have both safety and high performance.

This paper describes an efficient optimistic concurrency control scheme for use in distributed database systems in which objects are cached and manipulated at client machines while persistent storage and transactional support are provided by servers. The scheme provides both serializability and external consistency for committed transactions; it uses loosely synchronized clocks to achieve global serialization. It stores only a single version of each object, and avoids maintaining any concurrency control information on a per-object basis; instead, it tracks recent invalidations on a per-client basis, an approach that has low in-memory space overhead and no per-object disk overhead. In addition to its low space overheads, the scheme also performs well. The paper presents a simulation study that compares the scheme to adaptive callback locking, the best concurrency control scheme for client-server object-oriented database systems studied to date. The study shows that our scheme outperforms adaptive callback locking for low to moderate contention workloads, and scales better with the number of clients. For high contention workloads, optimism can result in a high abort rate; the scheme presented here is a first step toward a hybrid scheme that we expect to perform well across the full range of workloads.