[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.
Wednesday, December 3, 2008
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.
Wednesday, November 26, 2008
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.
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.
Monday, November 24, 2008
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.
** 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.
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.
Wednesday, November 19, 2008
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.
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.
Subscribe to:
Posts (Atom)