В число четырех главных экспериментов, проводимых на Большом адронном коллайдере в ЦЕРН, входит LHCb. Его детекторы и системы моделирования физических процессов ежегодно генерируют 15 экзабайт сырых данных, которые после обработки помещаются в распределенную систему хранения на жестких дисках и магнитных лентах. Понятно, что диски быстрее лент, но дороже, поэтому важно оптимизировать размещение файлов на разных носителях. Система управления дисковой памятью для LHCb основана на статистическом анализе истории обращения к данным, который наряду с алгоритмами машинного обучения дает возможность прогнозировать популярность файлов, что позволяет определить, какие файлы можно удалить с диска. А применяя алгоритмы регрессионного анализа и анализа временных рядов, удается определить оптимальное число копий файлов на диске для обеспечения их надежного хранения, экономии дискового пространства и уменьшения времени доступа к данным.

Алгоритмы машинного обучения уже давно применяются для улучшения производительности алгоритмов работы с кэш-памятью, например в [1] для прогнозирования популярности данных использовались цепи Маркова, а опираясь на этот прогноз, удалось добиться увеличения производительности гибридной (SSD + HDD) системы хранения. В [2] прогноз популярности файлов выполнялся с помощью нейронной сети и позволил определить оптимальное число копий файлов.

Особенность системы управления дисковой памятью для LHCb состоит в том, что история обращений к файлам сильно разрежена — временной ряд, отражающий факты обращений к дискам, имеет много нулевых значений. Большинство файлов используются редко, но интенсивно, поэтому такие методы, как искусственные нейронные сети [3], ARMA, ARIMA [4], демонстрируют плохие результаты из-за сильной разреженности данных. Вычисление дополнительных признаков для каждого файла, характеризующих особенности их истории обращений, позволяет разделить файлы на популярные и непопулярные.

Входными данными для алгоритма управления дисковой памятью для LHCb являются история обращений к файлам и метаданные, к которым относятся: источник данных, конфигурация детектора, тип файла, тип данных (полученные по методу Монте Карло или реальные данные), тип события, время создания файла, время первого/последнего обращения, размер одной копии, общий размер файла на диске, число копий на диске и др. Например, можно использовать историю обращения к файлам за два года с разбивкой по неделям и представить ее в виде временного ряда из 104 точек, каждая из которых — это число обращений к файлу за одну неделю.

Для прогноза популярности файлов используется классификатор — алгоритм машинного обучения с учителем, в результате работы которого каждый файл помечается как популярный или непопулярный. Как уже отмечалось, временные ряды истории обращений к файлам сильно разрежены, поэтому показатели за последние полгода (26 недель) истории обращений служат для разметки данных — если файл в течение этого периода не использовался, то он помечается как непопулярный и получает метку «1», в противном случае помечается как «0».

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

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

В роли классификатора использовался градиентный бустинг над деревьями (алгоритм машинного обучения, основанный на применении ансамбля деревьев решений), позволяющий без переобучения быстро получить высокое качество классификации. Для обучения использовался метод перекрестной проверки с 10 частями (k-fold cross-validation). Это означает, что все файлы разбиваются на 10 частей, при этом классификатор обучается на девяти частях данных, а затем используется для предсказания вероятности получения метки «1» для десятой части данных. Процедура повторяется 10 раз. В итоге получаем прогноз вероятности метки «1» для каждой из 10 частей. Предсказанная вероятность преобразуется в популярность так, чтобы популярность для класса с меткой «1» была распределена равномерно. Чем ближе популярность к 1, тем выше вероятность того, что файл не будет использован в будущем. То есть вычисленная популярность определяет антипопулярность файла. Такой выбор сделан с тем, чтобы файлы, являющиеся первыми кандидатами на удаление, имели большую величину метрики.

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

Сначала временные ряды сглаживались по формуле ядерного сглаживания Надарая — Ватсона на основе RBF-ядра (один из простейших видов непараметрической регрессии), а ширина окна сглаживания была взята в 30 недель.

Самый простой способ предсказать будущее значение временного ряда — это взять в его качестве значение из последней точки наблюдения (статическая модель прогноза в работе). На рисунке приведен пример временного ряда после применения формулы ядерного сглаживания Надарая —Ватсона и вычисления скользящего среднего.

Пример сглаженного временного ряда
Пример сглаженного временного ряда

 

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

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

Оптимальное число копий файлов определяется по предсказанной интенсивности обращений к файлам — чем выше интенсивность обращений, тем больше копий имеет конкретный файл.

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

Можно сравнить предложенный алгоритм работы рекомендательной системы с алгоритмом Least Recently Used (LRU), который смотрит на последние наблюдения в истории обращений к файлу и принимает решение по удалению файлов с диска.

В таблице дано сравнение результатов работы предложенного алгоритма и алгоритма LRU. «Отношение времени доступа» — это отношение времени доступа (загрузки) к файлам, полученное после применения алгоритма, к первоначальному времени доступа. Колонка «Число ошибок» показывает, сколько файлов было удалено с жесткого диска, но затем понадобилось в работе [2]. «Альфа» — коэффициент пропорциональности между числом копий файла и квадратным корнем интенсивности обращения к нему. Как видно из таблицы, оба алгоритма позволяют оптимизировать объем дискового пространства, однако LRU допускает больше ошибок.

Результаты сравнения алгоритмов
Результаты сравнения алгоритмов

 

Представленный рекомендательный вариант системы управления дисковой памятью для эксперимента LHCb реализован в виде открытой библиотеки на языке Python.

***

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

Литература

  1. Lipeng W., Zheng L., Qing C. et al. SSD-optimized workload placement with adaptive learning and classification in HPC environments // IEEE 30th Symposium on Mass Storage Systems and Technologies (MSST), 06/2014
  2. Beermann T. 2013 Popularity Prediction Tool for ATLAS Distributed Data Management // IOP Publishing: J. of Phys.: Conf. Ser. — 2014. 513, 042004
  3. Жианчанг Мао, Энил Джейн. Введение в искусственные нейронные сети // Открытые системы.СУБД. — 1997. — № 4. — С. 16–24. URL: http://www.osp.ru/os/1997/04/179189 (дата обращения: 18.12.2015).
  4. Rob J Hyndman, George Athanasopoulos. Forecasting: principles and practice. URL: https://www.otexts.org/fpp (дата обращения: 18.12.2015).

Михаил Гущин (mikhail91@yandex . ru) — Школа анализа данных «Яндекс», Московский физико-технический институт; Андрей Устюжанин (naderi@yandex.ru) — Школа анализа данных «Яндекс», Московский физико-технический институт, НИУ ВШЭ, НИЦ «Курчатовский институт» (Москва, Россия); Филипп Шарпентьер (Philippe.Charpentier@cern.ch) — ЦЕРН (Женева, Швейцария). Статья подготовлена на основе материалов доклада, представленного на VI Московском суперкомпьютерном форуме (МСКФ-2015, грант РФФИ 15-07-20824-г).