Flip Model: A Design Pattern

This article was originally published in the December 2018 issue of ACCU Overload Journal.

---

In this article, I will introduce a design solution that I have utilized multiple times in the past while working on applications designed to diagnose complex distributed systems. This solution has proven effective across various contexts and continues to demonstrate its robustness in various operational systems.

While I am aware that other developers have employed this pattern, my research has shown a lack of references to it in the existing literature. This motivated me to document and discuss it here.

After careful consideration, I have chosen to present this pattern in the familiar format of a Design Pattern. I believe that this approach remains a convenient way to discuss both software and architectural design, which are fundamental topics in Software Engineering and should not be overshadowed by more mundane concerns.

Moreover, I recognize that some novice developers may not be familiar with the groundbreaking book "Design Patterns" which has left a significant impact. With this article, I hope to bridge that knowledge gap and inspire curiosity about design patterns and software design in general.

In the following sections, I will detail the pattern following the well-established documentation structure outlined in the original book. For further reference on this structure, you can refer to the 'documentation' section in the Wikipedia article or, even better, read the original book.

Pattern name and Classification

Flip Model (behavioral).

Intent

The pattern allows multiple clients to read a complex data model that is continuously updated by a unique producer, in a thread-safe fashion.

Also known as

Model publisher, Pressman, Newsagent.

Motivation (Forces)

There are instances where it becomes necessary to decouple the utilization of a complex data structure from its source. This decoupling should enable each actor to operate at its own pace without causing interference.

Consider, for example, an application that periodically retrieves information from a vast sensor network to perform some kind of statistical elaboration on the collected data set and send alarms when some criteria are met. The data collected from the sensor network is structured in a complex lattice of objects resembling the ones you would find in the physical world so that the elaboration modules can navigate the data in a more natural way. The retrieval operation is a long, complex task, involving several network protocols, that is completely uncorrelated from the statistical analysis and alarms evaluation, and can possibly run in separated threads. Moreover, data retrieval and its usage have different timing (e.g., the sensor network is scanned every 5 minutes, while the statistical elaboration is performed on request by a human operator on the most recent collected dataset).

In this scenario, how can all the modules of the application work together on the same data structure? How can all the clients use the most updated data available in a consistent fashion? And how can the application get rid of the old data when it is no longer needed?

The core idea of the Flip Model pattern involves passing the sensor data structure from the producer to the consumers using two shared pointers (in C++) or two variables ((in garbage-collected languages). One variable (termed filling) holds the currently acquiring data object structure, while the other (termed current) holds the most recently acquired complete data.

A class named SensorNetwork determines when to initiate a new acquisition and replaces current with filling when the acquisition process concludes. When a client needs to perform some tasks on the data acquired, it contacts SensorNetwork, which returns current (i.e., the most recent data acquired). An instance of the SensorAcquisition class is kept alive and unchanged during the whole time a client holds the smart pointer (and the same is still valid in garbage collected languages).

Both data acquisition (performed by SensorAcquisition) and its reading (performed by the various clients: Statistics, ThresholdMonitor and WebService) can potentially run in multiple threads. The safety of the code is ensured through the following observations:

• A SensorAcquisition object can be modified only by the thread of SensorNetwork, and never changed after it becomes public (i.e., the smart-pointer current is substituted by filling).
• The smart pointer exchange is protected by a mutex.

It is worth noting that here the mutex is required because std::shared_ptr provides a synchronization mechanism that protects its control-block but not the shared_ptr instance. Thus, when multiple threads access the same shared_ptr and any of those accesses use a non-const member function, you need to provide explicit synchronization. Unfortunately, our code falls exactly under that case since the method SensorNetwork::ScanCompleted assigns the shared_ptr to a new value.

However, if the presence of a mutex makes you feel back in the eighties, please see the ‘Implementation’ section for some modern alternatives.

The figure below illustrates a typical class structure for the Flip Model pattern:

Applicability

Use Flip Model when:

• Dealing with a complex data structure that updates slowly.
• Multiple clients need to asynchronously read the most recent data consistently.
• Older information should be discarded when is no longer needed.

Structure

The following figure shows the pattern structure.

Participants

• Snapshot (SensorAcquisition)
  • Holds the whole set of data acquired from the source.
  • Performs a complete scan.
  • Possibly provides const function members to query the acquisition.
  • Possibly is a set of (heterogeneous) linked objects (e.g., a list of Measure objects).
• Source (SensorNetwork)
  • Periodically requests the source to perform a new scan.
  • Provides the latest complete scan to its clients.
• Client (WebService, ThresholdMonitor, Statistics)
  • Requests the Source for the latest available Snapshot and utilizes it (in read-only mode).

Collaborations

• Source periodically creates a new Snapshot instance, assigns it to the filling shared_ptr, and commands it to start the acquisition.
• Upon completion of the acquisition, Source performs the assignment current=filling protected by a mutex. If no clients were holding the previous current, the pointed Snapshot is automatically destroyed (by the shared pointer).
• When a client needs the most recent Snapshot, it invokes Source::GetLastSnapshot() to obtain current.

The figure below illustrates the collaborations between a client, a source and the snapshots it creates.

Consequences

• Flip Model decouples the producer from the readers: the producer can go on with the update of the data (slow) and each reader gets each time the most updated version.
• Synchronization: producer and readers can run in different threads.
• Flip Model ensures coherence across all data structures read by a reader at any given moment, without the need to lock these structures for a long time.
• Memory consumption is minimized while ensuring that each reader has coherent access to the most recent snapshot.

Implementation

Here are eight considerations to keep in mind while implementing the Flip Model pattern:

1. Acquisition can be initiated periodically (as illustrated in the example) or continuously (immediately after the previous acquisition concludes). In the former case, the scan period must exceed the scan duration; otherwise, the data acquired from the previous scan is discarded when the timer triggers again.
2. While the pattern is described using C++, it can also be implemented in languages with garbage collection. In C++, std::shared_ptr is necessary to ensure that a Snapshot is deleted when no clients are using it and Source has a more recent snapshot ready. In languages with garbage collection, the collector will take care of deleting old snapshots when they’re no longer in use (though this happens at an unspecified time, potentially leading to a buildup of unused snapshots in memory).
3. For the std::shared_ptr (or garbage collection) mechanism to work correctly (i.e., old snapshots are deleted) clients must use Source::GetLastSnapshot() each time they require a snapshot.
4. The Snapshot (and the application in general) can be synchronous or asynchronous. In the former scenario, the Snapshot::Scan method is a blocking function and the caller (Source) must wait until the data structure is completed before acquiring the mutex and assigning current to filling. Within a synchronous application, clients will run in other threads. In the latter scenario, the Snapshot::Scan method initiates the acquisition and promptly returns. When the data structure is completed, an event notification mechanism (e.g., events, callbacks, signals) takes care to announce the end of the operation to Source, that can finally acquire the mutex before assigning current to filling. Asynchronous applications can be single-threaded or multi-threaded.
5. The pattern supports every concurrency model: from single threaded (in a fully asynchronous application) to maximum parallelization (when the acquisition and each client operate in their own threads). When acquisition and snapshot usage occur in separate threads, a synchronization mechanism is necessary to safeguard the shared_ptr. While the simplest solution involves using a mutex, C++11 and beyond offer the possibility to use overload functions std::atomic_...<std::shared_ptr> (and maybe from C++20 std::atomic_shared_ptr). It's worth noting that the implementation of atomic functions might not always be lock-free (in fact, my tests with the latest GCC version show that they're not), potentially resulting in performance inferior to the mutex-based version. A better solution could involve using an atomic int as a key to select the correct shared_ptr (refer to the ‘Sample code’ section for more details).
6. The objects composing Snapshot (usually a huge complex data structure) can be deleted and recreated in each scan cycle. Alternatively, a pool of objects can be utilized (in this case, the shared_ptr must be replaced with a reference-counted pool object handler).
7. It's crucial to recognize that Snapshot (and the classes it represents) is immutable. After its creation and the scan is completed, clients can only read from it. Once a new snapshot is available, the old one is deleted, and clients begin reading the new snapshot. This approach greatly enhances concurrency, as multiple clients across different threads can read the same snapshot without requiring locks.
8. Be aware of stupid classes! Snapshot (and the classes it represents) should not merely be passive data containers. Each class should at least contribute to retrieve its own data, and one could also consider whether to add methods and facilities to use the data.

Sample Code

The C++ code below provides an outline of the Flip Model pattern's implementation based on the description provided in the 'Motivation' section:

class SensorAcquisition
{
public:
    // interface for clients
    const SomeComplexDataStructure& Data() const { /* ... */ }
    // interface for SensorNetwork
    template 
    void Scan(Handler h) { /* ... */ }
};

class SensorNetwork
{
public:
    SensorNetwork() :
        timer( [this](){ OnTimerExpired(); } )
    {
        timer.Start(10s);
    }
    shared_ptr GetLastMeasure() const
    {
        lock_guard lock(mtx);
        return current;
    }
private:
    void OnTimerExpired()
    {
        filling = make_shared();
        filling->Scan([this](){ OnScanCompleted(); });
    }
    void OnScanCompleted()
    {
        lock_guard lock(mtx);
        current = filling;
    }

    PeriodicTimer timer;
    shared_ptr filling;
    shared_ptr current;
    mutable mutex mtx; // protect "current"
};

class Client
{
public:
    Client(const SensorNetwork& sn) : sensors(sn) {}

    // possibly executed in another thread
    void DoSomeWork()
    {
        auto measure = sensors.GetLastMeasure();
        // do something with measure
        // ...
    }
private:
    const SensorNetwork& sensors;
};

It's worth noting that the inclusion of a mutex in the code above is intended for clarity. The subsequent code snippet demonstrates a lock-free alternative:

class SensorNetwork
{
public:
  SensorNetwork() :
    timer( [this](){ OnTimerExpired(); } )
  {
    // just to be sure :-)
    static_assert(current.is_always_lock_free); // c++17

    timer.Start(10s);
  }
  shared_ptr GetLastMeasure() const
  {
    assert(current < 2);
    return measures[current];
  }
private:
  void OnTimerExpired()
  {
    // filling = 1-current
    assert(current < 2);
    measures[1-current] = make_shared();
    measures[1-current]->Scan([this](){ OnScanCompleted(); });
  }
  void OnScanCompleted()
  {
    current.fetch_xor(1); // current = 1-current
  }

  PeriodicTimer timer;
  shared_ptr measures[2];
  // c++14
  atomic_uint current{0}; // filling = 1-current
};

Just in case you were wondering, you do need an atomic integer type here, although only one thread is writing it (have a look at C++ memory model to go down the rabbit hole).

Known Uses

Flip Model is used to retrieve the periodic diagnosis of network objects in several applications I worked on. Unfortunately, confidentiality constraints prevent me from sharing specific details about these projects.

Related Patterns

• The pattern is somewhat similar to ‘Ping Pong Buffer’ (also known as “Double Buffer” in computer graphics), but Flip Model allows multiple clients to read the state, each at its convenient pace. Moreover, in Flip Model, there can be multiple data structures simultaneously, while in ‘Ping Pong Buffer’/‘Double Buffer’ there are always two buffers (one for writing and the other for reading). Finally, in ‘Ping Pong Buffer’/‘Double Buffer’, buffers are swapped, while in Flip Model the data structures are passed from the writer to the readers and eventually deleted.
• Snapshot can serve as a “Façade” for a complex data structure.
• Source may utilize a “Strategy” to change update policies (e.g., periodic versus continuous)