MIMD 0009 Multi Threaded Scheduler

[bmuddha]

Multi Threaded Scheduler Design

Abstract

The current validator implementation lacks efficient transaction execution
scheduling, operating under a global state lock that creates a single pipeline
path for the transaction lifecycle. This design constraint limits execution to
one OS thread at a time, failing to leverage available hardware parallelization
capabilities. Additionally, the pipeline presents optimization opportunities
given the nature of ephemeral nodes.

This MIMD proposes an efficient multi-threaded scheduler implementation that
utilizes available OS threads to achieve near-linear scaling with CPU core
count under low-contention scenarios (minimal account lock conflicts).

Architecture and Control Flow

The proposed scheduler centers around a thread-safe account lock database
managed by a dedicated scheduler thread. The high-level execution flow follows
these stages:

Transaction Processing Pipeline

1. Signature Verification: Performed on the receiving thread without
   acquiring locks
2. Account Validation: Ensures all transaction accounts exist in the
   accounts database without lock acquisition
3. Queue Submission: Transactions are enqueued for processing by the
   scheduler thread
4. Dual-Queue Processing: The scheduler thread manages two distinct queues:
   • External Transaction Queue: Populated by client requests
   • Internal Priority Queue: Contains transactions blocked by account lock
     conflicts
5. Lock Management: The scheduler maintains an in-memory account lock
   database supporting both exclusive and shared access patterns
6. Work Distribution: Transactions are dispatched to available SVM worker
   threads with pre-acquired account locks
7. Lock Release: SVM workers release account locks upon completion and
   signal availability to the scheduler
8. Queue Reevaluation: When workers complete execution, their associated
   priority queues are reevaluated for immediate execution or redistribution

This architecture enables optimal parallelization while preserving transaction
ordering semantics where possible.

Account Lock Implementation

Lock Primitive

The core synchronization primitive utilizes an atomic 32-bit integer wrapped in an Arc:

type AccountLock = Arc<AtomicU32>;

Bit Field Layout

The 32-bit integer employs the following bit field structure:

+------------------------------------------------------------------------------+
| write lock (1 bit) | read lock (7 bits) | SVM ID (8 bits) | TXN ID (16 bits) |
+------------------------------------------------------------------------------+

Field Specifications

• Write Lock (1 bit): Boolean flag indicating exclusive write lock status
• Read Lock (7 bits): Counter tracking concurrent read lock holders (max 127)
• SVM Worker ID (8 bits): Identifier of the worker holding the write lock
  or last read lock acquirer (supports up to 256 workers)
• Transaction ID (16 bits): Wrapping counter identifying transactions with
  pending lock acquisition requests

This design implements a reader-writer lock with additional metadata to
facilitate efficient scheduling decisions.

Lock Acquisition Protocol

• Acquisition: Performed atomically by the scheduler thread
• Release: Executed by SVM worker threads upon transaction completion and
  AccountsDB updates

Fairness and Front-Running Prevention

Transaction Ordering Fairness

The lock mechanism implements fairness guarantees through transaction ID registration:

• Write Lock Requests: Set the transaction ID field to prevent additional
  read lock acquisitions
• Read Lock Requests: Register transaction ID during active write locks to
  prevent newer write lock acquisitions

Controlled Front-Running

To maximize throughput while preventing starvation, the system allows limited read transaction front-running:

struct AccountLockWithMeta {
    lock: AccountLock,
    front_runs: u8,
}

Front-Running Control Mechanism

• Counter Increment: The front_runs counter increments with each
  front-running event
• Threshold Enforcement: Upon reaching the configured limit, waiting write
  transactions block all subsequent readers
• Counter Reset: Occurs upon successful write lock acquisition

Priority Fee Mechanism

Transactions blocked by account locks are inserted into priority queues ordered
by the included priority fees, enabling higher-fee transactions to front-run
lower-fee transactions operating on the same accounts.

Inter-Thread Communication

The scheduler employs the Actor pattern with isolated state management,
communicating exclusively through message-passing channels:

Channel Architecture

1. Transaction Ingress Channel: RPC handlers → Scheduler

   • Carries transactions requiring scheduling decisions

2. Work Distribution Channel: Scheduler → SVM Workers

   • Transmits transactions with pre-acquired account locks for execution or
     simulation

3. Worker Availability Channel: SVM Workers → Scheduler

   • Signals worker readiness and triggers scheduling evaluation

This design eliminates shared mutable state except for the atomic account lock
integers, reducing synchronization overhead and improving cache locality.

Internal Priority Queue Structure

The internal priority queue maintains per-worker transaction queues for blocked
transactions:

+-------------------------------------------+
| SVM1 | TXN1 | TXN13 | TXN15  | ...        |
+-------------------------------------------+
| SVM2 | TXN2 | TXN3  | TXN7   | TXN10 | .. |
+-------------------------------------------+
| SVM3 | TXN4 | TXN5  | TXN6   | TXN11 | .. |
+-------------------------------------------+
| SVM4 | TXN4 |   ..                        |
+-------------------------------------------+

Queue Management

• Association: Each queue associates with an SVM worker currently holding blocking locks
• Reevaluation: Upon worker completion, associated queues undergo reevaluation
• Redistribution: Transactions may migrate between worker queues based on current lock availability

Performance Characteristics

Scalability

• Linear Scaling: Near-linear performance scaling with CPU core count under low-contention workloads
• Contention Handling: Graceful degradation under high account lock contention scenarios

Throughput Optimization

• Lock-Free Fast Path: Signature verification and account validation occur without lock acquisition
• Work Stealing: Dynamic load balancing through priority queue redistribution