订单状态机实现

Order State Machine

专题: General / 综合
难度: L1
来源: MyntBit

个人笔记

题目详情

在电子交易系统中，订单生命周期使用有限状态机严格追踪，以确保交易台与交易所之间的一致性。健壮的订单状态机防止无效状态转换，例如尝试取消已成交的订单，这可能导致监管和财务差异。

任务：实现一个订单状态机，处理所有合法的订单生命周期转换。

英文原题

In electronic trading systems, an order lifecycle is rigorously tracked using finite state machines to ensure consistency between the trading desk and the exchange. A robust order state machine prevents invalid state transitions, such as attempting to cancel an already filled order, which could lead to severe financial consequences.
Task
Implement an OrderStateMachine class that tracks the state of multiple orders and validates state transitions. Orders are identified by a unique integer orderI

解析

问题分析

电子交易系统中，订单的生命周期需要严格的状态机来追踪——从新建（NEW）到部分成交（PARTIALLY_FILLED）到完全成交（FILLED）到撤销（CANCELED）等。非法状态转换（如试图取消已成交订单）可能导致监管违规和财务损失。

解决方案

enum class OrderState { NEW, PENDING, PARTIALLY_FILLED, FILLED, 
                         CANCELED, REJECTED, EXPIRED };

class OrderStateMachine {
    OrderState state_ = OrderState::NEW;
    static const std::unordered_map<OrderState, std::set<OrderState>> transitions_;
public:
    bool transition(OrderState target) {
        auto it = transitions_.find(state_);
        if (it != transitions_.end() && it->second.count(target)) {
            state_ = target; return true;
        }
        return false;  // 非法转换
    }
    
    bool canCancel() const {
        return state_ == OrderState::NEW || 
               state_ == OrderState::PARTIALLY_FILLED;
    }
};

// 允许的状态转换
const std::unordered_map<OrderState, std::set<OrderState>> 
OrderStateMachine::transitions_ = {
    {OrderState::NEW, {OrderState::PENDING, OrderState::CANCELED}},
    {OrderState::PENDING, {OrderState::PARTIALLY_FILLED, OrderState::FILLED, 
                           OrderState::REJECTED, OrderState::CANCELED}},
    {OrderState::PARTIALLY_FILLED, {OrderState::FILLED, OrderState::CANCELED}},
    {OrderState::FILLED, {}},  // 终态，不可转换
    {OrderState::CANCELED, {}},
    {OrderState::REJECTED, {}},
};

关键考虑

不可逆终态：FILLED、CANCELED、REJECTED 为终态，不能再进入其他状态。这保证了一致性。
并发安全：状态转换必须是原子的。使用 `std::atomic` 包装枚举或加锁保护。
审计日志：每次状态转换应记录时间戳、触发原因和操作者，用于事后合规审查。
交易所同步：本地状态机需与交易所的订单状态保持同步，处理交易所主动推送的状态更新。
时间复杂度：转换检查 O(1)；空间复杂度：O(S²) 其中 S 为状态数。

英文解析

Analysis

In electronic trading systems, an order's lifecycle requires a strict state machine to track transitions — from NEW to PARTIALLY_FILLED to FILLED to CANCELED, etc. Illegal state transitions (e.g., attempting to cancel a filled order) can lead to regulatory violations and financial losses.

Solution

enum class OrderState { NEW, PENDING, PARTIALLY_FILLED, FILLED, 
                         CANCELED, REJECTED, EXPIRED };

class OrderStateMachine {
    OrderState state_ = OrderState::NEW;
    static const std::unordered_map<OrderState, std::set<OrderState>> transitions_;
public:
    bool transition(OrderState target) {
        auto it = transitions_.find(state_);
        if (it != transitions_.end() && it->second.count(target)) {
            state_ = target; return true;
        }
        return false;  // illegal transition
    }
    
    bool canCancel() const {
        return state_ == OrderState::NEW || 
               state_ == OrderState::PARTIALLY_FILLED;
    }
};

// Allowed state transitions
const std::unordered_map<OrderState, std::set<OrderState>> 
OrderStateMachine::transitions_ = {
    {OrderState::NEW, {OrderState::PENDING, OrderState::CANCELED}},
    {OrderState::PENDING, {OrderState::PARTIALLY_FILLED, OrderState::FILLED, 
                           OrderState::REJECTED, OrderState::CANCELED}},
    {OrderState::PARTIALLY_FILLED, {OrderState::FILLED, OrderState::CANCELED}},
    {OrderState::FILLED, {}},  // terminal state, no further transitions
    {OrderState::CANCELED, {}},
    {OrderState::REJECTED, {}},
};

Complexity & Edge Cases

Time complexity: O(1) for state transition lookup; O(S) for full state enumeration where S = number of states
Space complexity: O(S * T) for S states and T transitions table
Edge cases: (1) Invalid transition (e.g., canceling a filled order) must be rejected. (2) Partial fill transitions must track remaining quantity. (3) Concurrent state transitions from multiple threads require atomic updates.

Key Considerations

Irreversible terminal states: FILLED, CANCELED, and REJECTED are terminal states with no further transitions, guaranteeing consistency.
Concurrency safety: State transitions must be atomic. Use `std::atomic` wrapping the enum or lock protection.
Audit logging: Every state transition should record a timestamp, trigger reason, and operator for post-hoc compliance review.
Exchange synchronization: The local state machine must stay synchronized with the exchange's order status, handling exchange-pushed status updates.
Time complexity: transition check O(1); Space complexity: O(S\u00b2) where S is the number of states.