Алгоритмы управления буферным пулом СУБД при работе с флэш-накопителями Аспирант 1 года обучения ИСП РАН Прохоров Андрей Анатольевич

Содержание 1.Флэш-память 1.Физическое устройство 2.Особенности работы 3.Технические характеристики SSD 2.Буферный пул СУБД 3.Алгоритмы управления буферным пулом СУБД 1.CFDC – Clean-First Dirty-Clustered Кластерная запись 2.SAWC – Self Adaptive with Write Clustering 3.FD-Buffer – Flash Disk Buffer Подсчет вероятностей промахов для вложенных буферов 10:212

Физическое устройство флэш-памяти Ячейка хранения данных – транзистор с плавающим затвором. Разработана - Toshiba 1984 год. + ячейка хранения – только 1 транзистор – ограничение циклов перезаписи 10:213

Разновидности флэш-памяти По количеству бит на одну ячейку памяти SLC – 1 бит, MLC – 2 бита, TLC – 3 бита. По способу организации ячеек в чипе NOR – Not Or, NAND – Not And. SSD сегодня = MLC + NAND. 10:214

Устройство SSD Solid-state drive(SSD): Чипы флэш-памяти Контроллер Чип RAM 10:215

Особенности флэш-накопителей 10:216 Ограничения со стороны технологического устройства чипов флэш-памяти. Ограниченное количество циклов перезаписи; Запись осуществляется только на заранее стертые ячейки. Достижение высокой плотности компоновки элементов, а также снижение стоимости устройств. NOR -> NAND. Запись и чтение блоками размером 4 кбайт; Стирание блоками размером 128 кбайт.

Перемешивание cодержимого накопителя Количество циклов перезаписи: MLC – 10 4 ; SLC – Распределение износа – перемешивание содержимого диска(Wear leveling). Поддержка динамического отображения логических блоков на физические. 10:217

Асимметрия чтения и записи Изменение нескольких байт данных: 1.Считывание блока с данными во внутренний буфер; 2.Модифицирование необходимых байтов; 3.Вычисление нового местоположения согласно алгоритму перемешивания; 4.Стирание и перенос полезных данных из нового местоположения в старое*; 5.Запись блока данных на новое место. * Усиление записи – Write Amplification 10:218

Операция TRIM Для ускорения операции записи требуется информации о пустых блоках. 10:219 ранее не было необходимости, поэтому такой информации нет Проблема введение в интерфейс обмена с накопителем операции освобождения неиспользуемых блоков памяти TRIM. Выход

10:2110 Сравнение SSD и HDD по основным характеристикам. ХАРАКТЕРИСТИКАHDDSSD(NAND) Время доступа на чтение, мс200,1 Время доступа на запись, мс200,2 Скорость последовательного чтения, Мбайт/с Скорость последовательной записи, Мбайт/с Произвольное чтение блока в 8 Кбайт, QD = 32, IOPS Произвольная запись блока в 8 Кбайт, QD = 32, IOPS

Недостатки современных SSD Высокая стоимость за 1 Гбайт; Сильная зависимость от алгоритмов работы контроллера, которые не раскрываются производителями; Падение производительности записи с уменьшением свободного места на носителе. 10:2111

Достоинства современных SSD Архивирование данных на лету; Хранение скрытого запаса ячеек памяти(до 30% от общего объема); Параллельная и асинхронная работа с чипами памяти; 10:2112

Буферный пул СУБД. Кэширование данных в RAM. Скорость произвольного доступа к данным: 10:2113 НосительСкорость HDD0,5 Мбайт/с SSD20 Мбайт/с RAM2 Гбайт/с.

Буферный пул СУБД. Страничная организация памяти. СУБД отображает часть страниц данных БД из постоянной памяти в основную(буферный пул). 10:2114 Стр. i 1 Стр. i 2 Стр i 3 Стр. i 4 Стр. i 5 Стр. i 6 Стр. i n-5 Стр. i n-4 Стр. i n-3 Стр. i n-2 Стр. i n-1 Стр. i n … Стр. j 1 Стр. j 2 Стр. j 3 Стр. j 4 Стр. j 5 …Стр. j m-2 Стр. j m-1 Стр. j m Постоянная память. Основная(оперативная) память. Грязные страницы

Буферный пул СУБД. Схема работы. 10:2115 СУБД Буферный пул Внешний накопитель 1. Запрос страницы 4. Возврат страницы 2. Выталкивание страницы жертвы 3. Считывание страницы

10:2116 Алгоритмы замещения страниц. Предположения об архитектуре СУБД. Фиксирование транзакций. Использование протокола журнализации WAL (Write Ahead Log) или его аналогов – нет необходимости в выталкивании грязных страниц при завершении транзакций. Откат транзакций. Возможность упреждающей записи – выталкивание грязных страниц на носитель даже при незавершенных транзакциях.

Принципы замещения страниц. Классический подход. В основу классических алгоритмов замещения страниц легли следующие идеи. 10:2117 Чтение и запись блока данных при произвольном доступе к диску одинакова(HDD). Уменьшение количества обменов с диском приведет к требуемому результату. Необходимо выталкивать те страницы, которые дольше всего не будут использоваться в будущем. (Алгоритм Белади, LRU, LFU, GCLOCK,etc.)

Алгоритмы замещения страниц. CFDC (Clean-First Dirty-Clustered). Данный алгоритм разбивает буфер на 2 области. 1.Рабочая область – W. [(1- λ)×N] 2.Приоритетная область – P(претенденты на выталкивание). [λ×N] 10:2118 W P λ 1 - λ

Алгоритмы замещения страниц. Кластерная запись. Для увеличения эффективности выталкивания страниц на диск их можно объединять в кластеры исходя из территориального признака. 10: … Сluster 1Сluster 2Сluster 3… Использование кластерной записи приводит к уменьшению коэффициента усиления записи, а также увеличивает скорость выталкивания грязных страниц.

Алгоритмы замещения страниц. CFDC. Приоритетная область - P. P = {L, Q, Hash}. L – LRU список чистых страниц. Q – Кластеры грязных страниц. Hash – распределение грязных страниц по кластерам. P(c) – стоимость кластера c. 10:2120 P({1},{2},{3},{4}) < P({4},{2},{1},{3}).

Алгоритмы замещения страниц. CFDC. Выталкивание страниц из P. 1.В первую очередь выталкиваются чистые страницы из LRU списка L. 2.Если L пуст, определяется наиболее приоритетный кластер. 1.Выталкивается LRU страница из данного кластера. 2.Стоимость кластера принимается равной 0. 10:2121

Алгоритмы замещения страниц. SAWC (Self Adaptive with Write Clustering) Буфер разделяется на 2 LRU списка, один с чистыми, а один с грязными страницами. 10:2122 Схема работы.

Алгоритмы замещения страниц. SAWC. Основная идея. Алгоритм динамически распределяет буфер междучистыми и грязными страницами, используя нормализованную стоимость операций чтения и записи (C R + C w = 1,C w ÷ C R = cost ratio). 10:2123

Алгоритмы замещения страниц. FD-Buffer (Flash Disk Buffer). 10:2124 Основные принципы: поддержка высокого процента попаданий в буфер; минимизация использования дорогостоящей операции записи. Оба принципа можно объединить, если рассмотреть математическое ожидание среднего времени обращения к странице БД.

Алгоритмы замещения страниц. FD-Buffer. Подсчет вероятности промаха. Метод подсчета вероятности промаха - Мэтсон 1970 год, LRU. Свойство вложенности буферов; Счетчики попаданий Hit[1,…,]; 10:2125 буфера в пуле123…MM+1…N Hits …250149…5

Алгоритмы замещения страниц. FD-Buffer. Схема работы. Буфер разбивается на два LRU списка CLRU и DLRU, для каждого из которых поддерживаются счетчики попаданий. 10:2126

Алгоритмы замещения страниц. FD-Buffer. Размер CLRU и DLRU. 10:2127

Экспериментальные результаты 10:2128

Выводы SSD носители продолжат вытеснять HDD; Некоторые особенности работы флэш-памяти имеют объективное объяснение, т.е. они не являются следствием несовершенства технологии; Использование специальных алгоритмов повышает скорость работы СУБД до 30%, при работе на SSD; Кластерная запись привносит значительный вклад в улучшение производительности. 10:2129

Спасибо за внимание. 10:2130

Сокращения SSD – Solid-State Drive; HDD – Hard Disc Drive; RAM – Random Access Memory; SLC – Single-Level Cell; MLC – Multi-Level Cell; TLC – Three-Level Cell; QD – Queue Depth; IOPS – Input/Output Operations Per Second; 10:2131

Сокращения WAL – Write Ahead Log; LRU – Least Recently Used; CFLRU – Clean-First LRU; LFU – Least Frequently Used; CFDC – Clean-First Dirty-Clustered; SAWC – Self Adaptive with Write Clustering; FD-Buffer – Flash Disk Buffer. 10:2132