Posts

Misc links edition July 3rd

-
Nice papers:Serverless in the Wild: Characterizing and Optimizing the Serverless Workload at a Large Cloud Provider
Starling: A Scalable Query Engine on Cloud Function Services
Lambada: Interactive Data Analytics on Cold Data using Serverless Cloud Infrastructure
LogPlayer: Fault-tolerant Exactly-once Delivery using gRPC Asynchronous Streaming
Automated reasoning for cloud computing systems
Distributed systems class from MIT
Interesting posts:Programming language design and compilers: where to start?
NYT Is Threatening My Safety By Revealing My Real Name, So I Am Deleting The Blog
Copy editing
Creating a positive lab culture from Margo Seltzer
Saccadic masking
Podcast suggestions: Revisionist History by Malcolm Gladwell
Against the Rules by Michael Lewis
Pet peeves:Lack of participatory and effective leadership across all levels and domains is disconcerting. Rough waters are truer tests of leadership. In calm water, every ship has a good captain.
The immense popularity of ML makes it hard to recrui…
Post a Comment
Read more

Enlightenment Now (2019) by Steven Pinker

-
Image
The full title of the book is Enlightenment Now: The Case for Reason, Science, Humanism, and Progress. It came out in 2019, and Bill Gates called this book his "new favorite book of all time." For me, it is an OK book, I give it a 3.5 stars out of 5. 
The book makes an important point about the importance of science and reason, and how much we accomplished thanks to them. As Yuval Harari nicely summarized, the book "extols the amazing achievements of modernity, and demonstrates that humankind has never been so peaceful, healthy, and prosperous."
Ok, so it is a feel-good book, nothing wrong with that, right? Well, it is a very long-winded book, and it is hard not to get bored after some time. I really liked the first 50 pages: "Ok, this is going good, we have a good rapport as writer and reader". After page 100, I was like "OK dude I really get it, let's move on to something new now", and after page 150, I was pleading "Stop, stop, this is…
Post a Comment
Read more

The FuzzyLog: A partially ordered shared log (OSDI'18)

-
Image
This paper appeared in OSDI 18, and is authored by Joshua Lockerman, Jose M. Faleiro, Juno Kim, Soham Sankaran, Daniel J. Abadi, James Aspnes, Siddhartha Sen, Mahesh Balakrishnan.
The paper does not suggest many novel ideas or algorithms, but rather shows a nice amalgamation of existing ideas and algorithms for providing a more scalable version of a shared log across multiple datacenters.
Having a shared log, and funneling all updates through a globally shared log  provides simplicity for building fault-tolerant consistent distributed systems. Tango paper from SOSP'13, upon which they build here, argued for the simplicity benefits of such a system. Recently Jay Kreps wrote a nice and accessible explanation of the benefits of using globally shared logs for building distributed systems.
Despite the simplicity it provides, maintaining a shared log with a system-wide total order is impractical, because it is expensive: At large scale, the single sequencer will be a bottleneck for the thro…
Post a Comment
Read more

State-Machine Replication for Planet-Scale Systems (Eurosys 2020)

-
Image
This paper appeared at Eurosys 2020, and is authored by Vitor Enes, Carlos Baquero, Tuanir França Rezende, Alexey Gotsman, Matthieu  Perrin, and Pierre Sutra.
The paper introduces Atlas, a consensus protocol similar to EPaxos, that builds on the Fast Paxos idea. Most people call these protocols leaderless, but I think that is a misnomer. I call these protocols as opportunistic/any-leader protocols. In these protocols, any node can propose a command by becoming an opportunistic leader and using a fast path. If there is no other simultaneously proposed command by another opportunistic leader or if this command commutes with all simultaneously proposed commands, the fast path is enough for achieving consensus. In the presence of concurrent non-commuting commands, the protocol will have to take a slow path, the purpose of which is to establish (teach to the other nodes) the dependencies learned for this command in the fast path attempt.
This opportunistic/any-leader family of protocols do n…
1 comment
Read more

Paxos unpacked

-
I am looking for PhD students to work with me on my project "Paxos Unpacked". I am attaching a short abstract below. The work done here is very useful for distributed databases and cloud computing systems.
So if you are interested in a distributed systems PhD, or you know someone interested in a distributed systems PhD, please let me know by emailing me with a short CV and qualifications. 
I will have research assistantship funding available for qualifying applicants after they get accepted to the PhD program at University at Buffalo, SUNY.

Paxos Unpacked
Due to their excellent fault-tolerance properties, Paxos protocols have been employed by many cloud computing systems for consistent coordination of clusters of computers. This project aims to show that when properly customized, Paxos family of protocols can also deliver top-notch performance and scalability, which they currently lack. To this end, the project will design high-performance, scalable, practical, and usable Paxos …
Post a Comment
Read more

Misc dist-links edition June 17th

-
Making Databases Work: the Pragmatic Wisdom of Michael Stonebraker, December 2018. This is available as a free download at https://dl.acm.org/doi/book/10.1145/3226595. In addition to databases, the book talks about Stonebraker's approach to advising and finding research problems. Datacenter RPCs Can Be General and Fast
CockroachDB: The Resilient Geo-Distributed SQL Database (Sigmod 2020)
eXtreme Modelling in Practice (VLDB 2020)
Beyond Analytics: the Evolution of Stream Processing Systems (Sigmod 2020)
Follow on Twitter: Jonathan Ellis, Neil Gunther, Steven Strogatz
ICYMI: Research, writing, and career advice and Learning about distributed systems: where to start?
Podcast suggestion: Weird name aside, this is a nice podcast. This one was particularly a very good listen. I put the Stephen Cope's book on my reading queue. As for true calling, I have this weird fixation with distributed systems. The first time I took an undergraduate class that introduced distributed systems and algorit…
Post a Comment
Read more

Research, writing, and career advice

-
Wow! I had written more than 30 advice posts over the last decade. 
When I was writing them, I was hoping to first help myself. You see, I understand a concept well only after I think about it in depth, distill it to a small set of principles, and connect it with my existing knowledge-base. Writing helps me achieve this, so I write on things I want to understand better.
These advice can also help you by showing you what to expect as you take on new projects. You can get a head start and avoid costly mistakes by learning from someone who had traveled down that road. 
I selected 21 posts, and categorized them as Research, Writing, and Career. Enjoy!
Research Learn by doing, realize we are all stupid, and just askPublish--not perish, work hard, and understand the philosophy of researchEndure the twisty journey to taste the joy of figuring things outSequence it, write it down, find the right perspective, and persevereUse writing to generate your best ideas, insight, and contentRead research pa…
Post a Comment
Read more

Popular posts from this blog

I have seen things

-
Image
I still don't have any idea what Instagram or Facebook stories is. Tried Googling and still don't have a good idea about it. — Murat Demirbas (@muratdemirbas) March 5, 2020 Yesterday Twitter spoke and told me that I am an old man, with overwhelming decisiveness. If this has been with any more votes, I would be declared part of the vulnerable population for Corona virus, one of the expendables as people seem to refer to them.

Twitter followers... I thought we were friends!

But, Ok, I get the point. I have seen things.

I was born in 1976. I understand that in the eyes of millennials 1976 is around the same time period as 1796. My son sometimes asks me if TV was invented when I was a child.

Yes, we had a black and white TV when I was growing up. And a dial phone, that was tethered to the wall.

At 7th grade, my dad got us a Commodore 64, and I played Boulderdash, Load Lode runner, Falcon Patrol etc.

At 9th grade, I saw the TV broadcasting the first Gulf War. I didn't follow …
Read more

SOSP19 File Systems Unfit as Distributed Storage Backends: Lessons from 10 Years of Ceph Evolution

-
Image
This paper is by  Abutalib Aghayev (Carnegie Mellon University), Sage Weil (Red Hat Inc.), Michael Kuchnik (Carnegie Mellon University), Mark Nelson (Red Hat Inc.), Gregory R. Ganger (Carnegie Mellon University), George Amvrosiadis (Carnegie Mellon University)

Ceph started as research project in 2004 at UCSC. At the core of Ceph is a distributed object store called RADOS. The storage backend was implemented over an already mature filesystem. The filesystem helps with block allocation, metadata management, and crash recovery. Ceph team built their storage backend on an existing filesystem, because they didn't want to write a storage layer from scratch. A complete filesystem takes a lot of time (10 years) to develop, stabilize, optimize, and mature.

However, having a filesystem in the path to the storage adds a lot of overhead. It creates problems for implementing efficient transactions. It  introduces bottlenecks for metadata operations. A filesystem directory with millions of small…
Read more

PigPaxos: Devouring the communication bottlenecks in distributed consensus

-
Image
This is our most recent work, started and led by Aleksey Charapko. (This is a joint post with him.) You can get the paper at arxiv.org. The paper is currently under submission to a journal.

The story One day I challenged Aleksey to give me a ballpark number on how much he thinks we can scale Paxos vertically. While sharding --as in CockroachDB and Spanner-- helps for scaling Paxos deployments horizontally, vertical scaling is about how many nodes you can cram in a single Paxos cluster, with a single conflict domain.

Aleksey, who is not known for being an optimist, said that we can scale Paxos to several hundreds of nodes! He said this may be possible by employing intermediate proxy nodes to relay the communication between the leader and followers, as this would relieve the communication bottleneck at the leader.

I thought "yeah, it is a neat trick, but maybe not that impressive, because it is very simple". Surely others must have tried this, and there must be a catch/drawbac…
Read more

Frugal computing

-
Companies care about cheap computing.

Well, the first thing they care about is usability: Is it easy for average programmers to develop solutions using the framework?

And the second thing they care about is cheap computing: Does this break the bank? Can I do this cheaper?

Speed, efficiency, elegance, technical strength... These are often not of interest. People are OK with their analytic jobs return results hours later. We watched aghast, at the beginning of Hadoop epidemic, people use MapReduce for doing analytics in a wasteful and slow manner.

I was recently thinking about this question: How can we trade-off speed with monetary cost of computing? If the constraints are that the user will not need the results before a couple hours but it would be nice to get the results in a day, what is the cheapest way to get this analytics job done in the cloud?

While distributed systems may be the answer for a lot of questions (such as providing fault-tolerance, low-latency access for geo-distrib…
Read more

Fine-Grained Replicated State Machines for a Cluster Storage System

-
Image
This paper appeared in NSDI 2020 and was authored by Ming Liu and Arvind Krishnamurthy, University of Washington; Harsha V. Madhyastha, University of Michigan; Rishi Bhardwaj, Karan Gupta, Chinmay Kamat, Huapeng Yuan, Aditya Jaltade, Roger Liao, Pavan Konka, and Anoop Jawahar, Nutanix.

The paper presents the design and implementation of a consistent and fault-tolerant metadata index for a scalable block storage system via distributed key-value abstraction. The key idea is to use fine-grained replicated state machines (fRSM), where every key-value pair in the index is treated as a separate RSM to reduce tail-latency in key-value access and provide robustness to key access skews.

Motivation The problem arised from Nutanix's business in building private clouds for enterprises to enable them to instantiate VMs that run legacy applications. A cluster management software determines which node to run each VM on, migrating them as necessary. And Stargate provides a virtual disk abstractio…
Read more

My Distributed Systems Seminar's reading list for Spring 2020

-
Below is the first draft list of papers I plan to discuss in my distributed systems seminar in the Spring semester. If you have some suggestions on some good/recent papers to cover, please let me know.
PaxosCanopus: A Scalable and Massively Parallel Consensus Protocol (CoNext17) Consus taming the PaxiStable and consistent membership at scale with rapid (ATC18)Unifying consensus and atomic commit (VLDB19) Wormspace: A modular foundation for simple, verifiable distributed systems (SOCC19)  ReplicationMergeable replicated data types (OOPSLA19) Exploiting Commutativity For Practical Fast Replication (NSDI19) Amazon Aurora: On Avoiding Distributed Consensus for I/Os, Commits, and Membership Changes (SIGMOD18) Dynamic atomic storage without consensus (JACM 2011) PaxosStore:  High-availability Storage Made Practical in WeChat (VLDB17) Transactions/consistencyInteractive checks for coordination avoidance (VLDB19)SLOG: serializable, low-latency, geo-replicated transactions (VLDB19)  Enabling l…
Read more

Learning about distributed systems: where to start?

-
This is definitely not a "learn distributed systems in 21 days" post. I recommend a principled, from the foundations-up, studying of distributed systems, which will take a good three months in the first pass, and many more months to build competence after that.

If you are practical and coding oriented you may not like my advice much. You may object saying, "Shouldn't I learn distributed systems with coding and hands on? Why can I not get started by deploying a Hadoop cluster, or studying the Raft code." I think that is the wrong way to go about learning distributed systems, because seeing similar code and programming language constructs will make you think this is familiar territory, and will give you a false sense of security. But, nothing can be further from the truth.
Distributed systems need radically different software than centralized systems do.  --A. Tannenbaum This quotation is literally the first sentence in my distributed systems syllabus. Instead of…
Read more

Cross-chain Deals and Adversarial Commerce

-
Image
This paper appeared in VLDB'19 and is authored by Maurice Herlihy, Barbara Liskov, and Liuba Shrira.

How can autonomous, mutually-distrusting parties cooperate safely and effectively?

This question is very important for enabling commerce. The trading world answered this question so far by relying on a trusted third party, and in the worst case, on the government/rule-of-law to litigate parties deviating from their contracts. With prevalence of e-commerce and decentralization, this question is recently  considered in *trustless* settings by modern distributed data management systems.

Solving the trustless multi-party cooperation when all the parties use the same blockchain is achievable via smartcontracts, but solving the problem where the parties use different blockchains bring many additional challenges. Some of these challenges are familiar to us from the classical distributed systems research on distributed transactions, such as how to combine multiple steps into a single atomi…
Read more

Book review. Tiny Habits (2020)

-
Image
I had mentioned about the Tiny Habits technique by BJ Fogg back in 2014. And now Dr. Fogg wrote an entire book on Tiny Habits. He also provides resources for the Tiny Habits technique freely at https://www.tinyhabits.com/resources.

Here you can read more about Dr. Fogg and his career on captology, the study of computers as persuasive technologies, and some controversy about his work on captology. Interesting stuff.

Coming back to the book, to me the book felt longer than needed. Some people may still find this long-form immersive experience useful, but I mostly skimmed through the slow text to get to the visuals and take-aways. Below are some of my highlights from Kindle, and some important visuals from the book.

This is a very useful book. As I wrote earlier, "Instilling useful "habits" is a great trick to conserve energy. When you make something a habit, you don't need to waste your energy for remembering to do it and more importantly for finding the willpower to d…
Read more

Zoom Distributed Systems Reading Group

-
A couple days ago, I tweeted this out, and was surprised how well this was received.
What would be your involvement level?
The later options are inclusive of the earlier ones, so they involve more work. — Murat Demirbas (@muratdemirbas) March 23, 2020 The involvement level distribution looks healthy. One third wants to follow offline, one third likes to attend the discussion session live, and the remaining will get more involved in the reading group by doing their readings and some volunteering to present papers.

We will start the Zoom DistSys Reading Group on Wednesday April 1st (no joke!) at 15:30 EST and meet regularly every week. We announce our meeting links (password protected) at
https://join.slack.com/t/distsysreadinggroup/shared_invite/zt-eb853801-3qEpQ5xMyXpN2YGvUo~Iyg


Following a very brief presentation of the paper, we will start discussing the paper together. After we identify 4-5 interesting questions/directions to dig deeper, we will go into breakout sessions, so that e…
Read more