2

I'm working on system that analyses non-trivial amounts of data. The analysis is pyramidal, in that various combine to make intermediate values, which in turn combine with each other and more inputs to make higher-order intermediate values, and so on, until the value is produced. As a simple example: inputs A & B combine to make intermediate product X, inputs A & C combine to make intermediate product Y, inputs C & D combine to make intermediate product Z, and then intermediate products X, Y, and Z are combined with input E to make the final result. See below for a crude diagram representing this example relationship.

crude paint Paint diagram of pyramidal calculation

Nearly all of these steps are expensive enough to have user-noticeable performance costs, both retrieving the inputs and calculating the intermediate products. On the plus side, all of the inputs change only when requested by the user, so their values can be cached and reused, and the system can be specifically notified when one of the inputs has changed. Thus worrying about when to invalidate caches isn't a problem.

The problem I'm struggling with is where the responsibility lies for clearing the caches for the intermediate products; after all, if input A changes in the example above, we need to recalculate X and Y, but we can keep the cached values of Z, as well as B, C, D, and E.

I'm using the Event Aggregator pattern, but I can't decide what event the cache for, say, Y should use to trigger its invalidation. I can see a couple options:

  1. The cache for Y can subscribe to both the A-data-changed and the C-data-changed events and invalidate when it receives either of them. This requires Y to know that it depends on A & C, and means that higher-level caches have to subscribe to more and more data-changed events to cover all their dependencies (and their dependencies' dependencies, and so on).
  2. The caches for A & C could send a Y-data-changed event whenever they receive their own data-change events. This would require them to know that Y depends on them, and would also require them to send data-changed events for all the downstream products that depend on them. Additionally, it would generate unnecessary duplicate change events for higher-level products (as multiple dependencies all try to pass on the message).
  3. A separate dependency manager / event translator could keep track of all the dependencies and know that, e.g. if it sees a C-data-changed event it needs to send Y-data-changed and Z-data-changed events, as well as events for anything that depends on Y or Z, all the way up the pyramid.

I'm leaning towards going with #3 and putting the new manager with/near the DI root. Are there advantages/disadvantages to these approaches I've overlooked? Or alternate approaches, at that?

3
  • Each cache subscribes to one or more data sources, and is a data source for the next higher layer (cache or application/user reading the final result).
  • Each data source provides a value and a change event.
  • When a cache sees a change event from one of its sources, it sets a flag denoting its own value is invalid, and signals its change event.
  • After all change events have rippled up to the final consumer, the value at the top can be computed. Since every cache knows whether its data is valid or stale, only those computations which are necessary will be performed.

The tricky point is how to avoid unnecessary recomputations. Two possible causes:

  • A cache output does not actually change when an input changes. Example: The cache computes the maximum of its sources, and the changed source was and still is lower than the max, so the output stays the same. In such a situation, the cache might do eager invalidation (recompute its value when the event happens) and only signal its own change event when the output actually changed.
  • When a data source is consumed by two or more caches, its change will cause invalidation of all of them. To avoid an unnecessary recomputation at the next higher level, you need a mechanism to separate the event rippling phase from the recomputation phase. How this can be done depends on your application.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.