Taming State Management in Market Ranking: Three Approaches

When implementing complex algorithms like QuickSelect for market ranking, managing state correctly is crucial. We recently encountered a bug where partition arrays were being reset unexpectedly. Let's explore three different approaches to prevent such issues.

The Problem

Our QuickSelect implementation for market ranking had a subtle bug where partition arrays were being reset during comparisons:

// Bug manifestation
[34/73] Sizes: better=5, equal=1, worse=11
[35/73] undefined vs MFERUSDT -> undefined (undefined)
[36/73] Sizes: better=5, equal=1, worse=11

The root cause? Mixing mutable and immutable patterns in state management. Let's explore three solutions.

1. Full Immutable State Pattern

The core idea is to make state changes explicit and predictable by making state immutable.

// Before: Mutable state
interface QuickSelectState {
  currentPartition: {
    pivot: string;
    better: string[];
    worse: string[];
    equal: string[];
  };
}

// After: Immutable state
interface QuickSelectState {
  readonly currentPartition: {
    readonly pivot: string;
    readonly better: ReadonlyArray<string>;
    readonly worse: ReadonlyArray<string>;
    readonly equal: ReadonlyArray<string>;
  };
}

// State updates with Immer
import produce from 'immer';

function updatePartition(
  state: QuickSelectState,
  market: string,
  bucket: 'better' | 'worse' | 'equal',
): QuickSelectState {
  return produce(state, (draft) => {
    draft.currentPartition[bucket].push(market);
    draft.statsObj.comparisonsDone++;
  });
}

Testing

describe('Immutable QuickSelect', () => {
  it('preserves previous state after update', () => {
    const originalState = createState(['BTC', 'ETH']);
    const newState = updatePartition(originalState, 'BTC', 'better');

    expect(originalState.currentPartition.better).toHaveLength(0);
    expect(newState.currentPartition.better).toHaveLength(1);
  });
});

Debugging

• Each state change creates new object - perfect for time-travel debugging
• Easy to compare states with deep equality
• State snapshots are naturally isolated

2. State Machine with XState

Modeling the QuickSelect algorithm as a state machine makes transitions explicit and enforces invariants.

import { createMachine, assign } from 'xstate';

const quickSelectMachine = createMachine({
  id: 'quickselect',
  initial: 'init',
  context: {
    partition: { better: [], worse: [], equal: [], pivot: '' },
    progress: { compareIndex: 0, unsortedMarket: [] },
  },
  states: {
    init: {
      on: {
        START_PARTITION: {
          target: 'partitioning',
          actions: assign({
            partition: (context, event) => ({
              ...context.partition,
              pivot: selectPivot(context.progress.unsortedMarket),
            }),
          }),
        },
      },
    },
    partitioning: {
      on: {
        COMPARE: {
          actions: assign({
            partition: (context, event) =>
              updatePartitionWithValidation(
                context.partition,
                event.market,
                event.bucket,
              ),
          }),
        },
        PARTITION_DONE: 'recursing',
      },
    },
    recursing: {
      // State transitions for recursion phase
      on: {
        SWITCH_SUBRANGE: {
          target: 'partitioning',
          actions: assign({
            progress: (context, event) => ({
              compareIndex: 0,
              unsortedMarket: event.subrange,
            }),
          }),
        },
      },
    },
  },
});

Testing

test('state machine transitions', () => {
  const machine = interpret(quickSelectMachine);

  machine.onTransition((state) => {
    // Validate invariants after each transition
    const total =
      state.context.partition.better.length +
      state.context.partition.equal.length +
      state.context.partition.worse.length;
    expect(total).toBeLessThanOrEqual(
      state.context.progress.unsortedMarket.length,
    );
  });
});

Debugging

• Visual state charts with XState DevTools
• Every transition is traceable
• State invariants checked automatically
• Clear visualization of algorithm flow

3. Event Sourcing

Instead of mutating state directly, we record every change as an event and rebuild state from events.

// Events
type RankingEvent =
  | { type: 'PARTITION_STARTED'; pivot: string }
  | {
      type: 'MARKET_COMPARED';
      market: string;
      winner: string;
      bucket: 'better' | 'worse' | 'equal';
    }
  | { type: 'PARTITION_REBALANCED'; newPivot: string }
  | { type: 'RECURSION_STARTED'; subrange: string[] };

// Event Store
class RankingEventStore {
  private events: RankingEvent[] = [];

  append(event: RankingEvent) {
    this.events.push(event);
    this.persist(event); // Save to DB/Gist
  }

  rebuild(): QuickSelectState {
    return this.events.reduce(applyEvent, initialState);
  }
}

// State projection
function applyEvent(
  state: QuickSelectState,
  event: RankingEvent,
): QuickSelectState {
  switch (event.type) {
    case 'MARKET_COMPARED':
      return {
        ...state,
        currentPartition: {
          ...state.currentPartition,
          [event.bucket]: [
            ...state.currentPartition[event.bucket],
            event.market,
          ],
        },
      };
    // ... other events
  }
}

Testing

test('event sourcing', () => {
  const store = new RankingEventStore();

  // Record events
  store.append({ type: 'PARTITION_STARTED', pivot: 'BTC' });
  store.append({
    type: 'MARKET_COMPARED',
    market: 'ETH',
    winner: 'ETH',
    bucket: 'better',
  });

  // Rebuild state
  const state = store.rebuild();
  expect(state.currentPartition.better).toContain('ETH');

  // Test specific sequences
  const events = store.getEvents();
  expect(events).toMatchSnapshot();
});

Debugging & Auditing

• Perfect audit trail of all decisions
• Can replay events to any point in time
• Can analyze decision patterns
• Easy to add new projections for analytics
• Great for understanding algorithm behavior

Comparison of Approaches

Immutable State

• Pros: Simple to implement, familiar pattern, good IDE support
• Cons: Can be verbose, performance overhead for large states
• Best for: better applications, quick prototypes

State Machine

• Pros: Makes invalid states impossible, self-documenting
• Cons: Initial setup complexity, learning curve
• Best for: Complex business logic, critical systems

Event Sourcing

• Pros: Perfect audit trail, great for debugging, flexible analytics
• Cons: Most complex to implement, eventual consistency
• Best for: Systems requiring audit trails, complex debugging needs

Conclusion

For our market ranking system, the State Machine approach with XState would be the optimal choice because:

1. QuickSelect has well-defined states and transitions
2. We need to enforce strict invariants
3. Visual debugging would help understand the algorithm flow
4. Testing becomes more structured and comprehensive

However, if we needed perfect audit trails of market comparisons or wanted to analyze decision patterns, Event Sourcing would be worth the extra complexity.

The key lesson? Pick ONE pattern and stick to it consistently. Mixing patterns leads to subtle bugs that are hard to track down.

Next Steps

1. Implement proper state machine for QuickSelect
2. Add visual state debugging
3. Enforce state invariants through types
4. Add comprehensive transition tests

Remember: The goal isn't just to fix the bug, but to make similar bugs impossible by design.