Ludicrous-speed matching architecture: A MIO technology

One of the more recent technology innovations we’ve made at MIO is a very, very high-performance match system for massive data volumes.

I’d like to talk about it first of all because it’s cool…

…and secondly because it’s a great example of how it’s important to not just always run with whatever technology is new and shiny as a default.

© MIO

Background

Building a matching engine that’s:

• Persistent
• Instantly recoverable
• Continuously updatable
• Massively scalable
• And works on any data/object model

is very difficult. This is something you’d only need for very large volumes of data and the result requires significant hardware resources to process the amount of data it was built for.

I know because we at MIO have built such a system and have delivered extreme projects with it for over a decade.

But you don’t always need all that. What if you removed some of the tough to achieve requirements like “persistent” and “instantly recoverable” and limited the scalability to just one server?

The updated requirements

If your engine isn’t persistent or instantly recoverable, you have to restart after a crash. But if the non-persistent engine is orders of magnitudes faster than the persistent version, maybe that’s fine. And if you’re only matching with recent history, not over all time, restarting is even more acceptable.

And one server can be very large these days. So you can limit yourself to a single server and still process terabyte-sized datasets, which is large enough even for most Fortune 500 companies.

So we thought: what if doing our matching with a non-persistent engine, in one shared-memory space of a single server, meant it could run 100 times faster?

Meaning, it’s so much faster than the persistent version that you’d need 100x as many servers to do the persistent version effectively. Making the non-persistent version of our matching as scalable as the persistent version is, up to 100 servers.

A few years ago we had a project that needed this concept.

Developing the ludicrous engine

With our history we knew what we wanted to do and what architecture we were after. So it took a few days to complete the initial prototype and then a few weeks, around a month, to get all the extra details in.

Of course when you’re building something like this, it’s much easier if you have an existing platform that can do the matching handy. Which we did, in the form of MIOvantage.

Basically we could do the matching we wanted to do in MIOvantage, just not as fast. And MIOvantage was fully proven and tested at that point so we knew we could rely on it.

We used MIOvantage to build an answer sheet for a particular scenario, and then we compared the ludicrous engine results to that. Then we knew right away if the ludicrous engine was generating the correct matches and candidate sets or not.

We called the result “ludicrous,” a reference to “ludicrous speed.” So we have the ludicrous architecture, ludicrous engine, and ludicrous matching.

Ludicrous speed matching

Core “ludicrous matching” ideas:

• Execute everything in memory, using basic but very high-speed native language data structures, like Dictionary/Map instead of a database index.
• Leverage 64-bit shared memory when using these data structures
• Use multi-threading to leverage all the cores of the server
• Do not use any form of network or disk I/O during the match processing. That would only slow us down.
• Leverage object identity in memory to avoid duplication of data and to instantly provide transitive match properties.

These are on top of our core matching ideas:

• Index the records/objects you want to match by keys that represent candidate sets.
• Multiple indexes are used to support different kinds of candidate sets.
• Within a candidate set of possible matching records/objects, perform non-indexable matching like fuzzy matching or other, slower comparison rules.
• Record the set of matched objects/records (supermatching).
• Synthesize a final output based on the matched record set

Supermatching

Supermatching is really where using identity is so advantageous, because the same objects and records could be found to match in different candidate sets. So you need to coalesce these objects into one set.

In the persistent multi-server world, which is where we originally implemented this, this is complex.

That’s why we gave “supermatching” a special name.

But, in the ludicrous architecture, supermatching is rather straightforward.

All the processes in the ludicrous architecture share the same memory space, and the original object and record are still in memory when the matches are found in the candidate sets. So it’s easy to create a global registry of resulting groups, even in a highly-parallel multi-threaded environment.

Using the ludicrous engine

Our biggest project with the ludicrous engine provided streaming completion and composition of billions of cellphone records per day. They came in via Kafka and we matched transitively on different keys like IMEI and IMSI, and built a full view of the data to pass downstream.

This data is transient, and we only needed to keep a sliding window of old records available. So the ludicrous architecture’s all-in-memory solution was ideal. Otherwise, we’d spend considerable resources just on deleting old data once we are done with it.

Takeaway

Not everything requires big platforms or database engines. Sometimes the answer is a custom program that focuses on the fundamental goal and leverages basic computer science principles to get there.

Author’s note: I’d love to take the ludicrous engine further and use the ideas elsewhere, but we haven’t had a project that calls for that yet. If you have one, get in touch with MIO.

About the author

Bert Barabas is MIO’s co-founder and chief technology officer.