Основы HFT: из чего складывается задержка

Весь предыдущий блок мы строили то, что торгует в цепи, где один блок это секунды. Теперь уходим туда, где счёт идёт на наносекунды, и первое, что придётся сделать, это перестать говорить «быстро». В HFT нет быстрого кода, есть бюджет времени, разложенный по участкам, и у каждого участка своя цена сокращения. Пока бюджета нет, любая оптимизация это гадание.

Что такое HFT и чего в нём нет

Высокочастотная торговля это не «торговля часто». Частота тут следствие, а не цель. Определяющих признаков три, и все три про инженерию:

Решение принимается автоматически и без человека в контуре. Человек задаёт правила и границы риска, дальше цикл замкнут внутри программы. Человек не успевает физически: пока он моргнул, прошло сто тысяч событий.

Позиция держится коротко. От долей секунды до минут. Прибыль на сделку крошечная, иногда доли тика, а зарабатывает она на количестве сделок. Отсюда требование к издержкам: комиссия и проскальзывание съедают такую стратегию мгновенно.

Скорость это часть стратегии, а не деталь реализации. Если стратегия работает одинаково при задержке в микросекунду и в миллисекунду, это не HFT, а просто автоматическая торговля, и слава богу: жить там сильно легче.

Теперь чего в HFT нет. Это не предсказание цены на завтра: горизонт слишком короткий, и в нём работают не новости, а поток заявок. Это не «печатный станок»: доля прибыльных дней высокая, но маржа на сделку такая, что любой сбой в риске съедает месяц. И это не что-то принципиально новое: маркетмейкер в биржевой яме занимался ровно тем же, только его преимуществом было физическое место у столба, а не место в стойке.

Откуда берётся прибыль

Три источника, и они устроены по-разному.

Плата за мгновенность. Маркетмейкер стоит по обе стороны и даёт другим возможность купить или продать прямо сейчас. За это он получает спред. Мы считали это в уроке 44: спред это не жадность, а плата за право не ждать. Риск маркетмейкера в том, что кто-то знает больше него, и об этом ниже.

Связанные инструменты. Фьючерс на индекс и корзина акций этого индекса связаны арифметикой. Если одно уехало, а второе ещё нет, между ними есть разница, и она живёт ровно столько, сколько нужно самому быстрому, чтобы её забрать. Это тот же арбитраж, что между двумя пулами, только вместо блокчейна две площадки и провод между ними.

Опережение по данным. Одна и та же цена появляется на разных площадках не одновременно. Тот, кто увидел её на первой площадке и успел до второй, торгует по цене, которой уже нет. Это самый спорный источник: технически это работа с публичными данными, экономически это налог на тех, кто медленнее.

Кто платит. В первом случае платит тот, кому нужна мгновенность, и он получает за свои деньги реальную услугу. Во втором и третьем платит тот, кто медленнее, и никакой услуги не получает. Разговор о том, где проходит граница между полезным и паразитическим, идёт в индустрии двадцать лет и не закончен. Наше дело как инженеров понимать, что именно мы строим, и не путать одно с другим.

Бюджет tick-to-trade

Путь от того, как биржа положила байт в провод, до того, как наша заявка вернулась к ней обратно, называется tick-to-trade. Это единственное число, которое имеет смысл оптимизировать, и оно складывается из участков.

Опишем бюджет типом, а не комментарием. Тогда его можно считать, а не обсуждать:

/// Наносекунды. Отдельный тип, чтобы не путать их с микросекундами.
pub type Nanos = u64;

/// Участок пути сигнала: имя, задержка и то, чем её можно сократить.
pub struct Stage {
    pub name: &'static str,
    pub nanos: Nanos,
    pub lever: Lever,
}

/// Способ сократить участок. Порядок вариантов это порядок стоимости:
/// сначала то, что делается кодом, потом то, что делается деньгами.
#[derive(Clone, Copy, PartialEq, Eq)]
pub enum Lever {
    /// Переписать код: убрать аллокации, кэш-промахи, ветвления.
    Code,
    /// Настроить машину и ядро: изоляция ядер, huge pages, отключение прерываний.
    Kernel,
    /// Обойти ядро: сетевой стек в пользовательском пространстве.
    Bypass,
    /// Перенести логику в железо: FPGA, сетевая карта с отбором пакетов.
    Hardware,
    /// Сократить расстояние: колокация, кросс-коннект, прямой канал.
    Distance,
    /// Не сокращается: чужая сторона, ждём и учитываем.
    None,
}

Типовой бюджет софтового движка, который уже стоит в стойке биржи, но ещё ничем не оптимизирован:

Участок	Наносекунд	Чем лечится
провод до нашей стойки	250	расстояние
сетевая карта и ядро на приём	4000	обход ядра
разбор пакета фида	300	код
обновление стакана	400	код
решение стратегии	900	код
проверка риска	200	код
сборка заявки и ядро на отправку	3500	обход ядра
провод обратно	250	расстояние
итого	9800

Смотри на распределение, а не на сумму. Весь наш код это 1800 наносекунд из 9800, то есть меньше пятой части. Ядро операционной системы съедает 7500, три четверти бюджета.

impl LatencyBudget {
    /// Сколько времени скрыто за одним способом ускорения.
    /// Отвечает на вопрос «что даст обход ядра» до того, как мы его внедрили.
    pub fn by_lever(&self, lever: Lever) -> Nanos {
        self.stages
            .iter()
            .filter(|stage| stage.lever == lever)
            .map(|stage| stage.nanos)
            .sum()
    }

    /// Применить ускорение: участки с этим рычагом становятся быстрее
    /// в `factor` раз. Так проверяется гипотеза до того, как за неё заплатили.
    pub fn optimize(&self, lever: Lever, factor: f64) -> Self {
        let stages = self
            .stages
            .iter()
            .map(|stage| Stage {
                name: stage.name,
                nanos: if stage.lever == lever {
                    (stage.nanos as f64 / factor).round() as Nanos
                } else {
                    stage.nanos
                },
                lever: stage.lever,
            })
            .collect();
        Self { stages }
    }
}

Это закон Амдала в его исходном виде: ускорение системы ограничено долей той части, которую ты ускоряешь. Переписать разбор пакета так, чтобы он летал в десять раз быстрее, звучит как достижение, а даёт 270 наносекунд из 9800, меньше трёх процентов. Обход ядра при том же множителе даёт почти семь микросекунд.

Покрути бюджет руками. Включи ускорения по одному и в разных сочетаниях:

Обрати внимание на важное: выигрыш от правки кода зависит от того, что ты сделал до неё. В исходном бюджете код почти не виден, а после обхода ядра он становится главным участком, и та же самая правка вдруг начинает окупаться. Порядок работ важнее самих работ.

Почему смотрят на хвост, а не на среднее

Возьми движок, который обрабатывает событие за 400 наносекунд. Раз в пятьсот событий планировщик отбирает у него ядро, или срабатывает сборка мусора в соседнем процессе, или страница памяти уезжает в своп, и обработка занимает треть миллисекунды. Это две десятых процента случаев.

Среднее почти не изменится. А деньги потеряются именно в эти две десятых процента, потому что заявка, опоздавшая на треть миллисекунды, не опоздала «немножко»: она опоздала совсем, сделка уже ушла к другому.

Поэтому измеряют квантили. И измеряют их так, чтобы само измерение не стало источником задержки: гистограмма с логарифмическими корзинами делает запись за несколько операций, без аллокаций и без сортировки.

/// Корзин хватает на диапазон примерно от наносекунды до девяти секунд.
const BUCKETS: usize = 64;

pub struct Histogram {
    buckets: Vec<u64>,
    count: u64,
    sum: u128,
    max: Nanos,
    min: Nanos,
}

impl Histogram {
    /// Номер корзины: степень двойки, в которую попадает значение.
    /// Одна инструкция процессора, никаких сравнений в цикле.
    fn bucket_of(value: Nanos) -> usize {
        if value == 0 {
            0
        } else {
            (Nanos::BITS - value.leading_zeros()) as usize
        }
    }

    /// Записать замер. Это и есть весь горячий путь измерения.
    pub fn record(&mut self, value: Nanos) {
        let index = Self::bucket_of(value).min(BUCKETS - 1);
        self.buckets[index] += 1;
        self.count += 1;
        self.sum += value as u128;
        self.max = self.max.max(value);
        self.min = self.min.min(value);
    }

    /// Квантиль по корзинам: нижняя граница корзины, в которой лежит
    /// нужный по счёту замер. Ответ огрубляется, но никогда не врёт
    /// в сторону «у нас быстрее, чем на самом деле».
    pub fn quantile(&self, q: f64) -> Nanos {
        if self.count == 0 {
            return 0;
        }
        let target = (self.count as f64 * q).ceil().max(1.0) as u64;
        let mut seen = 0;
        for (index, &hits) in self.buckets.iter().enumerate() {
            seen += hits;
            if seen >= target {
                return Self::bucket_low(index);
            }
        }
        Self::bucket_low(BUCKETS - 1)
    }
}

Точность падает с ростом значения, и это ровно то, что нужно. Разница между 300 и 310 наносекундами важна. Разница между 30 и 31 миллисекундой не важна: обе означают «мы опоздали».

Вот что даёт этот код на сто тысячах замеров с описанным выше поведением:

Метрика	Значение
среднее	1448 нс
медиана	512 нс
p99	512 нс
p99.9	262144 нс
максимум	300000 нс

Среднее и p99 говорят одно и то же и оба врут. p99.9 говорит правду.