Как был устроен и как работал начальный вариант H-Store
H-Store выполняется в кластере компьютеров (почему-то в эта аппаратная среда упорно называется grid'ом – С.К.). При конфигурировании системы можно указать желаемый уровень ее надежности – число узлов, при выходе из строя которых система может восстановить работоспособность без потери выполняемых транзакций в течение заданного времени. (Поскольку восстановление системы основано на использовании реплик, то, очевидно, уровень надежности коррелирует с числом поддерживаемых реплик данных – С.К.).
В каждом узле строки разделов таблиц размещаются вплотную одна к другой, и доступ к ним производится на основе B-деревьев (т.е. строки размещаются в порядке сортировки по значениям ключа B-дерева). Размер блока B-дерева соответствует размеру блока кэша второго уровня используемого процессора. (Сравнительно ясно, что является ключом B-дерева для баз данных с древовидной схемой – первичный ключ для корневой таблицы и внешний ключ для любой таблицы-потомка. Что выбирается в качестве ключа B-дерева раздела таблицы при наличии других схем, неясно – С.К.).
В каждом узле H-Store поддерживает ровно один поток управления, в котором полностью, без каких-либо задержек выполняется каждая поступающая операция SQL. Узлы, в процессорах которых имеется несколько ядер, разбиваются на соответствующее число логических узлов. В H-Store каждый логический узел трактуется так же, как и любой физически независимый узел, и основная память многоядерного компьютера разделяется между логическими узлами.
Транзакции представляются в виде хранимых процедур базы данных, и в системе поддерживается только одна внешняя операция Execute transaction (parameter_list), позволяющая в любом узле инициировать выполнение любой предопределенной транзакции с передачей ей значений параметров. Внутри таких хранимых процедур (для написания которых в исходном прототипе использовался язык C++) сочетается логика приложений и операции манипулирования базами данных, причем вызовы SQL производятся как локальные вызовы.
Журнал повторного выполнения операций не поддерживается, а журнал отката (сохраняемый в основной памяти и освобождаемый при завершении транзакции) ведется только для транзакций, не являющихся двухфазными.
В исходном прототипе H-Store отсутствовал компилятор SQL, и планы всех операций SQL генерировались и оптимизировались вручную. Однако в отмечалось, что планируется разработка компилятора SQL с оценочной (cost-based) оптимизацией, и что этот компилятор-оптимизатор должен быть сравнительно простым, поскольку в типичном OLTP-запросе всегда идентифицируется некоторый опорный кортеж (anchor tuple), с которым соединяются несколько (немного) таблиц. И некоторый компилятор SQL действительно появился в коммерческом варианте H-Store – VoltDB (см., например, ), хотя по доступной документации системы трудно судить, какие возможности оптимизации в нем реализованы.
Для обеспечения возможности использования H-Store без потребности в "ручках управления" планировалось создание средства автоматического проектирования физических схем баз данных (дизайнера баз данных), определяющего горизонтальное разделение, репликацию и выбор ключей индексов. Цель дизайнера состоит в том, чтобы сделать как можно больше транзакций одноузловыми (т.е. избежать появления распределенных транзакций). (И, кроме того, насколько я понимаю, добиться выявления двухфазных и стерильных транзакций – С.К.).
Мне с самого начала возможность создания такого средства казалась сомнительной. Уж очень трудна задача статического анализа многочисленных хранимых процедур с многочисленными вызовами операций SQL. К настоящему времени (конец 2010 г.) эта задача, по всей видимости, не решена. В документации VoltDB разработчикам приложений предлагается лишь методика физического проектирования баз данных, да и то подчеркивается необходимость многократного выполнения тестовых испытаний (benchmarking, benchmarking, benchmarking!) на реальных данных до вывода приложения в производственный режим. С другой стороны, некоторую надежду на продвижение в этом направлении дает работа , хотя она основывается уже не на статическом анализе, а на анализе трасс выполнения рабочей нагрузки (см.
ниже).
Выполнение транзакций в исходном прототипе H- Store происходило по следующей схеме. На входе в систему каждой транзакции назначалась временная метка (timestamp) в формате (site_id, local_unique_timestamp). Если поддерживается порядок на множестве узлов кластера, то все метки являются уникальными и полностью упорядоченными. Предполагалось, что локальные часы в каждом узле некоторым образом синхронизуются.
Если все классы транзакций являются одноузловыми, то каждая транзакция может быть направлена в узел с требуемыми копиями данных и полностью в нем выполнена. Если не все классы транзакций являются стерильными, то узел, в котором завершилось выполнение некоторой транзакции, в течение небольшого времени (времени сетевых задержек – для локальной сети в пределах нескольких миллисекунд) ожидает поступления транзакций от других узлов-инициаторов, чтобы выполнение транзакций происходило в порядке временных меток. За счет этого все реплики будут обновляться в одном и том же порядке, и их состояние после конца любой транзакции будет идентично. Следовательно, для выполнения одноузловых транзакций не требуется журнал повторного выполнения операций, какое-либо управление параллелизмом и распределенная фиксация транзакций. Если же, в придачу ко всему остальному, транзакция является двухфазной, то для нее не требуется и журнал отката.
Если все транзакции являются стерильными, то обычно для их выполнения не требуется какое-либо управление параллелизмом. Более того, в этом случае не требуется назначение транзакциям временных меток и их выполнение в одном и том же порядке надо всеми репликами. Но если транзакция распространяется на несколько узлов, то отсутствует гарантия, что она будет во всех узлах успешно выполнена или аварийно завершена. Поэтому каждый исполнитель должен послать диспетчеру выполнения транзакции (в том узле, в котором она была инициирована) сообщение "аварийное завершение" или "нормальное завершение" в той точке своей части транзакции, после которой соответствующее решение изменить уже нельзя (для двухфазных транзакций – в конце первой фазы).
Диспетчер, в свою очередь, должен рассылать эти сообщения в другие узлы-исполнители. Другими словами, в этом случае приходится выполнять обычную процедуру фиксации распределенной транзакции. Если транзакция является строго двухфазной, этих накладных расходов можно избежать.
В общем случае (когда тразакция не является одноузловой или стерильной), приходится применять средства управления параллелизмом. При реализации исходного прототипа H-Store было принято решение отказаться от традиционной для SQL-ориентированных СУБД пессимистической схемы синхронизационных блокировок в пользу более оптимистических методов (как показывают более поздние статьи, посвященные H-Store в целом и управлению транзакциями в H-Store , это решение не является стратегическим – поиск методов продолжается; кстати, совершенно неясно, какая схема управления параллелизмом применяется в VoltDB – С.К.).
В схеме управления параллелизмом, описываемой в , применяются три стратегии – основная, промежуточная и усложненная. Для каждого класса транзакций определяются классы транзакций, с которыми транзакции данного класса могут конфликтовать (по-видимому, выявляются стандартные конфликты "запись-запись", "чтение-запись" и "запись-чтение" на уровне таблиц – С.К.). Каждая транзакция инициируется в некотором узле системы, и ее выполнение отслеживается координатором транзакций в этом узле. Координатор выполняет роль диспетчера транзакций в узле инициации и рассылает фрагменты транзакции в соответствующие узлы.
При применении основной стратегии сайт-исполнитель получает фрагмент и выжидает в течение времени сетевых задержек на предмет возможного поступления транзакции с большим значением временной метки. Если после этого в узле обнаруживаются транзакции с более поздними временными метками из классов, потенциально конфликтующих с данной транзакцией, то исполнитель не выполняет ее фрагмент и посылает координатору сообщение "аварийное завершение".
В противном случае фрагмент выполняется, и результирующие данные возвращаются в узел, из которого этот фрагмент был получен. Если координатор получает сообщение о нормальном выполнении фрагментов от всех узлов, он продолжает выполнение транзакции при наличии следующего набора ее фрагментов или же фиксирует транзакцию. В противном случае транзакция завершается аварийным образом.
Если при использовании основной стратегии возникает слишком много аварийных завершений транзакций (т.е. в данной рабочей нагрузке имеется высокий уровень потенциальной конфликтности транзакций – С.К.), применяется более сложная промежуточная стратегия. В этом случае каждый исполнитель до принятия решения о выполнении или аварийном завершении полученного фрагмента выжидает интервал времени величиной MaxD * среднее_время_обмена_сетевыми_сообщениями (где MaxD – максимальное число межузловых сообщений, которое потребуется для выполнения любой потенциально конфликтующей транзакции), чтобы установить, не появится ли фрагмент транзакции с меньшим значением временной метки. В этом случае исполнитель получает возможность корректного упорядочивания фрагментов, что уменьшает вероятность аварийного завершения транзакций.
Наконец, усложненная стратегия, к которой планировалось прибегать в тех случаях, когда ни основная, ни промежуточная стратегии не позволяют в достаточной степени сократить число аварийных завершений транзакций, – это достаточно традиционная стратегия оптимистического управления параллелизмом. В этом случае конфликты распознаются во время выполнения, для чего в каждом узле отслеживаются наборы прочитанных данных (read set) и наборы измененных данных (write set) каждой транзакции. Любой исполнитель запускает выполнение любого фрагмента и аварийно его завершает, если это требуется для разрешения динамически обнаруженной конфликтной ситуации.
Авторы сравнивали производительность начального прототипа H-Store с производительностью неназываемой коммерческой SQL-ориентированной СУБД на эталонном тестовом наборе TPC-C.
В обоих случаях транзакции реализовывались в виде хранимых процедур и запускались внешней командой, передаваемой по сети. За счет специально подобранного метода разделения базы данных TPC-C и тщательного анализа транзакций удалось преобразовать все классы транзакций к стерильному и строго двухфазному виду. В результате на одной и той же аппаратной конфигурации (один компьютер с двухъядерным процессором) H-Store показала производительность, в 82 раза превышающую производительность традиционной СУБД. По наблюдениям авторов, главным тормозом традиционной СУБД стала система журнализации изменений в дисковой памяти. На втором месте – накладные расходы на управление параллелизмом.
Кстати, в 2008 г. основные авторы опубликовали результаты более глубокого исследования влияния на производительность традиционных механизмов транзакционных СУБД . Это исследование, фактически, объясняет, за счет чего в H-Store удалось добиться такой производительности. Авторы взяли не очень известную систему Shore с открытыми исходными текстами, сконфигурировали ее таким образом, чтобы требуемая для их экспериментов база данных полностью помещалась в основной памяти, и измерили производительность полученной системы базы данных на смеси двух транзакций из тестового набора TPC-C. Затем они последовательно стали удалять из состава Shore компоненты журнализации, синхронизации и управления буферным пулом, и в результате получили вариант системы с ограниченной функциональностью, которая показала на том же тестовом наборе производительность, в 20 раз большую, чем у исходной Shore.
