Лучшее B-Tree в Hekaton

Microsoft Research опубликовала подробную информацию о том, как Hekaton, база данных в памяти, которая будет поставляться со следующей версией SQL Server, достигает 100-кратного увеличения производительности.

Впервые Hekaton был представлен на PASS 2012 в ноябре, где Тед Куммерт, корпоративный вице-президент подразделения бизнес-платформ Microsoft, описал его как «полностью работающий в памяти механизм транзакций, поставляемый как часть SQL Server». Для более полного описания ознакомьтесь с нашим отчетом. Теперь мы можем начать понимать механизмы, которые дают Hekaton его преимущества.

По словам Пола Ларсона, который является частью команды Hekaton:

«В традиционных моделях предполагается, что данные живут на диске и хранятся на дисковых страницах. Это создает много накладных расходов при попытке доступа к записям. Когда данные полностью находятся в памяти, мы можем использовать гораздо более простые структуры данных. Структуры данных индекса и хранилища Hekaton оптимизированы на том основании, что когда таблица объявляется оптимизированной для памяти, все ее записи находятся в памяти ».

Частично улучшение Hekaton связано с отходом от традиционного многоядерного подхода, который, по сути, рассматривает многоядерный процессор как распределенную систему, к конструкции без защелок, также называемой безблокировочной. Защелки используются для синхронизации транзакций, чтобы избежать повреждения данных, когда несколько пользователей пытаются изменить одни и те же данные. Побочным эффектом этого является создание узких мест для высокопроизводительных программных систем, работающих на многоядерных процессорах. Вместо этого методы без фиксации обновляют «оптимистично», никогда не блокируя записи или структуры данных. Это намного более эффективно для избежания узких мест, но при этом существует риск повреждения данных.

Подход, используемый командой Hekaton, заключается в использовании мультиверсионного управления параллелизмом (MVCC). При обновлении старые данные помечаются как устаревшие, и добавляется новая версия. В любое время может быть несколько версий данных, но только одна из них является последней. Большим преимуществом является то, что транзакции обновления могут добавлять новые версии, не мешая одновременному чтению. То, как это делается в Hekaton, описано в документе «Высокопроизводительные механизмы управления параллелизмом для баз данных в основной памяти», который был представлен в августе на Международной конференции по очень большим базам данных.

Наряду с изменением блокировки транзакций, Hekaton также имеет новую систему индексирования, которая разработана так, чтобы быть быстрее, чем традиционный индекс B-дерева. Новое Bw-дерево улучшило производительность кеш-памяти процессора. Bw-дерево основано на идее, что таблица, отображающая идентификаторы страниц в местоположения страниц, позволит как обновлять страницы без фиксации, так и хранить во флэш-памяти страницы с журнальной структурой.

Проблема с адресами bw-tree двоякая. Используя многоядерные процессоры, вы можете достичь высокого уровня параллелизма, но это создает проблему блокировки, поскольку один процесс пытается изменить данные, заблокированные другим процессом. Кроме того, достижение хорошей производительности многоядерного процессора зависит от высоких коэффициентов попадания в кэш ЦП, но обновление памяти на месте приводит к недействительности кеша.

Bw-дерево не имеет защелок, что означает, что поток не подвержен конфликтам. Это решает проблему промахов кеша, избегая обновления страниц на месте.

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

В тестах Bw-tree было быстрее по нескольким причинам, чем альтернативная технология без защелок, основанная на Skiplists. Bw-дерево также работает значительно лучше, чем реализация B-дерева на основе защелок BerkeleyDB. При тестировании в сценарии с высокой конкуренцией, который обычно вызывает серьезное снижение производительности, когда все потоки постоянно пытаются обновить последнюю страницу индекса B-дерева, Bw-дерево работает лучше в 24 раза по сравнению с другой, хорошо спроектированной защелкой. -основанная реализация.

.