Notelets

I've been looking with interest at Amazon's Web Service stuff, particularly S3, for several years though never really saw it as being a realistic part of the Investment Banking scene. However, I wonder if that's going to change with great deal of interest in SOA and now Web 2.0 from the marketeers which is feeding into IT strategy. Here's an idea I bandied around with Ian Grigg of Systemics, a leading light in the financial cryptography community and author of the seminal paper Financial Cryptography in 7 Layers.

Seems to me that the ideas and the technology have been around for a while - it's the time it takes to change the strategy juggernaut that's the issue...

A conversation with Ian Grigg of Systemics from 27th November 2003

I have an idea called Notelets - an arbitrary lightweight data storage mechanism with good
security and highly redundant. Access is via key or x509 cert. Notelets can be "chained" - linked together and "nested" - heirarchical, distributed - stored on at least n nodes (where n > 1.)

This is a bit like freenet project (freenet.sourceforge.net - forget the "freedom" rhetoric - this is the incentive mechanism) - a cryptographic file storage system which is highly redundant and highly distributed. However, there's no element of revenue in the model - and therefore no incentive to run a freenet node. Notelets is different in that the revenue model is a key part system - allowing those who host the service to earn a revenue and build a reputation.

The idea is to "give away" the software to whoever would host data storage - instant and pervasive infrastructure. One of the principal usages would be that of a semaphore between one-to-one or one-to-many parties.

The service could facilitate high levels of security (I won't bore you with the details - but a good analogy is the "tradecraft" symbols used to coordinate drop points as detailed in the Mitrokhin Archive)

A p2p management layer would handle server reputation, notelet distribution and would be geolegislatively sensitive.

[GB] Here's an idea. What about a "notes" service (a la post it notes.)

- user/application issues request for access
- cert issued via email/soap call
- cert presented when service accessed.


[IG] Hmmm.... OK. We are talking website - browser access with client cert here, right? That infrastructure exists which is a big plus. It has had mixed reports, which is a minus. I suppose we'd have to test it to see if the promise is kept.

[GB] - User can create up to 20 blobs of info/text/binary - up to 20KB each - blobs can be linked together - chained, deleted, modified, searched etc

[IG] OK, so this is a sort of user management desktop thing. As close as possible to one's personal PC capabilities, but over the web, right? An all-powerful web services thingie.

This would be sort of like PeopleSoft I imagine, not that I have the faintest clue what PeopleSoft do.

[GB] - blobs persist for 7 days then recycled. These blobs are free - alternatively, blobs cost 2cents per 20K (based on a dollar a gig at present - this will drop though.) One time fee - for five years (based on MTBF of disk) - Plus running costs of say 5.47 dollars a day for a 120GB mirrored server (5 years @ 2000 bucks for rent and power and bandwidth - based on uk prices)
works out at (120 * 1024 * 1024) / 20 * 1024 = 6144 "notes" per day is 5.47/6144 = .9 millicents per note per day - Then add our profit margin - 100%?- you get 4cents setup - 1.8 millicents per day.

[IG] Ok, so someone comes up with a pricing model and revenue and all that.

[GB] So who would use it? Well - you ever tried to build an application in a bank? ha ha - nightmare - power and control are exerted by restricting access to machines and storage.

[IG] Hmm, ok. But - to cast my devil's advocate spears at the idea - anyone who is working in a financial institution like that will not want to pay for the access to a "great tool." They would only use it if it was free to them, which means either there is some con going on and the bank pays for it without knowing, or, the bank is paying for it up front, and it is therefore part of the application.

Are you saying the latter, as that's ok, because the bank itself wants it anyway?

Where I would go a little weak at the knees is that most places I have been get all fuzzy and crazy when they hear that substantial amounts of information are off-site, out of their circle of "physical control."

But let's keep going I'm the plant, recall, I criticise and others grumble and groan until they figure out how to slip one past...

[GB] Second users would be lightweight coordination services - inter organisation - like as suggested in The Tentative Hold Protocol.

Nice idea I think matey

[IG] That's heading in an important direction. Whoever cracks the way to automate the pre-contract parts of the deal process is going to be big.

Personally, my current view is think of it this way:

1. build the payment
2. add the bits that make people use the payment...
2. a hence the IM addition to WebFunds which is "nearly there (tm)".

I.e., build one tool, and then build out from there.

One thing I'm very leary of is people who say that they've worked out a way to automate purchasing and contracting. They never have clue. But, this loose/tentative approach might be such that someone has realised how hard this is...

(Haven't time to read it. Oops, it was by Intel

But I agree, a nice idea. I doubt that we would be able to "build a protocol" .... It's a big job.

[GB] What is it that the large institutions want? In my experience, they want something sold to them by the big 5 (IBM, SUN, Microsoft, HP etc.) Of course, selling to them is next to impossible.

[GB] They want to minimise risk and cost and maximise profit (for them) of course

[IG] Yeah I heard that too If I knew how to do that, I'd be tempted to keep it to myself though

[GB] Sure - that's the crux - they want to buy from the big 5 so they can sue them if anything goes wrong. But the big five need to take advantage of the bazaar effect - millions of programmers rather than just a couple of thousand.

[IG] Well, if that's what you want, then do this:

http://www.iang.org/papers/task_market.html

That we can do. I have the tech, and the knowledge. There is a fair bit of programming to be done, but, I know the traps. Several companies have tried, and have all failed as far as I know. There is one company doing it currently, something with "brain" in the title.

Mind you it is a fair way from J&S. However, maybe it can be turned to legal work. "Project to research a brief on effects of digsig law on payment systems. Must include cases, cite precedences. Supports case to defend Twinkies Tokens v. Crown."

Now, confidentiality of the attack before the judge is an issue in litigation, so it might not be so obvious that we could use open research projects. But, it can be used for deception as well. And,
many projects would be obvious.

[GB] They need to consume services which are reliable and secure - and they will pay the price. The Big 5 need to peer content/services so they can have a comprehensive offering.


[IG] Um. OK. So, a characteristic is reliability. And, security. But, that's all something that we can consider when we've figured out the service.

[GB] This is the point of a directory approach - reputation is key to the success of a service - fast, reliable and cheap - that happy medium. Doesn't stop you downgrading when a service fails - and this gives you realtime failover which is kinda cute.


[IG] Right. But, you cannot have reputation unless you have success. First, you have to succeed, then you can create the brand to protect that success. It is improbable to create a reputation without first having a presence, which means a service or product that has already made it.

Catch 22, of course, which is why the big 5 like buying from big companies and paying the price

[IG] OK. If they are into the legal field... one thing that did arise in my thoughts was a thought that discovery could become a web service.

Here's how it works - in a case there are hundreds of documents flying back and forth. Discovery is the first phase, then there is an intermediate phase where documents are listed in preparation for hearings. Finally, there is the "lifting into evidence" phase, where certain of the previous set are presented.

Now. All the documents have to be fairly available. But, both sides have an incentive to futz with their responsibilities. So, the whole thing is ripe for intermediation. If, in the preliminary proceedings, someone suggests that "we go with S&J Discovery", then all documents/transactions would go to these guys instead. And, S&JD would mount a website, and a huge data repository, such that as documents come in, they are webbed. Each side gets their account, and their password. Access is private, so each side can't see what the other is doing.

In the hearings, S&JD deliver the sets, so the docs are standardised. Both sides get the same quality, so there are fewer arguments.

Hmm, having written the above, I see that it has nothing to do with FC Oh well, maybe S&J can make something of it. Ideas are cheap.

[GB] It dovetails nicely with my idea for a notes services - serendipity. And mine is very much about FC - because we're dealing at the engine level - not the car - the ladiemight make a truck out of it for the legal profession - and on the back of it we make an infra biz...

[IG] It does. Yes. What suprised me was that the legal services world is very very bad at technical stuff. They are very vulnerable to a service bureau taking over large parts of their enteprise.

So, it doesn't have to be the above idea. It could be any hook really, but, once you can get into the legal services field with a net based support service, that combines multiple firms, you can then expand out, using either your post-it notes idea, or the above discovery notion.

That is, eventually, you become the para-legals department. In a sense. You do everything for the lawyers, bar making the coffee.

Have you seen the movie "Minority Report"? Imagine the setup they had, and compare that to a law library.

Big barrier is the law library - it has to be purchased by a new attorney trying to set up practice. I asked my guy - a real good guy - what the good book to get for contracts was, so I could understand how to do Ricardian contracts properly. He said the reference is "Chitty on Contracts."

So I checked, and it is $500 at amazon :-/

Now, imagine S&J Legal Services, puts a big screen into the spare room that is now called the law library, but with no books... Lawyers drive the tech, rent if for $X per month, and scan and search and ...

But, the point is, it doesn't matter what the bait is, in principle, lawyers are vulnerable to this service dependency, I postulate. So the task is to find the best cheap easy bait, and the best set of hooks 1 thru N and roll them out.

[IG] I'll think of something more FC. Perhaps a legal settlement currency, where cases are settled and escrowed in advance, and held in a sort of funny money, in Ricardo of course, and thus less money changes hands?

Comments?

[GB] Sounds like a great idea. We've been dealing with some legal stuff recently - and one of the things people have been asking for is for us to deposit 30K with a solicitor - it would be better to indicate intent by depositing a virutal currency - which would indicate intent and effect contractual obligation?


[IG] There is certainly a market for independant escrow services. Placing it in a currency would be one way. It might be easier to find someone already doing it, and sell them an FC system.

Now that I think about it, if you ask the solicitor this, he'll probably say, "yes, this is what you do.
You go to J&S Escrow Partners in London, place the money with them, and they give you a piece of paper, which you then hand to the solicitor. They are the firm that everyone uses. But your solicitor won't ever tell you about them because he needs your funds in his account because he uses the float to cover his loan to the book seller......."

Now, the thing is to find that firm and sell them on the benefits of going digital. If they were to issue units in Ricardian, instead of paper, they could save some small amount on costs. But, the real future is that once they have got all the lawyers using their Ricardian escrow paper, they can launch a legal currency for other purposes.

[GB] Also it could be used as a proof service so that you could ask whether counterparty has deposited or performed some action?

[IG] yep!

Subprime Explained

A learned colleague sent me a presentation called The Subprime Primer which cynically explains the fine mess that the finance sector are in and how the RSG's bosses are all to blame - mild profanity - you have been warned...

MUSING Workshop - Turning Data Into Risk Knowledge - 21st May 2008

Of note is the MUSING Executive Workshop "Turning data into risk knowledge: Implementation of semantic-based risk management processes in the financial services industry". I've signed up as the agenda looks good. Lots of academics - in particular a guy from Sheffield who is working for GATE.

"MUSING is an Integrated Project co-financed by the 6th Framework Programme of the European Union. Its mission is to shape next generation (Basel II & beyond) semantic-based Business Intelligence, bringing benefits particularly for the financial sector and SMEs by ensuring they have more effective access to credit. MUSING will impact positively on the processes of internationalisation, and empower companies to manage their operational risks more effectively" - they're running the above event details of which you can find here.

I'm interested that a bunch of text miners are focusing on BASEL II compliance and lauding XBRL which seems to be much in the news this week. I read an article in CACM entitled Costs and Benefits of XBRL Adoption: Early Evidence which had good empirical evidence, quoting reporting speed ups of 4x.

If you're interested in this area, there's a good read called Intelligence and Security Informatics for International Security which is now a Google book. My take on the book was that it showed just how ineffective semantic analysis was (70% success rate). I infer that summarisation would fare no better but what do I know.

Sign up - come along - should be a hoot.

Enterprise Computing Strategies Summit

The 451 Group have kindly invited me to speak at the above event on low latency and security. This will give me the opportunity to summarise the High Performance Computing journey that started in 2005 and put in perspective what has evolved over the last three years as we move towards increasingly automated electronic trading.

My approach will be to start with message orientated architectures and argue that they're superior to event driven when it comes to high volumes. Electronic trading mandates the move from end-of-day to real-time risk calculation and analysis - no mean feat. This led my forays into FPGA based Monte Carlo and the whole accelerated simulation idea being followed by various Investment Banks.

Depth Aggregator Market

Of real interest is pricing which used to be done the mid-market average and was becoming market-depth aware about 4-5 years ago. With internalisation and MiFID, we now, in theory, have multiple "exchanges" which we need to consult to ensure we are offering best price. This means depth from each exchange needs to be aggregated as point-to-point won't scale. This could be achieved by depth aggregation services - a nice little business opportunity for someone out there. Perhaps we'll see this sort of service being offered by a smart hosting provider?

Topic-based Multicast Architectures

Specific techniques to calculate in real time could be facilitated by topic based, multi-cast architectures with n of m threshold schemes ensuring data quality.

Visualisation, Social Networking, Idea Networks

Then perhaps looking at the part humans play in this (from trader to trading "intelligence" analyst who builds her idea based social networks) and what visualisation is needed.

Accelerated Hardware Market

I'm then going to summarise the whole accelerated hardware scene, looking at why it's not really going anywhere (apathy, lack of easy integration, no standards, esoteric languages etc) then show the true path (IMHO) - ie monadic languages that are highly parallelisable.

That should be a hoot and quite unique...

Has Cringely been drinking the Kool-aid?

As with many of his articles Robert X Cringely started off with the breathless tones that got me thinking, "how could I have missed this?", but his post goes on for too long with too many unsubstantiated claims to maintain that emotion. As I've maintained over many pints, this is a fascinating time to be in IT. All we need is funding to check these claims, because nothing rankles like unsubstantiated claims.

For example, NPTL sounds really cool. Graeme may have some insights, but this statement seems like fuzzy thinking to me:

"My e-mail application runs on a four-core Opteron server," says a techie friend of mine, "but I've seen it have over 4,000 simultaneous connections - 4,000 separate threads (where I'm using "thread" to describe a lightweight process) competing for those four CPU's. And looking at the stats, my CPUs are running under five percent almost all the time. This stuff really has come a long way."

Is that good? Why do we need 4,000 threads if they aren't actually keeping the CPUs busy? I get the impression that most of these "lightweight processes" are waiting for something. NTPL may be a good thing, but I don't understand how this illustrates the benefits.

In his conclusion he says "If an Azul box were installed on that network, my little app would instantly and mysteriously run up to 50 times faster." Really? I can't follow his argument here at all.

I must have missed the point of his article. If anyone can clarify I'd love to find out more.

Hail the New Information Security World

As it happens I'm deep in Information Security management at the moment which is an interesting diversion from HPC. A young turk is trying to set up an Information Security practise at the firm of some chums and has been asking my advice on where Information Security is at and where it's heading. His hypothesis was to structure it along three lines: architecture (application and networks), implementation and compliance.

This, I feel, reflects the information security world of the past - blighted with too many people who write abstruse policies which no one reads and are heard to continually say "no you can't do that".

I feel it's time for a change so I proposed the following three areas:

• Security Architecture
• Strategy
• Governance
  
• Policy framework, policy and process design
• Security architecture: security architecture patterns
  
• Security API design and analysis
  
• Operational infrastructure design and implementation
• Product selection procurement
• Process design
  
• Information Security Operations
• Process implementation and operation
  
• SLA, compliance monitoring and reporting
• Information Security Analytics
• KRI production, trends, outlier analysis, event correlation, ad hoc reports, event visualisation
  
• Forensic evidence capture, expert witness
• Risk Assessment
  

But there's still something missing - the process of cumulative risk management. Click the image to expand:

General-purpose parallelism

Via Joe Duffy's weblog I just watched an interesting interview with Burton Smith, which is definitely worth sharing. It's about an hour long but here are some key points (many of which we have discussed here in the past):

• He discusses the "Von Neumann mistake" which has led to problems with scheduling due to shared state in computer programs, and ways to solve these problems

• Software transactional memory is a potential solution but currently has issues with scalability

• He is most enthusiastic about functional programming languages. Interestingly he points out that the most commonly used functional languages are Excel and SQL.

• Existing programming languages cannot be "tweaked" - an entirely new way of writing programs is needed to obtain the necessary levels of productivity

• He also says that if Microsoft doesn't solve this problem, nobody will. Maybe he's paid to say that, but they are doing some interesting things with .NET, in particular Smith notes that F# is being "productized" and they are working on parallel LINQ
  

Tokyo Exchange goes Boom! Is there a link to the LSE? Could be...

This article caught my eye when Google Readering yesterday.

http://www.finextra.com/fullstory.asp?id=18058

Back in November,I noted that the LSE went Boom! and that this won't be the last time it falls over. It seems a coincidence that the Tokyo Stock Exchange is suffering performance problems and system crashes like it's technology partner the LSE. The pair "are developing jointly traded products and share technology" - oh really? that's a good idea? Same security vulnerabilities, same performance problems, same mysterious crashes then...

Word on the street also about other products based on dot net having serious, unsolvable bugs: mysterious freezes, runaway memory growth, threading issues and performance headaches, just like I experienced when building my last algo trading platform.

Mind you, this is nothing specific against dot net. I remember when I first worked in the city in 1996 doing C++ and using Roguewave libraries - what a disaster that was. Well I did promise to tell you about the eek bug back in the Haskell post so here goes: I was at my first investment bank - sigh - the good old days. One of the developers had a bug that he couldn't solve after a week - we tried everything - every debugger known - they all pointed to threading problems in the Roguewave libraries but the manufacturer was responding slowly. One day, the programmer put the string "eeek" as a printf debug. Miraculously, the bug disappeared. We tested other strings - non worked - only the eeek string did the trick.

That hardened my heart against third party libraries developed by private companies - when the bugs hit - you often have nowhere to turn. My guess is there's an eeek bug or two in the dot net stuff. If it were open source, perhaps there would be a hope of fixing it...

zeroMQ - Fastest Messaging Ever

Interesting offering from zeroMQ who seem to be pals with Intel. I've checked out the code briefly and am surprised by the use of dynamic memory allocation at such a low level of granularity. I usually allocate a large lump and rely on paging to weed out the empty pages. Anyway, from the very brief look I've had, it's written in C++ and has AQMP compatibility and for some reason I get a whiff of Erlang. More analysis coming soon.

What do you mean by end-to-end latency?

Steve just sent this through:

Order execution dynamics in a global FX market

"Very nice overview. This is key: "First, you need to understand what you mean by end-to-end latency (it will be different for different types of organization)".

One of the key metrics for FX turns out to be time to cancel a trade - on EBS over 70% of $1M trades are cancelled. Nobody wants to talk about the games they are playing so it's a bit tricky to know what someone means when they say they want sub-millisecond execution."

An intuitive paper detailing the clustering, spread and timings of limit orders on EBS. It's argued that impatient traders can drop below current price for faster execution. Sitting above the price takes longer as one would imagine. There's also a correlation with order size, showing smaller volumes trade quicker. Volumes are based on 2006 data and are not particularly high.

What's missing though is the underlying need for fast price and market data. The logical implication is reduction in latency - and therefore the necessity for physical proximity. Perhaps it's time to replicate LINX idea for high performance trading applications?

Object Orientated Security Policy

I gave a talk this week on Object Orientated Security Architecture to a Infosec management audience outside of the normal financial sectors that I work. Hopefully it was well received and made some sense. You can download the original presentation here.

Current State

• Invisible policy framework
• •Loose collection of abstract policies
• •Rarely if ever read, understood or referred to
• •Complex & technical v. functional & clear
• •No business rules (BPML)
• •Monolithic & centralised v. global and federated
• •Uncertain legal status
• •Audit/accountancy driven v. business focused
• •Control rather than functionality

New Ideas

• •Inheritance applied to Security Policy
• •General and abstract to specific and detailed
• •Data, event and process centred
• • Detailed and technical to minimal and clear
• • Navigable framework
• •Process catalogue
• •human readable (ie not just by policy wonks)
• •machine executable

• Components

• Visual Policy framework – (BITS SIG++)
• Hierarchal process catalogue (BITS AUP++)
• •Security Architecture Capture
• subset of BITS SIG
• concentrates on data flows
• asset, data, risk classes
• business value and application complexity
• operational impact analysis

Compliance

• Standardised Information Gathering (SIG) -

- ISO27002:2005, COBIT, PCI-DSS 1.1

• Agreed Upon Procedures (AUP)

• - GLB, HIPPA, COSO, SysTrust, SOX

• Employment Law

Haskell Cryptographic Library - New Release

Having had quite a few contributions lately, I've released a new version of the Haskell Cryptographic Library. It now contains an implementation of TEA and BubbleBabble.

Erlang for Five Nines Talk

Erlang for Five Nines Talk

I attended the above talk given at Skillsmatter.com on the 13th December. There were 37 attendees, two of which were women (women in technology take note.) I'm afraid I was virtually the only suit in the room apart from Francesco (the speaker) so I stuck out like the proverbial sore thumb.

It was a good talk, well received and well presented. Not particulary technical, so I'm afraid I may have asked too many questions, but I couldn't let the opportunity to get a real understanding of practical Erlang slip by. I was particularly interesting in support for multicast but as no one else had heard of it I kept quiet.

Shared Memory Support

One area I was particulary interested in was no shared memory support - all comms has to go through a tcp/ip software stack apparently. I can understand the aesthetic reasons behind this but the implications for high performance messaging are significant: from one Erlang process to another on a remote machine there's an extra two stacks to cross. It would be interesting to compare with the high performance messaging providers.

Real-world Erlang - Yaws Performance

One rather amusing piece was on the performance of Yaws, the Erlang web server, which shows very high throughput compared to Apache. Yaws manages to run 80,000 parallel sessions, serviing 2 x 20KB pages whilst poor old Apache dies after 4,000.

One unfortunate side effect of this would be to consume your organisation's entire bandwidth so I'll stick with Apache for now. If I want to ship that much (presumably) random data, the last tech I'll use is a web server. HDF5, Lustre, GFS, Gigaspaces all have a better handle on this sort of data architecture.

Conclusion

I like Erlang as a concept but they have a mountain to climb with OTP (the function library) if they're going to be more than niche. New features are being added all the time - the latest being a "posix like" threading library and support for SMP. Faster ASN.1 support too with the latest version. Erlang is growing up fast.

For those of you interested in learning Erlang, I'd recommend starting with Joe Armstrong's PhD.

Haskell - The Next Mainstream Programming Language?

Steve sent a pdf by Tim Sweeney of Epic Games entitled "The Next Mainstream Language: A Game Developers Perspective". He commented "While Sweeney doesn't exactly embrace Haskell, he seems certain that some variant will prevail".

Sweeney's 67 page presentation is a worthwhile read. It summarises the logistics of a multi-player online game - Even250K lines of C++, highly object orientated and garbage collected with associated scripts and data files. Object state evolves with gameplay. Typically there's around 1000 classes with 10K objects active during play. Events touch about 5 objects on average.

Numerical computation (for intersect detection, graph traversal etc) uses around 5 GFlops, Shading is inherently data parallel, performed on the GPU using a custom language (HLSL.) It uses around 500 GFLops

The resultant code is performance-sensitive and requires highly modular design of reliable code. Sweeney comments that C++ is poorly equiped for concurrency. This is bourne out by my own experience in the early nineties with Roguewave (remind me to tell you about the eek! bug one day.) A truism is that analysing performance isn't a simple matter of identifying "hot spots" and optimising that code - or writing assembly language to get around an issue. This is never done as Sweeney notes. Event timing and handling, data structure construction, execution path may have to be revisitied resulting in a lack of productivity. A the end of the day - you have to compromise performance vs productivity.

Sweeney then proceeds to deconstruct C++ as a language and Object-Orientation as a principle. As you've probably found yourself, sometimes the base class has to change - leading to significant refactoring. In particular, he slates the inability of C++ compiler to handle dynamic failure, contrasting how Haskell handles this with ease. C# also comes in for a wry observation: it exposes 10 types of integer-like data types, none of which are those defined by Pythagoras...

Pushing Haskell, he hypothesises that 80% of CPU effort could be parallelised using Haskel ST - the Strict State Thread module and, further still, that programmer "hints" can be used to guide parallelisation - stating that Haskell's Monadic nature is a natural fit for parallelisation - imperative programming is perhaps the "wrong trousers".

As I found to my cost, "shared concurrency is [indeed] hopelessly intractible" in my "Why events are a bad idea" post. I too got in a mess with manual synchronisation. Sweeney also suggests as the quoted paper does, that message passing is the recipe for high performance because, when combined with software tranactional memory and multiple threads, the overhead of synchronisation is bearable when the object population his rate is small (~ 5 per 10000 per message.)

The article then concludes with his musings on the next generation language. All-in-all, a nice empirical paper from the coal face.

Next, I'll cast my eye on Erlang - there's buzz there too from the finance crowd, but I know what my next language is going to be - and hit begins with H...

Applied Infoviz and Knowledge Re-injection

The Infoviz toolkit is used at Project Seven by a friend of mine et al. They're working on an intelligence analysis tool which supports reinjection of explicit knowledge earlier in the categorisation/discovery chain to guide discovery.

This is a different approach to the one I took in my signature based approach in my paper "Community-of-interest predicated program trading" where I suggested using centroid categorisation augmented with off-center categories. The Project Seven techinque relies on heuristically directed iteration (or as it's known in lay terms - trial and error) where my technique relies on the visualisation of the categorisation centroid. I think both approaches have merit and would produce good results.

Fork/Join - The End of the Road for FPGA/GPU/ASIC Gang?

Steve W sent this article from IBM - Java Theory and Practise: Stick a fork in it

"One of the additions to the java.util.concurrent packages coming in Java™ 7 is a framework for fork-join style parallel decomposition. The fork-join abstraction provides a natural mechanism for decomposing many algorithms to effectively exploit hardware parallelism."

Steve says "Looks like java 7 will have built-in support for the Fork/Join pattern (i.e. similar to what Erlang has and what the Squeak guys have been talking about)"

Is this the end for the short-lived FPGA/GPU bandwagon? It could well be - with massively multi-core chips round the corner, they are considerably more attractive an option with their on core FPU and low-latency cache etc. Solves a whole lot of issues around buying and supporting esoteric hardware it would seem.

Talk: Erlang for Five Nines by Francesco Cesarini

Looks like an opportunity for a beer afterwards?

"Francesco Cesarini will be presenting the concurrent soft real time functional programming language Erlang and its rapidly growing community. He will describe why Erlang programs are generally 4 - 10 times shorter than their counterparts in Java, C and C++ achieving 99,999% availability. Ongoing research projects in the UK and overseas which will be covered, including refactoring, AI, type systems and control systems for robots. The talk will also go into why Erlang, originally invented to handle the next generation of Telecom products, has been successful in a much wider range of sectors including banking and e-commerce. "

Date: Thursday, 13th December 2007

Time:18:30-20:30

Venue:
Skills Matter
1 Sekforde Street
London EC1R 0BE
Near Farringdon Rail/Tube

Registration http://skillsmatter.com/menu/85

One Thread Per Core

Way back in 1990, when I was performance tuning Ingres on a multi-processor Sequent machine, I found that using processor affinity - ie tieing the main process to a particular CPU gave the best performance. Intuitively I figured that this was due to not having to context switch but never had the time to prove my theory.

More recently, numa issues have been surfacing again in the search for low latency.

A friend of mine has recenly been looking at k-way sorting and the thread scheduling again has come into play. I have always been curious about the analysis of Numa architecture but never got to spend that much time on it. In the old days of single core, context would have to be shared over the bus, Numa was a great advance, introducing a high performance inter-cpu/die channel with about 6GB/s throughput. Now with multicore it's all on the die but appears to be still an issue as the following results show from a friend show:

The k-way merge sort looks pretty good, almost twice as fast as a mono-threaded quicksort. Here some results for 10 millions numeric (double) values to sort :

sort 1st part done (parallel segments) in 3672ms
sort 2nd part done in 3157ms niter=19999993
Total time for k-way merge sorting 10000000 double values=6922 ms
Total time for monoquicksorting 10000000 double values=13609 ms


Now if you look at the performance variation when sorting 2 millions items, it appears that the best performance occurs when the number of parallel sorting threads equals the number of core available from the CPU (my box is a mono quad-core Xeon 5355 2.6Ghz) :

2 threads used:
sort 1st part done (parallel segments) in 1031ms
sort 2nd part done in 469ms niter=1999999
Total time for k-way merge sorting 2000000 double values=1562 ms
Total time for monoquicksorting 2000000 double values=1984 ms

3 threads used :
sort 1st part done (parallel segments) in 688ms
sort 2nd part done in 563ms niter=3333329
Total time for k-way merge sorting 2000000 double values=1281 ms
Total time for monoquicksorting 2000000 double values=2015 ms

4 threads used :
sort 1st part done (parallel segments) in 516ms
sort 2nd part done in 594ms niter=3999995
Total time for k-way merge sorting 2000000 double values=1125 ms
Total time for monoquicksorting 2000000 double values=2000 ms

8 threads used :
sort 1st part done (parallel segments) in 437ms
sort 2nd part done in 781ms niter=5999991
Total time for k-way merge sorting 2000000 double values=1234 ms
Total time for monoquicksorting 2000000 double values=2047 ms

16 threads used :
sort 1st part done (parallel segments) in 391ms
sort 2nd part done in 906ms niter=7999975
Total time for k-way merge sorting 2000000 double values=1313 ms
Total time for monoquicksorting 2000000 double values=2031 ms

LSE Goes Boom!

"No other exchange is undertaking such an ambitious technology refresh programme based on next-generation Microsoft technology. We have always provided a first-class service, but now we can claim to be the fastest in the world as well."
- David Lester, CIO, London Stock Exchange

Now I wonder why no other exchange uses Microsoft technology for high performance messaging then...

The LSE was a big coup for Microsoft - one of the worlds leading exchanges which, until the Infolect platform based on .Net technology came along, had no outages since 1987. Even more embarassing are the anti-linux rhetoric contained in the "Get The Facts" campaign quoting the above David Lester quote - a nice analysis of which you can find here from Paul Murphy. He concludes that the so called high performance message delivery is the same as a "relatively slow LAN".

This won't be the last time this occurs - in my operational experience, solutions based on .Net exhibited mysterious freezes which were never solved.

The Transition from N-Tier to High Performance Architecture

This is a little story of Anybank, who have a classic three-tier architecture using in-house developed solutions. They are embarking on a plan to improve the architecture, aiming for scalability, globalisation and integration in order to meet predicted growth in volumes.

In order to achieve this, the architecture will be transitioned from a transaction-orientated platform to an event-driven, peer-to-peer, asynchronous, persistent messaging-based architecture. Anybank have recognised that in order to achieve this, they must move away from in-house developed solutions and take advantage of open source and third-party products.

Architectural Components

Anybank have a classic three-tier architecture with a moderate level of fan out/in.

At the front end, there are a series of internal trading and control applications and several external client applications and gateways to systems such as FIX.

The communication from tier 3 to tier 2 is TCP based, carrying FIX or HTTP traffic to series of middle tier servers. Additionally, there is a custom protocol used by the thick client to talk to the middle tier servers. This is an efficient ASCII based protocol with pipe-delimited fields.

External Applications

The system has FIX connections to several exchanges and markets. Clients have a choice of a thick client or a web front end. Quotes are sent over FIX at a rate of 4/second.

Internal Applications and Services

There are several internal applications that are used by trading, credit and risk control and operations. The connections to these are managed by a series of front office servers and talk to the database tier for information. They run a generic set of applications that would be found in any other bank:

• Market Making, Trading Station and Sales Trader Workbench: Prop. trading tools
• Session Management: Routing, STP gateways, reception of execution reports.
• Order Moniting: provides snapshot requests and streaming prices
• Client Margin Calculation Engine: Limit checking, credit check, event publishing service
• Exposure and Barrier Monitoring
• Front Office Server: Authentication, Authorisation and Access control (AAA), Event notification.
• Trade Server: Visual trading, large trades and limit trading.
• Market Data Servers: Takes streaming market prices from feed handlers and distributes Market Data
• Metrics and SLA monitoring

The current system handles thousands of daily trades with a peak rate of 200/second. Latency across several systems is in the order of .5 – 1 second with a desire to improve this figure across the board.

Anybank Tiered Architecture Analysis

Several key components have been targeted in an attempt to reduce potential bottlenecks in the system. Serial activities are being replaced with parallel activities, single threaded code is being rewritten to be multhreaded.

However, by applying HPC techniques and chosing the right products, we can gain significant performance quickly and robustly.

Tier 1 - Database Persistence Layer

This is the database layer, which is currently a replicated SQL Server. As with all relational databases, the maximal transaction rate is a function of the IO subsystem, log file transaction rate, number of indexes, data volumes and access patterns. Typically, one can expect a transaction rate of between 1-5 thousand transactions per second, which translates into 5-1 milliseconds per transaction.

Business level transactions may consist of many database transactions, which results in the potential for adding considerable latency to client and API calls.

Tier 2 - Application Services and Access Control Layer

The application logic layers combines authentication, access control and authorisation with business logic, static and derived data, streaming market data and database transactions. It is traditionally at this layer where fan-in/out is facilitated.

Tier 3 - Application Layer

The application layer consists of traditional thick, web and FIX clients, each with their own particular data access profile. Thick clients typically are used when streaming data is consumed by, for example, a pricing application. They may consume data delineated by topic or routed by function.

Web clients typically consume http/https/javascript and/or xml data to drive form-based, browser applications.

FIX clients can potentially deliver 100K messages per second when using FAST, the FIX compression protocol.

HPC Tools Applied to Anybank

The architecture is in transition from client server to an event-based and message orientated structure in order to increase resilience and enable scalability. The architecture has already some elements of fan out via multiple services connected via TCP.

There are opportunities to augment the current architecture and improve transaction capacity whilst reducing latency in each of the three tiers of the current Anybank architecture using Open Source messaging and caching products which have proven robustness in real-world applications.

Tier 1 and 2 - Peer-to-peer Message Bus

The publish and subscribe paradigm is ideal to use where multiple senders and receivers or combinations of the two are present and is common pattern for trading applications where prices, curves, derived data, immediate messages and topic based mechanisms need to be catered for.

In Tier 1 and 2, it is proposed to use the MantaRay peer-to-peer messaging product to provide message caching to tier 2 applications and services, effectively decoupling tier 1 and 2. MantaRay Messaging persistence logic guarantees delivery to unavailable peers once they come back online. Sending nodes need not await responses from a broker before resuming
other tasks. Such capabilities are critical issues in high availability environments. This is considerably faster than a synchronous database access thereby accelerating application performance.

Also In tier 2, application/service fan out will be added using the pub/sub capabilities of the MantaRay solution.

Reliable Multicast over the WAN

MantaRay also has a WAN Bridge capability which accepts connections from other MantaRay peers thereby getting around multi-cast over the WAN issues. This would allow the mixing of the benefits of multicast with the recoverability of MantaRay.

This could be used to distribute real-time market data globally. Peer-to-peer is ideal for this purpose. It can be configured to deliver topic orientated messages over multiple multicast streams, layering the topics in order to use bandwidth effectively using source paced delivery which would be ideal for Anybank.

to be continued...