in Personal

Or How I Got An All-Expense-Paid Trip to Portugal and All You Got Was This Silly Blog – Part 1

I got an all-expense-paid vacation to Portugal, in exchange for giving a few talks and chatting with Joao Cachopo’s group about STMs.  His group has the only commercially successful use of an STM that I know about – the Fenix system.  The  Instituto Superior Técnico (biggest engineering faculty of Portugal) runs on it, including all student courses, grading, teachers, scheduling, etc.

Fenix ends up handling about 1000 transactions/minute in daily use, but during course sign-up periods can see 10000 transactions/minute.  A typically daily load is 750,000 read-only transactions (e.g. course queries), 15000 read/write transactions, 600 aborted transactions, and 10 with conflicts.  The typical transaction reads about 10000 transactified variables, but maybe 10 (successful) XTNs a day will read upwards of 1 million variables.

Fenix is basically 3 main parts:

  • a web application, written in Java with transactional & persistent semantics,

– JVSTM, a read-friendly (MVCC) pure-Java STM

  • a data modeling schema, which maps the interesting web data into pure Java objects which are otherwise transactified & persisted.

Or How Getting There is Half the Fun

….ahhh but I get ahead of myself.  The trip itself has been very interesting.  I’m leaving for nearly two weeks (one in Lisbon and one in Toronto at ISMM & PLDI, and so I’m checking a bag – contrary to nearly twenty years of personal flying habit.  Normally I can fit into a small carry-on and missed luggage isn’t an issue… but again I get ahead of myself.

Since I’m leaving bright and early out of SFO I manage to crash at a friends house in SF the night before.  We arrive at the airport plenty early, security is light and I breeze up to the gate… only to discover that the flight is delayed because of storms in Philadelphia. It’s a 1-hour delay and I had a 1.5 hour layover in Philly to make the international connection… 1/2 an hour is still enough time, but definitely getting tight.  I chill in SFO for a few hours.

The flight to Philly is easy, smooth and quiet.  Some clouds floating about when we finally get there but nothing big.  We get our gate info while still in the air, plus the passengers are told that a number of people have tight connections – and would those passengers with relaxed schedules please allow the others to exit first.  Despite all the announcements when we land a number of elderly people jump into the aisles, then wrestle veerrryyy slowly with their luggage… then slowly make their way over to the parking garage area – clearly in no rush.

Meanwhile, me and about 20 other passengers finally exit the plane and have to rush from the end of terminal C to the end of terminal A – it’s a good 1/2mile run – in about 15mins.  I keep telling myself that the flight to Lisbon is an 8 hour overnight flight, and there’s no reason it cannot wait a few minutes and make it up overnight.

As I arrive at the gate in terminal A I can hear the wailing of a woman about missing the plane; sure enough the gate is closed.  I check my watch: I’m no more than 5 minutes late, maybe only 2 or 3 late.  They must have slammed the gate shut literally in this woman’s face.  It’s unbelievable: people are puffing up behind me, the plane is still attached to the jetway – but the gate crew is firmly apologetic.  Rules-is-rules and they cannot open the gate.

In stunned silence I make my way over to the service desk… and I’m maybe person number 50 in line.  Slowly the line grows behind me: it probably peaks at 200 people and snakes down the aisle gate after gate.  The desk crew is overwhelmed; they handle about 1 passenger every 10 minutes…. a little math, 50x10min: I’m going to be here for hours and hours.

A young couple in line next to me strikes up a conversation with me and an elderly man (probably in his 80’s) traveling alone.  The old codger is spritely & opinionated, with a distinguished British accent.  We all take a liking to him immediately.  After a bit the young man takes a brief hike and returns with bagels for our little impromptu group (due to time zones, early rising, and late flights, I’ve not had a meal in about 10 hours and certainly am not getting one on my missed flight).  The couple came through Chicago, also delayed for weather in Philly (and Obama flying through Chicago).  The old fella came through LA; same sad story.  We are all going to Lisbon, we ran and ran and ran and missed the flight by mere minutes.  So we all stood in line and chatted about the stupidity of it all (they couldn’t hold the overnight 8-hr flight plane for a mere 5mins???), and the weather, and airport food, and all the other things perfect strangers can complain about when stuck together.

After about 2 hours, USAir management finally figures out that something is up with this huge line snaking through the airport (which by this late hour is nearly deserted) and bring in reinforcements for the desk crew.  They split us up in groups of 5 to 10 people to head off to other desks.  When my turn finally arrives I get the bad news:

  • I’m re-booked on tommorrow’s flight at the same time, so I’ve got 24 hours (well, about 20 now) to kill in Philly.
  • No food or hotel vouchers.  A “distressed rate” is the best they will do.  I’m just out $75 for the hotel, plus all meals.
  • No way to get my luggage: it’s been screened for international travel and they cannot get it back from the belly of the airport.  So no change of clothing or toiletries or medicines for me.

I turn around and see that the young couple (Trent and Krystal) are in a similar state of shock.  We decide to go the same “distressed rate” hotel together and make a tour of Philly in the morning.  The hotel at least was courteous, the room was pretty nice for $75/night, and I got a courtesy toothbrush (best the hotel could do) for toiletries.  We had spotted a 24-hr diner on the shuttle ride to the hotel, so we decided to meet in the lobby after checkin.  After a quick game of Frogger across a 4 lane divided highway we get to the diner and finally all get the first real meal of the day… at about midnight Philly time.

Next day we set about on a tour of Philadelphia.  The weather is gorgeous and we have a great time.  We see the Liberty Bell, Independence Hall, the first Supreme Court courtroom, Betsy Ross House, and lots and lots of quaint American history.  We tour the last east-coast Liberty Ship (last year my son got a chance to serve on the last west-coast Liberty Ship and totally loved it, so now we can compare notes).  We take pictures (their camera; they’ve promised to send the pictures when they can, so I’m looking  forward to seeing them yet).

After a full day we make our way over to the airport plenty early: no missing THIS flight by mere minutes.  We caught up with the old codger at the gate.  Turns out that in his polite but persistent way he got the airline to pay for his hotel and his food AND upgrade him to first class.  Being elderly, charming and British has its advantages.  We only got upgrades to exit-room seats and at other ends of the plane.  We hug and say goodbye.  I didn’t get a chance to see them in Lisbon.

One final airline travel note: my luggage didn’t make this flight.  It made the original flight on time.  Turns out that after closing the gate they stopped the plane on the tarmac in order to load my luggage.  So they took my bags (and those of about 20 others) – but not me (us).  Way to go US Airways.

My host in Lisbon (called Lisboa by the natives) is Joao Cachopo, and he’s agreed to take me site-seeing on my first day there.  Jet-lag to Europe is always really rough on me, I didn’t sleep on the plane (it was a smooth flight, I just can’t sleep on planes).  So I’m pushing being awake 19-20hrs and it’s just morning in Lisbon.  I need to stay awake until at least 8pm tonight – another 10 hours at least. I start main-lining espresso shots (if you ask for “coffee” here you get espresso).

Joao takes me and his family on a tour around the Portuguese countryside.  It’s a great tour; the western-most point of Europe, full of crazy cliff’s (pun intended) overlooking the sea.  It’s also the weekend local motorcycle gathering point, similar to Hollister is in California – hundreds and hundreds of bikes.  We see old-town Sintra, including this charming castle.  Be sure to scroll down to the part about the secret tunnels under the waterfalls and the “Initiates Well”.  I’d say it was straight out of Hollywood except it predates Hollywood … so it’s more a case of Art Imitating Life.  We eat the local fish (ok, it’s cod – which is not local, but is very very popular in Portugal; they say it’s served in 1000 ways), sample the local sweets, walk the cobblestone streets and generally take in the lifestyle and scenery.

It’s a good thing we just did site-seeing on Sunday.  Joao and his charming wife did their best to engage me in conversation and are generally wonderful to me… but I’m exhausted.  I’m pretty much a total zombie.  I barely make it back to the hotel around 8pm before collapsing in a puddle.


On How I Learned Something New About STMs

10 hours of sleep and a shower later, and I’m much better on Monday morning.

As I mentioned, JVSTM is a read-friendly pure-Java MVCC-style STM.  After recording a version number, read-only transactions can execute entirely without further synchronization.  The version number gives the read-only transaction a snapshot of all of memory; the XTN proceeds “as if” it atomically read everything at the XTN start.  Hence at commit-time a read-only transaction can always commit.

XTNs with writes have it harder of course; they need to atomically verify and commit (atomic with respect to other XTNs with writes).  The easy answer is just to lock write-XTNs against each other.  This works great as long as there are relatively few write-XTNs.

We talk STM shop, and Joao gives me a 70-slide 1-hr presentation he’s whipped up while I slept.  That’s a lot of slides!  Apparently he’s well known for being able to do that…  The presentation is good and we get down to nuts and bolts.  Basically he’s found a really good fit between a large complex workload that’s mostly (but not totally) read-only, and it’s real-world (and to my eye that general style of web app is popular the world over), and in need of a better solution that J2EE.

Joao is using a Data Model.  The data model both describes the entities and their relationships, it also names the shared variables in his concurrent programs (things not named as part of the Data Model do not get transactified) AND is used to describe the database (i.e., persistence).

This cute trick means that in one swoop the program:
– documents it’s data structure (e.g. to the programmers)
– describes it’s data structure to the DB
– names the transactified variables

By exclusion then, stuff not in the Data Model is not transactified. The STM does not deal with it.  Similar to Clojure, this approach names all the shared-variables explicitly (instead of assuming everything is shared by default) and thus reduces the count of shared variables by an order of magnitude (or more).  And _that_ trick means the STM can be much more performant.

Unlike Clojure, this approach is not a new language – it’s a style of naming the shared variables (using a Data Model).  It does not require every variable to be transactified.  Shared mutable state outside the STM is broken (because a STM abort & roll-back will unwind unnamed variables). Programmers can use VBoxes manually, to handle the case of shared mutable state outside any transaction.   I sure some purists do not like this – but I see this whole approach as a powerful and pragmatic solution, and one particularly well-suited to a broad class of modern problems.
This is the first time I’ve heard of an STM being used in a production setting – with success.  The system is clearly alive and well, the STM plays a crucial role in both the performance and ease-of-maintenance in the system.  I’ve talked with a number of people who tried really hard in the past to apply an STM to their particular situation, and for whatever the reason those systems eventually got declared failures.

Given the success of this ‘hammer’ in the Fenix system, Joao’s grad students have been busy trying to find more nails with some success.
speculative execution
a memoizing system
on-the-fly software upgrade system
concurrent lock-free commit algorithm for more write-heavy loads

My more dedicated readers can probably detect a shift in my attitude towards STMs here.  To be fair, this Microsoft blog summarizes my attitude towards STMs for the past three years… and my opinion has mostly not changed.   In short: highly negative, and lacking a killer app.  I think Joao may have found the killer app for STMs.


Joao ends up taking me out to dinner a number of times.  It’s very good to have a local host in a foreign land especially if you don’t speak a word of Portuguese!  The food varies from good to great (grilled seabass w/veggies, and another night some unpronounceable French chicken+figs+ cinnamon thing), and the company is excellent.  We manage a little more site-seeing (St Jorges castle).  I give 2 talks (both old ones, both well received).  My four days fly by but eventually I have to leave.

As of this writing I’m on a (very smooth again!) flight to Philadelphia (again), courtesy of US Airways (again) with a connecting flight to Toronto.  ISMM and PLDI are in Toronto this year and I was on both Program Committees.  Furthermore, Richard Jones has thrown out his back and needs somebody to chair his session.  So I’m duty bound to go in any case.

More later as I survive Toronto – but rest assured that getting there is yet another tale…

Cliff