Javaでシンプルな注文マッチングアルゴリズムを実装する

取引市場において、マッチング取引アルゴリズムは各注文が約定するための中核メカニズムです。売買双方が注文を出すたびに、システムは価格優先、時間優先のルールに基づいて自動的にマッチングして約定させます。ベテランの株式投資家にとって、これらのルールはおなじみですが、開発者の観点から見ると、効率的で再利用可能なマッチングエンジンを設計することは依然として課題です。本稿では、技術実装の観点から、Javaを使って簡略化したマッチング取引アルゴリズムを構築する方法を解説します。

売買板の設計方針

マッチングエンジンの中核は注文板（OrderBook）であり、買い板と売り板という2つのキューを管理します。買い板は価格の高い順に並べ、最も高い価格を提示した買い注文が優先的に約定するようにします。売り板は価格の低い順に並べ、最も低い価格を提示した売り注文が優先的に約定するようにします。

取引市場では、買い1価格が売り1価格以上になることは決してありません。そうでなければ、約定すべき注文をシステムが取りこぼしていることを意味します。同一価格の注文が複数ある場合は、時間順に約定します——今回の実装では、作成時刻を直接使うのではなく、グローバルに一意なsequenceIdによって並び順と処理順序を保証します。

多くの人は注文の格納にList<Order>を使うことを考えるでしょう。しかし、高頻度取引の環境では、注文の挿入と削除のコストが高すぎる（O(N)）ため、効率を保証するのが困難です。より良い方法は、JavaのTreeMapのような平衡木構造を使うことです。これにより、挿入、削除、検索操作の時間計算量をO(logN)に維持できます。

public record OrderKey(long sequenceId, BigDecimal price) { }

買い板と売り板では並び順のルールが異なるため、TreeMapには異なる2つのコンパレータを用意する必要があります。

private static final Comparator<OrderKey> SORT_SELL = (o1, o2) -> {
    int cmp = o1.price().compareTo(o2.price()); // 価格の低いものを先に
    return cmp == 0 ? Long.compare(o1.sequenceId(), o2.sequenceId()) : cmp;
};

private static final Comparator<OrderKey> SORT_BUY = (o1, o2) -> {
    int cmp = o2.price().compareTo(o1.price()); // 価格の高いものを先に
    return cmp == 0 ? Long.compare(o1.sequenceId(), o2.sequenceId()) : cmp;
};

比較器があれば、OrderBook の実装は非常に簡単です：

public class OrderBook {
    public final Direction direction;
    public final TreeMap<OrderKey, OrderEntity> book;

    public OrderBook(Direction direction) {
        this.direction = direction;
        this.book = new TreeMap<>(direction == Direction.BUY ? SORT_BUY : SORT_SELL);
    }

    public OrderEntity getFirst() {
        return this.book.isEmpty() ? null : this.book.firstEntry().getValue();
    }

    public boolean remove(OrderEntity order) {
        return this.book.remove(new OrderKey(order.sequenceId, order.price)) != null;
    }

    public boolean add(OrderEntity order) {
        return this.book.put(new OrderKey(order.sequenceId, order.price), order) == null;
    }
}

ヒント：Java で BigDecimal の値を比較する場合は、必ず compareTo() を使用し、equals() は使用しないでください。そうしないと、1.2 と 1.20 は等しくないと判定されます。

注文照合エンジンのコアロジック

買い注文板と売り注文板があれば、照合エンジンを実装できます。主要なデータ構造は次のとおりです：

public class MatchEngine {
    public final OrderBook buyBook = new OrderBook(Direction.BUY);
    public final OrderBook sellBook = new OrderBook(Direction.SELL);
    public BigDecimal marketPrice = BigDecimal.ZERO;
    private long sequenceId;

    public MatchResult processOrder(long sequenceId, OrderEntity order) {
        switch (order.direction) {
            case BUY:
                return processOrder(order, this.sellBook, this.buyBook);
            case SELL:
                return processOrder(order, this.buyBook, this.sellBook);
            default:
                throw new IllegalArgumentException(“方向が無効です。”);
        }
    }
}

注文を処理する際、買い注文の場合は売り注文板とのマッチングを試み、売り注文の場合は買い注文板とのマッチングを試みます。新しい注文をTaker、すでに板に出されている注文をメイカーと呼びます。テイカーが全量約定しなかった場合は、メイカーに変わって注文板に並びます。

MatchResult processOrder(OrderEntity takerOrder, OrderBook makerBook, OrderBook anotherBook) {
    long ts = takerOrder.createdAt;
    MatchResult matchResult = new MatchResult(takerOrder);
    BigDecimal takerUnfilledQuantity = takerOrder.quantity;

    for (;;) {
        OrderEntity makerOrder = makerBook.getFirst();
        if (makerOrder == null) break;

        if ((takerOrder.direction == Direction.BUY && takerOrder.price.compareTo(makerOrder.price) < 0) ||
            (takerOrder.direction == Direction.SELL && takerOrder.price.compareTo(makerOrder.price) > 0)) {
            break;
        }

        this.marketPrice = makerOrder.price;
        BigDecimal matchedQuantity = takerUnfilledQuantity.min(makerOrder.unfilledQuantity);
        matchResult.add(makerOrder.price, matchedQuantity, makerOrder);

        takerUnfilledQuantity = takerUnfilledQuantity.subtract(matchedQuantity);
        BigDecimal makerUnfilledQuantity = makerOrder.unfilledQuantity.subtract(matchedQuantity);

        if (makerUnfilledQuantity.signum() == 0) {
            makerOrder.updateOrder(makerUnfilledQuantity, OrderStatus.FULLY_FILLED, ts);
            makerBook.remove(makerOrder);
        } else {
            makerOrder.updateOrder(makerUnfilledQuantity, OrderStatus.PARTIAL_FILLED, ts);
        }

        if (takerUnfilledQuantity.signum() == 0) {
            takerOrder.updateOrder(takerUnfilledQuantity, OrderStatus.FULLY_FILLED, ts);
            break;
        }
    }

    if (takerUnfilledQuantity.signum() > 0) {
        takerOrder.updateOrder(takerUnfilledQuantity,
            takerUnfilledQuantity.compareTo(takerOrder.quantity) == 0 ? OrderStatus.PENDING : OrderStatus.PARTIAL_FILLED,
            ts);
        anotherBook.add(takerOrder);
    }

    return matchResult;
}

MatchResultには今回のTaker注文およびすべての約定記録が記録され、清算システムによる決済に便利です。

複数の取引ペアに対応

1つのエンジンインスタンスで処理できる取引ペアは1つだけです。同じシステムで複数の取引ペアをサポートしたい場合は、エンジングループを使用して管理できます：

class MatchEngineGroup {
    Map<Long, MatchEngine> engines = new HashMap<>();

    public MatchResult processOrder(long sequenceId, OrderEntity order) {
        Long symbolId = order.symbolId;
        MatchEngine engine = engines.get(symbolId);
        if (engine == null) {
            engine = new MatchEngine();
            engines.put(symbolId, engine);
        }
        return engine.processOrder(sequenceId, order);
    }
}

各注文に symbolId 属性を追加すれば、対応する取引ペアのエンジンインスタンスにルーティングされ、システム内部の分離が維持されます。

実例

次のような注文をマッチングエンジンに入力するとします：

方向価格数量buy2082.341売り2087.62買い2087.81買い2085.015売り2088.023売り2087.606買い2081.117買い2086.03買い2088.331売り2086.542売り2086.555買い2086.553

マッチング完了後、買い注文と売り注文は自動的に更新され、市場の最新約定価格もそれに伴って変化し、システムの内部状態は完全に再現可能です。すべての約定は価格優先、時間優先の原則に厳密に従い、マッチングプロセス全体が明確かつ効率的です。