После обсуждения традиционного хранения строк на диске (rowstore) в части 1 и колоночных хранилищ (columnstores) в части 2, пришло время обратить наш взгляд в SQL Server на структуры хранения, оптимизированные для памяти.
Оптимизированное для памяти хранение было представлено в SQL Server 2014 в рамках проекта, который имел кодовое название «Hekaton» и позже был переименован в in-memory OLTP. В то время как колоночные индексы были специально нацелены на крупномасштабную аналитическую работу, Hekaton и оптимизированные для памяти таблицы специально предназначены для высоконагруженных OLTP-нагрузок. Полностью устраняя блокировки обычные и краткие и используя предварительно скомпилированный машинный код, где это возможно, время обработки транзакций значительно сокращается, что позволяет достичь пропускной способности, ранее недостижимой.
Название «оптимизированные для памяти» выбрано очень осознанно. Эта функция не просто заменяет дисковое хранилище на хранилище в памяти. Сама структура данных была полностью переработана, чтобы извлечь выгоду из скорости современной памяти и обеспечить безопасный параллельный доступ без использования блокировок или защёлок.
Обратите внимание, что оптимизированные для памяти колоночные индексы, доступные с SQL Server 2016, будут описаны в отдельной статье. Эта статья посвящёна оптимизированным для памяти индексам rowstore.
Varheap (Системная куча)
Первое, что вы заметите, изучая структуры хранения, оптимизированные для памяти, — это то, что SQL Server поддерживает для них только некластерные индексы. Не существует такого понятия, как оптимизированный для памяти кластерный индекс. Конечно, мы знаем, что для любых данных SQL Server хранит их либо в кластерном индексе, либо в куче. Поскольку первое не поддерживается для in-memory OLTP, это означает, что по определению все оптимизированные для памяти таблицы хранят свои данные в куче. Однако для оптимизированной для памяти таблицы Microsoft использует термин varheap (системная куча).
Varheap состоит из одного или нескольких блоков памяти, каждый размером 64 МБ. (Обратите внимание, что этот размер не задокументирован; я вывел его из тестов на своей собственной системе, но фактический размер может отличаться на разном оборудовании, и Microsoft может изменить его без уведомления). Эти блоки соединены цепочкой указателей. Всякий раз, когда выделяется новый блок, он добавляется в начало цепочки, становясь «первым» в цепочке. Таким образом, последний блок будет первым блоком, выделенным для таблицы.
Затем каждая строка из таблицы сохраняется в одном из этих блоков. Там, где есть свободное место. Таким образом, это будет примерно зависеть от порядка вставки, с учётом приведённого выше замечания. Или порядка, в котором данные загружаются обратно в память после перезапуска сервера. В любом случае, этот порядок никак не будет полезным.
Чтобы обеспечить параллельный доступ без блокировок, кратких блокировок и конфликтов, SQL Server использует форму изоляции моментального снимка для всех оптимизированных для памяти таблиц. Это означает, что старые версии строк сохраняются (пока не перестанут быть нужны), но помечаются как более не текущие. Это делается путём добавления двух дополнительных внутренних столбцов к каждой строке, называемых временная метка начала (begin timestamp) и временная метка конца (end timestamp). Эти названия немного вводят в заблуждение, потому что данные в этих столбцах не связаны со временем. На самом деле это внутренний постоянно увеличивающийся счётчик транзакций. Но Microsoft решила использовать термин «временная метка» (timestamp), поэтому в этом блоге я буду использовать эту терминологию. Просто имейте в виду, что прямой связи с реальным временем нет.
Когда вы вставляете данные в оптимизированную для памяти таблицу, новая строка сохраняется в памяти, в varheap. Данные строки, конечно, будут содержать указанные вами данные. Временная метка начала будет установлена на временную метку текущей транзакции. Временная метка конца будет установлена на специальное значение, обозначающее бесконечность. С этого момента строка доступна всем транзакциям, которые начались после или во время вставки. Более старые транзакции встретят эту строку при чтении данных, но будут игнорировать её, потому что их временная метка ниже временной метки начала этой строки.
Когда вы удаляете существующую строку, временная метка конца устанавливается на временную метку транзакции удаления. Будущие операции чтения будут пропускать эту строку и игнорировать её, если их временная метка выше этой временной метки конца. Но более старые транзакции с более низкой временной меткой всё ещё будут видеть удалённую строку.
Для обновления два вышеуказанных действия объединяются. Текущая строка в памяти остаётся неизменной, но её временная метка конца устанавливается так, что она логически удаляется. Новая копия строки с обновлёнными столбцами, изменёнными на новые значения, вставляется с временной меткой начала, установленной на временную метку транзакции, и временной меткой конца, равной бесконечности. Любая операция чтения с той же или более высокой временной меткой будет игнорировать исходную версию и возвращать новую версию. Если это всё ещё активная более старая транзакция, она увидит только исходную версию строки, а не новую копию, потому что её временная метка ниже временной метки конца исходной и временной метки начала новой строки.
До сих пор я использовал термин «строка» для структур, хранящихся в varheap. Но, как вы теперь видите, это не совсем правильно. Любое обновление приводит к сохранению новой версии строки в дополнение к старой версии. Таким образом, вместо строк в varheap фактически хранятся версии строк, каждая из которых помечена временной меткой начала и конца, указывающей, для каких транзакций они действительны и, следовательно, видимы.
Некластерные индексы
Оптимизированные для памяти некластерные индексы не хранятся как отдельные структуры. Вместо этого они реализованы как цепочки указателей, которые соединяют версии строк различными способами. Каждая версия строки в varheap всегда хранится с местом для восьми указателей, что является причиной, по которой оптимизированные для памяти таблицы не поддерживают более восьми некластерных индексов.
Обратите внимание, что объявление меньшего количества индексов не экономит память. Место для восьми указателей всегда выделяется, даже если существует меньше индексов. Хотя это и приводит к потере памяти для таблиц с менее чем восемью индексами, у этого есть преимущество: дополнительные индексы можно создать без необходимости перетасовывать данные в памяти. Место для дополнительных указателей уже есть.
Ранее мы видели, что дисковые некластерные индексы хранятся как отдельные структуры с указателем на данные в кластерном индексе или куче (на основе данных или, в случае куч, на основе местоположения). Это не так для оптимизированных для памяти некластерных индексов. Они реализованы как указатели. Для каждого некластерного индекса один из восьми слотов указателя в каждой версии строки используется для связывания её со «следующей» версией строки в соответствии с логикой этого индекса.
SQL Server поддерживает два различных типа некластерных индексов в оптимизированных для памяти таблицах: некластерные хэш-индексы и некластерные индексы. Последний термин, на мой взгляд, очень сбивает с толку, потому что это имя также используется для дисковых строчных некластерных индексов. Поэтому для ясности я обычно называю их по имени их структуры хранения: Bw-индекс (Bw-index). И для краткости я часто сокращаю термин «некластерный хэш-индекс» до просто «хэш-индекс».
Хэш-индекс
Оптимизированный для памяти некластерный хэш-индекс основан на хэше одного или нескольких столбцов таблицы. Хэш-функция преобразует значения в этих столбцах в хэш-значение в диапазоне, указанном заданным количеством сегментов (buckets).
Где-то в памяти, в месте, хранящемся в метаданных, SQL Server выделяет массив указателей, равный по размеру этому количеству сегментов. Таким образом, для каждого сегмента существует один указатель. Этот указатель затем указывает на местоположение одной из версий строк, для которой хэшируемые столбцы дают это значение. Указатель в этой версии строки затем указывает на другую версию строки, которая также принадлежит этому сегменту, и так далее. Таким образом, каждый сегмент является началом цепочки указателей, которая соединяет все версии строк, принадлежащие этому сегменту, согласно хэш-функции на индексированных столбцах.
Итак, предположим, у вас есть таблица Persons с двумя хэш-индексами. Один по (LastName, FirstName); другой только по City. Версия строки для Джейн Смит, живущей в Нью-Йорке, будет где-то в цепочке указателей, ведущей к сегменту 164 для индекса по имени (поскольку Smith, Jane хэшируется в 164), и в цепочке к сегменту 883 (хэш Нью-Йорка) для индекса по городу. Если затем она переедет в Чикаго, новая версия строки будет добавлена где-то в той же цепочке указателей для 164 (её имя не изменилось), но она пойдёт в цепочку от сегмента 504 (хэш Чикаго), в то время как старая версия строки всё ещё останется связанной с сегментом 883.
(Обратите внимание, что хэш-значения в приведённом выше примере полностью вымышлены).
Bw-дерево (Bw-tree index)
Bw-дерево очень похоже на B-дерево, которое мы знаем по дисковым строчным индексам. Я не буду вдаваться в подробности различий. Если вы хотите узнать все мельчайшие детали, вы можете прочитать статью здесь. Как и B-дерево, Bw-дерево имеет единственный вход на корневом уровне, несколько промежуточных уровней и множество записей на листовом уровне. Всё это вместе называется «внутренними страницами».
В то время как B-дерево имеет одну запись на строку на своём листовом уровне, Bw-дерево имеет одну запись на каждое отдельное значение (или комбинацию значений) ключевого столбца (столбцов) во всех своих версиях строк. Эта запись листового уровня хранит значение и указатель на одну из версий строк с этим значением или набором значений в индексированном столбце (столбцах). Эта строка затем имеет указатель на другую версию строки с теми же значениями. Это может быть более старая или более новая версия той же строки, или, если индекс не объявлен как уникальный, это может быть версия другой строки, у которой случайно оказались те же значения.
Ещё одно важное отличие Bw-дерева от B-дерева заключается в том, что внутренние страницы (структура дерева) в Bw-дереве не указывают непосредственно друг на друга. Вместо этого каждая ссылка проходит через так называемую «таблицу отображения страниц» (page mapping table). Таким образом, в то время как записи на корневой странице обычного B-дерева указывают на записи на первом промежуточном уровне, записи на корневой странице Bw-дерева указывают на запись в таблице отображения страниц, которая затем, в свою очередь, указывает на фактическую запись первого уровня.
Очевидно, это замедляет каждый процесс, который перемещается по дереву. Каждый шаг к другой странице в структуре теперь требует двух переходов вместо одного. Конечно, каждый переход — это прямой доступ к ячейке памяти, поэтому он молниеносно быстр, но всё равно это кажется пустой тратой производительности. И если вы думаете только о чтении данных, вы будете правы. Однако эта дополнительная структура необходима для обеспечения полностью свободных от блокировок и кратких блокировок процессов для всех модификаций, включая добавление записей на промежуточную страницу, расщепления страниц и даже добавление уровня. Ни одна страница никогда не изменяется (потому что это потребовало бы по крайней мере краткой блокировки). Вместо этого для каждой затронутой страницы создаётся новая версия, а затем указатель в таблице отображения страниц обновляется, чтобы указывать на новую страницу.
Хотя этот процесс подходит для корневых и промежуточных страниц, оказалось, что листовые страницы изменялись слишком часто, и это стало бы обузой. Поэтому последним дополнительным усложнением для Bw-индексов является то, что только для листовых страниц используются так называемые «дельта-страницы» (delta pages). Модификация реализуется не путём создания новой версии страницы и последующего перенаправления таблицы отображения страниц, а путём выделения новой «дельта-страницы», которая описывает изменения и связывается с листовой страницей. Теперь SQL Server читает исходную листовую страницу, затем читает все дельта-страницы и применяет их изменения, чтобы сконструировать текущую версию листовой страницы в памяти. Фоновый процесс очистки периодически проходит по листовым страницам, чтобы объединить все изменения и создать новую версию листовой страницы.
Чтение из оптимизированной для памяти таблицы или индекса
После описания структуры индекса давайте теперь посмотрим, как можно получить доступ к данным.
Просмотр таблицы (Table Scan)
Просмотр таблицы в оптимизированной для памяти таблице читает версии строк непосредственно из varheap. Он начинается с первого блока памяти в цепочке (напомним, это самый недавно выделенный блок памяти). Для каждой строки в этом блоке памяти он проверяет временную метку начала и временную метку конца, чтобы убедиться, видима ли версия строки для текущей транзакции, затем проверяет предикат (если есть), а затем возвращает строку.
Просмотр индекса (Index Scan)
То, как обрабатывается просмотр (сканирование) индекса в оптимизированном для памяти индексе, зависит от типа индекса.
Сканирование индекса в Bw-дереве
Сканирование индекса в Bw-дереве начинается с первой записи в таблице отображения страниц, которая всегда указывает на корневую страницу дерева. Он использует первый указатель (снова через таблицу отображения страниц), чтобы найти логическую первую страницу первого промежуточного уровня. Это повторяется, пока не будет найдена логическая первая страница листового уровня. Применяются изменения с дельта-страниц для создания текущей версии, находится первое значение (или набор значений для составного индекса), а затем следует указатель на первую версию строки для этого набора значений. После проверки временной метки начала и конца, а также (если применимо) предиката, строка возвращается.
При следующем вызове используется указатель на следующую версию строки с теми же значениями в ключевом столбце. Это повторяется до конца цепочки указателей. В этот момент сканирование индекса возвращается к логической первой листовой странице, чтобы найти второе отдельное значение (или набор значений), и процесс повторяется.
После обработки всех записей на первой листовой странице сканирование индекса использует указатель на следующую листовую страницу (снова через таблицу отображения страниц), а затем повторяет процесс. Это продолжается до тех пор, пока не будет обработана последняя листовая страница, на что указывает нулевой указатель на следующую страницу.
Результатом является то, что любое сканирование индекса всегда будет возвращать данные в порядке индексированных столбцов. Оптимизатор может установить для свойства Ordered значение false, если этот порядок не требуется, но это не повлияет на фактическую стратегию доступа.
Просмотр в хэш-индексе
Сканирование индекса в хэш-индексе не поддерживается.
Однако вы всё же можете увидеть его в плане выполнения. Насколько мне известно, единственный способ получить это — буквально заставить SQL Server, указав индекс в подсказке индекса (index hint). Но если вы это сделаете, SQL Server подчинится вашей команде и сгенерирует план выполнения со сканированием индекса по этому хэш-индексу.
Однако это не то, что на самом деле происходит при выполнении запроса. Хотя план выполнения показывает сканирование индекса по указанному индексу, данные фактически возвращаются путём сканирования varheap, по одному блоку памяти за раз. Точно такой же метод, как и просмотр таблицы в оптимизированной для памяти таблице.
Итак, когда вы видите сканирование индекса (Index Scan) по хэш-индексу в своём плане выполнения, SQL просто обманывает вас, и на самом деле он выполнит просмотр таблицы.
Поиск по индексу (Index Seek)
Обработка поиска по индексу в оптимизированном для памяти индексе, конечно, также зависит от типа индекса.
Поиск по индексу в Bw-дереве
Для поиска по индексу SQL Server снова начинает с первой записи в таблице отображения страниц, которая всегда указывает на корневую страницу дерева. Теперь он смотрит на значения на этой странице, чтобы найти правильную промежуточную страницу первого уровня для перехода, а затем (через таблицу отображения страниц) находит эту промежуточную страницу. Этот процесс повторяется до достижения листового уровня. Применяются изменения с дельта-страниц для создания текущей версии, а затем находится запрашиваемое значение (или набор значений). Оператор следует указателю на первую версию строки для этого набора значений, проверяет временную метку начала и конца, проверяет предикат (если есть), а затем эта строка возвращается.
Для поиска одной строки (singleton lookup) на этом всё. Это происходит только тогда, когда план выполнения определяет поиск по равенству по всем индексированным столбцам в уникальном индексе. В цепочке указателей может быть больше версий строк. Но в уникальном индексе только одна из этих версий строк может быть действительной для любой транзакции, поэтому после чтения первой гарантируется, что любые другие существующие версии строк недействительны для этой же транзакции.
Если индекс неуникальный, указана только левая часть столбцов или используется предикат неравенства, операция всегда представляет собой поиск по диапазону, что означает, что оператор будет вызван снова для следующей подходящей строки. На этом этапе используется указатель на следующую версию строки с теми же значениями в ключевом столбце, и повторяются те же проверки начала и конца транзакции, а также предиката, если необходимо. В конце концов, все версии строк для этого набора значений обработаны. Для поиска по равенству по всем столбцам в неуникальном индексе на этом всё.
Для поиска по равенству по подмножеству столбцов, а также для любого предиката неравенства процесс затем всё ещё продолжается. Мы возвращаемся к листовой странице и берём следующую запись на той же листовой странице или на следующей листовой странице, чтобы проверить, удовлетворяет ли это значение предикату. Если да, то все версии строк, привязанные к этой записи, обрабатываются таким же образом. Если нет, то мы достигли конца подходящих данных.
Поиск по индексу в хэш-индексе всегда упорядочен. Поддерживаемые предикаты такие же, как и для поиска по индексу в дисковом строчном индексе: равенство по всем столбцам, равенство по левому подмножеству столбцов (опционально с неравенством по следующему столбцу) или неравенство по самому левому столбцу.
Поиск по индексу в хэш-индексе
Хэш-индекс поддерживает только поиск по индексу с предикатом равенства по всем индексированным столбцам. Для поиска по неравенству и для поиска по подмножеству индексированных столбцов хэш-индекс использоваться не может.
Процесс довольно прост. Поиск по индексу вычисляет хэш значения (или значений), которое ему нужно найти. Он находит соответствующий указатель в массиве указателей. Этот указатель является местоположением первой версии строки для этого ключа индекса. Как всегда, проверяются начало и конец транзакции (и предикат, если есть), прежде чем строка будет возвращена. Однако в этом случае также должно быть проверено свойство Seek Predicates, потому что коллизии хэшей могут привести к несоответствующим строкам в том же сегменте.
Если индекс объявлен как уникальный, это поиск одной строки. В том же сегменте может быть больше версий строк, но они либо для других значений ключа, у которых есть коллизия хэша, либо для тех же значений ключа, но не действительных для текущей транзакции.
Если индекс неуникальный, то может быть больше подходящих строк, поэтому мы выполняем поиск по диапазону. После возврата первой подходящей строки поиск по индексу будет вызван снова и продолжит цепочку указателей, чтобы найти больше версий строк с правильными данными в ключевых столбцах, которые действительны для текущей транзакции.
Поиск по ключу / Поиск по RID (Key Lookup / RID Lookup)
Поскольку оптимизированные для памяти таблицы не имеют кластерных индексов, поиск по ключу (Key Lookup) не поддерживается для этих таблиц. И хотя они являются своего рода кучей, поиск по RID (RID Lookup) также не поддерживается. Это связано с тем, что в данном случае некластерный индекс не является отдельной структурой, а представляет собой цепочку указателей, наложенную на данные. Следование по указателям приводит нас к полным данным, и нам не нужен отдельный шаг для извлечения дополнительных столбцов из кучи.
Заключение
Оптимизированные для памяти таблицы хранятся в памяти в структуре, подобной куче, которая называется varheap. Оператор просмотра таблицы (Table Scan) использует эту структуру для поиска данных, которые нужно вернуть.
Каждая оптимизированная для памяти таблица должна иметь по крайней мере один некластерный индекс. Возможно и больше, до максимума в восемь. Эти некластерные индексы бывают двух разновидностей.
- Хэш-индексы используют хэш-функцию для индексированных столбцов, чтобы определить, в каком сегменте должна храниться версия строки. Версии строк в каждом сегменте соединяются цепочкой указателей. Эта структура очень эффективна для поиска строк на основе точного совпадения всех индексированных столбцов, но не может использоваться для других типов доступа к данным.
- Bw-деревья используют структуру, очень похожую на B-дерево, для хранения всех отдельных значений в индексированных столбцах в виде древовидной структуры, а затем соединяют версии строк через цепочки указателей с этими значениями. Эти индексы более универсальны, но медленнее для точного поиска.
Комментариев нет:
Отправить комментарий