lstore.md

L-Store

Данный текст является вольным переводом статьи L-Store: A Real-time OLTP and OLAP System.

Термины

OLTP (Online Transaction Processing), транзакционная система -- обработка транзакций в реальном времени. Способ организации БД, при котором система работает с небольшими по размерам транзакциями, но идущими большим потоком, и при этом клиенту требуется от системы минимальное время отклика.

OLAP (Online Analytical Processing), интерактивная аналитическая обработка -- ехнология обработки данных, заключающаяся в подготовке суммарной (агрегированной) информации на основе больших массивов данных.

Record, запись -- строка в таблице.

Page, страница -- непрерывный участок памяти (например, в Linux это 4 кб, а в PostgreSQL 8 кб).

Сложности перевода

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

Родословная (Lineage, происхождение) -- связь между записями в хранилище. Когда мы обновляем запись, мы записываем ссылку на новую запись в оригинал и наоборот. Это позволяет нам найти предка записи (запись, появивщуюся в результате операции INSERT) или самую свежую версию записи (результат последней операции UPDATE над записью).

Бесконфликтный (Contention-free) -- исполняющийся без конкуренции в многопоточной среде.

Аннотация

Возможно, данные -- это новый природный ресурс в мире корпораций, имеющий беспрецедентную степень распространения. Но чтобы извлекать из данных в реальном времени оперативную полезную информацию, важно преодолеть разрыв между управлением данными, которые обновляются с высокой скоростью (т.е. OLTP), и анализом большого объема данных (т.е. OLAP). Однако существовал разделение, когда специализированные решения часто развертывались для поддержки рабочих нагрузок либо OLTP, либо OLAP, но не обеих, что ограничивало анализ устаревшими и, возможно, неактуальными данными.

Lineage-based Data Store (L-Store) объединяет обработку транзакционных и аналитических рабочих нагрузок в реальном времени в рамках единого унифицированного движка, внедряя новую архитектуру хранения на основе родословной. Используя родословную, мы разрабатываем бесконфликтную и ленивую подготовку столбчатых данных из оптимизированной для записи формы (подходящей для OLTP) в оптимизированную для чтения форму (подходящей для OLAP) в транзакционно согласованном подходе, который также поддерживает запросы и сохранение текущих и исторических данных.

Введение

Сейчас мы наблюдаем архитектурный сдвиг и разделение в сообществе баз данных. Первая школа мысли возникла из академической гипотезы, что «one size does not fit all» (т.е., отстаивание специализированных решений), что привело к множеству инноваций за последнее десятилетие в создании специализированных движков баз данных, ориентированных на различные нишевые рабочие нагрузки и сценарии приложений.

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

Во-первых, существуют огромные затраты на создание и поддержку нескольких движков как с точки зрения поставщиков баз данных, так и с точки зрения пользователей систем (например, затраты на разработку и развертывание приложений). Во-вторых, есть убедительные доводы в пользу поддержки принятия решений в реальном времени на основе последней версии данных, что может быть неосуществимо в слабо интегрированных движках, которые связаны через процесс ETL процесс. В-третьих, объединение функций OLTP и OLAP в реальном времени остается важным вопросом фундаментального исследования, требующим более глубокого изучения, даже если это чисто теоретическое исследование.

Поддерживая последнюю школу мысли (т.е. выступая за обобщенное решение), мы представляем хранилище данных на основе родословной (L-Store) с новой архитектурой хранения на основе родословной для решения конфликтов между построчным и столбцовым представлением путем разработки бесконфликтного и ленивого размещения столбчатых данных из оптимизированной для записи в оптимизированную для чтения форму транзакционно согласованным образом без необходимости репликации данных, поддержания множественного представления данных или разработки нескольких слабо интегрированных механизмов, что жертвует возможностями реального времени.

Чтобы еще больше устранить неоднозначность нашего понятия «one size fit all», в этой статье мы ограничиваем наше внимание возможностями реляционной OLTP и OLAP в реальном времени. Мы определяем набор архитектурных характеристик для выявления различий между существующими методами. Во-первых, может быть один продукт, состоящий из нескольких слабо интегрированных движков, которые могут быть развернуты и настроены для поддержки OLTP или OLAP. Во-вторых, может быть один движок, а не несколько специализированных движков, упакованных в один продукт. В-третьих, даже если у нас есть один движок, то у нас может быть несколько экземпляров, работающих на одном движке, где один экземпляр выделен и настроен для рабочих нагрузок OLTP, в то время как другой экземпляр оптимизирован для рабочих нагрузок OLAP, в котором предполагается, что разные экземпляры связаны с использованием ETL процесса. Наконец, даже при использовании одного и того же движка, работающего в одном экземпляре, может быть несколько копий или представлений (например, строковая или столбчатая компоновка) данных, где одна копия (или представление) данных оптимизирована для чтения, а вторая копия (или представление) оптимизирована для записи.

Архитектурное сравнение различных существующих методов, основанное на нашем строгом определении «один размер подходит всем», представлено в следующей таблице.

Сравнение существующих подходов

Иными словами, L-Store, важный первый шаг на пути к поддержке обработки OLTP и OLAP в реальном времени, который полностью соответствует нашему определению обобщенного решения, и, в частности, имеет следующие ключевые особенности:

• архитектура, которая обеспечивает безконфликтный механизм обновления на основе собственной многоверсионной столбчатой ​​модели хранения данных для ленивого и независимого перемещения стабильных данных из столбчатой ​​структуры, оптимизированной для записи (т.е. OLTP), в столбчатую структуру, оптимизированную для чтения (т.е. OLAP)
• Гарантирует доступ к последней версии любой записи не более чем за два прыжка (предотвращая ухудшение производительности чтения для точечных запросов)
• Бесконфликтное слияние только стабильных данных, а именно слияние базовых данных, доступных только для чтения, с недавно зафиксированными обновлениями (оба в столбчатом представлении) без необходимости блокировать текущие или новые транзакции
• Освобождение страниц без конфликтов (после завершения процесса слияния) с использованием подхода на основе эпох без необходимости очистки текущих транзакций

Единая архитектура

L-Store основан на столбоцовом хранении данных, при котором данные в столбцах выравниваются (для неявной реконструкции записи), где записи (виртуально) разделены на непересекающиеся диапазоны (также называемые диапазоном обновления, update range). Записи в каждом диапазоне охватывают набор сжатых страниц только для чтения, которые мы называем базовыми страницами (base pages). Что еще более важно, для каждого диапазона записей и для каждого обновленного столбца в диапазоне мы поддерживаем набор страниц только для добавления для хранения последних обновлений, которые мы называем хвостовыми страницами (tail pages). Каждый раз, когда запись обновляется на базовых страницах, новая запись добавляется к соответствующим ей хвостовым страницам, где есть явные значения только для обновленных столбцов (необновленным столбцам предварительно назначается специальное значение null при первом выделении страницы). Мы называем записи на базовых страницах базовыми записями, а записи на хвостовых страницах — хвостовыми записями. Каждая запись (независимо от того, находится ли она на базовой или конечной странице) охватывает набор выровненных столбцов.

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

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

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

Для ускорения обработки запросов также существует явная связь (прямые и обратные указатели) между записями. Из базовой записи есть прямой указатель на последнюю версию записи на хвостовых страницах. Различные версии одних и тех же записей на хвостовых страницах связаны вместе, чтобы обеспечить быстрый доступ к более ранней версии записи. Связь устанавливается путем введения в таблицу метастолбца Indirection, который хранит прямые указатели (т.е. RID) для базовых записей и обратные указатели для хвостовых записей (т.е. RID).

Но важно отметить, что RID, назначенный базовой записи, стабилен и остается неизменным на протяжении всего жизненного цикла записи, и все индексы ссылаются только на базовые записи; следовательно, устраняется проблема обслуживания индекса, связанная с тем, что операция обновления приводит к созданию новой версии записи. Когда читатель выполняет поиск по индексу, он всегда попадает на базовую запись, и из базовой записи он может достичь любой желаемой версии записи, следуя встроенному в таблицу Indirection столбцу, чтобы получить доступ к последней (если базовая запись устарела) или более ранней версии записи. Однако, когда запись обновляется, создается новая версия. Таким образом, создается новая хвостовая запись для хранения новой версии, и этой новой хвостовой записи назначается новый RID, на который ссылается базовая запись.

Каждая таблица, помимо столбцов данных, имеет несколько столбцов метаданных.

Столбец Indirection существует как в базовой, так и в хвостовой записях. Для базовых записей столбец Indirection интерпретируется как прямой указатель на последнюю версию записи, находящейся на хвостовых страницах, по сути, хранящий RID последней версии записи. Если запись никогда не обновлялась, то столбец Indirection будет содержать null. Напротив, для хвостовых записей столбец Indirection используется для хранения обратного указателя на последнюю обновленную версию записи на хвостовых страницах. Если более ранней версии не существует, то столбец Indirection будет указывать на RID базовой записи.

Столбец Schema encoding хранит битовое представление состояния столбцов данных для каждой записи, где каждому столбцу в схеме (за исключением столбцов метаданных) назначается один бит, и если столбец обновляется, его соответствующий бит в столбце Schema encoding устанавливается в 1, в противном случае устанавливается в 0. Schema encoding позволяет быстро определить, обновлялся ли столбец когда-либо или нет (для базовых записей) или определить для каждой хвостовой записи, какие столбцы были обновлены и имеют явные значения в отличие от тех столбцов, которые не были обновлены и имеют неявные специальные нулевые значения.

В столбце Start Time хранится время, когда базовая запись была впервые установлена ​​на базовых страницах (исходное время вставки), а для хвостовой записи столбец Start Time содержит время, когда запись была обновлена, что также является неявным конечным временем предыдущей версии записи. Столбец Start Time необходим для поддержания и различения различных версий записи.

В дополнение к столбцу Start Time для базовых записей мы поддерживаем столбец Last Updated Time, который заполняется только после того, как происходит процесс слияния, и отражает время начала тех хвостовых записей, которые включены в объединенные страницы. Также обратите внимание, что начальный столбец Start Time для базовых записей всегда сохраняется (даже после процесса слияния) для более быстрой обрезки тех записей, которые не видны читателям, поскольку они выходят за рамки снимка читателя.

Наконец, для хвостовых записей мы добавим столбец Base RID для хранения RID соответствующих им базовых записей; это используется для улучшения процесса слияния.

Развернутый вид архитектуры

Операции над хранилищем

Update и Delete

Без потери общности, с точки зрения уровня хранения, мы фокусируемся на том, как обрабатывать обновление или удаление одного столбца в L-Store. Каждое обновление может повлиять на одну или несколько записей. Поскольку записи (виртуально) разделены на набор непересекающихся диапазонов, каждая обновленная запись естественным образом попадает только в один диапазон. Теперь для каждого диапазона записей при первом обновлении этого диапазона создается набор хвостовых страниц для обновленных столбцов и добавляется в каталог страниц, т.е. ленивое распределение хвостовых страниц. Следовательно, обновления для каждого диапазона записей добавляются только к соответствующим им конечным страницам обновленных столбцов; тем самым происходит переподготовка всех версий записи, избегание in-place обновлений измененных столбцов данных и кластеризация обновлений для диапазона записей в пределах соответствующих им конечных страниц.

Алгоритм

Когда транзакция обновляет какой-либо столбец записи в первый раз, создаются две новые хвостовые записи (каждой присваивается уникальный RID), которые добавляются к соответствующим хвостовым страницам. Первая хвостовая запись содержит исходное значение обновленного столбца (а все остальные null), в то время как вторая содержит недавно обновленное значение (и снова null для остальных столбцов). Создание снимка исходных измененных значений становится необходимым для обеспечения слияния без конфликтов. Столбец, который никогда не обновлялся, даже не должен быть материализован со специальными нулевыми значениями. Однако для любых последующих обновлений создается только одна хвостовая запись с обновленным значением.

В рамках операции обновления метастолбец Indirection (прямые указатели) для базовых записей также обновляется, чтобы указывать на вновь созданную конечную запись. Аналогично столбец Indirection в хвостовых записях указывает на предыдущую версию записи. Важно отметить, что столбец Indirection базовых записей -- единственный столбец, требующий обновления на месте в нашей архитектуре.

Кроме того, индексы всегда указывают на базовые записи (т.е. base RID), и они никогда напрямую не указывают на какие-либо хвостовые записи (т.е. tail RID), чтобы избежать затрат на обслуживание индекса. Поэтому, когда создается новая версия записи (т.е. новая хвостовая запись), во-первых, все индексы, определенные в незатронутых столбцах, не должны быть изменены, и, во-вторых, только затронутые индексы изменяются с обновленными значениями, но они продолжают указывать на базовые записи, а не на вновь созданные хвостовые записи.

Есть еще два столбца метаданных, на которые влияет процедура обновления. Столбец Start Time для хвостовых записей просто содержит время, когда запись была обновлена ​​(неявное окончание предыдущей версии). Столбец Schema Encoding — это краткое представление, которое показывает, какие столбцы данных были обновлены к настоящему моменту. Schema Encoding также может поддерживаться опционально для базовых записей как часть процесса обновления или может быть заполнена только во время процесса слияния.

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

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

Пример

Пример операции Update

Допустим мы обновляем в столбце A строку с ключом k2 (ссылается на RID b2). Первая хвостовая запись с RID t1 содержит исходное значение обновленного столбца, т.е. a2. Вторая хвостовая запись содержит недавно обновленное значение для столбца A, а именно a21. При следующем обновлении создается только одна хвостовая запись с RID t3, изменяя значение столбца A с a21 до a22 для записи b2. После всех обновлений Indirection записи b2 указывает на хвостовую запись t5. Также после обновления столбца C записи b3 столбец Indirection указывает на последнюю версию b3, которая задается t7. Кроме того, запись t7 имеет начальное время 19:45, что также подразумевает, что это конечное время первой версии записи b3, а Schema Encoding хвостовой записи t7 установлен на «0001», что подразумевает, что был изменен только столбец C.

Теперь предположим, что есть индекс, определенный в столбце C. Теперь, после изменения записи b2 с c2 на c21, мы добавляем новую запись (c21, b2) в индекс по столбцу C. Впоследствии, когда читатель ищет значение c21 в индексе, он всегда сначала попадает на базовую запись b2, затем читатель должен определить видимую версию b2 (при необходимости следуя по Indirection) и проверить, имеет ли видимая версия значение c21 для столбца C, по сути, повторно оценивая предикаты запроса.

Удаление записи b1 приводит к созданию хвостовой записи t8 со всеми null значениями.

Insert

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

В предлагаемом нами дизайне вставки мы обозначаем конец таблицы как диапазон вставки (insert range). Диапазон вставки по сути является предварительно выделенным диапазоном базовых RID для размещения будущих вставок. Для диапазона вставки мы выделили набор хвостовых страниц для добавления новых записей, которые мы называем «хвостовыми страницами уровня таблицы», хотя структурно нет никакой разницы между хвостовыми страницами уровня таблицы и обычными хвостовыми страницами. В хвостовых страницах уровня таблицы мы выделяем хвостовые страницы для всех столбцов (в отличие от обновлений, которые были ограничены только обновленными столбцами), потому что оператор вставки всегда предоставляет значение для каждого столбца (даже если это неявное значение null для столбца, допускающего значение null).

Структура вставки новых записей

Добавление нового диапазона вставки состоит из резервирования набора базовых RID (например, порядка миллионов) и набора хвостовых RID; эти два набора RID равны по размеру и выровнены. Таким образом, 10-й базовый RID в диапазоне вставки соответствует 10-му хвостовому RID в хвостовом диапазоне уровня таблицы (т.е. оба диапазона следуют одному и тому же порядку вставки). Выравнивание RID позволяет неявно адресовать для поиска записи в диапазоне вставки. Когда новая запись собирается быть вставлена ​​в таблицу, новая запись получает зарезервированный базовый RID в диапазоне вставки и соответствующий хвостовой RID в хвостовом диапазоне уровня таблицы. Если диапазон вставки заполнен, то создается новый диапазон вставки. Но ключевым руководящим принципом для вставки является удовлетворение свойства стабильности базовых страниц (т.е. только для чтения) за исключением столбца Indirection, который обновляется на месте. Таким образом, процедура вставки просто состоит из получения базовых и хвостовых RID, вставки фактической записи в хвостовые страницы уровня таблицы и установки столбца Indirection в базовой записи на null. В качестве альтернативы столбец Indirection может быть установлен на null при выделении страниц для диапазона вставки.