Virtual Consensus in Delos

This paper has been awarded a best paper award at OSDI20 , and is authored by Mahesh Balakrishnan, Jason Flinn, Chen Shen, Mihir Dharamshi, Ahmed Jafri, Xiao Shi, Santosh Ghosh, Hazem Hassan, Aaryaman Sagar, Rhed Shi, Jingming Liu, Filip Gruszczynski, Xianan Zhang, Huy Hoang, Ahmed Yossef, Francois Richard, and Yee Jiun Song at Facebook, Inc. Delos is the database that stores control plane state for Facebook, building over a shared log system. Each Delos server stores a local copy of a full database, which keeps materialized state of the log, as a Delos table. This DB/ is maintained over the shared log as RSM by just reading commands from the log in sequence and applying them for materializing on the table. Virtual consensus This high level setup is familiar, so let's dive deeper to get to the novelty in this work. Delos uses virtual consensus, which is a fancy way of saying the following. The DB is maintained over a virtual log, which consists of loglets, each of which is implemen

Trial and error

Like many of you I watched The Queen's Gambit and loved it. The settings of scenery and decors in 1960s were mesmerizing.   And like many of you, this rekindled the interest for chess in me. Growing up, I didn't play chess much, but my younger brother got into it as a middle school student. He bought books detailing chess games and studied them. He got a city-wide championship and such. I didn't get much into it, because I guess I didn't think of it as a serious enterprise and didn't want to expend too much energy into it.  I had this Android chess app on my phone, and I started playing with that instead of my downtime Sudoku playing . In this chess app, it is very easy to undo moves, and try other moves. I play against the machine, and yes undoing is cheating, but I use it a lot to explore different scenarios at critical points in the game. I have been very surprised about how much this accelerated my chess learning. I was able to make progress through several har

Facebook: The Inside Story (2020) by Steven Levy

I didn't know much about Facebook's story, so many things in the book was news to me.  Here are my two main take-aways from the book.  There are many inaccuracies in "The Social Network" movie . The founding story is quite different. There had been many challengers claiming they had the "facebook" idea. But social networking was not a new idea. There was even a digital facebook in Exeter at Zuckerberg's boarding high school. Of course there is a luck factor involved, but Zuckerberg should get credit (and blame) for successfully executing this vision at large scale. In this case, the quote is apt: Ideas are worthless, execution is everything. "Never attribute to malice that which is adequately explained by stupidity/incompetence." Facebook has been very reckless and greedy. They botched up things badly, many times, over and over. But they are not inherently evil. The greedy obsession with growth did Facebook in. Zuckerberg has to have everything

Year in Review: Best of Metadata in 2020

What a decade this year has been! Here are some highlights among my 2020 posts. Distributed systems My Distributed Systems Seminar's reading list for Fall 2020  Learning about distributed systems: where to start?  Millions of tiny databases Compositional Programming and Testing of Dynamic Distributed Systems  Ocean Vista: Gossip-Based Visibility Control for Speedy Geo-Distributed Transactions  Zoom Distributed Systems Reading Group  Distributed coordination PigPaxos: Devouring the communication bottlenecks in distributed consensus  WormSpace: A modular foundation for simple, verifiable distributed systems  Hermes: A fast fault-tolerant and linearizable replication protocol  Scalog: Seamless Reconfiguration and Total Order in a Scalable Shared Log State-Machine Replication for Planet-Scale Systems Streamlet: textbook streamlined blockchains  Modeling Streamlet in TLA+ Book reviews Book review. Tiny Habits Vincent Van Gogh, Lust for Life  How innovation works and why it flourishes in

Hybrid clocks crate in Rust

I have been learning Rust in my spare time. It has a very steep learning curve, but in return you get to use an elegant, fast, and safe programming language you can use anywhere from embedded systems to datacenter computing. Rust stole like an artist the best concepts from several languages and combined them under one roof with style. Rust has seen a lot of traction recently, and I think Rust is here to stay for a long time.  In the last couple months, I have been writing small programs to practice Rust, and recently I decided I should go bigger and consider reading a real code base, but something with manageable size. I chose to focus on the hybrid clocks crate because it was the right size, and it solved an important problem.  The hybrid clocks crate showcases many of the best practices of Rust. It has a thoughtful design. It shows practical use of struct and trait implementations and trait objects . It was initially hard for me to wrap my mind around the design, because the design

Compositional Programming and Testing of Dynamic Distributed Systems

This paper is authored by Ankush Desai, Amar Phanishayee, Shaz Qadeer, and Sanjit A. Seshia, and it appeared at OOPSLA 2018. The paper describes the ModP framework extension over the P language . P is a language developed for safe event-driven programming. P models processes as state machines: the state machines communicate via message passing, and events cause state machines to transition between states.  The killer feature of P is unifying modeling with programming! P enables the programmers to write specifications and enables systematic testing both via random testing and exhaustive symbolic execution testing. P is used in event driven systems such as device drivers and robotics . The P GitHub page  states that P is used in Microsoft (P# and Coyote ) and also used extensively at AWS for model-based testing of complex distributed systems.   Compositional testing of distributed systems A problem with systematic testing is that monolithic testing of large systems fail due to combinato

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

Popular posts from this blog

I have seen things

PigPaxos: Devouring the communication bottlenecks in distributed consensus

My Distributed Systems Seminar's reading list for Fall 2020

Learning about distributed systems: where to start?

Fine-Grained Replicated State Machines for a Cluster Storage System

Book review. Tiny Habits (2020)

Zoom Distributed Systems Reading Group

My Distributed Systems Seminar's reading list for Spring 2020

How to run effective paper reading groups

Paxos unpacked