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

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

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

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

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

Сначала нам нужно отсортировать список всех заказов по цене, а затем по дате создания. Мы можем хранить заказы на продажу и покупку в разных таблицах, а потом при создании нового заказа подставлять его в нужное место. Но проблема в том, что eosio::multi_index, основанный на boost::multi_index, не гарантирует сохранность порядка хранимых данных и сортирует их сам по себе для него удобнее. Мы можем хранить в таблице два отсортированных массива, в которых хранится идентификатор каждого заказа. Для дополнительной оптимизации разделим ордера по областям ‹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, которая близка к EOS. Была попытка измерить отдельные части алгоритма и весь алгоритм в целом, но цифры сильно отличались друг от друга. Выявить более-менее точные закономерности и цифры было невозможно, потому что погрешность между несколькими запусками с одними и теми же данными могла составлять от пары сотен до пары тысяч микросекунд.

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

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

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

Компания Генесикс