Friday afternoon reading

Various random stuff I'm reading; as usual, presented with little or no comment, except to note it seems like you might find it interesting too.

• Toyota Acceleration Case

  NASA reported not running all the code in simulation due to a lack of tooling. Now, the new panel of experts appears to have actually managed to simulate the system, and found ways to make it crash in the interaction between multiple tasks. The fact that, as EETimes report, a certain task crashing can cause acceleration to continue without control, is pretty indicative of issues arising in integration rather than unit testing.

• The Saddest Moment

  Watching a presentation on Byzantine fault tolerance is similar to watching a foreign film from a depressing nation that used to be controlled by the Soviets—the only difference is that computers and networks are constantly failing instead of young Kapruskin being unable to reunite with the girl he fell in love with while he was working in a coal mine beneath an orphanage that was atop a prison that was inside the abstract concept of World War II.

• Why Does Windows Have Terrible Battery Life?

  The Windows light usage battery life situation has not improved at all since 2009. If anything the disparity between OS X and Windows light usage battery life has gotten worse.

• Comments on the 2013 Gartner Magic Quadrant for Operational Database Management Systems

  There’s generally an excessive focus on Gartner’s perception of vendors’ business skills, and on vendors’ willingness to parrot all the buzzphrases Gartner wants to hear.

• Drilling Network Stacks with packetdrill

  Testing and troubleshooting network protocols and stacks can be painstaking. To ease this process, our team built packetdrill, a tool that lets you write precise scripts to test entire network stacks, from the system call layer down to the NIC hardware. packetdrill scripts use a familiar syntax and run in seconds, making them easy to use during development, debugging, and regression testing, and for learning and investigation.

• Distributed Systems Archaeology: Works Cited

  That's a very nice reading list, even if it is basically from the previous millenium. In particular, I had not seen the new textbook by Varela before.

• I Failed a Twitter Interview

  I am upset that the interviewer didn't ask me the right questions to guide me towards the right train of thought. I don't know why Justin told me "this should work," when my solution in fact didn't . I know that this should have come up in the test cases he asked for, but since I missed the flaw when coming up with the algorithm, I didn't think of testing for it.

• Chuck Moore's Creations; Programming the F18; The Beautiful Simplicity of colorForth

  He is endlessly willing to rethink things from a truly clean slate. It's astonishing how simple things become when you're willing to do that and design something bottom up with that perspective; the "bottom" being raw silicon. He said in his talk that the colorForth compiler is "a dozen or so lines of code." This is shocking to most people. It's because tokenization is done at edit-time and there is almost a one-to-one correspondence between the primitive words in the language and instructions on the chip. The compiler is left with not much to do other than maintain the dictionary and do very straightforward instruction and call/jump packing. This "brutal simplicity" is possible because every aspect has been rethought and carefully orchestrated to work perfectly together.

• Dance Your Ph.D. Finalists Announced!

  This is the 6th year of the contest, which challenges scientists to explain their doctoral research through the medium of interpretive dance. The finalists were selected from 31 dance submissions by the winners from previous years of the contest. The production value has increased considerably from the live Ph.D. dance event that launched the contest in 2007. The goal is to do away with jargon -- indeed, to do away with spoken words altogether -- and use human bodies to convey the essence of scientific research.

Parbuckling, redux

Well, it's not the Costa Concordia, but closer to home we've had our own little parbuckling.

The local newspaper, the Alameda Sun, covers the action, all of which took place just 100 yards from my office: VIDEO: Old tug exhumed from watery grave

Thalhamer said the project may be the largest vessel removal effort to be undertaken on the West Coast since Pearl Harbor, at the start of World War II. The multi-agency team is expecting to remove 40 vessels settled along the length of the estuary, some of them visible to the rowers, sailors and Coasties who frequent the estuary, some of them obscured by water.

Apparently early reports about the tugboat's name and history were nothing more than urban legends, and some serious investigation must now be done to figure out what this wreck was and who abandoned it.

The construction area on the waterfront is amazing now, with a half dozen smaller abandoned boats scattered about, having been pulled from the estuary over the last week by the various cranes.

As the video shows, there are still at least three major vessel recoveries to go:

• The tugboat "Respect"
• Two large barges

The wrecks have to be extracted in the right order, since some are laying on top of others.

Keep up the great work, Cal Recycle!

Scaring away the earthquakes

Somehow I never knew about the story at the time, but I was delighted to read about The Rescue Of The Troll: Bay Bridge's mysterious protector out of hiding

The troll, who has no name, was created and surreptitiously installed in 1989 on a quickly fabricated section of bridge deck that replaced the pieces that collapsed in the Loma Prieta earthquake. He remained out of sight - only bridge workers and boaters could see him on the north side of the span - and cast his magic to protect the bridge and its users. In early September, when the new eastern span opened, the troll was spirited away by ironworkers, who wanted to make sure he was free before demolition of the old span began.

I must have passed under that section of the bridge more than a dozen times over the years, but never saw the troll. Of course, he was small and I was far away and I would have needed a good pair of binoculars to see him.

In some respects, it's best not to see the troll, nor even to know about the troll, as some things are better off that way:

"There's a great deal of mystery surrounding any troll," Goodwin said, "but a special amount of mystery surrounding this troll."

Thank you troll, may you have a safe and happy retirement.

TCP ex Machina

I enjoyed this short paper by Keith Winstein and Hari Balakrishnan of MIT: TCP ex Machina: Computer-Generated Congestion Control .

This paper describes a new approach to end-to-end congestion control on a multi-user network. Rather than manually formulate each endpoint’s reaction to congestion signals, as in traditional protocols, we developed a program called Remy that generates congestion-control algorithms to run at the endpoints.

In this approach, the protocol designer specifies their prior knowledge or assumptions about the network and an objective that the algorithm will try to achieve, e.g., high throughput and low queueing delay. Remy then produces a distributed algorithm—the control rules for the independent endpoints—that tries to achieve this objective.

As long-time readers of my blog know, I consider the TCP Congestion Control algorithm to be one of the "Hilbert Questions" of Computer Science: deep, fundamental, of great practical importance yet still unsolved after decades of work.

Many fine approximate algorithms have been developed over the years, yet we still remain frustratingly far from any clearly "best" algorithm.

The congestion control problem is easy to state:

Each endpoint that has pending data must decide for itself at every instant: send a packet, or don’t send a packet.

If all nodes knew in advance the network topology and capacity, and the schedule of each node’s present and future offered load, such decisions could in principle be made perfectly, to achieve a desired allocation of throughput on shared links.

In practice, however, endpoints receive observations that only hint at this information. These include feedback from receivers con- cerning the timing of packets that arrived and detection of packets that didn’t, and sometimes signals, such as ECN marks, from within the network itself. Nodes then make sending decisions based on this partial information about the network.

In this recent work, the authors have developed an algorithm for generating congestion-control algorithms, to see if a powerful computer, searching many alternatives, can uncover a superior algorithm:

Using a few CPU-weeks of computation, Remy produced several computer-generated congestion-control algorithms, which we then evaluated on a variety of simulated network conditions of varying similarity to the prior assumptions supplied at design-time.

On networks whose parameters mostly obeyed the prior knowledge supplied at design range — such as the dumbbell network with the 15 Mbps link — Remy’s end-to-end algorithms outperformed all of the human-generated congestion-control algorithms, even algorithms that receive help from network infrastructure.

But there is a twist: the new algorithm is superior, but we don't understand how it works:

Although the RemyCCs appear to work well on networks whose parameters fall within or near the limits of what they were prepared for — even beating in-network schemes at their own game and even when the design range spans an order of magnitude variation in network parameters — we do not yet understand clearly why they work, other than the observation that they seem to optimize their intended objective well.

We have attempted to make algorithms ourselves that surpass the generated RemyCCs, without success. That suggests to us that Remy may have accomplished something substantive. But digging through the dozens of rules in a RemyCC and figuring out their purpose and function is a challenging job in reverse-engineering.

RemyCCs designed for broader classes of networks will likely be even more complex, compounding the problem.

I recently whiled away an entire afternoon fiddling with the several dozen knobs on a modern Linux implementation of Congestion Control.

After some false starts, I found a promising path, and was able to speed up one of my benchmarks by a factor of 26, from 3,272 seconds down to 124 seconds.

There is tremendous opportunity for a TCP Congestion Control algorithm that can work well, as the gains in performance and efficiency are immense.

But, for now, what we have are our complex approximations, and even the most powerful computers aren't (yet) able to design a superior algorithm.

At least, not one we can understand.

OpenStack news

The Register takes note of the annual OpenStack Summit and surveys the state of the OpenStack nation: Inside OpenStack: Gifted, troubled project that wants to clobber Amazon

With their typical snark, The Register tell it like it is:

Though many bill OpenStack as "the Linux of the cloud", the technology so far fails to meet the expectations of usability and compatibility that defines the Linux community, though it is improving rapidly.

Ouch! Now, that's faint praise indeed!

On a more technical level, it seems that the largest problems are in the networking arena:

Another issue that is endemic to both within-compute networking (Nova) and the standalone in-development networking module (Neutron), is that for single-host and flat networks, the IP allocation, IP routing, NAT, DHCP, and OpenStack metadata services are in a single chunk of code making them difficult to interface with, while in a multi-host format the services are distributed across hypervisors presenting a much larger attack surface.

At the OpenStack Summit website, it's revealing to browse through the talks, to get a sense for the current priorities of the community.

Many of the component technologies are maturing fast, but it's still early days for OpenStack. The degree of interest in the conference is promising, but it's awfully hard to see this sort of fractured coalition catching up to the giants of the cloud.

Still, this is the way Open Source software works: it's messy, it's chaotic, it can be hard to figure out what's happening, or where it's going. Yet nonetheless the process works, and the software improves.

Team Geek: A Very Short Review

This fall, I zipped right through the new book by Brian Fitzpatrick and Ben Collins-Sussman, Team Geek: A Software Developer's Guide to Working Well with Others.

The authors are well-known engineers, both in the Open Source community (for Subversion), and as Googlers, and certainly have the necessary qualifications to write about software engineering practices.

But Team Geek is not that book.

Team Geek is rather surprising: it is a manual of manners, a book of etiquette.

This is not as far-fetched as it might seem; programmers certainly have a reputation as arrogant, egotistical, prima donnas who can't be bothered to hold a civil conversation. (Of course, if this is really the way you see us programmers, may I suggest you take a bit of time to read Michael Lopp's superb The Nerd Handbook, to help you understand why your favorite programmer is behaving the way he/she does.)

As the authors explain in their "Mission Statement", Team Geek is all about the realization that, in almost every situation, the successful programmer has to work as part of a team:

The goal of this book is to help programmers become more effective and efficient at creating software by improving their ability to understand, communicate with, and collaborate with other people.

And just a few pages later they make the point even more explicitly:

The point we've been hammering is that in the realm of programming, lone craftsmen are extremely rare -- and even when they do exist, they don't perform superhuman achievements in a facuum; their world-changing accomplishment is almost always the result of a spark of inspiration followed by a heroic team effort.

Team Geek is a fine book, easy to read, entertainingly written, with lots of anecdotes and lessons learned from hard experience. As I read it, I said to myself, over and over again: yes, yes, that's exactly how it is, that's indeed how it goes.

If you're a professional programmer, if you're a person who has to work extensively with professional programmers, if you're considering becoming a professional programmer, or if you're just interested in what it's like to be around professional programmers all the time, you will probably find Team Geek to be interesting, practical, and useful.

It won't teach you any new algorithms, or programming languages, and you won't learn anything about Subversion, but you will learn a lot about all the stuff they don't cover in your Computer Science classes in college.

You may not have thought that the world needed a manual of manners for programmers, but it does, and this is a pretty good one.

There are bugs, and then there are bugs

As everyone knows, I adore post mortems; there's so much to learn.

As David Wilson points out on his python sweetness blog, this is one of the greatest bug descriptions of all time, and even though it's contained in an official SEC finding, it's still fascinating to read.

The SEC doesn't bury the lede, they get right to it:

On August 1, 2012, Knight Capital Americas LLC (“Knight”) experienced a significant error in the operation of its automated routing system for equity orders, known as SMARS. While processing 212 small retail orders that Knight had received from its customers, SMARS routed millions of orders into the market over a 45-minute period, and obtained over 4 million executions in 154 stocks for more than 397 million shares. By the time that Knight stopped sending the orders, Knight had assumed a net long position in 80 stocks of approximately $3.5 billion and a net short position in 74 stocks of approximately $3.15 billion.

Yes, I'd call that a significant error.

If you're like me, questions just leap to mind when you read this:

• What was the actual bug, precisely?
• Why was it not caught during testing?
• Why do they not have safeguards at other levels of the software?
• Why do these sorts of bugs not appear more frequently?

Happily, the SEC document does not disappoint.

Let's start by getting a high-level understanding of RLP and SMARS:

To enable its customers’ participation in the Retail Liquidity Program (“RLP”) at the New York Stock Exchange, which was scheduled to commence on August 1, 2012, Knight made a number of changes to its systems and software code related to its order handling processes. These changes included developing and deploying new software code in SMARS. SMARS is an automated, high speed, algorithmic router that sends orders into the market for execution. A core function of SMARS is to receive orders passed from other components of Knight’s trading platform (“parent” orders) and then, as needed based on the available liquidity, send one or more representative (or “child”) orders to external venues for execution.

Well, that helps a little bit, but it doesn't hurt to learn a bit more. The New York Times takes a stab at explaining RLP: Regulators Approve N.Y.S.E. Plan for Its Own ‘Dark Pool’

Regulators have approved a controversial proposal from the New York Stock Exchange that will result in some stock trades being diverted away from the traditional exchange.

The program, expected to begin later this summer, will direct trades from retail investors onto a special platform where trading firms will bid to offer them the best price. The trading will not be visible to the public.

Although the details are obviously quite complex, the overall concept is straightforward: the exchange, with the government's permission, changed the regulations controlling how trades may be executed by the participant trading firms and brokers.

But note the timeframes here: the new rules were approved at the beginning of July, 2012, and went into effect on August 1, 2012. That is one compact period!

Anyway, back to the SEC finding. What, precisely, did the programmers at Knight do wrong?

Well, the first thing is that their codebase contained some old code, still present in the program, but intended to be unused:

Upon deployment, the new RLP code in SMARS was intended to replace unused code in the relevant portion of the order router. This unused code previously had been used for functionality called “Power Peg,” which Knight had discontinued using many years earlier. Despite the lack of use, the Power Peg functionality remained present and callable at the time of the RLP deployment. The new RLP code also repurposed a flag that was formerly used to activate the Power Peg code. Knight intended to delete the Power Peg code so that when this flag was set to “yes,” the new RLP functionality—rather than Power Peg—would be engaged.

This is a common mistake in software: old code is disabled, not deleted. It's scary to delete code, but of course if you have a top-notch Version Control System, you can always get it back. Still, programmers can be superstitious, and I'm not surprised to hear that somebody left the old code in place.

Unfortunately, unused, unexecuted, untested code tends to decay, as the SEC observe:

When Knight used the Power Peg code previously, as child orders were executed, a cumulative quantity function counted the number of shares of the parent order that had been executed. This feature instructed the code to stop routing child orders after the parent order had been filled completely. In 2003, Knight ceased using the Power Peg functionality. In 2005, Knight moved the tracking of cumulative shares function in the Power Peg code to an earlier point in the SMARS code sequence. Knight did not retest the Power Peg code after moving the cumulative quantity function to determine whether Power Peg would still function correctly if called.

So, there was old, buggy code in the program, and new code written to replace it, and that new code "repurposed a flag that was formerly used to activate the Power Peg code." We've got almost all the elements in place, but there is one more significant event that the SEC highlight:

Knight deployed the new RLP code in SMARS in stages by placing it on a limited number of servers in SMARS on successive days. During the deployment of the new code, however, one of Knight’s technicians did not copy the new code to one of the eight SMARS computer servers.

In the modern jargon, this deployment often goes under the terminology of "DevOps". The task of taking your program from its development phase and moving it into production seems like it should be simple, but unfortunately is fraught with peril. Techniques such as Continuous Delivery can help, but these approaches are sophisticated and take time to implement. Many organizations, as Knight apparently did, use old fashioned approaches: "hey Joe, can you copy the updated executable onto each of our production servers?"

The prologue has been written; the stage is set. What will happen next? The SEC finding continues:

The seven servers that received the new code processed these orders correctly. However, orders sent with the repurposed flag to the eighth server triggered the defective Power Peg code still present on that server.

I can barely imagine how challenging this must have been to diagnose under the best of conditions, but in real time, in production, with orders flowing and executives screaming, this must have been extremely hard to figure out. 88% of the work was being done correctly, with just the one computer acting in a rogue fashion.

It's interesting that, in the hours leading up to the go-live moment, there were hints and signals that something was wrong:

an internal system at Knight generated automated e-mail messages (called “BNET rejects”) that referenced SMARS and identified an error described as “Power Peg disabled.” Knight’s system sent 97 of these e-mail messages to a group of Knight personnel before the 9:30 a.m. market open.

But they didn't realize the implication of these special error messages until much later, unfortunately.

You might wonder why other fail-safes didn't kick in and abort the rogue runaway program. This, too, it turns out, was a bug, although in this case it was more of a policy bug than a programming bug.

Knight had an account—designated the 33 Account—that temporarily held multiple types of positions, including positions resulting from executions that Knight received back from the markets that its systems could not match to the unfilled quantity of a parent order. Knight assigned a $2 million gross position limit to the 33 Account, but it did not link this account to any automated controls concerning Knight’s overall financial exposure.

On the morning of August 1, the 33 Account began accumulating an unusually large position resulting from the millions of executions of the child orders that SMARS was sending to the market. Because Knight did not link the 33 Account to pre-set, firm-wide capital thresholds that would prevent the entry of orders, on an automated basis, that exceeded those thresholds, SMARS continued to send millions of child orders to the market despite the fact that the parent orders already had been completely filled.

When something goes wrong during a new deployment, a programmer's first instinct is to doubt the newest code. No matter what the bug is, almost always the first thing you do is look at the change you most recently made, since odds are that is what caused the problem. So this reaction was predictable, even if sadly it was exactly the worst thing to do:

In one of its attempts to address the problem, Knight uninstalled the new RLP code from the seven servers where it had been deployed correctly. This action worsened the problem, causing additional incoming parent orders to activate the Power Peg code that was present on those servers, similar to what had already occurred on the eighth server.

The SEC document contains a long series of suggestions about techniques that might have prevented these problems. To my mind, many of these ring quite stale to the ear:

a written procedure requiring a simple double-check of the deployment of the RLP code could have identified that a server had been missed and averted the events of August 1.

This seems mad to me. The solution to a human mistake by a manual operator who was redundantly deploying new code to 8 production servers is not, Not, NOT to institute a "written procedure requiring a simple double-check." That is a step backwards: humans make mistakes, but the answer is not to add additional humans to the process.

Rather, the solution is that the entire deployment process should be automated, with automated deployment and automated acceptance tests.

Other observations that the SEC make are more germane, in my opinion:

in 2003, Knight elected to leave the Power Peg code on SMARS’s production servers, and, in 2005, accessed this code to use the cumulative quantity functionality in another application without taking measures to safeguard against malfunctions or inadvertent activation.

It is, in general, a Very Good Idea to reuse code. The code you don't have to write contains the fewest bugs. So I can see why the programmers at Knight wanted to keep their existing code in the system, and tried to reuse it.

The flaw, in my view, is that this code wasn't adequately tested. They used existing code, but didn't have automated regression tests and automated acceptance tests to verify that the code was behaving the way they expected.

This is, frankly, hard. Testing is hard. It is hard to write tests, it is even harder to write good tests, and then you have to take the time to run the tests, and you have to review the results of the tests.

In my own development, it's not at all uncommon for the writing of the automated tests to take as long as the development of the original code. In fact, often it takes longer to write the tests than it does to write the code.

Moreover, the tests have to be maintained, just like the code does. And that's slow and expensive, too.

So I can understand why the programmers at Knight succumbed, apparently, to the temptation to skip the tests and deploy the code. Sadly, for them, that was a tragic mistake, and Knight Capital is now part of Getco Group.

Automated trading, like many of the most sophisticated uses of computers today, is not without its risks. This is not easy stuff. The rewards are high, but the risks are high, too. It is useful to try to learn from those mistakes, sad though it may be for those who suffered from them, and so I'm glad that the SEC took the time to share their findings with the world.