Dynamo: Amazon's Highly Available Key-Value Store

Authors: Guiseppe DeCandia (Amazon.com), Deniz Hastorun (Amazon.com), Madan Jampani (Amazon.com), Gunavardhan Kakulapati (Amazon.com), Avinash Lakshman (Amazon.com), Alex Pilchin (Amazon.com), Swami Sivasubramanian (Amazon.com), Peter Vosshall (Amazon.com), and Werner Vogels (Amazon.com)

Paper: http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html

Amazon is a loosely coupled, service-oriented architecture. Each service is independent, but must adhere to latency SLAs. Availability is paramount.

RDBMS is a poor fit despite key-value being a good fit: most features unused, scales up and not out, and availability limitations.

Generally care more about availability than consistency.

Needs to be always writable, even in failure, even without previous context.

Want "knobs" to tune tradeoffs between cost, consistency, durability, and latency.

Overview:

• consistent hashing
• optimistic replication
• "sloppy quorum"
• anti-entropy mechanisms
• object versioning

Use a full membership model rather than overlay routing. Use virtual nodes for load balancing.

"Sloppy quorum": N replicas in ideal state, read from at least R nodes, write to at least W nodes. "Sloppy" because the membership is dynamic based on node availability. Different values for N, R, and W yield different characteristics for the resulting system.

Each write is a new version. In worst case, might read a stale read version. A write based on this creates a branch in the version history.

It is up to the application to resolve version history conflicts! All (relevant) versions returned to app!

Use vector clocks to take care of version history (preserves causality).

Lessons learned:

• (missed first)
• repartitioning is slow because propagating data to new nodes takes forever (gets throttled; lots of random disk I/O)
• use fixed arcs; allow transfer of whole database (a file copy, linear read on disk)

Limitations:

• no transactional semantics
• no ordered traversal
• no large objects
• does not scale indefinitely

Q: Failure seems to add load. What kind of MTTF do you need to avoid filling the key space?
A: We overprovision to deal with typical failure scenarios, including whole datacenter dying.

Q: When you need to add capacity, don't you need to shed load off of everybody?
A: Nodes have lots of neighbors. Adding nodes does pull load away from a bunch of others.

Q: How do you do reconciliation?
A: Use merkel hash tree for reconciliation?

Q: How do you prove that you met SLAs?
A: not sure

Q: Talk about the kind of conflicts you saw?
A: 99.94% of reads return single value. Most others returning two versions. Some of those might be returning write retries that happen in parallel.

Q: How often do you not achieve quorum?
A: Never!

Q: Ever been a partition?
A: Sure...rack files. Client can't see it though.

Q: Clients might potentially see lots of versions (even if it's rare). How do clients do reconciliation? No version ancestry?
A: Very application-specific. Sometimes last-write wins. Somewhat hard model to program to. Could potentially not garbage collect. No proof of convergence.

Q: Why did you go with consistent hashing?
A: High availability.

Q: What happens when some keys are more popular than others?
A: Often we don't see that. Often falls into the noise.

PeerReview: Practical Accountability for Distributed Systems

Authors: Andreas Haeberlen (MPI-SWS), Petr Kouznetsov (MPI-SWS), and Peter Druschel (MPI-SWS)

Paper: http://www.sosp2007.org/papers/sosp118-haeberlen.pdf

How do you detect faults when the system is federated and you can't see all of it? Specifically, how do you detect faults, how do you identify faulty nodes, and how do you convince evidence? Obviously, we need verifiable evidence.

Genera solution: keep a log, have an auditor that periodically inspects the log. Log is a hash chain (to prevent changing the log ex post facto).

Probabilistic log checking allows for scalability (otherwise overhead would be quadratic).

Q: How do you prevent collusion?
A: We used consistent hashing to choose witnesses, then secure routing.

Q: How do you deal with selective processing?
A: (reiterates what said in the talk)

Q: Seems like most appropriate to malicious faults given that it's all the same state machines. Is this useful for failing software?
A: (nothing useful...offline)

Q: (you misrepresented my CATS system...) How do you make logs visible in a secure way?
A: ??? Assume always at least one correct witness node.

Q: Why is non-repudiation work from 70s not applicable?
A: (Not sure what you're saying, offline)

Sinfonia: A New Paradigm for Building Scalable Distributed Systems

Authors: Marcos K. Aguilera (HP Labs), Arif Merchant (HP Labs), Mehul Shah (HP Labs), Alistair Veitch (HP Labs), and Christos Karamanolis (VMWare)

Paper: http://www.sosp2007.org/papers/sosp064-aguilera.pdf

(SOSP presentation)

This is an infrastructure for distributed applications. The general idea is to create a set of linear memories, and a particular memory address is identified by a node id and an offset. They use small, short-lived transactions with the semantics that if all read values match what the transaction expects, then the transaction commits.

They have a simplified 2-phase commit protocol with, essentially, no coordinator. The transaction blocks if _any_ of the application nodes crash, but they argue this isn't that big a deal because the action may involve application data located on the application node, and if the application node isn't available, you're screwed anyway (rough paraphrase).

They built a cluster file system and a group communication service.

Crap...wasn't paying attention to questions (at least, not writing them down). From what I remember:

- Why this and not a federated array of bricks?
- Are there any pathological cases you found that resulted in frequent rollback?
- other stuff...

Building distributed applications using Sinfonia

Authors: Marcos K. Aguilera, Christos Karamanolis, Arif Merchant, Mehul Shah, and Alistair Veitch

Paper: http://www.hpl.hp.com/techreports/2006/HPL-2006-147.pdf

So...this paper presents a system called Sinfonia that is designed to be intrastructure for building distributed systems. Sinfonia presents 3 features:

1. a global address space, sort of -- addresses are tuples of the form (node ID, address). Values can be read and written.
2. "minitransactions" -- minitransactions are transactions restricted to be short lived and consist of distinct read, compare, and write phases (in that order), and they may only manipulate values in the global address space
3. notifications -- a node may request to be notified when changes occur in the store in a particular range of addresses

I'm not clear enough on the distributed theory literature to be able to tell how interesting or novel their protocol is. I think it's uninteresting. More specifically, as most systems papers do, it describes the protocol in a rather ad-hoc manner that makes it difficult to get an overall feel for what is actually happening in the system. They spend a lot of time detailing a variant of two-phase commit wherein, oddly, the failure of a coordinator can be tolerated (i.e., the system won't block) but the failure of a participant can't. The rationale for this design decision is that the coordinator ends up being a client (i.e., application server) of the system, whereas the participants are actual Sinfonia nodes. It seems a bit odd to me that they designed a protocol that essentially tolerates no failures. This is supposedly not an issue given that Sinfonia nodes have hot-backups. Decisions within a minitransaction made by the primary are forwarded to the backup. I suppose I can buy this as a design decision if transactions are small and short-lived, but I don't really see why it's interesting.

Also, and as a side note, I'm always a bit dubious of the concept of backup servers. Are you really better off making a distinction between primary and backup servers as opposed to integrating all the servers you _would_ have employed as backups into the system itself? I.e., are you better off having n primaries and n backups instead of a system with 2n nodes? Seems like the latter would give you greater flexibility, in general, in allocating your resources. I suppose primary and backup are simply logical roles, and that any given physical server could play multiple roles at one time, but if you do that you might find yourself unintentionally compromising failure correlation assumptions (e.g., several of your logical backups live on a single physical machine that crashes, thus screwing you).

Anyway, moving on...the notifications don't seem that interesting except insofar as they interact with the minitransactions, except they don't really talk about this. As far as I can tell, the semantics of the notifications are very weak. If that's the case, would employing them in the same system as the mini-transactions undermine the supposedly strong semantics the mini-transactions are supposed to give you? I suppose if you treat notifications are purely advisory then you should be okay, but isn't that ultimately the same as interacting with a system that has the same weak semantics that you're trying to avoid?

Regardless, however, I suspect their system is very practical and works just fine. I just don't really see any new contribution here. The contribution would come in the form of easing application development and making ultimate end-systems more robust, but without a deployment in the real world to point to, that point is basically lost.