Metadata

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

Dave has broad research interests in computer systems in the networked environment. What do you think systems community should be working on but isn't getting enough attention? With the stuttering of Moore's law as we get into nanoscales, there is more need to extract performance from systems through integrated co-design of hardware and software. We need integrated work through the entire stack to make systems faster and more reliable. How do you pick research ideas/projects? I stumble on interesting questions. There is a lot of cross-fertilization going on between different areas I am working on. If everything else fails, once a year or so, I take a notebook, go for a walk, and write down my ideas. My two sabbaticals were also very fruitful for finding research ideas and projects. At Google, I worked with AI/ML people, which opened new horizons for me. What do you think about the future prospects of blockchain systems? Will there be a killer application, like ever? There are v...

 There were several AMAs at SOSP21, where the attendees can ask questions. I really like Jon Howell 's AMA session. I asked two questions I was interested about learning.   Why do you think verification is at a breakaway point now? What are the factors that make this the go-big moment? We are now figuring out how to make common problems cheap. Historically Coq proving was about being clever: do something not done before. Now we are focusing on how do we make the common stuff cheap. The Ironclad project began when Rustan Leino came to our team, and said I have a tool, let's use this tool. The Dafny demos were interesting to me. A red squiggly line showed a bug. When you give hint, the bug went away. It was a lightbulb moment. It took me extra line of code/explanation for me to get it. The verifier already got it. We had verification runouts in slicon valley,  with tlc, tlaps and others. The verifier send back question mark, and we try to decode it, what we realize w...

SOSP, along with OSDI, is the premiere conference in computer systems. SOSP was held biannually; I had attended SOSP19 in person, and shared notes and paper summaries from that.  This year SOSP is virtual, which made it a lot easier to travel to. It is nice attending the conference from the convenience of your home. The experience is not too inferior to physical conference attending if you take the convenience factor into account.  Here are some notes from SOSP21. If you find and interesting paper, you can dig in, because: All SOSP papers are available as open access All the presentations are also available on YouTube Opening The conference opened with announcements from program committee (PC) chairs. SOSP21 had 348 submissions from 2078 authors, resulting on avg 6 authors per paper. 54 out of 348 papers are accepted. Reviews were conducted by 64 PC members, who produced 1500+ reviews. The trend is clear, the number of submissions are growing steeply.  Last year OSDI h...

Distributed/networked systems employ data replication to achieve availability and scalability. Consistency is concerned with the question of what should happen if a client modifies some data items and concurrently another client reads or modifies the same items possibly at a different replica. Linearizability is a strong form of consistency. (That is why it is also called as strong-consistency.) For a system to satisfy linearizability,  each operation must appear (from client perspective) to occur at an instantaneous point between its start time (when the client submits it) and finish time (when the client receives the response), and  execution at these instantaneous points should form a valid sequential execution (i.e., it should be as if operations are executed one at a time ---without concurrency, like they are being executed by a single node)  Let's simplify things further. In practice, consistency is often defined for systems that have two very specific operations: ...

This paper comes from my colleagues at AWS S3 Automated Reasoning Group, detailing their experience applying lightweight formal methods to a new class of storage node developed for S3 storage backend. Lightweight formal methods emphasize automation and usability. In this case, the approach involves three prongs: developing executable reference models as specifications, checking implementation conformance to those models, and building infrastructure to ensure the models remain accurate in the future. ShardStore ShardStore is a new append-only key-value storage node developed for AWS S3 backend. It is over 40K lines of Rust code. Shardstore is a log-structured merge tree (LSM tree) but with shard data stored outside the tree to reduce write amplification. ShardStore employs soft updates for avoiding the cost of redirecting writes through a write-ahead log while still being crash consistent. A soft updates implementation ensures that only writes whose dependencies are persisted are sent...

I had been hearing a lot of negative comments about Fountainhead on Twitter. These comments seemed politically motivated, how the book is a dumb libertarian propaganda. I had to check the book out myself to see what the deal is.  The book started out well. I was surprised to see that, first this is a novel, and second this is an easy read. I was waiting an impenetrable intellectual literary text. The book turned out to readable and initially charming, even though it was written in 1940.  The book felt like "The Goal" novel , communicating a concept/idea in story form. The main guy is this guy, Howard Roark, he is the best architect ever. Rather, he is the God of Architecture. He is architecture in flesh. He is like the best architect ever. The book is not at all subtle about this. He is 1000% dedicated to his craft, and he is the best ever, and he brings out his uncompromised gift in every building he designs. He is uncorruptable and willing to suffer for his art. The first ...

Michael Whittaker , Joe Hellerstein's PhD student at UC Berkeley, has recently defended his PhD thesis on Compartmentalized Paxos . The thesis deconstructs Paxos and shows ways to reconstruct it to be more scalable by individually focusing on each component/role in Paxos. It is a simple but effective trick. Even after you learn the trick, you still keep getting surprised by how effective it is. When I say Michael defended his thesis, I am speaking loosely. Michael was not defensive about anything. He didn't have to be, his work spoke for him. Just watch his PhD presentation and you will understand what I mean.  Michael has a great talent for explaining things simply. Unfortunately this is an underappreciated talent, especially in academia. This may make it look too easy and effortless, and like you didn't do sophisticated work. This dude did not even prepare presentation slides for his PhD thesis (the heresy!), and winged it on the fly by drawing his protocols on an iPad. H...

This is a pun on the saying "there is always room at the top". This is also the title of a famous Feynman lecture from 1959 , where he made a case for nanotechnology.  In this post, I will try to argue that there is plenty of room at the bottom for distributed algorithms. Most work on distributed algorithms are done at a high-level abstraction plane. These high level solutions do not transfer well to the implementation level, and this opens a lot of space to explore at the implementation level. But this is not just an opportunistic argument. It is imperative to target the implementation level with our distributed algorithms work, otherwise they remain as theoretical, unused, inapplicable.  Let me try to demonstrate using consensus protocols as examples. Someone else can make the same case using another subdomain. Be mindful of what is swept under the rug What is succinct at the high level could be very hard to implement and get right at the low level. Paxos seems simple , bu...

Let's start with the impossibility results, a good place to start distributed systems discussion. The coordinated attack result says that if the communication channels can drop messages arbitrarily and undetectably you cannot solve distributed consensus using a deterministic protocol in finite rounds. This result is all about *the curse of asymmetry of information*. Reliable channels are needed for two parties to agree on something. Otherwise the two parties are stuck in a Zeno's paradox of "You may not know that I know that you know that I know" kind of information chaining. A classic paper to checkout on the topic is " Knowledge and common knowledge in a distributed environment ". Assuming mostly reliable channels and demanding majority acks, it is possible to solve consensus in a partially synchronous system. Paxos shows us how to do this. Paxos uses quorum of acks to get around the problem of "the agreement having to occur in one shot" as in ...

This is a favorite saying of mine. I use it to motivate myself when I feel disheartened about how much I have to learn and improve. If I do a little every day or every week, I will get there. If I get one percent better each day for one year, I'll end up thirty-seven times better by the end of the year.   $1.01^{365}=37.78$ Years ago I had read this idea in one of John Ousterhouts life lessons, and it stuck with me.  "A little bit of slope makes up for a lot of y-intercept" Recently I noticed another advantage of progress over perfect. The emotional  advantage. Progress is better because it makes you feel better as you see improvement. You are getting there, you are making ... progress. Progress is growth mindset . You have an opportunity ahead of you. Perfect feels bad.. It puts you on defense. You have to defend the perfect, you have to keep the appearances. You can only go downwards from perfect, or maintain status quo. Progress gives you momentum. As long as you manag...

Programming How did you learn to program? I was lucky that our 5th grade (age 9-10) teacher knew how to use the computers in the school. I learned a little bit of BASIC on a Thomson MO-5. Then I had other hobbies until high school, at which point I joined a semi-formal programming class hosted by a math teacher. That's where I really cut my teeth with Pascal and x86 assembly. Later I got a degree in software engineering. Tell us about the most interesting/significant piece of code you wrote. I would mention two.  One is a critical component in a distributed system: several thousand lines of code, highly concurrent, performance sensitive, high risk (data corruption), lots of tests, months to get it right, years of refinements (optimizations, new use cases). Very valuable. It is far from perfect in several ways, but it worked very well in production for many years across many customers. An invisible part of a complex system. The other is a short script (a couple hundred lines), a mix...

Programming How did you learn to program? In college Tell us about the most interesting/significant piece of code you wrote. contributed to zfs, oracle file systems (writeback, journal, snapshot compaction) Who did you learn most from about computer systems? books, internet, architects Who is the greatest programmer you met, and what is impressive about them? Brian bendelorf (ZFS on Linux) maintainer, Matt Ahrens What is the best code you have seen? zfs, tintri file systems, yugabytedb, linux kernel What do you believe are the most important skills to be successful in your field? understanding the fundamentals, not giving up, digging deep What quality or ability do you value most in a computer systems person? Ability to debug code which others have written, mainly to the point that the RCA (root cause analysis) is correct and not superficial Ability to write clean decent design code at speed Simplicity in the complete process of systems software development Adding meaningful debugging ...

Programming How did you learn to program? I started programming at a relatively young age, around 6th standard (in India). Initially leanred HTML, CSS from w3school and online tutorial blogs/videos, then learned C++, mostly from School curriculum book. In college, I throughly enjoyed reading "Thinking in C++". Tell us about the most interesting/significant piece of code you wrote. I remember the first project I did in school which I'm really proud of, even though it was more of a toy fun project. It was an image editor for BMP files, written in C++.  Who did you learn most from about computer systems? Hacker News, I have been following it since high school. Who is the greatest programmer you met, and what is impressive about them? Interestingly, my own definition of good programmer has changed few times. In college times, I used to admire programmers who had strong algorithmic skills required for ICPC like competitions, but lately I have realised it's equally importan...