Process design: Excel-like mutually dependent computations

Questions / Help
,
1

Hello, I am fairly new to the Elixir ecosystem and I would like to know your opinion on what is the best OTP/process architecture for the following problem:

  1. Imagine a typical excel spreadsheet. There are lots of values in cells, some of the cells contain formulas (which may contain references to other cells, possibly also containing formulas). There is A LOT of cells, think hundreds of thousands to millions. Not all of them need to be “visible” at the same time though.

  2. Any value in cell can eventually change, however the frequency of changes spans several orders of magnitude. Most of the cells will update once per year randomly. Some cells will update once per day or hour, some cells are connected to some external data source and update several times per second.

  3. Assume that all cell formulas are representable as pre-defined parametrised functions (we do not care about formula parsing, UI etc.). However these functions may contain tasks of various complexity, for instance:

  • Combine several values from other cells in a simple math function
  • Compute an aggregation of values in a range of thousands of other cells
  • Take some values from other cells, make an external API call, process, output result
  • Dynamically decide on which other cells are needed for computation, compute a part, re-decide, recompute, output

Overall, the “value” in each cell doesn’t have to be a number, any term will do.

In general, the computation in the system is triggered by a change in value of some cell (typically ones connected to external data), which should trigger a re-computation of all cells that depend on it.

All of this seems to nicely fit into the whole process/functional/messaging paradigm, I have read something about actor model, heard something about C# orleans/grains (but don’t really understand it), and so far I have some ideas on how to design this:

Each cell is represented by genserver, that is created on-demand whenever its value is needed. Every cell should implement a function
compute( incoming_event, subscribed_values_map, state ) -> { list_of_actions, new_state }

During computations, the cell returns a list of actions, where each can be either broadcasting its value, broadcasting an event or subscribing to some other cell.

Above this is a linking layer that supervises all the cells, creates them on demand and handles pub/sub distribution of values and events.

The distinction between event and subscribed_values_map is just a convenience for the cell compute implementation. A subscribed value update is basically a :subcribed_value_changed event that would update internal map and recompute.

My main questions are:

  • This seems like a very generic problem that a lot of people must have been solving and maybe I am just missing the right keyword
  • It seems a bit wasteful to have a separate process for each and every cell, particularily ones with mostly-static data.
  • Aggregations of large numbers of cells seem to be hard, that’s why events are there, to support for “item added/updated/removed” messages, so that the aggregation cell can just update the value without need to reaggregate

Thanks in advance for any ideas, keywords and suggestions.

2 Likes
2

Mutually dependent computation leads to chaos. I would make sure the dependency is a tree, with no loops. Computation is then straightforward. To model loops, I would add state holding registers, to postpone some changes to the next round.

Simulation of a complex system is fun; abusing the actor model to have too many actors is not. Start from a single thread program just loop through all tree nodes. If you need parallelism for speed, you can partition the tree later.

3 Likes
3

+1 to what @derek-zhou said

  • It seems a bit wasteful to have a separate process for each and every cell, particularily ones with mostly-static data.

Also maybe get some inspiration from how LiveApps are to be modeled. There are 2 types of components Phoenix.LiveComponent backed by GenServer and “stateless” function Phoenix.Component (not baked by GenServer)

Make it work, then make it beautiful…

4

Performance is certainly a concern, but there’s a bigger problem: how do you read a consistent state out of a spreadsheet where every cell is a separate process? What if some of the cells are doing a long-running operation? It’s possible, with additional machinery, to do this - but it winds up looking like a Paxos knockoff because it is.

I’d recommend focusing on the pure-function part you mention above (compute etc). Then those functions can either be composed together sequentially (iterate over a list of changes to produce new changes, repeat until fixed point) or concurrently (split into communicating processes), but that’s an implementation detail.

2 Likes