So, one morning a few weeks or so ago, my colleague, Ruwen Hess,  stuck his head in my door and commented on an Article on Gmail and User Confidence he had just read.  He also pointed out a very interesting Article on the S3 failure from July 20th (which I had seen before).  Now, before I start commenting on the point of this blog post, I want to say that this is NOT meant as a slam on our competitors.   This is a complex and nascent space in which we are all learning.   I want to complement my former company, Amazon, on the openness exhibited in their discussion of the event of July 20th.  It is a new thing for Amazon to explain when stuff happens and I think it is great for the industry and great for Amazon.  Google is just fighting the good fight to provide highly available services.  They are both fascinating companies and worthy competitors.  Still, there are some interesting aspects to this publicly available news.

Of course, this leads my mind down too many different paths.  This was going to be a short post but I always get carried away!  Let me cover:

• Some Observations about Reliable Process Pairs,
• Less Is More,
• N-Version Programming,
• Availability Over Consistency,
• Eventual Consistency,
• Front-Ending the Cloud, and
• It's Going To Be a Fun Ride!

Some Observations about Reliable Process Pairs

Let me start by discussing independence of failures (and the need to focus on it to achieve high availability).  During the 1980s, when I was developing system software at Tandem Computers, some of our important programs were process pairs.  In this scheme, the same software ran in two different processes on different computers within the distributed system connected via messaging.  The goal was that if only one of the computers (and, hence, processes) failed, the other would "take-over" and continue offering service.  Of course, it was essential to be able to restart a backup and fill it up with sufficient state to continue the computation.  Specifically, every failure and take-over created the need to restart the other process (which used to be the primary).  Restarting implies the filling of the new backup with enough state to be ready to take-over.

During this time, I was privileged to be able to see a number of different implementations of process pairs within the Tandem System and, indeed, to do major development and implementation on a large process pair (in addition to a number of other pieces of software with different approaches to fault tolerance).   As I lived and breathed the triage of product support, crashes, dump analyses, patches, and major product upgrades, it became clear to me that there was a pattern.   Some process pairs were implemented to ship entire data structures.  Some were implemented to send very narrow and minimalist descriptions of an operational change in state (e.g. in the transaction manager: "We just advanced transaction-X to the stage of flushing the log records to disk").  In a different example, one process pair would send a message containing its entire address space of data to its partner whenever a change occurred!  Lots of lively debates raged about the best way to implement reliable process pairs.

I observed that the implementations which sent the minimum amount of data seemed to be the most resilient.  There were many crash dump analyses that showed a process running along and it would trash some data structure.  Then, a checkpoint would copy the data structure to the backup process, including its corruption.  (A checkpoint is the message used to communicate state from the primary process to the backup process in a process pair.)    Soon, the corruption caused the primary process (and its computer) to crash.  Now, the backup (with the corruption received from the checkpoint) takes over to do the work of the process pair.  Before long, the backup gets tangled up because of the corruption in the data structure and IT falls over, too!   The entire fault tolerant system has succumbed to a single failure because there is insufficient isolation between the parts.

Less Is More

Communicating less information within a message is usually best.  If you send extra stuff, it can cause corruption!

The failure of Amazon's S3 on July 20th is fascinating and, yet, very typical.   S3 uses a Gossip Protocol to spread state around the network without any master.   The knowledge is simply propagated to anyone that will listen and, very quickly, spreads around the network.   Unfortunately, there was a bit of poison introduced into the system.  Now, it just so happens that this was introduced because Amazon's MD5 hash protection of their messages did not cover some of the system status bits, but that is not my main point.   All (non-protected) data communications will occasionally have transmission errors and, unfortunately, the stuff being gossiped by S3 was not protected.  The article simply describes it as system status state.

I know that in these complex distributed systems,it is essential to keep somewhat accurate track of the state of the system.  What is not clear from the Amazon S3 article from July 20th was the shape and form of the system status information and why it did not settle out automatically after the corruption.   The article mentions that the system status state is given a higher priority and was starving out the real work as it was gossiping about the system state.

The main point is that when you are communicating information, it is essential to keep the information flow as sparse as possible.

While S3 is a brilliant system which is designed to continue functioning during a data center outage, it had a flaw (which I'm sure is now fixed) which allowed for some bad state to propagate to ALL the data centers.  To eliminate the problem, all the data centers were taken offline and then the entire system was restarted.

Let me reiterate my deep respect for the engineering at both Amazon and Google in addition to what I see at Microsoft.  Still, as the industry matures, we will all learn by the school of hard knocks to keep the information we spread across failure units as crisp and concise as semantically possible.

N-Version Programming

I've never personally experienced it but have read about uses of N-Version Programming.   In this scheme, specifications of a program are drawn up and presented to N different teams, each of which will produce a version of the system.  Now, if you develop 3 versions of the system, you may then implement a voting scheme in which when there are two disparate answers, you pick the one with two votes.  The concept is to reduce the probability of a software bug causing the entire system to fail.  Of course, one of the challenges in this approach is the development of comprehensive and clear specifications.

The reason I think of N-Version Programming is that it involves the "Less Is More" principle.  To do N-Version Programming correctly, you need to isolate your development teams and prohibit any out-of-band communication.  If the teams communicate (other than through the specifications), it increases the chances of propagating some corruption.

Availability Over Consistency

I am not aware of any information from Google about the cause of their outage but, again, we as an industry are still learning how to keep ever more complex applications and services available.   The article cited above, expresses the dismay of many users as a service they've grown to depend upon is simply not there for a while.

In many cases, the user would gladly take a "good enough" answer NOW rather than wait for the "correct" answer LATER.  In fact, it is MORE common to see users just want to keep going.  Right now, I am typing most of this on the bus with Windows Live Writer inserting notes to myself about the hyperlinks to fix when I am back online...  It's great to just "keep going" even with a reduced experience!

Amazon published a wonderful paper on  Dynamo at SOSP 2007.  This paper provides an excellent overview of the Dynamo storage system (which I had a role in encouraging from the sidelines -- I can't take credit for it).  Dynamo is in production with at least two running services and numerous fascinating techniques employed in its implementation.  I would encourage you to read the paper.

The reason that I raise this here is that Dynamo provides availability over consistency.  In a distributed system, it has been proven that Brewer's CAP Conjecture is true... Hence, it is now called the CAP Theory.   The idea is that you can have only two of Consistency, Availability, or Partition Tolerance.   You have have a consistent (and by this, the idea is a classic transactional ACID consistency) and partition tolerant system but it may not be available under some partitions.  Alternatively, you can have an available system which tolerates partitions but it won't have the classic notion of consistency.  Increasingly, I see applications designed with looser notions of consistency.  Most of the time, customers really want availability at the expense of classic consistency!  New means of expressing looser consistencies are emerging to provide availability even when failures occur!

I learned over 20 years ago working in transactional systems to ASK a customer what their priority was when dealing with an outage.  Indeed, some customers wanted you to ensure that every transaction was correct before bringing the system online.  At first, it shocked me to learn that many, many customers wanted the system up even if the results of the work might be somewhat "less than perfect".  Indeed, I saw this in some banking systems with humongous amounts of money being pushed around.  It wasn't that they were doing anything wrong... if the system came up, most of the transfers could be accomplished and overnight interest gathered for them.  The funds involved were large enough that hundreds of bank workers would simply stay up all night and verify the accuracy of the work, cleaning up as necessary.  The timeliness mattered more than the accuracy!

Again, more often than not, availability matters more than strict (classic) consistency!

Eventual Consistency

Also fascinating (at least to me) is the area of eventual consistency (and, again, this term implies a LOOSER form of consistency than classic ACID transactions).

The basic idea is that it is OK to diverge opinions across replicas.  What is needed is a system that coalesces when communication is reestablished between the replicas.  I talked about this in my talk The Irresistible Forces Meet the Movable Objects.   I am bringing this up because (I am arguing) that people really want availability over consistency.  When divergent changes are made while disconnected, they also want the messes to clean themselves up as much as possible.

It is my opinion that we will be designing systems to support eventual consistency.  Part of this trend will be to back away from our traditional separation of storage (e.g. database) from applications.  In my opinion, we will evolve towards integrated solutions that combine the storage with the execution of the application in a way that will make it easier to redo the operation by the application and create eventual consistency across different executions of the app.  This is much easier to do than to cope with reorderability of write operations against a data store.

Front-Ending the Cloud

So, I love and believe in cloud computing.  I think the entire space will grow and evolve.  The cost structures for many companies will make it very cost effective to use big data centers for hosting lots of their computation.  As I look at data center cost structures, it is clear that it is going to be a competitive business with many advantages to large data center managers with large economies of scale.  In a handful of years, most companies will look to offsite providers for their reliable servers.

Still, I wonder if there will be a market for local front-end systems running a replica of a portion of the applications needed to keep the business going.   Not all the computation a company performs is "mission critical".  In other words, the company can function with a subset of its computation (at least for a short while).  Will there be an emerging space of loosely-coupled eventually consistent computation run either at the local company or at a different hosting company than the main cloud-purveyor?   If there is an outage of the cloud services, this front-end would keep the business going.  When reconnected, the results of the work would be shared and reconciled.

This is very much like the relationship between Outlook and Exchange.  Outlook does a LOT of its functionality while disconnected and that is of huge value.

This may be an interesting economic point -- combining the cost savings of the cloud with independent failures of the front-end.

It's Going To Be a Fun Ride!

I am SO glad to be working in this space!  It seems to me this is a great time for distributed systems geeks!

- Pat

One last personal post and then I'll get to the work stuff.   Last Friday we got off the ship... Saturday was moving the office with Bob... Sunday we went to a SeaFair party!!!  I've lived in Seattle for 14 years and never really paid any attention to SeaFair but it was a blast!

So, SeaFair is a combination hydrofoil racing and airplane exhibition featuring the Blue Angels.  It turns out that some friends John and Wendy have an amazing house overlooking Lake Washington right above the hydrofoil races.  We were invited to a party, the weather was awesome, and we had a blast!   I have to share some photos and our thanks to John and Wendy for including us!!!

All these photos were taken from their lovely deck!

- Pat

I'm starting this blog entry on the bus riding to work on Monday, Aug 4th... it's taken all the bus rides until today, Thursday, to finish.  There's NO computer stuff in this post... This is a vacation travelogue!

Wow!  We had a good time in spite of Lisa being seasick for 1-1/2 days and the weather in Alaska (mostly) sucking...  Still, it was FUN!

First of all, it was lame of me to think that I was going to exercise every day on the ship... the exercise room was small and had no water or music.   I worked out one day and went to the buffet lines the rest of the time.   I am back in Seattle now and working hard to get rid of the two or three pounds I packed onto my butt...  I weigh within two pounds of what I did three years ago (but more is muscle so I am in 36 inch pants for the first time since the 1960s).  Giving away clothes when you get smaller is an important trick!   When the clothes get tight, STOP EATING SO MUCH...  My clothes are a little too tight after the cruise!

I did, however, succeed at my other goal of reading all 750ish pages of the last Harry Potter book.  JK Rowling is VERY creative and the book held lots of surprises!   I have a lot of respect for her work and enjoyed it immensely.

So, we started off Friday by meeting up with the other two couples, Bob and Rita and Kirk and Kathy, at our condo for brunch and then we caught cabs to the cruise ship dock which is TWO MILES from our home.   It was literally a 10 minute cab ride.   We can see all the cruise ships, including Rhapsody of the Seas coming and going from our living room.   There are two or three cruise ships in Seattle every Friday, Saturday, and Sunday each week from May through September.   Frequently, I am up at 5AM (at least on Fridays) to watch them arrive.  In the evening, at around 5pm, it is normal for them to all pull out within minutes of each other.   Most of them back out of the Port of Seattle and do a 180 degree spin right in front of our home.  I call it the cruise ship ballet!   Here are a couple of photos of the ship we took (Rhapsody of the Seas), taken from our home as it departed the evening after we arrived back in Seattle.

So, Friday (July 25th) was the day to arrive and unpack.  We got on board at around 1PM and started exploring the boat with our friends.   The luggage arrives over a few hours so you need to kill time a bit and then unpack.  So, we discovered the Windjammer Cafe.   This is the place where there are GOBS and GOBS of mediocre food, crowds of people jostling to pack their plates, and then (at some times of day), seriously insufficient tables to sit down and eat.   Now, here and there, you can find something really good in those buffet lines but it is VERY hard to do appropriate portion control because you think you've found the right stuff and the right amount of food but then you walk over to the next stuff and there's something else you want to slap on your plate!  Still, there is always something there and that's kinda' nice when you're locked up on the ship, you can always get something to eat.

Shortly before departure, we had the mandatory lifeboat drill... we all have to practice getting on our life preservers and going to our muster station where we can look at the 150 person lifeboats.   It is a necessary hassle.  Here's my wife, Lisa, looking beautiful in her life preserver!

Here is the view of Seattle as we were departing Seattle.  This photo includes the building with our condo.  It's the shorter one which is darker on the top half in the center of the photo.

Next year, we're moving to a different building only one block from Pike Place Market.  Here's the view of it under construction with the yellow crane in front.  Both of us LOVE downtown living and it was pretty darned cool to only take a 10 minute cab ride to catch an Alaska cruise!

I mentioned the "Cruise Ship Ballet" from Seattle.  Three ships set off at basically the same time that Friday.  Here is a Celebrity ship in from of us and a Holland America ship following behind us!

We went to the opening show and had a great time!  Dinner was fun and we met one of the singers at the next table having dinner with her mother and aunt who were cruising that week.  This set a pattern where we made a big point of sitting in the front row every evening and cheering on the performers... it was a blast!

As we cruised up the Pacific on the outside of the British Columbia and Southeast Alaska islands, the weather got a bit rougher... our stateroom was quite a bit forward and Lisa got seasick.  Consequently, she stayed in the room on the second dinner (which was the first formal dinner).  So, there were only five of us at dinner that night.  Here's Bob and Rita (all dressed up)

and Kirk and Kathy (all dressed up)

and me (in a tux) posing with Kathy since Lisa was upstairs in the stateroom being miserable.  She made it clear to me that I should go to dinner since if I stuck around while she was sick, I would annoy the heck out of her and make her MORE miserable... she was right!

On the third day, we pulled into Juneau and saw that it was in a beautiful location but it was POURING rain... Other than Lisa, none of us brought rain gear.   It turns out to get to town you need to board a bus but the line was outside in the rain.   We waited for a while and then set out to get onto the bus.  Standing (and freezing), we decided to bag it and go back into the ship... That was NICE and WARM.  I found time to read that last Harry Potter book!

Again, we very much enjoyed dinner and the show in the theater on the boat as we were getting underway from Juneau to Skagway.

The next day, we went to Skagway.  It is a cute little tourist town which will get between 5000 and 10,000 tourists every day of the week during the 5 month season.  We spent a couple of hours walking through the shops and exploring.   It was a nice break getting off the ship.

Again, we really enjoyed dinner (casual attire) and the show... it became a lovely rhythm as we met each day to spend the evening in the dining room with friends and head off to the show!

The next day, we got up at 6AM...  The original itinerary had us seeing the glacier in Tracy Arm Fjord.   The Captain announced that we would not be able to get very close (like 2 miles away) from that glacier because there were so many icebergs floating down the fjord that he would need to stay way back for safety...  Instead, he would take us down Endicott Arm Fjord and we would see a different glacier (Dawes Glacier) much closer up.   To make that happen, the visit would need to be much earlier so... we all got up!  Lisa and I met up with our friends in our stateroom to hang on our balcony... I didn't see it but I understand there were hoards of guests (many in their pajamas) on the 10th deck (with no wind protection).   We had a great view from our balcony.   Here are shots of the approach up the fjord and of the glacier as this huge ship did a 180 degree turn only a few thousand feet away.  Our stateroom happened to be on the port side and so it had a magnificent view!

While in front of the glacier, the crew lowered a lifeboat so they could capture some pieces of floating ice.  It just so happened that the boat they used was directly below our balcony!   One of the pieces of ice was later carved to become a salmon and put on display.

We were right behind the bridge and saw LOTS of fun stuff with the glacier...

So, later that day was the second formal dress night.   Lisa loves getting dressed up and (with her help), I think I am doing OK at it!

There was a very cool drum and dance act from Argentina and we had a blast with Bob and Rita at the show.

At the end of the evening, we found a cute folded towel puppy with Lisa's reading glasses on the bed in the stateroom.

The last stop on the cruise was Prince Rupert, British Columbia (necessary so that the ship makes an international stop).   It was a pretty town but there's not much to do there...  Lisa was thrilled to find a sushi restaurant, though!

So, this takes us to our last cruising day home through the inside passage.  It was mostly a quiet and uneventful day (as captured in this photo):

We were taking the inside passage (going South or home to Seattle).  This winds its way between Vancouver Island (which is about 400 miles long) and the mainland.   There are beautiful views and narrow passages between the various islands.  Coming home was the top line in this chart:

At lunchtime on that last day (Thursday), the ship was heading through a narrow passage while we were sitting down and eating.  Now, Bob and I have done quite a bit of boating in our day (especially Bob who is a licensed captain).  We were fascinated (but not worried) when the boat started listing to the starboard by what we thought was about 8 to 10 degrees.  This went on for a minute or two and LOTS of desert plates fell, carts went rolling, and people were quite surprised!  A couple of minutes later, the ship's captain announced that the ship was fine and not to be stressed.

Now, there is quite a difference between a roll (where the boat goes back and forth) and a list (where is stays for a while in one direction).  When the seas get rough, everything gets stowed and you may get a roll (or a pitch) motion which can involve a lot of motion.  When the seas are calm (like in the inside passage), stuff comes out from being stowed and it will fall if there's too much movement.

So, this was an UNUSUAL event!   The cruise ship company doesn't like to have this happen.   Both Bob and I could tell from the motion that we had been moving through a pass with a following current.  The islands and other geography in the inside passage are a special area.  As the tides change, you can have large bodies of water a few feet (or more) higher than what is lying on the other side of the narrow passage.  Consequently, the water squirts through one way (landing onto some calm but lower water) for a few hours and then when the tides change, it squirts through another way.   We could feel this in the motion of the ship.

Now, when a 79,000 ton ship does this, normally everything is lined up, it runs through the shoot and people barely feel a thing.   Both Bob and I (sitting at lunch) notice the slight variation and were chatting about it.  When we listed to the starboard (right), that got our attention as we could feel the rudder had gone over to make a turn to the port (left) and the following current was pushing the ship on the port side causing her to lean (or list) to the starboard side.   This lasted only a minute or two and the ship recovered nicely.

Later that day, Lisa and Rita went to a Q&A with the captain and his senior crew.  He described that he was definitely responsible (and on the bridge) while the pilot (a fellow NOT with the cruise line but who knows the local waters) was at the helm.  As the Rhapsody of the Seas was shooting through the pass with a 5 knot following current (which is a very noticeable but reasonable current to sail through), a couple of fishing vessels cut in front of the Rhapsody of the Seas and the pilot needed to take evasive action to avoid hitting them.  That caused us to make a slightly uncomfortable maneuver.   He claimed we listed 5 degrees (although it seemed like more to Bob and me).  Also, the captain said that was