Metadata

This paper investigates an interesting and promising research problem: how can we implement distributed transactions more efficiently by performing a cross-layer design of the transaction protocal/layer with the underlying distributed storage protocol/layer? This idea is motivated by the observation that there is wasted/duplicated work done both at the transaction layer and at the storage layer. The transaction layer already provides ordering (i.e., linearizability), and, if you look at the distributed storage layer, it also provides strongly consistent replication which orders/linearizes updates often with Paxos. The paper argues that this is overlapping functionality, and leads to higher latency and lower throughput. Ok, at this point, we have to take a step back and realize that we cannot avoid all coordination between the two layers. The distributed storage layer needs to be consistent with the order of updates at the transaction layer, because it serves reads and you like it to...

I have reviewed many Facebook papers in this blog before (see the links at the bottom for full list). Facebook papers are simple (in the good sense of the word) and interesting due to the huge scale of operation at Facebook. They are testaments of high scalability in practice. This one here is no different. This paper investigates the consistency of the Facebook TAO system. The TAO system is a replicated storage system for Facebook's social graph of billion vertices. In theory, TAO provides only eventual consistency. The interesting result in this paper is this: In practice, Facebook's TAO system is highly consistent, with only 5 inconsistency violations out of a million read requests! Facebook's TAO system TAO is basically 2-level memcached architecture backed by a database, as first discussed in NSDI'13 paper.  TAO architecture is given in Figure 1. As a prerequisite to TAO consistency discussion in the next section, it will be enough to review how TAO serves re...

Motivation for the paper Remember the 2-phase commit problem?  The 2-phase commit blocks when the initiator crashes. Or, after a server crash the client/initiator may not be able to determine whether the transaction is completed. And transaction blocks. Because if we retry we may end up giving inconsistent result or redoing the transaction which messes up linearizability. You need to have 3-phase commit to fix this. The new-leader/recovery-agent comes and tries to recommit things. Unfortunately, 3-phase commit solutions are complicated, there are a lot of corner cases. Lamport and Gray recommended that the Paxos consensus box can be used to remember the initiator's abort commit decision to achieve consistency, or more precisely they recommended the Paxos box remembers each participants decision  for the sake of shaving off a message in critical latency path. What this paper recommends is an alternative approach. Don't use Paxos box to remember the decision, instead use ...

Move fast and break things That was Facebook's famous mantra for developers. Facebook believes in getting early feedback and iterating rapidly, so it releases software early and frequently: Three times a day for frontend code, three times a day for for backend code. I am amazed that Facebook is able to maintain such an agile deployment process at that scale. I have heard other software companies, even relatively young ones, develop problems with agility, even to the point that deploying a trivial app would take couple months due to reviews, filing tickets, routing, permissions, etc. Of course when deploying that frequently at that scale you need discipline and good processes in order to prevent chaos. In his F8 Developers conference in 2014, Zuckerberg announced the new Facebook motto "Move Fast With Stable Infra." I think the configerator tool discussed in this paper is a big part of the "Stable Infra". (By the way, why is it configerator but not configu...

"The first principle is that you must not fool yourself --and you are the easiest person to fool."     ---Richard Feynman I agree with the second part. I am the easiest person to be fooled by myself, because I like to believe what is convenient, comfortable, less scary to me. For example, I am fooled to procrastinate, because I am scared of facing the task and not having a perfect complete product. Sometimes I am fooled to be overly optimistic, because I am scared of the alternative: failure and hassle. And sometimes I am fooled to be overly pessimistic, because I am scared of the long arduous fight to achieve something, so I say "No way, I won't be able to achieve it anyways". However, I like to propose a change to the first part of Feynman's quote. If it is so easy to fool yourself, you should exploit it: you should fool yourself in a beneficial manner to avoid fooling yourself in the usual/default harmful manner. For example, when you catch yourself...

The paper is available here. TensorFlow is Google's new framework for implementing  machine learning algorithms using dataflow graphs. Nodes/vertices in the graph represent operations (i.e., mathematical operations, machine learning functions), and the edges represent the tensors, (i.e.,  multidimensional data arrays, vectors/matrices) communicated between the nodes.  Special edges, called control dependencies, can also exist in the graph to denote that the source node must finish executing before the destination node starts executing. Nodes are assigned to computational devices and execute asynchronously and in parallel once all the tensors on their incoming edges becomes available. It seems like the dataflow model is getting a lot of attention recently and is emerging as a useful abstraction for large-scale distributed systems programming. I had reviewed Naiad dataflow framework earlier. Adopting the dataflow model provides flexiblity to TensorFlow, and as a result...

I liked this book a lot. It inspired me to write about "How to go for 10X" . That blog post and the "Zero to One" book I mentioned there got covered better than me b y Todd Hoff at his High Scalability blog . I am including my brief and unstructured notes on Zero to One book here just for the record. The main theme in the book is: Don't do incremental business, invent a new transformational product/approach. Technology is 0-to-1, globalization is 1-to-n. Most people think the future of the world will be defined by globalization, but the book argues that technology matters more. The book says: Globalization (copying  and incrementalism as China has been doing) doesn't scale, it is unsustainable. That's a hard argument to make, but a softer version of that argument is: "technology creates more value than globalization". A related theme is that you should aim to become a monopoly with your transformational product/technology. If you compete, e...

Pomodoro is a timeboxing technique . You set a Pomodoro timer for 25 minutes to get a task done. Then you take a break for 5 minutes, after which you can do another Pomodoro. Since Pomodoro imposes a limit on your work time, this adds a gaming element to the task. I have been using the Pomodoro technique for 3-4 years now and I had written about that before. Recently I changed my Pomodoro usage significantly. Now I use Pomodoro more deliberately to achieve intense mental workouts and to force myself to get more creative and obtain transformative results. Deep work versus Shallow work The problem I want to attack with this new deliberate Pomodoro practice is the shallow work problem. Human brain is programmed to save energy and go easy on itself, so it prefers shallow tasks (such as watching TV, web browsing, answering emails) and tries to avoid intense thinking sessions required for many creative tasks such as writing, thinking on a proof, and designing an algorithm. As a result,...

There have been amazing progress in technology in recent years . Just to name a few, I would mention deep learning, big data, ubiquitous tablets and smartphones, advances in medicine, BitCoin, 3D printing, accurate voice recognition, Arduino, Raspberry pie, maker movement, drones, etc. I can't help but wonder what we will see next, in the coming decade. What discoveries we will be able to make? How would the world change? I am very curious and excited about the future. To extrapolate to 2025, indulge me as I go back to the year 2005 to extrapolate. Ten years ago, iPhone was still not introduced (iPhone 1 got introduced on June 29, 2007). Smartphones were rare. Internet was not a household item. Cloud was not there. Tablets were not there. In fact, none of the technologies mentioned in the previous paragraph were there. In ten years we have come a long way. Let me add an anectode about how I witnessed this ride in the last 10 years. In 2005, I joined University at Buffalo as an ...

Below is the list of papers I plan to discuss in my distributed systems seminar in Spring'16 semester. These are all very exciting papers, and I am looking forward to the Spring semester. If you have some suggestions on other good/recent papers to cover, please let me know in the comments. Distributed coordination No compromises: distributed transactions with consistency, availability, and performance , SOSP 15 Implementing Linearizability at Large Scale and Low Latency , SOSP 15 High-Performance ACID via Modular Concurrency Control , SOSP 15 Existential Consistency: Measuring and Understanding Consistency at Facebook , SOSP 15 Holistic Configuration Management at Facebook , SOSP 15 Building Consistent Transactions with Inconsistent Replication , SOSP 15 Bolt-on Causal Consistency , Sigmod 13 The Design and Implementation of the Wave Transactional Filesystem Big data Arabesque: A System for Distributed Graph Mining , SOSP 15 Petuum: A New Platform for Distri...

This is a 2000 paper by Scott Stoller. The paper is about detecting global predicates in distributed systems. There has been a lot of previous work on predicate detection (e.g., Marzullo & Neiger WDAG 1991, Verissimo 1993), but those work considered vector clock (VC) timestamped events sorted via happened-before (hb) relationship. This paper proposes a framework for predicate detection over events timestamped with approximately-synchronized (think NTP) physical-time (PT) clocks. This was a tough/deep paper to read and a rewarding one as well. I think this paper should receive more interest from distributed systems developers as it has applications to the cloud computing monitoring services. As you can see in Facebook stack and Google stack , monitoring services are an indispensible component of large-scale cloud computing systems. Motivation Using PT for timestamping (and predicate detection) has several advantages over using VC. VC is O(N), whereas PT is a scalar. For c...