Metadata

This paper appeared in CIDR23 and is from Meta (wow, this is the first time I used the new name without needing to mention it is in fact Facebook... wait.. goddammit). The paper talks about how they applied Raft to MySQL replication, and used the flexible quorums in the process. This is not a technically deep paper, but it was interesting to see a practical application of flexible quorums idea to Raft rather than Paxos. The most technically interesting part is the adoption of flexible quorums to Raft rather than Paxos. What is the difference? Flexible quorums idea was developed for Paxos's two phases. But, Raft needs to impose an extra requirement on quorums in order to guarantee Leader Completeness: "the new leader must already have all log entries replicated by a majority of nodes in the previous term." The paper does not call this explicitly. This is what the paper says: "For state machine safety, every data commit quorum needs to intersect with every leader elec...

TAOBench is an opensource benchmarking framework that captures the social graph workload at Meta (who am I kidding, I'll call it Facebook). This paper (which will appear at VLDB'2022) studies the production workloads of Facebook's social graph datastore TAO, and distills them to a small set of representative features.  The integrity of TAOBench's workloads are validated by testing them against their production counterparts. The paper also describes several use cases of TAOBench at Facebook. Finally, the paper uses TAOBench to evaluate five popular distributed database systems (Spanner, CockroachDB, Yugabyte, TiDB, PlanetScale). The paper is a potpourri of many subquests. It feels a bit unfocused, but maybe I shouldn't complain because the paper is full to the brim, and provides three papers for the price of one. TAO TAO is a read-optimized geographically distributed in-memory data store that provides access to Facebook's social graph for diverse products and b...

This paper won the Best Industry Paper Award at VLDB 2021 . I really like the paper. It provides a good amalgamation of database and distributed system techniques! This paper is a followup to several previous paper some of the authors on this team had, including "Scalable atomic visibility with RAMP transactions" , "Highly Available Transactions", and "Coordination avoidance" . If we squint a bit more, we can say that the origins of the theme goes back to the "Probabilistically Bounded Staleness (PBS)" paper by Peter Bailis, et al. Peter found a gold mine with the PBS work. His observation that practical systems already have good freshness/consistency properties powered all of his follow-up work. This is an optimistic/opportunistic message. The theory of distributed systems and databases put most of their effort into the worst case scenario, but things are often not that bad in practice. I like this research-continuity. We should have more of th...

This paper picks up from where the "Virtual Consensus in Delos" paper finishes , and  talks about using Delos to build control plane databases at Facebook. These are my notes from Mahesh's excellent conference presentation. These control plane databases at Facebook were required to support multiple APIs: some SQL, some key-value pairs, and some ZooKeeper namespaces. Each such API typically requires a separate database to be built. But implementing and operating even a single zero dependency control plane system is difficult. To cut this dilemma, they observe that these databases have a similar structure: a consensus protocol at the bottom, and a replicated state machine on top. A lot of that state machine uses generic logic that can be reused across different APIs. This implies that there is an hourglass architecture at work here, where Delos platform is the narrow waist. This paper focuses on protocols which allow us to layer multiple apis on this common Delos platform....

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...

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...