Re^3: Multithreaded (or similar) access to a complex data structure

[BrowserUk]

(And that's just with the current data set, which is expected to expand tenfold over the next few years)

And therein lies the root of your problem. It's not just your implementation that doesn't scale, but your design.

You are running a very complex simulation representing many discrete, real-world entities that communicate asynchronously. And you are running that simulation on single processor that has to iterate its way over a single, huge God-object in order to simulate all those asynchronous communications and concurrent state changes.

If you attempt to then further complicate that by having multiple threads concurrently iterating their way through that God-object deriving their own particular views of it, they will need to apply locks either universally or to discrete chunks of the data structure in order to derive a consistent 'snap-shot in time' view of the entire entity.

Each new viewer will therefore be impinging and impeding every other viewer, and as the number of viewers grows, so the time spent waiting for locks will grow exponentially. And as the size of the network grows, so the time required to perform a single traversal -- whether to update the status of the nodes as the effects of the state changes of individual nodes ripple through to their neighbours, and then to their neighbours, and then to theirs; or in order to gather a particular view of the instantaneous state of the network for a particular viewer -- grows exponentially as well.

Sorry to be the bearer of bad tiding, given that you've almost certainly expended considerable effort on achieving what you have already, but your design is unsustainable. Adding further complexity to it -- in the form of concurrent viewers with all the additional lock contention and the potential for cascading deadlocking they represent -- will only further hamper your ability to run the simulation in anything like real time.

The only realistic way forward is to:

1. Distribute your network representation across multiple processors.

   Ie. break your God-object into manageable chunks each maintained by a different processor.

2. Distribute the view building.

   By divorcing the presentation logic from the state maintenance.

   I encourage you to think about how Google et al. manage to respond to millions of viewers to their simulations of the entire web in real time. They distribute the state of their model (and the maintenance of that state) across a huge farm of processors. And then service view requests by having front-end processors request the relevant state from that back-office farm before gathering it all together to build their particular view.

That is a bitter pill to deliver, and far worse to swallow, but I seriously believe it is your only way forward. Sorry. I wish you the very best of luck.

[FloydATC]

Well, you've certainly reminded me why I hate and fear multithreading. A flawed design is only a waste of time if you don't learn from it, right? I'll keep meditating on this. :-)

[BrowserUk]

Well, you've certainly reminded me why I hate and fear multithreading.

The problems I describe are not confined to "multi-threading"; they affect multi-processing of all forms.

For example, the typical approach to multiprocessing web applications is to use pre-forking server to run the code and an RDBMS to store the data. The oft misunderstood 'benefit' of this approach is that as forks don't share state, they don't need locking. But this completely misses that all that has happened is the shared state has been moved into the DB and it has to do the locking for you, and so suffers from all the same problems of exponential lock contention as the number of clients trying to access the same dataset increase.

It is exactly these problems with data access through a central "database manager" not scaling to deal with hyper-scale web applications that is the driving force behind the move away from RDBMSs in favour of the whole raft of distributed management data stores broadly categorised under the title NoSQL. Hence you get Google's BigTable; CouchDB; MongoDB; Terastore etc.

Back in the days when the biggest distributed apps were banks and credit cards with a few 10,000s of clients processing a few millions of data accesses per day, routing all those accesses through a central DBM worked. It required BigIron, highly structured and indexed data and very few, very well-defined queries, but it worked and worked well.

Then suddenly you get hyper-scale web applications where you have millions of concurrent clients and billions of transactions every day, asking a myriad of free-form queries against huge and broadly unstructured datasets. Then, having all your clients talking to one central DBM managing one huge data store is not just hugely expensive it is quite simply impossible. BigIron cannot get that big. And so 'the cloud' was born.

The only way forward is to distribute your dataset. Note that distribute is not the same as replicate. Subset the dataset into manageable chunks and have different processors (or clusters of processors) managing those discrete chunks. But then, your clients can no longer talk directly to a single DBM because each DBM only has access to a small subset of the overall data. Instead, clients talk to lightweight front-ends that know enough to be able to break up the inbound query into sub-queries which they route to the distributed DBMs as required. They then gather the various responses from those back-end DBMs and collate the results before finally wrapping it in the presentation layer and sending the reply back to the client.

It requires new architectures and new thinking, but the result is that applications can be scaled by expanding width-ways -- adding more cheap, commodity boxes at the front or back as required -- rather than having to buy bigger and bigger individual boxes at both ends as used to be the case.