Tuesday, June 12, 2007

Using Occam to Simulate p2p Web Services

About a year ago I gave a paper at an IEEE E-Commerce conference that described how I used the latest pi-calculus enhanced version of the old Inmos Transputer language Occam to build a very efficient massively threaded simulator for large scale p2p web services that ran on my laptop.

I blogged this at the time, but The paper itself is subject to the rules IEEE sets out for peer-reviewed conference papers and you need to be a member or pay a fee to get it from http://doi.ieeecomputersociety.org/10.1109/CEC-EEE.2006.81

However, I wanted to share this more widely and have just posted a pdf of the presentation slides for my IEEE paper. Here are the first few slides, and a description of the Tools section:

Simulation of Skype Peer-to-peer Web Services Choreography Using Occam-Pi

Abstract
Complex web services are very difficult to test and verify before deployment on a large scale.
A semantically equivalent in-memory simulation can be built using Occam-pi that runs up to 100,000 nodes about a million times faster than real life.
Rapid protocol development and detailed behavioral analysis using simulation supports the development of robust services that can scale.
The implementation of a simulator that models centralized web services and application to application messaging over the Skype Peer to Peer network is described.

Overview

  • The Landscape
  • The Problem
  • The Tools
  • The Solution
  • Implementation
  • Running the Simulation
  • Conclusion
  • References

The Tools – Pi Calculus

  • WS-BPEL, SSDL and WS-CDL are based on Pi-Calculus
  • Pi-Calculus is based on Communicating Sequential Processes (CSP)
  • Pi-Calculus provides a formal model of parallel message based computing
  • Occam-Pi
  • The Occam language is based on CSP, and has been extended to add the Pi-Calculus extensions to form the Occam-Pi language.
  • The primary implementation of this language is known as KROC, the Kent Re-targetable Occam Compiler
  • KROC is freely available from the University of Kent at Canterbury, UK
  • Runs on Intel architecture Linux, MacOS X, and Microsoft Windows/Cygwin platforms. Older versions exist for SPARC, PPC etc.

The Tools – Occam Language Constructs

  • The constructs that are used in Web Services choreography map directly to Occam language constructs
  • The Occam language has direct support for sequential, parallel and alternate processing blocks, complex protocols, and channel based communications
  • Occam-Pi adds more dynamic constructs to the language
  • Mobile channels - pass a channel end over another channel
  • Mobile processes - suspend a process, pass it over a channel and resume it in a new context
  • Dynamic process forking with barrier synchronization
  • Rigorous Occam-Pi Compile-time Checks
  • Processes or expressions are not allowed to have any “side effects”
  • Syntax and usage of all protocols, data and constructs is checked
  • Occam is designed to allow very comprehensive static analysis

The Tools – Occam Runtime Characteristics

  • There is no need to use XML message encoding or namespaces
  • since the compiler can check that a protocol is being communicated correctly
  • At runtime, the Occam-Pi language is fast small compiled code
  • with its own threading model, in a single process
  • The Occam-Pi runtime detects and reports deadlock
  • including the line number in the code at which each process was stalled
  • Occam-Pi is very efficient
  • All communication takes place in a single address space at memory bus speeds
  • Basic process creation takes 20 nanoseconds on an 800MHz PC
  • Basic channel communications takes 70 nanoseconds
  • Compared to typical web services transactions over the internet these transactions are about a million times faster
  • The language is also very compact, and one hundred thousand to one million threads can be created within a 2 GByte address space.
Works Cited
  • [Cygwin] “GNU + Cygnus + Windows”, http://www.cygwin.com/
  • [GraphML] “Graph Modeling Language “, http://graphml.graphdrawing.org/
  • [Hoare78] C. A. R. Hoare. “Communicating Sequential Processes.” Communications of the ACM 1978.
  • [Hoare85] C. A. R. Hoare. Communicating Sequential Processes. Prentice Hall, 1985.
  • [KROC]. “Kent Retargetable Occam Compiler” http://www.cs.kent.ac.uk/projects/ofa/kroc/
  • [Occam2] Inmos Ltd, Occam 2 Reference Manual. Prentice Hall, 1988.
  • [Milner99] Robin Milner, “Communicating and Mobile Systems: the Pi-Calculus”, Cambridge University Press, 1999.
  • [Skype]. “Skype Developers API” https://developer.skype.com
  • [SSDL] Webber et al. “Asynchronous Messaging between Web Services using SSDL.” IEEE Internet Computing Vol10, No1 2006.
  • [WS-BPEL]. “OASIS Web Services Business Process Execution Language” http://www.oasis-open.org
  • [WS-CDL] “Web Services Choreography Description Language”, http://www.w3.org
  • [yEd] “Graph visualization and editing tool”, http://www.yworks.com/

Friday, June 08, 2007

Aftermath is finally released...

After many years of listening to this song evolve from an initial concept to its final released form, its now time to share it with the world and find out what everyone else thinks of it. Its a moving reaction to the events and aftermath of 911, sounds like nothing else, and has an odd but catchy hook.

Its available on Fractal's site at fractal.bebo.com and via the iJigg widget below.

Saturday, May 19, 2007

Orb Swarm Rolling Robot Video at Maker Faire

Update: this is part of the Orb Swarm project. They intend to build several orbs and take them to events like Burning Man.

Friday, May 18, 2007

Workplace Myths - Career Advice

Some very good career advice on Guy Kawasaki's blog today. The Nine Biggest Workplace Myths, by Penelope Trunk. I've spent a lot of time mentoring people and helping with career development and this is pretty much what I've been telling people for many years.

Its not easy to follow the advice, but it does give a clear vision of what to aim for, and how to know when you get there...

Thursday, May 17, 2007

See you at Techshop at Maker Faire this weekend

I've been using Techshop to make cases for my homebrew phone on their 3D Printer, and I signed up for annual membership since I have a few other projects to work on (e.g. TIG welding some modifications to my Fiat 124 Abarth Rally replica :-)

I'm going to be at Maker Faire in San Mateo this weekend, helping explain the 3D printer to attendees at the Techshop pavillion, and hanging out with Matt on the SVHMPC booth. I'm on duty from 2pm onwards both Saturday and Sunday for Techshop so I should be easy to find and I'd be happy to chat about how to make mobile phone cases or millicomputing or whatever.

Wednesday, May 16, 2007

I'm hiring a senior engineer at Netflix

In my new role, I manage a small group and I have an open headcount for a senior engineer

The full job specification is at http://jobs.netflix.com/DetailFlix.asp?flix1642

Here's what we are looking for:

RESPONSIBILITIES:
  • Designing and developing the Netflix web application and middle-tier architecture focused on personalization software.
  • Full software life-cycle ownership of key strategic business logic from inception through production.
  • Conceiving, articulating and implementing projects in coordination with technical and non-technical coworkers for product enhancement and improvement.


QUALIFICATIONS:

  • Experience with high-traffic, highly scaling, multi-threaded software design.
  • 7+ years of web application development experience. (Java a plus)
  • Experience with Oracle or equivalent database system.
  • Flexibility to shift priorities based on changing needs of the business.
  • A Bachelors or Masters in Computer Science or equivalent engineering.
Characteristics of Success at Netflix:
  • Strong customer orientation, both internally and externally.
  • Strategic thinking both technically and business-wise.
  • Ability to execute successfully on business strategy.
  • Self motivated / self starter.
  • Personal drive to achieve world class software development.
  • Desire to work in a fast-paced, evolving, growing, dynamic environment.
  • Love of technical challenges and the sense of pride it brings to solve them.
  • Ability to work well in a cross functional environment.

Friday, May 04, 2007

Netflix and Silverlight and Joost

Very interesting demo of Microsoft Silverlight as a Netflix application from MIX07.

This seems like a nice, high performance multiplatform way to build web based user interfaces. It should give Flash some competition...

I'm handing back eBay's Dell D600 with Windows XP and getting a MacBook when I start at Netflix, it will be nice to have XP running only when I need it, and when the Silverlight version of Netflix web video ships, it will support Mac.

Joost has also released a new beta build, however I don't have a machine I can run it on during this transition. They don't support my old PowerBook G4 yet....

Monday, April 30, 2007

Jobs at Netflix

A few people have asked me if there are interesting jobs available at Netflix. I haven't started there yet, but they do seem to be looking for senior developers who have a clue about performance.

Here are some job descriptions, let me know if you apply to them...

http://jobs.netflix.com/DetailFlix.asp?flix1449

http://jobs.netflix.com/DetailFlix.asp?flix1576

http://jobs.netflix.com/DetailFlix.asp?flix1440

Friday, April 27, 2007

Leaving eBay to join Netflix

I recently gave notice to eBay and start at Netflix on May 7th. I've had a lot of fun working at eBay Research Labs, but I'm making a strategic move to a smaller company (about a tenth of the number of people as a technology organization) which makes it easier to take a broader role and develop skills and experience in new areas. I will be directing a few senior engineers who develop part of the Netflix web site as my primary role. Its an exciting new challenge!

Tuesday, April 24, 2007

Mobile Phones at Maker Faire

The Silicon Valley Homebrew Mobile Phone Club is going to be featured at Maker Faire this May 19/20th. One of my phone design pictures was used on the site :-)

I've also been continuing to develop the general purpose millicomputing concepts and have been documenting them on my companion blog. I have bought a Gumstix module for use in a phone, and I'm working on benchmarking it at the moment.

Saturday, April 21, 2007

Load Average Differences Between Solaris and Linux

A lot of people monitor their servers using load average as the primary metric. Tools such as Ganglia colorize all the nodes in a cluster view using load average. However there are a few things that aren't well understood about the calculation and how it varies between Solaris and Linux.

For a detailed explanation of the algorithm behind the metric, Neil Gunther has posted a series of articles that show how Load Average is a time-decayed metric that reports the number of active processes on the system with a one, five and fifteen minute decay period.

The source of the number of active processes can be seen in vmstat as the first few columns, and this is where Solaris and Linux differ. For example, some Linux vmstat from a busy file server is shown below.
procs -----------memory---------- ---swap-- -----io---- --system-- ----cpu----
 r  b   swpd   free   buff  cache   si   so    bi    bo   in    cs us sy id wa
 4 43      0  32384 2993312 3157696  0    0  6662  3579 11345 7445  7 65  0 27


The first two columns show the number of processes that are in the run queue waiting for CPU time and in the blocked queue waiting for disk I/O to complete. These metrics are calculated in a similar manner in both Linux and Solaris, but the difference is that the load average calculation is fed by just the "r" column for Solaris, and by the "r" plus the "b" column for Linux. This means that a Linux based file server that has many disks could be running quite happily from a CPU perspective but show a large load average.

The logic behind the load average metric is that it should be a kind of proxy for responsiveness on a system. To get a more scalable measure of responsiveness, it is common to divide the load average by the number of CPUs in the system, since more CPUs will take jobs off the run queue faster. For disk intensive workloads on Linux, it may also make sense to divide the load average by the number of active disks, but this is an awkward calculation to make.

It would be best to take r/CPU count and b/active disk count then average this combination with a time decay and give it a new name, maybe the "slowed average" would be good?

Monday, April 16, 2007

SEtoolkit and XEtoolkit releases

The SEtoolkit was developed in 1993 by Rich Pettit, and I used it as a way to prototype many new tools and ideas over the years. Its a Solaris specific performance tool scripting language that supports very rapid development of new tools. The SEtoolkit has been widely deployed as the Solaris collector for the popular system performance monitor Orca. Rich gave up development of the SEtoolkit a few years ago, put the code into open source under GPL, and its now available via sourceforge, where it is being maintained by Dagobert Michelsen. A bug in the SEtoolkit was causing it to crash when used with complex disk subsystems, and this has now been fixed in the SE3.4.1 release (April 10th, 2007).

Meanwhile, Rich has been trying to make a multi-platform (Solaris, Windows, Linux, FreeBSD, OSX, HP-UX, AIX) version of SE for a long time, and finally gave up trying to implement his own language, and based his latest development, the XEtoolkit, on Java 5. The first full release XEtoolkit 1.0 came out on April 15th, 2007. The code is released and supported under both open source and commercial licenses, by Rich's new company - Captive Metrics. The GPL license allows full free use of the provided tools, and development of new and derived tools that are also contributed to the community. The commercial license allows custom XEtoolkit development for proprietary tools, with a higher level of support.

The XEtoolkit 1.0 release doesn't support HP-UX or AIX, but AIX support is coming soon. I encourage you to try it out, give Rich some feedback and make it worth his while to continue. He's one of the very best programmers and performance tool architects I've ever met....

Thursday, April 12, 2007

myPhone 2.0 Case comes off the 3D printer



More pictures of the latest myPhone 2.0 case design.

This version has a deeper case, and was printed at a simple angle, the previous attempt ended up warping, so I hope these changes will keep it flat. It also has a slot in the bottom end to take an iPod connector, which carries power, USB, stereo line level output etc. an antenna mounting hole at the top, and a retaining clip design to hold the LCD in place.

This contains 2.6 cubic inches of ABS plastic, and used 1.4 cubic inches of support material, which costs about $40 in materials and took 8 hours to print at Techshop.

Wednesday, March 28, 2007

Low Power Microprocessors for General Purpose Computing

While researching devices for my home brew mobile phone, I've realized that the current generation of CPUs for mobile devices are actually seriously powerful, very low cost and use almost no power. The performance per watt and per dollar seems to be an order of magnitude better than the PC-class CPUs that are common in commodity servers nowadays. The absolute performance and memory capacity is lower, but is comparable to common PC hardware from a few years ago, and could be useful for more than running a high end phone or portable games machine. Devices such as the Marvel PXA270 and Freescale i.MX31 run at over 500MHz, some include floating point units, they support at least 128MB of RAM (a single chip), and a myriad of I/O interfaces, with Linux 2.6 support.

While the current mainstream CPUs were driven by the development of the home PC market, this generation is driven by the development of the mobile, battery powered device market, which is a very large. For example the worldwide cellphone market is something like a billion devices a year.

I think that there could be some interesting general purpose computer systems built from low power devices (CPUs that use less than one watt). I looked around but wasn't sure what to search for... I do know about the systems that are sold for embedded use, but they are typically configured using lower speed and lower memory options.

Does anyone know of vendors selling general purpose systems, or a category name for this space?

[Update: I asked around, and thought a while, and decided that this is interesting enough to have its own name "millicomputer" and its own blog "millicomputing"].

Thursday, March 01, 2007

The OpenMoko Story

Here is a link to the OpenMoko slide set presented at ETel. Worth a read, there is a lot of activity building around this platform at the OpenMoko community site.

Picture of myPhone

Here are the CAD pictures of the phone, I made the rear case cover translucent so that some of the parts inside can be seen. The big dark block is a Treo650 battery, the block in front of it is the Telit 862 GSM/GPS module that does all the phone stuff... Its 130mm long and 75mm wide, quite big, but thats a 3.7" 480x640 LCD, and its easier to fit off the shelf parts inside :-)



MyPhone Making Progress and ETel Conference

I'm at the O'Reilly ETel conference this week, lots of new and interesting things happening. I've met the OpenMoko people and held the phone (nice hardware, quite compact).

Several people from the SVHMPC are also attending, we have been showing off the cases I made a few weeks ago, and I've been spending way too long on a new and much cooler case design. I've posted my design including all the cad files (this is a completely open source project, including hardware designs) to a page on the Homebrew Mobile Wiki.

Thats the main reason there have been relatively few postings in the last week...

Joost sends out a batch of beta invites

I only got two, they are both already take and I don't have any spare, but several people are selling Joost invites on eBay for a few bucks...

Friday, February 16, 2007

Skype downloads approach 500 Million

In the next few days, Skype will pass the 500 million downloads mark. I seem to remember someone saying that Kazaa was the most downloaded program ever, and looking at the Kazaa home page, they currently show 389 Million. Skype is at 498 Million as I write this, and is downloading at almost a million a day. The download rate was over 1M a day when they made a new release available and existing users were getting updates. Compared to Kazaa, Skype is downloading every day, what Kazaa is downloading every week.

How are the competition doing? Vonage added a few hundred thousand users last quarter. Thats a few orders of magnitude away from being a competitor!

Of course, Kazaa is based on an earlier version of the P2P technology that powers Skype, and which is about to come to the world again via Joost. Joost just released a new beta for Windows, and their first beta for Intel based OSX. I still can't justify upgrading from my own Powerbook G4 (it just works) so I'll have to wait for them to backport to the older systems, and use my work laptop.

Monday, February 12, 2007

AMD Enhanced Power Now - Variable Cores and Clock Rates

There is an interesting article in The Register about the latest variant of AMD's enterprise power management system.

As I've mentioned before, in the interests of saving power, some enterprise server systems are varying their clock rates so that they end up showing a higher utilization at low load levels that you would expect. This non-linear relationship of load to utilization is one of the things I highlighted in my CMG06 paper called "Utilization is virtually useless as a metric".

The latest twist: in AMD's upcoming four core systems, individual cores will be stopped completely if there isn't enough work for them to do.

The effect on utilization metrics will depend upon how each operating system interacts with the power management capabilities...

For Solaris the so-called "idle loop" is actually quite busy. An idle CPU watches its neighbors to see if they have too many jobs on their run queues, and gets work by migrating processes that won't get to run soon to itself. Interrupts are also bound to individual CPUs, so that data structures don't have to migrate between caches at high interrupt rates.

It will be interesting to see how these technologies interact.

Adrian