Problem: Design In-Memory Trade Subscription Processor

You are tasked with designing and implementing the internal logic for an in-memory trade subscription processor in C++. The system needs to efficiently handle incoming market trades and notify registered subscribers based on their filtering criteria.

Provided Interface

A simplified C++ interface for the TreadProcessor class is provided:

using HANDLE = int;

struct Tread {
    std::string symbol;  // e.g. "AAPL"
    int         size;    // number of shares
    std::string flag;    // e.g. trade condition / venue flag
};

class TreadProcessor {
public:
    TreadProcessor() {}

    // Called whenever a new trade arrives from the market feed.
    void onNewTread(const Tread &tread);

    // Register interest in trades matching a given template.
    // Returns a handle that can later be used to unsubscribe.
    HANDLE subscribe(const Tread &filter,
                     std::function<void(const Tread &)> callback);

    // Cancel a previous subscription.
    void unSubscribe(HANDLE handle);

private:
    // Design and add your internal data structures here.
};

Assumptions and Matching Logic

• A subscription is defined by a filter of type Tread and a callback function.
• A new trade t delivered via onNewTread matches a subscription filter if:
  • t.symbol == filter.symbol (exact match), AND
  • Optionally, for this question, you can assume size and flag must also match if they are non-zero / non-empty in the filter. This means the filter can act as a simple template with optional fields.
• If a trade matches multiple subscriptions, all corresponding callbacks must be invoked with the trade.

Functional Requirements

1. subscribe(filter, callback):
   • Registers a new subscription using the given filter and callback.
   • Returns a unique HANDLE that identifies this subscription.
2. onNewTread(tread):
   • Called for every incoming trade.
   • Must efficiently find all subscriptions that match tread and invoke their callbacks.
3. unSubscribe(handle):
   • Cancels the subscription associated with handle so that its callback is no longer invoked for future trades.

Non-functional Requirements and Design Goals

• There can be up to 10^5 active subscriptions.
• There can be tens of thousands of trades per second.
• Aim for efficient average time complexity for onNewTread and subscribe.
• Design for reasonable memory usage.
• Assume at least one thread will be calling onNewTread, and another thread may be adding/removing subscriptions. Discuss how you would handle thread safety.

Task

Describe and justify a design for the internals of TreadProcessor. Your solution should cover:

• The internal data structures you will store in the private section to support fast matching.
• How subscribe, onNewTread, and unSubscribe will be implemented conceptually using these data structures.
• An analysis of the time and space complexity of your design.
• A discussion on how you would handle concurrency (e.g., locks, lock-free approaches, sharding, or other strategies) to support high throughput while maintaining correctness.