Карты пространства

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

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

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

Битовые карты

Наиболее распространенный способ представить свободное пространство - использовать битовую карту. Битовая карта - это просто битовый массив, в котором бит с номером N указывает, свободен ли блок с номером N. Накладные расходы на битовую карту невелики: 1 бит на блок. Для блока в 4Кб, это 1/(4096\*8) = 0,003% от размера блока (здесь 8 - количество бит в байте).

Для файловой системы в 1Гб битовая карта займет 32Кб -- её можно держать в оперативной памяти и довольно быстро сканировать для поиска свободного пространства. Для файловой системы в 1Тб размер битовой карты составит уже 32 Мб -- такой объём ещё можно уместить в оперативной памяти, но это уже нетривиально в смысле размера и времени сканирования. Битовая карта для файловой системы в 1Пб потребует уже 32Гб, и уже просто-напросто не поместится в оперативной памяти большинства машин. Следовательно, сканирование битовой карты в этом случае потребует её чтения с диска, который намного медленнее оперативной памяти.

Ясно, что такой способ плохо масштабируется.

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

Но это не избавляет нас от одной фундаментальной проблемы: битовые карты нужно обновлять не только когда выделяется новый блок, но и тогда, когда блок освобождается. Файловая система может управлять локальностью выделяемых блоков (решать, в каком месте размещать новые данные), но не имеет никакого способа влиять на положение освобождаемых блоков. Простая команда вроде 'rm -rf' может вызвать освобождение блоков, разбросанных по всему диску. Например, удаление 4Гб данных (т.е. миллиона блоков по 4Кб) из нашей файловой системы размером в 1Пб потребует, в худшем случае, чтения, изменения и повторной записи миллиона битовых карт. Это означает два миллиона дисковых операций ввода/вывода для освобождения каких-то 4Гб -- что неразумно даже в худшем случае.

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

Сбалансированные деревья

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

Что же делать?

Отложенное освобождение

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

А если пойти дальше?

Карты пространства: списки диапазонов с журнальной структурой

Вспомним, что файловые системы с журнальной структурой уже ставили такой вопрос довольно давно: что, если вместо периодической свёртки журнала транзакций обратно в файловую систему, сделать сам журнал транзакций файловой системой?

Такой же вопрос можно поставить и по отношению к нашему списку отложенных операций: что, если вместо свёртки в битовую карту или дерево сделать сам список отложенных операций представлением свободного пространства?

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

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

Карты пространства имеют несколько интересных свойств:

  • Не требуют инициализации: карта пространства без записей показывает, что операций выделения и освобождения блоков не было, все пространство доступно

  • Хорошо масштабируются: поскольку новые диапазоны только добавляются в конец объекта "карта пространства", для получения наилучшей производительности в памяти нужно хранить только лишь последний блок этого объекта, вне зависимости от того, пространством какого размера мы управляем

  • Не подвержены патологиям: карты пространства можно эффективно обновлять, независимо от последовательности операций выделения и освобождения

  • Одинаково эффективны при выделении свободного места, как при пустом, так и при заполненном пуле (в отличие от битовых карт, на сканирование которых требуется всё больше и больше времени по мере их наполнения)
Помимо этого, нужно отметить, что когда свободное пространство, описываемое картой, полностью исчерпано, для ее представления достаточно одного диапазона. Поэтому карты пространства имеют прекрасное свойство: по мере приближения заполненности пула к 100%, карты пространств�� начинают буквально "испаряться", занимая всё меньше и меньше места, давая возможность максимально использовать имеющееся дисковое пространство для хранения полезной информации.
Comments:

Post a Comment:
Comments are closed for this entry.
About

bonwick

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today