PatientZero 13 мар в 08:20

Уменьшаем базу данных в 2000 раз при помощи Rust

Средний

26 мин

8.7K

Rust*Администрирование баз данных*Клиентская оптимизация*Хранение данных*

Туториал

Перевод

Автор оригинала: Guillaume Endignoux

Этот проект на выходные начался с изучения репозитория открытых данных сети общественного транспорта Парижа, содержащего различные API для выполнения в реальном времени запросов отправления транспорта, изменений в графике движения и так далее. Моё внимание привлёк раздел о многократном использовании данных, потому что в нём были приведены внешние проекты, использующие эти открытые данные. В частности веб-сайт статуса сети RATP предоставляет удобный интерфейс для визуализации истории нарушений на линиях движения метро, сети экспрессов/поездов и трамваев.

Screenshot of the RATP status website — Обычный день нарушений на ratpstatus.fr.

В репозитории GitHub сайта ratpstatus.fr содержатся все файлы JSON, запрашиваемые из open-data API каждые две минуты. Данные сохраняются там уже почти год. Репозиторий с 188 тысячами коммитов и более чем 10 ГБ собранных данных всего лишь в одном последнем коммите (измерено при помощи git clone --depth=1) — это определённо интересный выбор для реализации базы данных! Уточню, что в этом посте я не собираюсь критиковать эту систему. Веб-сайт статуса сети RATP — превосходный веб-сайт, мгновенно и стабильно предоставляющий полезную информацию без обычного сегодня раздувания веб-сайтов. [И нет, сайт не написан на Rust. Веб-сайт на PHP тоже может быть невероятно быстрым!]

Тем не менее, размер базы данных (10 ГБ) заставил меня призадуматься: а можно ли сжать её лучше, потратив на это приемлемое количество времени (скажем выходные)? В этом подробном посте я расскажу, как использовал шаблон проектирования interning в Rust, чтобы сжать этот датасет в две тысячи раз! Мы посмотрим, как лучше структурировать сам интернер, как настроить схему данных для оптимальной работы с ним и как сделать так, чтобы сериализация использовала interning наилучшим образом.

Если у вас в хранилище накопилось множество файлов JSON, то вам стоит прочитать эту статью!

Импортируем данные (135%)

Первым этапом эксперимента стало импортирование исходных данных. Каждый пример данных был представлен в виде файла JSON со множеством записей такого вида:

{
  "disruptions": [
    {
      "id": "445a6032-d1ca-11ef-b3f5-0a58a9feac02",
      "applicationPeriods": [
        {
          "begin": "20250113T180000",
          "end": "20250228T230000"
        }
      ],
      "lastUpdate": "20250113T172013",
      "cause": "PERTURBATION",
      "severity": "BLOQUANTE",
      "title": "Activities in Aincourt",
      "message": "<p>Due to work in Aincourt, the Centre and Eglise stops will not be served in both directions of traffic on line 95 15 and in the direction of Magny en Vexin Gare Routière only on line 95 44. <br>From 13/01 until further notice. </p><br>Please refer to Les Cadenas stops"
    },
  ...
}

Давайте импортируем эти данные в нашу программу! Язык Rust сильно упрощает десериализацию данных из всевозможных форматов при помощи библиотек наподобие serde и serde_json. В своём манифесте Cargo.toml я реализовал зависимость от следующих версий:

[dependencies]
serde = { version = "1.0.217", features = ["derive"] }
serde_json = "1.0.137"

Благодаря этому мы можем определить схему данных как обычные struct/enum языка Rust и просто аннотировать их с помощью макроса derive Deserialize serde, чтобы автоматически реализовать для неё десериализацию. Рекомендую использовать атрибут deny_unknown_fields, чтобы неизвестные поля JSON не игнорировались молча. Эти атрибуты отдельно задокументированы на веб-сайте serde.rs (не в docs.rs).

use serde::Deserialize;

#[derive(Debug, Deserialize)]
#[serde(deny_unknown_fields)]
struct Data {
    #[serde(rename = "statusCode")]
    status_code: Option<i32>,
    error: Option<String>,
    message: Option<String>,
    disruptions: Option<Vec<Disruption>>,
    lines: Option<Vec<Line>>,
    #[serde(rename = "lastUpdatedDate")]
    last_updated_date: Option<String>,
}

Далее можно тривиальным образом десериализовать файл JSON в struct Data при помощи функций типа serde_json::from_reader().

// Открываем файл для чтения.
let file = File::open(path)?;
// Добавляем слой буферизации для повышения производительности
let reader = BufReader::new(file);
// Десериализуем содержимое JSON в Data.
let data: Data = serde_json::from_reader(reader)?;

В этой конкретной импортируемой схеме данных каждый Disruption содержит информативные поля, а также список временных промежутков, к которым они относятся. Например, на линии могут проводиться строительные работы каждый вечер в течение месяца, так что для каждого из этих вечеров будет существовать ApplicationPeriod.

#[derive(Debug, Deserialize)]
#[serde(deny_unknown_fields)]
struct Disruption {
    id: String,
    #[serde(rename = "applicationPeriods")]
    application_periods: Vec<ApplicationPeriod>,
    #[serde(rename = "lastUpdate")]
    last_update: String,
    cause: String,
    severity: String,
    tags: Option<Vec<String>>,
    title: String,
    message: String,
    disruption_id: Option<String>,
}

#[derive(Debug, Deserialize)]
#[serde(deny_unknown_fields)]
struct ApplicationPeriod {
    begin: String,
    end: String,
}

Данные также содержат индекс по Line, перечисляющий все объекты (например, станции), на которые влияют нарушения графика на каждой линии метро.

#[derive(Debug, Deserialize)]
#[serde(deny_unknown_fields)]
struct Line {
    id: String,
    name: String,
    #[serde(rename = "shortName")]
    short_name: String,
    mode: String,
    #[serde(rename = "networkId")]
    network_id: String,
    #[serde(rename = "impactedObjects")]
    impacted_objects: Vec<ImpactedObject>,
}

#[derive(Debug, Deserialize)]
#[serde(deny_unknown_fields)]
struct ImpactedObject {
    #[serde(rename = "type")]
    typ: String,
    id: String,
    name: String,
    #[serde(rename = "disruptionIds")]
    disruption_ids: Vec<String>,
}

Кроме того, я хотел оценить, какой объём памяти занимают эти объекты, чтобы выполнять бенчмаркинг улучшений, достигнутых методиками interning. Функция std::mem::size_of() Rust возвращает размер объекта в «стеке», но этого недостаточно, потому что при этом игнорируются все данные, распределённые в куче косвенно (например, через коллекцию Vec). Поэтому я определил новый трейт и реализовал его для нужных мне типов.

trait EstimateSize: Sized {
    /// Возвращает количество байтов, косвенно распределённых в куче для этого объекта.
    fn allocated_bytes(&self) -> usize;

    /// Возвращает общее количество байтов, используемое этим объектом.
    fn estimated_bytes(&self) -> usize {
        std::mem::size_of::<Self>() + self.allocated_bytes()
    }
}

impl EstimateSize for i32 {
    fn allocated_bytes(&self) -> usize {
        0  // В куче ничего не распределено.
    }
}

impl EstimateSize for String {
    fn allocated_bytes(&self) -> usize {
        self.len()  // Каждый элемент имеет длину один байт. Ёмкость строки игнорируется.
    }
}

impl<T: EstimateSize> EstimateSize for Vec<T> {
    fn allocated_bytes(&self) -> usize {
        // Рекурсивно суммируем общий размер каждого элемента.
        self.iter().map(|x| x.estimated_bytes()).sum()
    }
}

В случае составных типов (struct) реализация проверяет все поля. В принципе, это можно реализовать автоматически при помощи макроса derive (подобного Deserialize serde), но, учитывая масштаб моего эксперимента, создание нового макроса показалось мне излишней тратой времени.

impl EstimateSize for Data {
    fn allocated_bytes(&self) -> usize {
        self.status_code.allocated_bytes()
            + self.error.allocated_bytes()
            + self.message.allocated_bytes()
            + self.disruptions.allocated_bytes()
            + self.lines.allocated_bytes()
            + self.last_updated_date.allocated_bytes()
    }
}

Чтение всех файлов за май 2024 года при помощи этого кода дало мне следующие результаты: развёртывание 1,1 ГБ файлов JSON в struct внутри памяти увеличило размер на 35% (коммит d961e6e). Движемся не в том направлении… так что давайте займёмся оптимизацией!

Parsed 1137178883 bytes from 30466 files (+ 21 failed files)
Expanded to 1531039733 bytes in memory (relative size = 134.63%)

Interning

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

Строки (47%)

Первый сценарий использования interning, который приходит в голову — это строки; свидетельством тому стали самые популярные библиотеки Rust для interning. Мы не будем использовать ни один из этих пакетов, потому что я ставил себе задачу больше узнать о внутреннем устройстве interning.

Я наткнулся на пост matklad за 2020 год под названием Fast and Simple Rust Interner, и источником вдохновения для моей первой итерации стал его дизайн. Главное отличие заключается в том. что я обернул строки в Rc (обёртку с подсчётом ссылок), чтобы избежать их дублирования в памяти. Если бы интернер должен был использоваться из множества потоков, то я бы выбрал Arc, но в этом эксперименте я решил ничего не усложнять.

Что же такое интернер? По сути, это таблица строк, состоящая из вектора строк, сопряжённого с хэш-таблицей, позволяющей проверять, находится ли уже строка в базе данных, и если да, то по какому индексу в векторе.

use std::collections::HashMap;
use std::rc::Rc;

#[derive(Default)]
struct StringInternerImpl {
    vec: Vec<Rc<String>>,
    map: HashMap<Rc<String>, usize>,
}

impl StringInternerImpl {
    fn intern(&mut self, value: String) -> usize {
        if let Some(&id) = self.map.get(&value) {
            return id;
        }

        let id = self.vec.len();
        let rc: Rc<String> = Rc::new(value);
        self.vec.push(Rc::clone(&rc));
        self.map.insert(rc, id);
        id
    }

    fn lookup(&self, id: usize) -> Rc<String> {
        Rc::clone(&self.vec[id])
    }
}

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

Структура строк в памяти без interning и с ним

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

struct IString<'a> {
    interner: &'a StringInterner,
    id: usize,
}

impl<'a> IString<'a> {
    fn from(interner: &'a StringInterner, value: String) -> Self {
        let id = interner.intern(value);
        Self { interner, id }
    }

    fn lookup(&self) -> Rc<String> {
        self.interner.lookup(self.id)
    }
}

Как можно заметить, я объявил типы StringInterner и StringInternerImpl. В чём между ними разница?

Как только IString получает дескриптор интернера &StringInterner, связанный с ним StringInterner больше невозможно менять при помощи функции intern(), получающей параметр &mut self, потому что это нарушит правила алиасинга Rust: не может существовать &StringInterner и &mut StringInterner, одновременно указывающих на одно и то же. Это довольно неудобно, потому что не позволяет интернировать более одной строки!

Для разрешения этого конфликта можно воспользоваться внутренней изменяемостью, реализуемой при помощи типа RefCell. Определив StringInterner как RefCell<StringInternerImpl>, мы можем интернировать другие значения без необходимости ссылки &mut self на интернер.

#[derive(Default)]
struct StringInterner {
    inner: RefCell<StringInternerImpl>,
}

impl StringInterner {
    // Эта функция получает неизменяемую ссылку!
    fn intern(&self, value: String) -> usize {
        // Метод borrow_mut() выполняет проверки в среде исполнения и освобождает
        // изменяемую ссылку, если это безопасно (а если нет, то создаёт панику).
        self.inner.borrow_mut().intern(value)
    }

    fn lookup(&self, id: usize) -> Rc<String> {
        self.inner.borrow().lookup(id)
    }
}

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

impl PartialEq<String> for IString<'_> {
    fn eq(&self, other: &String) -> bool {
        self.lookup().deref() == other
    }
}

Также я определил новые struct для схемы данных, заменив все строки интернированными. Для этого понадобится добавлять везде срок жизни 'a, что не особо эргономично, но мы вернёмся к этому паттерну позже.

struct Disruption<'a> {
    id: IString<'a>,
    application_periods: Vec<ApplicationPeriod<'a>>,
    last_update: IString<'a>,
    cause: IString<'a>,
    severity: IString<'a>,
    tags: Option<Vec<IString<'a>>>,
    title: IString<'a>,
    message: IString<'a>,
    disruption_id: Option<IString<'a>>,
}

struct ApplicationPeriod<'a> {
    begin: IString<'a>,
    end: IString<'a>,
}

Кроме того, я определил функции для преобразования данных из исходных struct в интернированные, а также функции сравнения для валидации семантической эквивалентности интернированных данных исходным (и для проверки того, что мои бенчмарки не ошибаются).

impl<'a> ApplicationPeriod<'a> {
    fn from(interner: &'a StringInterner, source: source::ApplicationPeriod) -> Self {
        Self {
            begin: IString::from(interner, source.begin),
            end: IString::from(interner, source.end),
        }
    }
}

impl PartialEq<source::ApplicationPeriod> for ApplicationPeriod<'_> {
    fn eq(&self, other: &source::ApplicationPeriod) -> bool {
        self.begin == other.begin && self.end == other.end
    }
}

Благодаря этому мы уже можем увидеть эффективность interning: во входных данных каждая строка встречается в среднем 425 раз, данные внутри памяти занимают в три раза меньше, чем в исходном образце, и в два раза меньше, чем и исходных файлах JSON (коммит 5297faa). Но мы пока всё ещё далеко от результата, заявленного в заголовке поста!

Parsed 1137178883 bytes from 30466 files (+ 21 failed files)
Expanded to 1531039733 bytes in memory (relative size = 134.63%)
Optimized to 529308335 bytes (relative size = 46.55%)
- [0.84%] String interner: 56374 objects | 4433343 bytes (78.64 bytes/object) | 23964083 references (425.09 refs/object)

Произвольные типы (7,6%)

Дальше можно обратить внимание на то, что строки — это не единственные объекты, часто повторяющиеся во входных данных. Например, нарушение движения Disruption может длиться час, если оно неожиданное, или около месяца, если это запланированный текущий ремонт. Учитывая то, что входные данные — это временные последовательности, сэмплируемые каждые 2 минуты, стоит ожидать, что каждое нарушение будет встречаться в них многократно.

К счастью, методику interning можно использовать не только для строк: подойдут любые данные, которые можно поместить в вектор и хэш-таблицу. Поэтому мы можем использовать дженерики, чтобы interning работал для произвольных типов, реализующих Eq и Hash (для работы с хэш-таблицей).

// Псевдоним типа для удобства.
type IString<'a> = Interned<'a, String>;

struct Interned<'a, T> {
    interner: &'a Interner<T>,
    id: usize,
}

impl<'a, T: Eq + Hash> Interned<'a, T> {
    fn from(interner: &'a Interner<T>, value: T) -> Self {
        let id = interner.intern(value);
        Self { interner, id }
    }

    fn lookup(&self) -> Rc<T> {
        self.interner.lookup(self.id)
    }
}

В качестве нового требования нам также понадобится реализовать трейты PartialEq, Eq и Hash для Interned<_>, чтобы его можно было рекурсивно использовать в struct, подвергнутых интернированию. Наивная реализация будет заключатся в поиске действительных данных и их сравнении или хэшировании, но скоро мы к этому вернёмся.

use std::hash::{Hash, Hasher};

impl<T: Eq + Hash> PartialEq for Interned<'_, T> {
    fn eq(&self, other: &Self) -> bool {
        self.lookup().deref() == other.lookup().deref()
    }
}

impl<T: Eq + Hash> Eq for Interned<'_, T> {}

impl<T: Eq + Hash> Hash for Interned<'_, T> {
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher,
    {
        self.lookup().deref().hash(state)
    }
}

Что касается схемы данных, то теперь у нас есть набор интернеров: каждый тип получает собственный интернер.

#[derive(Default)]
struct Interners<'a> {
    string: Interner<String>,
    disruption: Interner<Disruption<'a>>,
    line: Interner<Line<'a>>,
    application_period: Interner<ApplicationPeriod<'a>>,
    impacted_object: Interner<ImpactedObject<'a>>,
}

struct данных в схеме теперь могут содержать интернированные версии других struct, например, Interned<'a, ApplicationPeriod<'a>> и просто порождать трейты сравнения и хэширования.

#[derive(Debug, Hash, PartialEq, Eq)]
struct Disruption<'a> {
    id: IString<'a>,
    application_periods: Vec<Interned<'a, ApplicationPeriod<'a>>>,
    last_update: IString<'a>,
    cause: IString<'a>,
    severity: IString<'a>,
    tags: Option<Vec<IString<'a>>>,
    title: IString<'a>,
    message: IString<'a>,
    disruption_id: Option<IString<'a>>,
}

Преобразование из исходных типов данных теперь использует ссылку на всю коллекцию Interners.

impl<'a> Disruption<'a> {
    fn from(interners: &'a Interners<'a>, source: source::Disruption) -> Self {
        Self {
            id: Interned::from(&interners.string, source.id),
            application_periods: source
                .application_periods
                .into_iter()
                .map(|x| {
                    Interned::from(
                        &interners.application_period,
                        ApplicationPeriod::from(interners, x),
                    )
                })
                .collect(),
            ...
        }
    }
}

Благодаря этому обобщению уменьшение размера начинает становиться существенным: данные стали примерно в шесть раз меньше, чем на предыдущем этапе, и в 12 раз меньше, чем в исходных входных файлах (коммит f532ef9).

Parsed 1137178883 bytes from 30466 files (+ 21 failed files)
Expanded to 1531039733 bytes in memory (relative size = 134.63%)
Optimized to 86349519 bytes (relative size = 7.59%)
[67.50%] Interners: 58288479 bytes
- [5.13%] String interner: 56374 objects | 4433343 bytes (78.64 bytes/object) | 23964083 references (425.09 refs/object)
- [1.81%] Disruption interner: 7550 objects | 1565896 bytes (207.40 bytes/object) | 625760 references (82.88 refs/object)
  - [0.28%] ApplicationPeriod interner: 5883 objects | 245688 bytes (41.76 bytes/object) | 631593 references (107.36 refs/object)
- [53.61%] Line interner: 97090 objects | 46289464 bytes (476.77 bytes/object) | 930026 references (9.58 refs/object)
  - [6.66%] ImpactedObject interner: 56110 objects | 5754088 bytes (102.55 bytes/object) | 3183332 references (56.73 refs/object)

Избавляемся от ссылки (2.8%)

Возможно, вы заметили, что ссылка на Interner распространяется сильно дальше, чем struct Interned. Это заставляет нас (1) везде добавлять срок жизни 'a и (2) использовать внутреннюю изменяемость, приводящую к разделению Interner/InternerImpl.

struct Interned<'a, T> {
    interner: &'a Interner<T>,
    id: usize,
}

Здесь очень важно то, что из-за большого количества дубликатов объём используемой памяти сильно увеличивается: struct наподобие Disruption<'a> содержит не менее семи ссылок на один и тот же строковый интернер! Что, если мы просто избавимся от этого?

В текущей структуре кода тип Interned интрузивен (он знает об окружающем его Interner). Вместо этого можно сделать интернер внешним и позволить вызывающей стороне при необходимости указывать ссылку на интернер.

use std::marker::PhantomData;

struct Interned<T> {
    id: usize,
    // Маркер, указывающий, что интернированный объект ведёт себя как функция,
    // возвращающая T (при помощи метода lookup).
    _phantom: PhantomData<fn() -> T>,
}

impl<T: Eq + Hash> Interned<T> {
    // Ссылку на интернер теперь передаёт вызывающая сторона.
    fn from(interner: &Interner<T>, value: T) -> Self {
        interner.intern(value)
    }

    // Здесь то же самое.
    fn lookup(&self, interner: &Interner<T>) -> Rc<T> {
        interner.lookup(self.id)
    }
}

Сложность с этим упрощённым дизайном заключается в способе реализации методов сравнения и хэширования для Interned<T>. Эти операторы имеют фиксированный API, задаваемый трейтами наподобие PartialEq, поэтому ссылку на интернер невозможно передать, например, как дополнительное значение функции eq().

Чтобы решить эту проблему, мы можем отметить, что интернированный индекс полностью представляет исходный объект (в рамках интернера): два значения могут быть интернированы к одному индексу тогда и только тогда, когда они равны. Поэтому вместо того, чтобы выполнять глубокое (рекурсивное) сравнение, мы можем просто сравнить индексы, то есть выполнить derive их реализации для Interned. Аналогично и для хэширования.

#[derive(Debug, Hash, PartialEq, Eq)]
struct Interned<T> { /* ... */ }

Однако сложности по-прежнему возникают, когда нам нужно сравнить Interned<T> с T. В этом случае нам нужно поискать исходное значение и выполнить глубокое сравнение. Для того я определил новый трейт EqWith, допускающий передачу интернера как вспомогательного объекта для сравнения.

trait EqWith<Rhs, Helper> {
    fn eq_with(&self, other: &Rhs, helper: &Helper) -> bool;
}

impl<T: Eq + Hash> EqWith<T, Interner<T>> for Interned<T> {
    fn eq_with(&self, other: &T, interner: &Interner<T>) -> bool {
        self.lookup(interner).deref() == other
    }
}

Тогда мы сможем сравнивать struct из исходной и оптимизированной схем.

#[derive(Debug, Hash, PartialEq, Eq)]
struct ApplicationPeriod {
    begin: IString,
    end: IString,
}

impl EqWith<source::ApplicationPeriod, Interners> for ApplicationPeriod {
    fn eq_with(&self, other: &source::ApplicationPeriod, interners: &Interners) -> bool {
        self.begin.eq_with(&other.begin, &interners.string)
            && self.end.eq_with(&other.end, &interners.string)
    }
}

Благодаря этому мы вдвое уменьшили размер Interned<T>, а потому практически вдвое уменьшили и общий размер в памяти (коммит 59fae78).

Parsed 1137178883 bytes from 30466 files (+ 21 failed files)
Expanded to 1531039733 bytes in memory (relative size = 134.63%)
Optimized to 49829943 bytes (relative size = 4.38%)
[68.66%] Interners: 34215191 bytes
- [8.90%] String interner: 56374 objects | 4433335 bytes (78.64 bytes/object) | 23964083 references (425.09 refs/object)
- [2.17%] Disruption interner: 7550 objects | 1081928 bytes (143.30 bytes/object) | 625760 references (82.88 refs/object)
  - [0.30%] ApplicationPeriod interner: 5883 objects | 151552 bytes (25.76 bytes/object) | 631593 references (107.36 refs/object)
- [49.71%] Line interner: 97090 objects | 24768600 bytes (255.11 bytes/object) | 930026 references (9.58 refs/object)
  - [7.59%] ImpactedObject interner: 56110 objects | 3779776 bytes (67.36 bytes/object) | 3183332 references (56.73 refs/object)

Можно ли ещё уменьшить его вдвое?

Да! В посте matklad использовался индекс u32, а не usize. Это и в самом деле достаточно разумный выбор для объектов, на которые может быть много ссылок. В данном случае датасет не содержал ни одного типа с более чем одним миллионом объектов, так что это даёт вполне приемлемый запас.

struct Interned<T> {
    id: u32,  // Теперь это 32-битный индекс.
    _phantom: PhantomData<fn() -> T>,
}

impl<T: Eq + Hash> Interner<T> {
    fn intern(&mut self, value: T) -> u32 {
        if let Some(&id) = self.map.get(&value) {
            return id;
        }

        // Проверка в среде выполнения, что идентификатор не превышает u32.
        let id = self.vec.len();
        assert!(id <= u32::MAX as usize);
        let id = id as u32;

        let rc: Rc<T> = Rc::new(value);
        self.vec.push(Rc::clone(&rc));
        self.map.insert(rc, id);
        id
    }

    fn lookup(&self, id: u32) -> Rc<T> {
        Rc::clone(&self.vec[id as usize])
    }
}

Размер уже менее 3% от размера исходного датасета (коммит 84d79e7). Стабильный прогресс!

Parsed 1137178883 bytes from 30466 files (+ 21 failed files)
Expanded to 1531039733 bytes in memory (relative size = 134.63%)
Optimized to 31391391 bytes (relative size = 2.76%)
[72.41%] Interners: 22730967 bytes
- [14.12%] String interner: 56374 objects | 4433335 bytes (78.64 bytes/object) | 23964083 references (425.09 refs/object)
- [2.48%] Disruption interner: 7550 objects | 779548 bytes (103.25 bytes/object) | 625760 references (82.88 refs/object)
  - [0.33%] ApplicationPeriod interner: 5883 objects | 104488 bytes (17.76 bytes/object) | 631593 references (107.36 refs/object)
- [45.86%] Line interner: 97090 objects | 14396532 bytes (148.28 bytes/object) | 930026 references (9.58 refs/object)
  - [9.61%] ImpactedObject interner: 56110 objects | 3017064 bytes (53.77 bytes/object) | 3183332 references (56.73 refs/object)

Настраиваем схему

Использование обобщённых техник interning — не конец нашего приключения. На самом деле мы можем использовать бизнес-знания о наших данных, чтобы ещё больше их оптимизировать.

Сортируем множества (1,5%)

В этих данных присутствует общий паттерн — поле, содержащее множество объектов (интернированных). Например, Line содержит множество объектов, хранящихся как Vec<Interned<ImpactedObject>>, а каждый ImpactedObject содержит множество ID нарушений в виде Vec<IString>.

struct Line {
    id: IString,
    name: IString,
    short_name: IString,
    mode: IString,
    network_id: IString,
    impacted_objects: Vec<Interned<ImpactedObject>>,
}

struct ImpactedObject {
    typ: IString,
    id: IString,
    name: IString,
    disruption_ids: Vec<IString>,
}

Любопытно, что с семантической точки зрения эти множества не имеют определённого порядка: нам важно только то, какие объекты относятся к линии метро, а не то, был ли объект «до» другого (что бы это ни значило). Однако в Rust тип коллекции Vec семантически упорядочен!

Это значит, что два ImpactedObject с одинаковыми полями typ, id и name, но с disruption_ids, равными [123, 42, 73] в одном случае и [73, 123, 42] в другом будут считаться разными с точки зрения хэширования и равенства, хотя семантически они одинаковы.

Оказалось, что API возвращает такие множества в произвольном порядке в разных запросах (что, я думаю, логично, если они внутри представлены в виде хэш-таблиц или множеств хэшей). То есть один объект, содержащий множество из N элементов, может быть представлен N! разными способами в JSON, которые интернер будет считать отличающимися (количество перестановок N элементов).

К сожалению, проблема накапливается: Line содержит множество ImpactedObject, которые сами содержат множества IString. Рассмотрим следующий пример: каждый из двух ImpactedObject, имеет 3!=6 возможных представлений и существует 2!=2 возможных способа упорядочивания этих двух объектов, так что эта Line имеет до 6⋅6⋅2=72 представлений. И это ещё относительно простой пример, в реальности множества могут быть длиннее, чем 3 нарушения. На практике, Interner<Line> с наибольшим количеством объектов (97090) имел размер 14 МБ, что составляло 45% от оптимизированных байтов.

Line {
    impacted_objects: vec![
        ImpactedObject {
            disruption_ids: vec![1, 2, 3], ...
        },
        ImpactedObject {
            disruption_ids: vec![4, 5, 6], ...
        },
    ],
    ...
}

// Один и тот же объект, сериализируемый разным образом.
Line {
    impacted_objects: vec![
        ImpactedObject {
            disruption_ids: vec![6, 4, 5], ...
        },
        ImpactedObject {
            disruption_ids: vec![2, 1, 3], ...
        },
    ],
    ...
}

Для устранения этой проблемы мы можем канонизировать такие множества; проще всего будет их отсортировать. Однако добавлять операторы упорядочивания (при помощи трейтов PartialOrd и Ord) ко всем структурам в схеме было бы слишком утомительно. Но это и не требуется: нам нужно упорядочить только множества Interned<T>, и это можно сделать, просто упорядочив внутренние индексы! И в самом деле: нам нужен лишь канонический порядок и нас не волнует, отражает ли этот порядок семантику объектов.

К сожалению, мы не можем выполнить derive PartialOrd для Interned<T> , если сам внутренний T его не реализует. Это известное давнее ограничение derive (ему больше десяти лет!).

use std::marker::PhantomData;

#[derive(PartialEq, Eq, PartialOrd, Ord)]
struct Interned<T> {
    id: u32,
    _phantom: PhantomData<fn() -> T>,
}

struct MyArbitraryType;

fn foo(set: &mut [Interned<MyArbitraryType>]) {
    // error[E0277]: the trait bound `MyArbitraryType: Ord` is not satisfied
    set.sort_unstable();
}

error[E0277]: the trait bound `MyArbitraryType: Ord` is not satisfied
    --> src/lib.rs:13:9
     |
13   |     set.sort_unstable();
     |         ^^^^^^^^^^^^^ the trait `Ord` is not implemented for `MyArbitraryType`
     |
     = help: the trait `Ord` is implemented for `Interned<T>`
note: required for `Interned<MyArbitraryType>` to implement `Ord`
    --> src/lib.rs:3:37
     |
3    | #[derive(PartialEq, Eq, PartialOrd, Ord)]
     |                                     ^^^ unsatisfied trait bound introduced in this `derive` macro
note: required by a bound in `core::slice::<impl [T]>::sort_unstable`
    --> /playground/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/mod.rs:2932:12
     |
2930 |     pub fn sort_unstable(&mut self)
     |            ------------- required by a bound in this associated function
2931 |     where
2932 |         T: Ord,
     |            ^^^ required by this bound in `core::slice::<impl [T]>::sort_unstable`
     = note: this error originates in the derive macro `Ord` (in Nightly builds, run with -Z macro-backtrace for more info)
help: consider annotating `MyArbitraryType` with `#[derive(Ord)]`
     |
9    + #[derive(Ord)]
10   | struct MyArbitraryType;
     |

То есть мы должны вручную реализовать для Interned<T> трейты сравнения, что не так уж страшно. Стоит отметить, что если мы реализуем PartialEq вручную, то сможем выполнять для него derive(Hash), но Clippy lint будет предупреждать о нежелательности этого.

use std::cmp::Ordering;
use std::hash::{Hash, Hasher};

impl<T> PartialEq for Interned<T> {
    fn eq(&self, other: &Self) -> bool {
        self.id.eq(&other.id)
    }
}

impl<T> Eq for Interned<T> {}

impl<T> PartialOrd for Interned<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<T> Ord for Interned<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.id.cmp(&other.id)
    }
}

impl<T> Hash for Interned<T> {
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher,
    {
        self.id.hash(state);
    }
}

Затем я решил создать абстракцию InternedSet<T>, которая будет сортировать элементы в каноническом порядке. Стоит отметить использование функции sort_unstable(), которая эффективнее обобщённой sort(). Также обратите внимание, что мы храним множество как boxed-слайс Box<[_]> вместо Vec<_>, что более компактно для неизменяемых последовательностей, поскольку не требует хранить поле ёмкости для потенциального увеличения размера вектора.

#[derive(Debug, Hash, PartialEq, Eq)]
struct InternedSet<T> {
    set: Box<[Interned<T>]>,
}

impl<T> InternedSet<T> {
    fn new(set: impl IntoIterator<Item = Interned<T>>) -> Self {
        let mut set: Box<[_]> = set.into_iter().collect();
        set.sort_unstable();
        Self { set }
    }
}

Теперь мы можем интегрировать это в схему следующим образом.

struct ImpactedObject {
    typ: IString,
    id: IString,
    name: IString,
    disruption_ids: InternedSet<String>,
}

impl ImpactedObject {
    fn from(interners: &mut Interners, source: source::ImpactedObject) -> Self {
        Self {
            typ: Interned::from(&mut interners.string, source.typ),
            id: Interned::from(&mut interners.string, source.id),
            name: Interned::from(&mut interners.string, source.name),
            disruption_ids: InternedSet::new(
                source
                    .disruption_ids
                    .into_iter()
                    .map(|x| Interned::from(&mut interners.string, x)),
            ),
        }
    }
}

Это изменение разделило количество уникальных объектов Line на 14 и снова суммарно оптимизировало код вдвое (коммит bdb00b5).

Parsed 1137178883 bytes from 30466 files (+ 21 failed files)
Expanded to 1531039733 bytes in memory (relative size = 134.63%)
Optimized to 16578863 bytes (relative size = 1.46%)
[50.70%] Interners: 8405895 bytes
- [26.74%] String interner: 56374 objects | 4433335 bytes (78.64 bytes/object) | 23964083 references (425.09 refs/object)
- [3.97%] Disruption interner: 7550 objects | 658748 bytes (87.25 bytes/object) | 625760 references (82.88 refs/object)
  - [0.63%] ApplicationPeriod interner: 5883 objects | 104488 bytes (17.76 bytes/object) | 631593 references (107.36 refs/object)
- [4.06%] Line interner: 6880 objects | 672568 bytes (97.76 bytes/object) | 930026 references (135.18 refs/object)
  - [15.30%] ImpactedObject interner: 55373 objects | 2536756 bytes (45.81 bytes/object) | 3183332 references (57.49 refs/object)

Используем enum (1,4%)

На этом этапе корневые struct Data используют половину оптимизированного размера. Можно заметить, что они содержат только опциональные поля.

struct Data {
    status_code: Option<i32>,
    error: Option<IString>,
    message: Option<IString>,
    disruptions: Option<InternedSet<Disruption>>,
    lines: Option<InternedSet<Line>>,
    last_updated_date: Option<IString>,
}

Однако на практике задаваемые поля идут вместе: объект или содержит ошибку с полями status_code, error и message, или содержит полезные данные с полями disruptions, lines и last_updated_date. Для лучшего представления можно использовать перечисление с двумя вариантами.

enum Data {
    Success {
        disruptions: InternedSet<Disruption>,
        lines: InternedSet<Line>,
        last_updated_date: IString,
    },
    Error {
        status_code: i32,
        error: IString,
        message: IString,
    },
}

Такое разделение имеет два плюса: схема становится более согласованной семантически и занимает меньше места в памяти. Interned<T> занимает 4 байта (индекс u32), а Option<Interned<T>> занимает 8 байтов: 1 бит под состояние опции и остальное для выравнивания размера до кратного 4 байтам.

На этот раз снижение размера оказалось гораздо более скромным (коммит c8ac261).

Parsed 1137178883 bytes from 30466 files (+ 21 failed files)
Expanded to 1531039733 bytes in memory (relative size = 134.63%)
Optimized to 15847679 bytes (relative size = 1.39%)
[53.04%] Interners: 8405895 bytes
- [27.97%] String interner: 56374 objects | 4433335 bytes (78.64 bytes/object) | 23964083 references (425.09 refs/object)
- [4.16%] Disruption interner: 7550 objects | 658748 bytes (87.25 bytes/object) | 625760 references (82.88 refs/object)
  - [0.66%] ApplicationPeriod interner: 5883 objects | 104488 bytes (17.76 bytes/object) | 631593 references (107.36 refs/object)
- [4.24%] Line interner: 6880 objects | 672568 bytes (97.76 bytes/object) | 930026 references (135.18 refs/object)
  - [16.01%] ImpactedObject interner: 55373 objects | 2536756 bytes (45.81 bytes/object) | 3183332 references (57.49 refs/object)

Разбиваем struct (0,82%)

В примере с ImpactedObject можно также заметить, что он содержит и константные поля (type, identifier, name) и изменяющиеся поля (список нарушений). Это значит, что при каждом добавлении или удалении нарушения из списка новый ImpactedObject создаётся и добавляется в интернер, даже если определяющие объект поля «заголовка» не поменялись. Оптимизированней было бы извлекать поля в отдельный объект и добавить для них новый интернер.

struct ImpactedObject {
    // Неизменяемая часть объекта.
    object: Interned<Object>,
    disruption_ids: InternedSet<String>,
}

// Новая struct, группирующая неизменяемые поля объекта.
struct Object {
    typ: IString,
    id: IString,
    name: IString,
}

Стоит отметить, что новый дизайн не изменил общее количество ImpactedObject (55373), но уменьшил каждый из них: по одному индексу u32 для Interned<Object> вместо трёх индексов IString. Однако количество Object стало намного меньше (1679), потому что на каждый из них ссылаются многие ImpactedObject (коммит 8914a64).

Parsed 1137178883 bytes from 30466 files (+ 21 failed files)
Expanded to 1531039733 bytes in memory (relative size = 134.63%)
Optimized to 15330607 bytes (relative size = 1.35%)
[51.46%] Interners: 7888823 bytes
- [28.92%] String interner: 56374 objects | 4433335 bytes (78.64 bytes/object) | 23964083 references (425.09 refs/object)
- [4.30%] Disruption interner: 7550 objects | 658748 bytes (87.25 bytes/object) | 625760 references (82.88 refs/object)
  - [0.68%] ApplicationPeriod interner: 5883 objects | 104488 bytes (17.76 bytes/object) | 631593 references (107.36 refs/object)
- [3.67%] Line interner: 6880 objects | 562488 bytes (81.76 bytes/object) | 930026 references (135.18 refs/object)
  - [0.01%] LineHeader interner: 45 objects | 1428 bytes (31.73 bytes/object) | 930026 references (20667.24 refs/object)
  - [13.66%] ImpactedObject interner: 55373 objects | 2093772 bytes (37.81 bytes/object) | 3183332 references (57.49 refs/object)
    - [0.23%] Object interner: 1679 objects | 34564 bytes (20.59 bytes/object) | 3183332 references (1895.97 refs/object)

На этот раз улучшение было маленьким, но если взглянуть на вторую половину ImpactedObject , то можно заметить, что на многие объекты может повлиять одно и то же множество нарушений, например, потому, что они представляют станции на одной линии. Добавив ещё один слой косвенности и выполнив interning интернированного множества, мы снова можем снизить избыточность. На практике есть лишь 9127 уникальных множеств ID нарушений (коммит fcff0d5).

struct ImpactedObject {
    object: Interned<Object>,
    // Тоже интернируем множество.
    disruption_ids: Interned<InternedSet<String>>,
}

Это уменьшило оптимизированный размер более чем на треть.

Parsed 1137178883 bytes from 30466 files (+ 21 failed files)
Expanded to 1531039733 bytes in memory (relative size = 134.63%)
Optimized to 9364491 bytes (relative size = 0.82%)
[94.79%] Interners: 8877035 bytes
- [47.34%] String interner: 56374 objects | 4433335 bytes (78.64 bytes/object) | 23964083 references (425.09 refs/object)
- [3.50%] InternedSet<String> interner: 9127 objects | 327620 bytes (35.90 bytes/object) | 3183332 references (348.78 refs/object)
- [7.90%] InternedSet<Disruption> interner: 7066 objects | 739652 bytes (104.68 bytes/object) | 30430 references (4.31 refs/object)
  - [7.03%] Disruption interner: 7550 objects | 658748 bytes (87.25 bytes/object) | 625760 references (82.88 refs/object)
    - [1.12%] ApplicationPeriod interner: 5883 objects | 104488 bytes (17.76 bytes/object) | 631593 references (107.36 refs/object)
- [11.88%] InternedSet<Line> interner: 7183 objects | 1112896 bytes (154.93 bytes/object) | 30430 references (4.24 refs/object)
  - [6.01%] Line interner: 6880 objects | 562488 bytes (81.76 bytes/object) | 930026 references (135.18 refs/object)
    - [0.02%] LineHeader interner: 45 objects | 1428 bytes (31.73 bytes/object) | 930026 references (20667.24 refs/object)
    - [9.63%] ImpactedObject interner: 55373 objects | 901816 bytes (16.29 bytes/object) | 3183332 references (57.49 refs/object)
      - [0.37%] Object interner: 1679 objects | 34564 bytes (20.59 bytes/object) | 3183332 references (1895.97 refs/object)

Специализируем типы (0,64%)

После всех этих оптимизаций строки занимали половину оптимизированного места: каждый Interner — это таблица, на которую остальные объекты могут ссылаться по индексу. На практике, интернер строк содержал значения очень разнородной семантики: одни строки были длинными сообщениями об ошибках в формате HTML, другие — простыми названиями мест, третьи — идентификаторами наподобие UUID, четвёртые — метками времени в человекочитаемом формате. Особенно интересны последние два вида: вместо того, чтобы хранить их в виде простых строк, можно спарсить их в более компактные и семантически обогащённые форматы.

Для UUID мы можем просто использовать тип Uuid из крейта uuid. Внутри этот тип использует под хранение каждого идентификатора всего 16 байтов вместо 36 байтов для строк наподобие 67e55044-10b1-426f-9247-bb680e5fe0c8 (оверхед шестнадцатеричного кодирования + разделителей).

Для меток времени я выбрал крейт chrono, желая хранить каждую в 8 байтах (64-битное количество секунд с эпохи Unix) вместо 15-24 байтов для чего-то типа 20240428T044500 или 2024-05-01T00:59:25.384Z. Однако возникла сложность: некоторые метки времени были закодированы в формате RFC 3339 с точностью до миллисекунд в часовом поясе UTC, в других указывалась наивные дата + время в секундах для косвенно подразумеваемого часового пояса Парижа. В этом случая я использовал крейт chrono-tz для выполнения преобразований и канонизации их в UTC.

Однако когда часовой пояс не указан явным образом, есть одна тонкость: в дни, когда начинается или заканчивается переход на летнее время, время между 2 и 3 часами ночи может интерпретироваться неоднозначно (мы не знаем, находимся ли мы в часовом поясе CET или CEST при переходе времени с 3 на 2 часа) или неправильно (когда время переходит с 2 на 3 часа). Тем не менее, сеть метрополитена обычно в этом время закрыта, поэтому небольшая неточность не так уж важна. При работе, например, с расписанием ночных поездов это бы больше напрягало.

use chrono::offset::LocalResult;
use chrono::{DateTime, NaiveDateTime};
use chrono_tz::Europe::Paris;

struct TimestampSecondsParis(i64);

impl TimestampSecondsParis {
    fn from_formatted(x: &str, format: &str) -> Self {
        let naive_datetime = NaiveDateTime::parse_from_str(x, format).unwrap_or_else(|_| {
            panic!("Failed to parse datetime (custom format {format:?}) from {x}")
        });

        // Обрабатываем специфику моментов переходов летнего времени.
        let datetime = match naive_datetime.and_local_timezone(Paris) {
            LocalResult::Single(x) => x,
            LocalResult::Ambiguous(earliest, latest) => {
                eprintln!("Ambiguous mapping of {naive_datetime:?} to the Paris timezone: {earliest:?} or {latest:?}");
                earliest
            }
            LocalResult::None => {
                panic!("Invalid mapping of {naive_datetime:?} to the Paris timezone")
            }
        };

        TimestampSecondsParis(datetime.timestamp())
    }
}

Это изменение позволило избавиться от подавляющего большинства интернированных строк, сэкономив ещё 2 МБ (коммиты 2031f42 и ad29181).

Parsed 1137178883 bytes from 30466 files (+ 21 failed files)
Expanded to 1322690141 bytes in memory (relative size = 116.31%)
Optimized to 7264110 bytes (relative size = 0.64%)
[89.93%] Interners: 6532926 bytes
- [25.03%] String interner: 8050 objects | 1818466 bytes (225.90 bytes/object) | 17309489 references (2150.25 refs/object)
- [2.25%] Uuid interner: 6617 objects | 163296 bytes (24.68 bytes/object) | 4735218 references (715.61 refs/object)
- [10.18%] InternedSet<Disruption> interner: 7066 objects | 739652 bytes (104.68 bytes/object) | 30430 references (4.31 refs/object)
  - [9.90%] Disruption interner: 7550 objects | 719148 bytes (95.25 bytes/object) | 625760 references (82.88 refs/object)
    - [2.09%] ApplicationPeriod interner: 5883 objects | 151552 bytes (25.76 bytes/object) | 631593 references (107.36 refs/object)
- [15.32%] InternedSet<Line> interner: 7183 objects | 1112896 bytes (154.93 bytes/object) | 30430 references (4.24 refs/object)
  - [7.74%] Line interner: 6880 objects | 562488 bytes (81.76 bytes/object) | 930026 references (135.18 refs/object)
    - [0.02%] LineHeader interner: 45 objects | 1428 bytes (31.73 bytes/object) | 930026 references (20667.24 refs/object)
    - [12.41%] ImpactedObject interner: 55373 objects | 901816 bytes (16.29 bytes/object) | 3183332 references (57.49 refs/object)
      - [0.48%] Object interner: 1679 objects | 34564 bytes (20.59 bytes/object) | 3183332 references (1895.97 refs/object)
      - [4.51%] InternedSet<Uuid> interner: 9127 objects | 327620 bytes (35.90 bytes/object) | 3183332 references (348.78 refs/object)

Продолжение следует...

Теги:

Хабы:

Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку