Перевод/заметки German Strings

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

Мы не стали исключением и создали свой собственный тип строк, который хорошо оптимизирован для обработки данных. Хотя мы и не ожидали этого, когда впервые написали об этом в нашей первой исследовательской работе Umbra, многие новые системы приняли наш формат. Сейчас он реализован в DuckDB, Apache Arrow, Polars, и Facebook Velox.

В этом посте расскажем о преимуществах так называемых «German Strings» и о том, на какие компромиссы мы пошли.

Но сначала давайте сделаем шаг назад и посмотрим, как обычно реализуются строки.

Как это делает C

В C строки - это просто последовательность байтов с обещанием, что в какой-то момент байт \0 завершит строку.

This is an image

Это очень простая модель с точки зрения концепции, но очень неудобная на практике:

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

Как это делает C++

C++ предоставляет гораздо более удобные строки через свою стандартную библиотеку. Стандарт C++ не требует конкретной реализации, но вот как это сделано в libc++:

This is an image

Каждый объект string хранит свой размер (уже лучше, чем в C!), указатель на фактическую полезную нагрузку и вместимость буфера, в котором хранятся данные. Вы можете добавлять к строке «бесплатно» до тех пор, пока полученная строка не станет больше размера буфера, тогда строка сама позаботится об аллокации нового буфера и освобождении старого. std::strings мутабельны.

Такие строки также позволяют реализовать очень важную «short string optimization»: Достаточно короткая строка может храниться «in place», то есть мы устанавливаем определенный бит в поле capacity, и остаток capacity, а также size и ptr становятся самой строкой. Таким образом, мы экономим на аллокации буфера и разыменовании указателя при каждом обращении к строке. Оптимизация, которая, кстати, невозможна в Rust ;).

Можем ли мы сделать лучше?

C++, особенно с оптимизацией коротких строк, уже неплохо справляется. Однако, если вы знаете свой сценарий использования, оказывается, что можно сделать лучше.

В процессе создания CedarDB мы сделали следующие наблюдения:

Большинство строк короткие

Несмотря на возможность хранить произвольные объемы текста, большинство людей хранят в своих строках достаточно короткие и предсказуемые данные (об этом сообщают Vogelsgesang и др. в своей фантастической статье “Get Real”).

Примерами таких коротких строк:

  • ISO country codes (USA, DEU, GBR), 3 символа
  • IATA airport codes (LHR, MUC), 3 символа
  • Enums (MALE/FEMALE/NONBINARY, YES/NO/MAYBE), обычно не более 10 символов
  • ISBNs (0465062881), 10 или 13 цифр

Мы определенно хотим оптимизировать такие короткие строки, когда это возможно.

Строки обычно меняют не так часто

Большинство данных записывается один раз, но читается много раз. Подход libc++, при котором 64 бита на строку резервируются только для хранения емкости на случай, если кто-то захочет расширить строку, кажется расточительным, когда размеры строк меняются не так уж часто.

Кроме того, одновременное обращение к строке и ее модификация могут привести к data race, если мы не используем дорогие методы блокировки или не продумаем наше приложение очень тщательно.

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

Обычно мы используем только небольшую часть строки

Посмотрите на следующий SQL-запрос:

select * from messages where starts_with(content, 'http');

Обратите внимание, что оптимизация коротких строк в libc++ здесь не спасает: Если строка не короткая, мы должны следовать за указателем, даже если нам важен только префикс.

Давайте рассмотрим другой запрос:

select sum(p.amount) 
from purchases p, books b  
where p.ISBN = b.ISBN and b.title = 'Gödel, Escher, Bach: An Eternal Golden Braid';

Здесь нам нужно сравнить все ISBN друг с другом и все названия книг со строковой константой. Хотя нам, очевидно, нужно сравнить всю строку, чтобы убедиться в совпадении, большинство книг, вероятно, не будут называться «Gödel, Escher, Bach: An Eternal Golden Braid» (как много строк, начинающихся с «Gö»?). Если символ в начале строки уже отличается, мы можем исключить его, не проверяя остальную часть строки.

Анатомия German String

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

Эта структура содержит одно из двух следующих представлений:

Представление коротких строк

Вот лейаут памяти для коротких строк:

This is an image

Пока строка состоит из 12 или менее символов, мы сохраняем содержимое прямо так.

Получить доступ к самому содержимому или только к префиксу очень просто: достаточно начать чтение сразу после поля len, и не нужно никаких разыменований указателей!

Представление длинных строк

Строки длиной более 12 символов требуют другого подхода:

This is an image

Как и в строках C++, мы также храним поле len и указатель на сами данные, но с некоторыми изменениями:

Length

Чтобы уместить всю строку в 128 бит, мы сокращаем поле длины до 32 бит. Это ограничивает размер строки до 4 ГБ, что является компромиссом, на который мы готовы пойти для нашего случая.

Prefix

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

Pointer

Указывает на область памяти размером ровно со строку. Никакого буфера с оставшимся capacity!

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

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

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

Storage Class

Разрабатывая концепцию строк, мы заметили, что разработчики предъявляют разные требования к сроку службы строк в зависимости от того, где они их используют. Мы назвали их «storage classes», которые вы можете указать при создании строки. Строка может быть persistent, transient или temporary. Чтобы закодировать этот класс хранения, мы берем два бита из указателя.

Начнем с примеров, которые, возможно, уже знакомы вам по вашему любимому языку программирования:

  • temporary строки ведут себя так же, как их аналоги в C++: При создании временной строки конструктор строки сам выделяет некоторую память, сохраняет полезную нагрузку и корректно устанавливает указатель. Когда строка выходит из области видимости, память освобождается в стиле RAII.
  • persistent строки ведут себя как строковые константы: Они остаются актуальными всегда. Все короткие строки всегда являются постоянными, потому что вы можете просто передать их через стек или регистры процессора. Длинные строки также могут быть постоянными, например, при обращении к строковым литералам C++. Память, в которой хранятся данные строкового литерала, автоматически выделяется статически при запуске программы и никогда не удаляется, поэтому ссылки на данные строки всегда актуальны.

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

  • сначала загрузите страницу в память,
  • а затем инициализировать новую строку, которая копирует данные в только что инициализированную память.

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

select * from books where starts_with(title,'Tutorial')

Если мы отфильтруем все книги на предмет совпадений, большинство строк не попадут в список. Нам никогда не понадобится показывать их человеку, сделавшему запрос, так зачем же копировать их, если нам не нужно будет обращаться к ним в дальнейшем?

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

Вот тут-то и пригодятся transient строки. Они указывают на данные, которые действительны в данный момент, но могут стать недействительными позже, например, когда мы переместим страницу, на которой хранится полезная нагрузка, на диск после снятия блокировки со страницы.

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

Различие между представлениями

Как узнать, с короткой или длинной строкой мы имеем дело? На самом деле это очень просто! Если ее размер составляет 12 символов или меньше, то это короткая строка. Поскольку наши строки неизменяемы, не существует особого случая, когда длинная строка может стать короткой или наоборот.

Если мы хотим получить доступ только к префиксу, нам даже не нужно проверять, длинная строка или короткая. В любом случае биты 32-63 будут первыми четырьмя символами.

Заключение

Немецкие строки имеют множество преимуществ: Высокая производительность за счет экономии места и сокращения аллокации и перемещения данных. Поскольку данные всегда рассматриваются как неизменяемые, распараллелить код обработки строк гораздо проще. Благодаря концепции классов хранения(storage classes) вы можете жестко управлять временем жизни ваших строк, при необходимости обменивая производительность на простоту использования.

Конечно, ничто не обходится без сложностей: Немецкие строки требуют от вас более глубоких знаний в процессе их использования: Каково время жизни моей строки? Могу ли я обойтись transient строкой или мне придется ее копировать? Часто ли будут обновляться мои строки? Можно ли обойтись неизменяемыми строками?

Если вы не против задать себе эти вопросы, вы можете извлечь много пользы из German Strings, даже если вы не создаете базу данных.

Комментарии в Telegram-группе!