Testing Distributed Systems

When testing a distributed system, it is the lines that connect the boxes that are a challenge.

In a single program, we can unit test a function f and show that it behaves correctly in isolation for all input parameters. Because f is deterministic, we can have high confidence that, for a given input, it will always produce the same result.

The challenge in distributed systems is that correctness depends not only on the behaviour of individual functions or services, but also on the interactions between them. The devil is in the edges.

Unit tests give us confidence in the nodes. But system behaviour emerges from the paths between them.

The testing scale explosion of a distributed system

Imagine a small distributed system of ten services, named A to J. Always starting at A, and assuming no node is used twice, there are 986,409 simple paths or workflows.

For path length 2 we visit three nodes with two edges. Always starting at A we can visit any of the remaining 9 nodes. If we chose B we can then visit any one of the remaining 8 nodes, C to J. There are 72 such workflows, including A -> B -> C, A -> B -> D, ..., A -> I -> J.

However, not every workflow is valid through ten services.

For a customer placing an order, we may have:

Customer Browser →
    API Gateway →
    Authentication Service →
    Shopping Basket Service →
    Order Service →
    Payment Service

We would not have Customer Browser → Authentication Service → API Gateway and nor would we have Payment Service → Order Service → Shopping Basket Service.

In a real graph of services, the set of valid workflows is decided by the business logic.

A distributed system of \(n\) nodes can be viewed as a graph, where nodes represent services and edges represent interactions between them. As a workflow executes, it traverses a path through this graph.

The 986,409 unique workflows shows the size of the space with just 10 nodes and explicitly writing and maintaining a meangingful number of workflow tests is not possible.

As \(n\) moves beyond 10, the number of possible paths (service combinations) becomes huge.

In a system with a sizeable number of services (\(n\) is around 50 or 100), a number of sub-systems could exist, and workflows within one sub-system might never interact with those within another sub-system.

When we combine this sub-system view with the business logic defining the actual number of workflows, there may be significantly fewer paths. However, even if this reduced the number of paths to one millionth of the theoretic maximum, for N=50, the number of paths would still be 1.653e57.

Discussion

The significance of the rapidly increasing number of paths is not that every path must be tested. However, it does illustrate that exhaustive testing becomes infeasible even for modestly sized distributed systems.

As system size grows, testing must move from proving correctness based on coverage to managing risk through careful path selection, architectural constraints, observability, and operational controls.

As you introduce services, you multiple the number of total workflows by approximately \(n\). The total number of workflows when \(n = 10\) is 986,409, at \(n = 11\) it is 9,864,100. As you introduce a node into a distributed system, you significantly increase the testing burden.

Exhaustive testing becomes impossible very quickly

By 20 nodes, coverage becomes a sampling problem. Only those nodes that really matter are tested. Selecting the right path becomes a business decision not one solely for engineering.

Risk is concentrated in specific workflows

The workflow:

Browse → Basket → Checkout → Payment is commercially more important than Browse → Recommendations → Reviews.

It is bad if recommendations or reviews are not working. It is catastrophic if users cannot pay as the company is not earning revenue and customers may permanently go elsewhere.

Testing effort should be directed to workflows that have impact for the business.

Statistical confidence replaces certainty

To build confidence in sample-testing our distributed system:

• unit tests, establishs that a component works correctly in isolation
• integration tests, shows that pair-wise or short workflows are correct
• full workflow tests, demonstrates end-to-end customer use is valid
• production monitoring
• canary releases (a new version of a system is released to a small subset of users or services first)
• synthetic transactions

Production becomes part of the testing strategy

Given the number of possible workflows, some may never be executed in a test environment. Observability and recovery becomes as important as testing.

Logs, metrics, tracing, alerting, and rapid rollback become your staple correctness features that let you respond should a given production path fail.

As we can only have confidence in our distributed systems that cannot be exhaustively tested, the tools available to us to recover when something fails are paramount.

Architecture

As \(n\) increases, reducing the number of possible interactions is a positive way forward: it is hard to reason about a component A that can call any of 50 services.

If component A can only interact with an Orchestrator that must call a Domain Service, that is easier to think about should there be a failure.

One way to support this is to define legal interactions at run-time. If a component other than A called the Orchestrator, a run-time error could be flagged via observability.

It is tempting to define this through configuration. However, for size \(n = 50\), even with sub-systems and a constrained number of workflows defined by the business logic, there will be a significant amount of configuration to write and maintain. Rather than do this, inter-component calls could be logged and observability could flag unusual interactions to a human based on historical data.

Chaos engineering can also bring to light those unusual interactions that humans might not think to explicitly test. Such testing can be handled by having components interact with each other at random; the assumption being randomization will lead to untested workflows.

Interactions matter more than components

In testing a distributed system, it is hard to show that a service works correctly when interacting with other services as part of a workflow.

This is because there are so many components involved, and the resources that the correctness of the system relies on reside outside the components.

This networking, hardware and software evironment can be changed at any time, independently of the components. Any such change may cause component failure.

The devil is in the edge

In a distributed system, when Component A calls a remote B, a significant amount of faith is placed in the technology that is in neither A nor B to complete the invocation correctly. And the likelihood of an error increases the further apart they become.

If both A and B are in the same data centre, one set of possible failure scenarios applies. If A and B are executing on different continents, a larger set of possible failure scenarios applies.

For example, both running within the same data centre means it is more likely the two components are subject to the same administration policies. If A and B are separated by a continnent, it is more likely - but not guaranteed - that A and B are subject to differing hardware, network, and software management policies. Within the same data centre, changes that affect A are likely to also affect B, which is less likely in the other case.

We are all familiar with a failure caused by B crashing or inadequate resourcing within A or B causing an invocation to fail.

But examples of a different class of failure, that lie outside both A and B are:

• the invocation timesout
• B is available but there is no network route to it
• B is not available due to management policies
• the invocation fails due to inadequate resourcing in between A and B

These kinds of issues are why faith is required when invoking a remote component. So much of the invocation travels through technology that is not directly related to either A or B.

This is why calls between A and B on the same machine work, only to fail when A and B are separated by more distance.

If A and B are designed, implemented and tested assuming A and B are running on the same machine, and then B is moved to a data centre in another city, the number of failure types has increased. Therefore, the invocation is more likely to fail. The code has not changed, the environment has.

The environment may change independently of the code. And when it does, this is why logs, metrics, tracing, alerting, and the rapid rollback of change become your staple correctness features.

Conclusion

It is hard to test a distributed system for two main reasons: scale, and the components of the system run within a separate environment that may change independently of component code.

Testing approaches based on sampling help address scale and chaos engineering can expose workflows that might not be tested explicitly.

A distributed system is really two systems: the components that implement the soilution, and the environment in which those component operate. Changes in the environment can affect correct operation of the components. Minimizing such changes is key to operating distributed systems.

Read next: Why Early Architectural Decisions Restrict Your Future Options
Residuality is the design discipline of creating a boundary so that an implementation does not exclude future options.

Related Articles

• Retry Windows and the Limits of Idempotency
• Preventing Double‑Spend: Idempotency, Internal IDs, and the Discipline of State Before Side‑Effects
• What Python async exposes that synchronous code hides
• Latency is architectural
• Hashgraph: a Byzantine fault-tolerant state‑driven, history‑interpreting consensus algorithm