Posts

The Everything Store: Jeff Bezos and the Age of Amazon (Brad Stone 2013)

-
This book tells the story of Amazon's first 20 years from 1994 to 2014. It is a long book, but I found it very engaging. In comparison, I had not that much enjoyed  the GooglePlex book from Steven Levy (an author I adore).  A caveat though... In 2014, MacKenzie Scott (then Bezos), a writer herself,  had given the book a 1-star Amazon review  due to inaccuracies, crossing the line of nonfiction to fiction in terms of character development, and failing to provide a balanced narrative. Well, as usual, here are some of my highlights from the book.  D. E. Shaw Bezos was in his midtwenties at the time, five foot eight inches tall, already balding and with the pasty, rumpled appearance of a committed workaholic. He had spent five years on Wall Street and impressed seemingly everyone he encountered with his keen intellect and boundless determination. Upon graduating from Princeton in 1986, Bezos worked for a pair of Columbia professors at a company called Fitel that was developing a priva
Post a Comment
Read more

How innovation works and why it flourishes in freedom (2020, by Matt Ridley)

-
This was a very enjoyable read from Matt Ridley. This book takes over from where the Rational Optimist book left , and talks about the how and mechanics of innovation. He has some controversial opinions in some areas (like fracking, vaping, GMOs) where you sense a somewhat single-sided treatment of the subjects, but these do not take away from the overall theme and arguments in the book.  I guess I didn't learn anything I didn't already know about the process of innovation. However, I think the book helped increase my respect for the importance of innovation compared to just invention. I recommend the book. The book is worth a read just for the nice anecdotes about the history of innovation in different fields alone. However, the book could have been shorter and better organized (tidier). Also, the book could have made its case for why innovation flourishes in freedom tighter.  Some of my highlights from the book In Douglas Adams’s The Hitchhiker’s Guide to the Galaxy, Zaphod B
Post a Comment
Read more

High availability in cheap distributed key value storage

-
Image
This paper is authored by Thomas  Kim, Daniel Lin Kit, Gregory Ganger, Michael  Kaminsky, and David Andersen. It appeared in SOCC 2020. The paper talks about using NVMM for building a distributed key value store. NVMMs are a new technology. They are slowly rolling into the datacenters, but there are still questions about their performance and how many writes it could handle before a write wear. NVMMs have very low latency comparable to DRAM, yet they are 10 times cheaper. Awesome, right? Unfortunately they don't have the same high bandwidth as DRAM or SSDs. Also, they are still not anywhere as cheap as SSDs, and it may not be affordable to want to build all NVMM key-value stores.  Before reading this paper, it is important to understand that this is all about money, money, money. The cost of NVMM and SSDs influences the design decisions, and lead to this non-straightforward heterogeneous design. If cost was not an issue, we could even have DRAMs for all replicas in K-V store, eas
Post a Comment
Read more

Consolidating concurrency control and consensus for commits under conflicts

-
Image
This paper is by Shuai Mu, Lamont Nelson, Wyatt Lloyd, and Jinyang Li and it appeared in OSDI 2016. This paper presents Janus, another two-in-one shampoo & conditioner solution. Why deal with providing a solution for replication and another solution layered on top for transaction ordering when you can do both together in less time with a unified solution?  TAPIR had investigated this question first, and Janus does a followup. Instead of using the general transaction model considered in TAPIR, Janus uses one shot transactions, where each transaction contains multiple pieces and each piece has one read/write operation on a single key.  This reduced power transaction model allows Janus to implement an abort-free transaction ordering capability. A novel insight in Janus is that it notices it is possible to consolidate replication ordering and transaction ordering using the same setup. To order the transactions and replication alike, Janus takes a dependency graph tracking approach, l
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 d
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
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 cat
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. Inst
Read more

My Distributed Systems Seminar's reading list for Fall 2020

-
For the Fall semester distributed systems seminar, we will discuss these papers: Bipartisan Paxos: A Family of Fast, Leaderless, Modular State Machine Replication Protocols eXtreme Modelling in Practice     Starling: A Scalable Query Engine on Cloud Function Services Lambada: Interactive Data Analytics on Cold Data using Serverless Cloud Infrastructure   Tiered Replication: A Cost-effective Alternative to Full Cluster Geo-replication   Scalable State-Machine Replication   Designing Distributed Systems Using Approximate Synchrony in Data Center Networks   Armada: Low-Effort Verification of High-Performance Concurrent Programs   Ocean Vista: Gossip-Based Visibility Control for Speedy Geo-Distributed Transactions   Consolidating Concurrency Control and Consensus for Commits under Conflicts    Tales of the Tail: Hardware, OS, and Application-level Sources of Tail Latency   Near-Optimal Latency Versus Cost Tradeoffs in Geo-Distributed Storage   Scaling Symbolic Evaluation for Automated Veri
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 abst
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. Paxos Canopus: A Scalable and Massively Parallel Consensus Protocol  (CoNext17)  Consus taming the Paxi   Stable and consistent membership at scale with rapid  (ATC18) Unifying consensus and atomic commit  (VLDB19)  Wormspace: A modular foundation for simple, verifiable distributed systems  (SOCC19)  Replication Mergeable 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/consistency Interactive checks for coordination avoidance  (VLDB19) SLOG: serializable, low-late
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
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 wil
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 sessio
Read more