Архитектура системы
H-Store выполняется в grid’е компьютеров. Все объекты разделяются между узлами grid’а. Подобно тому, как это делалось в C-Store [SAB+05], пользователь может указать желаемый уровень K-надежности (K – это число узлов, при одновременном отказе которых система может восстановить работоспособность без потери выполняемых транзакций в течение заданного времени t).
В каждом узле grid строки таблиц размещаются вплотную одна к другой с использованием традиционной индексации на основе B-деревьев. Размер блока B-дерева настраивается в соответствии с размером блока кэша второго уровня используемой машины. Хотя вместо традиционных B-деревьев можно было бы использовать более эффективные варианты, основанные на знании поведения кэша [RR99, RR00], авторы решили прибегнуть к этой оптимизации только в том случае, если код поддержки индексации окажется существенным узким местом для производительности системы.
Каждый узел H-Store является однопотоковым, и в нем полностью, без прерываний выполняется каждая поступающая на обработку команда SQL. Каждый узел разбивается на несколько логических узлов в соответствии с числом ядер в соответствующем процессоре. Каждый логический узел трактуется как независимый физический узел со своими собственными индексами и областью хранения кортежей. Основная память реального физического узла разделяется между логическими узлами. Таким образом, у каждого логического узла имеется выделенный ЦП и единственный поток управления.
В среде OLTP в большинстве приложений для сокращения числа двухсторонних коммуникаций между приложением и СУБД используются хранимые процедуры. Поэтому в H-Store поддерживается всего лишь одна возможность СУБД – возможность выполнения предопределенной транзакции (выполнение транзакции может инициироваться в любом узле): Execute transaction (parameter_list).
В текущем прототипе для написания хранимых процедур используется язык C++, хотя у авторов имеются соображения по поводу возможности применения более удобных языков (см. разд. 6). В данной реализации в одном и том же процессе сочетаются логика приложения и непосредственное манипулирование базой данных. Этот подход позволяет добиться адекватной производительности при выполнении всего приложения внутри одной хранимой процедуры, в которой вызовы SQL производятся как вызовы локальных процедур (не на основе ODBC/JDBC), а данные возвращаются через совместно используемые массивы данных (опять же не на основе ODBC/JDBC).
Так же, как и в C-Store, не поддерживается журнал повторного выполнения операций (redo), а журнал отката (undo) поддерживается только при необходимости (обсуждение см. в подразделе 4.4). Журнал отката (если он ведется) сохраняется только в основной памяти и ликвидируется при фиксации транзакции.
Архитектурные соображения по поводу СУБД, ориентированных на OLTP
В этом разделе приводятся пять основных соображений, которые можно использовать в новом программном средстве управления данными, ориентированном на OLTP, для достижения производительности, существенно превосходящей производительность существующих РСУБД.
Дизайнер баз данных
Для обеспечения функционирования без потребности в ручках управления в среде H-Store будет создано средство автоматического проектирования физических схем баз данных (дизайнер баз данных), которое будет определять горизонтальное разделение, реплицирование и индексные поля.
В отличие от C-Store, где предполагалась поддержка массы материализованных представлений, уместных в среде с большинством операций только чтения, в H-Store сохраняются таблицы, определенные пользователями, и для достижения высокого уровня доступности используется стандартная репликация этих таблиц. Большая часть таблиц будет горизонтально разделена между всеми узлами grid’а. Для достижения высокого уровня доступности для каждого такого фрагмента таблицы (table fragment) должны иметься один или несколько партнеров (buddy), которые содержат в точности ту же информацию с использованием, возможно, другого физического представления (например, с другим порядком сортировки).
Цель дизайнера баз данных состоит в том, чтобы сделать как можно большее число классов транзакций одноузловыми. Используемая стратегия аналогична той, которая применялась в C-Store [SAB+05]. В C-Store для использования в среде хранилищ данных автоматически конструировались вездесущие схемы «звезда» или «снежинка», а теперь эти алгоритмы обобщаются для построения схем, являющихся «почти снежинками». Кроме того, в H-Store будут автоматически строиться схемы для поддержки распространенных в среде OLTP CTA-приложений, и будет использоваться ранее упоминавшаяся стратегия разделения базы данных между узлами на основе значений первичного ключа корневой таблицы с распределением по узлам кортежей других таблиц на основе кортежей корневой таблицы, потомками которых они являются. Будет использоваться и некоторые расширения, такие как оптимизация для только читаемых таблиц и вертикальное разделение, упоминавшиеся в разд. 3. Исследовательская задача авторов состоит в том, чтобы понять, насколько далеко можно распространить этот подход, и насколько успешным он окажется.
В настоящее время горизонтальное разделение и варианты индексации определяются вручную знающими пользователями.
Конец архитектурной эпохи
Современные РСУБД исходно создавались для аппаратной архитектуры, превалировавшей в 1970-е гг., а именно, для мультипроцессоров с общей памятью. В 1980-е гг. компании Sun и HP инициировали архитектуру мультипроцессоров с разделяемыми дисками, и большая часть СУБД была расширена возможностями для поддержки этой архитектуры. Кажется правдоподобным, что в следующем десятилетии будут доминировать компьютерные системы без общих ресурсов (shared-nothing), часто называемые grid- или блейд-компьютерами. Следовательно, требуется оптимизировать все СУБД в расчете на такую конфигурацию. Очевидная стратегия состоит в горизонтальном разбиении данных по узлам grid. Этот прием был впервые исследован в известном проекте Gamma [DGS+90].
Кроме того, никто не любит массовой модернизации оборудования. Поэтому любая новая система должна проектироваться в расчете на возможность инкрементного расширения аппаратных средств. Если grid-компьютер с N узлами не обеспечивает достаточной мощности, должна быть иметься возможность добавить к нему еще K узлов с получением системы, включающей N+K узлов. Более того, должна иметься возможность выполнения такой модернизации без потребности в каких-либо сложных действиях над используемой СУБД. Это позволит избавить системных администраторов от самого страшного для них ночного кошмара – массивной модернизации аппаратуры с последующей полной перезагрузкой данных и запуском системы заново.
Для достижения возможности инкрементной модернизации аппаратуры без выполнения каких-либо сложных действий над базами данных и СУБД требуются средства, отсутствующие в существующих системах. Например, должно иметься средство копирования частей базы данных с одного узла на другой без приостановки транзакций. Непонятно, как можно внедрить такую возможность в большинство существующих систем. Однако потребность в таком средстве можно включить в число требований к новой разработке, а потом эффективно его реализовать. В частности, в заново разработанном коде системы Vertica поддерживается в точности такая возможность.
Характеристики транзакций и схем
При использовании H-Store требуется заранее специфицировать рабочую нагрузку в виде набора классов транзакций. В каждом классе содержатся транзакции с одними и теми же операторами SQL и программной логикой, отличающиеся только значениями констант времени выполнения. Поскольку предполагается, что в системе OLTP не будут возникать непредвиденные (ad-hoc) транзакции, это требование не кажется неразумным. Такие классы транзакций должны заранее регистрироваться в H-Store, и не допускается, чтобы при их выполнении возникали задержки по вине пользователей (user stall) (задержки по другим причинам допускаются – например, они могут появиться в распределенной среде, когда одна машина ожидает, пока другая машина выполнит ее запрос). Аналогично, в H-Store предполагается, что заранее известным является и набор таблиц (логическая схема база данных), над которой будут выполняться транзакции.
Авторы обнаружили, что во многих базах данных OLTP у каждой таблицы, кроме одной, называемой корневой таблицей, имеется ровно один элемент соединения, представляющий собой связь n-к-1 со своим предком. Следовательно, схема является деревом связей 1-к-n. Такие схемы являются весьма распространенными. Например, клиенты производят заказы, в которых имеются позиции и графики выполнения. Для древовидных схем имеется очевидное горизонтальное разделение по узлам grid’а. Корневую таблицу можно разделить в соответствии с диапазонами значений первичного ключа или с использованием хеширования этих значений. Каждую таблицу-потомка можно разделить таким образом, что при выполнении любого эвкисоединения в каждом узле требуются данные, хранимые только в этом узле. Далее авторы более подробно обсуждают древовидные и не древовидные схемы.
Предположим, что при использовании древовидной схемы в каждом операторе каждой транзакции имеются предикаты сравнения по равенству с первичным ключом корневой таблицы (например, в приложениях электронной коммерции многие команды относятся к конкретному заказчику, и поэтому они будут содержать предикаты типа customer_id = 27).
Если использовать упомянутое выше горизонтальное разделение, то становится очевидно, что каждый оператор SQL в каждой транзакции будет являться локальным для одного узла. Если же, кроме того, каждый оператор каждой транзакции является локальным для одного и того же узла, то соответствующее приложение называется приложением над ограниченным деревом (constrained tree application, CTA). У CTA-приложений имеется то ценное свойство, что каждая транзакция может быть полностью выполнена в единственном узле. Как демонстрируется в , ценность таких одноузловых транзакций состоит в том, что транзакции могут выполняться без каких-либо задержек из-за коммуникаций с другими узлами grid’а (однако в некоторых случаях потребуется синхронизация реплик, чтобы транзакции над ними выполнялись в одном и том же порядке).
Если в каждой команде каждой транзакции CTA-приложения, кроме предиката сравнения по равенству с первичным ключом корневой таблицы, специфицируются предикаты сравнения по равенству с первичными ключами одной или нескольких таблиц, являющихся непосредственными потомками, то разделение древовидной схемы может быть иерархически расширено с включением в него этих таблиц-потомков. В этом случае, если это требуется, можно использовать более детальное разбиение.
CTA-приложения составляют важный класс одноузловых приложений, которые могут выполняться очень эффективно. Многолетний опыт авторов по разработке приложений баз данных для ведущих компаний позволяет заключить, что OLTP-приложения часто разрабатываются в точности в стиле CTA, а в других случаях часто возможна их декомпозиция для преобразования к CTA-приложениям [Hel07]. Помимо выяснения факта о распространенности CTA-приложений, авторов интересуют методы преобразования к одноузловым приложениям приложений, не относящихся к категории CTA. Интересной исследовательской проблемой является установление характеристик ситуаций, в которых это сделать можно. Здесь можно систематически применять два вида преобразований схем.
Во-первых, в схеме можно выделить все таблицы, которые являются только читаемыми, т.е. не изменяемыми ни одним классом транзакций. Эти таблицы можно реплицировать во всех узлах. Если приложение является CTA-приложением по отношению ко всем остальным таблицам, то после репликации только читаемых таблиц оно станет одноузловым.
Другой важный класс приложений составляют приложения с одноразовым использованием результатов (one-shot). Эти приложения обладают тем свойством, что все их транзакции можно выполнять параллельно без потребности в передаче промежуточных результатов между узлами. Более того, результаты предыдущих SQL-запросов никогда не требуются в последующих командах. В этом случае каждую транзакцию можно декомпозировать в некоторый набор одноузловых планов, каждый из которых можно выполнить в соответствующем узле.
Приложения часто можно сделать one-shot-приложениями путем вертикального разделения таблиц между узлами (необновляемые столбцы реплицируются). Например, так можно поступить с тестовым набором TPC-C (подробнее это обсуждается в разд. 5).
Некоторые классы транзакций являются двухфазными (two-phase) (или могут быть преобразованы к двухфазным). На первой фазе выполняется набор операций только чтения. На основании результатов этих запросов транзакция может быть аварийно завершена. Вторая фаза состоит из последовательности запросов и операций обновления, которые не могут нарушить какие-либо ограничения целостности. Использование свойства двухфазности в H-Store позволяет обойтись без журнала откатов. Авторы статьи установили, что многие транзакции, включая те, которые включены в TPC-C, являются двухфазными.
Класс транзакций является строго двухфазным (strongly two-phase), если он является двухфазным и, кроме того, обладает тем свойством, что операции первой фазы во всех узлах, участвующих в обработке данной транзакции, производят один и тот же результат по отношению к аварийному завершению или продолжению выполнения этой транзакции.
Кроме того, для каждого класса транзакций обнаруживаются все другие классы, транзакции которого являются коммутативными с транзакциями данного класса.Коммутативность определяется следующим образом:
Две параллельно выполняемые транзакции из одного и того же класса или из разных классов транзакций являются коммутативными, если при любом перекрытии их одноузловых подпланов образуется то же окончательное состояние базы данных, что и при любом другом перекрытии (в предположении, что обе транзакции фиксируются).
Класс транзакций, являющийся коммутативным со всеми другими классами транзакций (включая самого себя), называется стерильным (sterile).
В описываемых в алгоритмах H-Store используются свойства одноузлового выполнения, стерильности, двухфазности и строгой двухфазности. На основе своего опыта работы с ведущими коммерческими онлайновыми приложениями розничной торговли авторы установили уместность этих свойств, и они уверены, что подобные свойства будут обнаружены во многих других реальных приложениях баз данных.
Классы запросов
Все классы транзакций, кроме new_order, уже являются двухфазными, поскольку для них никогда не требуется аварийное завершение. Для транзакций класса new_order может потребоваться аварийное завершение, поскольку во входных данных могут быть указаны неверные номера товаров. Однако в спецификации TPC-C допускается выполнение в начале таких транзакций запросов для каждого номера товара для проверки правильности этих номеров. За счет такой трансформации логики этой транзакции все классы транзакций становятся двухфазными. На самом деле, все они являются строго двухфазными, поскольку таблица Item никогда не модифицируется, и, следовательно, по поводу всех транзакций new_order, отправляемых ко всем репликам, принимается одно и то же решение о продолжении или аварийном завершении.
После применения основной стратегии разделения и репликации все пять классов транзакций оказываются стерильными. В связи с этим поводу авторы делают три наблюдения.
Во-первых, транзакция new_order вставляет кортежи в таблицы Order table и New_Order, а также заносит данные о позициях заказа в таблицу Order-line. В каждом узле эти операции будут являться частью некоторого единственного подплана, и перекрывающихся операций не будет. Это гарантирует, что транзакция order_status не сможет увидеть данные еще не полностью обработанного заказа. Во-вторых, поскольку транзакции new_order и payment в TPC-C являются строго двухфазными, между узлами не требуется какая-либо дополнительная координация даже при обновлении данных удаленного склада.
В третьих, транзакцию stock_level разрешается выполнять как несколько транзакций, которые могут наблюдать уровни запасов разных товаров в разные моменты времени, лишь бы соответствующие данные происходили от зафиксированных транзакций. Но, поскольку, транзакции new_orders при необходимости аварийно завершаются до выполнения каких-либо модификаций, любая информация о запасах будет происходить только от зафиксированных транзакций (или транзакций, которые скоро будут зафиксированы).
Следовательно, все классы транзакций являются стерильными и строго двухфазными. По существу, уже это позволяет правильно выполнить TPC-C без какого-либо управления параллелизмом. Хотя можно было производить тестирование на этой конфигурации, авторы решили еще более повысить производительность, сделав все классы транзакций TPC-C классами с одноразовым использованием результатов.
После применения основной стратегии все классы транзакций, кроме new_order и payment являются одноузловыми и, следовательно, классами с одноразовым использованием результатов. Класс транзакций payment уже является классом с одноразовым использованием результатов, поскольку при обновлении кортежей удаленного склада отсутствует потребность в обменах данными. Однако транзакциям класса new_order требуется вносить в таблицу Order-line информацию о районе, в котором имеется в наличии товар, и эта информация может находиться в другом узле. Поскольку это поле никогда не изменяется, и в таблице Stock отсутствуют удаления и вставки, можно вертикально разделить эту таблицу и реплицировать ее только читаемые части во всех узлах. После применения этой схемы репликации совместно с основной стратегией класс транзакций new_order становится классом с одноразовым использованием результатов.
Таким образом, удается добиться того, что все классы транзакций становятся строго двухфазовыми классами с одноразовым использованием результатов. Если при обработке добавить короткую задержку, упоминавшуюся в , то свойства ACID достигаются без каких-либо накладных расходов.
Последнее произведенное усовершенствование происходит из того наблюдения, что при наличии упомянутой выше схемы, приводящей к одноразовому использованию результатов, транзакции остаются стерильными. Для выполнения стерильных транзакций не требуется задержка, необходимая для безопасного выполнения транзакций с одноразовым использованием ресурсов. Таким образом, тестируемая конфигурация была стерильной, строго двухфазовой со схемой, приводящей к одноразовому использованию результатов.
Трудно представить, чтобы какая-либо автоматическая программа смогла понять, что требуется для того, чтобы сделать классы транзакций TPC-C стерильными или классами с одноразовым использованием результатов. Эти классы транзакций пришлось бы кодировать знающему человеку. Однако авторам кажется, что большинство классов транзакций анализировать будет проще. Таким образом, успешность автоматического анализа классов транзакций является открытым вопросом.
Конец архитектурной эпохи, или Наступило время полностью переписывать системы управления данными
Майкл Стоунбрейкер, Сэмюэль Мэдден, Дэниэль Абади, Ставрос Харизопулос, Набил Хачем, Пат Хеллэнд
Пересказ: Сергей Кузнецов
Оригинал: , , , , , . The End of an Architectural Era (It's Time for a Complete Rewrite). Proceedings of VLDB, 2007, Vienna, Austria
Майкл Стоунбрейкер, Сэмюэль Мэдден, Дэниэль Абади, Ставрос Харизопулос, Набил Хачем, Пат Хеллэнд
Пересказ: Сергей Кузнецов
Оригинал: , , , , , . The End of an Architectural Era (It's Time for a Complete Rewrite). Proceedings of VLDB, 2007, Vienna, Austria
Майкл Стоунбрейкер, Сэмюэль Мэдден, Дэниэль Абади, Ставрос Харизопулос, Набил Хачем, Пат Хеллэнд
Пересказ: Сергей Кузнецов
Оригинал: , , , , , . The End of an Architectural Era (It's Time for a Complete Rewrite). Proceedings of VLDB, 2007, Vienna, Austria
Майкл Стоунбрейкер, Сэмюэль Мэдден, Дэниэль Абади, Ставрос Харизопулос, Набил Хачем, Пат Хеллэнд
Пересказ: Сергей Кузнецов
Оригинал: , , , , , . The End of an Architectural Era (It's Time for a Complete Rewrite). Proceedings of VLDB, 2007, Vienna, Austria
Майкл Стоунбрейкер, Сэмюэль Мэдден, Дэниэль Абади, Ставрос Харизопулос, Набил Хачем, Пат Хеллэнд
Пересказ: Сергей Кузнецов
Оригинал: , , , , , . The End of an Architectural Era (It's Time for a Complete Rewrite). Proceedings of VLDB, 2007, Vienna, Austria
Майкл Стоунбрейкер, Сэмюэль Мэдден, Дэниэль Абади, Ставрос Харизопулос, Набил Хачем, Пат Хеллэнд
Пересказ: Сергей Кузнецов
Оригинал: , , , , , . The End of an Architectural Era (It's Time for a Complete Rewrite). Proceedings of VLDB, 2007, Vienna, Austria
Краткий обзор H-Store
В этом разделе обсуждается, как в проекте H-Store используются ранее описанные свойства для реализации очень эффективной системы баз данных, ориентированной на OLTP.
Многопотоковость и управление ресурсами
OLTP-транзакции являются очень легковесными. Например, в наиболее тяжелой транзакции из TCP-C считывается около 400 записей. При работе с базами данных в основной памяти полезная работа такой транзакции занимает менее одной миллисекунды даже при использовании низкопроизводительных компьютеров. Кроме того, в большинстве известных авторам статьи средах OLTP отсутствуют «задержки по вине пользователей» («user stall»). Например, когда на сайте Amazon пользователь нажимает на кнопку «buy it», он активизирует OLTP-транзакцию, данные от которой будут возвращены пользователю только после ее завершения. По причине отсутствия дисковых операций и задержек по вине пользователей фактическая продолжительность OLTP-транзакции является минимальной. В таком мире имеет смысл выполнять все команды SQL в рамках последовательных транзакций с использованием однопотоковой модели исполнения, а не тратить время и другие ресурсы на изоляцию параллельно выполняемых операторов.
Современные РСУБД представляют собой тщательно разработанные многопотоковые системы, ориентированные на полное использование ресурсов ЦП и дисков. Это позволяет выполнять в параллель много запросов. Кроме того, в этих системах имеются подсистемы, предназначенные для предотвращения перегрузки системных ресурсов, чтобы не возникла ситуация исчерпания IP-соединений, дескрипторов файлов, основной памяти, требуемой для выполнения сортировок, и т.д. В однопотоковой системе не требуется подсистема регулирования ресурсов.
При использовании однопотоковой модели исполнения не требуются структуры данных, для которых поддерживается параллельный доступ. Поэтому можно полностью обойтись, например, без сложного кода, требуемого для поддержки параллельного доступа к B-деревьям. Это позволяет создавать более надежные системы, обладающие более высокой производительностью.
Может возникнуть вопрос: «А как быть с долго выполняемыми командами?». Ответ состоит в том, что в реальных OLTP-системах таких команд просто нет. Во-первых, операции, которые могли бы привести к долговременно выполняемым транзакциям, такие как ввод данных для покупки в Internet-магазине, обычно расщепляются на несколько транзакций, чтобы время выполнения каждой из них оставалось небольшим. Другими словами, в правильно разработанном OLTP-приложении поддерживаются только короткие транзакции. Во-вторых, долго выполняемые произвольные (ad-hoc) запросы направляются в систему хранилища данных, которая оптимизируется для выполнения именно таких операций. Нет никаких оснований заставлять систему OLTP решать проблемы, не относящиеся к OLTP. Такой подход применяется только в «безразмерном» мире.
Некоторые комментарии по поводу мира, в котором один размер не является пригодным для всех
Если признать результаты этой статьи убедительными, то мы движемся по направлению к миру с не менее чем пятью специализированными программными средствами, миру, в котором не остается места для унаследованных «безразмерных» систем. В этом разделе рассматриваются некоторые последствия таких архитектурных изменений.
Никаких ручек управления
Существующие системы строились в ту эпоху, когда ресурсы были чрезвычайно дорогими, и за каждой вычислительной системой присматривали чародеи в белых лабораторных халатах, отвечающие за обслуживание, электропитание, настройку и оптимизацию системы. В то время компьютеры были дорогими, а люди – дешевыми. Теперь все изменилось. Основные расходы IT-подразделений уходят на содержание персонала.
Единственным выходом из этого положения является перевод систем на «самообслуживание» (самовосстановление, автоматическое техническое обслуживание, автоматическую настройку и т.д.). Однако во всех РСУБД имеется огромное количество ручек управления, унаследованных от прошедшей эпохи. Безусловно, все поставщики пытаются обеспечить автоматические средства, устанавливающие эти ручки управления без вмешательства человека. Однако из унаследованного кода невозможно удалить какие-либо имеющиеся возможности. Поэтому в дополнение к операциям с ручками управления, устанавливаемыми людьми, появится операция включения автоматического режима управления, что приведет к еще большему объему системной документации. Кроме того, в настоящее время средства автоматической настройки в РСУБД, с которыми знакомы авторы статьи, не позволяют добиться производительности системы, близкой к той, которую может обеспечить квалифицированный администратор баз данных. До тех пор, пока средства настойки в существующих системах не будут значительно улучшены, администраторы будут продолжать крутить ручки управления. Намного лучшим решением является полный пересмотр процесса настройки и создание новой системы без явных ручек управления.
Основная память
В конце 1970-х гг. в больших вычислительных машинах имелось где-то около мегабайта основной памяти. Сегодня распространенным явлением является наличие нескольких гигабайт основной памяти в персональных компьютерах, а в больших машинах объем памяти достигает сотни гигабайт. Через несколько лет не будет редкостью терабайтная основная память. Вполне представима grid-система общей стоимостью менее 50000 долларов, состоящая из 20 узлов без совместно используемых ресурсов, в каждом из которых имеется 32 Гб основной памяти (с возможностью расширения в ближайшем будущем до 100 Гб). По существу, в основной памяти прямо сейчас или в близком будущем можно разместить любую базу данных объемом менее терабайта. Объем подавляющего большинства баз данных OLTP не превосходит одного терабайта, и этот объем возрастает достаточно медленно. Показательным фактом, например, является то, что в тестовой базе данных TPC-C для одной физической оптовой базы (склада) требуется около 100 Мб. В очень крупном торговом предприятии может иметься 1000 складов, для хранения данных которых требуется около 100 Гб памяти, что вполне укладывается в упомянутые выше ограничения для размещения в основной памяти.
В связи с этим, авторы полагают, что если не в настоящее время, то через несколько лет рынок OLTP можно будет считать рынком баз данных, поддерживаемых в основной памяти. Соответственно, у производителей сегодняшних РСУБД имеются решения проблемы баз данных в основной памяти с использованием дисков. Коротко говоря, 30-летнее воздействие закона Мура приводит к вытеснению из области OLTP-приложений реляционной архитектуры, ориентированной на работу с данными на дисках.
Однако, хотя на рынке имеется несколько продуктов управления базами данных в основной памяти, таких как TimesTen и SolidDB, и эти системы унаследовали черты System R. К унаследованным чертам относится использование для восстановления журнала, поддерживаемого на дисках, и применение динамических блокировок, что приводит к существенным накладным расходам, снижающим производительность системы.
Предположения о транзакциях, обработке и среде
Если предположить наличие grid’а из вычислительных систем с хранением баз данных в основной памяти, наличие встроенных средств поддержки высокого уровня доступности, отсутствие задержек транзакций по вине пользователей и продолжительность работы транзакций в пределах одной миллисекунды, то становятся очевидными следующие выводы:
Долговременно хранимый журнал повторного выполнения операций почти гарантированно является существенным узким местом для достижения высокой производительности. Даже при использовании групповой фиксации транзакций принудительное выталкивание на диск записей о фиксации может добавить миллисекунды к общему времени выполнения каждой транзакции. Обсуждавшаяся ранее система поддержки высокого уровня доступности и обработки отказов позволяет легко освободиться от этой архитектурной особенности. Если отказаться от журнала повторного выполнения операций, то, вероятно, следующим по значимости узким местом будет вызов операций в системе и передача ответных параметров приложению. Накладные расходы интерфейсов в стиле JDBC/ODBC станут обременительными, и придется использовать что-либо более эффективное. В частности, авторы статьи выступают за выполнение логики приложения – в форме хранимых процедур – «в процессе» внутри системы базы данных вместо того, чтобы испытывать накладные расходы межпроцессных взаимодействий, свойственные традиционной клиент-серверной модели. Во всех случаях, когда это целесообразно, следует отказаться и от журнала откатов, поскольку он тоже будет являться существенным узким местом. Следует приложить все усилия, чтобы избавиться от затрат на традиционные динамические блокировки для управления параллелизмом, которые тоже будут являться узким местом. Вероятно, будет обременительной и синхронизация на основе «защелок» (latching), связанная с доступом к одним и тем же структурам данных из нескольких потоков управления. Притом, что время выполнения транзакций будет коротким, эти накладные расходы можно устранить с незначительным падением производительности путем перехода к однопотоковой модели исполнения. По мере возможности следует избегать применения двухфазного протокола фиксации (two-phase commit protocol, 2PC) распределенных транзакций, поскольку сетевые задержки, возникающие при двухсторонних коммуникациях в 2PC, часто достигают порядка миллисекунд.
Возможность отказаться от управления параллелизмом, обработки фиксации распределенных транзакций и журнализации откатов зависит от нескольких характеристик схем и транзакций, которые обсуждаются в следующем подразделе.
Реализация
Авторы реализовали некоторый вариант TPC-C на H-Store и на очень популярной коммерческой РСУБД. Для обеих систем использовался один и тот же драйвер, генерирующий транзакции с наивысшей скоростью без моделирования времени на размышления. В обе системы транзакции доставлялись с использованием TCP/IP. Все классы транзакций реализовывались как хранимые процедуры. В H-Store логика транзакций кодировалась на C++, и для обращения к подсистеме выполнения запросов использовались локальные вызовы процедур. Для коммерческой системы логика транзакций программировалась с применением проприетарного языка хранимых процедур. Ни в одну из систем не включались средства высокой доступности и коммуникаций с терминалами пользователей.
Обе СУБД запускались на компьютере с двухъядерным процессором, работающим на частоте в 2.8 Ггц, с 4 Гб основной памяти и четырьмя жесткими дисками SATA емкостью по 250 Гб. В обеих СУБД использовалось горизонтальное разделение данных.
Реляционная модель не обязательно является решением
Пережив продолжительные дебаты 1974 года [Rus74] и дискуссии между защитниками Codasyl и реляционной модели данных, авторы не желают более «кормить эту священную корову». Однако они считают уместным обсудить модель данных (или модели данных), на которой они основывают свои системы. В 1970-е гг. в мире СУБД имелись только приложения обработки бизнес-данных, и идея Теда Кодда о нормализации данных в плоские таблицы хорошо послужила сообществу баз данных в течение 30 лет. Однако теперь имеются новые области приложений, которые необходимо принимать во внимание: хранилища данных, Web-ориентированный поиск, аналитика в реальном времени и полуструктурированные данные. Авторы предлагают следующие наблюдения.
В области хранилищ данных почти сто процентов схем относятся к категориям «звезда» или «снежинка», содержащим центральную таблицу фактов с соединениями 1-к-n с окружающими ее таблицами измерений, которые, в свою очередь, могут участвовать в соединениях 1-к-n с таблицами измерений второго уровня и т.д. Хотя схемы «звезда» и «снежинка» легко моделируются с использованием реляционных схем, на самом деле, в этой среде проще и естественнее использовать модель «сущности-связи». Более того, в E/R-модели проще формулируются запросы к хранилищам данных. Наконец, операции над хранилищами данных в реляционной реализации являются существенно более дорогостоящими. Например, операцию, эквивалентную операции изменения ключа строки в таблице измерений, можно гораздо быстрее выполнить в реализации на основе E/R-модели.
В области обработки потоковых данных имеются следующие потребности:
обработка потоков сообщений, поступающих с высокой скоростью; установление соотношений таких потоковых данных с хранимыми данными.
Для решения обеих задач принято использовать язык StreamSQL, обобщение SQL, позволяющее одновременно указывать в разделе FROM SQL-запроса хранимые таблицы и потоки.
Этот язык появился в результате пионерской работы [ABW06], выполненной в Стэндфордском университете, и в настоящее время активно обсуждается его стандартизация. Конечно, в StreamSQL поддерживаются реляционные схемы как для таблиц, так и для потоков.
Однако в коммерческих каналах, таких как Reuters, Infodyne и т.д., не фиксирована модель данных, которой должны следовать передаваемые сообщения. Некоторые из них являются плоскими и хорошо укладываются в реляционную схему. Но имеются и иерархические сообщения, например, в канале FX по поводу курсов иностранных валют. Системы обработки потоковых данных, такие как StreamBase и Coral8, в настоящее время поддерживают только плоские (реляционные) сообщения. В таких системах входной адаптер должен нормализовывать иерархические объекты в несколько типов плоских сообщений для их дальнейшей обработки. Но, к сожалению, довольно неприятным занятием является соединение частей исходного сообщения, когда требуется обработка нескольких компонентов иерархии.
Авторы статьи ожидают, что для решения этой проблемы поставщики потоковых систем будут активно переходить к использованию иерархических моделей данных, и тогда они, несомненно, отойдут от принципов Теда Кодда.
Очевидно, реляционная модель никогда не использовалась в области текстовой обработки.
В любой СУБД, ориентированной на обработку научных данных, такой как ASAP [SBC+07], в качестве базового типа данных, вероятно, будут использоваться многомерные массивы, а не таблицы.
В последнее время ведутся активные обсуждения моделей данных, подходящих для представления полуструктурированных данных. Конечно, энергично обсуждается чрезмерная сложность спецификации XMLSchema [SC05]. Имеются сторонники использования для таких данных RDF [MM04] и те, кто утверждает, что RDF можно эффективно хранить в реляционной базе данных с хранением данных по столбцам [AMM+07]. Авторы считают достаточным сказать, что имеется много идей, на которых может основываться дальнейшее развитие этой области.
Реляционная модель разрабатывалась для «безразмерного» мира.При переходе к специализированным системам для каждой из них можно подобрать модель данных, наилучшим образом соответствующую конкретным особенностям этой системы.
Резюме и планы на будущее
В последней четверти прошлого века произошел ряд серьезных изменений:
Рынки СУБД: произошел переход от одного рынка обработки бизнес-данных к набору рынков с разными требованиями. Необходимые возможности: к числу новых требований относятся поддержка архитектуры «shared nothing» и высокий уровень доступности. Технология: почти все изменилось благодаря наличию большого объема основной памяти, возможности «горячего» резервирования и существованию Web.
Результатом этих изменений является следующее:
предсказываемая кончина эпохи «безразмерности»; несоответствие существующих реляционных реализаций требованиям какого бы то ни было сегмента рынка; необходимость переосмысления моделей данных и языков запросов, соответствующих особенностям специализированных программных средств, которые, по ожиданиям авторов статьи, будут доминировать на различных вертикальных рынках.
Прототип H-Store демонстрирует выигрыш в производительности, который удалось получить за счет отказа от традиционного образа мышления. Конечно, несмотря на получение ободряющих начальных результатов, описанных в данной статье, имеется ряд областей, в которых необходимо проведение дополнительных исследований и разработок. В частности:
Требуются исследования возможности автоматического определения одноузловых, двухфазных приложений с одноразовым использованием результатов. Также требуются автоматические средства, которые могли бы обеспечить разделение данных, ведущее к появлению у приложений этих свойств. Развитие технологии многоядерных процессоров наводит на мысль об интересных оптимизациях, связанных с совместной работой логических узлов, физически располагающихся в одном и том же компьютере. Требуется тщательное исследование эффективности различных стратегий управления транзакциями, общие черты которых были описаны в разд. 3. Изучение накладных расходов различных компонентов систем OLTP – журнализации, обработки транзакций и двухфазной фиксации, блокировок, JDBC/ODBC и т.д. – могло бы помочь установить, какие аспекты архитектуры традиционных СУБД приводят к появлению большинства наблюдаемых накладных расходов. После устранения всех этих накладных расходов общая производительность H-Store определяется эффективностью работы со структурами основной памяти, из чего следует важность оптимизации этих структур.
Например, авторы обнаружили, что в H- Store достигается существенное повышение скорости обработки транзакций за счет простой оптимизации путем представления только читаемых таблиц в виде массивов. Если потребуется «бесшовное» сосуществование систем, подобных H-Store, с системами хранилищ данных, то существенной окажется интеграция со средствами поддержки хранилищ данных – путем использования, например, памяти с одноразовой записью и периодической выгрузки содержимого базы данных в хранилище данных.
Коротко говоря, текущая ситуация, сложившаяся в сообществе баз данных, напоминает авторам статьи период 1970-1985 гг., когда производился поиск наилучшего способа построения серверов баз данных, и происходили существенные изменения как в коммерческих продуктах, так и в составе их поставщиков. Это было время интенсивных обсуждений, множества новых идей и существенных потрясений.
Авторы предсказывают, что следующие пятнадцать лет будут не менее бурными.
Результаты
В этой конфигурации на H-Store выполнялось 70416 транзакций TPC-C в секунду, а на коммерческой системе авторы смогли достичь скорости всего лишь в 850 транзакций в секунду, и для этого потребовалось несколько дней интенсивной работы профессионального администратора баз данных, специализирующегося на администрировании именно этого продукта. Тем самым, H-Store оказалась быстрее в 82 раза (почти на два порядка).
В соответствии с предыдущими обсуждениями, приведенными в этой статье, узким местом коммерческих систем являются накладные расходы на журнализацию. В данном случае коммерческая система проводила 2/3 времени в подсистеме журнализации. Один из авторов статьи потратил много часов в попытках настроить подсистему журнализации (ведение журнального файла на выделенном диске, изменение размера записи о групповой фиксации; все, что было можно). При полном отключении журнализации и отсутствии других узких мест пропускная способность возрастала до 2500 транзакций в секунду.
Как кажется авторам, следующим узким местом традиционной СУБД была подсистема управления параллелизмом. В будущих экспериментах они планируют выяснить, какой вклад в общие накладные расходы этой подсистемы вносят журнализация повторного выполнения операций, журнализация откатов, защелки (latching) и блокировки.
Наконец, хотя авторы не реализовали полностью всю спецификацию TPC-C (например, они не моделировали время ожидания), они считают полезным сравнить свою частичную реализацию с данными об наилучших результатах прогонов TPC-C, представленными на Web-сайте TPC. Наилучшим результатом прогона эталонных тестов TPC-C является показатель 4 миллиона транзакций в минуту, или 133000 транзакций в секунду. Этот результат был получен на машине с разделяемой общей памятью и 128 процессорными ядрами, так что в этой реализации пришлось примерно 1000 транзакций в секунду на одно ядро. Рекомендуется сравнить этот результат с 425 транзакциями в секунду на одно ядро в коммерческой системе, выполняемой на небольшом настольном компьютере, и с 35000 транзакциями на одно ядро в H-Store!
Результаты этого тестирования показывают, что на системе, разработанной в соответствии с принципами H-Store, можно добиться повышения производительности при выполнении тестов TPC-C примерно на два порядка величин.
SQL также не является решением
SQL является «безразмерным» языком. В мире OLTP никого и никогда не интересуют служащие, зарабатывающие больше своих менеджеров. На самом деле, как отмечалось ранее, в этом мире вообще не задаются непредвиденные запросы. Следовательно, в этом случае достаточно было бы иметь некоторый язык, который был бы более ограниченным, чем SQL. По соображениям производительности вездесущими являются хранимые процедуры. В мире хранилищ данных требуется другое подмножество SQL, поскольку здесь распространены сложные непредвиденные запросы, но нет хранимых процедур. Поэтому для специализированных программных средств управления данными можно иметь специализированные языки, ориентированные на конкретный вертикальный рынок и не обладающие устрашающей сложностью, свойственной SQL.
Переосмысление количества одновременно существующих языков и их сложности будет обладать колоссальным положительным побочным эффектом. В настоящее время SQL – это унаследованный язык со многими известными серьезными недостатками, ряд из которых отмечался Крисом Дейтом еще два десятка лет тому назад [Dat84]. Следующая попытка разработки языков может оказаться более удачной.
При переосмыслении языков доступа к данным авторам вспоминается яростная дискуссия 1970-х гг. С одной стороны, имелись сторонники подъязыков данных, для которых могли бы иметься интерфейсы с любыми языками программирования. Это привело к появлению интерфейсов с высокими накладными расходами, таких как JDBC и ODBC. Кроме того, эти интерфейсы очень трудно использовать из традиционного языка программирования. С другой стороны, некоторые члены сообщества баз данных предлагали намного более привлекательные возможности доступа к базам данных, встраиваемые в языки программирования. Типичными представителями этих языковых средств в 1970-е гг. являлись Pascal R [Sch80] и Rigel [RS79]. В обоих этих средствах обеспечивалась полная интеграция со средствами языков программирования, такими как организация логики управления, локальные переменные и т.д.
С теми же целями Крис Дейт предлагал расширение языка PL/1 [Dat76].
Как видно, ни один из этих языков не вошел в широкую практику, и победу одержало направление поъязыков данных. Сообщество баз данных средства разработало невероятно безобразные средства сопряжения языков программирования с подъязыком баз данных, и результатом являются низко производительные системы, происходящие из прошедшей эпохи. Поэтому авторы статьи выступают за полный отказ от подъязыков данных в пользу встраивания в языки программирования средств доступа к данным.
В сообществе языков программирования наблюдается бурное развитие «малых языков», таких как Python, Perl, Ruby и PHP. Идея состоит в том, чтобы для решения любой конкретной задачи можно было использовать язык, наиболее подходящий именно в этом случае. Малые языки привлекательны еще и тем, что их легче изучать, чем языки общего назначения. При взгляде со стороны это явление кажется симптомом конца эпохи «безразмерности» в мире языков программирования.
У малых языков имеются два очень приятные свойства. Во-первых, в большинстве случаев они относятся к категории open source и поэтому могут изменяться сообществом. Во-вторых, их не так страшно модифицировать, как современные языки общего назначения. В связи с этим, авторы выступают за модификацию малых языков с целью включения в них встроенных средств доступа к данным.
В настоящее время любимым примером этого подхода у авторов является Ruby-on-Rails. Эта система основана на малом языке Ruby, расширенном интегрированной поддержкой доступа к данным и манипулирования ими на основе паттерна программирования «model-view-controller». Ruby-on-Rails компилируется в стандартный JDBC, но вся сложность этого интерфейса скрывается.
Поэтому авторы планируют отказаться от применения языка C++ для программирования хранимых процедур в среде H-Store и перейти к использованию Ruby-on-Rails. Конечно, подсистема поддержки времени исполнения Ruby-on-Rails должна быть скомпонована в одном адресном пространстве совместно с СУБД, и ее необходимо изменить, чтобы вызовы служб СУБД производились с использованием высокопроизводительных локальных вызовов процедур, а не JDBC.
Сравнение производительности
TPC-C выполняется над схемой, показанной на рис. 1, и для этого тестового набора определяются пять классов транзакций (new_order, payment, order status, delivery и stock_level).
Рис. 1. Схема TPC-C (воспроизводится из спецификации TPC-C версии 5.8.0, стр. 10)
По причине ограниченности объема в этой статье не приводится код этих транзакций; читатели отсылаются к спецификации TPC-C [TPCC]. В табл. 1 резюмируется их поведение.
Таблица 1. Классы транзакций TPC-C
| new_order | Размещает заказ пользователя. 90% всех заказов может быть полностью удовлетворено со складов, находящихся неподалеку от месторасположения пользователей («домашних» складов пользователей); для 10% заказов требуется доступ к удаленным складам. Эта транзакция производит выборки из базы данных и модифицирует данные. Минимальное процентное соотношение таких транзакций в смеси запускаемых транзакций не задается, но их должно быть около 50%. |
| payment | Обновляет остаток средств пользователей и поля sales в таблицах Warehouse и District. 85% обновлений относится к «домашним» складам, 15% – к удаленным складам. Транзакция производит выборки из базы данных и модифицирует данные. В смеси должно присутствовать не менее 43% таких транзакций. |
| order-status | Запрашивает состояние последнего заказа пользователя. Только читающая транзакция. В смеси должно присутствовать не менее 4% таких транзакций. |
| delivery | Выбирает склад и для каждого из 10 районов «доставляет» заказ, что означает удаление записи из таблицы new_order и обновление остаток средств пользователя. Каждая доставка может быть отдельной транзакцией. В смеси должно присутствовать не менее 4% таких транзакций. |
| stock-level | Находит изделия с уровнем запасов, меньшим некоторого порогового значения. Только читающая транзакция. Должна читать зафиксированные данные, но не требует сериализуемости. В смеси должно быть не менее 4% таких транзакций. |
Имеются три возможных подхода к эффективной реализации TPC-C на основе H-Store.
Во-первых, этот тестовый набор можно было бы выполнить на компьютере с одним одноядерным процессором. Это автоматически привело бы к тому, что все классы транзакций стали бы одноузловыми, и каждая транзакция могла бы выполняться от начала до завершения в однопотоковой среде. В парном узле, обеспечивающем высокий уровень доступности, будет поддерживаться тот же порядок выполнения. Как будет показано немного ниже, все классы транзакций TPC-C могут быть сделаны строго двухфазными. Поэтому все транзакции в обоих узлах будут либо зафиксированы, либо аварийно прекращены. Следовательно, при работе системы в одном узле при наличии парного узла, обеспечивающего высокий уровень доступности, свойства ACID удается достичь без каких бы то ни было накладных расходов.
Для использования компьютеров с одним или несколькими многоядерными процессорами требуется тщательное кодирование транзакций TPC-C для достижения их свойств стерильности или одноразового использования результатов и обеспечения функционирования без накладных расходов в многоузловой среде. Сначала авторы обсуждают разделение данных.
Схема базы данных TPC-C не является древовидной. Такой ее делает наличие таблицы Item и связи между таблицами Order-line и Stock. Однако таблица Item только читается, и ее можно реплицировать в каждом узле. Таблицу Order-line можно разделить между всеми узлами в соответствии со значениями столбца Order. При проведении таких репликации и разделения схема декомпозируется таким образом, что в каждом узле содержится подмножество кортежей, относящихся к некоторому разделу таблицы складов по районам. Это далее будет называться основной стратегией H-Store для разделения и репликации.
Ссылки
[ABW06] A. Arasu, S. Babu, and J. Widom. “The CQL Continuous Query Language: Semantic Foundations and Query Execution.” The VLDB Journal, 15(2), June 2006.
[ACL87] Agrawal, R., Carey, M. J., and Livny, M. “Concurrency control performance modeling: alternatives and implications.” ACM Trans. Database Syst. 12(4), Nov. 1987.
[AMM+07] D. Abadi, A. Marcus, S. Madden, and K. Hollenbach. “Scalable Semantic Web Data Management Using Vertical Partitioning.” In Proc. VLDB, 2007.
[Ants07] ANTs Software. ANTs Data Server - Technical White Paper, 2007.
[BSR80] Bernstein, P.A., Shipman, D., and Rothnie, J. B. “Concurrency Control in a System for Distributed Databases (SDD-1).” ACM Trans. Database Syst. 5(1), March 1980.
[Bon02] P. A. Boncz. “Monet: A Next-Generation DBMS Kernel For Query-Intensive Applications.” Ph.D. Thesis, Universiteit van Amsterdam, Amsterdam, The Netherlands, May 2002.
[Dat76] C. J. Date. “An Architecture for High-Level Language Database Extensions.” In Proc. SIGMOD, 1976.
[Dat84] Date, C. J. “A critique of the SQL database language.” In SIGMOD Record 14(3):8-54, Nov. 1984.
[DGS+90] Dewitt, D. J., Ghandeharizadeh, S., Schneider, D. A., Bricker, A., Hsiao, H., and Rasmussen, R. “The Gamma Database Machine Project.” IEEE Transactions on Knowledge and Data Engineering 2(1):44-62, March 1990.
[Hel07] P. Helland. “Life beyond Distributed Transactions: an Apostate's Opinion.” In Proc. CIDR, 2007.
[HM93] Herlihy, M. and Moss, J. E. “Transactional memory: architectural support for lock-free data structures.” In Proc. ISCA, 1993.
[KL81] Kung, H. T. and Robinson, J. T. “On optimistic methods for concurrency control.” ACM Trans. Database Syst. 6(2):213-226, June 1981.
[LM06] E. Lau and S. Madden. “An Integrated Approach to Recovery and High Availability in an Updatable, Distributed Data Warehouse.” In Proc.
VLDB, 2006.
[MHL+92] Mohan, C., Haderle, D., Lindsay, B., Pirahesh, H., and Schwarz, P. “ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging.” ACM Trans. Database Syst. 17(1):94-162, March 1992.
[Mil89] Mills, D. L. “On the Accuracy and Stability of Clocks Synchronized by the Network Time Protocol in the Internet System.” SIGCOMM Comput. Commun. Rev. 20(1):65-75, Dec. 1989.
[MM04] Manola, F. and Miller, E. (eds). RDF Primer. W3C Specification, February 10, 2004.
[RR99] Rao, J. and Ross, K. A. “Cache Conscious Indexing for Decision-Support in Main Memory.” In Proc. VLDB, 1999.
[RR00] Rao, J. and Ross, K. A. “Making B+- trees cache conscious in main memory.” In SIGMOD Record, 29(2):475-486, June 2000.
[RS79] L. A. Rowe and K. A. Shoens. “Data Abstractions, Views and Updates in RIGEL.” In Proc. SIGMOD, 1979.
[Rus74] Randall Rustin (Ed.): Proceedings of 1974 ACM SIGMOD Workshop on Data Description, Access and Control, Ann Arbor, Michigan, May 1-3, 1974, 2 Volumes.
[SAB+05] M. Stonebraker, D. Abadi, A. Batkin, X. Chen, M. Cherniack, M. Ferreira, E. Lau, A. Lin, S. Madden, E. O’Neil, P. O’Neil, A. Rasin, N. Tran, and S. Zdonik. “C-Store: A Column-oriented DBMS.” In Proc. VLDB, 2005.
[SBC+07] M. Stonebraker, C. Bear, U. Cetintemel, M. Cherniack, T. Ge, N. Hachem, S. Harizopoulos, J. Lifter, J. Rogers, and S. Zdonik. “One Size Fits All? - Part 2: Benchmarking Results.” In Proc. CIDR, 2007.
Перевод на русский язык: “Пригоден ли один размер для всех? Часть 2: результаты тестовых испытаний”
[SC05] M. Stonebraker and U. Cetintemel. “One Size Fits All: An Idea whose Time has Come and Gone.” In Proc. ICDE, 2005.
Перевод на русский язык: “"Один размер пригоден для всех": идея, время которой пришло и ушло”
[Sch80] Schmidt, J.W. et al. “Pascal/R Report.” U Hamburg, Fachbereich Informatik, Report 66, Jan 1980.
[TPCC] The Transaction Processing Council. TPC-C Benchmark (Revision 5.8.0), 2006.
Управление транзакциями, репликация и восстановление
Поскольку в H-Store поддерживается не менее двух копий каждой таблицы, реплики должны быть транзакционно обновляемыми. Это достигается за счет того, что любой SQL-запрос адресуется к любой соответствующей реплике, а операции обновления выполняются надо всеми соответствующими репликами.
Кроме того, при входе в H-Store каждой транзакции назначается временная метка (timestamp), имеющая формат (site_id, local_unique_timestamp). Если поддерживать порядок на множестве узлов grid, то временные метки будут являться уникальными и полностью упорядоченными. Предполагается, что локальные часы, генерирующие локальные временные метки, взаимно синхронизируются с использованием какого-либо алгоритма типа NTP [Mil89].
Имеется несколько ситуаций, в которых технология H-Store позволяет упростить протоколы управления параллелизмом и фиксации.
Одноузловые (single-sited) транзакции / транзакции с одноразовым использованием результатов (one-shot): Если все классы транзакций являются одноузловыми или содержат только транзакции с одноразовым использованием результатов, то каждая индивидуальная транзакция может быть направлена для выполнения в узлы с нужными копиями данных и полностью там выполнена. Если не все классы транзакций являются стерильными, то каждый узел выполнения транзакций должен подождать в течение небольшого промежутка времени (для учета сетевых задержек) поступления транзакций от других инициаторов, чтобы выполнение транзакций происходило в порядке временных меток. За счет незначительного увеличения времени задержки все реплики будут обновляться в одном и том же порядке, а предельные значения задержек в локальной сети не будут превышать миллисекунды. Этот будет гарантировать идентичность состояния всех реплик. Следовательно, не может произойти рассогласование реплик. Кроме того, либо во всех репликах будут зафиксированы изменения от данной транзакции (если она заканчивается фиксацией), либо все они останутся неизменными (если транзакция заканчивается аварийно). Следовательно, любая транзакция может локально фиксироваться или аварийно завершаться с гарантией того, что у всех реплик останется одно и то же состояние.
Не требуются журнал повторного выполнения операций (redo), управление параллелизмом и обработка распределенной фиксации.
Двухфазовые транзакции: Не требуется журнал откатов (undo). Для транзакций, которые обладают этим свойством совместно со свойствами, рассмотренными в предыдущем пункте, вообще не требуются системные средства поддержки.
Стерильные транзакции: Если все транзакции являются стерильными, то их выполнение обычно будет производиться без какого-либо управления параллелизмом. Более того, в этом случае исчезает потребность в назначении временных меток и выполнении транзакций в одном и том же порядке надо всеми репликами. Однако если в обработке транзакции принимает участие несколько узлов, то отсутствует гарантия того, что все узлы аварийно ее завершат, или все они продолжат ее выполнение. В этом случае исполнители в конце первой фазы должны посылать диспетчеру выполнения сообщения «аварийное завершение» или «продолжение выполнения», а диспетчер должен пересылать эту информацию в узлы исполнителей. Следовательно, в конце первой фазы требуется производить стандартную обработку фиксации. Этих дополнительных накладных расходов можно избежать, если транзакция является строго двухфазной.
Другие случаи: В других случаях (отсутствие стерильности, не одноузловые транзакции, транзакции не с одноразовым использованием результатов) приходится применять какую-либо схему управления параллелизмом. Во всех знакомых авторам статьи РСУБД для обеспечения согласованности транзакций используются динамические блокировки. При принятии решения об использовании этого подхода производители следовали пионерской работе [ACL87], в которой на основе моделирования было показано, что вариант с блокировками работает лучше других схем. Однако авторы полагают, что динамические блокировки плохо подходят для H-Store, руководствуясь следующими соображениями:
Транзакции являются очень короткими. Отсутствуют задержки по вине пользователей и из-за обменов с дисками.
Поэтому транзакции существуют в течение очень коротких временных промежутков. Это говорит в пользу оптимистических методов управления параллелизмом в противовес пессимистическим методам, подобным методу динамических блокировок. Другие исследователи и разработчики, в частности, разработчики языка программирования, использующие транзакциями при работе с моделями памяти [HM93], пришли к таким же выводам. Каждая транзакция разбивается на наборы подкоманд, являющихся локальными для некоторого узла. Как отмечалось ранее, этот набор подкоманд выполняется в каждом узле в однопотоковом режиме. Следует снова заметить, что это приводит к отсутствию ожиданий в связи с использованием «защелок» (latch), сокращению общего времени выполнения и опять является доводом в пользу использования более оптимистических методов. Авторы статьи предполагают заранее получать весь набор классов транзакций. Эту информацию можно использовать для сокращения накладных расходов на управление параллелизмом, как это делалось в системах, подобных SDD-1 [BSR80], еще в 1970-е гг. В правильно спроектированной системе имеется очень мало коллизий транзакций и тупиковых ситуаций. Такие ситуации приводят к деградации производительности, и для их устранения разработчики всегда модифицируют приложения. Поэтому скорее следует производить разработку, в которой будут отсутствовать коллизии, чем использовать пессимистические методы.
В H-Store из этих факторов извлекается польза.
Для каждого класса транзакций (с отсутствием стерильности, с не одноузловыми транзакциями и транзакциями с не одноразовым использованием результатов) обнаруживается набор классов транзакций, с которыми транзакции данного класса могут конфликтовать. Транзакция инициируется в некотором узле grid и взаимодействует с координатором транзакций в этом узле. Координатор транзакций действует как диспетчер транзакций в узле инициации транзакции и рассылает части подплана в различные узлы. Сайт-исполнитель получает подплан и выжидает упоминавшийся ранее небольшой промежуток времени на предмет поступления возможно конфликтующей транзакции с меньшим значением временной метки.
После этого исполнитель делает следующее:
Выполняет подплан, если в его узле отсутствуют незафиксированные, потенциально конфликтующие транзакции с меньшими значениями временных меток и затем посылает результирующие данные в запрашивающий их узел, который может являться промежуточным узлом или координатором транзакции. В противном случае посылает координатору сообщение «abort».
Если координатор получает сообщение «ok» от всех узлов, он продолжает выполнение транзакции путем рассылки следующего набора подпланов, возможно, со встроенной в них логикой на C++. Если подпланов больше нет, координатор фиксирует транзакцию. В противном случае транзакция завершается аварийно.
В представленном алгоритме заключается основная стратегия H-Store. В процессе выполнения транзакций монитор транзакций отслеживает процентное соотношение успешно завершившихся транзакций. Если возникает слишком много аварийных завершений, H-Store динамически переходит к использованию следующей более сложной стратегии.
До выполнения или отказа в выполнении подплана каждый исполнитель выжидает промежуток времени, приблизительно равный MaxD * average_round_trip_message_delay, в попытке дождаться поступления плана с меньшим значением временной метки. В таком случае исполнитель корректно упорядочивает подпланы, уменьшая вероятность аварийного завершения транзакций. В приведенной формуле MaxD является максимальной глубиной класса конфликтующих транзакций.
Эта промежуточная стратегия позволяет уменьшить вероятность аварийного завершения транзакций, но за это приходится платить несколькими дополнительными миллисекундами задержки. В настоящее время авторы статьи производят моделирование для выяснения условий, в которых эта стратегия приводит к повышению производительности.
При применении усложненной (advanced) стратегии в каждом узле отслеживаются наборы прочитанных данных (read set) и наборы измененных данных (write set) каждой транзакции. В этом случае исполнитель запускает любой подплан, а затем при необходимости аварийно прекращает его выполнение в соответствии со стандартными правилами оптимистического управления параллельностью.
За счет дополнительных расходов на сбор дополнительной информации и дополнительной работы для обнаружения потребности в аварийном прекращении выполнения можно еще существеннее уменьшить вероятность аварийного завершения транзакций. В настоящее время производится моделирование с целью выявления ситуаций, в которых эта стратегия является выигрышной.
Таким образом, алгоритм управления параллелизмом в H-Store состоит в следующем:
Запускать стерильные транзакции, одноузловые транзакции и транзакциями с одноразовым использованием результатов без какого-либо управления параллелизмом. Прочие транзакции запускать с использованием основной стратегии. Если возникает слишком много аварийных завершений транзакций, переходить к использованию промежуточной стратегии. Если все равно возникает слишком много аварийных завершений транзакций, переходить к использованию усложненной стратегии.
Следует заметить, что этот алгоритм представляет собой усовершенствованную схему оптимистического управления параллелизмом. Оптимистические методы активно исследовались ранее [KR81, ACL87]. В СУБД Ants [Ants07] свойство коммутативности используется для снижения расходов на блокировки. Поэтому методы, описанные в этом разделе, можно считать объединением ранее известных методов, ориентированным на достижение очень низкого уровня накладных расходов.
Авторы также отмечают, что они пока еще не использовали какие-либо усложненные методы планирования для снижения уровня конфликтности транзакций. Например, можно было бы запускать транзакции из всех возможных пар классов транзакций и фиксировать частоту возникновения конфликтов. После этого планировщик мог бы руководствоваться этой информацией и пытаться не запускать вместе транзакции с высокой вероятностью конфликтов.
В следующем разделе демонстрируется, как эти методы и реализация H-Store в целом работают при выполнении тестового набора TPC-C.
Все популярные реляционные СУБД берут
Все популярные реляционные СУБД берут свое начало от системы System R, разработанной в 70-е годы прошлого века. Например, СУБД DB2 является прямой наследницей System R, и на первый выпуск этой системы оказала сильнейшее влияние подсистема RDS System R. Аналогично, MS SQL Server – это непосредственный наследник Sybase System 5, на разработку которой очень сильно повлияла System R. Наконец, в первом выпуске Oracle был напрямую реализован пользовательский интерфейс System R.
Все три перечисленные системы были построены более 25 лет тому назад, когда характеристики аппаратуры существенно отличались от тех, которые имеются сегодня. Процессоры обладают тысячекратно большей мощностью, а память – тысячекратно большей емкостью. Невероятно возросли объемы дисковой памяти, позволяющие теперь долговременно сохранять все, что заблагорассудится. Однако пропускная возможность канала между диском и основной памятью растет гораздо медленнее. Можно было ожидать, что скорость развития компьютерных технологий в последней четверти минувшего столетия приведет к существенным изменениям архитектуры систем баз данных, но, как это не странно, архитектура большинства СУБД, по существу, остается идентичной архитектуре System R.
Кроме того, в то время, когда задумывались реляционные СУБД, существовал единственный рынок СУБД – рынок систем обработки бизнес-данных. За прошедшие 25 лет образовался ряд других рынков: хранилищ данных, обработки текстовых данных, обработки потоковых данных. В этих областях имеются совсем другие требования, чем в области обработки бизнес-данных.
Наконец, во времена разработки РСУБД основным устройством, поддерживающим интерфейс с конечными пользователями, являлся алфавитно-цифровой терминал, и в качестве конечных пользователей производители имели в виду операторов, вводящих в интерактивном режиме запросы по приглашению, появляющемуся на экране терминала. Теперь конечные пользователи имеют дело с мощными персональными компьютерами, подключенными к Web.
На Web-сайтах, на которых используются транзакционные СУБД, редко выполняются интерактивные транзакции, а их пользователям вряд ли предоставляются интерфейсы на основе SQL.
Итак, существующие сегодня РСУБД разрабатывались в расчете на рынок обработки бизнес-данных в то время, когда имелись совсем другие интерфейсы пользователей, а аппаратура обладала совсем другими характеристиками. Эти РСУБД обладают рядом архитектурных черт, унаследованных от System R:
структуры хранения данных и индексов, ориентированные на дисковую память; использование многопотоковости для сокрытия временных задержек; механизмы управления параллельным доступом на основе блокировок; восстановление на основе журналов.
Конечно, с годами в этих архитектурах появились некоторые расширения, включающие поддержку сжатия данных, параллельное управление данными с использованием общей дисковой памяти, битовые индексы (bitmap index), поддержка определяемых пользователями типов данных и операций и т.д. Однако ни одна система не разу не подверглась полному перепроектированию после ее исходного изготовления. В данной статье авторы утверждают, что пришло время полностью переписывать СУБД.
В статье [SBC+07] приводились результаты тестовых испытаний, в ходе которых основные РСУБД показали производительность, на два порядка уступающую производительности специализированных программных средств в нескольких прикладных областях:
в области управления текстовыми данными (специализированные программные средства от Google, Yahoo и т.д.); в области хранилищ данных (системы с хранением данных по столбцам, такие как Vertica, Monet [Bon02] и т.д.); в области обработки потоковых данных (системы обработки потоковых данных, такие как StreamBase и Coral8); научные базы данных (системы хранения массивов данных, такие как MATLAB и ASAP [SBC+07]).
Эти результаты позволили одному из авторов (по всей видимости, Майклу Стоунбрейкеру) придти к следующим выводам:
РСУБД разрабатывались в расчете на рынок обработки бизнес-данных, и именно эта область является их лакомым куском; их производительность можно превзойти почти в любой другой области, которая является достаточно широкой для того, чтобы можно было гарантированно окупить тщательную разработку специализированных программных средств.
В данной статье авторы дополняют результаты, представленные в [SBC+07], демонстрируя, что сегодняшние архитектуры РСУБД не подходят даже и для обработки бизнес-данных. Для этого используется методология, аналогичная той, которая применялась в [SBC+07]. Авторами разрабатывается новая СУБД H-Store, предназначенная для OLTP. H-Store уже работает достаточно устойчиво, чтобы позволить сравнить ее производительность с производительностью популярных РСУБД. Результаты экспериментов показывают, что H-Store на эталонном тестовом наборе TPC-C работает в 82 раза быстрее РСУБД.
Поскольку удается превзойти производительность РСУБД почти на два порядка на стандартном тестовом наборе OLTP, не остается рынка, на котором РСУБД являются конкурентоспособными. К этим системам теперь следует относиться, как унаследованной технологии с возрастом более четверти века, следующим шагом по отношению к которой является полное перепроектирование.
Во втором разделе данной статьи обсуждаются архитектурные соображения, которые удалось использовать для достижения упомянутого показателя 82 на тестовом наборе TPC-C. В разд. 3 приводятся характеристики приложений, на поддержку которых ориентировано данное специализированное программное средство. В разд. 4 описываются некоторые детали разработки H-store. В разд. 5 содержатся экспериментальные данные, полученные при прогоне тестового набора TPC-C на H-Store и одной из популярных РСУБД. Наконец, в заключительном шестом разделе статьи приводятся некоторые радикальные предложения по поводу текущих исследовательских задач сообщества баз данных.
Выполнение запросов
Планируется разработка традиционного оценочного (cost-based) оптимизатора запросов, производящего планы выполнения SQL-операторов, которые содержатся в классах транзакций, во время определения этих классов. Авторы полагают, что этот оптимизатор может быть сравнительно простым, поскольку в средах OLTP никогда не встречаются, например, запросы с шестью соединениями таблиц. В запросах с несколькими соединениями всегда идентифицируется некоторый уникальный кортеж, представляющий интерес, (например, номер заказа), и кортежи, которые должны быть соединены с этой записью (например, позиции заказа). Поэтому все выполнение запроса опирается на некоторый опорный кортеж (anchor tuple), над которым выполняется небольшое число соединений 1-к-n, формирующих кортежи результата запроса. В средах OLTP редко встречаются запросы с GROUP BY и агрегатными функциями. Конечным результатом является простой план выполнения запроса.
Планы выполнения всех команд некоторой транзакции могут относиться к одной из следующих категорий:
Одноузловые (single-sited): В этом случае весь набор планов может быть направлен для выполнения в соответствующий узел.
C одноразовым использованием результатов (one-shot): В этом случае можно произвести декомпозицию в набор планов, каждый из которых выполняется только в одном узле.
Общие: В общем случае будут иметься команды, для которых требуется передача результатов между узлами grid’а. Кроме того, могут иметься команды, параметры времени выполнения которых получаются в результате выполнения предыдущих команд. В этом случае требуется применение выполнения запросов в стиле системы Gamma с поддержкой диспетчера выполнения (execution supervisor) в узле, в котором транзакция была инициирована в системе, и этот диспетчер должен взаимодействовать с исполнителями (worker) в узлах, где располагаются данные.
Для транзакций общего вида вычисляется глубина (depth) класса транзакций как число межузловых сообщений, обмен которыми потребуется для выполнения соответствующего набора планов выполнения запросов.
Высокий уровень доступности
Реляционные СУБД разрабатывались в ту эпоху (1970-е гг.), когда в типичной организации имелась одна вычислительная машина. Если она выходила из строя, компания несла убытки из-за недоступности системы. Для решения проблемы аварийных ситуаций организации поддерживали и тщательно сохраняли журнальные ленты. При возникновении аварийной ситуации поставщик аппаратуры (обычно IBM) проявлял чудеса героизма, в течение нескольких дней поставляя новую аппаратуру и приводя ее в режим эксплуатации. Затем производилось восстановление системы на основе журнальных лент, что позволяло привести ее к почти тому состоянию, в котором она находилась до возникновения аварийной ситуации.
Десятилетием позже, в 1980-е гг. организации заключали контракты со службами восстановления после аварийных ситуаций, такими как Comdisco, на предмет обеспечения ресурсов резервной аппаратуры, так что имелась возможность быстрой установки журнальных лент на удаленных резервных компьютерах. Эта стратегия позволяла сократить время простоя предприятия по причине аварийной ситуации.
Сегодня имеются многочисленные организации, использующие горячее резервирование (hot standby), которое позволяет производить обработку отказов аппаратуры в реальном времени. В некоторых других компаниях поддерживается несколько основных вычислительных систем, что обеспечивает еще более быструю обработку отказов. Организациям оказывается выгодно платить за несколько систем, чтобы избежать сокрушительных финансовых последствий простоя, когда каждая минута простоя часто обходится в тысячи долларов.
Авторы ожидают, что в будущем высокий уровень доступности и встроенные средства восстановления после аварийных ситуаций станут важными чертами рынка OLTP (и других рынков). Из этого утверждения следует несколько очевидных выводов. Во-первых, в любой СУБД, ориентированной на OLTP, потребуется поддержка нескольких согласованных копий данных, для чего нужна возможность эффективного выполнения СУБД в grid, в состав которого входит несколько географически распределенных систем.
Во-вторых, у большинства поставщиков существующих РСУБД имеется интеграционная поддержка системы из нескольких машин поверх их исходной архитектуры, ориентированной на SMP (Symmetric MultiProcessor, симметричный мультипроцессор, компьютерная архитектура, в которой несколько процессоров имеет равноправный доступ к совместно используемой основной памяти). Очевидно, что гораздо более эффективной является поддержка архитектуры shared-nothing с самого начала разработки системы.
В третьих, наилучший способ поддержки архитектуры без общих ресурсов состоит в использовании нескольких машин в одноранговой (peer-to-peer) конфигурации. Тогда нагрузка OLTP может быть распределена между несколькими машинами, а межмашинную репликацию можно использовать для отказоустойчивости. В обычном режиме эксплуатации доступными являются ресурсы всех машин. При отказах деградация функционирования системы возможна только из-за сокращения числа ресурсов. В отличие от этого, во многих коммерческих системах реализуется режим горячего резервирования, при котором вторая машина, по существу, простаивает до тех пор, пока не возьмет на себя управление при отказе первой машины. В этом случае в обычном режиме эксплуатации используется только половина ресурсов, что является заведомо худшим решением. Эти доводы доказывают потребность в полном перепроектировании серверов РСУБД, чтобы в них можно было обеспечить одноранговую высокую доступность внутри новой архитектуры.
В высокодоступной системе, независимо от того, основывается ли она на горячем резервировании или является одноранговой, можно существенно упростить журнализацию. По-прежнему необходимо поддерживать журнал откатов (undo) на тот случай, если произойдет сбой внутри некоторой транзакции, и ее потребуется откатить. Однако журнал откатов не требуется сохранять после завершения транзакции. По существу, этот журнал может представлять собой некоторую структуру в основной памяти, которая удаляется при фиксации транзакции. Никогда не требуется производить повторное выполнение операций (redo), поскольку требуемого эффекта можно достичь путем восстановления данных по сети с удаленного узла.
Когда вышедший из строя узел возобновит свое функционирование, его состояние можно обновить за счет данных работающего узла.
В статье [LM06] утверждается, что процедуры обработки отказа узла путем передачи нагрузки на другой узел и восстановления функционирования узла, вновь вошедшего в строй, (failover/rebuild) настолько же эффективны, что и процедура прямого восстановления по журналу. Следовательно, у этого способа поддержки высокого уровня доступности, по существу, нет недостатков. В мире высокой доступности не требуется поддержка журнала повторного выполнения операций, нужен только временный журнал откатов. Это поразительно упрощает логику восстановления. Можно отказаться от подсистемы журнализации в стиле Aries [MHL+92] и пользоваться новыми функциональными возможностями для восстановления состояния узла, возобновляющего функционирование после отказа, на основе данных других узлов.
И в этом случае большая часть сложного кода существующих РСУБД оказывается ненужной, а требуются совсем другие средства.
