Crash-only software, HOTOS'03

-
Here is the summary for the second paper we covered in the first class of our seminar. The paper has a provocative title, and in fact there is a wikipedia entry on this title: "Crash-only software refers to computer programs that handle failures by simply restarting, without attempting any sophisticated recovery. Correctly written components of crash-only software can microreboot to a known-good state without the help of a user. Since failure-handling and normal startup use the same methods, this can increase the chance that bugs in failure-handling code will be noticed..." (We had previously seen this observation in the last section of Ousterhout's "The role of distributed state" paper.)

Motivation
Since crashes are unavoidable, software must be at least as well prepared for a crash as it is for a clean shutdown. But then --in the spirit of Occam's Razor-- if software is crash-safe, why support additional, non-crash mechanisms for shutting down? A frequent reason is the desire for higher performance. For example, to avoid slow synchronous disk writes, many UNIX file systems cache metadata updates in memory. As a result, when a UNIX workstation crashes, the file system reaches an inconsistent state that takes a lengthy fsck to repair, an inconvenience that could have been avoided by shutting down cleanly. This captures the design tradeoff that improves steady state performance at the expense of shutdown and recovery performance. But, if the cost of such performance enhancements is dependability, perhaps it's time to reevaluate our design strategy.

The major benefit of a crash-only design is the following: A crash-only system makes it affordable to transform every detected failure into component-level crashes; this leads to a simple fault model, and components only need to know how to recover from one type of failure. If we state invariants about the system's failure behavior and make such behavior predictable, we are effectively coercing reality into a small universe governed by well-understood laws. If we don't use a crash-only system and allow any fault and recovery behavior, the resulting set of states becomes very big and complex due to many possible states.

Requirements of Crash-Only Software
To make components crash-only, the crash-only approach requires that all important non-volatile state be kept in dedicated crash-only state stores, leaving applications with just program logic. Specialized state stores (e.g., databases, file system appliances, distributed data structures, non-transactional hashtables, session state stores, etc.) are much better suited to manage state than code written by developers with minimal training in systems programming. Applications become stateless clients of the state stores, which allows them to have simpler and faster recovery routines. (This requirement will hurt the system performance unavoidably.)

To make a system of interconnected components crash-only, it must be designed so that components can tolerate the crashes and temporary unavailability of their peers. Thus, the approach prescribes strong modularity with relatively impermeable component boundaries, timeout-based communication and lease-based resource allocation, and self-describing requests that carry a time-to-live and information on whether they are idempotent. Many Internet systems today have some subset of these properties as they are built from many heterogenous components, accessed over standard request-reply protocols such as HTTP, and serve workloads that consist of large numbers of relatively short tasks that frame state updates.

What can go wrong here?
The paper mentions the following potential problem: The dynamics of loosely coupled systems can sometimes be surprising. For example, resubmitting requests to a component that is recovering can overload it and make it fail again; so the RetryAfter exceptions provide an estimated time-to-recover. To prevent reboot cycles and other unstable conditions during recovery, it is possible to quiesce the system when a set of components is being crash-rebooted. This can be done at the communication/RPC layer, or for the system as a whole. In our prototype, we use a stall proxy in front of the web tier to keep new requests from entering the system during the recovery process.

Taking things further, I can think of more scary scenarios. A component restart may take some time and, hence, may trigger restarts or problems at other components that depend on this component. As a result one restart may trigger a system-wide restart storm. The silver-lining in this cloud is that, hopefully, by designing thr system to be crash-only, you will test for and notice these problems before deployment as these cases will be exercised often.

Another complaint is that the crash-only approach puts some burden on the developers. It requires the components are designed to be very loosely coupled. It requires the developer to write code to keep track of lost requests, and retry the lost requests if they are idempotent, else either perform a rollback recovery or apply a compensating operation for it or somehow tolerate the inconsistency. While these code are for the component-level recovery (and thankfully not system-wide recovery), the code may still grow too complex for the developer to handle. Again, this may be unavoidable, fault-tolerance comes with a cost.

My another concern about the crash-only approach is a continuous cyclic corruption of components (this case is different than "the recorruption of a component during recovery" mentioned two paragraphs above). In this scenario, faults in component A leak and corrupts component B, and after A restarts and corrects itself, this time faults leak from component B to re-contaminate/corrupt A. Rinse repeat the above loop, and we have a vicious cycle of on-going corruption/contamination. My advisor Anish Arora had a solution to this problem for composition of self-stabilizing components. The solution used dependency graphs on the corruption and correction relations among components and accordingly prescribed some blocking wrappers to freeze contamination and break cycles. I found that the authors of the crash-only approach has a simpler solution to this, which they provide in their recursive-restartability paper. Their idea is to first attempt recovery of a small subset of components (say only one component), and if restart proves ineffective, the subsequent attempts recover progressively larger subsets. In other words this technique chases fault through successive boundaries, and can thus break the corruption cycle. It is not very efficient but it is simple and it works eventually.

The paper is realistic about the limitations of the crash-only approach, and does not paint an all rosy picture. Here are some quotes from the paper on this:
  • Building crash-only systems is not easy; the key to widespread adoption of our approach will require employing the right architectural models and having the right tools.
  • We are focusing initially on applications whose workloads can be characterized as relatively short-running tasks that frame state updates. Substantially all Internet services fit this description, in part because the nature of HTTP has forced designers into this mold. We expect there are many applications outside this domain that could not easily be cast this way, and for which deriving a crash-only design would be impractical or infeasible.
  • We expect throughput to suffer in crash-only systems, but this concern is secondary to the high availability and predictability we expect in exchange.
Comparison to self-stabilization
I think the crash-only approach is a special (more blackbox and more scalable) instance of self-stabilizing system design.

The crash-only approach uses the component crash abstraction to abstract away different fault-types and different arrival sequence of these faults. Similarly, the self-stabilization approach uses the arbitrary state corruption abstraction to avoid the need to characterize the effects of different types of faults. Of course the difference between the stabilization approach and crash-only approach is that stabilization requires access to the code and requires figuring out the good states of the system to converge to. In other words, stabilization is a chisel and crash-only is a large hammer. But, for scalability of adding fault-tolerance to large systems, you may be better off using a hammer than a chisel.

State-store approach and keeping application logic stateless also connects back to the self-stabilization approach. Building a stateless system is a trivial way to make a system self-stabilizing. If you don't have any state to corrupt, the system is trivially self-stabilizing. (Similarly, if the system is built to be soft-state, then the corrupted state expires with time and new/correct information is written in the new state, so the system is again easily shown to be self-stabilizing.)

Final remarks
The paper includes the following sentence in the conclusions section, which I think is a very good summary/evaluation of the approach: "Writing crash-only components may be harder, but their simple failure behavior can make the assembly of such components into large systems easier."

Yes, crash-only approach provides some compositionality of fault-tolerance because it uses restarts to transform arbitrary faults into crashes and each crash-only component is written anticipating that it will interact with other crash-only components so it can tolerate crashes of other components. However, things are not always easy in practice and there are caveats as we mentioned above. Some faults can leak through the crash-only abstraction and contaminate other components. Also there could be hidden/emergent interactions/couplings between components that the developer needs to tune.

Comments

Anonymous said…
This comment has been removed by a blog administrator.
January 10, 2012 at 12:47 AM
Post a Comment

Popular posts from this blog

Hints for Distributed Systems Design

-
This is with apologies to Butler Lampson, who published the " Hints for computer system design " paper 40 years ago in SOSP'83. I don't claim to match that work of course. I just thought I could draft this post to organize my thinking about designing distributed systems and get feedback from others. I start with the same  disclaimer Lampson gave. These hints are not novel, not foolproof recipes, not laws of design, not precisely formulated, and not always appropriate. They are just hints.  They are context dependent, and some of them may be controversial. That being said, I have seen these hints successfully applied in distributed systems design throughout my 25 years in the field, starting from the theory of distributed systems (98-01), immersing into the practice of wireless sensor networks (01-11), and working on cloud computing systems both in the academia and industry ever since. These heuristic principles have been applied knowingly or unknowingly and has proven
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 >>

Making database systems usable

-
Image
C. J. Date's Sigmod 1983 keynote, "Database Usability", was prescient. Usability is the most important thing to the customers. They care less about impressive benchmarks or clever algorithms, and more about whether they can operate and use a database efficiently to query, update, analyze, and persist their data with minimal headache. (BTW, does anyone have a link to the contents of this Sigmod'83 talk? There is no transcript around, except for this short abstract .) The paper we cover today is from Sigmod 2007. It takes on the database usability problem raised in that 1983 keynote head-on, and calls out that the king is still naked.  Let's give some context for the year 2007. Yes, XML format was still popular then. The use-case in the paper is XQuery. The paper does not contain any  reference to json. MongoDB would be released in 2009 with the document model; and that seems to be great timing for some of the usability pains mentioned in the paper! Web 2.0 was in
Read more >>

Looming Liability Machines (LLMs)

-
As part of our zoom reading group ( wow, 4.5 years old now ), we discussed a paper that uses LLMs for automatic root cause analysis (RCA) for cloud incidents. This was a pretty straightforward application of LLMs. The proposed system employs an LLM to match incoming incidents to incident handlers based on their alert types, predicts the incident's root cause category, and provides an explanatory narrative. The only customization is through prompt-engineering. Since this is a custom domain, I think a more principled and custom-designed  machine learning system would be more appropriate rather than adopting LLMs. Anyways, the use of LLMs for RCAs spooked me vicerally. I couldn't find the exact words during the paper discussion, but I can articulate this better now. Let me explain. RCA is serious business Root cause analysis (RCA) is the process of identifying the underlying causes of a problem/incident, rather than just addressing its symptoms. One RCA heuristic is asking 5 Why&#
Read more >>

Foundational distributed systems papers

-
I talked about the importance of reading foundational papers last week. To followup, here is my compilation of foundational papers in the distributed systems area. (I focused on the core distributed systems area, and did not cover networking, security, distributed ledgers, verification work etc. I even left out distributed transactions, I hope to cover them at a later date.)  I classified the papers by subject, and listed them in chronological order. I also listed expository papers and blog posts at the end of each section. Time and State in Distributed Systems Time, Clocks, and the Ordering of Events in a Distributed System. Leslie Lamport, Commn. of the ACM,  1978. Distributed Snapshots: Determining Global States of a Distributed System. K. Mani Chandy Leslie Lamport, ACM Transactions on Computer Systems, 1985. Virtual Time and Global States of Distributed Systems.  Mattern, F. 1988. Practical uses of synchronized clocks in distributed systems. B. Liskov, 1991. Expository papers
Read more >>

Advice to the young

-
Image
I notice I haven't written any advice posts recently. Here is a collection of my advice posts pre 2020. I've been feeling all this elderly wisdom pent up in me, ready to pour at any moment. So here it goes. Get ready to quench your thirst from my fount of wisdom. No man, think for yourself, only get what works for you. It is called foundations, not theory Foundations of computer science (or rather any field of study) are the most important topics you can learn. These lay down the frame of thinking/perspective for that area of study. Yet, I am saddened to hear these called as "theory", and labeled as "unpractical". This couldn't be farther from the truth. Take a look at how I recommend studying distributed systems . Don't you dare call this "theory" and "unpractical". This lays the bedrock that you build your practice on. Don't skimp on the foundations. Don't build your home on quicksand. Keep your hands dirty, your mind cl
Read more >>

Linearizability: A Correctness Condition for Concurrent Objects

-
Image
This paper is from Herlihy and Wing appeared in ACM Transactions on Programming Languages and Systems 1990. This is the canonical reference for the linearizability definition. I had not read this paper in detail before, so I thought it would be good to go to the source to see if there are additional delightful surprises in the original text. Hence, this post. I will dive into a technical analysis of the paper first, and then discuss some of my takes toward the end. I had written an accessible explanation of linearizability earlier; you may want to read that first. I will assume an understanding of linearizability to keep this review at reasonable length. Introduction I love how the old papers just barge in with the model, without bothered by pleasantries such as motivation of the problem. These are the first two sentences of the introduction. "A concurrent system consists of a collection of sequential processes that communicate through shared typed objects . This model encompass
Read more >>

Scalable OLTP in the Cloud: What’s the BIG DEAL?

-
Image
This paper is from Pat Helland, the apostate philosopher of database systems, overall a superb person, and a good friend of mine. The paper appeared this week at CIDR'24. (Check out the program for other interesting papers). The motivating question behind this work is: " What are the asymptotic limits to scale for cloud OLTP (OnLine Transaction Processing) systems? " Pat says that the CIDR 2023 paper "Is Scalable OLTP in the Cloud a Solved Problem?" prompted this question.  The answer to the question? Pat says that the answer lies in the joint responsibility of database and the application. If you know of Pat's work, which I have summarized several in this blog , you would know that Pat has been advocating along these lines before. But this paper provides a very crisp, specific, concrete answer. Read on for my summary of the paper. Disclaimer: This is a wisdom and technical information/detail packed 13-page paper, so I will try my best to summarize the sa
Read more >>

Understanding the Performance Implications of Storage-Disaggregated Databases

-
Image
Storage-compute disaggregation in databases has emerged as a pivotal architecture in cloud environments, as evidenced by Amazon ( Aurora ), Microsoft ( Socrates ), Google (AlloyDB), Alibaba ( PolarDB ), and Huawei (Taurus). This approach decouples compute from storage, allowing for independent and elastic scaling of compute and storage resources. It provides fault-tolerance at the storage level. You can then share the storage for other services, such as adding read-only replicas for the databases. You can even use the storage level for easier sharding of your database. Finally, you can also use this for exporting a changelog asynchronously to feed into peripheral cloud services, such as analytics. Disaggregated architecture was the topic of Sigmod 23 panel . I think this quote summarizes the industry's thinking on the topic. "Disaggregated architecture is here, and is not going anywhere. In a disaggregated architecture, storage is fungible, and computing scales independently.
Read more >>

Designing Data Intensive Applications (DDIA) Book

-
Image
We started reading this book as part of Alex Petrov's book club . We just got started, so you can join us, by joining the discord channel above. We meet Wednesday's 11am Eastern Time.  Previously we had read transaction processing book by Grey and Reuters. This page links to my summaries of that book. Chp 1. Reliable, Scalable, and Maintainable Applications I love the diagrams opening each chapter. Beautiful! The first chapter consists of warm up stuff. It talks about the definitions of reliabilty, scalability, and maintainability. It is still engaging, because  it is written with an educator and technical blogger voice, rather than a dry academic voice. This book came out on 2017. Martin is working on the new version. So if you have comments for things to focus on for the new version, it would be helpful to collect them in a document and email it to Martin. For example, I am curious about how the below paragraph from the Preface will get revised with 8 more years of hindsight:
Read more >>