Dynamo: Amazon's Highly Available Key-value Store

[This is the first paper in which I've been able to tell that the authors are not native English speakers..]

Dynamo is a highly available decentralized storage system that sacrifices consistency (and ACID in general) for high availability. A few important assumptions about Dynamo are that it is used for applications needing to store only small objects and that it is used only in Amazon's non-hostile internal environment, hence removing the need to authenticate. Clients and servers make Service Level Agreements (SLAs) specifying certain system-related client expectations.

Dynamo was designed to take advantage of heterogeneity and to scale well, which it does through consistent hashing. By replicating data on multiple hosts and asynchronously propagating updates through these hosts, Dynamo provides high availability. It deals with failures through hinted handoffs, in which data for an unreachable node can be redirected and then put into the correct node at a later time. Dynamo provided an impressive amount of availability over 2 years at 99.9995% of requests.

Speculative Execution in a Distributed File System

Oops, ParLab opening + me losing the paper copy in Vegas -> didn't get to read before class/write a summary.

Deconstructing Process Isolation

This paper adds on to the afore-mentioned Singularity paper by presenting comparative costs of Singularity's selective use of hardware isolation. In a number of benchmarks, the number of cycles was very close for all the setups with SIPs and HIPs running in Ring 0; for the most part, the Ring 3 HIPs performed comparably as well, except for the small handful in which each process ran in an unprivileged non-kernel domain in Ring 3 and encountered 10x the number of cycles. This latter setup is apparently the one used in most hardware-isolated microkernel systems.

Singularity: Rethinking the Software Stack, Hunt & Larus

The Singularity project was started to re-examine design decisions of modern operating systems. The project consists of a microkernel operating system, C#-based programming language, and verification tools meant to address such shortcomings as security vulnerabilities, lack of robustness, and unexpected application interactions and failures. The three major features of Singularity are software-isolated processes (SIPs), use of contract-based channels for communication, and manifest-based programs (MBPs). SIPs were designed such that they could be easily garbage-collected; SIPs can only have pointers to their own memory or their memory on the exchange heap.

The authors place a huge amount of importance on safe, verified code, leading them to create Sing#. The overhead associated with run-time checking of the language accounts for an additional 4-5% of cycles, but the authors deem that an acceptable trade-off. It was interesting to note that the manifest-based configuration code syntax seems to be approaching Perl with its multiple dollar signs and forall keyword. Another interesting point was the distrust of the compiler Bartok and its ability to compile MSIL assuredly into safe native code.

Two-Phase Commit

This looks like another one of those awesome '80s database papers. Woo, R*! I think I'll pass.

** Update (Nov. 29, 2010): For some reason this blog entry seems to be attracting lots of traffic. Sadly, I don't have a review to offer of this paper, but I can share a quote and some advice for you if you want to learn more about Two-Phase Commit.

"Two-phase commit: isn't that just like a simplified Paxos?" My advice: read the original Two-Phase Commit paper by Mohan, Lindsay, and Obermarck. Then read Lamport's "Paxos Made Simple." Then re-read "Two-Phase Commit" and enjoy how easy the algorithm is.

Paxos Made Simple, Lamport

Paxos is a distributed consensus algorithm for a network of processes in which each process plays the role of proposer, acceptor, and learner. The algorithm is carried out in two phases; in the first phase, a proposer selects a proposal number and sends a prepare request to some majority of acceptors. An acceptor will only accept this proposal if it has not seen a larger proposal number, and if it accepts, it responds with the highest-numbered proposal it has previously seen. Before sending this response, the acceptor records its intended response to stable storage so that consensus can still be reached in case of failure.

In the second phase, the proposer awaits responses to its prepare requests. If a majority of the acceptors respond, then the proposer subsequently sends out an accept request for the value of the highest-numbered response it received. Each acceptor then accepts the value sent to it unless it has already responded to a prepare request for a larger value. The purpose of these carefully designed phases is to enforce the rule that only one value will be chosen solely from proposed values. The possibility of failure of one acceptor created a need for multiple acceptors, which then created a need for reaching consensus among these multiple acceptors. This paper's abstract was an effective attention-grabber. I can only imagine how painful the original paper was when Paxos was not explained in simple terms.

Implementing Declarative Overlays

P2 is a system used for the declarative construction of networks. P2's language OverLog can be used to specify overlays very concisely, requiring only 16 rules to express a Narada-style network and 47 for a Chord overlay. However, the conciseness of OverLog does not necessarily speak for the learnability of the language. Better readability (a la SQL) would help its popularity, particularly since OverLog's declarative nature is already somewhat foreign to the typical imperative-language programmer.

P2's modularity is useful in that unlike PIER, P2 can be used with a variety of underlying networks, building up a knowledge of the network from a small set of nearby neighbor addresses. Its architecture is based on Click, though P2 differs from Click in that P2 elements are meant to act as database operators rather than packet routing functions. Performance testing of P2 Chord overlays revealed expected performance on par with those of Chord itself. The results of hop-count, latency, and performance under churn were "acceptable" as the authors didn't expect to compete with hand-tuned implementations.

K42: Building a Complete Operating System

This paper discusses K42, a highly-customizable object-oriented operating system. K42 was designed to address some technology predictions made by the authors, including the rise of multiprocessors and 64-bit machines. One of the goals of K42 was the ability to scale up with multiprocessors, which was achieved through minimizing sharing using techniques like Protected Procedure Calls and clustered objects, and affected the design of memory management. K42's design places a lot of importance on locality and customizability; the latter feature is a really interesting one in that K42 allows each instance of a resource to be managed by different sets of object instances.

Also supported is dynamic customization through hot swapping and dynamic upgrade. K42 reduces system calls and storage/pinned memory in the kernel by moving thread-scheduling into user-space. However, this user-level scheduling creates problems when using pthreads. Though Windows was predicted to dominate the market, the authors decided to provide Linux compatibility in K42.

Lessons from Giant-Scale Services, Brewer

This paper discusses giant-scale services and their advantages, as well as maintaining high availability. The giant-scale services mentioned here are single-site, single-owner, well-connected clusters and provide ubiquitous infrastructure that allow users to access services and centralized data from multiple devices. The paper discusses load management and high availability as major factors in the design of giant-scale services.

The availability metrics of uptime, yield, and harvest, as well as the DQ principle are brought up in deciding whether replication or partitioning is a better scheme for increasing availability. The author agrees with the traditionally held viewpoint that replication is the better strategy, although he suggests that some combination of partitioning and replication could give finer recovery control. Good strategies for graceful degradation, disaster tolerance, and online evolution are crucial for high availability. The author mentions that he has developed tools to help design giant-scale systems, but the paper delves more into metrics and high-level topics instead of said tools.

The Impact of DHT Routing Geometry on Resilience and Proximity

This paper discusses DHTs and compares the performance of different routing designs. The paper focuses on routing geometry rather than algorithmic details. Flexibility, that is, the amount of freedom available in choosing neighbors and next-hop paths, is a direct consequence of the geometry and in turn affects such properties as static resilience, path latency, and local convergence. Geometries that have little optimal path route selection flexibility are tree, butterfly, XOR and hybrid geometries, while hypercube and butterfly geometries have little flexibility in neighbor selection.

Based on path latency experiments, the atuhors suggest that geometries only actually affect path latency based on their ability to implement Proximity Neighbor/Route Selection. The authors tentatively suggest that the comparatively simple ring geometry be used more frequently because it is flexible and performs just as well or better than other geometries in a variety of tests. It seems odd that the authors should sound so tentative about using ring geometries, seeing as Chord had already been successfully implemented prior to this paper's publishing.

Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications

Chord is a scalable lookup protocol that supports the operation of mapping a given key onto a node. It is fully distributed and attempts to load balance by acting as a distributed hash function. Nodes only need to keep track of a few successor nodes on the circle, which they maintain in a finger table. Chord allows for a dynamic network; it correctly maintains each node's sucessor and ensures that a node is responsible for every key. It uses stabilization to keep nodes' successor pointers correct but also allows for lookup retries in the event that stabilizing has not happened recently enough. This paper contained a lot of theoretical analysis about Chord in addition to simulation/experimental results, and the authors use these analyses to back up the idea that Chord functions correctly even in the face of incorrect or failed nodes.

The Click Modular Router

Click is a flexible software architecture for creating routers. These routers are built from components called elements, which represent small units of router processing and are implemented as C++ objects. Click routers support both push and pull connections but with carefully specified rules as to which output and input types can be connected to explicit Queue elements.

Click runs as a single-thread in the Linux kernel and supports handlers and hot-swapping for changing configurations. It uses polling instead of interrupts and achieves a much higher max loss-free forwarding rate than Linux with interrupts. Click supports extensions such as varying types of packet schedulers and dropping policies. The Click language paired with small, modular elements makes it simple for users to create quick configurations, but a few additions would be helpful such as the use of configuration variables to prevent the user from having to copy information manually.

U-Net: A User-Level Network Interface for Parallel and Distributed Computing

I decided to pass on this summary.

TCP Congestion Control with a Misbehaving Receiver

This paper discusses how a TCP receiver can misbehave by defeating congestion control measures through various attacks. The three attacks described are ACK Division, DupACK spoofing, and Optimistic ACKing. An ACK Division attack divides an acknowledgment for a data segment into multiple separate acknowledgments. DupACK spoofing involves sending back multiple acknowledgments for the last data segment received, and Optimistic ACKing is preemptive sending of acknowledgments for data that has not yet been received.

The first two cause the sender to send packets in a quick burst by quickly expanding the congestion window, while the third causes the sender to send data sooner than it originally would have. All three attacks were generally successful against the TCP implementations of a variety of OSes. The authors use a simple HTTP request in their test and provide graphs that clearly show that their exploits worked. The attacks were able to be implemented with a disturbingly small amount of code.

Congestion Avoidance and Control, Jacobson & Karels

This paper discusses techniques added for the sake of packet conservation in TCP. Three problems addressed are connections not getting to equilibrium, senders injecting new packets before old ones exit, and equilibrium not being attained due to limited resources on the path. The first problem is fixed through slow start. For every ack that arrives, two new ones are generated, opening the window exponentially.

The second problem is due to not estimating variation of round-trip time, ultimately causing packets to be retransmitted whose delivery has only been delayed; the authors provide an estimation method and also suggest the use of an exponential backoff timer for retransmits. The solution to this second problem, that is, taking variation into account, is one of the most important contributions of the paper because it hugely reduces the number of packets needing to be retransmitted. For the third problem, the authors note that a timeout is a good indicator of packet loss, which is a good indicator of congestion, hence suggestion to use timeout as a signal of congestion. Upon receiving a timeout, the congestion window is halved, and for each ack the congestion window is increased by 1/(congestion window).

ReVirt: Enabling Intrusion Analysis through Virtual-Machine Logging and Replay

ReVirt is a system logger that moves the operating system into a VM and then runs below the OS. It does this to avoid relying on the integrity of the OS being logged and also to allow replaying non-deterministic events. ReVirt is implemented as a kernel module in the host OS; using an OS-on-OS virtualization strategy, the authors argue that although attackers may gain control of a guest OS, their actions on the host OS are severely restricted, as the implemented VMM allows the guest kernel access to fewer than 7% of system calls.

To log enough information to replay non-deterministic events, the authors record asynchronous virtual interrupts and external input. They suggest cooperative logging as a way to reduce log volume. The authors pass off the overhead associated with kernel-intensive workloads (up to 58%) as being an acceptable tradeoff for security, although they only provide one brief case of how they successfully used ReVirt to find and analyze an intrusion.

Live Migration of Virtual Machines

This paper discusses live, in-service OS migration as opposed to migration at the process-level. Reasons for choosing this granularity include avoiding "residual dependencies" that require original host machines to remain accessible to migrated processes, transferring in-memory state consistently and efficiently, and separating the concerns of users and operators.

The approach to moving memory used is pre-copy migration, a multi-step process combining push and stop-and-copy techniques. The first phase in a push phase in which all pages are transferred to the new VM, and future phases transfer only pages that were modified during the previous round. Once the remaining pages are part of the frequently-written writable working set, the current VM is suspended, the remaining pages are transferred, and the new VM is started. This pre-copy approach improved upon the amount of downtime caused by a full stop-and-copy significantly for a number of different migrations.

The authors ignore the issue of having to deal with local resources; they make the assumption that migrations tend to happen in a cluster environment within a single LAN and that data centers tend to use network-attached storage in place of local disks.

Are Virtual Machine Monitors Microkernels Done Right?

This paper discusses a few areas in which microkernels and VMMs differ architecturally but in which VMMs seem to have gotten things right. The first of these areas is avoiding liability inversion, which happens to microkernels that rely on user-space components to continue execution instead of keeping individual VM failure isolated the way VMMs do.

The next area is making IPC performance irrelevant, which VMMs do by making communication between VMs look like device interactions instead of through IPC- and RPC-based interfaces. Lastly, and perhaps most importantly for their mainstream adoption, is the treatment of operating systems. VMMs were designed to support existing OSes, avoiding the additional efforts required by microkernels to do so after the fact.

Xen and the Art of Virtualization

Xen is a virtual machine monitor that allows many instances of an operating system to share hardware together. It employs the use of paravirtualization but with support for existing ABIs and multi-application OSes. Memory is statically partitioned between each guest OS domain to provide strong isolation, although the guest OS may request additional memory pages or return unused ones to Xen. Xen uses disk I/O rings to handle requests from the guest OSes. I/O requests placed by the OSes may be reordered before Xen handles them and places the completed ones back in the ring.

XenoLinux performs similarly to Linux in regards to context switch times, file system latency, various process benchmarks, and so on. The differences, such as in the execution of fork, exec, and sh, are due to verifications Xen must make of page table updates since the guest OS runs at a lower privilege level than the Xen hypervisor.

Eddies: Continuously Adaptive Query Processing, Avnur & Hellerstein

An eddy is a query processing mechanism that can reorder queries at runtime for optimization purposes. Eddies were designed to minimize synchronization barrier overhead and take advantage of moments of symmetry for reordering. The authors use a pre-optimizer to set up joins and kept this step very simple so that the focus stayed on eddies. An eddy keeps track of which operators the input tuples have been processed by and only outputs tuples that have been seen by every eligible operator.

The "naive eddy" works well for operators with the same selectivity, whereas the "fast eddy" takes into account both the consumption and production rates, and hence both cost and selectivity, via lottery scheduling. A window scheme is added to the lottery scheduling to only take recent history into account, allowing the eddy to adapt over time to changes in performance and data.