[Перевод] Уменьшаем базу данных в 2000 раз при помощи Rust (завершение)14.03.2025 08:46

Окончательный результат: легковесная база данных только для добавления

Чтобы воссоздать эти результаты, можно найти мой код на GitHub. Я использовал данные RATP Status из коммита ef028cc (файлы в папке datas/json/).

git init
git remote add origin https://github.com/wincelau/ratpstatus
git fetch --depth 1 origin ef028cce567b6ce9183a185e699206e0f483b99d
git checkout FETCH_HEAD

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

К концу этой статьи мы опосредованно создали одну из самых простых архитектур реляционных баз данных (без части, относящейся к запросам/SQL). Она обладает некоторыми ограничениями, приемлемыми при работе с временными последовательностями:

• только добавление данных: мы не можем ни изменять, ни удалять имеющиеся объекты,

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

• один писатель: для выполнения инкремента при интернировании нового объекта без синхронизации.

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

А следует ли на практике использовать один из бесчисленного количества крейтов для interning, или их следует писать самостоятельно? Ответ зависит от того, что вы хотите сделать!

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

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

Приложение: оптимизируем функцию interning

Пользователи Reddit предложили мне два способа улучшения реализации interning.

• watsonborn порекомендовал использовать HashMap::entry() API, чтобы не искать значение дважды при его вставке в интернер.

• angelicosphosphoros порекомендовал использовать для манипуляций со строками Rc вместо Rc.

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

Непосредственное применение HashMap::entry() не будет оптимальным, потому что он требует передачи полного ключа, то есть всегда понадобится создавать Rc , даже если мы просто выполняем поиск (при котором будет достаточно передачи &T).

impl Interner {
    fn intern(&mut self, value: T) -> u32 {
        // Функция entry() требует создания Rc.
        let rc: Rc = Rc::new(value);
        *self.map.entry(Rc::clone(&rc)).or_insert_with(|| {
            let id = self.vec.len();
            assert!(id <= u32::MAX as usize);
            self.vec.push(rc);
            id as u32
        })
    }
}

Однако существует более эффективный HashMap::raw_entry_mut() API, доступный в nightly-фиче hash_raw_entry (или в крейте hashbrown стабильного Rust). Этот API позволяет начала поискать элемент с тем, что заимствует ключ (в нашем случае ссылка &T), и позже развернуть полный ключ Rc только в случае, если элемент пуст. Это максимальная оптимизация, доступная для map API в Rust.

#![feature(hash_raw_entry)]

impl Interner {
    fn intern(&mut self, value: T) -> u32 {
        let (_, id) = self
            .map
            .raw_entry_mut()
            // Здесь мы передаём &T для поиска.
            .from_key(&value)
            .or_insert_with(|| {
                let id = self.vec.len();
                assert!(id <= u32::MAX as usize);

                let rc: Rc = Rc::new(value);
                self.vec.push(Rc::clone(&rc));
                // Здесь мы передаём Rc для вставки.
                (rc, id as u32)
            });
        *id
    }
}

Что касается второй рекомендации, то с ней не всё так просто: хотя Rc занимает меньше места в памяти и избегает уровня разыменования указателя, преобразование из String в Rc требует клонирования всего содержимого строки. Однако затраты на это клонирование возникают только при вставке новых строк, поэтому можно надеяться, что они будут амортизированы с запасом в случае многократного повторения одинаковых строк (в чём и заключается смысл interning).

Или же можно использовать что-то типа крейта CompactStr (выполняющего оптимизацию малых строк) для экономии места в памяти.

Но что потребуется для поддержки Interner? Сначала нам нужно добавить повсюду явное ограничение T: ?Sized, так как срез строки str — это динамический тип. Во-вторых, мы не можем вызывать функцию с обычным параметром T = str, потому что он динамический. Вместо этого, например, можно использовать трейты преобразования Borrow и Into, чтобы создать более гибкий обобщённый API.

Если объединить две рекомендации, то функция interning принимает показанный ниже вид. Вместо получения T она принимает любой параметр, который (1) можно заимствовать как &T (чтобы искать его в map) и (2) можно преобразовать в Rc (чтобы вставлять его в map).

impl Interner {
    fn intern(&mut self, value: impl Borrow + Into>) -> u32 {
        let (_, id) = self
            .map
            .raw_entry_mut()
            // Поиск принимает любой тип, который можно заимствовать как &T.
            .from_key(value.borrow())
            .or_insert_with(|| {
                let id = self.vec.len();
                assert!(id <= u32::MAX as usize);
                let id = id as u32;

                // Вставка принимает любой тип, который можно преобразовать в Rc.
                let rc: Rc = value.into();
                self.vec.push(Rc::clone(&rc));
                (rc, id)
            });
        *id
    }
}

Это позволяет передавать Interner широкий спектр типов: заимствованный срез строки &str, принадлежащую строку String, boxed-срез строки Box, срез строки с копированием при записи Cow<'_, str>, и Rc и так далее. Однако стоит учитывать, что преобразование большинства этих типов в Rc (для пути вставки) вызовет клонирование содержимого строки.

Это изменение также потребовало изменений в логике оценки размера и десериализации, подробности приведены в коммите 279e2cb.

1. And no, RATP status isn«t implemented in Rust. A PHP website can be blazingly fast too!  ↩

2. In my opinion, this approach, made popular by formats like Protocol Buffers, may unfortunately give a false sense of «out-of-the-box» versioning. If you«re changing the semantics of your system, you almost always need to write additional code to ensure compatibility between the various versions. Out-of-the-box versioning can prevent outright outages in the short term, but also makes it easier to forget writing the needed compatibility code and to introduce more subtle differences due to ignoring unknown but important fields. This can cause errors, data corruption, instabilities or even other outages in the longer term. ↩