Правило пяти минут двадцать лет спустя, и как флэш-память изменяет правила

Гоц Грейф
Пересказ: Сергей Кузнецов

Оригинал: Goetz Graefe. The Five-minute Rule: 20 Years Later and How Flash Memory Changes the Rules, ACM QUEUE, July/August 2008

Назад Содержание Вперёд

Перемещение страниц

Кроме обеспечения ввода-вывода в основную память и из нее, в трехуровневой иерархии памяти также требуется перемещение данных между флэш-памятью и дисками. Механизм перемещения страниц может быть реализован на уровне аппаратуры (например, на основе DMA, Direct Memory Access) или на основе пересылки данных через основную память. Первый вариант обещает более высокую производительность, зато второй может быть полностью реализован программным образом без потребности в новой аппаратуре. С другой стороны, у производителей гибридных дисков уже могут иметься аппаратные реализации, пригодные по соотношению «цена-производительность».

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

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

Отслеживание местоположения страниц

Механизмы отслеживания местоположения страниц в файловых системах и системах баз данных заметно отличаются. В файловых системах страницы данных или экстенты (run) смежных страниц отслеживаются в страницах указателей (pointer page). При перемещении индивидуальной страницы может потребоваться разбиение экстента. В любом случае страницу указателей приходится модифицировать и затем записывать.

В системах баз данных большая часть данных хранится в индексах на основе B-дерева, включая кластеризованные (первичные, не избыточные) и некластеризованные (дополнительные, избыточные) индексы на таблицах, материализованные представления и каталоги баз данных. С использованием B-деревьев просто и эффективно представляются битовые индексы, поколоночные хранилища таблиц и совместно кластеризованные таблицы со связью «один-ко-многим» [18]. Древовидные структуры, близкие к B-деревьям, также используются для хранения BLOB’ов и близки к структурам хранения некоторых файловых систем [19,20].

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

Во-первых, если в каждой странице B-дерева поддерживаются ссылки на соседние страницы, то при перемещении одной страницы требуется обновление двух соседних страниц, а также родительского узла. Если же указатели на соседей являются логическими, основанными на использовании «ограждающих ключей» (fence key), то при перемещении страницы нужно обновлять только страницу-предка [21]. Если родительская страница находится в основной памяти, возможно, даже зафиксирована в буферном пуле, то фиксация нового местоположения выполняется подобно обновлению таблицы преобразования адресов, располагающейся в основной памяти. Операция изменения указателя в родительской странице журнализуется в журнале восстановления, но нет нужды немедленно выталкивать журнал в стабильную память, поскольку это изменение является всего лишь структурным, не изменяющим содержимое базы данных.

Во-вторых, в системах баз данных журнализуются изменения физической базы данных, и в предельном случае в журнал попадает содержимое как удаленной, так и заново созданной страницы. Таким образом, при неэффективной реализации при каждом перемещении одной страницы данных из одного места в другое заполняются две страницы журнала. При более эффективной реализации журнализуются только действия, связанные с новым размещением страницы данных, а старая страница вместе со своим содержимым не освобождается до тех пор, пока новое содержимое не будет надежно записано на новое место [22]. Другими словами, при перемещении страницы из одного местоположения (например, в персистентной флэш-памяти) в другое местоположение (например, на диске) требуется записать в журнал восстановления всего лишь несколько байт.

Файловые системы и системы баз данных различаются эффективностью операций обновления, допускаемой журналом восстановления. В файловой системе новое положение страницы должно быть сохранено как можно быстрее путем записи нового содержимого страницы указателей. В системе баз данных нужно всего лишь добавить в буфер журнала одну или несколько коротких записей. Таким образом, накладные расходы перемещения страницы в файловой системе состоят в записи всей страницы указателей с использованием произвольного доступа, в то время как в системе баз данных в буфер журнала добавляется запись из нескольких десятков байт, которая, в конце концов, будет записана с использованием крупных операций последовательной записи.

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

Однако в системе баз данных имеются встроенные механизмы, позволяющие легко отслеживать перемещения страниц. Эти механизмы свойственны структуре данных, являющейся «рабочей лошадкой» систем баз данных, – индексам на основе B-деревьев. По сравнению с файловыми системами, эти механизмы обеспечивают эффективные перемещения страниц, при каждом из которых требуется только часть последовательной операции записи (в журнале восстановления), а не целая операция записи с произвольным доступом.

Кроме того, механизмы баз данных являются надежными. Если при перемещении страницы произойдет отказ, то база данных будет восстановлена по журналу, в то время как для файловой системы потребуется полная проверка во время перезапуска.

Обработка контрольных точек

Для обеспечения быстрого восстановления после отказа системы в системах баз данных используются контрольные точки. При восстановлении нужно учитывать операции над базой данных, выполненные позже установки последней контрольной точки, плюс некоторые действия, явно отраженные в информации контрольной точки. Основная работа при установке контрольной точки состоит в записи в персистентное хранилище данных обновленных страниц, содержащихся в буферном пуле.

Если бы флэш-память считалась частью буферного пула, то содержащиеся в ней измененные страницы должны были бы записываться на диск при выполнении операций установки контрольной точки базы данных. Обычно интервалы между последовательными контрольными точками составляют секунды или минуты. В качестве варианта, если контрольные точки на самом деле являются не точками, а интервалами, разумно непрерывно выталкивать страницы и производить действия по установке контрольной точки, начиная новую операцию установки контрольной точки сразу по завершению предыдущей операции. Таким образом, при выполнении многочисленных операций записи в флэш-память вскоре потребуется запись на диск, и флэш-память как промежуточный уровень иерархии памяти не сможет амортизировать операции записи на диск. Этот эффект может усилиться, если объем основной памяти остается небольшим из-за наличия флэш-памяти.

Если же флэш-память считается персистентным хранилищем данных, то достаточно производить записи в флэш-память. Сквозная запись на диск требуется только при замещении страницы (т.е. когда статистика использования данной страницы делает целесообразным размещение этой страницы на диске, а не во флэш-памяти). Таким образом, при установке контрольных точек не требуется перемещать данные из флэш-памяти на диск.

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

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

Размеры страниц

В дополнение к настройке на основе правила пяти минут имеется оптимизация, основанная на показателях эффективности доступа и заключающаяся в выборе оптимального размера узлов B-дерева. При выборе оптимального размера страницы минимизируется время, затрачиваемое на выполнение операций ввода-вывода при поиске от корня к листьям дерева. Достигается компромисс между коротким временем доступа (т.е. потребностью в небольших страницах) и сильным сокращением пространства поиска (т.е. потребностью в крупных страницах). Если внутри узлов B-дерева используется двоичный поиск, то сокращение пространства поиска измеряется логарифмом числа записей в каждом узле. Этот показатель в одной из предыдущих статей автора [23] был назван полезностью (utility) узла. Эта оптимизация, по существу, эквивалентна той, которая описывалась в исходном исследовании B-деревьев [24].

Табл. 4. Полезность страниц для узлов B-дерева на диске

Размер страницы	Число записей в странице	Полезность узла	Время доступа	Полезность/время
4 Кб	140	7	12.0 мс	0.58
16 Кб	560	9	12.1 мс	0.75
64 Кб	2240	11	12.2 мс	0.90
128 Кб	4480	12	12.4 мс	0.97
256 Кб	8960	13	12.9 мс	1.01
512 Кб	17920	14	13.7 мс	1.02
1 Мб	35840	15	15.4 мс	0.97

В табл. 4 эта оптимизация иллюстрируется для записей из 20-ти байт (типичных при отбрасывании префикса и суффикса [25]) и узлов, заполненных примерно на 70%. Не удивительно, что оптимальный размер узла B-дерева на современных дисках с высокой пропускной способностью намного больше размера страницы, используемого в традиционных системах баз данных. При использовании этих дисков для всех страниц небольшого размера доминирует время доступа, так что передача большего числа байт и, следовательно, большая полезность даются почти бесплатно.

Размер узла B-дерева в 256 Кб очень близок к оптимальному. Как показывает табл. 3, для этого размера страницы интервал равнозатратности для основной памяти и диска составляет 88 секунд. Для флэш-диска стоимостью $400 и традицонного вращающегося жесткого диска этот интервал составляет 337 секунд, или чуть больше пяти минут. Это первое из двух новых правил пяти минут, представленное в данной статье.

Табл. 5. Полезность страниц для узлов B-дерева на флэш-диске

Размер страницы	Число записей в странице	Полезность узла	Время доступа	Полезность/время
1 Кб	35	5	0.11 мс	43.4
2 Кб	70	6	0.13 мс	46.1
4 Кб	140	7	0.16 мс	43.6
8 Кб	280	8	0.22 мс	36.2
16 Кб	560	9	0.34 мс	26.3
64 Кб	2240	11	1.07 мс	10.3

В табл. 5 иллюстрируются аналогичные вычисления для B-деревьев во флэш-памяти. По причине отсутствия механического перемещения головок и вращения время передачи доминирует даже для страниц небольшого размера. Оптимальный размер страницы для B-деревьев во флэш-памяти составляет 2 килобайта, намного меньше, чем в случае использования традиционных дисковых устройств.

В таблице 3 интервал равнозатратности для страниц размером в 4 килобайта составляет 351 секунду. Это второе новое правило пяти минут.

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

К счастью, Патрик О’Нейл (Patrick O’Neil) из Массачусетского университета уже разработал схему распределения памяти для B-деревьев, при использовании которой соседние листовые страницы обычно размещаются в одном непрерывном экстенте страниц [26]. При потребности в новой странице по причине расщепления узла выделяется другая страница в том же экстенте. Когда экстент переполняется, половина его страниц перемещается в заново выделенный экстент. Другими словами, логика B-деревьев по «отщеплению половины при переполнении» теперь применяется не только к страницам, содержащим записи, но и к дисковым экстентам, содержащим страницы.

При использовании SB-деревьев О’Нейла (S означает sequential, в данном случае, непрерывный) экстенты размером в 256 килобайт могут служить единицами передачи данных между флэш-памятью и диском, а страницы размером в 4 килобайта – единицей передачи между основной и флэш-памятью.

Аналогичные понятия «самоподобных» (self-similar) B-деревьев предлагались для более высоких уровней иерархии памяти (например, в форме B-деревьев строк кэша для поддержки таблиц преобразования адресов внутри страниц большого размера) [27]. Если учесть, что в настоящее время имеется, по крайней мере, три уровня B-деревьев и три размера узлов (т.е. строки кэша, страницы флэш-памяти и страницы диска), очень перспективными могут оказаться исследования B-деревьев, при работе с которыми не учитываются конкретные характеристики кэша.

Обработка запросов

Подход самоподобности применяется как к структурам данных, таким как B-деревья, так и к алгоритмам. Например, в алгоритмах сортировки уже используются алгоритмы, подобные традиционным алгоритмам внешней сортировки с многоканальным (multiple way) слиянием, для слияния частичных результатов сортировки не только на диске, но и в основной памяти, где размеры начальных частей массива выбираются таким образом, чтобы размеры частичных результатов сортировки ограничивались размером кэша центрального процессора [29, 30].

Такую же технику можно применить три, а не два раза: сначала частичные результаты сортировки, хранящиеся в основной памяти и ограниченные размером кэша, сливаются, образуя частичные результаты, хранящиеся в флэш-памяти и ограниченные размером основной памяти; потом, при выполнении очень крупных операций сортировки, частичные результаты сортировки, хранящиеся в флэш-памяти и ограниченные размером основной памяти, сливаются, образуя частичные результаты на диске; и, наконец, частичные результаты сортировки, хранящиеся на диске, сливаются для получения окончательного результата сортировки. Такие приемы, как упреждающее чтение, прогнозирование, отложенная запись и выбор оптимального размера страниц, заслуживают того, чтобы взглянуть на них по-новому при наличии многоуровневой иерархии памяти, включающей кэш, основную память, флэш-память и традиционные дисковые устройства. Затем на основе этих размеров страниц можно произвести вычисления величин интервалов равнозатратности и получить, тем самым, руководство для оценки оптимального объема ресурсов на каждом уровне памяти.

Можно предположить, что некоторая разновидность описанного алгоритма сортировки будет не только быстрой, но и эффективной в смысле энергопотребления. Хотя эффективность энергопотребления всегда была критичной для устройств с питанием от батарей, только в последнее время начали исследоваться проблемы обработки запросов с эффективным энергопотреблением [31]. Например, и для флэш-памяти, и для дисков размеры страниц, оптимальные с точки зрения энергопотребления, могут значительно отличаться от размеров страниц, оптимальных с точки зрения производительности.

Характер ввода-вывода внешней сортировки со слиянием аналогичен (хотя и в противоположном направлении) характеру ввода-вывода внешней сортировки с разделением (external partition sort), а также характеру ввода-вывода разделения при выполнении хэш-соединений и вычислении агрегатных функций на основе хэширования. Кроме того, при наличии трехуровневой иерархии памяти (или даже четырехуровневой, если принимать во внимание и кэши центральных процессоров), также требуется пересмотр двух последних разновидностей алгоритмов [32].

Флэш-память со своим очень быстрым временем доступа может вновь пробудить интерес к исполнению запросов на основе индексов [33, 34]. Оптимальные размеры страниц и интервалы их удержания обсуждались в предыдущих разделах статьи.

Кэши записей и объектов

С годами размер страниц в системах баз данных увеличивался, хотя и не так быстро, как скорость передачи данных на диски. С другой стороны, при использовании небольших страниц требуется меньше памяти в буферном пуле для каждого поиска от корня к листьям B-деревьев. Например, рассмотрим индекс с 20 миллионами элементов. При использовании индексных страниц размеров в 128 килобайт, содержащих по 4500 записей, при поиске от корня к листьям требуется два узла и, следовательно, 256 килобайт в буферном пуле, хотя половина этой памяти (корневой узел), вероятно, будет использоваться совместно с другими транзакциями. При использовании индексных страниц размером в 8 килобайт, содержащих по 280 записей, при поиске от корня к листьям требуется три узла, или 24 килобайта в буферном пуле, т.е. на порядок меньше.

В традиционной архитектуре систем баз данных размер страницы, используемый по умолчанию, является компромиссом между эффективным индексным поиском (за счет крупных индексных страниц, как обсуждалось ранее в этой статье и в первоначальных статьях о B-деревьях [35]) и умеренными требованиями к объему буферного пула при каждом индексном поиске. Тем не менее, в приведенном примере требуется 24 килобайта в буферном пуле для нахождения записи, состоящей, возможно, всего из 20 байт, а также 8 килобайт в буферном пуле для удержания этих 20 байт в основной памяти. При альтернативной организации используются крупные страницы на диске и кэш записей, работающий на приложения; кэш записей позволяет минимизировать потребности в памяти, обеспечивая, тем не менее, удержание требуемых данных. Системы баз данных с хранением данных в основной памяти, используемые в качестве внешних систем традиционных систем баз данных с хранением данных на дисках, можно считать некоторой разновидностью кэша записей.

Внедрение флэш-памяти с ее быстрым временем доступа и небольшим оптимальным размером страниц может привести к отказу от кэшей записей. При использовании крупных дисковых страниц и только небольших страниц в буферном пуле основной памяти желаемый компромисс можно достичь без потребности в двух отдельных структурах данных (т.е. B-дерева и отдельного кэша записей).

В объектно-ориентированных приложениях, которые собирают сложные объекты из многих таблиц и индексов, хранимых в реляционной базе данных, эта проблема может упроститься или усложниться в зависимости от технологии поддержки B-деревьев. Если в традиционных индексах применяется отдельное B-дерево для каждого формата записи, то для сборки сложного объекта в основной памяти требуется много поисков от корня к листьям и, следовательно, много узлов B-деревьев в буферном пуле. Если же записи из нескольких индексов можно перемежать внутри одного B-дерева на основе их общих ключей поиска и порядка сортировки [36, 37] (например, объектного идентификатора и уместных дополнительных ключей), то может оказаться достаточно выполнить всего несколько, а то и один поиск по B-дереву. Более того, весь сложный объект можно удержать в одной странице буферного пула.

Направления будущих исследований

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

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

В-третьих, Грей и Пуцолу предлагали и другие эмпирические правила, такие как правило десяти байт для нахождения компромисса между емкостью памяти и мощностью центрального процессора. В связи с изменением расходов на приобретение и энергоснабжение эти правила также должны быть пересмотрены. По сравнению с 1987 г. наиболее существенное изменение, возможно, состоит в том, что мощность ЦП следует измерять не в числе команд, выполненных единицу времени, а в числе замещений строк кэша. Поиск компромисса между объемом памяти и временем в этой среде можно считать новой проблемой.

В-четвертых, каковы наилучшие политики перемещения данных? Одна из крайностей состоит в том, что администратор баз данных явно перемещает целиком файлы, таблицы и индексы между флэш-памятью и традиционными дисками. Другой крайностью является автоматическое перемещение отдельных страниц, управляемое политикой замещения, такой как LRU. Промежуточные политики могут сосредотачиваться на роли отдельных страниц базы данных или на текущей активности обработки запросов. Например, после изменения схемы можно перемещать страницы каталога для ускорения повторной компиляции всех сохраненных в кэше планов выполнения запросов, а узлы верхних уровней B-деревьев можно заранее считывать и удерживать в основной или флэш-памяти при выполнении планов запросов, опирающихся на навигацию по индексам.

В-пятых, в чем состоят дополнительные воздействия от внедрения флэш-памяти в иерархию памяти сервера баз данных? Например, быстрое время доступа позволяет ограничить уровень мультипрограммирования, поскольку асинхронный ввод-вывод и переключение контекста в этом случае «скрывает» только короткие операции ввода-вывода. В свою очередь, низкая степень мультипрограммирования может привести к понижению уровня конкуренции за память при выполнении операций сортировки и хэширования, а также за блокировки (управление параллелизмом при совместной работе с содержимым базы данных) и за «защелки» (latch) (управление параллелизмом при совместной работе со структурами данных в основной памяти). Если это воздействие окажется существенным, то можно сократить объем и сложность работы, связанной с использованием гранулированных блокировок.

В-шестых, как затронет внедрение флэш-памяти системы баз данных, сохраняемых в основной памяти? Станут ли они более масштабируемыми, доступными и популярными, если будут опираться на использование основной памяти, дешевым образом расширяемой флэш-памятью? Или же их популярность снизится по причине существенного ускорения традиционных систем баз данных, в которых вместо дисков (или в дополнение к ним) будет использоваться флэш-память? Смогут ли традиционные системы, в которых вместо традиционных дисков применяется флэш-память, конкурировать со специализированными системами баз данных в основной памяти по производительности, общей стоимости владения, стоимости разработки и сопровождения, времени выхода на рынок и выпуска очередных релизов и т.д.?

Наконец, для иерархий памяти могут оказаться полезными методы, аналогичные методам «сборки мусора разных поколений» (generational garbage collection). Выборочное освобождение памяти применяется не только к недостижимым объектам в основной памяти, но также и к страницам буферного пула и к соответствующим областям долговременной памяти. Такие исследования могут также оказаться полезными для файловых систем с журнальным структурированием и B-деревьев, оптимизированных в расчете на запись, в RAID-хранилищах.

Назад Содержание Вперёд