Решение для матчинга ордеров в 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

Материал опубликован пользователем. Нажмите кнопку «Написать», чтобы поделиться мнением или рассказать о своём проекте.

Написать
{ "author_name": "Юлия Прокопенко", "author_type": "self", "tags": [], "comments": 0, "likes": 1, "favorites": 0, "is_advertisement": false, "subsite_label": "crypto", "id": 68580, "is_wide": false, "is_ugc": true, "date": "Wed, 22 May 2019 15:56:04 +0300" }
{ "id": 68580, "author_id": 276570, "diff_limit": 1000, "urls": {"diff":"\/comments\/68580\/get","add":"\/comments\/68580\/add","edit":"\/comments\/edit","remove":"\/admin\/comments\/remove","pin":"\/admin\/comments\/pin","get4edit":"\/comments\/get4edit","complain":"\/comments\/complain","load_more":"\/comments\/loading\/68580"}, "attach_limit": 2, "max_comment_text_length": 5000, "subsite_id": 199126, "last_count_and_date": null }

Комментариев нет 0 комм.

Популярные

По порядку

0
{ "page_type": "article" }

Прямой эфир

[ { "id": 1, "label": "100%×150_Branding_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox_method": "createAdaptive", "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "ezfl" } } }, { "id": 2, "label": "1200х400", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "ezfn" } } }, { "id": 3, "label": "240х200 _ТГБ_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fizc" } } }, { "id": 4, "label": "240х200_mobile", "provider": "adfox", "adaptive": [ "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "flbq" } } }, { "id": 5, "label": "300x500_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "ezfk" } } }, { "id": 6, "label": "1180х250_Interpool_баннер над комментариями_Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "bugf", "p2": "ffyh" } } }, { "id": 7, "label": "Article Footer 100%_desktop_mobile", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fjxb" } } }, { "id": 8, "label": "Fullscreen Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fjoh" } } }, { "id": 9, "label": "Fullscreen Mobile", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fjog" } } }, { "id": 10, "disable": true, "label": "Native Partner Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyb" } } }, { "id": 11, "disable": true, "label": "Native Partner Mobile", "provider": "adfox", "adaptive": [ "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyc" } } }, { "id": 12, "label": "Кнопка в шапке", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "p1": "bscsh", "p2": "fdhx" } } }, { "id": 13, "label": "DM InPage Video PartnerCode", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox_method": "createAdaptive", "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "bugf", "p2": "flvn" } } }, { "id": 14, "label": "Yandex context video banner", "provider": "yandex", "yandex": { "block_id": "VI-223676-0", "render_to": "inpage_VI-223676-0-1104503429", "adfox_url": "//ads.adfox.ru/228129/getCode?pp=h&ps=bugf&p2=fpjw&puid1=&puid2=&puid3=&puid4=&puid8=&puid9=&puid10=&puid21=&puid22=&puid31=&puid32=&puid33=&fmt=1&dl={REFERER}&pr=" } }, { "id": 15, "label": "Плашка на главной", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "p1": "byudx", "p2": "ftjf" } } }, { "id": 16, "label": "Кнопка в шапке мобайл", "provider": "adfox", "adaptive": [ "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "p1": "byzqf", "p2": "ftwx" } } }, { "id": 17, "label": "Stratum Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fzvb" } } }, { "id": 18, "label": "Stratum Mobile", "provider": "adfox", "adaptive": [ "tablet", "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "bugf", "p2": "fzvc" } } }, { "id": 19, "label": "Тизер на главной", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "p1": "cbltd", "p2": "gazs" } } } ]
Команда калифорнийского проекта
оказалась нейронной сетью
Подписаться на push-уведомления
{ "page_type": "default" }