Решение для матчинга ордеров в EOSIO

Сегодня мы рассмотрим решение реализации матчинга ордеров.

Что такое матчинг ордеров? Когда пользователь хочет совершить сделку, создается ордер, который сопоставляется с уже размещенными ордерами и начинает их выкупать. Начиная от самого выгодного, заканчивая самым невыгодным до тех пор, пока деньги в этом ордере или другие ордера не закончатся.

Вот как список ордеров выглядит на binance:

Красные ордера на продажу, зеленые на покупку. Чем ближе они к середине общего списка, тем выгоднее.

Матчинг ордеров можно реализовать как ончейн, так и оффчейн. Сначала была попытка реализовать ончейн решение. Несмотря на то, что в конце концов мы отказались от него в пользу оффчейн решения, будет полезно разобрать его тоже.

Сначала нам нужно отсортировать список всех ордеров по цене, а потом по дате создания. Мы можем хранить ордера на продажу и на покупку в разных таблицах, а потом при создании нового ордера подставлять его в нужное место. Но проблема в том, что eosio::multi_index, который основан на boost::multi_index, не гарантирует сохранность порядка хранимых данных и сам сортирует их так, как ему удобнее. Можно хранить в таблице два отсортированных массива, хранящих ID каждого ордера. Для дополнительной оптимизации мы разделим ордера по скоупам <symbol1+contract1>+<symbol2+contract2>, например, EOSeosio.tokenFOOfoo.token. Читается сложно, но система без труда сможет работать с этой записью. Теперь у нас есть таблица с описанием всех пар, которые есть на бирже, если пара не существует, она создается автоматически при создании ордера.

Важно! EOSeosio.tokenFOOfoo.token != FOOfoo.tokenEOSeosio.token.

Остается еще одна нерешенная проблема: при увеличении количества ордеров, увеличивается время на их обработку, а на выполнение транзакции EOS ставит ограничение в 30 мс. Тут появляется необходимость просчитать алгоритмическую сложность и оптимизировать процесс, чтобы иметь возможность обработать наибольшее количество ордеров. Для этого попробуем разобраться с neworder и trade.

Начнем с neworder. Список ID ордеров мы храним в std::vector<uint64_t>. Чтобы отсортировать массив, используем упрощенную сортировку вставками. Так как данные будут поступать постепенно, нам надо просто проходиться по массиву, находить место нового ордера и вставлять ID. В лучшем случае, когда самый выгодный ордер стоит в начале поиска, сложность составляет O(1), в худшем O(n).

Вставка в конец или удаление элементов в конце имеет O(1) сложность. В середине O(n-k), где k - это расстояние между позицией и концом вектора. Внимательный читатель увидит, что при таком раскладе массивы будут сортироваться справа налево (с конца в начало), где справа самый выгодный ордер.

При трейде просто проходимся справа налево по вышеописанному массиву и выкупаем ордера, пока деньги или ордера в списке не закончатся.

Главной причиной отказа от этого варианта решения послужила сложность точных измерений по CPU. EOS не предоставляет инструментов или функций для его измерения. Единственный способ - пушить транзакции и выявлять среднее значение. Для этого был использован локальный тестнет и Jungle testnet, который приближен к EOS. Была попытка измерить отдельные части алгоритма и весь алгоритм в целом, но цифры сильно разнились друг от друга. Нельзя было выявить более менее точных закономерностей и цифр, т.к. погрешность между несколькими запусками с одинаковыми данными могла составить от пару сотен до пару тысяч микросекунд.

Теперь об оффчейн решении, оно в разы проще. Сервер через demux слушает все события в бирже, дублирует у себя список ордеров и самостоятельно матчит. После чего готовит транзакцию с ID ордеров и передает её пользователю на подпись.

Влияет ли этот подход на централизацию биржи? Нет. С ней все также можно взаимодействовать. Единственный нюанс, что таким образом можно выкупить любой ордер, а не только самый выгодный с конца. Также для взаимодействия с конкретным ордером необходимо знать его ID, но эту информацию можно легко взять из таблиц.

Автор: Александр Молина,

Редактор: Юлия Прокопенко,

компания Genesix