Stock Exchange Matching Engine ডিজাইন

ভাবো ঢাকা স্টক এক্সচেঞ্জ (DSE) বা NASDAQ-এর হৃদপিণ্ড। লাখো ট্রেডার সেকেন্ডে হাজার হাজার buy আর sell অর্ডার পাঠাচ্ছে। কে কার সাথে, কোন দামে ট্রেড করবে—এই সিদ্ধান্ত নেয় matching engine। এখানে একটা পয়সাও এদিক-ওদিক হওয়া চলবে না, আবার microsecond দেরিও ব্যবসায় বড় ক্ষতি করতে পারে। চলো এই সিস্টেমটা ধাপে ধাপে ডিজাইন করি।

১. সমস্যা বোঝা (Requirements)

Functional requirements:

• ট্রেডার limit order ও market order জমা দিতে পারবে, এবং অর্ডার cancel করতে পারবে।
• প্রতিটা symbol (যেমন GP, BEXIMCO) এর জন্য একটা order book থাকবে—এক পাশে bids (buy), আরেক পাশে asks (sell)।
• ম্যাচিং হবে price-time priority মেনে: ভালো দামের অর্ডার আগে, একই দামে আগে আসা অর্ডার আগে।
• প্রতিটা match থেকে execution report ও সবার জন্য market data feed বের হবে।

Non-functional requirements (এখানেই আসল খেলা):

• Correctness: ম্যাচিং logic 100% সঠিক হতে হবে। কোনো অর্ডার ভুল দামে fill হলে আইনি ঝামেলা।
• Determinism: একই অর্ডার সিকোয়েন্স দিলে সবসময় একই ফলাফল আসতে হবে—অডিট আর রিপ্লের জন্য জরুরি।
• Latency: ম্যাচিং decision হতে হবে দশ microsecond-এর ঘরে, ১ ms-এর অনেক কম।
• Fairness: কেউ যেন queue jump করতে না পারে।
• Durability: crash হলেও একটা অর্ডারও হারানো যাবে না।

২. স্কেল আন্দাজ (Estimation)

Peak load (একটা বড় এক্সচেঞ্জ):
  Order rate          = 1,000,000 orders/sec (peak burst)
  Symbols             = ~5,000
  Avg per symbol      = 200 orders/sec/symbol

Latency budget (gateway থেকে gateway):
  Network in          ~ 5  µs
  Sequencer           ~ 1  µs
  Matching (in-mem)   ~ 1-5 µs  (lock-free, branch-predicted)
  Market data out     ~ 5  µs
  ----------------------------------
  Total p99           < 50 µs  (tail সহ)

Persistence:
  প্রতি অর্ডার log entry ~ 100 bytes
  1M/sec * 100 B       = 100 MB/sec ≈ 8.6 TB/দিন (raw)
  → compressed + tiered storage-এ পাঠানো হয়

মূল শিক্ষা: throughput বিশাল নয় (১ মিলিয়ন/sec একটা single core সামলাতে পারে), কিন্তু latency-র tail (p99) কে নিয়ন্ত্রণে রাখাই আসল চ্যালেঞ্জ।

৩. API ডিজাইন

API গুলো সাধারণত একটা binary protocol (যেমন FIX বা SBE) দিয়ে হয়, কিন্তু concept বোঝার জন্য logical form-এ দেখানো হলো:

# অর্ডার জমা (gateway → sequencer → engine)
NEW_ORDER {
  client_order_id: "C-7781"   # ক্লায়েন্টের নিজস্ব idempotency id
  symbol:          "GP"
  side:            BUY | SELL
  type:            LIMIT | MARKET
  price:           99.50       # MARKET হলে উপেক্ষিত
  quantity:        500
  tif:             GTC | IOC | FOK
}

CANCEL_ORDER { order_id: 100451 }

# Engine থেকে বের হওয়া events (outbound)
ACK            { order_id, seq_no, ts }
TRADE          { maker_order_id, taker_order_id, price, qty, seq_no }
MARKET_DATA    { symbol, side, price, qty_delta, seq_no }
REJECT         { client_order_id, reason }

লক্ষ্য করো seq_no—প্রতিটা event-এ একটা global monotonic sequence number থাকে। এটাই determinism ও ordering-এর মেরুদণ্ড।

৪. ডেটা মডেল

Hot path পুরোটাই in-memory, কিন্তু persistence ও downstream system-এর জন্য নিচের মডেল লাগে:

Table / Store	মূল ফিল্ড	উদ্দেশ্য
orders	order_id, client_order_id, symbol, side, type, price, qty, status, seq_no	প্রতিটা অর্ডারের জীবনচক্র
trades	trade_id, symbol, price, qty, maker_id, taker_id, ts, seq_no	প্রতিটা executed match
input_log	seq_no, raw_message, ts	sequencer-এর append-only command log (event sourcing)
eod_positions	account_id, symbol, net_qty, avg_price	দিনশেষে clearing/settlement

কেন SQL ও strong consistency এখানে জেতে? টাকা ও মালিকানার হিসাব এখানে—eventual consistency মানে কেউ এমন শেয়ার বিক্রি করে ফেলতে পারে যা তার নেই। তাই অর্ডার, trade আর balance-এর জন্য strong consistency আবশ্যক। তবে মজার ব্যাপার: core engine নিজে কোনো ডাটাবেস ছোঁয় না হট পাথে—সে শুধু in-memory state নিয়ে কাজ করে, আর সঠিকতা নিশ্চিত করে input log দিয়ে। ডাটাবেস write হয় asynchronously, engine-এর বাইরে।

৫. হাই-লেভেল ডিজাইন

ধাপে ধাপে একটা অর্ডারের যাত্রা:

1. Gateway: ট্রেডারের কানেকশন handle করে, FIX/binary message parse করে, basic validation (rate limit, auth, risk check) করে।
2. Risk / Pre-trade check: ক্লায়েন্টের কাছে কি যথেষ্ট ব্যালেন্স/মার্জিন আছে? না থাকলে এখানেই REJECT।
3. Sequencer: এটাই single source of truth। সব gateway থেকে আসা অর্ডারকে একটা মাত্র total order-এ সাজায়, প্রতিটাকে একটা seq_no দেয়, এবং input log-এ লিখে ফেলে (durability)।
4. Matching engine: sequence-করা অর্ডার এক এক করে in-memory order book-এ apply করে, match হলে TRADE তৈরি করে।
5. Market data publisher: order book-এর প্রতিটা পরিবর্তন ও trade সবার কাছে broadcast করে।
6. Downstream: persistence service, clearing/settlement, surveillance—সবাই input log বা output event stream পড়ে কাজ করে।

মূল আর্কিটেকচারাল সিদ্ধান্ত: engine-এর আগে sequencer। এতে engine deterministic থাকে—সে শুধু একটা ordered stream consume করে। একই stream দুটো replica-তে চালালে দুটোতেই হুবহু একই state তৈরি হয় (hot-hot redundancy)।

৬. গভীরে (Deep Dive)

Order book ডেটা স্ট্রাকচার

একটা order book-এ দুটো দিক: bids (descending price) ও asks (ascending price)। প্রতিটা price level-এ একটা FIFO queue থাকে।

• প্রতিটা price level-এর জন্য একটা doubly-linked list (time priority FIFO)।
• Price level গুলো একটা sorted structure-এ—অনেক engine একটা simple array ব্যবহার করে যেখানে index = price (tick অনুযায়ী), কারণ price range সীমিত আর array lookup O(1) ও cache-friendly। RB-tree-ও চলে কিন্তু pointer-chasing cache miss বাড়ায়।
• order_id → node একটা hash map, যাতে cancel O(1)-এ হয়।

Matching algorithm (একটা incoming BUY limit-এর জন্য):

while order.qty > 0 and best_ask exists and best_ask.price <= order.price:
    level = best_ask
    while order.qty > 0 and level not empty:
        resting = level.front()        # সবচেয়ে পুরনো অর্ডার (time priority)
        fill = min(order.qty, resting.qty)
        emit TRADE(price = resting.price, qty = fill)   # maker-এর দাম
        order.qty   -= fill
        resting.qty -= fill
        if resting.qty == 0: level.pop_front()
    if level empty: remove price level
if order.qty > 0 and type == LIMIT:
    add order to bids at order.price   # বাকিটা book-এ বসে যায় (maker হয়)

লক্ষ্য করো ট্রেড হয় resting (maker) order-এর দামে, incoming (taker)-এর দামে নয়—এটাই price-time priority-র সঠিক প্রয়োগ এবং ট্রেডারের জন্য price improvement দেয়।

Determinism ও single-threaded design

বহু লোকের ধারণা low latency মানেই বেশি thread। কিন্তু matching engine-এ উল্টো। একটা single thread, একটা CPU core-এ pin করা (CPU affinity), কোনো lock নেই, কোনো garbage collection pause নেই (off-heap বা C++/Rust)। কেন?

• Lock-free: lock contention মানে unpredictable latency। একটা thread হলে সমস্যাই নেই।
• Deterministic: thread scheduling-এর randomness নেই, তাই একই ইনপুট → একই আউটপুট, সবসময়।
• Cache locality: এক core-এ হট ডেটা L1/L2 cache-এ গরম থাকে।

LMAX Disruptor (একটা বিখ্যাত open-source pattern) ঠিক এভাবেই একটা single thread-এ মিলিয়ন+ TPS করে দেখিয়েছে।

Persistence ও crash recovery (Event Sourcing)

Engine RAM-এ চলে—crash হলে কী হবে? উত্তর: input log রিপ্লে।

Sequencer প্রতিটা command engine-এ পাঠানোর আগেই durable log-এ লেখে (এবং ideally একটা replica-তে replicate করে)। Recovery-তে:

1. সর্বশেষ snapshot লোড করো (যেমন প্রতি ৫ মিনিট অন্তর নেওয়া order book-এর dump)।
2. snapshot-এর seq_no-র পর থেকে input log রিপ্লে করো।

যেহেতু engine deterministic, রিপ্লে করলে crash-এর ঠিক আগের state হুবহু ফিরে আসে।

৭. বটলনেক ও স্কেলিং

• Single core throughput: একটা symbol-set এক core সামলায়। স্কেল করতে হলে partition by symbol—A–F symbol এক engine instance-এ, G–M আরেকটাতে। যেহেতু দুই symbol-এর order book স্বাধীন, এতে correctness নষ্ট হয় না।
• Latency tail: GC pause, page fault, NUMA cross-socket access—এগুলোই p99 নষ্ট করে। সমাধান: pre-allocated memory, huge pages, kernel bypass networking (DPDK / Solarflare), busy-spin polling (interrupt নয়)।
• Sequencer bottleneck: sequencer একটাই (single point of ordering)। এটাকে hot-standby দিয়ে redundant করা হয়, sequence number gap detect করে failover।
• Fairness: সব gateway-কে সমান latency দেওয়া কঠিন; তাই অনেক exchange equal-length cable পর্যন্ত ব্যবহার করে যাতে কেউ physically এগিয়ে না থাকে।

৮. সারসংক্ষেপ

Matching engine-এর হৃদয় খুব সরল ধারণা—price-time priority-তে অর্ডার মেলানো—কিন্তু শয়তান লুকিয়ে আছে non-functional দিকে: determinism, microsecond latency, আর একটাও অর্ডার না হারানো। মূল trick তিনটা: (১) sequencer দিয়ে সব ইনপুটকে এক total order-এ আনা, (২) single-threaded in-memory engine দিয়ে deterministic ও দ্রুত ম্যাচিং, (৩) input log + snapshot দিয়ে event-sourced recovery।