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

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

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

Содержание

Предположения

Файловые системы

Системы баз данных

Флэш-память

Другие аппаратные средства

Правило пяти минут

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

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

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

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

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

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

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

Резюме и выводы

Благодарности

Литература

Статья Гоца Грейфа, пересказ которой предлагается вашему вниманию, формально посвящена очередному пересмотру «правила пяти минут» Джима Грея и Джанфранко Пуцолу. Этому автор посвятил большую часть своей статьи. Но мне кажется, что гораздо более важно то, что в статье предлагаются и обосновываются вполне конкретные подходы по применению флэш-памяти в файловых системах и СУБД. Похоже, что подобные подходы могут сильно подействовать на будущее технологии баз данных (например, привести к отказу от систем баз данных, поддерживаемых в основной памяти). Кроме того, очень ценно то, что Грейф приводит список нерешенных проблем, связанных с использованием флэш-памяти. Эти проблемы действительно актуальны и интересны. Хотелось бы надеяться, что за их решение возьмется кто-нибудь из российских специалистов. Как обычно, обращаю ваше внимание, что для удобства читателей я снабдил большинство материалов из списка литературы ссылками на источники, свободно доступные в Internet.

Сергей Кузнецов

В 1987 г. Джим Грей (Jim Gray) и Джанфранко Пуцолу (Gianfranco Putzolu) опубликовали свое знаменитое правило для разумного соотношения объема основной памяти и темпа ввода-вывода [1]. В своих подсчетах они сравнивали стоимость постоянного сохранения записи (или страницы) в основной памяти со стоимостью выполнения обмена с диском при каждом обращении к этой записи (или странице), используя существовавшее тогда соотношение цен на схемы основной памяти и дисковые устройства. Название правила происходит от интервала времени между равнозатратными обращениями к записи (или странице). Если обращения к записи (или странице) происходят более часто, то ее следует сохранять в основной памяти; если реже – ее нужно хранить на диске и считывать при необходимости.

Основываясь на тогдашних ценах и характеристиках производительности оборудования компании Tandem, Грей и Пуцолу обнаружили, что стоимость основной памяти, достаточной для хранения записи размером в 1 килобайт, примерно совпадает с (частью) стоимости дискового устройства, обеспечивающего доступ к такой записи через каждые 400 секунд, которые они округлили до пяти минут. Интервал равнозатратности обратно пропорционален размеру записи. По Грею и Пуцолу он равен одному часу для записи размером 100 байт и двум минутам для страниц в 4 килобайта.

Десять лет спустя правило пяти минут было проанализировано заново [2]. К этому времени изменилось множество цен и параметров производительности (например, стоимость мегабайта основной памяти упала с 5000 до 15 долларов). Тем не менее, правило пяти минут сохранилось. Интервал равнозатратности, равный примерно пяти минутам, существовал теперь для страниц размером в 8 килобайт. Первой целью этой статьи является анализ правила пяти минут спустя еще десять лет.

Конечно, в обеих предыдущих статьях признавалось, что в любой момент времени цены и производительность сильно зависят от технологий и конкретных устройств (например, основная память для мейнфреймов стоила совсем не столько же, сколько память для миникомпьютеров, диски SCSI обладают совсем другой ценой и производительностью, чем диски IDE, и т.д.). Поэтому заинтересованным читателям стоит самим пересчитать соответствующие формулы для своей среды и оборудования. Цифры, использованные в данной статье (см. табл. 1), типичны для технологии 2007 г.

	Основная память	Флэш-диск	SATA-диск
Цена и емкость	$3 за 8x64 мегабит	$999 за 32 гигабайта	$80 за 250 гигабайт
Пропускная способность передачи данных (Transfer bandwidth)	----	66 Мбайт/сек API	300 Мбайт/сек API
Время ожидания доступа (Access latency)	----	0.1 мсек	12 мсек в среднем
Потребляемая мощность в активном состоянии (Active power)	----	1 Вт	10 Вт
Потребляемая мощность в состоянии простоя (Idle power)	----	0.1 Вт	8 Вт
Потребляемая мощность в режиме пониженного энергопотребления (Sleep power)	----	0.1 Вт	1 Вт

Таблица 1. Цена и производительность флэш-памяти и дисков

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

• виртуализация с использованием аппаратной и программной поддержки, а также повышения коэффициента загруженности физических машин;

• многоядерные процессоры и транзакционная память, поддерживаемая как в программных средах, так и на уровне аппаратуры [3];

• использование контейнеров, вмещающих тысячи процессоров и многие терабайты данных [4];

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

Флэш-память занимает место между традиционной основной памятью и персистентной массовой памятью, основанной на вращающихся магнитных дисках, по показателям стоимости приобретения, задержки доступа, пропускной способности передачи данных, пространственной плотности, потребления энергии и расходов на охлаждение [5]. Это иллюстрируется данными, приведенными в табл. 1, и производными показателями, которые демонстрируются в табл. 2.

	NAND-флэш-память	Диск SATA
Цена и емкость	$999 за 32 гигабайта	$80 за 250 гигабайт
Цена за гигабайт	$31.20	$0.32
Время чтения страницы в 4 килобайта	0.16 мсек	12.01 мсек
Число считываний 4-килобайтных страниц в секунду	6200	83
Стоимость в расчете на считывание одной 4-килобайтной страницы в секунду	$0.16	$0.96
Время чтения страницы в 256 килобайт	3.98 мсек	12.85 мсек
Число считываний 256-килобайтных страниц в секунду	250	78
Стоимость в расчете на считывание одной 256-килобайтной страницы в секунду	$3.99	$1.03

Таблица 2. Сравнительная стоимость флэш-памяти и дисков

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

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

Основной вопрос состоит в том, следует ли относиться к флэш-памяти как к специальной части основной памяти или же как к специальной части персистентной памяти? Тот же вопрос можно задать по-иному: если система включает традиционную основную память емкостью в 1 гигабайт, 8 гигабайт флэш-памяти и 250-гигабайтный традиционный диск, то будет ли программное обеспечение считать, что имеются 250 гигабайт персистентной памяти и буферный пул объемом в 9 гигабайт, или же, что имеются 258 гигабайт персистентной памяти и буферный пул объемом в 1 гигабайт? Вторая цель статьи состоит в том, чтобы ответить на этот вопрос, а на самом деле, – дать разные ответы для файловых систем и систем баз данных.

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

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

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

Предположения

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

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

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

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

Файловые системы

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

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

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

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

Системы баз данных

Предполагается наличие достаточно традиционных систем баз данных с индексами на основе B-деревьев в качестве основополагающего компонента структуры хранения. Аналогичные древовидные структуры используются для поддержки не только традиционных кластеризованных и некластеризованных индексов, но также и битовых индексов, поколоночного хранения данных, XML-индексов, каталогов (метаданных) и структур данных, применяемых для распределения памяти.

Что касается транзакционных гарантий, предполагается традиционная журнализация с упреждающей записью в журнал (write-ahead logging) как операций изменений содержимого (таких как вставка или удаление записей), так и структурных изменений (таких как расщепление узлов B-деревьев). Эффективное восстановление по журналу после сбоев обеспечивается за счет поддержки контрольных точек, при установке которых модифицированные данные насильственно выталкиваются из буферного пула в персистентное хранилище.

Можно также допустить применение таких вариантов, как использование алгоритма «second chance» или метода нечетких (fuzzy) контрольных точек. Кроме того, для некоторых операций, таких как операция создания индекса, допускается нежурнализируемое выполнение (журнализируются только действия по распределению памяти). Для поддержки таких операций требуется соответствующее упорядочивание операций записи на диск и «силовая политика» управления буферным пулом [6].

Флэш-память

Предполагается, что аппаратура и драйверы устройств скрывают многие реализационные детали, такие как конкретный аппаратный интерфейс к флэш-памяти. Например, флэш-память можно установить на системной плате компьютера, на слоте DIMM, на плате PCI или внутри стандартного корпуса диска. Во всех случаях предполагается наличие возможности прямой передачи данных (на основе DMA (direct memory access) или какого-то более совершенного механизма) между основной и флэш-памятью. Кроме того, предполагается, что либо имеется эффективная DMA-передача данных между флэш-памятью и диском, либо поддерживается буфер передачи в основной памяти. В первом приближении размер такого буфера передачи должен быть примерно равен произведению скорости передачи данных на величину задержки обменов с диском. Если требуется, чтобы операции записи на диск никогда не задерживали выполнение операций чтения с диска, в этих вычислениях должна учитываться дополнительная задержка отложенной записи.

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

Поскольку надежность современной NAND-флэш-памяти падает после выполнения от 100000 до миллиона циклов перезаписи, предполагается, что обеспечиваются некоторые механизмы «выравнивания износа» («wear leveling»). Эти механизмы гарантируют, что все страницы или блоки страниц записываются с почти одинаковой частотой. Важно обратить внимание на сходство между алгоритмами выравнивания износа и файловыми системами с журнальным структурированием (log-structured file system) [9, 10], хотя при выравнивании износа перемещаются и стабильные, неизмененные данные, чтобы некоторые циклы перезаписи затрагивали их местоположения во флэш-памяти. Заметим также, что и традиционные дисковые устройства не поддерживают большее число операций записи. Например, за шесть лет постоянной и непрерывной записи со скоростью 100 мегабайт в секунду диск объемом в 250 гигабайт будет полностью перезаписан меньше чем 80000 раз. Другими словами, если предположить, что файловые системы с журнальным структурированием пригодны для использования на дисковых массивах RAID-5 или RAID-6, то надежность современной NAND-флэш-памяти представляется сопоставимой. Аналогично этому, для перезаписи флэш-диска объемом в 32 гигабайта 100000 раз на скорости 30 мегабайт в секунду потребуется примерно три с половиной года.

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

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

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

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

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

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

Другие аппаратные средства

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

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

Правило пяти минут

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

Грей и Пуцолу предложили следующую формулу [13,14]:

BreakEvenIntervalinSeconds = (PagesPerMBofRAM / AccessesPerSecondPerDisk) x (PricePerDiskDrive / PricePerMBofRAM)

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

При использовании современной основной памяти и дискового устройства со страницами размером 4 килобайта, а также значений из табл. 1 и 2 эта формула приводит к следующему:

(256/83) x ($80/$0.047) = 5,248 seconds = 90 минут = 1,5 часа

(Знак «=» в этой статье означает округление.) Сравните полученное значение c двумя минутами (для страниц размером 4 килобайта) 20 лет назад.

Если в этом изменении и есть нечто удивительное, так это то, что интервал равнозатратности вырос менее чем на два порядка. Напомним, что в 1987 г. основная память стоила около $5000 за мегабайт, а в 2007 г. – примерно $0.05 за мегабайт, т.е. цена отличается на пять порядков. С другой стороны, цены на диски тоже упали (в 1987 г. стоимость диска составляла $15000), задержки обменов существенно сократились, а скорость обмена – повысилась (с 15 обменов в секунду до 100 на SATA и 200 на высокопроизводительных дисках SCSI).

Для основной памяти и флэш-дисков объемом в 32 гигабайта интервал равнозатратности составляет

(256/6,200) x ($999/$0.047) = 876 секунд = 15 минут

В 2007 г. цена флэш-дисков включала «надбавку за новизну» и без ее учета приближалась к цене «сырой» флэш-памяти, около $400 (эта цена также предвиделась Греем и Фицджеральдом [5]). При этой цене интервал равнозатратности составляет 351 секунду = 6 минут.

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

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

(256/83) x ($80/$0.03) = 8,070 секунд = 2,25 часа

Таким образом, все активные данные будут оставаться в основной и флэш-памяти.

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

В 1987 г. Грей и Пуцолу рассуждали о будущем через двадцать лет и предсказывали «правило пяти часов» для основной памяти и дисков. Для записей длиной в 1 килобайт при ценах и спецификациях, типичных для 2007 г., их формула дает 20978 секунд, или немного меньше шести часов. Предсказание оказалось поразительно точным.

Размер страницы	1 Кб	4 Кб	16 Кб	64 Кб	256 Кб
ОЗУ-SATA	20978	5248	1316	334	88
ОЗУ-флэш	2513	876	467	365	339
Флэш-SATA	32253	8070	2024	513	135
ОЗУ-$400	1006	351	187	146	136
$400-SATA	80553	20155	5056	1281	337

Таблица 3. Интервалы равнозатратности

В табл. 3 показаны интервалы равнозатратности, включая те, которые упоминались выше, для разных размеров страниц и комбинаций технологий хранения. «$400» обозначает 32-гигабайтный NAND-флэш-диск, который стоил в 2007 г. $999 (просто «флэш» в табл. 3), а за вычетом «надбавки за новизну» должен был стоить $400.

Старое правило пяти минут для основной памяти и дисков теперь применимо к страницам размеров в 64 килобайта (334 секунды). В 1987 г. пять минут составляли приблизительный интервал равнозатратности для страниц размером в один килобайт [16], а в 1997 г. – для страниц размером в 8 килобайт [17]. В этой тенденции отражаются разные скорости сокращения задержек доступа к дискам и повышения скорости передачи данных.

Пятиминутный интервал равнозатратности также применим к комбинации основной памяти и дорогостоящей флэш-памяти в ценах 2007 г. для страниц размером в 64 килобайта и более (365 секунд для 64-килобайтных страниц и 339 секунд для 256-килобайтных). По мере сокращения стоимости флэш-памяти сокращаются и интервалы равнозатратности (146 и 136 секунд соответственно).

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

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